基于混沌的MMAS算法及其在旅行商问题中的应用

doi:10.3969/j.issn.1000-3428.2016.03.035

计算机工程

基于混沌的MMAS算法及其在旅行商问题中的应用

耿志强,邱大洪,韩永明

(北京化工大学信息科学与技术学院,北京 100029)

收稿日期:2015-01-16 出版日期:2016-03-15 发布日期:2016-03-15
作者简介:耿志强(1973-),男,教授、博士生导师,主研方向为系统建模与优化、数据挖掘、机器学习;邱大洪,硕士研究生;韩永明,讲师、博士。
基金资助:
国家自然科学基金资助项目(61374166);教育部博士点基金资助项目(20120010110010);中央高校基本科研业务费专项基金资助项目(YS1404)。

Max-min Ant System Algorithm Based on Chaos and Its Application in TSP

GENG Zhiqiang,QIU Dahong,HAN Yongming

(College of Information Science & Technology,Beijing University of Chemical Technology,Beijing 100029,China)

Received:2015-01-16 Online:2016-03-15 Published:2016-03-15

摘要/Abstract

摘要：

最大最小蚂蚁系统算法初始信息素均匀分布,但存在无法快速进行全局搜索,容易出现停滞并陷入局部最优的缺点。为此,通过引入全局遍历性能更优的Tent混沌映射,提出一种基于混沌的最大最小蚁群改进算法。利用混沌的遍历特性产生一组较优路径指导初始信息素的非均匀分布,运用混沌扰动的方法增强算法跳出局部最优的能力。以较大规模旅行商问题为应用对象进行实验,结果表明,改进算法具有更高的全局寻优成功率和更快的收敛速度。

关键词: 混沌, Tent映射, 最大最小蚂蚁系统, 旅行商问题, 信息素

Abstract:

In Max-min Ant System(MMAS) algorithm,initial pheromone distributes well,it can not reach global search,which is easy to stop and falls into local optima.Therefore an improved MMAS algorithm is proposed based on Tent chaotic mapping to enhance the capability of escaping from local optima.This method generates a group of candidates to guide the distribution of pheromone by exploiting ergodic property of chaos.When the searching stagnation is appeared,a chaotic disturbance method is utilized to obtain a better solution.Results among different ant colony optimization algorithm on large-scale Traveling Salesman Problem(TSP) show that the improved algorithm has higher success rate and faster convergence rate for global optimization.

Key words: chaos, Tent mapping, Max-min Ant System(MMAS), Traveling Salesman Problem(TSP), pheromone

中图分类号:

TP18

