CMA-PAES: Pareto archived evolution strategy using covariance matrix adaptation for Multi-Objective Optimisation

The quality of Evolutionary Multi-Objective Optimisation (EMO) approximation sets can be measured by their proximity, diversity and pertinence. In this paper we introduce a modular and extensible Multi-Objective Evolutionary Algorithm (MOEA) capable of converging to the Pareto-optimal front in a minimal number of function evaluations and producing a diverse approximation set. This algorithm, called the Covariance Matrix Adaptation Pareto Archived Evolution Strategy (CMA-PAES), is a form of (μ + λ) Evolution Strategy which uses an online archive of previously found Pareto-optimal solutions (maintained by a bounded Pareto-archiving scheme) as well as a population of solutions which are subjected to variation using Covariance Matrix Adaptation. The performance of CMA-PAES is compared to NSGA-II (currently considered the benchmark MOEA in the literature) on the ZDT test suite of bi-objective optimisation problems and the significance of the results are analysed using randomisation testing.

I. Introduction

The quality of Evolutionary Multi-Objective Optimisation (EMO) candidate solution sets can be measured by their proximity, diversity and pertinence. Proximity is a measure of the distance between the approximation set and the true Paretooptimal front¹

This notion of “Pareto” optimality was originally proposed by Francis Edgeworth in 1881 [1] and was later developed by the Italian economist Vilfredo Pareto in 1896 who used the concept in his studies of economic efficiency and income distribution [2].

whilst diversity is a measure of the distribution of solutions along that front in multi-objective space. An ideal multi-objective optimiser converges to solutions that are uniformly spread along the true Pareto-optimal front [3]. In real-world optimisation problems this approximation set must also be pertinent [4] (that is relevant to the preferences expressed by the Decision Maker (DM)). A good Multi-Objective Evolutionary Algorithm (MOEA) satisfies these goals adequately, presenting the DM with an approximation set of diverse trade-off solutions within the search space of their specified Region Of Interest (ROI). These measures of performance have been illustrated in figure 1. Figure 1. Proximity, diversity, and pertinence characteristics in an approximation set for a bi-objective problem.