Using Unconstrained Elite Archives for Multi-Objective Optimisation

J.E. Fieldsend, R.M. Everson and S. Singh

Abstract

Multi-Objective Evolutionary Algorithms (MOEAs) have been the subject of numerous studies over the past 20 years. Recent work has highlighted the use of an active archive of elite, non-dominated solutions to improve the optimisation speed of these algorithms. However preserving all elite individuals is costly in time (due to the linear comparison with all archived solutions needed before a new solution can be inserted into the archive). Maintaining an elite population of a fixed maximum size (by clustering or other means) alleviates this problem, but can cause retreating (or oscillitory) and shrinking estimated Pareto fronts - which can affect the efficiency of the search process. New data structures are introduced to facilitate the use of an unconstrained elite archive, without the need for a linear comparison to the elite set for every new individual inserted. The general applicability of these data structures is shown by their use in an Evolutionary Strategy based MOEA and a Genetic Algorithm based MOEA. It is demonstrated that MOEAs using the new data structures run significantly faster than standard, unconstrained archive MOEAs, and result in estimated Pareto fronts significantly ahead of MOEAs using a constrained archive.
It is also shown that the use of an unconstrained elite archive permits robust criteria for algorithm termination to be used, and that the use of the data structure can also be used to increase the speed of algorithms using $\epsilon $-dominance methods.

Gzipped postscript  (5200 kb)     PDF  (801 kb)