An analysis of ϵ-lexicase selection for large-scale many-objective optimization
William La Cava, Jason H. Moore · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2018
In this paper we adapt ϵ-lexicase selection, a parent selection strategy designed for genetic programming, to solve many-objective optimization problems, ϵ-lexicase selection has been shown to perform well in regression due to its use of full program semantics for conducting selection. A recent theoretical analysis showed that this selection strategy preserves individuals located near the boundaries of the Pareto front in semantic space. We hypothesize that this strategy of biasing search to extreme positions in objective space may be beneficial for many-objective optimization as the number of objectives increases. Here, we replace program semantics with objective fitness to define ϵ-lexicase selection for many-objective optimization. We then compare this method to multi-objective optimization methods from literature on problems ranging from 3 to 100 objectives. We find that ϵ-lexicase selection outperforms state-of-the-art optimization algorithms in terms of convergence to the Pareto front, spread of solutions, and CPU time for problems with more than 3 objectives.