Metaheuristics and Heuristics for Global Optimization Problems

全局优化问题的元启发式和启发式

• 批准号: RGPIN-2015-05522
• 负责人: Tawhid, Mohamed
• 金额: $ 1.31万
• 依托单位: Thompson Rivers University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=613600
• 关键词: Metaheuristics; Heuristics; 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.

二次分配问题（QAP）于1957年被引入，作为一组不可分割的经济活动位置的数学模型。考虑将一组设施分配到一组位置的问题，成本是设施之间的距离和流量的函数，加上与放置在某个位置的设施相关的成本。目标是将每个设施分配到一个位置，以使总成本最小化。结果表明，QAP是NP-难（非确定性多项式时间困难），即使找到一个近似的解决方案，从一些常数因子的最优解不能在多项式时间内完成，除非P=NP。事实上，QAP与其线性对应的线性分配问题相比，仍然是最困难的优化问题之一，并且没有精确的算法可以解决大小n > 20的问题。QAP是全局组合优化的一个例子，在运筹学和理论计算机科学中很重要。全局优化问题属于更广泛的非线性优化类别。 非线性优化的数值算法可以分为基于梯度的方法和直接搜索方法。基于导数的方法使用梯度或Hessian，而直接搜索方法不使用导数信息。在这个项目中，我们感兴趣的是解决问题时，衍生的基础数据是不可用的，不可靠的，或不切实际的获得。这些算法被称为无导数算法。在这个项目中，我们认为元算法和元算法是无导数算法。启发式方法是一种近似算法，在这种算法中，我们寻求以相对较低的计算成本获得好的，即接近最优的解决方案，而不能保证算法的最优性。 解决方案启发式方法的缺点是：要么只生成非常有限数量的不同解决方案，要么停在质量较差的局部最优解，即 迭代改进方法。元分析学已经被提出，试图绕过这些问题。元启发式可以被看作是一种通用的启发式方法，用于搜索包含高质量解决方案的有希望的搜索空间区域。 我们的目标是从这个项目是分析，修改，并建议一些最常见的元算法的方法，并显示这些可以用来解决无线传感器网络，输出反馈极点配置问题，CP/维斯/MPEC，极大极小和整数规划问题。最后，我对将元启发式算法与确定性算法结合起来解决上述问题很感兴趣。最后，拟议的研究计划将加强和促进整合前沿研究到跨学科的运筹学和计算机科学教育汤普森河流大学的多样化的学生群体。