Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Modularity is thought to improve the evolvability of biological systems [18, 22]. Recent studies in the field of evolutionary computation show that the use of modularity improves performance and scalability of evolutionary algorithms for certain applications. [5, 12, 15, 16, 17]. The effects of introducing modularity to evolutionary search, however, are not well understood. This paper focuses on analyzing the effects of modularity on evolutionary computation. In particular, we analyze the effects of modular representations on the search space bias.

REFERENCES

• 1: L. Altenberg. Fitness distance correlation analysis: An instructive counterexample. In T. Baeck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA97), pages 57--64, San Francisco, CA,, 1997. Morgan Kaufmann. http://dynamics.org/Altenberg/PAPERS/FDCAAIC/.
• 2: P. J. Angeline and J. B. Pollack. The evolutionary induction of subroutines. In Proceedings of the Fourteenth Annual Conference of the Cognitive Science Society, Bloomington, Indiana, USA, 1992. Lawrence Erlbaum.
• 3: P. J. Angeline and J. B. Pollack. Evolutionary module acquisition. In D. Fogel and W. Atmar, editors, Proceedings of the Second Annual Conference on Evolutionary Programming, pages 154--163, La Jolla, CA, USA, February 25-26 1993.
• 4: E. D. De Jong and T. Oates. A coevolutionary approach to representation development. In Proc. of the ICML-2002 WS on development of rep., page 1, 2002.
• 5: E. D. De Jong, D. Thierens, and R. A. Watson. Defining modularity, hierarchy, and repetition. In GECCO 2004 Workshop Proceedings, 2004.
• 6: I. I. Garibay, O. O. Garibay, and A. S. Wu. Effects of module encapsulation in repetitively modular genotypes on the search space. In GECCO '04: Proceedings of the Genetic and Evolutionary Computation Conference, pages 1125--1137, 2004.
• 7: O. O. Garibay, I. I. Garibay, and A. S. Wu. The modular genetic algorithm: Exploiting regularities in the problem space. In Proceedings of ISCIS 2003 The International Symposium on Computer and Information Systems, LNCS, pages 584--591. Springer-Verlag, 2003.
• 8: O. O. Garibay, I. I. Garibay, and A. S. Wu. No free luch theorem for modular genomes. Technical report, University of Central Florida, 2004.
• 9: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 10: D. G. Green, D. Newth, D. Cornforth, and M. Kirley. On evolutionary processes in natural and artificial systems. In P. Whigham et al., editors, Proceedings of the 5th Australia-Japan Joint Workshop on Intelligent and Evolutionary Systems, pages 1--10, 2001.
• 11: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 12: Gregory S. Hornby, Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068297]
• 13: Gregory S. Hornby , Jordan B. Pollack, Creating high-level components with a generative representation for body-brain evolution, Artificial Life, v.8 n.3, p.223-246, 2002 [doi>10.1162/106454602320991837]
• 14: Terry Jones , Stephanie Forrest, Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.184-192, July 15-19, 1995
• 15: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 16: H. Lipson. Principles of modularity, regularity, and hierarchy for scalable systems. In GECCO 2004 Workshop Proceedings, 2004.
• 17: H. Lipson, J. B. Pollack, and N. P. Suh. Promoting modularity in evolutionary design. In Proceedings of DETC'01: 2001 ASME Design and Engineering Technical Conferences, Pittsburg, Pennsylvania, USA, September 9-12 2001.
• 18: H. Meinhardt. Pathways and building blocks. Nature, 430:970--970, 2004.
• 19: Mitchell A. Potter , Kenneth A. De Jong, A Cooperative Coevolutionary Approach to Function Optimization, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.249-257, October 09-14, 1994
• 20: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 21: J. P. Rosca and D. H. Ballard. Learning by adapting representations in genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, Orlando, Florida, USA, 27-29 June 1994. IEEE Press.
• 22: G. Schlosser and G. P. Wagner, editors. Modularity in Development and Evolution. The University of Chicago Press, 2004. QH 491.M59 2004.
• 23: A. S. Wu and R. K. Lindsay. Empirical studies of the genetic algorithm with non-coding segments. Evolutionary Computation, 3(2):121--147, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

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

General Terms:
Algorithms

Keywords:
genetic algorithms, modularity, search algorithms