Home > A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II

Page 1 |

Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T Meyarivan

Kanpur Genetic Algorithms Laboratory (KanGAL) Indian Institute of Technology Kanpur Kanpur, PIN 208 016, India

deb,samira,apratap,mary @iitk.ac.in http://www.iitk.ac.in/kangal

KanGAL Report No. 200001

Over the past decade, a number of multi-objective evolutionary algorithms (MOEAs) have been suggested [9,3,5,13]. The primary reason for this is their ability to find multiple Pareto-optimal solutions in one single run. Since the principal reason why a problem has a multi-objective formulation is because it is not possible to have a single solution which simultaneously optimizes all objectives, an algorithm that gives a large number of alternative solutions lying on or near the Pareto-optimal front is of great practical value. The Non-dominated Sorting Genetic Algorithm (NSGA) proposed in Srinivas and Deb [9] was one of the first such evolutionary algorithms. Over the years, the main criticism of the NSGA approach have been as follows:

Page 2 |

is very expensive, especially since the population needs to be sorted in every gen- eration.

In the study of Zitzler, Deb, and Theile [12], it was clearly shown that elitism helps in achieving better convergence in MOEAs. Among the existing elitist MOEAs, Zitzler and Thiele’s [13] strength Pareto EA (SPEA), Knowles and Corne’s Pareto-archived evolution strategy (PAES) [6], and Rudolph’s [8] elitist GA are well known. Zitzler and Thiele [13] suggested an elitist multi-criterion EA with the concept of non-domination in their strength Pareto EA (SPEA). They suggested maintaining an external population at every generation storing all non-dominated solutions discovered so far beginning from the initial population. This external population participates in genetic operations. At each generation, a combined population with the external and the current population is first constructed. All non-dominated solutions in the com- bined population are assigned a fitness based on the number of solutions they dominate and dominated solutions are assigned fitness worse than the worst fitness of any non- dominated solution. This assignment of fitness makes sure that the search is directed towards the non-dominated solutions. A deterministic clustering technique is used to ensure diversity among non-dominated solutions. Although the implementation sug- gested in [13] is ��´����¿µ, with proper book-keeping the complexity of SPEA can be reduced to ��´����¾µ. An important aspect of this study and subsequent studies [12, 11] is that they clearly show the importance of introducing elitism in evolutionary multi- criterion optimization. Knowles and Corne [6] suggested a simple MOEA using an evolution strategy (ES). In their Pareto-archived ES (PAES) with one parent and one child, the child is compared with respect to the parent. If the child dominates the parent, the child is accepted as the next parent and the iteration continues. On the other hand, if the parent dominates the child, the child is discarded and a new mutated solution (a new child) is found. However, if the child and the parent do not dominate each other, the choice between the child and

Page 3 |

the parent considers the second objective of keeping diversity among obtained solutions. To maintain diversity, an archive of non-dominated solutions is maintained. The child is compared with the archive to check if it dominates any member of the archive. If yes, the child is accepted as the new parent and the dominated solution is eliminated from the archive. If the child does not dominate any member of the archive, both parent and child are checked for their

µ,

the overall complexity of Rudolph’s algorithm is also ��´����¾µ.

The non-dominated sorting GA (NSGA) proposed by Srinivas and Deb in 1994 has been applied to various problems [10, 7]. However as mentioned earlier there have been a number of criticisms of the NSGA. In this section, we modify the NSGA approach in order to alleviate all the above difficulties. We begin by presenting a number of different modules that form part of NSGA-II.

Page 4 |

each front) complexity of this algorithm is ��´����¿µ. In the following we describe a fast non-dominated sorting approach which will require at most ��´����¾µ computations. First, for each solution we calculate two entities: (i) �� , the number of solutions which dominate the solution , and (ii) �� , a set of solutions which the solution domi- nates. The calculation of these two entities requires ��´����¾µ comparisons. We identify all those points which have ��

¼ and put them in a list ½. We call ½ the current

