Читать книгу Power Magnetic Devices - Scott D. Sudhoff - Страница 37

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

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 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.

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 F₁. Now suppose we remove the members of F₁ 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 F₂ = {2, 3, 7}. Now let us once more consider the population P but now less the members in F₁ and F₂. Finding the nondominated set of the remaining population by again applying Kung’s algorithm yields the third front, F₃ = {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 be resolved using the concept of crowding distance. The crowding distance associated with a solution xⁱ is defined as

(1.8-2)

where F_n is the set of indices in front n, we assume i is in front F_n, o is an index of objective number, O is the number of objectives, N_L(o, i, F_n) returns the index of the individual with the next largest fitness (greater than individual i) in the oth objective in front F_n, and N_S(o, i, F_n) returns the index of the individual with the next smallest fitness (less than individual i) in the oth objective in front F_n. In the case where there is no next larger or smaller individual in some objective—that is, it is a maximum or minimum in some objective—the crowding distance is taken as a very large number (pseudo‐infinity).

Crowding tournament selection uses the concepts of front rank and crowding distance in order to decide which individuals to put into the mating pool. In this method, individuals x^c1 and x^c2 are randomly drawn from the current population. If one of these solutions has a better front rank than the other, it is copied into a mating pool. If the two individuals have the same front rank, then the one with the better (larger) crowding distance goes into the mating pool, as it has greater diversity in terms of objectives.