蚁群优化算法及其应用研究
|
摘要
组合优化问题的解决在理论和实际应用领域都有非常重要的地位。随着问题规模的扩大,因为计算复杂度的问题,如果使用确定性算法很多组合问题的最优解是无法实现的。蚁群优化元启发式算法是一种专门针对难解的离散优化问题的理想方法,它能在合理的时间得到能够接受的解。蚁群优化算法具有正反馈、分布式、鲁棒性强、易于与其它算法结合的优点。理论上讲,经过适当转化,蚁群优化算法可以解决任何组合优化问题。从最初的蚂蚁系统发展到现在众多的改进蚁群算法,蚁群算法在性能上已经取得了很大的进步。其应用已经涵盖了组合优化、连续函数优化、网络路由、机器学习、图像处理等众多学科。
本文主要围绕蚁群优化的原理、基本蚁群算法的改进、蚁群优化理论。就如何改进蚁群算法性能,如何改进算法的全局搜索能力进行了深入的研究。此外还总结了蚁群优化应用规则和使用蚁群优化求解问题的一般步骤,最后给出了一些典型的应用实例。主要研究成果如下:
提出一种改进蚁群算法,在转移概率公式中引入一个新的自适应因子以避免算法陷入局部最优解。随着迭代次数的增加,该因子有利于蚂蚁探索较弱信息素浓度的边而避免信息素浓度过度积累。这一特性使蚂蚁在迭代后期仍能以较高概率搜索到更好的解。仿真实验显示,改进后算法对解决旅行商问题有更优的全局搜索能力。
Discrete optimization plays a great role both in thoery and application. It’s almost impossible to retain the optimal solution with deterministic algorithm especially when the scale of the problem is very large. Ant colony optimization(ACO) belongs to meta-heristic algorithms and it can help us to obtain a reasonable optimal solution. ACO has such features as positive feedback, parallel computing,robustness and so on.Any discrete optimization can be settled by ACO if modified properly. Great breakthrough has been made in performance of ACO since the appearance of ant system. Its application includes discrete optimization, net routing, machine learning, image processing and so on.
This paper concentrates on the principle of ACO, improved versions of ant system,the theory, as well as stategies to improve the performance of the algorithm. The discipline and the main steps to apply ACO are also discussed in the paper. Besides, some instances are given to illustrate the great performance of ACO. The main contribution comes as follows:
An improved Ant Colony System (IACS), which employed a new factor in transition rule to overcome the premature behavior in (ACO) is proposed. The factor can help the ants to obtain a better result by exploring the arc with low pheromone trail accumulated so far as time elapses. Besides, it can avoid the over-concentration of pheromone trail to enlarge the searching range. Simulation results shows that the IACS has better performance in solving the Traveling Salesman Problems (TSP) and more outstanding global optimization properties.
本文主要围绕蚁群优化的原理、基本蚁群算法的改进、蚁群优化理论。就如何改进蚁群算法性能,如何改进算法的全局搜索能力进行了深入的研究。此外还总结了蚁群优化应用规则和使用蚁群优化求解问题的一般步骤,最后给出了一些典型的应用实例。主要研究成果如下:
提出一种改进蚁群算法,在转移概率公式中引入一个新的自适应因子以避免算法陷入局部最优解。随着迭代次数的增加,该因子有利于蚂蚁探索较弱信息素浓度的边而避免信息素浓度过度积累。这一特性使蚂蚁在迭代后期仍能以较高概率搜索到更好的解。仿真实验显示,改进后算法对解决旅行商问题有更优的全局搜索能力。
Discrete optimization plays a great role both in thoery and application. It’s almost impossible to retain the optimal solution with deterministic algorithm especially when the scale of the problem is very large. Ant colony optimization(ACO) belongs to meta-heristic algorithms and it can help us to obtain a reasonable optimal solution. ACO has such features as positive feedback, parallel computing,robustness and so on.Any discrete optimization can be settled by ACO if modified properly. Great breakthrough has been made in performance of ACO since the appearance of ant system. Its application includes discrete optimization, net routing, machine learning, image processing and so on.
This paper concentrates on the principle of ACO, improved versions of ant system,the theory, as well as stategies to improve the performance of the algorithm. The discipline and the main steps to apply ACO are also discussed in the paper. Besides, some instances are given to illustrate the great performance of ACO. The main contribution comes as follows:
An improved Ant Colony System (IACS), which employed a new factor in transition rule to overcome the premature behavior in (ACO) is proposed. The factor can help the ants to obtain a better result by exploring the arc with low pheromone trail accumulated so far as time elapses. Besides, it can avoid the over-concentration of pheromone trail to enlarge the searching range. Simulation results shows that the IACS has better performance in solving the Traveling Salesman Problems (TSP) and more outstanding global optimization properties.
引文
[1] Marco Dorigo, Thomas Stutzle. Ant Colony Optimization. 2004, The MIT Press. Cambridge, Masschusetts London, England.
[2] Applegate,D., Bixby,R., Chvatal ,V.,&Cook,W. On the solution of traveling salesman problems.Documenta Mathematica,Extra Volume ICM III,645-656.
[3] M. Dorigo. Optimiztion, Learning and Natural Algorithma(in Italian)[D]. Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, IT, 1992.
[4] Colorni A, Dorigo M, Maniezzo V, etal. Distributed optimization by ant colonies. Proceedings of the 1st European Conference on Artificial Life,1991,134-142.
[5] M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy[R]. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
[6] A. Colorni, M. Dorigo, and V. Maniezzo. Distributed optimization by ant colonies[C]. In Proceedings of the First European Conference onArtificial Life, Elsevier, 1992. 134-142.
[7] M.Dorigo, L.M.Gambardella. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[8] T. Stützle and H. Hoos. Improvements on the ant system: Introducing MAX–MIN ant system[C]. In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, Springer Verlag, Wien, 1997. 245–249.
[9] B. Bullnheimer, R. F. Hartl, and C. Strauss. A new rank-based version of the Ant System: A computational study[J]. Central European Journal for Operations Research and Economics, 7(1):25–38, 1999.
[10] C Blum,M Dorigo. The hyper-cube framework for ant colony optimization IEEE Transactions on Syetems[J], Man and Cybemetics, part B,2004, 34(2): 1161-1172.
[11] Stüezle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms [J] . IEEE Transactions on Evolutionary Computation , 2002 , 6 (4) :358-365
[12] Gutjahr W J . A graph-based ant system and its convergence [J] . Future Generation Computer Systems ,2000 , 16 (8) : 873-888.
[13] Yoo J H , La RJ , Makowski A M. Convergence results for ant routing [R] . Technical Report CSHCN 2003 - 46 ,Institute for Systems Research , University of Maryland ,College Park (MD) , 2003.
[14] Yoo J H , La R J , Makowski A M. Convergence of ant routing algorithms 2 results for simpleparallel network and perspectives[R] . Technical Report CSHCN 2003 - 44,Institute for Systems Research , University of Maryland ,College Park (MD) , 2003.
[15]孙焘,王秀坤,刘业欣等.一种简单蚂蚁算法及其收敛性分析[J].小型微型计算机系统,2003,21 (8):1524-1526.
[16]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析[J] .自动化学报, 2004 ,30 (4) : 659-634.
[17]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展.1999,36(10):1240-1243.
[18]张传升,萧蕴诗,吴纪伟.一种新的基于并行蚁群算法的旅行商问题求解方法的研究[J].微型电脑应用[J],2009,25 (2) : 59-62.
[19]李建明,胡祥培,庞占龙,钱昆明.一种基于GPU加速的细粒度并行蚁群算法[J].控制与决策[J].2009,24(8):1132-1136.
[20]郑松,侯迪波,周泽魁.动态调整选择策略的改进蚁群算法[J].控制与决策,2008,23(2)225-228.
[21]杨勇,胡上序等.蚁群算法求解连续空间优化问题[J].控制与决策, 2003,18(5):573-576.
[22]黄美玲,白似雪.蚁群神经网络在旅行商问题中的应用[J].计算机辅助设计与图形学学报. 2007,5:600-603.
[23]闭应洲,丁立新,陆建波.基于免疫修复的快速蚁群优化算法[J],控制与决策, 2009, 10:1509-1512.
[24] Deneubourg,J.-L,Aron,S.,&Pasteels,J.-M.The self-organizing exploratory pattern of the Argentine ant .Journal of Insect Behavior, 1990, 3: 159-168.
[25] Dorigo,M.,Maniezzo,V.,&Colorni,A.. Ant System: Optimization by a colony of cooperating angents.IEEE Transactions on Syestem,Man,and Cybernetics-Part B, ,1996,26(1):29-41.
[26] T. Stützle and H. Hoos. MAX–MIN Ant system and local search for combinatorial optimization problems[M]. In S. Vo?, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 137–154. Kluwer, Boston, 1998.
[27] W. J. Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution[J]. Info. Processing Lett., 2002, 8(3): 145–153.
[28] Thomas Stützle and Marco Dorigo. A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms[J]. IEEE Transactions on Evolutionary Computation, 2002,6(4): 358-365.
[29] Lee SG, Jung TU, Chung TC. An effective dynamic weighted rule for ant colony sysytem optimization[C].In:Proc.of the 2001 Congress on Evolutionary Computation,2001.
[30]胡小兵,黄席樾,张著洪.一种新的自适应蚁群算法及其应用[J].计算机仿真.2004,4:(108-111).
[31] Watkins,C.J.,&Dayan,P. Q-learning.Machine Learning, 1992,8: 279-292.
[32] Sutton,R. S., &Barto,A,G.. Reforcement Learning:An Introduction. Cambridge,MA,MIT Press 1998.
[33] Gambardella, L. M., Dorigo. M Solving symmetric and asymmetric TSPs by ant colonies[J]. Proceedings of the IEEE International Conference on Evolutionary Computation, 1996, 622-627.
[34]薛晗,李迅,马宏绪.生存模糊自适应的蚁群算法及收敛性[J].控制与决策.2009, 249: 1288-1293.
[35] TSPLIB-ATraveling Salesman Problem Library. http://www.iwr.uni-heidelberg.de /groups/comopt/software/TSPLIB95/tsp/.
[36]梁云川,李德玉.个体变异蚁群算法在TSP问题中的应用研究[J],西南大学学报, 2009.3.
[37]段海滨.蚁群算法原理及其应用[M].北京:科学出版社.2005.
[38]郝晋,石立宝,周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程与实践,2002,9:88-92.
[39]李玉英,温巧燕,李丽香,彭海朋,朱辉.改进的混沌蚂蚁群算法[J].仪器仪表学报,2009,4:733-737.
[40]吴建辉,章兢,刘朝华.基于蚁群算法和免疫算法融合的TSP问题求解[J].湖南大学学报,2009.10:81—87.
[41]黄美玲,白似雪.蚁群神经网络在旅行商问题中的应用[J].计算机辅助设计与图形学学报.2007,5:600—603.
[42]杨佳等.一种新的量子蚁群优化算法[J].中山大学学报.2009, 3: 22-27.
[43]闭应洲,丁立新,陆建波.基于免疫修复的快速蚁群优化算法[J],控制与决策, 2009.10:1509-1512.
[44] Yoo J H , La RJ , Makowski A M. Convergence results for ant routing [R] . Technical Report CSHCN 2003 - 46 ,Institute for Systems Research , University of Maryland ,College Park (MD) , 2003.
[45]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析[J] .自动化学报, 2004 ,30 (4) : 659-634.
[46] T. Stützle . MAX-MIN Ant System for Quadratic Assignment Problems[R]. Technical Report AIDA-97-04, Intellectics Group, Department of Computer Science, Darmstadt University of Technology, Germany, July 1997.
[47] Socha,K., Knowles,J., &Sampels, M.Ant algrithms for the university course timetablingproblem with regard to the state-of-art.Applications of Evolutionary Computating,Proceedings of Evo Workshops 2003,vol 2611 of Lecture Notes in Computer Science Berlin,Springer-Verlag: 334-345.
[48] R.S.Parpinelli, H.S.Lopes and A.A.Freitas. Ant ant colony algorithm for classification rule disbovery.In H.A.Abbass,R.A.Sarker,and C.S.Newton(Eds.), Data Mining:A Heuristic Approach. Hershey,PA,Idea Group Publishing,2002: 191-208.
[49] R.S.Parpinelli, H.S.Lopes and A.A.Freitas. Data mining with an ant colony optimization algorithm.IEEE Transactions on Evolutionary Computation, 2002,6(4):321-332,.
[50] De Campos,L,M.,Fernandez-Luna,J.M.,Gamez,J.A.,&Puerta,J.M. Ant colony optimization for learning Bayesian networks.International Journal of Approximate Reasoning, 2002,31(3) :291-311.
[51] Gamez,J.A., &Puerta,J.M. Searching the best elimination sequence in Bayesian networks by using ant colony optimization. Pattern Recognition Letters, 2002,23(1-3):261-277.
[52] Schoonderwoerd,R., Holland,O., Bruten,J., &Rothkrantz,L. Ant-based load balancing in telecommunications networds. Adapative Behavior,1996,5(2):169-207.
[53]苗京,黄红星,程卫生,袁启勋.基于蚁群模糊聚类算法的图像边缘检测.武汉大学学报(工学版).2005,38(5):124-127.
[54]高德威,陈天煌,刘朋.蚁群算法在图像边缘检测上的应用.计算机与数字工程.2009, 1(37):131-134.
[55]周爽,张钧萍,张枫,苏宝库.基于蚁群算法的遥感图像聚类方法.哈尔滨工程大学学报.2009,30 (2): 210-215.
[2] Applegate,D., Bixby,R., Chvatal ,V.,&Cook,W. On the solution of traveling salesman problems.Documenta Mathematica,Extra Volume ICM III,645-656.
[3] M. Dorigo. Optimiztion, Learning and Natural Algorithma(in Italian)[D]. Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, IT, 1992.
[4] Colorni A, Dorigo M, Maniezzo V, etal. Distributed optimization by ant colonies. Proceedings of the 1st European Conference on Artificial Life,1991,134-142.
[5] M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy[R]. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
[6] A. Colorni, M. Dorigo, and V. Maniezzo. Distributed optimization by ant colonies[C]. In Proceedings of the First European Conference onArtificial Life, Elsevier, 1992. 134-142.
[7] M.Dorigo, L.M.Gambardella. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[8] T. Stützle and H. Hoos. Improvements on the ant system: Introducing MAX–MIN ant system[C]. In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, Springer Verlag, Wien, 1997. 245–249.
[9] B. Bullnheimer, R. F. Hartl, and C. Strauss. A new rank-based version of the Ant System: A computational study[J]. Central European Journal for Operations Research and Economics, 7(1):25–38, 1999.
[10] C Blum,M Dorigo. The hyper-cube framework for ant colony optimization IEEE Transactions on Syetems[J], Man and Cybemetics, part B,2004, 34(2): 1161-1172.
[11] Stüezle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms [J] . IEEE Transactions on Evolutionary Computation , 2002 , 6 (4) :358-365
[12] Gutjahr W J . A graph-based ant system and its convergence [J] . Future Generation Computer Systems ,2000 , 16 (8) : 873-888.
[13] Yoo J H , La RJ , Makowski A M. Convergence results for ant routing [R] . Technical Report CSHCN 2003 - 46 ,Institute for Systems Research , University of Maryland ,College Park (MD) , 2003.
[14] Yoo J H , La R J , Makowski A M. Convergence of ant routing algorithms 2 results for simpleparallel network and perspectives[R] . Technical Report CSHCN 2003 - 44,Institute for Systems Research , University of Maryland ,College Park (MD) , 2003.
[15]孙焘,王秀坤,刘业欣等.一种简单蚂蚁算法及其收敛性分析[J].小型微型计算机系统,2003,21 (8):1524-1526.
[16]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析[J] .自动化学报, 2004 ,30 (4) : 659-634.
[17]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展.1999,36(10):1240-1243.
[18]张传升,萧蕴诗,吴纪伟.一种新的基于并行蚁群算法的旅行商问题求解方法的研究[J].微型电脑应用[J],2009,25 (2) : 59-62.
[19]李建明,胡祥培,庞占龙,钱昆明.一种基于GPU加速的细粒度并行蚁群算法[J].控制与决策[J].2009,24(8):1132-1136.
[20]郑松,侯迪波,周泽魁.动态调整选择策略的改进蚁群算法[J].控制与决策,2008,23(2)225-228.
[21]杨勇,胡上序等.蚁群算法求解连续空间优化问题[J].控制与决策, 2003,18(5):573-576.
[22]黄美玲,白似雪.蚁群神经网络在旅行商问题中的应用[J].计算机辅助设计与图形学学报. 2007,5:600-603.
[23]闭应洲,丁立新,陆建波.基于免疫修复的快速蚁群优化算法[J],控制与决策, 2009, 10:1509-1512.
[24] Deneubourg,J.-L,Aron,S.,&Pasteels,J.-M.The self-organizing exploratory pattern of the Argentine ant .Journal of Insect Behavior, 1990, 3: 159-168.
[25] Dorigo,M.,Maniezzo,V.,&Colorni,A.. Ant System: Optimization by a colony of cooperating angents.IEEE Transactions on Syestem,Man,and Cybernetics-Part B, ,1996,26(1):29-41.
[26] T. Stützle and H. Hoos. MAX–MIN Ant system and local search for combinatorial optimization problems[M]. In S. Vo?, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 137–154. Kluwer, Boston, 1998.
[27] W. J. Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution[J]. Info. Processing Lett., 2002, 8(3): 145–153.
[28] Thomas Stützle and Marco Dorigo. A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms[J]. IEEE Transactions on Evolutionary Computation, 2002,6(4): 358-365.
[29] Lee SG, Jung TU, Chung TC. An effective dynamic weighted rule for ant colony sysytem optimization[C].In:Proc.of the 2001 Congress on Evolutionary Computation,2001.
[30]胡小兵,黄席樾,张著洪.一种新的自适应蚁群算法及其应用[J].计算机仿真.2004,4:(108-111).
[31] Watkins,C.J.,&Dayan,P. Q-learning.Machine Learning, 1992,8: 279-292.
[32] Sutton,R. S., &Barto,A,G.. Reforcement Learning:An Introduction. Cambridge,MA,MIT Press 1998.
[33] Gambardella, L. M., Dorigo. M Solving symmetric and asymmetric TSPs by ant colonies[J]. Proceedings of the IEEE International Conference on Evolutionary Computation, 1996, 622-627.
[34]薛晗,李迅,马宏绪.生存模糊自适应的蚁群算法及收敛性[J].控制与决策.2009, 249: 1288-1293.
[35] TSPLIB-ATraveling Salesman Problem Library. http://www.iwr.uni-heidelberg.de /groups/comopt/software/TSPLIB95/tsp/.
[36]梁云川,李德玉.个体变异蚁群算法在TSP问题中的应用研究[J],西南大学学报, 2009.3.
[37]段海滨.蚁群算法原理及其应用[M].北京:科学出版社.2005.
[38]郝晋,石立宝,周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程与实践,2002,9:88-92.
[39]李玉英,温巧燕,李丽香,彭海朋,朱辉.改进的混沌蚂蚁群算法[J].仪器仪表学报,2009,4:733-737.
[40]吴建辉,章兢,刘朝华.基于蚁群算法和免疫算法融合的TSP问题求解[J].湖南大学学报,2009.10:81—87.
[41]黄美玲,白似雪.蚁群神经网络在旅行商问题中的应用[J].计算机辅助设计与图形学学报.2007,5:600—603.
[42]杨佳等.一种新的量子蚁群优化算法[J].中山大学学报.2009, 3: 22-27.
[43]闭应洲,丁立新,陆建波.基于免疫修复的快速蚁群优化算法[J],控制与决策, 2009.10:1509-1512.
[44] Yoo J H , La RJ , Makowski A M. Convergence results for ant routing [R] . Technical Report CSHCN 2003 - 46 ,Institute for Systems Research , University of Maryland ,College Park (MD) , 2003.
[45]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析[J] .自动化学报, 2004 ,30 (4) : 659-634.
[46] T. Stützle . MAX-MIN Ant System for Quadratic Assignment Problems[R]. Technical Report AIDA-97-04, Intellectics Group, Department of Computer Science, Darmstadt University of Technology, Germany, July 1997.
[47] Socha,K., Knowles,J., &Sampels, M.Ant algrithms for the university course timetablingproblem with regard to the state-of-art.Applications of Evolutionary Computating,Proceedings of Evo Workshops 2003,vol 2611 of Lecture Notes in Computer Science Berlin,Springer-Verlag: 334-345.
[48] R.S.Parpinelli, H.S.Lopes and A.A.Freitas. Ant ant colony algorithm for classification rule disbovery.In H.A.Abbass,R.A.Sarker,and C.S.Newton(Eds.), Data Mining:A Heuristic Approach. Hershey,PA,Idea Group Publishing,2002: 191-208.
[49] R.S.Parpinelli, H.S.Lopes and A.A.Freitas. Data mining with an ant colony optimization algorithm.IEEE Transactions on Evolutionary Computation, 2002,6(4):321-332,.
[50] De Campos,L,M.,Fernandez-Luna,J.M.,Gamez,J.A.,&Puerta,J.M. Ant colony optimization for learning Bayesian networks.International Journal of Approximate Reasoning, 2002,31(3) :291-311.
[51] Gamez,J.A., &Puerta,J.M. Searching the best elimination sequence in Bayesian networks by using ant colony optimization. Pattern Recognition Letters, 2002,23(1-3):261-277.
[52] Schoonderwoerd,R., Holland,O., Bruten,J., &Rothkrantz,L. Ant-based load balancing in telecommunications networds. Adapative Behavior,1996,5(2):169-207.
[53]苗京,黄红星,程卫生,袁启勋.基于蚁群模糊聚类算法的图像边缘检测.武汉大学学报(工学版).2005,38(5):124-127.
[54]高德威,陈天煌,刘朋.蚁群算法在图像边缘检测上的应用.计算机与数字工程.2009, 1(37):131-134.
[55]周爽,张钧萍,张枫,苏宝库.基于蚁群算法的遥感图像聚类方法.哈尔滨工程大学学报.2009,30 (2): 210-215.