front. Now, for each solution in the current front we visit each member () in its set �� and reduce its �� count by one. In doing so, if for any member the count becomes zero, we put it in a separate list ��. When all members of the current front have been checked, we declare the members in the list ½ as members of the first front. We then continue this process using the newly identified front �� as our current front. Each such iteration requires ��´��µ computations. This process continues till all fronts are identified. Since at most there can be �� fronts, the worst case complexity of this loop is ��´��¾µ. The overall complexity of the algorithm now is ��´����¾µ ·��´��¾µ or ��´����¾µ. It is worth mentioning here that although the computational burden has reduced from ��´����¿µ to ��´����¾µ by performing systematic book-keeping, the storage has increased from ��´��µ to ��´��¾µ in the worst case. The fast non-dominated sorting procedure which when applied on a population �� returns a list of the non-dominated fronts .

fast-nondominated-sort(��)

for each �� ¾ �� for each �� ¾ �� if ´�� ��µ then if �� dominates �� then ���� ���� �� include �� in ���� else if ´�� ��µ then if �� is dominated by �� then ���� ���� · ½ increment ���� if ����

¼ then

if no solution dominates �� then

½ ½

�� �� is a member of the first front

½

while

��

for each �� ¾ for each member �� in for each �� ¾ ���� modify each member from the set ���� ���� ���� ½ decrement ���� by one if ����

¼ then �� �� ��

if ���� is zero, �� is a member of a list ��

· ½

��

current front is formed with all members of ��

���� �� serves as an estimate of the size of the

Page 5 |

