Abstract
There is increasing interest in evolutionary algorithms that have variable-length genomes and/or location independent genes. However, our understanding of such algorithms both theoretically and empirically is much less well developed than the more traditional fixed-length, fixed-location ones. Recent studies with VIV (Virtual Virus), a variable length, GA-based computational model of viral evolution, have revealed several emergent phenomena of both biological and computational interest. One interesting and somewhat surprising result is that the length of individuals in the population self-adapts in direct response to the mutation rate applied, so the GA adaptivelv strikes the balance it needs to successfully solve the problem. Over a broad range of mutation rates, genome length tends to increase dramatically in the early phases of evolution, and then decrease to a level based on the mutation rate. The plateau genome length (i.e., the average length of individuals in the final population) generally increases in response to an increase in the base mutation rate. Furthermore, the mutation operator rate and adapted length resulting in the best problem solving performance is about one mutation per individual. This is also the rate at which mutation generally occurs in biological systems, suggesting an optimal, or at least biologically plausible, balance of these operator rates. These results suggest that an important property of these algorithms is a considerable degree of self-adaptation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
T. Baeck. The interaction of mutation rate, selection, and self-adaptation within a genetic algorithm. In R. Maenner and B. Manderick, editors, Proc. Parallel Problem Solving from Nature 2, pages 85–94, 1992.
T. Baeck. Self-adaptation in genetic algorithms. In F.J. Varela and P. Bourgine, editors, Proc. First European Conf. Artificial Life, pages 203–271, 1992.
D. S. Burke, K. A. De Jong, J. J. Grefenstette, C. L. Ramsey, and A. S. Wu. Putting more genetics in genetic algorithms, 1998. To appear in Evolutionary Computation.
L. Davis. Adapting operator probabilities in genetic algorithms. In J. D. Schaffer, editor, Proc. 3rd Int. Conf. Genetic Algorithms, pages 61–69, 1989.
T. C. Fogarty. Varying the probability of mutation in the genetic algorithm. In J. D. Schaffer, editor, Proc. 3rd Int. Conf. Genetic Algorithms, pages 104–109, 1989.
S. Forrest and M. Mitchell. Relative building-block fitness and the building-block hypothesis. In Foundations of Genetic Algorithms 2, pages 109–126, 1992.
D. Goldberg, K. Deb, and B. Korb. Messy genetic algorithms: motivation, analysis, and first results. Complex Systems, 3:493–530, 1989.
J. J. Grefenstette, C. L. Ramsey, and A. C. Schultz. Learning sequential decision rules using simulation models and competition. Machine Learning, 5(4):355–381, 1990.
I. Harvey. The SAGA cross: the mechanics of crossover for variable-length genetic algorithms. In Parallel Problem Solving from Nature 2, pages 269–278, 1992.
I. Harvey. Species adaptation genetic algorithms: a basis for a continuing SAGA. In Proc. 1st European Conference on Artificial Life, 1992.
T. Haynes. Duplication of coding segments in genetic programming. In Proc. 13th National Conference on Artificial Intelligence, pages 344–349, 1996.
H. Iba, H. deGaris, and T. Sato. Genetic programming using a minimum description length principle. In Advances in Genetic Programming, pages 265–284, 1994.
J. R. Koza. Genetic programming. MIT Press, 1992.
W. B. Langdon and R. Poli. Fitness causes bloat. In 2nd On-line World Conference on Soft Computing in Engineering Design and Manufacturing, 1997.
J. R. Levenick. Inserting introns improves genetic algorithm success rate: taking a cue from biology. In Proc. 4th int'l Conf. Gen. Alg., pages 123–127, 1991.
K. E. Mathias and L. D. Whitley. Initial performance comparisons for the delta coding algorithm. In Proc. IEEE Conference on Evolutionary Computation, volume 1, pages 433–438, 1994.
H. A. Mayer. Genetic Algorithms Using Promoter/Terminater Sequences — Evolution of Number, Size, and Location of Parameters and Parts of the Representation. PhD thesis, University of Salzburg, 1997.
P. Nordin and W. Banzhaf. Complexity compression and evolution. In Proc. 6th International Conference on Genetic Algorithms, pages 310–317, 1995.
P. Nordin, F. Francone, and W. Banzhaf. Explicitly defined introns and destructive crossover in genetic programming. In Advances in Genetic Programming 2, pages 111–134, 1996.
S. F. Smith. Flexible lenrning of problem solving heuristics through adaptive search. In Proc. 8th International Joint Conference on Artificial Intelligence, pages 422–425 Morgan Kaufmann, 1983.
A. S. Wu and R. K. Lindsay. Empirical studies of the genetic algorithm with non-coding segments. Evolutionary Computation. 3(2):121–147, 1995.
A. S. Wu and R. K. Lindsay. A comparison of the fixed and floating building block representation in the genetic algorithm. Evolutionary Computation, 4(2):169–193, 1996.
B. T. Zhang and H. Muhlenbein. Balancing accuracy and parsimony in genetic programming. Evolutionary Compulation, 3(1), 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ramsey, C.L., De Jong, K.A., Grefenstettc, J.J., Wu, A.S., Burke, D.S. (1998). Genome length as an evolutionary self-adaptation. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, HP. (eds) Parallel Problem Solving from Nature — PPSN V. PPSN 1998. Lecture Notes in Computer Science, vol 1498. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0056877
Download citation
DOI: https://doi.org/10.1007/BFb0056877
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65078-2
Online ISBN: 978-3-540-49672-4
eBook Packages: Springer Book Archive