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

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (10): 37-39.

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

张翠军,邹慧,张有华

石家庄经济学院信息工程学院，石家庄 050031

收稿日期:2007-09-21 修回日期:2007-11-30 出版日期:2008-04-01 发布日期:2008-04-01
通讯作者: 张翠军

Hybrid ant colony algorithm based on quadratic assignment problem

ZHANG Cui-jun,ZOU Hui,ZHANG You-hua

College of Information and Technology，Shijiazhuang University of Economics，Shijiazhuang 050031，China

Received:2007-09-21 Revised:2007-11-30 Online:2008-04-01 Published:2008-04-01
Contact: ZHANG Cui-jun

摘要/Abstract

摘要： 二次分配问题是组合优化领域中经典的NP-hard问题之一，应用广泛。在对二次分配问题进行分析的基础上，提出了一种求解该问题的混合蚁群算法。该算法通过在蚁群算法中引入遗传算法的2-交换变异算子，增强了算法的局部搜索能力，提高了解的质量。实验结果表明，该算法在求解二次分配问题时优于蚁群算法和遗传算法。

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

Abstract: 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 search 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.

Key words: quadratic assignment problem, NP-hard problem, hybrid ant colony algorithm, 2-interchange mutation operator, local search

张翠军,邹慧,张有华. 基于二次分配问题的混合蚁群算法[J]. 计算机工程与应用, 2008, 44(10): 37-39.

ZHANG Cui-jun,ZOU Hui,ZHANG You-hua. Hybrid ant colony algorithm based on quadratic assignment problem[J]. Computer Engineering and Applications, 2008, 44(10): 37-39.

[1]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[2]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[3]	张明伟，李波，屈晓龙，郭盈. 基于混合蚁群算法的异质车队低碳VRP研究[J]. 计算机工程与应用, 2020, 56(14): 240-249.
[4]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[5]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[6]	董小帅1，2，3，毛政元1，2，3. 基于改进遗传算法的动态路径规划研究[J]. 计算机工程与应用, 2018, 54(19): 49-55.
[7]	吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1. 改进的差分演化算法求解多维背包问题[J]. 计算机工程与应用, 2018, 54(11): 153-160.
[8]	胡炜1，2，曾斌1，姚路1. 事件驱动下的重点海域监测站部署算法研究[J]. 计算机工程与应用, 2017, 53(7): 136-140.
[9]	宋强. 改进迭代局部搜索算法在MMTVRP中的应用[J]. 计算机工程与应用, 2017, 53(7): 248-255.
[10]	洪剑珂1，张峥华2，许贵平2. 基于加强概率控制策略的SAT局部搜索算法[J]. 计算机工程与应用, 2017, 53(14): 56-60.
[11]	王蒙，樊坤，翟亚飞，李心宁. 网络并行计算中多处理机任务调度问题研究[J]. 计算机工程与应用, 2017, 53(10): 264-270.
[12]	伍艳莲1，2，姜海燕1，2，庄嘉祥1，郭小清1，许一骅1. 精英策略个体优势遗传算法研究[J]. 计算机工程与应用, 2016, 52(7): 143-149.
[13]	林耿1，徐梅琴2. 图的最大二等分问题的一种离散填充函数算法[J]. 计算机工程与应用, 2016, 52(5): 27-32.
[14]	鲁宇明1，4，王彦超2，刘嘉瑞3，Wu Liu4. 一种改进的生物地理学优化算法[J]. 计算机工程与应用, 2016, 52(17): 146-151.
[15]	胡博. 基于均匀设计的免疫克隆多峰函数优化[J]. 计算机工程与应用, 2015, 51(2): 57-59.