Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control

Published in Journal Articles

  1. Leonardo Trujillo. Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control. Soft Comput. 15(8):1551-1567, 2011. BibTeX

    @article{DBLP:journals/soco/Trujillo11,
    	author = "Leonardo Trujillo",
    	title = "Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control",
    	journal = "Soft Comput.",
    	volume = 15,
    	number = 8,
    	year = 2011,
    	pages = "1551-1567",
    	ee = "http://dx.doi.org/10.1007/s00500-010-0687-7",
    	bibsource = "DBLP, http://dblp.uni-trier.de"
    }
    

Abstract

Genetic programming (GP) is one of the most widely used paradigms of evolutionary computation due to its ability to automatically synthesize computer programs and mathematical expressions. However, because GP uses a variable length representation, the individuals within the evolving population tend to grow rapidly without a corresponding return in fitness improvement, a phenomenon known as bloat. In this paper, we present a simple bloat control strategy for standard tree-based GP that achieves a one order of magnitude reduction in bloat when compared with standard GP on benchmark tests, and practically eliminates bloat on two real-world problems. Our proposal is to substitute standard subtree crossover with the one-point crossover (OPX) developed by Poli and Langdon (Second online world conference on soft computing in engineering design and manufacturing, Springer, Berlin (1997)), while maintaining all other GP aspects standard, particularly subtree mutation. OPX was proposed for theoretical purposes related to GP schema theorems, however since it curtails exploration during the search it has never achieved widespread use. In our results, on the other hand, we are able to show that OPX can indeed perform an effective search if it is coupled with subtree mutation, thus combining the bloat control capabilities of OPX with the exploration provided by standard mutation.

Published in
Soft Computing
Volume 15, Issue 8
Pages 1551-1567
http://link.springer.com/article/10.1007%2Fs00500-010-0687-7
Published
August 2011
Print ISSN
1432-7643
Online ISSN
1433-7479

 

Feedback