concrete terms, suppose we wished to minimize volume and loss for some electromagnetic device. If our first objective was volume and our second objective was loss, we would repeatedly minimize loss with different constraints on the volume. In this case, each ε value would correspond to a different volume. For each numerically different volume constraint, we would get the corresponding loss and thereby—one single‐objective optimization at a time—build up a Pareto‐optimal front between volume and loss.
As it turns out, GAs are well‐suited to compute Pareto‐optimal sets. This is because they operate on a population. In multi‐objective optimizations, the population of designs can be made to conform to the Pareto‐optimal set. This allows a GA to determine the Pareto‐optimal set and Pareto‐optimal front in a single analysis without requiring the solution of a separate optimization for every point on the front as is needed in the weighted sum method, ε‐constraint method, and weighted metric methods.
1.8 Multi‐Objective Optimization Using Genetic Algorithms
GAs are well‐suited for multi‐objective optimization, and there are a large number of approaches that can be taken. The goal in all of these methods is to evolve the population so that it becomes a Pareto‐optimal set.
Multi‐objective GAs fall into two classes, nonelitist and elitist. The elitist strategies are particularly effective because they explicitly identify and preserve, when possible, the nondominated individuals. Elitist strategies include the elitist nondominated sorting GA (NSGA‐II), distance‐based Pareto GA, and the strength Pareto GA [11]. In order to keep the present discussion limited that we might soon start discussing device design, we will somewhat arbitrarily focus our attention on the elitist NSGA‐II.
Before setting forth this algorithm, we will first consider the problem of finding the nondominated individuals in a population. Since finding the Pareto‐optimal front is the goal of any multi‐objective optimization, being able to identify those candidate solutions which are nondominated will be an important task. In a generic sense, the nondominated solutions will be given a favored status in many multi‐objective methods. To identify the nondominated solutions, we will consider Kung’s method. Consider a population P. We wish to find the nondominated subset of P, which we will denote E. The first step in Kung’s method is to sort the members of P from best to worst in terms of the first objective. In the event that two or more members have identical values of the first objective, this subset is ordered by the second objective (and by subsequent objectives if necessary). This sorted population will be denoted Ps. The nondominated set E is then calculated as
Table 1.5 Pseudo‐Code for Kung’s Method
function R=front(S) if ∣S∣=1 R=S else i=floor(∣S∣/2) T=front(S1:i) B=front(Si+1|S|) N=solutions of B not dominated by any solution of T R=T ∪ N end end
|
(1.8-1)
where front() is a recursively defined function. In order to describe this function, let ∣ · ∣ denote the number of elements in a set, and let Pa:b denote the ath to bth individuals in a population or set. With this notation, the pseudo‐code for Kung’s algorithm is listed in Table 1.5. Therein, S and R denote the input and output of the routine. The terms T, B, and N refer to intermediate variables that represent sets. The variable i is a scalar integer index.
In order to illustrate this algorithm, let us apply Kung’s algorithm to the set of designs illustrated in Figure 1.15. For this problem, P = {1, 2, 3, 4, 5, 6, 7, 8}. Considering cost to be our first objective, Ps = {1, 6, 2, 3, 8, 4, 7, 5}. Figure 1.18 illustrates the calls to the front routine. Therein, the order of the calls and the input and output arguments to each call are indicated. The basis of this method is that whenever the front is called, its return argument R will never have any dominated members. This is a result of the following: (a) The sorting of the first objective ensures that no member of a return argument T can be dominated by a member of B, (b) every member of B is checked against every member of T before returning to the next higher level, and (c) a set of one is inherently a nondominated set. As a result, T, B, and R are all nondominated sets.
In executing this example, calls 4, 5, 7, 8, 11, 12, 14, and 15 return nondominated sets because their input and output argument set size is 1. In calls 3, 6, 10, and 13, no member of an input set T can be dominated by the corresponding set B because of the ordering with respect to the first objective. The return arguments of calls 3, 6, 10, and 13 cannot have dominated members because the input sets to these calls (T and B) were nondominated, no member of T can be dominated by a member of B, and every member of B is checked against every member of T. Thus, proceeding from the bottom of Figure 1.18 to the top as subroutine calls are made, we see that the process involves a gradual combining and sifting of smaller nondominated sets to yield a larger nondominated set.
One question that arises in this example is why we need function calls beyond call 1 as it generates the nondominated set. It must be remembered that the calls are recursive in nature and so the algorithm of call 1 cannot be completed without calls 2–15. Another question that is often asked is if we really need to make calls to front when the number of elements in the input set is one. With some additional if‐then constructs, calls to front with an input set size of one could in fact be avoided.
Figure 1.18 Application of Kung’s method.
In addition to Kung’s method, two more processes will be needed in order to set forth the elitist NSGA‐II. The first of these is nondominated sorting (NDS). In order to understand NDS, let us consider again Figure 1.15 with population P = {1, 2, 3, 4, 5, 6, 7, 8}. As we have already discussed, the nondominated set is {1,6,8}, which was found using Kung’s algorithm. Let us consider this set front 1, denoted F1. Now suppose we remove the members of F1 from P, and find the nondominated set of the remaining population by again applying Kung’s algorithm. This will yield the second front, given by F2 = {2, 3, 7}. Now let us once more consider the population P but now less the members in F1 and F2. Finding the nondominated set of the remaining population by again applying Kung’s algorithm yields the third front, F3 = {4, 5}. In this way, it is possible to associate with every member of the population a rank with regard to which front they are associated. This ranking will be used to compare different members of the population in order to determine which members will become a part of the mating pool.
Although a population member on the first front can be said to be superior to a member on the second front, the question arises as to how to compare solutions on the same front. This issue will