Population diversity maintenance in brain storm optimization algorithm

• Autorzy: Cheng S. , Shi Y. , Qin Q. , Zhang Q , Bai R.

Identyfikatory

DOI

10.1515/jaiscr-2015-0001

• Języki publikacji: EN

Abstrakty

EN

The convergence and divergence are two common phenomena in swarm intelligence. To obtain good search results, the algorithm should have a balance on convergence and divergence. The premature convergence happens partially due to the solutions getting clustered together, and not diverging again. The brain storm optimization (BSO), which is a young and promising algorithm in swarm intelligence, is based on the collective behavior of human being, that is, the brainstorming process. The convergence strategy is utilized in BSO algorithm to exploit search areas may contain good solutions. The new solutions are generated by divergence strategy to explore new search areas. Premature convergence also happens in the BSO algorithm. The solutions get clustered after a few iterations, which indicate that the population diversity decreases quickly during the search. A definition of population diversity in BSO algorithm is introduced in this paper to measure the change of solutions’ distribution. The algorithm’s exploration and exploitation ability can be measured based on the change of population diversity. Different kinds of partial reinitialization strategies are utilized to improve the population diversity in BSO algorithm. The experimental results show that the performance of the BSO is improved by part of solutions re-initialization strategies.

Słowa kluczowe

EN

brainstorm; optimization algorithm; convergence; divergence; brainstorm optimization; BSO; swarm intelligence; BSO algorithm

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2014
• Tom: Vol. 4, No. 2
• Strony: 83--97
• Opis fizyczny: Bibliogr. 50 poz., rys.

Twórcy

autor

Cheng S.

• International Doctoral Innovation Centre, The University of Nottingham Ningbo, China Division of Computer Science, University of Nottingham Ningbo, China, Ningbo, 315100, Zhejiang, China

autor

Shi Y.

• Department of Electrical & Electronic Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, 215123, Jiangsu, China

autor

Qin Q.

• Department of Management Science, Shenzhen University, Shenzhen, China, Shenzhen, 518060, Guangdong, China

autor

Zhang Q

• Department of Management Science, Shenzhen University, Shenzhen, China, Shenzhen, 518060, Guangdong, China

autor

Bai R.

• Division of Computer Science, University of Nottingham Ningbo, China, Ningbo, 315100, Zhejiang, China

Bibliografia

