A fast and elitist multiobjective genetic algorithm: nsga-ii evolutionary Computation, ieee transactions on
results of the constrained NSGA-II on a number of test problems
tải về 0.7 Mb. Chế độ xem pdf
|
- Điều hướng trang này:
- Constraint handling, elitism, genetic algorithms, multicriterion decision making, multiobjective optimization, Pareto-optimal solutions.
| results of the constrained NSGA-II on a number of test problems,
including a five-objective seven-constraint nonlinear problem, are compared with another constrained multiobjective optimizer and much better performance of NSGA-II is observed. Index Terms—Constraint handling, elitism, genetic algorithms, multicriterion decision making, multiobjective optimization, Pareto-optimal solutions. I. I NTRODUCTION T HE PRESENCE of multiple objectives in a problem, in principle, gives rise to a set of optimal solutions (largely known as Pareto-optimal solutions), instead of a single optimal solution. In the absence of any further information, one of these Pareto-optimal solutions cannot be said to be better than the other. This demands a user to find as many Pareto-optimal solu- tions as possible. Classical optimization methods (including the multicriterion decision-making methods) suggest converting the multiobjective optimization problem to a single-objective opti- mization problem by emphasizing one particular Pareto-optimal solution at a time. When such a method is to be used for finding multiple solutions, it has to be applied many times, hopefully finding a different solution at each simulation run. Over the past decade, a number of multiobjective evolu- tionary algorithms (MOEAs) have been suggested [1], [7], [13], Manuscript received August 18, 2000; revised February 5, 2001 and September 7, 2001. The work of K. Deb was supported by the Ministry of Human Resources and Development, India, under the Research and Development Scheme. The authors are with the Kanpur Genetic Algorithms Laboratory, Indian In- stitute of Technology, Kanpur PIN 208 016, India (e-mail: deb@iitk.ac.in). Publisher Item Identifier S 1089-778X(02)04101-2. [20], [26]. The primary reason for this is their ability to find multiple Pareto-optimal solutions in one single simulation run. Since evolutionary algorithms (EAs) work with a population of solutions, a simple EA can be extended to maintain a diverse set of solutions. With an emphasis for moving toward the true Pareto-optimal region, an EA can be used to find multiple Pareto-optimal solutions in one single simulation run. The nondominated sorting genetic algorithm (NSGA) pro- posed in [20] was one of the first such EAs. Over the years, the main criticisms of the NSGA approach have been as follows. 1) High computational complexity of nondominated sorting: The currently-used nondominated sorting algorithm has a computational complexity of (where is the number of objectives and is the population size). This makes NSGA computationally expensive for large popu- lation sizes. This large complexity arises because of the complexity involved in the nondominated sorting proce- dure in every generation. 2) Lack of elitism: Recent results [25], [18] show that elitism can speed up the performance of the GA significantly, which also can help preventing the loss of good solutions once they are found. 3) Need for specifying the sharing parameter : Tradi- tional mechanisms of ensuring diversity in a population so as to get a wide variety of equivalent solutions have relied mostly on the concept of sharing. The main problem with sharing is that it requires the specification of a sharing parameter ( ). Though there has been some work on dynamic sizing of the sharing parameter [10], a param- eter-less diversity-preservation mechanism is desirable. In this paper, we address all of these issues and propose an improved version of NSGA, which we call NSGA-II. From the simulation results on a number of difficult test problems, we find that NSGA-II outperforms two other contemporary MOEAs: Pareto-archived evolution strategy (PAES) [14] and strength- Pareto EA (SPEA) [24] in terms of finding a diverse set of so- lutions and in converging near the true Pareto-optimal set. Constrained multiobjective optimization is important from the point of view of practical problem solving, but not much attention has been paid so far in this respect among the EA researchers. In this paper, we suggest a simple constraint-handling strategy with NSGA-II that suits well for any EA. On four problems chosen from the literature, NSGA-II has been compared with another recently suggested constraint-handling strategy. These results encourage the application of NSGA-II to more complex and real-world multiobjective optimization problems. In the remainder of the paper, we briefly mention a number of existing elitist MOEAs in Section II. Thereafter, in Section III, 1089-778X/02$17.00 © 2002 IEEE DEB et al.: A FAST AND ELITIST MULTIOBJECTIVE GA: NSGA-II 183 we describe the proposed NSGA-II algorithm in details. Sec- tion IV presents simulation results of NSGA-II and compares them with two other elitist MOEAs (PAES and SPEA). In Sec- tion V, we highlight the issue of parameter interactions, a matter that is important in evolutionary computation research. The next section extends NSGA-II for handling constraints and compares the results with another recently proposed constraint-handling method. Finally, we outline the conclusions of this paper. II. E LITIST M ULTIOBJECTIVE E VOLUTIONARY A LGORITHMS During 1993–1995, a number of different EAs were sug- gested to solve multiobjective optimization problems. Of them, Fonseca and Fleming’s MOGA [7], Srinivas and Deb’s NSGA [20], and Horn et al.’s NPGA [13] enjoyed more attention. These algorithms demonstrated the necessary additional oper- ators for converting a simple EA to a MOEA. Two common features on all three operators were the following: i) assigning fitness to population members based on nondominated sorting and ii) preserving diversity among solutions of the same nondominated front. Although they have been shown to find multiple nondominated solutions on many test problems and a number of engineering design problems, researchers realized the need of introducing more useful operators (which have been found useful in single-objective EA’s) so as to solve multiobjective optimization problems better. Particularly, the interest has been to introduce elitism to enhance the convergence properties of a MOEA. Reference [25] showed that elitism helps in achieving better convergence in MOEAs. Among the existing elitist MOEAs, Zitzler and Thiele’s SPEA [26], Knowles and Corne’s Pareto-archived PAES [14], and Rudolph’s elitist GA [18] are well studied. We describe these approaches in brief. For details, readers are encouraged to refer to the original studies. Zitzler and Thiele [26] suggested an elitist multicriterion EA with the concept of nondomination in their SPEA. They sug- gested maintaining an external population at every generation storing all nondominated solutions discovered so far beginning from the initial population. This external population partici- pates in all genetic operations. At each generation, a combined population with the external and the current population is first constructed. All nondominated solutions in the combined pop- ulation 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 nondominated solution. This assignment of fitness makes sure that the search is directed toward the nondominated solutions. A deterministic clustering technique is used to ensure diversity among nondominated solutions. Although the implementation suggested in [26] is , with proper bookkeeping the complexity of SPEA can be reduced to . Knowles and Corne [14] suggested a simple MOEA using a single-parent single-offspring EA similar to (1 1)-evolution strategy. Instead of using real parameters, binary strings were used and bitwise mutations were employed to create offsprings. In their PAES, with one parent and one offspring, the offspring is compared with respect to the parent. If the offspring domi- nates the parent, the offspring is accepted as the next parent and the iteration continues. On the other hand, if the parent dom- inates the offspring, the offspring is discarded and a new mu- tated solution (a new offspring) is found. However, if the off- spring and the parent do not dominate each other, the choice be- tween the offspring and the parent is made by comparing them with an archive of best solutions found so far. The offspring is compared with the archive to check if it dominates any member of the archive. If it does, the offspring is accepted as the new parent and all the dominated solutions are eliminated from the archive. If the offspring does not dominate any member of the archive, both parent and offspring are checked for their near- ness with the solutions of the archive. If the offspring resides in a least crowded region in the objective space among the mem- bers of the archive, it is accepted as a parent and a copy of added to the archive. Crowding is maintained by dividing the entire search space deterministically in subspaces, where is the depth parameter and is the number of decision variables, and by updating the subspaces dynamically. Investigators have cal- culated the worst case complexity of PAES for evaluations as , where is the archive length. Since the archive size is usually chosen proportional to the population size , the overall complexity of the algorithm is . Rudolph [18] suggested, but did not simulate, a simple elitist MOEA based on a systematic comparison of individuals from parent and offspring populations. The nondominated solutions of the offspring population are compared with that of parent so- lutions to form an overall nondominated set of solutions, which becomes the parent population of the next iteration. If the size of this set is not greater than the desired population size, other individuals from the offspring population are included. With this strategy, he proved the convergence of this algorithm to the Pareto-optimal front. Although this is an important achievement in its own right, the algorithm lacks motivation for the second task of maintaining diversity of Pareto-optimal solutions. An ex- plicit diversity-preserving mechanism must be added to make it more practical. Since the determinism of the first nondominated front is , the overall complexity of Rudolph’s algo- rithm is also . In the following, we present the proposed nondominated sorting GA approach, which uses a fast nondominated sorting procedure, an elitist-preserving approach, and a parameterless niching operator. III. E LITIST N ONDOMINATED S ORTING G ENETIC A LGORITHM tải về 0.7 Mb. Chia sẻ với bạn bè của bạn:
|