耿志强,邱大洪,韩永明. 基于混沌的MMAS算法及其在旅行商问题中的应用[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.03.035.

GENG Zhiqiang,QIU Dahong,HAN Yongming. Max-min Ant System Algorithm Based on Chaos and Its Application in TSP[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.03.035.

https://www.ecice06.com/CN/Y2016/V42/I3/192

参考文献

参考文献［1］Dorigo M,Maniezzo V,Colorni A.Ant System:Optimization by a Colony of Cooperating Agents［J］.IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,1996,26(1):2941. ［2］Johnson D S,Mcgeoch L A.The Traveling Salesman Problem:A Case Study in Local Optimization［M］.New York,USA:John Wiley and Sons,Inc.,1996. ［3］Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem［J］.IEEE Transactions on Evolu tionary Computation,1997,1(1):5366. ［4］Stutzle T,Hoos H H.Maxmin Ant System［J］.Future Generation Computer Systems,2000,16(8):889914. ［5］Yu Weijie,Zhang Jun.Pheromone Distribution Based Adaptive Ant Colony System［C］//Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation.Portland,USA:［s.n.］,2010:3138. ［6］Abdelbar A M.Is There a Computational Advantage to Representing Evaporation Rate in Ant Colony Optimization as a Gaussian Random Variable［ C］//Proceedings of the 14th International Conference on Genetic and Evolutionary Computation Conference.New York,USA:ACM Press,2012:18. ［7］Abdelbar A M,Wunsch D C.Improving the Performance of MaxMin Ant System on the TSP Using Stubborn Ants［C］//Proceedings of the 14th Inter national Conference on Genetic and Evolutionary Computation.New York,USA:ACM Press,2012:13951396. ［8］李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法［J］.控制与决策,2013,28(6):873878. ［9］薛锋,王慈光,牟峰.基于信息熵和混沌理论的遗传蚁群协同优化算法［J］.控制与决策,2011,26(1):4448. ［10］孟祥萍,片兆宇,沈中玉,等.基于方向信息素协调的蚁群算法［J］.控制与决策,2013,28(5):782786. ［11］郑松,侯迪波,周泽魁.动态调整选择策略的改进蚁群算法［J］.控制与决策,2008,23(2):225228. ［12］杨海,王洪国,侯鲁男,等.混沌蚁群算法及其在智能交通中的应用［J］.成都大学学报:自然科学版,2008,26(4):309312. ［13］刘晓莹,蔡自兴,余伶俐,等.一种正交混沌蚁群算法在群机器人任务规划中的应用研究［J］.小型微型计算机系统,2010,31(1):165167. ［14］Tavazoei M S,Haeri M.Comparison of Different Onedimensional Maps as Chaotic Search Pattern in Chaos Optimization Algorithms［J］.Applied Mathematics and Computation,2007,187(2):10761085. ［15］柯亨通.基于最大最小蚁群算法的配电网优化重构研究［D］.武汉:华中科技大学,2013. ［16］柳贺,黄猛,黄道.基于混沌搜索的优化方法的研究进展［J］.南京理工大学学报:自然科学版,2005,29(S1):130134. ［17］Gambardella L M,Dorigo M.AntQ:A Reinforcement Learning Approach to the TSP［C］//Proceedings of the 12th International Conference on Machine Learning.Washington D.C.,USA:IEEE Press,1995:252260. 编辑索书志

[1]	葛非, 闵珊, 邱含, 代振阳, 杨智敏. 求解时间依赖型绿色车辆路径问题的算法研究[J]. 计算机工程, 2024, 50(4): 1-10.
[2]	杜鹏, 崔琦, 王思翔, 董有恒, 李晖. 基于新型时空混沌系统的隐私图像加密算法[J]. 计算机工程, 2024, 50(2): 140-153.
[3]	付雪, 朱良宽, 黄建平, 王璟瑀, ARYSTANRyspayev. 基于改进北方苍鹰优化算法的多阈值图像分割[J]. 计算机工程, 2023, 49(7): 232-241.
[4]	韦丞婧, 李国东. 结合超混沌系统和Logistic映射的视频图像加密算法[J]. 计算机工程, 2022, 48(5): 263-271.
[5]	王改云, 陆家卓, 焦傲, 郭智超, 张琦. 混沌粒子群鸡群融合优化的RSSI质心定位算法[J]. 计算机工程, 2021, 47(6): 197-202.
[6]	夏磊, 杨华, 宋玉蓉. 多用户载波索引差分混沌移位键控通信系统及性能分析[J]. 计算机工程, 2021, 47(5): 181-188.
[7]	刘鹏飞, 杜欣军. 基于加权反馈三维混沌系统的调制跳变通信[J]. 计算机工程, 2021, 47(3): 183-189,195.
[8]	曾祥秋, 叶瑞松. 基于改进Logistic映射的混沌图像加密算法[J]. 计算机工程, 2021, 47(11): 158-165,174.
[9]	杨吉云, 姚锐冬, 周洁, 高凌云. 基于切比雪夫混沌映射的车联网高效认证方案[J]. 计算机工程, 2021, 47(10): 34-42,51.
[10]	杜学武, 张明新, 沙广涛, 伍秋玉. 基于改进蝙蝠算法的模糊PID规则优化研究[J]. 计算机工程, 2020, 46(8): 305-312.
[11]	龙浩, 张书奎, 张力. 群智感知中基于维诺单元的隐私保护方法[J]. 计算机工程, 2020, 46(5): 181-186,192.
[12]	王若愚, 陈勇全. 基于强化学习的旅行商问题解构造方法[J]. 计算机工程, 2020, 46(11): 293-300.
[13]	魏德宾, 刘健, 潘成胜, 邹启杰. 卫星网络中基于多QoS约束的蚁群优化路由算法[J]. 计算机工程, 2019, 45(7): 114-120.
[14]	邵良杉, 兰亭洋, 李臣浩. 基于改进花朵授粉算法的极限学习机模型[J]. 计算机工程, 2019, 45(12): 281-288.
[15]	曹蕾. 基于快速响应码约束的光学图像加密算法[J]. 计算机工程, 2019, 45(1): 121-128.

选择文件类型/文献管理软件名称

选择包含的内容

基于混沌的MMAS算法及其在旅行商问题中的应用

Max-min Ant System Algorithm Based on Chaos and Its Application in TSP

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于混沌的MMAS算法及其在旅行商问题中的应用

Max-min Ant System Algorithm Based on Chaos and Its Application in TSP

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价