Representations for evolutionary algorithms

ABSTRACT

Successful and efficient use of evolutionary algorithms (EAs) depends on the choice of the genotype, the problem representation (mapping from genotype to phenotype) and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation.

In EA practice one can distinguish two complementary approaches. The first approach uses indirect representations where a solution is encoded in a standard data structure, such as strings, vectors, or discrete permutations, and standard off-the-shelf search operators are applied to these genotypes. To evaluate the solution, the genotype needs to be mapped to the phenotype space. The proper choice of this genotype-phenotype mapping is important for the performance of the EA search process. The second approach, the direct representation, encodes solutions to the problem in its most 'natural' space and designs search operators to operate on this representation.

Research in the last few years has identified a number of key concepts to analyse the influence of representation-operator combinations on EA performance. These concepts are *locality and *redundancy. Locality is a result of the interplay between the search operator and the genotype-phenotype mapping. Representations are redundant if the number of phenotypes exceeds the number of possible genotypes. Furthermore, redundant representations can lead to biased encodings if some phenotypes are on average represented by a larger number of genotypes. Finally, a bias need not be the result of the representation but can also be caused by the search operator.

The tutorial gives a brief overview about existing guidelines for representation design, illustrates the different aspects of representations, gives a brief overview of theoretical models describing the different aspects, and illustrates the relevance of the aspects with practical examples.

It is expected that the participants have a basic understanding of EA principles.

REFERENCES

