Centric selection: a way to tune the exploration/exploitation trade-off

ABSTRACT

In this paper, we study the exploration / exploitation trade-off in cellular genetic algorithms. We define a new selection scheme, the centric selection, which is tunable and allows controlling the selective pressure with a single parameter. The equilibrium model is used to study the influence of the centric selection on the selective pressure and a new model which takes into account problem dependent statistics and selective pressure in order to deal with the exploration / exploitation trade-off is proposed: the punctuated equilibria model. Performances on the quadratic assignment problem and NK-Landscapes put in evidence an optimal exploration / exploitation trade-off on both of the classes of problems. The punctuated equilibria model is used to explain these results.

REFERENCES

• 1: Enrique Alba , Bernab Dorronsoro, Cellular Genetic Algorithms, Springer Publishing Company, Incorporated, 2008
• 2: E. Alba and G. Luque. Growth Curves and Takeover Time in Distributed Evolutionary Algorithms. In K. D. et al., editor, Genetic and Evolutionary Computation Conference (GECCO--2004), volume 3102 of Lecture Notes in Computer Science, pages 864--876, Seattle, Washington, 2004.
• 3: Enrique Alba , José M. Troya, Cellular Evolutionary Algorithms: Evaluating the Influence of Ratio, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.29-38, September 18-20, 2000
• 4: M. Giacobini, E. Alba, and M. Tomassini. Selection intensity in asynchronous cellular evolutionary algorithms. In GECCO, pages 955--966, 2003.
• 5: M. Giacobini, M. Tomassini, A. Tettamanzi, and E. Alba. Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Trans. Evolutionary Computation, 9(5):489--505, 2005.
• 6: D. E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. In FOGA, pages 69--93, 1990.
• 7: M. Gorges-Schleuter. An analysis of local selection in evolution strategies. In GECCO, pages 847--854, 1999.
• 8: S. Janson, E. Alba, B. Dorronsoro, and M. Middendorf. Hierarchical cellular genetic algorithm. In J. Gottlieb and G. R. Raidl, editors, Evolutionary Computation in Combinatorial Optimization EvoCOP, volume 3906, page 111.122, 2006.
• 9: Kenneth A. De Jong , Jayshree Sarma, On Decentralizing Selection Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.17-23, July 15-19, 1995
• 10: S. A. Kauffman. The Origins of Order. Oxford University Press, New York, 1993.
• 11: T. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. Econometrica, 25(1):53--76, 1957.
• 12: V. Migkikh, E. Topchy, V. Kureichik, and E. Tetelbaum. Combined genetic and local search algorithm for the quadratic assignment. In Proceedings of the SecondAsia-Pacific Conference on Genetic Algorithms and Applications (APGA, pages 144--151, 2000.
• 13: Alfonsas Misevicius, A fast hybrid genetic algorithm for the quadratic assignment problem, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144194]
• 14: C. Nugent, T. Vollman, and J. Ruml. An experimental comparison of techniques for the assignment of techniques to locations. Operations Research, 16:150--173, 1968.
• 15: Gabriela Ochoa , Marco Tomassini , Sebástien Vérel , Christian Darabos, A study of NK landscapes' basins and local optima networks, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389204]
• 16: Jayshree Sarma , Kenneth A. De Jong, An Analysis of the Effects of Neighborhood Size and Shape on Local Selection Algorithms, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.236-244, September 22-26, 1996
• 17: David Simoncini , Sébastien Verel , Philippe Collard , Manuel Clergue, Anisotropic selection in cellular genetic algorithms, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144098]
• 18: P. Spiessens and B. Manderick. A massively parallel genetic algorithm: Implementation and first analysis. In ICGA, pages 279--287, 1991.
• 19: J. Sprave. A unified model of non--panmictic population structures in evolutionary algorithms. Proceedings of the congress on Evolutionary computation, 2:1384--1391, 1999.
• 20: Marco Tomassini, Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 21: S. Verel, M. Tomassini, and G. Ochoa. The connectivity of nk landscapes' basins: a network analysis. In Proceedings of Artificial Life XI, pages 648--655, 8-5 2008.
• 22: E. Weinberger. Correlated and un correlated fitness landscapes and how to tell the difference. In Biological Cybernetics, pages 63:325--336, 1990.
• 23: L. Darrell Whitley, Cellular Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.658, June 01, 1993

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
cellular evolutionnary algorithms, selection operators, selective pressure, theoretical model