Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Redundant representations in evolutionary computation

Published: 01 December 2003 Publication History

Abstract

This paper discusses how the use of redundant representations influences the performance of genetic and evolutionary algorithms. Representations are redundant if the number of genotypes exceeds the number of phenotypes. A distinction is made between synonymously and non-synonymously redundant representations. Representations are synonymously redundant if the genotypes that represent the same phenotype are very similar to each other. Non-synonymously redundant representations do not allow genetic operators to work properly and result in a lower performance of evolutionary search. When using synonymously redundant representations, the performance of selectorecombinative genetic algorithms (GAs) depends on the modification of the initial supply. We have developed theoretical models for synonymously redundant representations that show the necessary population size to solve a problem and the number of generations goes with O(2kr/r), where kr is the order of redundancy and r is the number of genotypic building blocks (BB) that represent the optimal phenotypic BB. As a result, uniformly redundant representations do not change the behavior of GAs. Only by increasing r, which means overrepresenting the optimal solution, does GA performance increase. Therefore, non-uniformly redundant representations can only be used advantageously if a-priori information exists regarding the optimal solution. The validity of the proposed theoretical concepts is illustrated for the binary trivial voting mapping and the real-valued link-biased encoding. Our empirical investigations show that the developed population sizing and time to convergence models allow an accurate prediction of the empirical results.

References

