An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization

ABSTRACT

Cellular genetic algoritms (cGAs) are characterized by its grid structure population, in which individuals can only interact with their neighbors. This kind of algorithms has demonstrated to have a high numerical performance thanks to the good exploration/exploitation balance they perform in the search space. Although cGAs seem very appropriate for parallelism, there is a low number of works proposing or studing parallel models for clusters of computers. This is probably because the model requires a high communication level between sub-populations due to the tight interactions among individuals. These parallel versions are however needed to cope with the high computational requirements of the current real-world problems. This article proposes a new parallel cellular genetic algorithm which maintains (or even improves because its asynchronicity) the numerical behaviour of a serial cGA, while at the same time it provokes an important reduction on the execution time for finding the optimal solution.

REFERENCES

• 1: Enrique Alba, Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, 2005
• 2: E. Alba , F. Almeida , M. Blesa , C. Cotta , M. Díaz , I. Dorta , J. Gabarró , C. León , G. Luque , J. Petit , C. Rodríguez , A. Rojas , F. Xhafa, Efficient parallel LAN/WAN algorithms for optimization: the MALLBA project, Parallel Computing, v.32 n.5, p.415-440, June 2006 [doi>10.1016/j.parco.2006.06.007]
• 3: Enrique Alba , Bernab Dorronsoro, Cellular Genetic Algorithms, Springer Publishing Company, Incorporated, 2008
• 4: E. Alba, B. Dorronsoro, M. Giacobini, and M. Tomassini. Handbook of Bioinspired Algorithms and Applications, chapter 7, Decentralized Cellular Evolutionary Algorithms, pages 103--120. CRC Press, 2006.
• 5: E. Alba and M. Tomassini. Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 6(5):443--462, October 2002.
• 6: J. Beasley. A note on solving large-median problems. European Journal on Operations Reserach, 21:270--273, 1985.
• 7: R.C. and S.R. Central facilities location. Geographical Analysis, 2:30--42, 1970.
• 8: Erick Cantu-Paz, Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: K.D.D. Goldberg and J. Horn. Massively multimodality, deception and genetic algorithms. In R. Männer and B. Manderick, editors, Proceedings of the PPSN II, pages 37--46. North-Holland, 1992.
• 11: K.D. Jong, M. Potter, and W. Spears. Using problem generators to explore the effects of epistasis. In T. Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA), pages 338--345. Morgan Kaufmann, 1997.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

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

General Terms:
Performance

Keywords:
asynchronous cellular gas, combinatorial optimization, parallelism