Metaheuristics and Heuristics for Global Optimization Problems

点击翻译按钮获取中文摘要

The quadratic assignment problem (QAP) was introduced in 1957 as a mathematical model for the location of a set of indivisible economical activities. Consider the problem of allocating a set of facilities to a set of locations, with the cost being a function of the distance and flow between the facilities, plus costs associated with a facility being placed at a certain location. The objective is to assign each facility to a location such that the total cost is minimized. It was shown that the QAP is NP-hard (Non-deterministic Polynomial-time hard), and that even finding an approximate solution within some constant factor from the optimal solution cannot be done in polynomial time unless P=NP. In fact the QAP, in contrast with its linear counterpart the linear assignment problem, remains one of the hardest optimization problems and no exact algorithm can solve problems of size n > 20. QAP is an example of a global combinatorial optimization, important in operations research and theoretical computer science. Global optimization problems fall within the broader class of nonlinear optimization. Numerical algorithms for nonlinear optimization can be categorized into gradient-based methods and direct search methods. Gradient-based methods use gradients or Hessians while direct search methods do not use derivative information. In this project, we are interested in solving problems when the derivatives of the underlying data are unavailable, unreliable, or impractical to obtain. These algorithms are known as derivative-free algorithms. In this project, we consider metaheuristics and heuristics algorithms as derivative-free algorithms. Heuristic methods are approximate algorithms in which we seek to obtain good, that is, near-optimal solutions at relatively low computational cost without being able to guarantee the optimality of solutions. A disadvantage of heuristic methods is that they: Either generate only a very limited number of different solutions, or stop at poor quality local optima, which is the case for iterative improvement methods. Metaheuristics have been proposed which try to bypass these problems. A metaheuristic can be seen as a general purpose heuristic method toward promising regions of the search space containing high-quality solutions. Our objective from this project is to analyze, modify, and suggest some of the most common metaheuristics approaches, and show how these can be used to solve wireless sensor networks, output feedback pole assignment problems, CP/VIs/MPEC, minimax and integer programming problems. Finally, I am interested in combining metaheuristics algorithms with deterministic algorithms for the above problems. Finally, the proposed research program will enhance and promote the integration leading-edge research into interdisciplinary operations research and computer science education for Thompson Rivers University’s diverse student population.