一种求解QAP问题的混合嵌套分区优化算法  

A hybrid nested partitions optimization algorithm for the QAP problem

作　　者：武维[1] 卫军胡[2] 管晓宏[3] 

机构地区：[1]西安交通大学制造系统国家重点实验室,西安710049 [2]西安交通大学智能网络与网络安全教育部重点实验室,西安710049 [3]西安交通大学系统工程研究所,西安710049

出　　处：《控制与决策》2010年第6期889-893,898,共6页Control and Decision

基　　金：国家自然科学基金项目(60736027;60704033);国家863计划项目(2007AA04Z154);陕西省自然科学基础研究计划项目(2007F41)

摘　　要：提出一种基于嵌套分区算法(NPM)框架求解二次分配问题(QAP)的混合优化算法.算法利用嵌套分区树来描述二次分配过程,对可行域进行系统性分区,采用禁忌抽样算子对分区进行抽样并评估各个分区的性能.在每次迭代中,算法重点跟踪和搜索优良解最有希望出现的分区,并结合禁忌搜索算法来实现分区转移.数值仿真实验表明,引入更加有效的禁忌抽样算子后,NPM算法具有更好的寻优能力.This paper proposes a hybrid optimization algorithm based on nested partitions method（NPM） framework for solving quadratic assignment problem（QAP）.In the algorithm,the QAP is described as a nested partitions tree.The algorithm systematically partitions the feasible region and uses tabu search sampling operator to evaluate the performance of each subregion.In the each iteration,the algorithm focused on the most promising region for searching the optimal solutions.And the tabu search is incorporated into the sampling procedure to make the subregion correct move.The results of numerical experiments show that the hybrid algorithm has better performance.

关 键 词：嵌套分区算法 二次分配问题 禁忌搜索算法 组合优化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]