Particle Swarm Ant Colony Optimization Algorithm for Solving Circle Permutation Problem

doi:10.16182/j.issn1004731x.joss.201702003

Abstract

Abstract: A particle swarm ant colony optimization algorithm of solving circle permutation problem was proposed. Based on the basis of analyzing relationship between circular permutation problem and traveling salesman problem, circular permutation problem was translated into traveling salesman problem, and it was further transformed into an optimization problem. In order to further improve the performance of the algorithm, here, four kinds of new scheme were proposed to solve circular permutation problem based on particle swarm ant colony optimization algorithm. In the simulation experiments, compared with the existing algorithm, the simulation results show that the proposed method is reasonable and feasible. Namely, the proposed four kinds of new algorithm have fast convergence speed and optimal performance.

Key words: circle permutation problem, traveling salesman problem, combinatorial optimization, particle swarm optimization algorithm, ant colony algorithm

CLC Number:

TP301

Xu Xiaoping, Zhu Qiuqiu, Wang Feng. Particle Swarm Ant Colony Optimization Algorithm for Solving Circle Permutation Problem[J]. Journal of System Simulation, 2017, 29(2): 248-254.

References

[1] Applegate D L, Bixby R E, Chvatal V, et al.The Traveling Salesman Problem: A Computational Study [M]. Princeton, USA: Princeton University Press, 2011.
[2] 麻存瑞, 马昌喜. 不确定旅行商问题的鲁棒模型与算法[J]. 计算机应用, 2014, 34(7): 2090-2092.
(Ma Cunrui, Ma Changxi.Robust Model and Algorithms for Uncertain Traveling Salesman Problem[J]. Journal of Computer Applications, 2014, 34(7): 2090-2092.)
[3] 王庆, 刘学鹏. 基于流水算法的旅行商问题求解[J]. 预测, 2014, 33(1): 65-69.
(Wang Qing, Liu Xuepeng.Solution for Travelling Salesman Problem Based on Flowing Water Algorithm[J]. Forecasting, 2014, 33(1): 65-69.)
[4] 杨金勇, 宋海洲. 圆排列包装问题最优解解析[J]. 华侨大学学报, 2013, 34(2): 221-224.
(Yang Jinyong, Song Haipeng.Solving Circle Permutation Packing Problem[J]. Journal of Huaqiao University, 2013, 34(2): 221-224.)
[5] 杨巍, 刘占良. 农机作业路径优化的研究-基于旅行商问题新算法[J]. 农机化研究, 2014, 36(6): 54-57.
(Yang Wei, Liu Zhanliang.Research on the Optimization of Agricultural Machinery Operation Path-Based on Traveling Salesman Problem New Algorithm[J], Journal of Agricultural Mechanization Research, 2014, 36(6): 54-57.)
[6] 刘明, 张培勇. 求解多旅行商问题的新混合遗传算法-以应急物资为例[J]. 系统管理学报, 2014, 23(2): 247-254.
(Liu Ming, Zhang Peiyong.A New Hybrid Genetic Algorithm for Multiple Traveling Salesman Problem-Taking Emergency Supplies as an Example[J]. Journal of Systems Management, 2014, 23(2): 247-254.)
[7] Costa D, Hertz A.Ants can colour graphs[J]. Journal of the Operational Research Society (S0160-5682), 1997, 48(3): 295-305.
[8] Kuntz P, Layzell P, Snyers D.A Colony of Ant-like Agents for Partitioning in VLSI Technology[C]// Proceedings of the 4th European Conference on Artificial Life. Boston, USA, 1997. USA: IEEE, 1997: 417-424.
[9] Schoonderwoerd R, Holland O, Bruten J.Ant like Agents for Loadbalancing in Telecommunications Networks[C]// Proceedings of Agemts'97 Marinadel del Rey, Washington, USA, USA: ACM, 1997: 209-216.
[10] Di Caro G, Dorigo M.Mobile Agents for Adaptive Routing[C]// Proceedings of the 31st Hawaii International Conference on System. Los Alamitos, USA, 1998. USA: IEEE, 1998: 74-83.
[11] Bullnheimer B, Hartl R F, Strauss C.Applying the Ant System to the Vehicle Routing Problem[J]. Meta- Heuristics: Advances and Trends in Local Search Paradigms for Optimization (S0092-2102), 1998, 89(8): 109-120.
[12] Colorni A, Dorigo M, Maniezzo V, et al.Ant System for Job Shop Scheduling[J]. Belgian of Operations Research Statistics and Computer Science (S1098-7371), 1994, 34(1): 39-53.
[13] Kennedy J F, Eberhart R C.Particle Swarm Optimization[C]// Proceedings of IEEE International Conference on Neural Networks, Perth, Australia, 1995. USA: IEEE, 1995: 1942-1948.
[14] 纪震, 廖惠连, 吴青华. 粒子群优化算法及应用 [M]. 北京: 科学出版社, 2009.
(Ji Zheng, Liao Huilian, Wu Qinghua.Particle Swarm Optimization Algorithm and Its Application [M]. Beijing, China: Science Press, 2009.)
[15] Yan Z, Deng C, Zhou J, et al.A Novel Two- subpopulation Particle Swam Optimization[C]// Proceedings of 10th Intelligent Control and Automation, Beijing, China, 2012. USA: IEEE, 2012: 4113-4117.
[16] Muruganandham A, Wahida Banu Dr S D. Adaptive Fractal Image Compression Using PSO[J]. Procedia Computer Science (S1877-0509), 2010, 2(2): 338-344.
[17] Wei Ding.A New Method for Image Noise Removal Using Chaos PSO and Nonlinear ICA[J]. Procedia Engineering (S1877-7058), 2011, 24(1): 111-115.
[18] Yu Z, Li J, Liu K.Radar Emitter Recognition based on PSO-BP Network[J]. AASRI Procedia (S2212-6716), 2012, 1(4): 213-219.
[19] Hu Y, Wang X.PSO-based Energy-balanced Double Cluster-heads Clustering Routing for Wireless Sensor Networks[J]. Procedia Engineering (S1877-7058), 2011, 24(15): 3073-3077.
[20] 刘俊杰, 巴海涛. 基于粒子群优化的观测站部署算法[J]. 指挥控制与仿真, 2014, 36(3): 40-43.
(Liu Junjie, Ba Haitao.Management of Multi-sensor Based on Particle Swarm Optimization[J]. Command Control & Simulation, 2014, 36(3): 40-43.)
[21] 史峰, 王辉, 郁磊, 等. 智能算法30个案例分析 [M]. 北京: 北京航空航天大学出版社, 2010.
(Shi Feng, Wang Hui, Yu Lei, et al.Intelligent Algorithms 30 Case Analysis [M]. Beijing, China: Beihang University Press, 2010.)
[22] 高尚, 杨静宇, 吴小俊, 等. 圆排列问题的蚁群模拟退火算法[J]. 系统工程理论与实践, 2004, 8(8): 102-106.
(Gao shang, Yang Jingyu, Wu Xiaojun, et al. Solving Circle Permutation Problem with Ant Colony Simulated Annealing Algorithm[J]. System Engineering Theory & Practice, 2004, 8(8): 102-106.)
[23] 章义刚, 王会颖. 改进蚁群算法求解圆排列问题[J]. 机电工程, 2008, 25(5): 92-95.
(Zhang Yigang, Wang Huiying.An Improved Ant Colony Algorithm of Solving Circle Permutation Problem[J]. Mechanical & Electrical Engineering Magazine, 2008, 25(5): 92-95.)