largest cuboid enclosing the point without including any other point in the population (we call this the

Cuboid

f f

1 2

i i-1 i+1 0 l

distance of each point in the set �� :

crowding-distance-assignment(��)

��

��

number of solutions in �� for each , set �� ℄ ���� ��

¼

initialize distance for each objective ��

�� = sort(�� ��µ

sort using each objective value

�� Ѕ℄ ���� �� = �� ��℄ ���� �� = ½

so that boundary points are always selected for

¾ to ´�� Ѕµ

for all other points

�� ℄ ���� �� = �� ℄ ���� �� + ´�� · Ѕ℄ �� �� Ѕ℄ ��µ

Here �� ℄ �� refers to the ��-th objective function value of the -th individual in the set ��. The complexity of this procedure is governed by the sorting algorithm. In the worst case (when all solutions are in one front), the sorting requires ��´���� ���� ��µ computations.

��

if (�� ��

�� ��) or ((�� �� = �� ��) and ( ���� �� ���� �� ) )

Page 6 |

That is, between two solutions with differing non-domination ranks we prefer the point with the lower rank. Otherwise, if both the points belong to the same front then we prefer the point which is located in a region with lesser number of points (the size of the cuboid inclosing it is larger).

½ and for a particular generation is shown in the following:

���� ���� ���� combine parent and children population

fast-nondominated-sort(����)

´ ½

¾

µ, all non-dominated

fronts of ���� until ����·Ѕ �� till the parent population is filled

crowding-distance-assignment( ) calculate crowding distance in

����·Ѕ ����·Ѕ include -th non-dominated front in the parent pop Sort(����·Ѕ

��)

sort in descending order using �� ����·Ѕ ����·Ѕ ¼ ��℄ choose the first N elements of ����·Ѕ ����·Ѕ = make-new-pop(����·Ѕ) use selection,crossover and mutation to create �� �� · ½ a new population ����·Ѕ First, a combined population ���� ���� ���� is formed. The population ���� will be of size ¾��. Then, the population ���� is sorted according to non-domination. The new parent population ����·Ѕ is formed by adding solutions from the first front till the size exceeds ��. Thereafter, the solutions of the last accepted front are sorted according to

�� and the first �� points are picked. This is how we construct the population ����·Ѕ of

size ��. This population of size �� is now used for selection, crossover and mutation to create a new population ����·Ѕ of size ��. It is important to note that we use a binary tournament selection operator but the selection criterion is now based on the niched comparison operator ��. Let us now look at the complexity of one iteration of the entire algorithm. The basic operations being performed and the worst case complexities associated with are as follows: 1. Non-dominated sort is ��´����¾µ, 2. Crowding distance assignment is ��´���� ���� ��µ, and 3. Sort on �� is ��ґѕ�� ���� ґѕ��µµ. As can be seen, the overall complexity of the above algorithm is ��´����¾µ. The diversity among non-dominated solutions is introduced by using the crowding comparison procedure which is used in the tournament selection and during the popula- tion reduction phase. Since solutions compete with their crowding distance (a measure

Page 7 |

of density of solutions in the neighborhood), no extra niching parameter (such as × �� needed in the NSGA) is required here. Although the crowding distance is calculated in the objective function space, it can also be implemented in the parameter space, if so desired [1]. It is interesting to note here the connection of this algorithm with the algorithm proposed by Rudolph [8]. Since the non-dominated front finding algorithm used in Rudolph’s algorithm is ��´����¾µ for each front, Rudolph control’s the complexity of his algorithm by working with just the first few fronts in the parent and the child pop- ulations and treating the rest of the individuals in the child population at par. With the availability of a fast non-domination sorting algorithm we can now afford to combine the parent and child populations and do a complete sort to identify all the fronts and allocate fitness accordingly.

We compare NSGA-II with PAES on five test problems (minimization of both objec- tives): MOP2:

½ґ��µ ½ ���� ���� ½ �� ½���� ¾

��½ ��¾ ��¿

¾ґ��µ ½ ���� ���� ½ �� · ½���� ¾

(1) MOP3:

½ґ��µ

¢

Ѕ·ґ ½ ½µ

¾

· ´ ¾ ¾µ

¾£ ¾ґ��µ

¢

´�� · їµ¾ · ´�� · Ѕµ¾£

(2) where

½

¼ × �� ½ ¾ ���� ½ · × �� ¾ ½ ���� ¾

¾

½ × �� ½ ���� ½ · ¾ × �� ¾ ¼ ���� ¾

½

¼ × �� �� ¾ ������ · × �� �� ½ ������

¾

½ × �� �� ���� �� · ¾ × �� �� ¼ ������

MOP4:

´

½ґ��µ

���� ½

½

Ѕј ���� ¼ ¾ ��

��¾ · ��¾

·Ѕ

��½ ��¾ ��¿

¾ґ��µ

����

½

�� ¼ · × ��ґ�� µ¿¡ (3) EC4:

´

½ґ��µ ��½

¼

��½

½

¾ґ��µ

½

��

��Ѕ

��¾

��Ѕј (4) where

ґ��µ Ѕ·

Ѕј ¾

��¾ Ѕј ����ґ �� µ

¡

EC6:

½ґ��µ ½ ����ґ ��½µ × �� ´ ��½µ ¼

��

½ ½ Ѕј

¾ґ��µ

½ ´ ½ µ¾¡

(5) where

ґ��µ Ѕ·

Ѕј ¾

��

јѕ

Since the diversity among optimized solutions is an important matter in multi- objective optimization, we devise a measure based on the consecutive distances among

Page 8 |

the solutions of the best non-dominated front in the final population. The obtained set of the first non-dominated solutions are compared with a uniform distribution and the deviation is computed as follows: ¡

½ ½

½

(6) In order to ensure that this calculation takes into account the spread of solutions in the entire region of the true front, we include the boundary solutions in the non-dominated front ½. For discrete Pareto-optimal fronts, we calculate a weighted average of the above metric for each of the discrete regions. In the above equation, is the Euclidean distance between two consecutive solutions in the first non-dominated front of the final population in the objective function space. The parameter is the average of these distances. The deviation measure ¡ of these consecutive distances is then calculated for each run. An average of these deviations over 10 runs is calculated as the measure (¡) for comparing different algorithms. Thus, it is clear that an algorithm having a smaller ¡ is better, in terms of its ability to widely spread solutions in the obtained front. For all test problems and with NSGA-II, we use a population of size 100, a crossover probability of 0.8, a mutation probability of ½ �� (where �� is the number of variables). We run NSGA-II for 250 generations. The variables are treated as real numbers and the simulated binary crossover (SBX) [2] and the real-parameter mutation operator are used. For the (1+1)-PAES, we have used an archive size of 100 and depth of 4 [6]. A mutation probability of ¼ јЅ is used. In order to make the comparisons fair, we have used 25,000 iterations in PAES, so that total number of function evaluations in NSGA-II and in PAES are the same. Table 1 shows the deviation from an ideal (uniform) spread (¡) and its variance in 10 independent runs obtained using NSGA-II and PAES. We show two columns for each test problem. The first column presents the ¡ value of 10 runs and the second column shows its variance. It is clear from the table that in all five test problems NSGA- II has found much smaller ¡, meaning that NSGA-II is able to find a distribution of solutions closer to a uniform distribution along the non-dominated front. The variance columns suggest that the obtained ¡ values are consistent in all 10 runs.

In order to have a better understanding of how these algorithms are able to spread so- lutions over the non-dominated front, we present the entire non-dominated front found

Page 9 |

by NSGA-II and PAES in two of the above five test problems. Figures 2 and 3 show that NSGA-II is able to find a much better distribution than PAES on MOP4. In EC4, converging to the global Pareto-optimal front is a difficult task. As reported elsewhere [11], SPEA converged to a front with

¼ in at least one out of five

different runs. With NSGA-II, we find a front with

¿ in one out of five different

-12 -10 -8 -6 -4 -2 0 -20 -19 -18 -17 -16 -15 -14 f_2 f_1 NSGA-II

-12 -10 -8 -6 -4 -2 0 -20 -19 -18 -17 -16 -15 -14 f_2 f_1 PAES

runs. Figure 4 shows the non-dominated solutions obtained using NSGA-II and PAES for EC6. Once again, it is clear that the NSGA-II is able to better distribute its population along the obtained front than PAES. It is worth mentioning here that with similar num- ber of function evaluations, SPEA, as reported in [11], had found only five different solutions in the non-dominated front.

In this paper, we have proposed a computationally fast elitist multi-objective evolution- ary algorithm based on non-dominated sorting approach. On five difficult test problems borrowed from the literature, it has been found that the proposed NSGA-II outperforms PAES—another multi-objective EA with the explicit goal of preserving spread on the non-dominated front. With the properties of a fast non-dominated sorting procedure, an elitist strategy, and a parameterless approach, NSGA-II should find increasing attention and applications in the near future.

Authors acknowledge the support provided by All India Council for Technical Educa- tion, India during the course of this study.

Page 10 |

0 0.2 0.4 0.6 0.8 1 1.2 1.4 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 f_2 f_1 Pareto-Optimal Front NSGA-II PAES

1. Deb, K. (1999) Multi-objective genetic algorithms: Problem difficulties and construction of test Functions.

Page 11 |

- QUANTILE REGRESSION
- Topological Features in Locally Connected RBMs
- C. Steven Evans CV
- Toward a Theory of Social Support: Closing Conceptual Gaps
- Top 10 Issues for Banking M&A in 2014 Searching for growth and scale
- O o SPECIAL COURT FOR SIERRA LEONE JOMO KENYATTA ROAD • FREETOWN • SIERRA LEONE PHONE: +1 212 963 9915 Extension: 178 7000 or +39 0831 257000
- PHYLIP (Phylogeny Inference Package) Version 3.57c by Joseph Felsenstein July, 1995
- SCOTT ALLEN TAYLOR
- Astronomy 480 66 Linux Tutorial II

- Internet Companies
- Overseas Listing
- ProtocolControl Mode
- Information Disclosure
- anxiety
- human liberation
- driftand regression
- Reactive Compensation
- Reactive Power
- Controller
- Digital Signal Processor
- East Turkistan separatists Group
- Xinjiang problem
- China
- United States
- Countermeasure
- Osteostat
- NF κB
- signal transduction
- prokaryotic expression
- recombination protein

All Rights Reserved Powered by Free Document Search and Download

Copyright © 2011This site does not host pdf,doc,ppt,xls,rtf,txt files all document are the property of their respective owners. complaint#nuokui.com