Genotypic differences and migration policies in an island model

ABSTRACT

In this paper we compare different policies to select individuals to migrate in an island model. Our thesis is that choosing individuals in a way that exploits differences between populations can enhance diversity, and improve the system performance. This has lead us to propose a family of policies that we call multikulti, in which nodes exchange individuals different "enough" among them. In this paper we present a policy according to which the receiver node chooses the most different individual among the sample received from the sending node. This sample is randomly built but only using individuals with a fitness above a threshold. This threshold is previously established by the receiving node. We have tested our system in two problems previously used in the evaluation of parallel systems, presenting different degree of difficulty. The multikulti policy presented herein has been proved to be more robust than other usual migration policies, such as sending the best or a random individual.

REFERENCES

• 1: Michael Affenzeller , Stefan Wagner, SASEGASA: A New Generic Parallel Evolutionary Algorithm for Achieving Highest Quality Results, Journal of Heuristics, v.10 n.3, p.243-267, May 2004 [doi>10.1023/B:HEUR.0000026895.72657.a2]
• 2: Enrique Alba , Bernab Dorronsoro, Cellular Genetic Algorithms, Springer Publishing Company, Incorporated, 2008
• 3: Enrique Alba , Antonio J. Nebro , José M. Troya, Heterogeneous computing and parallel genetic algorithms, Journal of Parallel and Distributed Computing, v.62 n.9, p.1362-1385, September 2002 [doi>10.1006/jpdc.2002.1851]
• 4: Enrique Alba , José M. Troya, Influence of the Migration Policy in Parallel DistributedGAs with Structured and Panmictic Populations, Applied Intelligence, v.12 n.3, p.163-181, May-June 2000 [doi>10.1023/A:1008358805991]
• 5: Enrique Alba , José M. Troya, Analyzing synchronous and asynchronous parallel distributed genetic algorithms, Future Generation Computer Systems, v.17 n.4, p.451-465, January 2001 [doi>10.1016/S0167-739X(99)00129-6]
• 6: L. Araujo, J.J. Merelo, C. Cotta, and F. de Vega. MultiKulti Algorithm: Migrating the Most Different Genotypes in an Island Model. ArXiV preprint arXiv:0806.2843, 2008.
• 7: E. Cantú-Paz. Migration policies and takeover times in genetic algorithms. In GECCO, page 775, 1999.
• 8: Erick Cantú-Paz, Migration Policies, Selection Pressure, and Parallel Evolutionary Algorithms, Journal of Heuristics, v.7 n.4, p.311-334, July 2001 [doi>10.1023/A:1011375326814]
• 9: R.J. Collins and D.R. Jefferson. Selection in massively parallel genetic algorithms. In R.K. Belew and L.B. Booker, editors, Proceedings of the 4th International Conference on Genetic Algorithms, pages 249--256, San Diego, CA, 1991. Morgan Kaufmann.
• 10: Kenneth De Jong, Evolutionary computation: a unified approach, Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1388969.1389054]
• 11: J. Denzinger and J. Kidney. Improving migration by diversity. In 2003 Congress on Evolutionary Computation, volume 1, pages 700--707. IEEE Press, 2003.
• 12: T. Eldos. A New Migration Model For Distributed Genetic Algorithms. In Proceedings of the International Conference on Scientific Computing (CSC' 06), Las Vegas, NV, pages 128--134, 2006.
• 13: M. Giacobini, M. Preuss, and M. Tomassini. Effects of scale-free and small-world topologies on binary coded self-adaptive CEA. In J. Gottlieb and G.R. Raidl, editors, Evolutionary Computation in Combinatorial Optimization -- EvoCOP 2006, volume 3906 of LNCS, pages 85--96, Budapest, 10-12 April 2006. Springer Verlag.
• 14: D.E. Goldberg, K. Deb, and J. Horn. Massive multimodality, deception, and genetic algorithms. In R. Männer and B. Manderick, editors, Parallel Problem Solving from Nature, 2, Amsterdam, 1992. Elsevier Science Publishers, B.V.J.J. Merelo. Evolutionary computation in Perl. In M. Perl Mongers, editor, YAPC:Europe::2002, pages 2--22, 2002.
• 15: E.D.D. Jong, R.A. Watson, and J.B. Pollack. Reducing Bloat and Promoting Diversity using Multi-Objective Methods. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pages 11--18. Morgan Kaufmann Publishers, 2001.
• 16: K.A.D. Jong, M.A. Potter, and W.M. Spears. Using problem generators to explore the effects of epistasis. In T. Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA97), San Francisco, CA, 1997. Morgan Kaufmann.
• 17: Juan J. Merelo , Antonio M. Mora , Pedro A. Castillo , Juan L. Laredo , Lourdes Araujo , Ken C. Sharman , Anna I. Esparcia-Alcázar , Eva Alfaro-Cid , Carlos Cotta, Testing the Intermediate Disturbance Hypothesis: Effect of Asynchronous Population Incorporation on Multi-Deme Evolutionary Algorithms, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_27]
• 18: P. Moscato and M.G. Norman. A Memetic Approach for the Traveling Salesman Problem Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing Systems. In M. Valero, E. Onate, M. Jane, J.L. Larriba, and B. Suarez, editors, Parallel Computing and Transputer Applications, pages 177--186, Amsterdam, 1992. IOS Press.
• 19: H. Muhlenbein. Evolution in time and space -- the parallel genetic algorithm. In G. Rawlings, editor, Foundations of Genetic Algorithms, pages 316--337. Morgan Kaufmann, 1991.
• 20: E. Noda, A. Coelho, I. Ricarte, A. Yamakami, and A. Freitas. Devising adaptive migration policies for cooperative distributed genetic algorithms. IEEE International Conference on Systems, Man and Cybernetics, 2002, pp. 6.
• 21: D. Power, C. Ryan, and R. Azad. Promoting diversity using migration strategies in distributed genetic algorithms. IEEE Conqress on Evolutionary Computation, 2:1831--1838, 2005.
• 22: P. Spiessens and B. Manderick. A massively parallel genetic algorithm: Implementation and first analysis. In R.K. Belew and L.B. Booker, editors, Proceedings of the 4th International Conference on Genetic Algorithms, pages 279--287, San Diego, CA, 1991. Morgan Kaufmann.
• 23: J. Stender. Parallel Genetic Algorithms: Theory and Applications, chapter Implementation in Occam of Parallel Genetic Algorithms on Transputer Networks. IOS Press, 1993.
• 24: R. Tanese. Distributed genetic algorithms. In J.D. Schaeffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 434--439, San Mateo, California, 1989. Morgan Kaufmann Publishers.
• 25: Marco Tomassini, Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 26: R.K. Ursem. Diversity-guided evolutionary algorithms.
• 27: In J.J. Merelo, P. Adamidis, H.-G. Beyer, J.L.F.-V. Martín, and H.-P. Schwefel, editors, PPSN, volume 2439 of Lecture Notes in Computer Science, pages 462--474. Springer, 2002.
• 28: J. Ward and J. Stanford. Intermediate-Disturbance Hypothesis: An Explanation for Biotic Diversity Patterns in Lotic Ecosystems. Dynamics of Lotic Systems, Ann Arbor Science, Ann Arbor MI. 1983. 347--356 p, 2 fig, 35 ref., 1983.
• 29: D. Whitley, S. Rana, and R. Heckendorn. The island model genetic algorithm: On separability, population size and convergence. Journal of Computing and Information Technology, 7:33--47, 1999.
• 30: S. Yang and R. Tinós. A hybrid immigrants scheme for genetic algorithms in dynamic environments. International Journal of Automation and Computing, 4(3):243--254, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance

Keywords:
diversity, genetic algorithms, island model, migration policy, parallelism