Genetic programming: parametric analysis of structure altering mutation techniques
Pages 220 - 227
Abstract
We hypothesize that the relationship between parameter settings, specifically parameters controlling mutation, and performance is non-linear in genetic programs. Genetic programming environments have few means for a priori determination of appropriate parameters values. The hypothesized nonlinear behavior of genetic programming creates difficulty in selecting parameter values for many problems. In this paper we study three structure altering mutation techniques using parametric analysis on a problem with scalable complexity. We find through parameter analysis that two of the three mutation types tested exhibit nonlinear behavior. Higher mutation rates cause a larger degree of nonlinear behavior as measured by fitness and computational effort. Characterization of the mutation techniques using parametric analysis confirms the nonlinear behavior. In addition, we propose an extension to the existing parameter setting taxonomy to include commonly used structure altering mutation attributes. Finally we show that the proportion of mutations applied to internal nodes, instead of leaf nodes, has a significant effect on performance.
References
[1]
E. K. Burke, S. Gustafson, and K. Kendall. Diversity in genetic programming: An analysis of measures and correlation with fitness. IEEE Transactions on Evolutionary Computation, 8(1):47--62, 2004.
[2]
B. P. Douglas Zongker. lil-gp 1.0 user's manual. Technical report, Michigan State University, 1995.
[3]
A. E. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in evolutionary algorithms. IEEE Transations on Evolutionary Computation, 3(2):124--141, 1999.
[4]
R. Feldt and P. Nordin. Using factorial experiments to evaluate the effect of genetic programming parameters. In R. Poli, W. Banzhaf, W. B. Langdon, J. F. Miller, P. Nordin, and T. C. Fogarty, editors, Genetic Programming, Proceedings of EuroGP'2000, volume 1802 of LNCS, pages 271--282, Edinburgh, 15--16 Apr. 2000. Springer-Verlag.
[5]
C. Gathercole and P. Ross. An adverse interaction between crossover and restricted tree depth in genetic programming. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 291--296, Stanford University, CA, USA, July 1996. MIT Press.
[6]
J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection, pages 106--107. MIT Press, Cambridge, MA, USA, 1992.
[7]
J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.
[8]
J. R. Koza, F. H. Bennett III, D. Andre, and M. A. Keane. Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann Press, May 1999.
[9]
J. R. Koza, M. A. Keane, M. J. Streeter, W. Mydlowec, J. Yu, and G. Lanza. Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic Publishers, July 2003.
[10]
W. B. Langdon and R. Poli. An analysis of the MAX problem in genetic programming. In J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo, editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 222--230, Stanford University, CA, USA, 13--16 July 1997. Morgan Kaufmann.
[11]
S. Luke. Modification point depth and genome growth in genetic programming. Evolutionary Computation, 11(1):67--106, 2003.
[12]
S. Luke and L. Spector. A comparison of crossover and mutation in genetic programming. In J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo, editors, Genetic Programming 1997: Proc. of the Second Annual Conf., pages 240--248, San Francisco, CA, 1997. Morgan Kaufmann.
[13]
B. J. Ross. Searching for search algorithms: Experiments in meta-search. Technical report, Brock University, December 2002. Technical Report CS-02-23.
Index Terms
- Genetic programming: parametric analysis of structure altering mutation techniques
Recommendations
A comparison of selection, recombination, and mutation parameter importance over a set of fifteen optimization tasks
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking PapersHow does one choose an initial set of parameters for an evolutionary computing algorithm? Clearly some choices are dictated by the problem itself, such as the encoding of a problem solution, or how much time is available for running the evolution. ...
A survey of mutation techniques in genetic programming
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computationThe importance of mutation varies across evolutionary computation domains including: genetic programming, evolution strategies, and genetic algorithms. In the genetic programming community, researchers' view of mutation's effectiveness spans the range ...
A parameter-less genetic algorithm with customized crossover and mutation operators
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationGenetic algorithm is one of the well-known population based meta-heuristics. The reasonable performance of the algorithm on a wide variety of problems as well as its simplicity made this algorithm a first choice in lots of cases. However, the algorithm ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2005 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 June 2005
Check for updates
Author Tags
Qualifiers
- Article
Conference
GECCO05
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 217Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in