Franz Rothlauf
ABSTRACT
Successful and efficient use of evolutionary algorithms (EA) 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. This is for example the case in standard genetic algorithms, evolution strategies, and some genetic programming approaches like grammatical evolution or cartesian genetic programming. 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. Relevant properties of representations 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. Redundant representations can lead to biased encodings if some phenotypes are on average represented by a larger number of genotypes or search operators favor some kind of phenotypes.
The tutorial gives a brief overview about existing guidelines for representation design, illustrates the different aspects of representations, gives a brief overview of 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.
- Bäck, T., Michalewicz, Z., and Yao, X., editors (1997). Proceedings of the Fourth International Conference on Evolutionary Computation, Piscataway. IEEE Service Center.Google Scholar
- Barnett, L. (1997). Tangled webs: Evolutionary dynamics on fitness landscapes with neutrality. Master's thesis, School of Cognitive Sciences, University of East Sussex, Brighton.Google Scholar
- Barnett, L. (1998). Ruggedness and neutrality: The NKp family of fitness landscapes. In Adami, C., Belew, R. K., Kitano, H., and Taylor, C. E., editors, Proceedings of the 6th International Conference on Artificial Life (ALIFE-98), pages 18--27, Cambridge. MIT Press. Google ScholarDigital Library
- Barnett, L. (2001). Netcrawling - optimal evolutionary search with neutral networks. In (Kim et al., 2001), pages 30--37.Google Scholar
- Beasley, D., Bull, D. R., and Martin, R. R. (1993). Reducing epitasis in combinatorial problems by expansive coding. In Forrest, S., editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 400--407, San Francisco. Morgan Kaufmann. Google ScholarDigital Library
- Choi, S.-S. and Moon, B.-R. (2003). Normalization in genetic algorithms. In Cantú-Paz, E., Foster, J. A., Deb, K., Davis, D., Roy, R., O'Reilly, U.-M., Beyer, H.-G., Standish, R., Kendall, G., Wilson, S., Harman, M., Wegener, J., Dasgupta, D., Potter, M. A., Schultz, A. C., Dowsland, K., Jonoska, N., and Miller, J., editors, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2003, pages 862--873, Heidelberg. Springer. Google ScholarDigital Library
- Choi, S.-S. and Moon, B.-R. (2008). Normalization for genetic algorithms with nonsynonymously redundant encodings. IEEE Trans. Evolutionary Computation, 12(5):604--616. Google ScholarDigital Library
- 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, Piscataway. IEEE.Google ScholarCross Ref
- Daida, J. M., Bertram, R., Stanhope, S., Khoo, J., Chaudhary, S., Chaudhri, O., and Polito, J. (2001). What makes a problem GP-hard? Analysis of a tunably difficult problem in genetic programming. Genetic Programming and Evolvable Machines, 2(2):165--19 Google ScholarDigital Library
- Davis, L. (1989). Adapting operator probabilities in genetic algorithms. In Schaffer, J. D., editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 61--69, Burlington. Morgan Kaufmann. Google ScholarDigital Library
- Ebner, M., Langguth, P., Albert, J., Shackleton, M., and Shipman, R. (2001). On neutral networks and evolvability. In (Kim et al., 2001), pages 1--8.Google Scholar
- 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, Burlington. Morgan Kaufmann.Google Scholar
- Feller, W. (1957). An Introduction to Probability Theory and its Applications, volume 1. John Wiley & Sons, New York, 1st edition.Google Scholar
- Fogel, D. B. and Stayton, L. C. (1994). On the effectiveness of crossover in simulated evolutionary optimization. BioSystems, 32:171--182.Google ScholarCross Ref
- Fonseca, C., Kim, J.-H., and Smith, A., editors (2000). Proceedings of 2000 IEEE Congress on Evolutionary Computation, Piscataway. IEEE Press.Google Scholar
- 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. Morgan Kaufmann.Google Scholar
- Gerrits, M. and Hogeweg, P. (1991). Redundant coding of an NP-complete problem allows effective genetic algorithm search. In Schwefel, H.-P. and Männer, R., editors, Parallel Problem Solving from Nature - PPSN I, volume 496 of LNCS, pages 70--74, Berlin. Springer. Google ScholarDigital Library
- Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading. Google ScholarDigital Library
- Goldberg, D. E. (1991). Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems, 5(2):139--167.Google Scholar
- 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 et al., 1997), pages 7--12.Google Scholar
- Hoai, N. X., McKay, R. I., and Essam, D. L. (2006). Representation and structural difficulty in genetic programming. IEEE Trans. Evolutionary Computation, 10(2):157--166. Google ScholarDigital Library
- Jones, T. and Forrest, S. (1995). Fitness distance correlation as a measure of problem difficulty for genetic algorithms. Proceedings of the Sixth International Conference on Genetic Algorithms, pages 184--192. Google ScholarDigital Library
- 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, GECCO '99, page 791, Burlington. Morgan Kaufmann.Google Scholar
- Kim, J.-H., Zhang, B.-T., Fogel, G., and Kuscu, I., editors (2001). Proceedings of 2001 IEEE Congress on Evolutionary Computation, Piscataway. IEEE Press.Google Scholar
- Kimura, M. (1983). The Neutral Theory of Molecular Evolution. Cambridge University Press.Google ScholarCross Ref
- Knowles, J. D. and Watson, R. A. (2002). On the utility of redundant encodings in mutationbased evolutionary search. In Merelo, J. J., Adamidis, P., Beyer, H.-G., Fernandez- Villacanas, J.-L., and Schwefel, H.-P., editors, Parallel Problem Solving from Nature- PPSN VII, pages 88--98, Berlin. Springer. Google ScholarDigital Library
- Liepins, G. E. and Vose, M. D. (1990). Representational issues in genetic optimization. Journal of Experimental and Theoretical Artificial Intelligence, 2:101--115.Google ScholarCross Ref
- Moraglio, A. and Poli, R. (2004). Topological interpretation of crossover. In Deb, K., Poli, R., Banzhaf, W., Beyer, H.-G., Burke, E., Darwen, P., Dasgupta, D., Floreano, D., Foster, J., Harman, M., Holland, O., Lanzi, P. L., Spector, L., Tettamanzi, A., Thierens, D., and Tyrrell, A., editors, gecco2004, pages 1377--1388, Heidelberg. Springer.Google ScholarCross Ref
- Palmer, C. C. (1994). An approach to a problem in network design using genetic algorithms. PhD thesis, Polytechnic University, Brooklyn, NY. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- Raidl, G. R. (2000). An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem. In (Fonseca et al., 2000), pages 43--48.Google Scholar
- Reeves, C. R. (2000). Fitness landscapes: A guided tour. Joint tutorials of SAB 2000 and PPSN 2000, tutorial handbook.Google Scholar
- Ronald, S. (1997). Robust encodings in genetic algorithms: A survey of encoding issues. In (Bäck et al., 1997), pages 43--48.Google Scholar
- Ronald, S., Asenstorfer, J., and Vincent, M. (1995). Representational redundancy in evolutionary algorithms. In Fogel, D. B. and Attikiouzel, Y., editors, Proceedings of the 1995 IEEE International Conference on Evolutionary Computation, volume 2, pages 631--636, Piscataway. IEEE Service Center.Google ScholarCross Ref
- Rothlauf, F. (2002). Representations for Genetic and Evolutionary Algorithms. Number 104 in Studies on Fuzziness and Soft Computing. Springer, Heidelberg, 1st edition. Google ScholarDigital Library
- Rothlauf, F. and Goldberg, D. E. (2003). Redundant representations in evolutionary computation. Evolutionary Computation, 11(4):381--415. Google ScholarDigital Library
- Rowe, J. E., Vose, M. D., and Wright, A. H. (2010). Representation invariant genetic operators. Evolutionary Computation, 18(4):635--660. Google ScholarDigital Library
- Shackleton, M., Shipman, R., and Ebner, M. (2000). An investigation of redundant genotypephenotype mappings and their role in evolutionary search. In (Fonseca et al., 2000), pages 493--500.Google Scholar
- Shipman, R. (1999). Genetic redundancy: Desirable or problematic for evolutionary adaptation? In Dobnikar, A., Steele, N. C., Pearson, D. W., and Albrecht, R. F., editors, Proceedings of the 4th International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA), pages 1--11, Berlin. Springer.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Shipman, R., Shackleton, M., and Harvey, L. (2000b). The use of neutral genotype-phenotype mappings for improved evoutionary search. British Telecom Technology Journal, 18(4):103--111. Google ScholarDigital Library
- 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.Google Scholar
- Smith, T., Husbands, P., and O'Shea, M. (2001b). Neutral networks and evolvability with complex genotype-phenotype mapping. In Proceedings of the European Converence on Artificial Life: ECAL2001, volume LNAI 2159, pages 272--281, Berlin. Springer. Google ScholarDigital Library
- Smith, T., Husbands, P., and O'Shea, M. (2001c). Neutral networks in an evolutionary robotics search space. In (Kim et al., 2001), pages 136--145.Google Scholar
- Surry, P. D. and Radcliffe, N. (1996). Formal algorithms + formal representations = search strategies. In Voigt, H.-M., Ebeling, W., Rechenberg, I., and Schwefel, H.-P., editors, Parallel Problem Solving from Nature - PPSN IV, pages 366--375, Berlin. Springer. Google ScholarDigital Library
- Toussaint, M. and Igel, C. (2002). Neutrality: A necessity for self-adaptation. In Fogel, D. B., El-Sharkawi, M. A., Yao, X., Greenwood, G., Iba, H., Marrow, P., and Shackleton, M., editors, Proceedings of 2002 IEEE Congress on Evolutionary Computation, pages 1354--1359, Piscataway. IEEE Press. Google ScholarDigital Library
- Watson, R. A., Hornby, G. S., and Pollack, J. B. (1998). Modeling building-block interdependency. In Eiben, A. E., Bäck, T., Schoenauer, M., and Schwefel, H.-P., editors, Parallel Problem Solving from Nature - PPSN V, volume 1498 of LNCS, pages 97--106, Berlin. Springer. Google ScholarDigital Library
- Whitley, L. D. (2000). Walsh analysis, schemata, embedded landscapes and no free lunch. Joint Tutorials of SAB 2000 and PPSN 2000.Google Scholar
- Yu, T. and Miller, J. (2001). Neutrality and evolvability of Boolean function landscapes. In Miller, J., Tomassini, M., Lanzi, P. L., Ryan, C., Tetamanzi, A. G. B., and Langdon, W. B., editors, Proceedings of the Fourth European Conference on Genetic Programming (EuroGP-2001), volume 2038 of LNCS, pages 204--217, Berlin. Springer. Google ScholarDigital Library
- Yu, T. and Miller, J. (2002). Finding needles in haystacks is not hard with neutrality. In Foster, J. A., Lutton, E., Miller, J., Ryan, C., and Tettamanzi, A. G. B., editors, Proceedings of the Fifth European Conference on Genetic Programming (EuroGP- 2002), volume 2278 of LNCS, pages 13--25, Berlin. Springer. Google ScholarDigital Library
Index Terms
- Representations for Evolutionary Algorithms
Recommendations
Representations for evolutionary algorithms
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computationSuccessful 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 ...
Representations for evolutionary algorithms
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking PapersSuccessful 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 ...
Representations for evolutionary algorithms
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationSuccessful 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 ...
Comments