[1]
Abramowitz, M., & Stegun, I. A. (1972). Handbook of mathematical functions. New York: Dover Publications.]]
[2]
Abuali, F. N., Wainwright, R. L., & Schoenefeld, D. A. (1995). Determinant factorization: A new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem. See Eschelman (1995), pp. 470-477.]]
[3]
Ackley, D. H. (1987). A connectionist machine for genetic hill climbing. Boston: Kluwer Academic.]]
[4]
Banzhaf, W. (1994). Genotype-phenotype-mapping and neutral variation - A case study in genetic programming. See Davidor, Schwefel, and Männer (1994), pp. 322-332.]]
[5]
Banzhaf, W., Daida, J., Eiben, A. E., Garzon, M. H., Honavar, V., Jakiela, M., & Smith, R. E. (Eds.) (1999). Proceedings of the Genetic and Evolutionary Computation Conference: Volume 1. San Francisco, CA: Morgan Kaufmann Publishers.]]
[6]
Barnett, L. (1997). Tangled webs: Evolutionary dynamics on fitness landscapes with neutrality . Master's thesis, School of Cognitive Sciences, University of East Sussex, Brighton.]]
[7]
Barnett, L. (1998, June 27-29). Ruggedness and neutrality: The NKp family of fitness landscapes. In Adami, C., Belew, R. K., Kitano, H., & Taylor, C. (Eds.), Proceedings of the 6th International Conference on Artificial Life (ALIFE-98) (pp. 18-27). Cambridge, MA, USA: MIT Press.]]
[8]
Barnett, L. (2001). Netcrawling - optimal evolutionary search with neutral networks. In Proceedings of the 2001 Congress on Evolutionary Computation CEC01 (pp. 30-37). Piscataway, NJ: IEEE Press.]]
[9]
Belew, R. K., & Booker, L. B. (Eds.) (1991). Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann.]]
[10]
Cohoon, J. P., Hegde, S. U., Martin, W. N., & Richards, D. (1988). Floorplan design using distributed genetic algorithms. In IEEE International Conference on Computer Aided-Design (pp. 452-455). IEEE.]]
[11]
Darwin, C. (1859). On the origin of species. London: John Murray.]]
[12]
Dasgupta, D. (1995). Incorporating redundancy and gene activation mechanisms in genetic search for adapting to non-stationary environments. In Chambers, L. (Ed.), Practical Handbook of Genetic Algorithms (Chapter 13, pp. 303-316). CRC Press.]]
[13]
Davidor, Y., Schwefel, H.-P., & Määnner, R. (Eds.) (1994). Parallel Problem Solving from Nature- PPSN III. Berlin: Springer-Verlag.]]
[14]
Davis, L. (1989). Adapting operator probabilities in genetic algorithms. In Schaffer, J. D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms (pp. 61-69). San Mateo, CA: Morgan Kaufmann.]]
[15]
Deb, K., Altenberg, L., Manderick, B., Bäck, T., Michalewicz, Z., Mitchell, M., & Forrest, S. (1997). Theoretical foundations and properties of evolutionary computations: fitness landscapes. In Bääck, T., Fogel, D. B., & Michalewicz, Z. (Eds.), Handbook of Evolutionary Computation (pp. B2.7:1-B2.7:25). Bristol and New York: Institute of Physics Publishing and Oxford University Press.]]
[16]
Deb, K., & Goldberg, D. E. (1993). Analyzing deception in trap functions. In Whitley, L. D. (Ed.), Foundations of Genetic Algorithms 2 (pp. 93-108). San Mateo, CA: Morgan Kaufmann.]]
[17]
Ebner, M., Langguth, P., Albert, J., Shackleton, M., & Shipman, R. (2001, 27-30 May). On neutral networks and evolvability. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001 (pp. 1-8). COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea: IEEE Press.]]
[18]
Eschelman, L. (Ed.) (1995). Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco, CA: Morgan Kaufmann.]]
[19]
Eshelman, L. J., & Schaffer, J. D. (1991). Preventing premature convergence in genetic algorithms by preventing incest. See Belew and Booker (1991), pp. 115-122.]]
[20]
Gaube, T., & Rothlauf, F. (2001). The link and node biased encoding revisited: Bias and adjustment of parameters. In Boers, E. J. W., Cagnoni, S., Gottlieb, J., Hart, E., Lanzi, P. L., Raidl, G. R., Smith, R. E., & Tijink, H. (Eds.), Applications of evolutionary Computing: Proc. EvoWorkshops 2001 (pp. 1-10). Berlin: Springer.]]
[21]
Gerrits, M., & Hogeweg, P. (1991). Redundant coding of an NP-complete problem allows effective Genetic Algorithm search. In Schwefel, H.-P., & Määnner, R. (Eds.), Parallel Problem Solving from Nature (pp. 70-74). Berlin: Springer-Verlag.]]
[22]
Goldberg, D. E., Deb, K., & Clark, J. H. (1992). Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6, 333-362.]]
[23]
Gottlieb, J., Julstrom, B. A., Raidl, G. R., & Rothlauf, F. (2001). Prüüfer numbers: A poor representation of spanning trees for evolutionary search. In Spector, L., E., G., Wu, A., B., L. W., Voigt, H.-M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M., & Burke, E. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference 2001 (pp. 343-350). San Francisco, CA: Morgan Kaufmann Publishers.]]
[24]
Hamming, R. (1980). Coding and information theory. Prentice-Hall.]]
[25]
Harik, G. R., Cantú-Paz, E., Goldberg, D. E., & Miller, B. L. (1997). The gambler's ruin problem, genetic algorithms, and the sizing of populations. In Bääck, T. (Ed.), Proceedings of the Forth International Conference on Evolutionary Computation (pp. 7-12). New York: IEEE Press.]]
[26]
Harvey, L., & Thompson, A. (1997). Through the labyrinth evolution finds a way: A silicon ride. Lecture Notes in Computer Science, 1259, 406-422.]]
[27]
Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press.]]
[28]
Horn, J. (1995). Genetic algorithms, problem difficulty, and the modality of fitness landscapes (IlliGAL Report No. 95004). Urbana, IL: University of Illinois at Urbana-Champaign.]]
[29]
Huynen, M. (1996). Exploring phenotype space through neutral evolution. J. Mol. Evol., 43, 165-169.]]
[30]
Huynen, M., Stadler, P., & Fontana, W. (1996). Smoothness within ruggedness: The role of neutrality in adaptation. In Proceedings of the National Academy of Sciences of the USA, 1993 (pp. 397-401). Washington, D.C.: National Academy of Sciences.]]
[31]
Jones, T., & Forrest, S. (1995). Fitness distance correlation as a measure of problem difficulty for genetic algorithms. See Eschelman (1995), pp. 184-192.]]
[32]
Julstrom, B. A. (1999). Redundant genetic encodings may not be harmful. See Banzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, and Smith (1999), pp. 791.]]
[33]
Kargupta, H. (2000). The genetic code-like transformations and their effect on learning functions. See Schoenauer, Deb, Rudolph, Yao, Lutton, Merelo, and Schwefel (2000), pp. 99-108.]]
[34]
Kargupta, H. (2001). A striking property of genetic code-like transformations. Complex Systems, 13(1), 1-32.]]
[35]
Kimura, M. (1983). The neutral theory of molecular evolution. Cambridge University Press.]]
[36]
Knowles, J. D., & Watson, R. A. (2002). On the utility of redundant encodings in mutation-based evolutionary search. In Merelo, J. J., Adamidis, P., Beyer, H.-G., Fernandez-Villacanas, J.-L., & Schwefel, H.-P. (Eds.), Parallel Problem Solving from Nature, PPSN VII (pp. 88-98). Berlin: Springer-Verlag.]]
[37]
Krishnamoorthy, M., & Ernst, A. T. (2001). Comparison of algorithms for the degree constrained minimum spanning tree. Journal of Heuristics, 7, 587-611.]]
[38]
Manderick, B., de Weger, M., & Spiessens, P. (1991). The genetic algorithm and the structure of the fitness landscape. See Belew and Booker (1991), pp. 143-150.]]
[39]
Mayr, E. (1991). One long argument: Charles Darwin and the genesis of modern evolutionary thought. Cambridge, Massachusetts: Harvard University Press.]]
[40]
Miller, B. L., & Goldberg, D. E. (1996a). Genetic algorithms, selection schemes, and the varying effects of noise. Evolutionary Computation, 4(2), 113-131.]]
[41]
Miller, B. L., & Goldberg, D. E. (1996b). Optimal sampling for genetic algorithms. In Dagli, C. H., Akay, M., Chen, C. L. P., Fernáández, B. R., & Ghosh, J. (Eds.), Proceedings of the Artificial Neural Networks in Engineering (ANNIE'96) conference, Volume 6 (pp. 291-297). New York: ASME Press.]]
[42]
Mühlenbein, H., & Schlierkamp-Voosen, D. (1993). Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization. Evolutionary Computation, 1 (1), 25-49.]]
[43]
O'Neill, M., & Ryan, C. (2001). Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4), 349-358.]]
[44]
Palmer, C. C. (1994). An approach to a problem in network design using genetic algorithms. unpublished PhD thesis, Polytechnic University, Troy, NY.]]
[45]
Palmer, C. C., & Kershenbaum, A. (1994a). Representing trees in genetic algorithms. In Proceedings of the First IEEE Conference on Evolutionary Computation, Volume 1 (pp. 379-384). Piscataway, NJ: IEEE Service Center.]]
[46]
Palmer, C. C., & Kershenbaum, A. (1994b). Two algorithms for finding optimal communication spanning trees. IBM research report RC-19394.]]
[47]
Prim, R. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36,1389-1401.]]
[48]
Prüfer, H. (1918). Neuer Beweis eines Satzes über Permutationen. Archiv für Mathematik und Physik, 27, 742-744.]]
[49]
Raidl, G. R., & Julstrom, B. A. (2000). A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem. In Carroll, J., Damiani, E., Haddad, H., & Oppenheim, D. (Eds.), Proceedings of the 2000 ACM Symposium on Applied Computing (pp. 440-445). ACM Press.]]
[50]
Rana, S. B., & Whitley, L. D. (1997). Bit representations with a twist. In Bääck, T. (Ed.), Proceedings of the Seventh International Conference on Genetic Algorithms (pp. 188-195). San Francisco: Morgan Kaufmann.]]
[51]
Reidys, C. M., & Stadler, P. F. (1998). Neutrality in fitness landscapes. Applied Mathematics and Computation, 117(2-3), 321-350.]]
[52]
Ronald, S., Asenstorfer, J., & Vincent, M. (1995). Representational redundancy in evolutionary algorithms. In 1995 IEEE International Conference on Evolutionary Computation, Volume 2 (pp. 631-636). Piscataway, NJ: IEEE Service Center.]]
[53]
Rothlauf, F. (2002). Representations for genetic and evolutionary algorithms. Number 104 in Studies on Fuzziness and Soft Computing. Berlin: Springer.]]
[54]
Rothlauf, F., & Goldberg, D. E. (2000). Prüüfernumbers and genetic algorithms: A lesson on how the low locality of an encoding can harm the performance of GAs. See Schoenauer, Deb, Rudolph, Yao, Lutton, Merelo, and Schwefel (2000), pp. 395-404.]]
[55]
Rothlauf, F., Goldberg, D. E., & Heinzl, A. (2002). Network random keys - A tree network representation scheme for genetic and evolutionary algorithms. Evolutionary Computation, 10(1), 75-97.]]
[56]
Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Merelo, J. J., & Schwefel, H.-P. (Eds.) (2000). Parallel Problem Solving from Nature, PPSN VI. Berlin: Springer-Verlag.]]
[57]
Schuster, P. (1997). Genotypes with phenotypes: Adventures in an RNA toy world. Biophys. Chem., 66, 75-110.]]
[58]
Shackleton, M., Shipman, R., & Ebner, M. (2000, 6-9 July). An investigation of redundant genotype-phenotype mappings and their role in evolutionary search. In Proceedings of the 2000 Congress on Evolutionary Computation CEC00 (pp. 493-500). La Jolla Marriott Hotel La Jolla, California, USA: IEEE Press.]]
[59]
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) (pp. 1-11). Springer Verlag.]]
[60]
Shipman, R., Shackleton, M., Ebner, M., & Watson, R. (2000). Neutral search spaces for artificial evolution: A lesson from life. In Bedau, M., McCaskill, J., Packard, N., & Rasmussen, S. (Eds.), Proceedings of Artificial Life VII (pp. section III (Evolutionary and Adaptive Dynamics )). MIT Press.]]
[61]
Shipman, R., Shackleton, M., & Harvey, L. (2000). The use of neutral genotype-phenotype mappings for improved evoutionary search. British Telecom Technology Journal, 18(4), 103-111.]]
[62]
Smith, T., Husbands, P., & O'Shea, M. (2001a). Evolvability, neutrality and search space (Technical Report 535). School of Cognitive and Computing Sciences, University of Sussex.]]
[63]
Smith, T., Husbands, P., & 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 (pp. 272-281). Berlin: Springer.]]
[64]
Smith, T., Husbands, P., & O'Shea, M. (2001). Neutral networks in an evolutionary robotics search space. In of Electrical, I., & Engineers, E. (Eds.), Proceedings of 2001 IEEE International Conference on Evolutionary Computation (pp. 136-145). Piscataway, NJ: IEEE Service Center.]]
[65]
Thierens, D. (1995). Analysis and design of genetic algorithms. Leuven, Belgium: Katholieke Universiteit Leuven.]]
[66]
Thierens, D., & Goldberg, D. E. (1994). Convergence models of genetic algorithm selection schemes. See Davidor, Schwefel, and Määnner (1994), pp. 119-129.]]
[67]
Toussaint, M., & 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., & Shackleton, M. (Eds.), Proceedings of the 2002 Congress on Evolutionary Computation CEC2002 (pp. 1354-1359). IEEE Press.]]
[68]
Weinberger, E. (1990). Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics, 63, 325-336.]]
[69]
Whitley, D. (1999). A free lunch proof for gray versus binary encodings. See Banzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, and Smith (1999), pp. 726-733.]]
[70]
Whitley, D. (2000). Functions as permutations: Implications for no free lunch, walsh analysis and statistics. See Schoenauer, Deb, Rudolph, Yao, Lutton, Merelo, and Schwefel (2000), pp. 169-178.]]
[71]
Whitley, D. (2002, September). Evaluating evolutionary algorithms. Tutorial Program at Parallel Problem Solving from Nature PPSN 2002.]]
[72]
Whitley, D., Rana, S., & Heckendorn, R. (1997). Representation issues in neighborhood search and evolutionary algorithms. In Genetic Algorithms and Evolution Strategy in Engineering and Computer Science (Chapter 3, pp. 39-58). West Sussex, England: John Wiley & Sons Ltd.]]
[73]
Yu, T., & Miller, J. (2001). Neutrality and evolvability of Boolean function landscapes. In Proceedings of the 4th European Conference on Genetic Programming (EuroGP), Volume LNCS 2038 (pp. 204-217). Springer.]]
[74]
Yu, T., & Miller, J. (2002). Finding needles in haystacks is not hard with neutrality. In Proceedings of the 5th European Conference on Genetic Programming (EuroGP), Volume LNCS (pp. 13-25). Springer.]]

