求解圆排列问题的粒子群蚁群优化算法

doi:10.16182/j.issn1004731x.joss.201702003

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (2): 248-254.doi: 10.16182/j.issn1004731x.joss.201702003

求解圆排列问题的粒子群蚁群优化算法

徐小平¹, 朱秋秋¹, 王峰²

1.西安理工大学理学院,西安 710054;
2.西安交通大学数学与统计学院,西安 710049

收稿日期:2015-03-25 修回日期:2015-10-24 出版日期:2017-02-08 发布日期:2020-06-01
作者简介:徐小平(1973-),男,陕西蓝田,博士,副教授,研究方向为进化算法,系统建模理论等。
基金资助:
国家自然科学基金(61273127), 陕西省教育厅专项科研计划(14JK1538), 西安理工大学科技创新计划项目(2016CX013)

Particle Swarm Ant Colony Optimization Algorithm for Solving Circle Permutation Problem

Xu Xiaoping¹, Zhu Qiuqiu¹, Wang Feng²

1. School of sciences, Xi'an University of Technology, Xi'an 710054, China;
2. School of Mathematics and Statistics Sciences, Xi'an Jiaotong University, Xi'an 710049, China

Received:2015-03-25 Revised:2015-10-24 Online:2017-02-08 Published:2020-06-01

摘要/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

中图分类号:

TP301

徐小平, 朱秋秋, 王峰. 求解圆排列问题的粒子群蚁群优化算法[J]. 系统仿真学报, 2017, 29(2): 248-254.

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.

参考文献

[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.)

求解圆排列问题的粒子群蚁群优化算法

Particle Swarm Ant Colony Optimization Algorithm for Solving Circle Permutation Problem

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[2]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[3]	宁涛, 苟涛, 刘向东. 考虑低碳约束的生鲜农产品冷链物流策略仿真研究[J]. 系统仿真学报, 2022, 34(4): 797-805.
[4]	胡蓉, 陈文博, 钱斌, 郭宁, 向凤红. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
[5]	唐婕, 曹瑾鑫. 共享汽车联合调度优化研究[J]. 系统仿真学报, 2021, 33(8): 1959-1968.
[6]	王霄汉, 张霖, 任磊, 谢堃钰, 王昆玉, 叶飞, 陈真. 基于强化学习的车间调度问题研究简述[J]. 系统仿真学报, 2021, 33(12): 2782-2791.
[7]	王青云, 焦德忠, 史铄, 彭根燕, 孙俊华, 段雨昕. 改进的蚁群干扰资源分配方法[J]. 系统仿真学报, 2021, 33(12): 2967-2974.
[8]	王闯, 张勇, 李学贵, 董宏丽. 改进粒子群优化算法及其在聚类分析中应用[J]. 系统仿真学报, 2020, 32(8): 1577-1587.
[9]	杨卫, 曾亮, 康新晨. 基于蚁群算法的群机器人自组织聚集行为建模[J]. 系统仿真学报, 2020, 32(2): 191-200.
[10]	史岩, 张立华, 董受全, 王珏. 基于ACO算法和Bezier曲线优化的巡航导弹航路规划[J]. 系统仿真学报, 2020, 32(1): 122-129.
[11]	陈海亮, 陈彬, 袁鹏, 董健, 艾川. 基于观测数据的社交网络推断方法研究[J]. 系统仿真学报, 2019, 31(12): 2712-2720.
[12]	张会丽, 李志河. 一种基于HNN的云服务组合优化[J]. 系统仿真学报, 2019, 31(11): 2335-2343.
[13]	叶多福, 刘刚, 何兵. 一种多染色体遗传算法解决多旅行商问题[J]. 系统仿真学报, 2019, 31(1): 36-42.
[14]	曾艳阳, 张泽浩, 冯云霞. 自适应可调混沌粒子群算法的体绘制视点选择[J]. 系统仿真学报, 2018, 30(12): 4595-4601.
[15]	仇永斌, 张树春, 王元诚, 范文澜, 李德鑫. 最优粒子初值有效估计的线阵列方向图优化算法[J]. 系统仿真学报, 2018, 30(11): 4079-4085.