|
The Rise of Evolutionary Multiobjective Optimizers
We must not ignore non-EC approaches, and cite here a selection of classical and recent works in which other optimization paradigms have addressed the needs of multiple objectives (Kung et al, 1975; Benson, 1978; Steuer, 1986; Dasgupta et al, 1999; Miettinen, 1999). See also Deb (2001) for significant space given to the treatment of the alternative methods in relation to evolutionary computation. In this article, however, we concentrate on EC approaches, (Deb, 2001; Coello et al, 2002), and remark that, as ever, EC-oriented methods certainly seem broadly the most effective overall, but that, in particular, the ideal approach to any given complex multiobjective problem will typically be some form of hybrid of an EC method and a classical method. It is worth noting here that the new conference series on Evolutionary Multicriterion Optimization (EMO) is making successful efforts at uniting the various optimization communities which specialize in multi-objective optimization; this is reflected in the first (of what we think will be many) EMO proceedings (Zitzler et al, 2001).
Moving on to discuss the rise of evolutionary multi-objective optimizers, we will first skate through an often-published history. This is to be found in some form in many of the recent theses which have introduced new evolutionary multi-objective algorithms and/or performed extensive case studies (Fonseca, 1995; Van Veldhuizen, 1999; Andersson, 2001; Zitzler, 2001; Knowles, 2002) – there are many more beyond this selection, and Carlos Coello is maintaining a good repository for such references as well as other multi-objective-related resources (software, test problems and so forth) at http://www.lania.mx/~ccoello/EMOO/. The tale goes as follows; after earlier work which seriously considered multi-objective problems but used penalty-function based approaches (Box, 1957; Fogel et al, 1966) serious effort to design specialist multi-objective optimization techniques in the evolutionary computation community seem to have started with Schaffer (1984). Schaffer’s idea, in the so-called VEGA method, involved considering each objective in turn in different cycles of the optimization. It was quite a while later (following a discussion in Goldberg (1989)) that researchers started to use the notion of dominance (see section 2) as a feature of their algorithms. That is, instead of the central scheme of selection (choosing something from the population which will then be subjected to mutation or crossover) being biased by a single-objective value, researchers began, after 1989, to use selection schemes which were based on dominance measures. I.e. the more a candidate solution in the population dominates others, the more likely it is to be selected to progress the optimization. It also seemed crucial to combine this with some form of ‘niching’ scheme, which ensured that selection was not unduly biased towards fit regions simply because lots of similar solutions were in that region. In such situations, near-copies of a very good individual tend to ‘steal’ the available chances for selection without themselves adding anything ‘new’ to the search. Such schemes were attracting much attention in single-objective evolutionary optimization at the time, and were carried over directly into the emerging Evolutionary multiobjective algorithms, where they seemed very helpful in leading to a well-distributed and extensive Pareto tradeoff surface. The early-90s crop of techniques which incorporated such notions (and later versions are still used), prominently included NSGA (Srinivas & Deb, 1994), NPGA (Horn et al, 1994), and MOGA (Fonseca & Fleming, 1993).
For a while after that, progress was not spectacular until it became generally noticed that elitism, while not a good thing in single objective optimization, tends to be very beneficial in multi-objective optimization. In the single-objective case, elitism – which essentially means mostly selecting the best so far, tends to quickly lead to premature convergence to suboptimal solutions. However, the corresponding concept in multi-objective optimization is to choose mainly from the current approximation to the Pareto front; i.e. the set of non-dominated solutions in the current population; since there is still a great deal of diversity present in such an ‘elite’ set (assuming the underlying optimizer is good), good progress towards even better solutions is not hampered, and is usually accelerated. So-called elitist evolutionary multiobjective optimization algorithms started coming to the fore with SPEA (Zitzler & Thiele, 1998; Zitzler et al, 2000), an application by Parks and Miller (Parks & Miller, 1998), ERMOCS (Neef et al, 1999), NSGA-II (Deb et al, 2000), PAES (Knowles & Corne, 2000), PESA (Corne et al, 2000), and many more. Finally, of rampant recent interest are hybrid approaches which combine evolutionary multi-objective optimization and local search in strategically suitable ways. To provide just a snippet of a growing thread, we cite Ishibuchi & Murata (1996) as a seminal example of such work with their MOGLS algorithm, which has been recently re-engineered by Jaszkiewicz (2002) with extremely competitive results.
This post-1995 explosion of interest in new techniques for evolutionary multiobjective optimization was fuelled by the following common experience: on real and complex problems, the new methods are able to evolve good Pareto fronts with no significant extra time cost above that of a single objective optimizer finding just one solution on the front. Hence, treating a multi-objective real world problem as it really should be treated – i.e. without simplifying and changing it to a single-objective pseudo-real problem – was clearly becoming a viable, fast and effective alternative. In recent years, the fruits of this are apparent in a multifarious collection of real-world applications. For example, the civil engineering enterprise of designing and controlling water networks is gaining much from the ascent of this field (Halhal et al, 1997; Chen & Chang, 1998; Reed et al, 2001). The rise of effective multiobjective optimization is also making great impact in engineering design and control (Chipperfield & Fleming, 1996; Dakev et al, 1997; Kim & Ghaboussi, 1999), in various design applications (Park & Grierson, 1999; Parmee et al, 2000; Balling, 2001), for optimization of networks of various kinds (Lo & Chang, 2000; Knowles et al, 2000; Ramírez-Rosado & Bernal-Agustín, 2001), and many other applications far too numerous to list in anything smaller than a large book. Again, the reader interested in getting a good feel for the breadth of work currently going on can refer to the books and the web location previously mentioned, as well as, of course, the standard WWW search engines.
|
