Metaheuristics and Heuristics for Global Optimization Problems

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

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

二次分配问题（QAP）作为一组不可分割的经济活动的定位数学模型于1957年提出。考虑将一组设施分配到一组地点的问题，成本是设施之间的距离和流量的函数，加上与设施放置在某一地点有关的成本。目标是将每个设施分配到一个位置，使总成本最小化。证明了QAP是NP-hard (Non-deterministic polynomial -time hard)，并且即使在最优解的某个常数因子内找到近似解也不能在多项式时间内完成，除非P=NP。事实上，与线性分配问题相比，QAP仍然是最难的优化问题之一，没有精确的算法可以解决规模为n的问题。QAP是全局组合优化的一个例子，在运筹学和理论计算机科学中很重要。全局优化问题属于广义的非线性优化问题。