Two decades of evolutionary multi-criterion optimization: A glance back and a look ahead

Abstract

Summary form only given. The field of evolutionary multi-criterion optimization has undergone a tremendous growth since the first approaches have been proposed in the mid-1980's. Due to their population-based structure, evolutionary algorithms are inherently suited to optimization problems where the goal is to find a set of solutions. For this reason and with the advent of sufficient computing resources, they have become a valuable tool to approximate the set of Pareto-optimal solutions for highly complex applications in various domains. Several trends could be observed during the last two decades. Concerning the design of EMO algorithms, the early methods used component-wise selection mechanisms, while meanwhile dominance-based fitness assignment schemes combined with diversity preservation techniques and elitist environmental selection are most popular. A further paradigm shift has been initiated where the search is based on set quality measures. A second trend is related to the performance assessment of EMO methods. The first studies were proof-of-principle results and mainly using visual comparisons to evaluate simulation results. Later, quantitative measures were introduced and a variety of approaches for assessing the quality of sets have been proposed. The issue of statistical testing in the context of random sets has gained only little attention until 2000, but has become more and more standard meanwhile. Finally, a third trend addresses theoretical aspects of EMO. Within the last four years, several studies have been presented run-time analyses of simple model algorithms for various types of problems; these complement the many empirical studies published in the second decade of EMO history. Despite the many advances that have been achieved during the last 20 years, there are several challenges ahead. The integration of the search process into the decision making process has been discussed for many years, but so far only little research has been devoted to real interactive EMO methods. In the light of this question, especially problems with a large number of objectives are of particular interest. But many other topics can be mentioned in this context: uncertainty, robustness, and integration of exact optimization methods, to name only a few.