求解组合优化问题的混合蛙跳算法的研究
|
摘要
群体智能算法是一种高效的优化算法。由单个结构复杂的个体所完成的任务可由大量结构简单的个体所组成的群体合作来完成,并且后者往往更具有健壮性、灵活性和经济上的优势。在无集中控制且不提供全局模型的前提下,群体智能算法为解决组合优化问题提供了一种新对策。
混合蛙跳算法是一种新兴的群体智能算法。目前,利用混合蛙跳算法求解组合优化问题的相关成果不多见。本文对于如何利用混合蛙跳算法求解组合优化问题进行了探讨。主要研究成果如下：
首先,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解对子种群中的最差个体施加影响,这种优化方式是对子种群中的单一个体施加影响。在第三章中,本文提出了一种利用全局最优解“指导”每个子种群整体向前进化的策略。与传统的混合蛙跳算法不同,这种子种群进化策略可以同时作用于多个个体,是一种并行爬山的进化方式。随着城市数量的增加,常见的演化算法容易陷入局部极值的陷阱,无法搜索到全局最优路径。由于将郭涛算法和混合蛙跳算法的优点进行了有机的结合,“当前最优解作用于整个子种群”的混合蛙跳算法在求解TSP问题时表现出了良好的性能,能够以极小的时间代价搜索到用户的满意解。
其次,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解“吸引”每个子种群中的最差青蛙。通过这种“吸引”的作用,这两个个体指导了最差青蛙的进化方向。与传统的混合蛙跳算法不同,本文利用子种群中的其它个体对最差的个体的“排斥”作用来指导最差青蛙的进化方向。第四章中,本文利用“排斥最差个体”的混合蛙跳算法求解背包问题,该算法能够高效率地搜索到问题的全局最优解。
Swarm intelligence algorithm is an efficient optimization algorithm. Large amount of simple individuals have more advantages over a single complex one. The simple individuals often show better performance on robustness、flexibility and a smaller economic cost. Swarm intelligence provides a new way to solve the combinational optimization problems without global control and global model.
The Shuffled Frog Leaping algorithm(SFLA) is a kind of rising swarm intelligence optimizer. Currently, there is rare research on the use of SFLA to solve the combinatorial optimization problems. The thesis presents how to solve the combinatorial optimization problems with the SFLA. The primary contents and results are following
Firstly, the traditional SFLA depends on the global best result and the local best result to improve the worst ones in each sub-population. The strategy imposes on the worst frog in each sub-population. In chapter 3, a new improved strategy was proposed in the simple neighborhood search. The global best result guides each sub-population to achieve a better performance. The strategy is different from the traditional one, it can act on the sub-population instead of a single one.With the city number increases, the traditional evolutionary algorithms may easily fall into the trap of local search, they can not find the global optimal solution. The improved algorithm can efficiently solve the TSP, it can find a satisfactory solution at a small cost.
Secondly, the traditional SFLA uses the global best frog and the local best frog to attract the worst frog in each sub-population. They guide the worst one to be a better one. A new improved strategy was proposed in the simple neighborhood search which makes use of the repulsion between the other frogs in the sub-population and the worst frog.In chapter 4, we see the algorithm can efficiently find the KP's global optimal solution.
混合蛙跳算法是一种新兴的群体智能算法。目前,利用混合蛙跳算法求解组合优化问题的相关成果不多见。本文对于如何利用混合蛙跳算法求解组合优化问题进行了探讨。主要研究成果如下：
首先,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解对子种群中的最差个体施加影响,这种优化方式是对子种群中的单一个体施加影响。在第三章中,本文提出了一种利用全局最优解“指导”每个子种群整体向前进化的策略。与传统的混合蛙跳算法不同,这种子种群进化策略可以同时作用于多个个体,是一种并行爬山的进化方式。随着城市数量的增加,常见的演化算法容易陷入局部极值的陷阱,无法搜索到全局最优路径。由于将郭涛算法和混合蛙跳算法的优点进行了有机的结合,“当前最优解作用于整个子种群”的混合蛙跳算法在求解TSP问题时表现出了良好的性能,能够以极小的时间代价搜索到用户的满意解。
其次,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解“吸引”每个子种群中的最差青蛙。通过这种“吸引”的作用,这两个个体指导了最差青蛙的进化方向。与传统的混合蛙跳算法不同,本文利用子种群中的其它个体对最差的个体的“排斥”作用来指导最差青蛙的进化方向。第四章中,本文利用“排斥最差个体”的混合蛙跳算法求解背包问题,该算法能够高效率地搜索到问题的全局最优解。
Swarm intelligence algorithm is an efficient optimization algorithm. Large amount of simple individuals have more advantages over a single complex one. The simple individuals often show better performance on robustness、flexibility and a smaller economic cost. Swarm intelligence provides a new way to solve the combinational optimization problems without global control and global model.
The Shuffled Frog Leaping algorithm(SFLA) is a kind of rising swarm intelligence optimizer. Currently, there is rare research on the use of SFLA to solve the combinatorial optimization problems. The thesis presents how to solve the combinatorial optimization problems with the SFLA. The primary contents and results are following
Firstly, the traditional SFLA depends on the global best result and the local best result to improve the worst ones in each sub-population. The strategy imposes on the worst frog in each sub-population. In chapter 3, a new improved strategy was proposed in the simple neighborhood search. The global best result guides each sub-population to achieve a better performance. The strategy is different from the traditional one, it can act on the sub-population instead of a single one.With the city number increases, the traditional evolutionary algorithms may easily fall into the trap of local search, they can not find the global optimal solution. The improved algorithm can efficiently solve the TSP, it can find a satisfactory solution at a small cost.
Secondly, the traditional SFLA uses the global best frog and the local best frog to attract the worst frog in each sub-population. They guide the worst one to be a better one. A new improved strategy was proposed in the simple neighborhood search which makes use of the repulsion between the other frogs in the sub-population and the worst frog.In chapter 4, we see the algorithm can efficiently find the KP's global optimal solution.
引文
[1]胡中功,李静.群智能算法的研究进展[J].自动化技术与应用,2008,27(2)
[2]Holland J. Adaptation in Natural and Artificial Systems[M].University of Michigan Press, Ann Arbor, MIT,1975
[3]M H Alsuwaiyel.算法设计技巧与分析[M].电子工业出版社,2006
[4]潘正君,康立山,陈磂屏.演化计算[M].清华大学出版社,1998
[5]王辉,钱峰.群体智能优化算法[J].化工自动化及仪表,2007,34(5)
[6]王玫,朱云龙,何小贤.群体智能研究综述[J].计算机工程,2007,31(22)
[7]Eusuff M M, Lansey K E.Optimization of water distribution network design using shuffled frog leaping algorithm[J] Journal of Water Resources Planning and Management,2003,129(3):210-225
[8]Elbeltagi E, Hegazy T, Grierson D.Comparison among five evolutionary-based optimization algorithms[J].Advanced Engineering Informatics,2005,19(1):43-53
[9]Muzaffar Eusuff, Kevin Lansey, Fayzul Pasha.Shuffled frog leaping algorithm:a memetic meta-heuristic for discrete Optimization[J]. Engineering Optimization,2006,28(2)
[10]Alireza Rahimi-Vahed, Ali Hossein Mirzaei.A hybrid multi-object shuffled frog leaping algorithm for a mixed-model assembly line sequencing problem. Computer & Industrial Engineering.2007,53(4)
[11]Kerola.Color Image Segmentation Using Clonal Selection_Based Shuffled Frog Leaping Algorithm. Proceedings of the International Conference on Advances in Recent Technologies in Communication and computing,2009
[12]李英海,周建中,杨俊杰,刘力.一种基于阈值选择策略的改进混合蛙跳算法[J].计算机工程与应用,2007,43(35)
[13]Ziyang Zhen, Daobo Wang, Yuanyuan Liu. Improved shuffled frog leaping algorithm for continuous optimization problem[A].Proceedings of the Eleventh conference on Congress on Evolutionary Computation. PiscatawayNJ:IEEE Press,2009
[14]Yinghai Li, Jianzhong Zhou, Yongchuan Zhang, HuiQin, LiLiu. Novel Multiobjective Shuffled Frog Leaping Algorithm with Application to Reservoir Flood control Operation[J]J.Water Resour.Plng.and Mgnt,2010,136 (2):217-226
[15]Wolpert DH, Macready WG.No free lunch theorems for optimization.IEEE Trans.on Evolutionary Computation 1997,1(1):67-82.
[16]Guo Tao, Zbigniew Michalewicz. Inver-Over operator for the TSP[C]. Proceedings of the 5th International Conference on Parallel Problem Solving from Nature,1998.803-812
[17]闭应洲,丁立新,杨小雄.快速倒序算子的研究[J].计算机工程与应用,2009,45(4)
[18]Birbil S I, Fang S-C.An electromagnetism-like mechanism for global optimization[J] Journal of Global Optimization,2003,25(3):263-282.
[19]Kennedy J, EberhartR C.Particle swarm optimization[A].Proceedings of the 1995 IEEE International Conference on NeuralNetworks.PiscatawayNJ:IEEE press,1995
[20]段海滨.蚁群算法原理及其应用[M].北京：科学出版社,2005.
[21]李晓磊,路飞,田国会,钱积新.组合优化问题的人工鱼群算法应用[J].山东大学学报,2004,24(5).
[22]Karaboga.D, An Idea Based on Honey Bee Swarm For Numberical optimization. Technical Report-TR 06.Erciyes University,2005
[23]Dervis Karaboga, Bahriye Basturk. Artifical Bee Cology (ABC) Optimization problems. IFSA 2007,LNAI 4529,2007:789-798
[24]Teodorovic D, Dell'Orco M. Bee colony optimization accoperative learning approach to complex transportation problems[A]. Praceedings of the 10 th EWGT Meeting and 16th M in i EURO Conference[C], Poznan,2005
[25]陈家照,罗寅生.群智能算法研究[A].第三届中国智能计算大会论文集,2009
[26]贺毅朝,刘坤起,张翠军等.求解背包问题的贪心遗传算法及其应用[J].计算机工程与设计,2007；28(11)：2655-2657
[27]陆鹏,高茂庭,李迎新.遗传算法在0-1一维背包问题上的应用研究[J].计算机与数字工程,2007；35(10)：35—37
[28]刘勇,许秋艳,马良.智能优化算法在聚类分析中的应用[J].计算机工程与应用,2009,45(19)
[29]薛嘉,蔡金燕,马飒飒.基于群智能的连续优化算法研究[J].计算机工程与设计,2009,30(8)
[30]高亮,周驰.用Memetic算法求解有时间约束的TSP问题[J].华中科技大学学报,2008,36(7)
[31]王艳玲,李龙澍,胡哲.群体智能优化算法[J].计算机技术与发展,2008,18(8)
[32]黄冀卓,王湛.结合梯度法的混合微粒群优化算法[J].计算机工程与应用,2008,44(35)
[33]夏桂梅,曾建潮.一种基于单纯形法的随机微粒群算法[J].计算机工程与科学,2007,29(1)
[34]叶永春,车林仙,何兵.一种求解0-1背包问题的混合粒子群算法[J].长沙电力学院学报,2006,21(4)
[35]王晓娟.类电磁机制算法及其若干应用研究[D].华中科技大学,2006
[36]王晓娟,高亮,陈亚洲、类电磁机制算法及其应用[J].计算机应用研究,2006(6)
[37]夏桂梅,曾建潮.双群体随机微粒群算法[J].计算机工程与应用,2006,42(24)
[38]崔志华,曾建潮.一种动态调整的改进微粒群算法[J].系统工程学报,2005,20(6)
[39]陈国初,俞金寿.两群替代微粒群优化算法及其应用[J].华东理工大学学报,2005,31(6)
[40]李爱国.多粒子群协同优化算法[J].复旦学报：自然科学版,2004,43(5)
[41]张丽平,俞欢军,陈德钊等.粒子群优化算法的分析与改进[J].信息与控制,2004,33(5)
[42]曾建潮,介蜻,崔志华微粒群算法[M].北京；科学出版社,2004
[43]史今驰.背包问题的使用求解算法研究[D].山东大学,2004
[44]杨燕,蕲蕃.微粒群优化算法研究现状及其发展[J].计算机工程,2004,30(21)
[45]吴斌,傅伟鹏,郑毅,史忠植.一种基于群体智能的web文档聚类算法[J].计算机研究与发展,2002,39(11)
[46]SI Birbil, Shu-Cherng Fang.A Multi-point Stochastic Search Method for Global Optimization.the proceedings of the 4th International Symposium on Operations Research and Its Applications,2002
[47]Xiaohui Hu, Eberhart, R C.Adaptive particle swarm optimization:detection and response to dynamic systems[A].Proceedings of the 2002 Congress on Evolutionary Computation[C].Honolulu, HIUSA,2002
[48]Kennedy J, Mendes R.Population structure and particle swarm performance[A].Proceedings of the IE-EE Congress on Evolutionary Computation (CEC 2002)[C].Honolulu, HIUSA,2002
[49]James Kennedy, Russell C Eberhart.Swarm Intelligence[M].San Francisco:Morgan Kaufmann. Publisher, 2001:165-178
[50]T Stutzle, H H Hoos.MAXMIN Ant system[J]. Journal of Future Generation Computer Systems,2000
[51]T Stutzle, H H Hoos.The MAX2MIN ant system and local search for the traveling salesman problem[A]. In Proceedings of the IEEE International Conference on Evolutionary Computation.Indianapolis, USA, 1997
[52]Michalewics Z,Genetic Algorithm+Data Structure= Evolutionary Programs,3rd edition, New York, 1996
[53]Schwefel H, Evolution and Optimum Seeking, Wiley, NewYork,1995
[54]Eberhart R C, Kennedy J.A new optimizer using particle swarm theory[A].Proceedings of the Sixth International Symposiumon Micro Machine and Human Science[C].Nagoya Japan,4-6Oct,1995
[2]Holland J. Adaptation in Natural and Artificial Systems[M].University of Michigan Press, Ann Arbor, MIT,1975
[3]M H Alsuwaiyel.算法设计技巧与分析[M].电子工业出版社,2006
[4]潘正君,康立山,陈磂屏.演化计算[M].清华大学出版社,1998
[5]王辉,钱峰.群体智能优化算法[J].化工自动化及仪表,2007,34(5)
[6]王玫,朱云龙,何小贤.群体智能研究综述[J].计算机工程,2007,31(22)
[7]Eusuff M M, Lansey K E.Optimization of water distribution network design using shuffled frog leaping algorithm[J] Journal of Water Resources Planning and Management,2003,129(3):210-225
[8]Elbeltagi E, Hegazy T, Grierson D.Comparison among five evolutionary-based optimization algorithms[J].Advanced Engineering Informatics,2005,19(1):43-53
[9]Muzaffar Eusuff, Kevin Lansey, Fayzul Pasha.Shuffled frog leaping algorithm:a memetic meta-heuristic for discrete Optimization[J]. Engineering Optimization,2006,28(2)
[10]Alireza Rahimi-Vahed, Ali Hossein Mirzaei.A hybrid multi-object shuffled frog leaping algorithm for a mixed-model assembly line sequencing problem. Computer & Industrial Engineering.2007,53(4)
[11]Kerola.Color Image Segmentation Using Clonal Selection_Based Shuffled Frog Leaping Algorithm. Proceedings of the International Conference on Advances in Recent Technologies in Communication and computing,2009
[12]李英海,周建中,杨俊杰,刘力.一种基于阈值选择策略的改进混合蛙跳算法[J].计算机工程与应用,2007,43(35)
[13]Ziyang Zhen, Daobo Wang, Yuanyuan Liu. Improved shuffled frog leaping algorithm for continuous optimization problem[A].Proceedings of the Eleventh conference on Congress on Evolutionary Computation. PiscatawayNJ:IEEE Press,2009
[14]Yinghai Li, Jianzhong Zhou, Yongchuan Zhang, HuiQin, LiLiu. Novel Multiobjective Shuffled Frog Leaping Algorithm with Application to Reservoir Flood control Operation[J]J.Water Resour.Plng.and Mgnt,2010,136 (2):217-226
[15]Wolpert DH, Macready WG.No free lunch theorems for optimization.IEEE Trans.on Evolutionary Computation 1997,1(1):67-82.
[16]Guo Tao, Zbigniew Michalewicz. Inver-Over operator for the TSP[C]. Proceedings of the 5th International Conference on Parallel Problem Solving from Nature,1998.803-812
[17]闭应洲,丁立新,杨小雄.快速倒序算子的研究[J].计算机工程与应用,2009,45(4)
[18]Birbil S I, Fang S-C.An electromagnetism-like mechanism for global optimization[J] Journal of Global Optimization,2003,25(3):263-282.
[19]Kennedy J, EberhartR C.Particle swarm optimization[A].Proceedings of the 1995 IEEE International Conference on NeuralNetworks.PiscatawayNJ:IEEE press,1995
[20]段海滨.蚁群算法原理及其应用[M].北京：科学出版社,2005.
[21]李晓磊,路飞,田国会,钱积新.组合优化问题的人工鱼群算法应用[J].山东大学学报,2004,24(5).
[22]Karaboga.D, An Idea Based on Honey Bee Swarm For Numberical optimization. Technical Report-TR 06.Erciyes University,2005
[23]Dervis Karaboga, Bahriye Basturk. Artifical Bee Cology (ABC) Optimization problems. IFSA 2007,LNAI 4529,2007:789-798
[24]Teodorovic D, Dell'Orco M. Bee colony optimization accoperative learning approach to complex transportation problems[A]. Praceedings of the 10 th EWGT Meeting and 16th M in i EURO Conference[C], Poznan,2005
[25]陈家照,罗寅生.群智能算法研究[A].第三届中国智能计算大会论文集,2009
[26]贺毅朝,刘坤起,张翠军等.求解背包问题的贪心遗传算法及其应用[J].计算机工程与设计,2007；28(11)：2655-2657
[27]陆鹏,高茂庭,李迎新.遗传算法在0-1一维背包问题上的应用研究[J].计算机与数字工程,2007；35(10)：35—37
[28]刘勇,许秋艳,马良.智能优化算法在聚类分析中的应用[J].计算机工程与应用,2009,45(19)
[29]薛嘉,蔡金燕,马飒飒.基于群智能的连续优化算法研究[J].计算机工程与设计,2009,30(8)
[30]高亮,周驰.用Memetic算法求解有时间约束的TSP问题[J].华中科技大学学报,2008,36(7)
[31]王艳玲,李龙澍,胡哲.群体智能优化算法[J].计算机技术与发展,2008,18(8)
[32]黄冀卓,王湛.结合梯度法的混合微粒群优化算法[J].计算机工程与应用,2008,44(35)
[33]夏桂梅,曾建潮.一种基于单纯形法的随机微粒群算法[J].计算机工程与科学,2007,29(1)
[34]叶永春,车林仙,何兵.一种求解0-1背包问题的混合粒子群算法[J].长沙电力学院学报,2006,21(4)
[35]王晓娟.类电磁机制算法及其若干应用研究[D].华中科技大学,2006
[36]王晓娟,高亮,陈亚洲、类电磁机制算法及其应用[J].计算机应用研究,2006(6)
[37]夏桂梅,曾建潮.双群体随机微粒群算法[J].计算机工程与应用,2006,42(24)
[38]崔志华,曾建潮.一种动态调整的改进微粒群算法[J].系统工程学报,2005,20(6)
[39]陈国初,俞金寿.两群替代微粒群优化算法及其应用[J].华东理工大学学报,2005,31(6)
[40]李爱国.多粒子群协同优化算法[J].复旦学报：自然科学版,2004,43(5)
[41]张丽平,俞欢军,陈德钊等.粒子群优化算法的分析与改进[J].信息与控制,2004,33(5)
[42]曾建潮,介蜻,崔志华微粒群算法[M].北京；科学出版社,2004
[43]史今驰.背包问题的使用求解算法研究[D].山东大学,2004
[44]杨燕,蕲蕃.微粒群优化算法研究现状及其发展[J].计算机工程,2004,30(21)
[45]吴斌,傅伟鹏,郑毅,史忠植.一种基于群体智能的web文档聚类算法[J].计算机研究与发展,2002,39(11)
[46]SI Birbil, Shu-Cherng Fang.A Multi-point Stochastic Search Method for Global Optimization.the proceedings of the 4th International Symposium on Operations Research and Its Applications,2002
[47]Xiaohui Hu, Eberhart, R C.Adaptive particle swarm optimization:detection and response to dynamic systems[A].Proceedings of the 2002 Congress on Evolutionary Computation[C].Honolulu, HIUSA,2002
[48]Kennedy J, Mendes R.Population structure and particle swarm performance[A].Proceedings of the IE-EE Congress on Evolutionary Computation (CEC 2002)[C].Honolulu, HIUSA,2002
[49]James Kennedy, Russell C Eberhart.Swarm Intelligence[M].San Francisco:Morgan Kaufmann. Publisher, 2001:165-178
[50]T Stutzle, H H Hoos.MAXMIN Ant system[J]. Journal of Future Generation Computer Systems,2000
[51]T Stutzle, H H Hoos.The MAX2MIN ant system and local search for the traveling salesman problem[A]. In Proceedings of the IEEE International Conference on Evolutionary Computation.Indianapolis, USA, 1997
[52]Michalewics Z,Genetic Algorithm+Data Structure= Evolutionary Programs,3rd edition, New York, 1996
[53]Schwefel H, Evolution and Optimum Seeking, Wiley, NewYork,1995
[54]Eberhart R C, Kennedy J.A new optimizer using particle swarm theory[A].Proceedings of the Sixth International Symposiumon Micro Machine and Human Science[C].Nagoya Japan,4-6Oct,1995