Using Unconstrained Elite Archives for Multi- Objective Optimisation
Fieldsend, Jonathan E.
Everson, Richard M.
IEEE Transactions on Evolutionary Computation
Institute of Electrical and Electronics Engineers (IEEE)
Multiobjective 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, nondominated solutions to improve the optimization 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 evolution-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 ε-dominance methods.
Copyright © 2003 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Notes: This paper demonstrates the benefits of having an unconstrained archive in multi-objective optimisation in order to maintain a ‘best’ estimate of the Pareto front solutions to a problem. It gave the first empirical demonstration of the problems arising from limited archive size, which had previously only been discussed theoretically, and, crucially, presents a novel data structure to mitigate the query time when using unconstrained archives.
Vol. 7 (3), pp. 305 - 323