Self-adaptation via multi-objectivisation: an empirical study

Non-elitist evolutionary algorithms (EAs) can be beneficial in optimisation of noisy and or rugged fitness landscapes. However, this benefit can only be realised if the parameters of the non-elitist EAs are carefully adjusted in accordance with the fitness function. Self-adaptation is a promising parameter adaptation method that encodes and evolves parameters in the chromosome. Existing self-adaptive EAs often sort the population by first preferring higher fitness and then the mutation rate. A previous study (Case and Lehre, 2020) proved that self-adaptation can be effective in certain discrete problems with unknown structure. However, the population can be trapped on local optima, because individuals in “dense” fitness valleys which survive high mutation rates and individuals on “sparse” local optima which only survive with lower mutation rates cannot be simultaneously preserved.

Recently, the Multi-Objective Self-Adaptive EA (MOSA-EA) (Lehre and Qin, 2022) was proposed to optimise single-objective functions, treating parameter control via multi-objectivisation. The algorithm maximises the fitness and the mutation rates simultaneously, allowing individuals in “dense” fitness valleys and on “sparse” local optima to co-exist on a non-dominated Pareto front. The previous study proved its efficiency in escaping local optima with unknown sparsity, where some fixed mutation rate EAs become trapped. However, the performance is unknown in other settings.

This paper continues the study of MOSA-EA through an empirical study. We find that the MOSA-EA has a comparable performance on unimodal functions, and outperforms eleven randomised search heuristics considered on a bi-modal function with “sparse” local optima. For NP-hard problems, the MOSA-EA increasingly outperforms other algorithms for harder NK-LANDSCAPE and k-SAT instances. Notably, the MOSA-EA outperforms a problem-specific MAXSAT solver on several hard k-SAT instances. Finally, we show that the MOSA-EA self-adapts the mutation rate to the noise level in noisy optimisation. The results suggest that self-adaptation via multi-objectivisation can be adopted to control parameters in non-elitist EAs.