How an optimal observer can collapse the search space

ABSTRACT

Many metaheuristics have difficulty exploring their search space comprehensively. Exploration time and efficiency are highly dependent on the size and the ruggedness of the search space. For instance, the Simple Genetic Algorithm (SGA) is not totally suited to traverse very large landscapes, especially deceptive ones. The approach introduced here aims at improving the exploration process of the SGA by adding a second search process through the way the solutions are coded. An "observer" is defined as each possible encoding that aims at reducing the search space. Adequacy of one observer is computed by applying this specific encoding and evaluating how this observer is beneficial for the SGA run. The observers are trained for a specific time by a second evolutionary stage. During the evolution of the observers, the most suitable observer helps the SGA to find a solution to the tackled problem faster. These observers aim at collapsing the search space and smoothing its ruggedness through a simplification of the genotype. A first implementation of this general approach is proposed, tested on the Shuffled Hierarchical IF-and-only-iF (SHIFF) problem. Very good results are obtained and some explanations are provided about why our approach tackles SHIFF so easily.

REFERENCES

• 1: H. Bersini. Whatever emerges should be intrinsically useful. In Artificial life 9, pages 226--231. The MIT Press, 2004.
• 2: Christian Blum , Andrea Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys (CSUR), v.35 n.3, p.268-308, September 2003 [doi>10.1145/937503.937505]
• 3: J. Crutchfield. Is anything ever new? considering emergence. In D. P. G. Cowan and D. Melzner, editors, Integrative Themes, volume XIX of Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley Publishing Company, Reading, Massachusetts, 1994.
• 4: J. Crutchfield and M. Mitchell. The evolution of emergent computation. In Proceedings of the National Academy of Science, volume 23, page 103, 1995.
• 5: E. D. de Jong, D. Thierens, and R. A. Watson. Hierarchical genetic algorithms. In X. Yao, E. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervós, J. A. Bullinaria, J. Rowe, P. T. A. Kabán, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature - PPSN VIII, volume 3242 of LNCS, pages 232--241, Birmingham, UK, 2004. Springer-Verlag.
• 6: Edwin D. de Jong , Richard A. Watson , Dirk Thierens, On the complexity of hierarchical problem solving, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068207]
• 7: A. Defaweux, T. Lenaerts, and J. I. van Hemert. Evolutionary transitions as a metaphor for evolutionary optimisation. In Advances in Artificial Life, 8th European Conference, ECAL 2005, Canterbury, UK, September 5-9, 2005, Proceedings, volume 3630 of Lecture Notes in Computer Science, pages 342--352. Springer, 2005.
• 8: Anne Defaweux , Tom Lenaerts , Jano van Hemert , Johan Parent, Transition models as an incremental approach for problem solving in evolutionary algorithms, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068110]
• 9: S. Forrest and M. Mitchell. Relative building-block fitness and the building block hypothesis. In L. D. Whitley, editor, FOGA, pages 109--126. Morgan Kaufmann, 1992.
• 10: Stephanie Forrest , Melanie Mitchell, What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation, Machine Learning, v.13 n.2-3, p.285-319, Nov./Dec. 1993 [doi>10.1007/BF00993046]
• 11: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 13: M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and ga performance. In F. J. Varela and P. Bourgine, editors, Proceedings of the First European Conference on Artificial Life, Cambridge, MA, 1992. MIT Press.
• 14: C. Philemotte and H. Bersini. Coevolution of effective observers and observed multi-agents system. In Advances in Artificial Life, 8th European Conference, ECAL 2005, Canterbury, UK, September 5-9, 2005, Proceedings, volume 3630 of Lecture Notes in Computer Science, pages 785--794. Springer, 2005.
• 15: Christophe Philemotte , Hugues Bersini, Intrinsic emergence boosts adaptive capacity, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068103]
• 16: Luc Steels, Towards a theory of emergent functionality, Proceedings of the first international conference on simulation of adaptive behavior on From animals to animats, p.451-461, February 1991, Paris, France
• 17: M. Toussaint. Compact genetic codes as a search strategy of evolutionary processes. In A. H. Wright, M. D. Vose, K. A. D. Jong, and L. M. Schmitt, editors, Foundations of Genetic Algorithms, 8th International Workshop, FOGA 2005, Aizu-Wakamatsu City, Japan, January 5-9, 2005, Revised Selected Papers, volume 3469 of Lecture Notes in Computer Science, pages 75--94. Springer, 2005.
• 18: Michael D. Vose, The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA, 1998
• 19: R. A. Watson. A computational model of symbiotic composition in evolutionary transitions. Biosystems, 69(2--3):187--209, 2003.
• 20: Richard A. Watson , Greg Hornby , Jordan B. Pollack, Modeling Building-Block Interdependency, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.97-108, September 27-30, 1998
• 21: Richard A. Watson , Jordan B. Pollack, Compositional evolution: interdisciplinary investigations in evolvability, modularity, and symbiosis, 2002
• 22: L. Whitley, K. Mathias, and P. Fitzhorn. Delta coding: An iterative search strategy for genetic algorithms. In Proc. of the Fourth International Conference on Genetic Algorithms, pages 77--84, San Diego, CA, 1991.

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, Design, Experimentation, Performance

Keywords:
landscape, observer, representation, simple genetic algorithm, speedup technique