Cited By

View all
  • (2024)Representations for Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648426(1017-1037)Online publication date: 14-Jul-2024
  • (2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
  • (2024)Grammar-Based Evolution of PolyominoesGenetic Programming10.1007/978-3-031-56957-9_4(56-72)Online publication date: 3-Apr-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation
Evolutionary Computation  Volume 11, Issue 4
Winter 2003
122 pages
ISSN:1063-6560
EISSN:1530-9304
Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 December 2003
Published in EVOL Volume 11, Issue 4

Author Tags

  1. link-and-node biased encoding
  2. neutral networks
  3. neutral theory
  4. non-synonymously redundant
  5. redundant representations
  6. synonymously redundant
  7. trivial voting mapping

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Representations for Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648426(1017-1037)Online publication date: 14-Jul-2024
  • (2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
  • (2024)Grammar-Based Evolution of PolyominoesGenetic Programming10.1007/978-3-031-56957-9_4(56-72)Online publication date: 3-Apr-2024
  • (2023)Representations for Evolutionary AlgorithmsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595034(1048-1068)Online publication date: 15-Jul-2023
  • (2023)The Influence of Probabilistic Grammars on EvolutionProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590706(611-614)Online publication date: 15-Jul-2023
  • (2022)Representations for evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533661(1046-1066)Online publication date: 9-Jul-2022
  • (2022)Co-evolutionary probabilistic structured grammatical evolutionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528833(991-999)Online publication date: 8-Jul-2022
  • (2022)Evolutionary Multiobjective Clustering Over Multiple Conflicting Data ViewsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322018727:4(817-831)Online publication date: 7-Nov-2022
  • (2022)Probabilistic Structured Grammatical Evolution2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870397(1-9)Online publication date: 18-Jul-2022
  • (2022)On the Schedule for Morphological Development of Evolved Modular Soft RobotsGenetic Programming10.1007/978-3-031-02056-8_10(146-161)Online publication date: 20-Apr-2022
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media