人工蜂群算法的混合策略研究
|
摘要
群智能算法是通过模拟自然界生物的群体行为而构造的随机优化算法,它为解决大量存在于计算机科学、管理科学、控制工程等领域的全局优化问题提供了新的途径,因此成为学术界长期研究的热点。
人工蜂群算法(ABC)是一种模拟蜜蜂群智能搜索行为的群智能优化算法。由于其控制参数少、易于实现、计算简洁等优点,已被越来越多的学者所关注。但是目前关于人工蜂群算法的研究与应用还处于初级阶段,还存在很多问题有待深入改进和解决。为了有效改善人工蜂群算法的性能,论文从多个角度对其混合策略进行了研究。
首先,论文对人工蜂群算法的选择策略进行了详细分析,通过引入三种不同的选择策略对人工蜂群算法进行了改进与比较,仿真实验表明,改进的算法具有更强的寻优能力,在收敛速度和精度上都有显著提高。
其次,结合混沌优化的思想,提出一种自适应搜索空间的混沌蜂群算法(SA-CABC)。其基本思想是在原搜索区域的基础上,根据每次寻优的结果自适应的调整搜索空间,逐步缩小搜索区域,并利用混沌变量的内在随机性和遍历性跳出局部最优点,最终获得最优解。仿真实验表明,SA-CABC算法能有效地加快收敛速度,提高最优解的精度,其性能明显优于基本ABC算法,尤其适合高维的复杂函数的寻优。
最后,结合差分进化算法,提出一种新的双种群差分蜂群算法(BDABC)。首先通过基于反向学习的策略初始化种群,使得初始化的个体尽可能均匀分布在搜索空间,然后将种群中的个体随机分成两组,每组采用不同的优化策略同时进行寻优,并通过在两群体之间引入交互学习的思想,来提高算法的收敛速度。仿真实验表明,BDABC算法能有效避免早熟收敛,全局优化能力和收敛速率都有显著提高。
Swarm Intelligence Algorithm is a kind of stochastic optimization algorithm based on behavior of biological swarm, which provides a new method to solve global optimization problem existed in the fields of computer science, management science, control engineering and so on. So it becomes a focus among researchers in a long term.
Artificial bee colony (ABC) algorithm is a swarm intelligence optimization algorithm based on the particular intelligent behavior of honeybee swarms. Because of the advantages of its less control parameters, easily programming and simple calculation, it has received more and more attention by scholars, but the research and application on artificial bee colony algorithm is still in primitive stage at present. There are still many problems to be improved and solved. In order to effectively improve performance of artificial bee colony algorithm (ABC), the hybrid strategies from various angles are studied in the paper.
Firstly, the selection strategy of ABC algorithm is analyzed in this paper. In order to improve the population diversity and avoid the premature, several selection strategies, such as rank selection strategy, disruptive selection strategy and tournament selection strategy, are analyzed and compared through simulation, and the results show that the modified algorithm outperforms the basic ABC algorithm.
Secondly, this paper proposes an improved artificial bee colony (ABC) algorithm called chaotic artificial bee colony algorithm with self-adapting search space (SA-CABC). The main idea is self-adapting adjust search space according to the results of each optimization, and takes use of the randomicity and ergodicity properties of the chaos to break away the local optima, and ultimately finds the global optima. Simulation results show that the SA-CABC algorithm not only accelerates the convergence rate and improves its accuracy, but also effectively avoids the premature convergence. SA-CABC algorithm is better than the basic ABC, and provides excellent performance in dealing high-dimensional complex problems.
Finally, a novel Bi-group differential artificial bee colony algorithm (BDABC) which is combined with differential evolution (DE) algorithm is proposed. In this algorithm, an initialization strategy based on the opposition-based learning is applied to diversify the initial individuals in the search space. All of the individuals are divided into two populations randomly, and the evolutions of two sub-groups are parallel performed with different optimization strategies. The interactive learning strategy is introduced to accelerate the convergence speed. Experimental results on six benchmark functions show that the BDABC algorithm can not only effectively avoids the premature convergence, but also significantly improves the global optimization ability and the convergence speed.
人工蜂群算法(ABC)是一种模拟蜜蜂群智能搜索行为的群智能优化算法。由于其控制参数少、易于实现、计算简洁等优点,已被越来越多的学者所关注。但是目前关于人工蜂群算法的研究与应用还处于初级阶段,还存在很多问题有待深入改进和解决。为了有效改善人工蜂群算法的性能,论文从多个角度对其混合策略进行了研究。
首先,论文对人工蜂群算法的选择策略进行了详细分析,通过引入三种不同的选择策略对人工蜂群算法进行了改进与比较,仿真实验表明,改进的算法具有更强的寻优能力,在收敛速度和精度上都有显著提高。
其次,结合混沌优化的思想,提出一种自适应搜索空间的混沌蜂群算法(SA-CABC)。其基本思想是在原搜索区域的基础上,根据每次寻优的结果自适应的调整搜索空间,逐步缩小搜索区域,并利用混沌变量的内在随机性和遍历性跳出局部最优点,最终获得最优解。仿真实验表明,SA-CABC算法能有效地加快收敛速度,提高最优解的精度,其性能明显优于基本ABC算法,尤其适合高维的复杂函数的寻优。
最后,结合差分进化算法,提出一种新的双种群差分蜂群算法(BDABC)。首先通过基于反向学习的策略初始化种群,使得初始化的个体尽可能均匀分布在搜索空间,然后将种群中的个体随机分成两组,每组采用不同的优化策略同时进行寻优,并通过在两群体之间引入交互学习的思想,来提高算法的收敛速度。仿真实验表明,BDABC算法能有效避免早熟收敛,全局优化能力和收敛速率都有显著提高。
Swarm Intelligence Algorithm is a kind of stochastic optimization algorithm based on behavior of biological swarm, which provides a new method to solve global optimization problem existed in the fields of computer science, management science, control engineering and so on. So it becomes a focus among researchers in a long term.
Artificial bee colony (ABC) algorithm is a swarm intelligence optimization algorithm based on the particular intelligent behavior of honeybee swarms. Because of the advantages of its less control parameters, easily programming and simple calculation, it has received more and more attention by scholars, but the research and application on artificial bee colony algorithm is still in primitive stage at present. There are still many problems to be improved and solved. In order to effectively improve performance of artificial bee colony algorithm (ABC), the hybrid strategies from various angles are studied in the paper.
Firstly, the selection strategy of ABC algorithm is analyzed in this paper. In order to improve the population diversity and avoid the premature, several selection strategies, such as rank selection strategy, disruptive selection strategy and tournament selection strategy, are analyzed and compared through simulation, and the results show that the modified algorithm outperforms the basic ABC algorithm.
Secondly, this paper proposes an improved artificial bee colony (ABC) algorithm called chaotic artificial bee colony algorithm with self-adapting search space (SA-CABC). The main idea is self-adapting adjust search space according to the results of each optimization, and takes use of the randomicity and ergodicity properties of the chaos to break away the local optima, and ultimately finds the global optima. Simulation results show that the SA-CABC algorithm not only accelerates the convergence rate and improves its accuracy, but also effectively avoids the premature convergence. SA-CABC algorithm is better than the basic ABC, and provides excellent performance in dealing high-dimensional complex problems.
Finally, a novel Bi-group differential artificial bee colony algorithm (BDABC) which is combined with differential evolution (DE) algorithm is proposed. In this algorithm, an initialization strategy based on the opposition-based learning is applied to diversify the initial individuals in the search space. All of the individuals are divided into two populations randomly, and the evolutions of two sub-groups are parallel performed with different optimization strategies. The interactive learning strategy is introduced to accelerate the convergence speed. Experimental results on six benchmark functions show that the BDABC algorithm can not only effectively avoids the premature convergence, but also significantly improves the global optimization ability and the convergence speed.
引文
[1]吴启迪,汪镭.智能微粒群算法的研究及应用[M].南京:江苏教育出版社,2005.
[2]胡中功,李静.群智能算法的研究进展[J].自动化技术与应用,2008,27(2):13-15.
[3]王辉,钱锋.群体智能优化算法[J].化工自动化及仪表,2007,34(5):7—13.
[4] Colorni A, Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]. Proceedings of the First European Conference on Artificial Life,1991:134-142.
[5] Kennedy J, Eberhart R C. Particle swarm optimization[C]. Proceeding Soft the IEEE International Conference on Neural Networks, Perth, Australia. Piscataway, NJ:IEEEPress,1995:1942-1948.
[6] 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.
[7]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.
[8] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical Report-TR06, Erciyes. University, Engineering Faculty, Computer Engineering Department, 2005.
[9]李峰磊.蜂群算法的研究与应用[D].南京:河海大学硕士论文,2008.
[10]昆友.蜜蜂的舞蹈语言[EB/OL].http://www.bjkp.gov.cn/dwly/dwsy/k0733-05.htm/ 2010-03-15.
[11] Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007,39(3): 459-471.
[12] Basturk B, Karaboga D. An Artificial Bee Colony (ABC) Algorithm for Numeric function Optimization[C]. USA,Indiana: IEEE Swarm Intelligence Symposium, 2006.
[13] Karaboga D, Basturk B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing. 2008,8(1):687–697.
[14] Karaboga D, Basturk B. Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems[C]. LNCS: Advances in Soft Computing: Foundations of Fuzzy Logic and Soft Computing,IFSA 2007,Springer- Verlag,2007,4529: 789-798.
[15] Karaboga D,Akay B B. Artificial Bee Colony Algorithm on Training Artificial Neural Networks[C]. Signal Processing and Communications Applications,SIU 2007,IEEE 15th. 2007:1-4.
[16] Karaboga D,Akay B B, Ozturk C. Artificial Bee Colony (ABC) Optimization Algorithm for Training Feed-Forward Neural Networks[C]. LNCS: Modeling Decisions for Artificial Intelligence,MDAI 2007,Springer-Verlag,2007,4617:318-319.
[17] Karaboga D, Ozturk C. Neural Networks Training by Artificial Bee Colony Algorithm on Pattern Classification[J]. Neural Network World, 2009,19(3):279-292.
[18] Rao R S, Narasimham S, Ramalingaraju M, Optimization of Distribution Network Configuration for Loss Reduction Using Artificial Bee Colony Algorithm[J]. International Journal of Electrical Power and Energy Systems Engineering (IJEPESE), 2008,1(2):709-715.
[19] Karaboga N. A New Design Method Based on Artificial Bee Colony Algorithm for Digital IIR filters[J]. Journal of the Franklin Institute, 2009, 346 (4): 328-348.
[20] Bahamish H, Abdullah R, Salam R. Protein Tertiary Structure Prediction Using Artificial Bee Colony Algorithm[C]. Third Asia International Conference on Modelling & Simulation, Bandung, Bali, Indonesia. May 25-29, 2009:258-263.
[21] Akay B, Karaboga D. Solving Integer Programming Problems by Using Artificial Bee Colony Algorithm[C]. Proceedings of the 14th International Conference on Advances in Artificial Intelligence by the Italian Association for Artificial Intelligence(AI*IA2009), Springer-Verlag, 2009,5883:355-364..
[22] Kurban T, Be?dok E. A Comparison of RBF Neural Network Training Algorithms for Inertial Sensor Based Terrain Classification[J]. Sensors, 2009, 9:6312-6329.
[23] Omkar S.N; Senthilnath J. Artificial Bee Colony for Classification of Acoustic Emission Signal[J]. International Journal of Aerospace Innovations, 2009,1(3):129-143.
[24]康飞,李俊杰,许青.混合蜂群算法及其在混凝土坝动力材料参数反演中的应用.水利学报,2009,40(6):736-742.
[25]胡中华,赵敏.基于人工蜂群算法的机器人路径规划[J].电焊机, 2009,39(4):93-96.
[26]李端明,程八一.基于人工蜂群算法求解不同尺寸工件单机批调度问题[J].四川大学学报(自然科学版), 2009,46(3):657-662.
[27] Singh A. An Artificial Bee Colony Algorithm for the Leaf-constrained Minimum Spanning Tree Problem[J]. Applied Soft Computing, 2009,9(2):625-631.
[28] Tsai Pei-Wei, Pan Jeng-Shyang, Liao Bin-Yih and Chu Shu-Chuan. Enhanced Artificial Bee Colony Optimization [J]. International Journal of Innovative Computing, Information and Control, 2009, 5(12):5081-5092.
[29]丁海军,李峰磊.蜂群算法在TSP问题上的应用及参数改进[J].中国科技信息,2008(3):241-243.
[30]胡中华,赵敏,撒鹏飞.基于人工蜂群算法的JSP的仿真与研究[J].机械科学与技术,2009,28(7):851-856.
[31]康飞等.改进人工蜂群算法及其在反演分析中的应用[J].水电能源科学,2009,27(1):126-129.
[32]宋爱国,陆佶人.一种基于排序操作的进化算子自适应遗传算法[J].电子学报,1999,27(1):85-88.
[33] Kuo T, Huang S Y. Using Disruptive Selection to Maintain Diversity in Genetic Algorithms[J]. Applied Intelligence, 1997,7(3):257-267.
[34] Blickle T, Thiele L. A Mathematical Analysis of Tournament Selection[C]. Proceedings of the Sixth International Conference on Genetic Algorithms. CA:Morgan Kaufmann Publishers,1995:9-16.
[35] Yao X, Liu Y, Lin G M. Evolutionary Programming Made Faster[J]. IEEE Transactions on Evolutionary Computation, 1999,3(2):82-102.
[36]李兵,蒋慰孙.混沌优化方法及其应用[J].控制理论与应用,1997,14(4):613-615
[37]张春慨等.改进混沌优化及其在非线性约束优化问题中的应用[J].上海交通大学学报,2000,34(5):593-596.
[38] Yuan X, Yuan Y, Zhang Y. A hybrid chaotic genetic algorithm for short-term hydro system scheduling [J] .Mathematics and Computers in Simulation, 2002 ,59: 319-327.
[39]袁晓辉等.一种新型的自适应混沌遗传算法[J].电子学报,2006,34(4): 708-712.
[40]陈炳瑞等.自适应混沌遗传混合算法及其参数敏感性分析[J].东北大学学报(自然科学版),2006,27(6):689-693.
[41] Liu B, Wang L, Jin Y H et al. Improved particle swarm optimization combined with chaos [J].Chaos Solitons &Fractals (S0960-0779),2005,25(5):1261-1271.
[42]高尚,杨静宇.混沌粒子群优化算法研究[J].模式识别与人工智能,2006,9(2):266-270.
[43]陈如清,俞金寿.混沌粒子群混合优化算法的研究与应用[J].系统仿真学报, 2008,20(3):685-688.
[44] Storn R, Price K. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Space [J]. Journal of Global Optimization,1997,11(4):341-359.
[45] Mendes R, Mohais A S. DynDE: A Differential Evolution for Dynamic Optimization Problems [C]. 2005 IEEE Congress on Evolutionary Computation. CA: IEEE Press,2005:2808-2815.
[46]吴昱,李元香,徐星.基于群智能的新型反向混合差分进化算法[J].小型微型计算机系统,2009,5(5):903-907.
[47]毛润宇,王小平,薛小平.一种自适应差分演化算法[J].计算机应用与软件,2008,25(12):7-8.
[2]胡中功,李静.群智能算法的研究进展[J].自动化技术与应用,2008,27(2):13-15.
[3]王辉,钱锋.群体智能优化算法[J].化工自动化及仪表,2007,34(5):7—13.
[4] Colorni A, Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]. Proceedings of the First European Conference on Artificial Life,1991:134-142.
[5] Kennedy J, Eberhart R C. Particle swarm optimization[C]. Proceeding Soft the IEEE International Conference on Neural Networks, Perth, Australia. Piscataway, NJ:IEEEPress,1995:1942-1948.
[6] 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.
[7]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.
[8] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical Report-TR06, Erciyes. University, Engineering Faculty, Computer Engineering Department, 2005.
[9]李峰磊.蜂群算法的研究与应用[D].南京:河海大学硕士论文,2008.
[10]昆友.蜜蜂的舞蹈语言[EB/OL].http://www.bjkp.gov.cn/dwly/dwsy/k0733-05.htm/ 2010-03-15.
[11] Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007,39(3): 459-471.
[12] Basturk B, Karaboga D. An Artificial Bee Colony (ABC) Algorithm for Numeric function Optimization[C]. USA,Indiana: IEEE Swarm Intelligence Symposium, 2006.
[13] Karaboga D, Basturk B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing. 2008,8(1):687–697.
[14] Karaboga D, Basturk B. Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems[C]. LNCS: Advances in Soft Computing: Foundations of Fuzzy Logic and Soft Computing,IFSA 2007,Springer- Verlag,2007,4529: 789-798.
[15] Karaboga D,Akay B B. Artificial Bee Colony Algorithm on Training Artificial Neural Networks[C]. Signal Processing and Communications Applications,SIU 2007,IEEE 15th. 2007:1-4.
[16] Karaboga D,Akay B B, Ozturk C. Artificial Bee Colony (ABC) Optimization Algorithm for Training Feed-Forward Neural Networks[C]. LNCS: Modeling Decisions for Artificial Intelligence,MDAI 2007,Springer-Verlag,2007,4617:318-319.
[17] Karaboga D, Ozturk C. Neural Networks Training by Artificial Bee Colony Algorithm on Pattern Classification[J]. Neural Network World, 2009,19(3):279-292.
[18] Rao R S, Narasimham S, Ramalingaraju M, Optimization of Distribution Network Configuration for Loss Reduction Using Artificial Bee Colony Algorithm[J]. International Journal of Electrical Power and Energy Systems Engineering (IJEPESE), 2008,1(2):709-715.
[19] Karaboga N. A New Design Method Based on Artificial Bee Colony Algorithm for Digital IIR filters[J]. Journal of the Franklin Institute, 2009, 346 (4): 328-348.
[20] Bahamish H, Abdullah R, Salam R. Protein Tertiary Structure Prediction Using Artificial Bee Colony Algorithm[C]. Third Asia International Conference on Modelling & Simulation, Bandung, Bali, Indonesia. May 25-29, 2009:258-263.
[21] Akay B, Karaboga D. Solving Integer Programming Problems by Using Artificial Bee Colony Algorithm[C]. Proceedings of the 14th International Conference on Advances in Artificial Intelligence by the Italian Association for Artificial Intelligence(AI*IA2009), Springer-Verlag, 2009,5883:355-364..
[22] Kurban T, Be?dok E. A Comparison of RBF Neural Network Training Algorithms for Inertial Sensor Based Terrain Classification[J]. Sensors, 2009, 9:6312-6329.
[23] Omkar S.N; Senthilnath J. Artificial Bee Colony for Classification of Acoustic Emission Signal[J]. International Journal of Aerospace Innovations, 2009,1(3):129-143.
[24]康飞,李俊杰,许青.混合蜂群算法及其在混凝土坝动力材料参数反演中的应用.水利学报,2009,40(6):736-742.
[25]胡中华,赵敏.基于人工蜂群算法的机器人路径规划[J].电焊机, 2009,39(4):93-96.
[26]李端明,程八一.基于人工蜂群算法求解不同尺寸工件单机批调度问题[J].四川大学学报(自然科学版), 2009,46(3):657-662.
[27] Singh A. An Artificial Bee Colony Algorithm for the Leaf-constrained Minimum Spanning Tree Problem[J]. Applied Soft Computing, 2009,9(2):625-631.
[28] Tsai Pei-Wei, Pan Jeng-Shyang, Liao Bin-Yih and Chu Shu-Chuan. Enhanced Artificial Bee Colony Optimization [J]. International Journal of Innovative Computing, Information and Control, 2009, 5(12):5081-5092.
[29]丁海军,李峰磊.蜂群算法在TSP问题上的应用及参数改进[J].中国科技信息,2008(3):241-243.
[30]胡中华,赵敏,撒鹏飞.基于人工蜂群算法的JSP的仿真与研究[J].机械科学与技术,2009,28(7):851-856.
[31]康飞等.改进人工蜂群算法及其在反演分析中的应用[J].水电能源科学,2009,27(1):126-129.
[32]宋爱国,陆佶人.一种基于排序操作的进化算子自适应遗传算法[J].电子学报,1999,27(1):85-88.
[33] Kuo T, Huang S Y. Using Disruptive Selection to Maintain Diversity in Genetic Algorithms[J]. Applied Intelligence, 1997,7(3):257-267.
[34] Blickle T, Thiele L. A Mathematical Analysis of Tournament Selection[C]. Proceedings of the Sixth International Conference on Genetic Algorithms. CA:Morgan Kaufmann Publishers,1995:9-16.
[35] Yao X, Liu Y, Lin G M. Evolutionary Programming Made Faster[J]. IEEE Transactions on Evolutionary Computation, 1999,3(2):82-102.
[36]李兵,蒋慰孙.混沌优化方法及其应用[J].控制理论与应用,1997,14(4):613-615
[37]张春慨等.改进混沌优化及其在非线性约束优化问题中的应用[J].上海交通大学学报,2000,34(5):593-596.
[38] Yuan X, Yuan Y, Zhang Y. A hybrid chaotic genetic algorithm for short-term hydro system scheduling [J] .Mathematics and Computers in Simulation, 2002 ,59: 319-327.
[39]袁晓辉等.一种新型的自适应混沌遗传算法[J].电子学报,2006,34(4): 708-712.
[40]陈炳瑞等.自适应混沌遗传混合算法及其参数敏感性分析[J].东北大学学报(自然科学版),2006,27(6):689-693.
[41] Liu B, Wang L, Jin Y H et al. Improved particle swarm optimization combined with chaos [J].Chaos Solitons &Fractals (S0960-0779),2005,25(5):1261-1271.
[42]高尚,杨静宇.混沌粒子群优化算法研究[J].模式识别与人工智能,2006,9(2):266-270.
[43]陈如清,俞金寿.混沌粒子群混合优化算法的研究与应用[J].系统仿真学报, 2008,20(3):685-688.
[44] Storn R, Price K. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Space [J]. Journal of Global Optimization,1997,11(4):341-359.
[45] Mendes R, Mohais A S. DynDE: A Differential Evolution for Dynamic Optimization Problems [C]. 2005 IEEE Congress on Evolutionary Computation. CA: IEEE Press,2005:2808-2815.
[46]吴昱,李元香,徐星.基于群智能的新型反向混合差分进化算法[J].小型微型计算机系统,2009,5(5):903-907.
[47]毛润宇,王小平,薛小平.一种自适应差分演化算法[J].计算机应用与软件,2008,25(12):7-8.