.

Figure 1.17 Calculation of Pareto‐optimal front with ε‐constraint method.

      In more 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 P_s. The nondominated set E is then calculated as

Table 1.5 Pseudo‐Code for Kung’s Method

      (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 P^a: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, P_s = {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.