• [1] K. A. De Jong, “An analysis of the behavior of a class of genetic adaptive systems,” Ph.D. dissertation, Department of Computer and Communication Sciences, University of Michigan, August 1975.
• [2] M. L. Mauldin, “Maintaining diversity in genetic search,” in Proceedings of the National Conference on Artificial Intelligence (AAAI 1984), August 1984, pp. 247–250.
• [3] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA,USA: Addison-Wesley Longman Publishing Co., Inc., 1989.
• [4] A´ . E. Eiben, R. Hinterding, and Z. Michalewicz, “Parameter control in evolutionary algorithms,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 124–141, July 1999.
• [5] S. F. Adra, T. J. Dodd, I. A. Griffin, and P. J. Fleming, “Convergence acceleration operator for multiobjective optimization,” IEEE Transactions on Evolutionary Computation, vol. 12, no. 4, pp. 825–847, August 2009.
• [6] Y. Jin and B. Sendhoff, “A systems approach to evolutionary multiobjective structural optimization and beyond,” IEEE Computational Intelligence Magazine, vol. 4, no. 3, pp. 62–76, August 2009.
• [7] R. K. Sundaram, A First Course in Optimization Theory. Cambridge University Press, 1996.
• [8] R. C. Purshouse and P. J. Fleming, “On the evolutionary optimization of many conflicting objectives,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 770–784, December 2007.
• [9] S. F. Adra and P. J. Fleming, “Diversity management in evolutionary many-objective optimization,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 2, pp. 183–195, April 2011.
• [10] A. Engelbrecht, X. Li, M. Middendorf, and L. M. Gambardella, “Editorial special issue: Swarm intelligence,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 4, pp. 677–680, August 2009.
• [11] J. Kennedy, R. Eberhart, and Y. Shi, Swarm Intelligence. Morgan Kaufmann Publisher, 2001.
• [12] E. K. Burke, S. Gustafson, and G. Kendall, “A survey and analysis of diversity measures in genetic programming,” in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2002, pp. 716–723.
• [13] Y. Shi and R. Eberhart, “Population diversity of particle swarms,” in Proceedings of the 2008 Congress on Evolutionary Computation (CEC2008), 2008, pp. 1063–1067.
• [14] ——, “Monitoring of particle swarm optimization,” Frontiers of Computer Science, vol. 3, no. 1, pp. 31–37, March 2009.
• [15] S. Cheng and Y. Shi, “Diversity control in particle swarm optimization,” in Proceedings of 2011 IEEE Symposium on Swarm Intelligence (SIS 2011), Paris, France, April 2011, pp. 110–118.
• [16] S. Cheng, Y. Shi, and Q. Qin, “Experimental Study on Boundary Constraints Handling in Particle Swarm Optimization: From Population Diversity Perspective,” International Journal of Swarm Intelligence Research (IJSIR), vol. 2, no. 3, pp. 43–69, July-September 2011.
• [17] S. Cheng, “Population diversity in particle swarm optimization: Definition, observation, control, and application,” Ph.D. dissertation, Department of 96 Cheng S., Shi Y., Qin Q., Zhang Q. and Ba R. Electrical Engineering and Electronics, University of Liverpool, May 2013.
• [18] S. Cheng, Y. Shi, and Q. Qin, “A study of normalized population diversity in particle swarm optimization,” International Journal of Swarm Intelligence Research (IJSIR), vol. 4, no. 1, pp. 1–34, January-March 2013.
• [19] Y. Shi, “Brain storm optimization algorithm,” in Advances in Swarm Intelligence, ser. Lecture Notes in Computer Science, Y. Tan, Y. Shi, Y. Chai, and G.Wang, Eds. Springer Berlin/Heidelberg, 2011, vol. 6728, pp. 303–309.
• [20] ——, “An optimization algorithm based on brainstorming process,” International Journal of Swarm Intelligence Research (IJSIR), vol. 2, no. 4, pp. 35–62, October-December 2011.
• [21] X. Guo, Y. Wu, and L. Xie, “Modified brain storm optimization algorithm for multimodal optimization,” in Advances in Swarm Intelligence, ser. Lecture Notes in Computer Science, Y. Tan, Y. Shi, and C. A. C. Coello, Eds. Springer International Publishing, 2014, vol. 8795, pp. 340–351.
• [22] J. Xue, Y. Wu, Y. Shi, and S. Cheng, “Brain storm optimization algorithm for multi-objective optimization problems,” in Advances in Swarm Intelligence, ser. Lecture Notes in Computer Science, Y. Tan, Y. Shi, and Z. Ji, Eds. Springer Berlin /Heidelberg, 2012, vol. 7331, pp. 513–519.
• [23] L. Xie and Y. Wu, “A modified multi-objective optimization based on brain storm optimization algorithm,” in Advances in Swarm Intelligence, ser. Lecture Notes in Computer Science, Y. Tan, Y. Shi, and C. Coello, Eds. Springer International Publishing, 2014, vol. 8795, pp. 328–339.
• [24] Z.-H. Zhan, W.-N. Chen, Y. Lin, Y.-J. Gong, Y. long Li, and J. Zhang, “Parameter investigation in brain storm optimization,” in 2013 IEEE Symposium on Swarm Intelligence (SIS), April 2013, pp. 103–110.
• [25] S. Cheng, Y. Shi, Q. Qin, and S. Gao, “Solution clustering analysis in brain storm optimization algorithm,” in Proceedings of The 2013 IEEE Symposium on Swarm Intelligence, (SIS 2013). Singapore: IEEE, 2013, pp. 111–118.
• [26] S. Cheng, Y. Shi, Q. Qin, T. O. Ting, and R. Bai, “Maintaining population diversity in brain storm optimization algorithm,” in Proceedings of 2014 IEEE Congress on Evolutionary Computation,(CEC 2014). Beijing, China: IEEE, 2014, pp. 3230–3237.
• [27] Z. hui Zhan, J. Zhang, Y. hui Shi, and H. lin Liu, “A modified brain storm optimization,” in Evolutionary Computation (CEC), 2012 IEEE Congress on, June 2012, pp. 1–8.
• [28] H. Jadhav, U. Sharma, J. Patel, and R. Roy, “Brain storm optimization algorithm based economic dispatch considering wind power,” in 2012 IEEE International Conference on Power and Energy (PECon 2012), Kota Kinabalu, Malaysia, December 2012, pp. 588–593.
• [29] C. Sun, H. Duan, and Y. Shi, “Optimal satellite formation reconfiguration based on closed-loop brain storm optimization,” IEEE Computational Intelligence Magazine, vol. 8, no. 4, pp. 39–51, November 2013.
• [30] H. Duan, S. Li, and Y. Shi, “Predatorcprey brain storm optimization for dc brushless motor,” IEEE Transactions on Magnetics, vol. 49, no. 10, pp. 5336–5340, October 2013.
• [31] H. Duan and C. Li, “Quantum-behaved brain storm optimization approch to solving loney’s solenoid problem,” IEEE Transactions on Magnetics, p. in press, 2014.
• [32] Y. Tan and Y. Zhu, “Fireworks algorithm for optimization,” in Advances in Swarm Intelligence, ser.Lecture Notes in Computer Science, Y. Tan, Y. Shi, and K. C. Tan, Eds. Springer Berlin Heidelberg, 2010, vol. 6145, pp. 355–364.
• [33] S. Zheng, A. Janecek, and Y. Tan, “Enhanced fireworks algorithm,” in 2013 IEEE Congress onEvolutionary Computation (CEC), June 2013, pp. 2069–2077.
• [34] Y. Shi, J. Xue, and Y. Wu, “Multi-objective optimization based on brain storm optimization algorithm,” International Journal of Swarm Intelligence Research (IJSIR), vol. 4, no. 3, pp. 1–21,July-September 2013.
• [35] C. Darwin, On the Origin of Species by Means of Natural Selection, or the Preservation of FavouredRaces in the Struggle for Life, 5th ed. London: John Murray, 1869.
• [36] M. Affenzeller, S. Winkler, S. Wagner, and A. Beham, Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications, ser. Numerical Insights, A. Sydow, Ed. Chapman & Hall/CRC Press, 2009, vol. 6.
• [37] S. Cheng, Y. Shi, and Q. Qin, “Dynamical exploitation space reduction in particle swarm optimization for solving large scale problems,” in Proceedings of 2012 IEEE Congress on Evolutionary Computation, (CEC 2012). Brisbane, Australia: IEEE, 2012, pp. 3030–3037.
• [38] ——, “Population diversity based study on search information propagation in particle swarm optimization,” in Proceedings of 2012 IEEE Congress on Evolutionary Computation, (CEC 2012). Brisbane, Australia: IEEE, 2012, pp. 1272–1279.
• [39] K. P. Murphy, Machine Learning: A Probabilistic Perspective, ser. Adaptive computation and machine learning series. Cambridge, Massachusetts: The MIT Press, 2012.
• [40] D. Zhou, Y. Shi, and S. Cheng, “Brain storm optimization algorithm with modified step-size and individual generation,” in Advances in Swarm Intelligence, ser. Lecture Notes in Computer Science, Y. Tan, Y. Shi, and Z. Ji, Eds. Springer Berlin / Heidelberg, 2012, vol. 7331, pp. 243–252.
• [41] S. Cheng, Y. Shi, and Q. Qin, “Population diversity of particle swarm optimizer solving single and multi-objective problems,” International Journal of Swarm Intelligence Research (IJSIR), vol. 3, no. 4, pp. 23–60, 2012.
• [42] ——, “Promoting diversity in particle swarm optimization to solve multimodal problems,” in Neural Information Processing, ser. Lecture Notes in Computer Science, B.-L. Lu, L. Zhang, and J. Kwok, Eds. Springer Berlin / Heidelberg, 2011, vol. 7063, pp. 228–237.
• [43] W. Cede˜no and V. R. Vemuri, “On the use of niching for dynamic landscapes,” in Proceedings of 1997 IEEE Congress on Evolutionary Computation, (CEC 1997). IEEE, 1997, pp. 361–366.
• [44] A. Della Cioppa, C. De Stefano, and A. Marcelli, “Where are the niches? dynamic fitness sharing,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 4, pp. 453–465, August 2007.
• [45] A. Ghosh, S. Tsutsui, and H. Tanaka, “Function optimization in nonstationary environment using steady state genetic algorithms with aging of individuals,” in Proceedings of 1998 IEEE Congress on Evolutionary Computation, (CEC 1998). IEEE, 1998, pp. 666–671.
• [46] Y. Jin and B. Sendhoff, “Constructing dynamic optimization test problems using the multi-objective optimization concept,” in Applications of Evolutionary Computing, ser. Lecture Notes in Computer Science, G. R. Raidl, S. Cagnoni, J. Branke, D. W. Corne, R. Drechsler, Y. Jin, C. G. Johnson, P. Machado, E. Marchiori, F. Rothlauf, G. D. Smith, and G. Squillero, Eds. Springer Berlin /Heidelberg, 2004, vol. 3005, pp. 525–536.
• [47] D. H.Wolpert andW. G. Macready, “No free lunch theorems for optimization,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67–82, April 1997.
• [48] X. Yao, Y. Liu, and G. Lin, “Evolutionary programming made faster,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 82–102, July 1999.
• [49] J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, “Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,” IEEE Transactions on Evolutionary Computation, vol. 10, no. 3, pp. 281–295, June 2006.
• [50] T. Blackwell and P. Bentley, “Don’t push me! collision-avoiding swarms,” in Proceedings of The Fourth Congress on Evolutionary Computation (CEC 2002), May 2002, pp. 1691–1696