基于细菌觅食的改进蚁群算法
|
摘要
蚁群算法是模仿蚂蚁觅食行为的一种新的仿生学智能优化算法。针对其收敛速度慢和易陷入局部最优的不足,将细菌觅食算法和蚁群算法相结合,提出一种细菌觅食-蚁群算法。在蚁群算法迭代过程中,引入细菌觅食算法的复制操作,以加快算法的收敛速度;引入细菌觅食算法的趋向操作,以增强算法的全局搜索能力。通过经典的旅行商问题和函数优化问题测试表明,细菌觅食-蚁群算法在寻优能力、可靠性、收敛效率和稳定性方面均优于基本蚁群算法及两种改进蚁群算法。
Ant colony optimization is a new bionic intelligent optimization algorithm to mimics the foraging behavior of ants.Aiming at the problems of local optimum and slow convergence speed of ant colony optimization,we propose a bacteria foraging ant colony optimization algorithm by combining the bacterial foraging algorithm with the ant colony algorithm.In the iterative process of ant colony optimization,a reproduction process is introduced to the ant colony optimization to accelerate the convergence speed.A chemo taxis process is introduced to enhance the global searching ability.Simulation experiments on the classic traveling salesman problem and function optimization problem show that,compared with the traditional ant colony optimization and two improved ant colony optimization algorithms,the proposed algorithm is more effective in optimization capability,reliability,convergence efficiency and stability.
Ant colony optimization is a new bionic intelligent optimization algorithm to mimics the foraging behavior of ants.Aiming at the problems of local optimum and slow convergence speed of ant colony optimization,we propose a bacteria foraging ant colony optimization algorithm by combining the bacterial foraging algorithm with the ant colony algorithm.In the iterative process of ant colony optimization,a reproduction process is introduced to the ant colony optimization to accelerate the convergence speed.A chemo taxis process is introduced to enhance the global searching ability.Simulation experiments on the classic traveling salesman problem and function optimization problem show that,compared with the traditional ant colony optimization and two improved ant colony optimization algorithms,the proposed algorithm is more effective in optimization capability,reliability,convergence efficiency and stability.
引文
[1] Min Ke-xue,Ge Hong-wei,Zhang Yi,et al.Solving traveling salesman problems by an ACO-and-PSO-based hybrid algorithm[J].Journal of Jilin University(Information Science Edition),2006,25(4):402-405.(in Chinese)
[2] Hu Xiang-pei,Ding Qiu-lei,Li Yong-xian.A review on ant colony system[J].Journal of Industrial Engineering and Engineering Management,2008,22(2):74-79.(in Chinese)
[3] Wang Lei,Li Ming,Liu Zhi-hu.Application of an ant colony optimization based on attractive field in TSP[J].Journal of Jiangsu University(Natural Science Edition),2015,36(5):573-577.(in Chinese)
[4] Duan Hai-bin,Wang Dao-bo,Yu Xiu-fen,et al.Improvement of ant colony algorithm based on cloud models theory[J].Journal of Harbin Institute of Technology,2005,37(1):115-119.(in Chinese)
[5] Yu B,Yang Z Z,Yao B Z.An improved ant colony optimization for vehicle routing problem[J].European Journal of Operational Research,2009,196(1):171-176.
[6] Sun Kai,Wu Hong-xing,Wang Hao,et al.Hybrid ant colony and particle swarm algorithm for solving TSP[J].Computer Engineering and Applications,2012,48(34):60-63.(in Chinese)
[7] Wu Hua-feng,Chen Xin-qiang,Mao Qi-huang,et al.Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J].Journal on Communications,2013,34(4):165-170.(in Chinese)
[8] Liu Zhen,Hu Yun-an.Multi-granularity pattern ant colony optimization algorithm and its application in path planning[J].Journal of Central South University(Science and Technology),2013,44(9):3713-3722.(in Chinese)
[9] Kalayci C B,Kaya C.An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications,2016,66(C):163-175.
[10] Dorigo M.Optimization,learning and natural algorithms[D].Italy:Politecnico di Milano,1992.
[11] Yang Xue-feng.Ant colony algorithm for TSP problem[D].Changchun:Jilin University,2010.(in Chinese)
[12] Li Shi-wei,Wang Jian-qiang,Zeng Jun-wei.Model of ant colony algorithm parameters optimization based on genetic algorithm[J].Computer Engineering and Design,2011,32(10):3490-3493.(in Chinese)
[13] Liu Y,Passino K M.Biomimicry of social foraging bacteria for distributed optimization:Models,principles,and emergent behaviors[J].Journal of Optimization Theory and Applications,2002,115(3):603-628.
[14] Hu Jie.Research on the modified bacteria foraging optimization algorithm and its application[D].Wuhan:Wuhan University of Technology,2012.(in Chinese)
[15] Zhou Zi-lian,Yang Jin,Ma Liang.A hybrid bacteria foraging algorithm for solving the traveling salesman problem[J].Mathematics in Practice and Theory,2015,45(16):159-165.(in Chinese)
[16] Wang Yong-zhen,Chen Yan,Li Tao-ying,et al.Discrete bacteria foraging optimization algorithm for solving TSP[J].Application Research of Computers,2014,31(12):3642-3645.(in Chinese)
[17] TSPLIB[EB/OL].[2016-12-10].http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/.
[18] Zhang Li-yi,Fei Teng,Liu Ting,et al.Application in medical device emergency logistics distribution routing optimization based on chaos ant colony optimization[J].Journal of Civil Aviation University of China,2011,29(3):61-64.(in Chinese)
[19] Zhang Li-yi,Wang Ying,Fei Teng,et al.Research on low carbon logistics routing optimization based on chaotic-simulated annealing ant colony algorithm[J].Computer Engineering and Applications,2017,53(1):63-68.(in Chinese)
[20] Zhou Kang,Qiang Xiao-li,Tong Xiao-jun,et a1.Algorithm of TSP[J].Computer Engineering and Applications,2007,43(29):43-47.(in Chinese)
[21] Ye Zhi-wei,Zheng Zhao-bao.Configuration of parametersα,β,ρin ant algorithm[J].Geomatics and Information Science of Wuhan University,2004,29(7):597-601.(in Chinese)
[22] Fei Teng,Zhang Li-yi,Bai Yu,et al.Improved artificial fish swarm algorithm based on DNA[J].Journal of Tianjin University(Science and Technology),2016,49(6):581-588.(in Chinese)
[1]闵克学,葛宏伟,张毅,等.基于蚁群和粒子群优化的混合算法求解TSP问题[J].吉林大学学报(信息科学版),2006,25(4):402-405.
[2]胡祥培,丁秋雷,李永先.蚁群算法研究评述[J].管理工程学报,2008,22(2):74-79.
[3]王雷,李明,刘志虎.基于吸引场的蚁群算法在TSP中的应用[J].江苏大学学报(自然科学版),2015,36(5):573-577.
[4]段海滨,王道波,于秀芬,等.基于云模型理论的蚁群算法改进研究[J].哈尔滨工业大学学报,2005,37(1):115-119.
[6]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.
[7]吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013,34(4):165-170.
[8]刘振,胡云安.一种多粒度模式蚁群算法及其在路径规划中的应用[J].中南大学学报(自然科学版),2013,44(9):3713-3722.
[11]杨学峰.蚁群算法求解TSP问题的研究[D].长春:吉林大学,2010.
[12]李世威,王建强,曾俊伟.遗传算法调整蚁群算法参数模型研究[J].计算机工程与设计,2011,32(10):3490-3493.
[14]胡洁.细菌觅食优化算法的改进及应用研究[D].武汉:武汉理工大学,2012.
[15]周自廉,杨进,马良.基于混合的细菌觅食算法求解TSP问题[J].数学的实践与认识,2015,45(16):159-165.
[16]王勇臻,陈燕,李桃迎.离散型细菌觅食算法求解TSP[J].计算机应用研究,2014,31(12):3642-3645.
[18]张立毅,费腾,刘婷,等.基于混沌蚁群算法的应急物流路径优化算法[J].中国民航大学学报,2011,29(3):61-64.
[19]张立毅,王迎,费腾,等.混沌扰动模拟退火蚁群算法低碳物流路径优化[J].计算机工程与应用,2017,53(1):63-68.
[20]周康,强小利,同小军,等.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47.
[21]叶志伟,郑肇葆.蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例[J].武汉大学学报(信息科学版),2004,29(7):597-601.
[22]费腾,张立毅,白煜,等.基于DNA的改进人工鱼群算法[J].天津大学学报(自然科学与工程技术版),2016,49(6):581-588.
[2] Hu Xiang-pei,Ding Qiu-lei,Li Yong-xian.A review on ant colony system[J].Journal of Industrial Engineering and Engineering Management,2008,22(2):74-79.(in Chinese)
[3] Wang Lei,Li Ming,Liu Zhi-hu.Application of an ant colony optimization based on attractive field in TSP[J].Journal of Jiangsu University(Natural Science Edition),2015,36(5):573-577.(in Chinese)
[4] Duan Hai-bin,Wang Dao-bo,Yu Xiu-fen,et al.Improvement of ant colony algorithm based on cloud models theory[J].Journal of Harbin Institute of Technology,2005,37(1):115-119.(in Chinese)
[5] Yu B,Yang Z Z,Yao B Z.An improved ant colony optimization for vehicle routing problem[J].European Journal of Operational Research,2009,196(1):171-176.
[6] Sun Kai,Wu Hong-xing,Wang Hao,et al.Hybrid ant colony and particle swarm algorithm for solving TSP[J].Computer Engineering and Applications,2012,48(34):60-63.(in Chinese)
[7] Wu Hua-feng,Chen Xin-qiang,Mao Qi-huang,et al.Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J].Journal on Communications,2013,34(4):165-170.(in Chinese)
[8] Liu Zhen,Hu Yun-an.Multi-granularity pattern ant colony optimization algorithm and its application in path planning[J].Journal of Central South University(Science and Technology),2013,44(9):3713-3722.(in Chinese)
[9] Kalayci C B,Kaya C.An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications,2016,66(C):163-175.
[10] Dorigo M.Optimization,learning and natural algorithms[D].Italy:Politecnico di Milano,1992.
[11] Yang Xue-feng.Ant colony algorithm for TSP problem[D].Changchun:Jilin University,2010.(in Chinese)
[12] Li Shi-wei,Wang Jian-qiang,Zeng Jun-wei.Model of ant colony algorithm parameters optimization based on genetic algorithm[J].Computer Engineering and Design,2011,32(10):3490-3493.(in Chinese)
[13] Liu Y,Passino K M.Biomimicry of social foraging bacteria for distributed optimization:Models,principles,and emergent behaviors[J].Journal of Optimization Theory and Applications,2002,115(3):603-628.
[14] Hu Jie.Research on the modified bacteria foraging optimization algorithm and its application[D].Wuhan:Wuhan University of Technology,2012.(in Chinese)
[15] Zhou Zi-lian,Yang Jin,Ma Liang.A hybrid bacteria foraging algorithm for solving the traveling salesman problem[J].Mathematics in Practice and Theory,2015,45(16):159-165.(in Chinese)
[16] Wang Yong-zhen,Chen Yan,Li Tao-ying,et al.Discrete bacteria foraging optimization algorithm for solving TSP[J].Application Research of Computers,2014,31(12):3642-3645.(in Chinese)
[17] TSPLIB[EB/OL].[2016-12-10].http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/.
[18] Zhang Li-yi,Fei Teng,Liu Ting,et al.Application in medical device emergency logistics distribution routing optimization based on chaos ant colony optimization[J].Journal of Civil Aviation University of China,2011,29(3):61-64.(in Chinese)
[19] Zhang Li-yi,Wang Ying,Fei Teng,et al.Research on low carbon logistics routing optimization based on chaotic-simulated annealing ant colony algorithm[J].Computer Engineering and Applications,2017,53(1):63-68.(in Chinese)
[20] Zhou Kang,Qiang Xiao-li,Tong Xiao-jun,et a1.Algorithm of TSP[J].Computer Engineering and Applications,2007,43(29):43-47.(in Chinese)
[21] Ye Zhi-wei,Zheng Zhao-bao.Configuration of parametersα,β,ρin ant algorithm[J].Geomatics and Information Science of Wuhan University,2004,29(7):597-601.(in Chinese)
[22] Fei Teng,Zhang Li-yi,Bai Yu,et al.Improved artificial fish swarm algorithm based on DNA[J].Journal of Tianjin University(Science and Technology),2016,49(6):581-588.(in Chinese)
[1]闵克学,葛宏伟,张毅,等.基于蚁群和粒子群优化的混合算法求解TSP问题[J].吉林大学学报(信息科学版),2006,25(4):402-405.
[2]胡祥培,丁秋雷,李永先.蚁群算法研究评述[J].管理工程学报,2008,22(2):74-79.
[3]王雷,李明,刘志虎.基于吸引场的蚁群算法在TSP中的应用[J].江苏大学学报(自然科学版),2015,36(5):573-577.
[4]段海滨,王道波,于秀芬,等.基于云模型理论的蚁群算法改进研究[J].哈尔滨工业大学学报,2005,37(1):115-119.
[6]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.
[7]吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013,34(4):165-170.
[8]刘振,胡云安.一种多粒度模式蚁群算法及其在路径规划中的应用[J].中南大学学报(自然科学版),2013,44(9):3713-3722.
[11]杨学峰.蚁群算法求解TSP问题的研究[D].长春:吉林大学,2010.
[12]李世威,王建强,曾俊伟.遗传算法调整蚁群算法参数模型研究[J].计算机工程与设计,2011,32(10):3490-3493.
[14]胡洁.细菌觅食优化算法的改进及应用研究[D].武汉:武汉理工大学,2012.
[15]周自廉,杨进,马良.基于混合的细菌觅食算法求解TSP问题[J].数学的实践与认识,2015,45(16):159-165.
[16]王勇臻,陈燕,李桃迎.离散型细菌觅食算法求解TSP[J].计算机应用研究,2014,31(12):3642-3645.
[18]张立毅,费腾,刘婷,等.基于混沌蚁群算法的应急物流路径优化算法[J].中国民航大学学报,2011,29(3):61-64.
[19]张立毅,王迎,费腾,等.混沌扰动模拟退火蚁群算法低碳物流路径优化[J].计算机工程与应用,2017,53(1):63-68.
[20]周康,强小利,同小军,等.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47.
[21]叶志伟,郑肇葆.蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例[J].武汉大学学报(信息科学版),2004,29(7):597-601.
[22]费腾,张立毅,白煜,等.基于DNA的改进人工鱼群算法[J].天津大学学报(自然科学与工程技术版),2016,49(6):581-588.