Single- and multi-objective genetic programming: New runtime results for sorting

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 optimisation process. Consequently, problems that are relatively easy to optimise can not be handled by variable-length evolutionary algorithms. In this article, we present several new bounds for different single- and multi-objective algorithms on the sorting problem, a problem that typically lacks independent and additive fitness structures.