Volume 2 Issue 2 pp. 419-430 Spring, 2011


A multilevel evolutionary algorithm for optimizing numerical functions


Reza Akbari and Koorush Ziarati


This is a study on the effects of multilevel selection (MLS) theory in optimizing numerical functions. Based on this theory, a Multilevel Evolutionary Optimization algorithm (MLEO) is presented. In MLEO, a species is subdivided in cooperative populations and then each population is subdivided in groups, and evolution occurs at two levels so called individual and group levels. A fast population dynamics occurs at individual level. At this level, selection occurs among individuals of the same group. The popular genetic operators such as mutation and crossover are applied within groups. A slow population dynamics occurs at group level. At this level, selection happens among groups of a population. The group level operators such as regrouping, migration, and extinction-colonization are applied among groups. In regrouping process, all the groups are mixed together and then new groups are formed. The migration process encourages an individual to leave its own group and move to one of its neighbour groups. In extinction-colonization process, a group is selected as extinct, and replaced by offspring of a colonist group. In order to evaluate MLEO, the proposed algorithms were used for optimizing a set of well known numerical functions. The preliminary results indicate that the MLEO theory has positive effect on the evolutionary process and provide an efficient way for numerical optimization.


DOI: 10.5267/j.ijiec.2010.03.002

Keywords: Meta-Heuristic, Genetic Algorithm, Multilevel Selection, Colonization, Regrouping, Migration, Numerical Functions
References

Bergmuller, R., Russell, A. F., Johnstone, R. A. & Bshary, R. (2007). On the further integration of cooperative breeding and cooperation theory, Journal of Behavioural Processes, 76, 170–181.

Billard, S. & Lenormand, T. (2005). Evolution of migration under kin selection and local adaptation, The Society for the Study of Evolution. 59(1), 13–23.

Boyer, D. O., Martnez, C. H. & Pedrajas, N. G. (2007). Crossover Operator for Evolutionary Algorithms Based on Population Features, Applied Soft Computing, 39(3), 459-471.

Fletchera, J. A. & Zwick, M. (2007). The evolution of altruism: Game theory in multilevel selection and inclusive fitness, Journal of Theoretical Biology, 245, 26–36.

Frank, S. A. (1986). Dispersal polymorphism in subdivided populations, Journal of Theoretical Biology, 122:303–309.

Hamilton, W. D. & May, R. M. (1977). Dispersal in stable habitats, Nature, 269:578–581.

Hogeweg, P., 2002. Multilevel processes in evolution and development: Computational models and biological insights, Springer-Verlag Berlin Heidelberg, 217–239.

Ichinose, G. & Arita, T. (2008). The role of migration and founder effect for the evolution of cooperation in a multilevel selection context”, journal of ecological modelling, 210, 221–230.

Kennedy, J. & Eberhart, R. (1995). Particle swarm optimization, Proceeding of IEEE Int. Conference of Neural Networks, 4, 1942–1947.

McAndrew, F. T. (2002). New Evolutionary Perspectives on Altruism: Multilevel-Selection and Costly-Signaling Theories, Current Directions in Psychological Science, 11(2), 79-81.

Potter, M. A. & de Jong, K. A. 1994, A cooperative coevolutionary approach to function optimization, The Third Parallel Problem Solving From Nature. Berlin, Germany: Springer-Verlag, 249–257.

Sober, E. & Wilson, D. S. (1998). Unto others, the evolution and psychology of unselfish behaviour, Harvard University Press.

Srinivasan, D. & Seow, T. H. 2003. Evolutionary Computation, The 2003 congress on evolutionary computations, Canberra, Australia, 2292–2297, 2003.

Traulsen, A. & Nowak, M. A. (2006). Evolution of cooperation by multilevel selection, Proceedings of the national academy of sciences of the United States of America, 103(29), 10952-10955, 2006.

Valleriani, A. & Meene, T. (2007). Multilevel selection in a gradient, journal of ecological modeling, 208, 159–164.

Venable, D. L. & Brown, J. S. (1998). The selective interactions of dispersal, dormancy, and seed size as adaptations for reducing risk in variable environment”, American Naturalist, 131:360–384.