On the Performance of Different Genetic Programming Approaches for the SORTING Problem

In genetic programming, the size of a solution is typically not specified in advance, and solutions of larger size may have a larger benefit. The flexibility often comes at the cost of the so-called bloat problem: individuals grow without providing additional benefit to the quality of solutions, and...

Full description

Saved in:
Bibliographic Details
Published in:Evolutionary computation 2015-12, Vol.23 (4), p.583-609
Main Authors: Wagner, Markus, Neumann, Frank, Urli, Tommaso
Format: Article
Language:English
Subjects:
Algorithms
Biological Evolution
Blocking
Complement
Computational Biology
Computational complexity
Computer Simulation
Evolutionary algorithms
Flexibility
Genetic algorithms
genetic programming
Humans
Mathematical models
Models, Genetic
Models, Theoretical
multiobjective optimization
Mutation
Optimization
single-objective optimization
sortedness
Sorting
variable-length representation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In genetic programming, the size of a solution is typically not specified in advance, and solutions of larger size may have a larger benefit. The flexibility often comes at the cost of the so-called bloat problem: individuals grow without providing additional benefit to the quality of solutions, and the additional elements can block the optimization process. Consequently, problems that are relatively easy to optimize cannot be handled by variable-length evolutionary algorithms. In this article, we analyze different single- and multiobjective algorithms on the sorting problem, a problem that typically lacks independent and additive fitness structures. We complement the theoretical results with comprehensive experiments to indicate the tightness of existing bounds, and to indicate bounds where theoretical results are missing.
ISSN:1063-6560
1530-9304
DOI:10.1162/EVCO_a_00149