Hybrid ant colony algorithm based on quadratic assignment problem

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (10): 37-39.

• 理论研究 • Previous Articles Next Articles

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

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

张翠军,邹慧,张有华

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

通讯作者: 张翠军

Abstract

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

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

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

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.

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

[1]	XU Chenhua, LUO Zhuguang, WU Guanhong, LIU Bin. Grey Wolf Optimization Algorithm Based on Sine Factor and Quantum Local Search [J]. Computer Engineering and Applications, 2021, 57(24): 83-89.
[2]	HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei. Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[3]	ZHANG Mingwei, LI Bo, QU Xiaolong, GUO Ying. Research on Low Carbon VRP of Heterogeneous Fleet Based on Hybrid Ant Colony Algorithm [J]. Computer Engineering and Applications, 2020, 56(14): 240-249.
[4]	YAN Miaomiao, LIU Sanyang. Multi-Classes Interaction Teaching-Learning-Based Optimization Algorithm [J]. Computer Engineering and Applications, 2019, 55(9): 10-16.
[5]	LIU Chunmiao, ZHANG Huizhen. Hybrid bat algorithm for un-capacitated facility location problem [J]. Computer Engineering and Applications, 2018, 54(22): 28-34.
[6]	DONG Xiaoshuai1，2，3, MAO Zhengyuan1，2，3. Research on solution of dynamic Vehicle Routing Problem based on improved genetic algorithm [J]. Computer Engineering and Applications, 2018, 54(19): 49-55.
[7]	WU Congcong1, ZHAO Jianli1，2, LIU Xuejing1, CHEN Yiying1. Modified differential evolution algorithm for solving multidimensional knapsack problem [J]. Computer Engineering and Applications, 2018, 54(11): 153-160.
[8]	HU Wei1,2, ZENG Bin1, YAO Lu1. Algorithm on deployment of monitoring station focused on key sea area driven by events [J]. Computer Engineering and Applications, 2017, 53(7): 136-140.
[9]	SONG Qiang. Application of improved iterated local search algorithm in MMTVRP [J]. Computer Engineering and Applications, 2017, 53(7): 248-255.
[10]	HONG Jianke1, ZHANG Zhenghua2, XU Guiping2. SAT local search algorithm based on enhanced probability controlling strategies [J]. Computer Engineering and Applications, 2017, 53(14): 56-60.
[11]	WANG Meng, FAN Kun, ZHAI Yafei, LI Xinning. Study of multiprocessor task scheduling problem in network parallel computing system [J]. Computer Engineering and Applications, 2017, 53(10): 264-270.
[12]	WU Yanlian1，2, JIANG Haiyan1，2, ZHUANG Jiaxiang1, GUO Xiaoqing1, XU Yihua1. Research of individual advantages genetic algorithm based on elitist strategy [J]. Computer Engineering and Applications, 2016, 52(7): 143-149.
[13]	LIN Geng1, XU Meiqin2. Discrete filled function method for max-bisection problem [J]. Computer Engineering and Applications, 2016, 52(5): 27-32.
[14]	LU Yuming1，4, WANG Yanchao2, LIU Jiarui3, Wu Liu4. Improved biogeography-based optimization algorithm [J]. Computer Engineering and Applications, 2016, 52(17): 146-151.
[15]	HU Bo. Multi-model function optimization based on immune clonal optimization with uniform design [J]. Computer Engineering and Applications, 2015, 51(2): 57-59.

Hybrid ant colony algorithm based on quadratic assignment problem

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics