基于二次分配问题的混合蚁群算法  

Hybrid ant colony algorithm based on quadratic assignment problem

作　　者：张翠军[1] 邹慧[1] 张有华[1] 

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031

出　　处：《计算机工程与应用》2008年第10期37-39,共3页Computer Engineering and Applications

基　　金：国家高技术研究发展计划(863)(the National High-Tech Research and Development Plan of China under Grant No.2006AA06Z233);河北省科学技术研究与发展项目(No.06213553)

摘　　要：二次分配问题是组合优化领域中经典的NP-hard问题之一,应用广泛。在对二次分配问题进行分析的基础上,提出了一种求解该问题的混合蚁群算法。该算法通过在蚁群算法中引入遗传算法的2-交换变异算子,增强了算法的局部搜索能力,提高了解的质量。实验结果表明,该算法在求解二次分配问题时优于蚁群算法和遗传算法。Quadratic assignment problem is one of the classical NP-hard problems in combinatorial optimization field.It is known for its diverse applications.Based on the analysis about quadratic assignment problem,a hybrid ant colony algorithm for solving it is designed.It adopts 2-interchange mutation operator in ant colony algorithm to increase its ability of local searvh and to improve the quality of the solution.The experiment results show that the algorithm is superior to ant colony algorithm and genetic algorithm in solving quadratic assignment problem.

关 键 词：二次分配问题 NP-HARD问题 混合蚁群算法 2-交换变异算子 局部搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]