Parsimony pressure versus multi-objective optimization for variable length representations

Abstract

We contribute to the theoretical understanding of variable length evolutionary algorithms. Such algorithms are very flexible but can encounter the bloat problem which means solutions grow during the optimization run without providing additional benefit. We explore two common mechanisms for dealing with this problem from a theoretical point of view and point out the differences of a parsimony and a multi-objective approach in a rigorous way. As an example to point out the differences, we consider different measures of sortedness for the classical sorting problem which has already been studied in the computational complexity analysis of evolutionary algorithms with fixed length representations.