• 1: Barnett, L. (1997). Tangled webs: Evolutionary dynamics on fitness landscapes with neutrality. Master's thesis, School of Cognitive Sciences, University of East Sussex, Brighton.
• 2: Lionel Barnett, Ruggedness and neutrality—the NKp family of fitness landscapes, Proceedings of the sixth international conference on Artificial life, p.18-27, August 1998, Madison, Wisconsin, United States
• 3: Barnett, L. (2001). Netcrawling -- optimal evolutionary search with neutral networks. In Proceedings of the 2001 Congress on Evolutionary Computation CEC01, pages 30--37, Piscataway, NJ. IEEE Press.
• 4: David Beasley , David R. Bull , Ralph R. Martin, Reducing Epistasis in Combinatorial Problems by Expansive Coding, Proceedings of the 5th International Conference on Genetic Algorithms, p.400-407, June 01, 1993
• 5: Choi, S.-S. and Moon, B.-R. (2003). Normalization in genetic algorithms. In et al., E. C.-P., editor, Proceedings of the Genetic and Evolutionary Computation Conference 2003, pages 862--873, Heidelberg. Springer.
• 6: Choi, S.-S. and Moon, B.-R. (2007). Normalization in genetic algorithms. forthcoming in IEEE Transactions on Evolutionary Computation.
• 7: Cohoon, J. P., Hegde, S. U., Martin, W. N., and Richards, D. (1988). Floorplan design using distributed genetic algorithms. In IEEE International Conference on Computer Aided-Design, pages 452--455. IEEE.
• 8: Jason M. Daida , Robert R. Bertram , Stephen A. Stanhope , Jonathan C. Khoo , Shahbaz A. Chaudhary , Omer A. Chaudhri , John A. Ii Polito, What Makes a Problem GP-Hard? Analysis of a Tunably Difficult Problem in Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.2, p.165-191, June 2001 [doi>10.1023/A:1011504414730]
• 9: Lawrence Davis, Adapting Operator Probabilities in Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.61-69, June 01, 1989
• 10: Ebner, M., Langguth, P., Albert, J., Shackleton, M., and Shipman, R. (2001). On neutral networks and evolvability. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pages 1--8, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea. IEEE Press.
• 11: Eshelman, L. J. and Schaffer, J. D. (1991). Preventing premature convergence in genetic algorithms by preventing incest. In Belew, R. K. and Booker, L. B., editors, Proceedings of the Fourth International Conference on Genetic Algorithms}, pages 115--122, San Mateo, CA. Morgan Kaufmann.
• 12: Feller, W. (1957). An Introduction to Probability Theory and its Applications, volume 1. John Wiley & Sons, New York, 1st edition.
• 13: Fogel, D. B. and Stayton, L. C. (1994). On the effectiveness of crossover in simulated evolutionary optimization. BioSystems, 32:171--182.
• 14: Fox, B. R. and McMahon, M. B. (1991). Genetic operators for sequencing problems. In Rawlins, G. J. E., editor, Foundations of Genetic Algorithms, pages 284--300, San Mateo, CA. Morgan Kaufmann.
• 15: Marleen Gerrits , Paulien Hogeweg, Redundant Coding of an NP-Complete Problem Allows Effective Genetic Algorithm Search, Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, p.70-74, October 01-03, 1990
• 16: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 17: Goldberg, D. E. (1991). Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems, 5(2):139--167. (Also IlliGAL Report 90001).
• 18: Harik, G. R., Cantú-Paz, E., Goldberg, D. E., and Miller, B. L. (1997). The gambler's ruin problem, genetic algorithms, and the sizing of populations. In Bäck, T., editor, Proceedings of the Fourth International Conference on Evolutionary Computation}, pages 7--12, New York. IEEE Press.
• 19: Hartl, D. L. and Clark, A. G. (1997). Principles of population genetics. Sinauer Associates, Sunderland, Massachusetts, 3rd edition.
• 20: Hoai, N. X., BobMcKay, R. I., and Essam, D. L. (2006). Representation and structural difficulty in genetic programming. IEEE Trans. Evolutionary Computation, 10(2):157--166.
• 21: 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
• 22: Julstrom, B. A. (1999). Redundant genetic encodings may not be harmful. In Banzhaf, W., Daida, J., Eiben, A. E., Garzon, M. H., Honavar, V., Jakiela, M., and Smith, R. E., editors, Proceedings of the Genetic and Evolutionary Computation Conference: Volume 1, page 791, San Francisco, CA. Morgan Kaufmann Publishers.
• 23: Kimura, M. (1964). Diffusion models in population genetics. J. Appl. Prob., 1:177--232.
• 24: Kimura, M. (1983). The Neutral Theory of Molecular Evolution. Cambridge University Press.
• 25: Joshua D. Knowles , Richard A. Watson, On the Utility of Redundant Encodings in Mutation-Based Evolutionary Search, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.88-98, September 07-11, 2002
• 26: Liepins, G. E. and Vose, M. D. (1990). Representational issues in genetic optimization. Journal of Experimental and Theoretical Artificial Intelligence, 2:101--115.
• 27: Lobo, F. G., Goldberg, D. E., and Pelikan, M. (2000). Time complexity of genetic algorithms on exponentially scaled problems. In Whitley, D., Goldberg, D. E., Cantú-Paz, E., Spector, L., Parmee, L., and Beyer, H.-G., editors, Proceedings of the Genetic and Evolutionary Computation Conference 2000, pages 151--158, San Francisco, CA. Morgan Kaufmann Publishers.
• 28: Moraglio, A. and Poli, R. (2004). Topological interpretation of crossover. In Deb, Kalyanmoy et al., editor, gecco2004, pages 1377--1388, Heidelberg. Springer.
• 29: Charles Campbell Palmer, An approach to a problem in network design using genetic algorithms, Polytechnic University, Brooklyn, NY, 1994
• 30: Radcliffe, N. J. (1992). Non-linear genetic representations. In Männer, R. and Manderick, B., editors, Parallel Problem Solving from Nature-PPSN II, pages 259--268, Berlin. Springer-Verlag.
• 31: Radcliffe, N. J. (1997). Theoretical foundations and properties of evolutionary computations: schema processing. In Bäck, T., Fogel, D. B., and Michalewicz, Z., editors, Handbook of Evolutionary Computation, pages B2.5:1--B2.5:10. Institute of Physics Publishing and Oxford University Press, Bristol and New York.
• 32: Raidl, G. R. (2000). An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem. In Proceedings of 2000 IEEE International Conference on Evolutionary Computation, pages 43--48, Piscataway, NJ. IEEE.
• 33: Reeves, C. (2000). Fitness landscapes: A guided tour. Joint tutorials of SAB 2000 and PPSN 2000, tutorial handbook.
• 34: Ronald, S. (1997). Robust encodings in genetic algorithms: A survey of encoding issues. In Proceedings of the Fourth International Conference on Evolutionary Computation, pages 43--48, Piscataway, NJ. IEEE.
• 35: Ronald, S., Asenstorfer, J., and Vincent, M. (1995). Representational redundancy in evolutionary algorithms. In 1995 IEEE International Conference on Evolutionary Computation, volume 2, pages 631--636, Piscataway, NJ. IEEE Service Center.
• 36: Rothlauf, F. (2002). Representations for Genetic and Evolutionary Algorithms. Number 104 in Studies on Fuzziness and Soft Computing. Springer, Heidelberg, 1 edition.
• 37: Franz Rothlauf , David E. Goldberg, Redundant representations in evolutionary computation, Evolutionary Computation, v.11 n.4, p.381-415, Winter 2003 [doi>10.1162/106365603322519288]
• 38: Shackleton, M., Shipman, R., and Ebner, M. (2000). An investigation of redundant genotype-phenotype mappings and their role in evolutionary search. In Proceedings of the 2000 Congress on Evolutionary Computation CEC00, pages 493--500, La Jolla Marriott Hotel La Jolla, California, USA. IEEE Press.
• 39: Shipman, R. (1999). Genetic redundancy: Desirable or problematic for evolutionary adaptation? In Proceedings of the 4th International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA)}, pages 1--11. Springer Verlag.
• 40: Shipman, R., Shackleton, M., Ebner, M., and Watson, R. (2000a). Neutral search spaces for artificial evolution: A lesson from life. In Bedau, M., McCaskill, J., Packard, N., and Rasmussen, S., editors, Proceedings of Artificial Life VII, page section III (Evolutionary and Adaptive Dynamics). MIT Press.
• 41: R. Shipman , M. Shackleton , I. Harvey, The Use of Neutral Genotype-Phenotype Mappings for Improved Evolutionary Search, BT Technology Journal, v.18 n.4, p.103-111, October 2000 [doi>10.1023/A:1026714927227]
• 42: Smith, T., Husbands, P., and O'Shea, M. (2001a). Evolvability, neutrality and search space. Technical Report 535, School of Cognitive and Computing Sciences, University of Sussex.
• 43: Tom Smith , Phil Husbands , Michael O'Shea, Neutral Networks and Evolvability with Complex Genotype-Phenotype Mapping, Proceedings of the 6th European Conference on Advances in Artificial Life, p.272-281, September 10-14, 2001
• 44: Smith, T., Husbands, P., and O'Shea, M. (2001c). Neutral networks in an evolutionary robotics search space. In of Electrical, I. and Engineers, E., editors, Proceedings of 2001 IEEE International Conference on Evolutionary Computation, pages 136--145, Piscataway, NJ. IEEE Service Center.
• 45: Patrick D. Surry , Nicholas J. Radcliffe, Formal Algorithms + Formal Representations = Search Strategies, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.366-375, September 22-26, 1996
• 46: Patrick D. Surry , Nicholas J. Radcliffe, Formal Algorithms + Formal Representations = Search Strategies, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.366-375, September 22-26, 1996
• 47: Thierens, D., Goldberg, D. E., and Pereira, Â. G. (1998). Domino convergence, drift, and the temporal-salience structure of problems. In of Electrical, I. and Engineers, E., editors, Proceedings of 1998 IEEE International Conference on Evolutionary Computation, pages 535--540, Piscataway, NJ. IEEE Service Center.
• 48: M. Toussaint , C. Igel, Neutrality: a necessity for self-adaptation, Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, p.1354-1359, May 12-17, 2002
• 49: 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
• 50: Whitley, D. (2000). Walsh analysis, schemata, embedded landscapes and no free lunch. Joint Tutorials of SAB 2000 and PPSN 2000.
• 51: Tina Yu , Julian F. Miller, Neutrality and the Evolvability of Boolean Function Landscape, Proceedings of the 4th European Conference on Genetic Programming, p.204-217, April 18-20, 2001
• 52: Tina Yu , Julian F. Miller, Finding Needles in Haystacks Is Not Hard with Neutrality, Proceedings of the 5th European Conference on Genetic Programming, p.13-25, April 03-05, 2002

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:
bias, design guidelines, locality, representations, scaling