基于搜索集中度和动态信息素更新的蚁群算法
|
摘要
蚁群算法是一种启发式搜索算法,被广泛应用于求解复杂的组合优化问题。基本蚁群算法存在收敛速度慢和早熟停滞等问题,针对这些问题,提出了一种基于搜索集中度和动态信息素更新的蚁群算法。通过在选择策略中引入"搜索集中度"因子,让算法可以自适应的调节蚂蚁选择城市的范围,在此基础上采用动态改变信息素增量和信息素回滚的机制,缩短了搜索时间,也使算法更容易跳出局部极值。仿真实验结果表明,改进后的算法算法具有较快的收敛速度,提高了解的全局性,有效避免了算法陷入局部最优。
Ant colony algorithm is a kind of heuristic search algorithms.It has been widely used to solve complex combinatorial optimization problems.Basic ant colony algorithm has some disadvantages,such as slow convergence and premature stagnation.In order to overcome these problems,we propose an improved ant colony algorithm,which is based on search concentration and dynamic pheromone updating.Specifically, by introducing the "Search Concentration"factor in the selection strategy,the algorithm can adaptively adjust the range of cities selected by the ants.In addition,increments of pheromone are dynamically changed and a kind of pheromone rollback mechanism is used.As a result,the search time are shortened and the algorithm is more easy to jump out of the local extremum.Simulation experimental results show that the improved algorithm has a faster convergence speed,improves the global understanding,and effectively avoids the algorithm falling into local optimum.
Ant colony algorithm is a kind of heuristic search algorithms.It has been widely used to solve complex combinatorial optimization problems.Basic ant colony algorithm has some disadvantages,such as slow convergence and premature stagnation.In order to overcome these problems,we propose an improved ant colony algorithm,which is based on search concentration and dynamic pheromone updating.Specifically, by introducing the "Search Concentration"factor in the selection strategy,the algorithm can adaptively adjust the range of cities selected by the ants.In addition,increments of pheromone are dynamically changed and a kind of pheromone rollback mechanism is used.As a result,the search time are shortened and the algorithm is more easy to jump out of the local extremum.Simulation experimental results show that the improved algorithm has a faster convergence speed,improves the global understanding,and effectively avoids the algorithm falling into local optimum.
引文
[1]DORIGO M, MANIEZZO V,COLORNI A.Ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems Man &Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man &Cybernetics Society,1996,26(1):29.
[2]夏亚梅,程渤,陈俊亮,等.基于改进蚁群算法的服务组合优化[J].计算机学报,2012,35(2):270-281.
[3]李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878,883.
[4]吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013,34(4):165-170.
[5]李成兵,郭瑞雪,李敏.改进蚁群算法在旅行商问题中的应用[J].计算机应用,2014,34(S1):131-132,165.
[6]肖菁,李亮平.基于信息熵调整的自适应蚁群算法[J].计算机工程与设计,2010,31(22):4873-4876.
[7]游晓明,刘升,吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策,2017,32(3):552-556.
[8]孙泽宇,魏巍.一种改进蚁群算法组合优化问题的研究[J].计算机仿真,2010,27(8):194-197.
[9]朱庆保,杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报,2004,15(2):185-192.
[10]覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制,2002,31(3):198-201.
[11]刘瑞杰,胡小兵.基于动态调节信息素增量的蚁群算法[J].计算机应用研究,2012,29(1):135-136.
[12]夏小云,周育人.蚁群优化算法的理论研究进展[J].智能系统学报,2016,11(1):27-36.
[13]陈峻,章春芳.并行蚁群算法中的自适应交流策略[J].软件学报,2007,18(3):617-624.
[14]周文.我国城市集中度对经济发展的影响及其机制——基于面板数据的实证研究[J].经济社会体制比较,2015(4):76-87.
[15]郑卫国,田其冲,张磊.基于信息素强度的改进蚁群算法[J].计算机仿真,2010,27(7):191-193.
[16]刘浩然,孙美婷,李雷,等.基于蚁群节点寻优的贝叶斯网络结构算法研究[J].仪器仪表学报,2017,38(1):143-150.
[2]夏亚梅,程渤,陈俊亮,等.基于改进蚁群算法的服务组合优化[J].计算机学报,2012,35(2):270-281.
[3]李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878,883.
[4]吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013,34(4):165-170.
[5]李成兵,郭瑞雪,李敏.改进蚁群算法在旅行商问题中的应用[J].计算机应用,2014,34(S1):131-132,165.
[6]肖菁,李亮平.基于信息熵调整的自适应蚁群算法[J].计算机工程与设计,2010,31(22):4873-4876.
[7]游晓明,刘升,吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策,2017,32(3):552-556.
[8]孙泽宇,魏巍.一种改进蚁群算法组合优化问题的研究[J].计算机仿真,2010,27(8):194-197.
[9]朱庆保,杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报,2004,15(2):185-192.
[10]覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制,2002,31(3):198-201.
[11]刘瑞杰,胡小兵.基于动态调节信息素增量的蚁群算法[J].计算机应用研究,2012,29(1):135-136.
[12]夏小云,周育人.蚁群优化算法的理论研究进展[J].智能系统学报,2016,11(1):27-36.
[13]陈峻,章春芳.并行蚁群算法中的自适应交流策略[J].软件学报,2007,18(3):617-624.
[14]周文.我国城市集中度对经济发展的影响及其机制——基于面板数据的实证研究[J].经济社会体制比较,2015(4):76-87.
[15]郑卫国,田其冲,张磊.基于信息素强度的改进蚁群算法[J].计算机仿真,2010,27(7):191-193.
[16]刘浩然,孙美婷,李雷,等.基于蚁群节点寻优的贝叶斯网络结构算法研究[J].仪器仪表学报,2017,38(1):143-150.