On the Utility of Redundant Encodings in Mutation-Based Evolutionary Search
- ️Tue Jan 01 2002
Abstract
A number of recent works in the evolutionary computation field have suggested that introducing large amounts of genetic redundancy may increase the evolvability of a population in an evolutionary algorithm. These works have variously claimed that the reliability of the search, the final fitness achieved, the ability to cope with changing environments, and the robustness to high mutation rates, may all be improved by employing this strategy. In this paper we dispute some of these claims, arguing that adding random redundancy cannot be generally useful for optimization purposes. By way of example we report on experiments where a proposed neutral encoding scheme (based on random Boolean networks) is compared to a direct encoding in two mutation-only EAs, at various mutation rates. Our findings show that with the appropriate choice of per-bit mutation rate, the evolvability of populations using the direct encoding is no less than with the redundant one.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Barnett. Netcrawling—optimal evolutionary search with neutral networks. In Proceedings of the 2001 Congress on Evolutionary Computation (CEC2001). IEEE Service Centre, Piscataway NJ, 2001.
S. Bornholdt and K. Sneppen. Robustness as an evolutionary principle. Proceedings of the Royal Society of London Series B-Biological Sciences, 267:2281–2286, 2000.
S. Bullock. Smooth operator? Understanding and visualising mutation bias. In J. Kelemen and P. Sosik, editors, Sixth European Conference on Artificial Life, pages 602–612, 2001.
M. Ebner, M. Shackleton, and R. Shipman. How neutral networks influence evolvability. Complexity, 2002. (In press).
I. Harvey and A. Thompson. Through the labyrinth evolution finds a way: A silicon ridge. In Proceedings of ICES96, pages 406–422. Springer-Verlag, 1996.
S. A. Kauffman. Adaptation on rugged fitness landscapes. In D. Stein, editor, Lectures in the Sciences of Complexity, pages 527–618. Redwood City: Addison-Wesley, 1989. SFI Studies in the Sciences of Complexity, Lecture Volume I.
M. Kimura. The Neutral Theory of Molecular Evolution. Cambridge University Press, 1983.
M. Motoki and R. Uehara. Unique solution instance generation for the 3-satisfiability (3-SAT) problem. Technical Report C-129, Dept. of Math and Comp. Sciences, Tokyo Institute of Technology, 1999.
M. A. Potter. An NK-landscape generator, 1997. Presented at the Workshop on Test Problem Generators for Evolutionary Algorithms, at the 7th ICGA.
C. M. Reidys and P. F. Stadler. Neutrality in fitness landscapes. Appl. Math. Comput., 117:321–350, 1998.
M. Shackleton, R. Shipman, and M. Ebner. An investigation of redundant genotype-phenotype mappings and their role in evolutionary search. In Proceedings of the 2000 Congress on Evolutionary Computation, pages 493–500, Piscataway, NJ, 2000. IEEE Service Center.
R. Shipman. Genetic redundancy: Desirable or problematic for evolutionary adaptation? In Proceedings of the 4th International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA). Springer-Verlag, 1999.
R. Shipman, M. Shackleton, M. Ebner, and R. Watson. Neutral search spaces for artificial evolution: a lesson from life. In Artificial Life VII: Proceedings of the Seventh International Conference. MIT Press, 2000.
E. van Nimwegen and J. P. Crutchfield. Metastable evolutionary dynamics: Crossing fitness barriers or escaping via neutral paths? Bulletin of Mathematical Biology,62(5):799–848, Sep 2000.
V. K. Vassilev and J. F. Miller. The advantages of landscape neutrality in digital circuit evolution. In ICES, pages 252–263, 2000.
R. A. Watson. Analysis of recombinative algorithms on a non-separable buildingblock problem. In Foundations of Genetic Algorithms VI, pages 69–89. Morgan Kaufmann, 2001.
R. A. Watson, G. S. Hornby, and J. B. Pollack. Modeling building-block interdependency. In Parallel Problem Solving from Nature— PPSN V, pages 97–106. Springer-Verlag, 1998.
T. Yu and J. Miller. Neutrality and the evolvability of Boolean function landscape. In Proceedings of the 4th European Conference on Genetic Programming (EuroGP), volume LNCS 2038, page 204 ff. Springer-Verlag, 2001.
Author information
Authors and Affiliations
IRIDIA— CP 194/6, Université Libre de Bruxelles, Ave. F. D. Roosevelt, 50, Brussels, 1050, Belgium
Joshua D. Knowles
DEMO, Volen Center for Complex Systems, Brandeis University, MS018, Waltham, MA, 02454, USA
Richard A. Watson
Authors
- Joshua D. Knowles
You can also search for this author in PubMed Google Scholar
- Richard A. Watson
You can also search for this author in PubMed Google Scholar
Editor information
Editors and Affiliations
Escuela Técnica Superior de Ingeniería Informática, 18071, Granada, Spain
Juan Julián Merelo Guervós
Department of Informatics, Technological Educational Institute of Thessaloniki, 54101, Thessaloniki, Greece
Panagiotis Adamidis
Department of Informatics XI, University of Dortmund, 44221, Dortmund, Germany
Hans-Georg Beyer & Hans-Paul Schwefel &
Department of Signal Theory and Communications, Universidad Carlos III, Madrid, Spain
José-Luis Fernández-Villacañas
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Knowles, J.D., Watson, R.A. (2002). On the Utility of Redundant Encodings in Mutation-Based Evolutionary Search. In: Guervós, J.J.M., Adamidis, P., Beyer, HG., Schwefel, HP., Fernández-Villacañas, JL. (eds) Parallel Problem Solving from Nature — PPSN VII. PPSN 2002. Lecture Notes in Computer Science, vol 2439. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45712-7_9
Download citation
DOI: https://doi.org/10.1007/3-540-45712-7_9
Published: 04 October 2002
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44139-7
Online ISBN: 978-3-540-45712-1
eBook Packages: Springer Book Archive