Optimization based on symbiotic multi-species coevolution. (English) Zbl 1152.92014

Chen, Hanning; Zhu, Yunlong

Appl. Math. Comput. 205, No. 1, 47-60 (2008).

Summary: This paper presents a general optimization model gleaning ideas from the coevolution of symbiotic species in natural ecosystems. Species extinction and speciation events are also considered in this model to tie it closer to natural evolution, as well as improve the algorithm robustness. This model is instantiated as a novel multi-species optimizer, namely PS\(^{2}\)O, which extends the dynamics of the canonical PSO algorithm by adding a significant ingredient that takes into account the symbiotic coevolution between species. When tested against benchmark functions, the PS\(^{2}\)O markedly outperforms the canonical PSO algorithm in terms of accuracy, robustness and convergence speed.

MSC:

92D15	Problems related to evolution
92D40	Ecology
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

symbiosis; multi-species coevolution; species extinction and speciation; PSO; PS\(^{2}\)O

Software:

MCPSO

References:

[1]	R.C. Eberchart, J. Kennedy, A new optimizer using particle swarm theory, in: Proceeding of the 6th International Symposium on Micromachine and Human Science, Nagoya, Japan, 1995, pp. 39-43.
[2]	J. Kennedy, R.C. Eberchart, Particle swarm optimization, in: proceeding of IEEE International Conference on Neural Networks, Piscataway, NJ, 1995, pp. 1942-1948.
[3]	Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE transactions on systems man and cybernetics (part B), 26, 1, 29-41, (1996)
[4]	Dorigo, M.; Gambardella, L., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE transactions on evolutionary computation, 1, 1, 53-66, (1997)
[5]	R.C. Eberchart, Y. Shi, Particle swarm optimization: developments, applications and resources, in: Proceedings of the IEEE Congress on Evolutionary Computation, Piscataway, NJ, 2001, pp. 81-86.
[6]	Kennedy, J.; Eberchart, R.C.; Shi, Y., Swarm intelligence, (2001), Morgan Kaufman Publishers San Francisco
[7]	Frank, S.A., Models of symbiosis, American naturalist, 150, 80-99, (1997)
[8]	M.D. Jason, S.G. Catherine, A.S. Stephen, J.R. Steven, Symbionticism and complex adaptive systems I: implications of having symbiosis occur in nature, in: Proceedings of the 5th Annual Conference on Evolutionary Programming, Cambridge, 1996, pp. 177-186.
[9]	Marshall, C.R., Mass extinction probed, Nature, 392, 17-20, (1998)
[10]	Newman, M., Simple models of evolution and extinction, IEEE computing in science and engineering, 80-86, (2000)
[11]	R.A. Watson, J.B. Pollack, How symbiosis can guide evolution, in: Proceedings of the 15th European Conference on Artificial Life, Springer, Dario Floreano, Jean-Daniel Nicoud, Francesco Mondada, 1999, pp. 29-38.
[12]	Frank, S., The origin of synergistic symbiosis, Journal of theoretical biology, 176, 403-410, (1995)
[13]	C.K. Chow, H.T. Tsui, Autonomous agent response learning by a multi-species particle swarm optimization, in: Proceeding of Congress on Evolutionary Computation, Portland, Oregon, USA, 2004, pp. 778-785.
[14]	R. Brits, A.P. Engelbrecht, F. Bergh, A niching particle swarm optimizer, in: Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning 2002, pp. 692-696.
[15]	K.E. Parsopoulos, M.N. Vrahatis, Modification of the particle swarm optimizer for locating all the global minima, in: Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA2001), Prague, Czech Republic, 2001, pp. 324-327. · Zbl 1011.68103
[16]	Van den Bergh, F.; Engelbrech, A.P., A cooperative approach to particle swarm optimization, IEEE transactions on evolutionary computing, 8, 3, 225-239, (2004)
[17]	S. Baskar, P.N. Suganthan, A novel concurrent particle swarm optimization, in: Proceedings of the 2004 Congress on Evolutionary Computation, vol. 1, 2004, pp. 792-796.
[18]	T. Blackwell, J. Branke, Multi-swarm optimization in dynamic environments, in: Proceedings of Applications of Evolutionary Computing, Lecture Notes in Computer Science, Springer, vol. 3005, Portugal, 2004, pp. 488-599.
[19]	Kauffman, S.A.; Johnsen, S., Coevolution to the edge of chaos: coupled fitness landscapes poised states and coevolutionary avalanches, Journal of theoretical biology, 149, 467-505, (1991)
[20]	Clerc, M.; Kennedy, J., The particle swarm: explosion stability and convergence in a multidimensional complex space, IEEE transactions on evolutionary computation, 6, 1, 58-73, (2002)
[21]	T. Krink, J.S. Vestertroem, J. Riget, Particle swarm optimization with spatial particle extension, in: Proceedings of the IEEE Congress on Evolutionary Computation, Honolulu, Hawaii, 2002, pp. 1474-1479.
[22]	Y. Shi, R.C. Ebrehart, A modified particle swarm optimizer, in: Proceeding of the 1998 IEEE International Conference on Evolutionary Computation, Piscataway, NJ, 1998, pp. 69-73.
[23]	Y. Shi, R.C. Eberhart, Empirical study of particle swarm optimization, in: Proceedings of the 1999 IEEE Congress on Evolutionary Computation, Piscataway, NJ, 1999, pp. 1945-1950.
[24]	Niu, Ben; Zhu, Yunlong; He, XiaoXian; Zeng, Xiangping; Wu, Henry, MCPSO: a multi-swarm cooperative particle swarm optimizer, Applied mathematics and computation, 185, 2, 1050-1062, (2007) · Zbl 1112.65055
[25]	Zhang, Jun; Huang, D.S.; Lok, Tat-Ming; Lyu, Michael R., A novel adaptive sequential niche technique for multimodal function optimization, Neurocomputing, 69, 16-18, 2396-2401, (2006)
[26]	J. Kennedy, Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance, in: Proceedings of the Congress on Evolutionary Computation, Piscataway, NJ, 1999, pp. 1931-1938.
[27]	J. Kennedy, R. Mendes, Population structure and particle swarm performance, in: Proceedings of the 2002 Congress on Evolutionary Computation, Piscataway, NJ, 2002, pp. 1671-1675.
[28]	P.N. Suganthan, Particle swarm optimizer with neighborhood operator, in: Proceedings of the Congress on Evolutionary Computation (CEC 1999), Piscataway, NJ, 1999, pp. 1958-1962.
[29]	Shi, X.H.; Liang, Y.C.; Lee, H.P.; Lu, C.; Wang, L.M., An improved GA and a novel PSO-GA-based hybrid algorithm, Information processing letters, 93, 255-261, (2005) · Zbl 1173.68828
[30]	W.J. Zhang, X.F. Xie, DEPSO: Hybrid particle swarm with differential evolution operator, in: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Washington, DC, USA, 2003, pp. 3816-3821.
[31]	Ye, B.; Zhu, C.Z.; Guo, C.X.; Cao, Y.J., Generating extended fuzzy basis function networks using hybrid algorithm, Lecture notes in artificial intelligence, 3613, 79-88, (2005)
[32]	He, S.; Wu, Q.H.; Wen, J.Y.; Saunders, J.R.; Paton, R.C., A particle swarm optimizer with passive congregation, Biosystems, 78, 35-147, (2004)
[33]	B. Niu, Y.L. Zhu, X.X. He, Multi-population cooperative particle swarm optimization, in: Proceedings ECAL2005, Lecture Notes in Computer Science No. 3630, 2005, pp. 874-883.