A fast and elitist multiobjective genetic algorithm: nsga-ii evolutionary Computation, ieee transactions on
tải về 0.7 Mb. Chế độ xem pdf
|
| A. Test Problems
We first describe the test problems used to compare different MOEAs. Test problems are chosen from a number of signifi- cant past studies in this area. Veldhuizen [22] cited a number of test problems that have been used in the past. Of them, we choose four problems: Schaffer’s study (SCH) [19], Fonseca and Fleming’s study (FON) [10], Poloni’s study (POL) [16], and Kursawe’s study (KUR) [15]. In 1999, the first author suggested a systematic way of developing test problems for multiobjec- tive optimization [3]. Zitzler et al. [25] followed those guide- lines and suggested six test problems. We choose five of those six problems here and call them ZDT1, ZDT2, ZDT3, ZDT4, and ZDT6. All problems have two objective functions. None of these problems have any constraint. We describe these prob- lems in Table I. The table also shows the number of variables, their bounds, the Pareto-optimal solutions, and the nature of the Pareto-optimal front for each problem. All approaches are run for a maximum of 25 000 function evaluations. We use the single-point crossover and bitwise mutation for binary-coded GAs and the simulated binary crossover (SBX) operator and polynomial mutation [6] for real-coded GAs. The crossover probability of and a mutation probability of or (where is the number of decision variables for real-coded GAs and is the string length for binary-coded GAs) are used. For real-coded NSGA-II, we use distribution indexes [6] for crossover and mutation operators as and , respectively. The population obtained at the end of 250 generations (the population after elite-preserving operator is applied) is used to calculate a couple of performance metrics, which we discuss in the next section. For PAES, we use a depth value equal to four and an archive size of 100. We use all population members of the archive obtained at the end of 25 000 iterations to calculate the performance metrics. For SPEA, we use a population of size 80 and an external population of size 20 (this 4 : 1 ratio is suggested by the developers of SPEA to maintain an adequate selection pressure for the elite solutions), so that overall population size becomes 100. SPEA is also run until 25 000 function evaluations are done. For SPEA, we use the 188 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002 Fig. 3. Distance metric 7. nondominated solutions of the combined GA and external populations at the final generation to calculate the performance metrics used in this study. For PAES, SPEA, and binary-coded NSGA-II, we have used 30 bits to code each decision variable. B. Performance Measures Unlike in single-objective optimization, there are two goals in a multiobjective optimization: 1) convergence to the Pareto-op- timal set and 2) maintenance of diversity in solutions of the Pareto-optimal set. These two tasks cannot be measured ade- quately with one performance metric. Many performance met- rics have been suggested [1], [8], [24]. Here, we define two per- formance metrics that are more direct in evaluating each of the above two goals in a solution set obtained by a multiobjective optimization algorithm. The first metric measures the extent of convergence to a known set of Pareto-optimal solutions. Since multiobjective al- gorithms would be tested on problems having a known set of Pareto-optimal solutions, the calculation of this metric is pos- sible. We realize, however, that such a metric cannot be used for any arbitrary problem. First, we find a set of uni- formly spaced solutions from the true Pareto-optimal front in the objective space. For each solution obtained with an algo- rithm, we compute the minimum Euclidean distance of it from chosen solutions on the Pareto-optimal front. The average of these distances is used as the first metric (the conver- gence metric). Fig. 3 shows the calculation procedure of this metric. The shaded region is the feasible search region and the solid curved lines specify the Pareto-optimal solutions. Solu- tions with open circles are chosen solutions on the Pareto-op- timal front for the calculation of the convergence metric and so- lutions marked with dark circles are solutions obtained by an algorithm. The smaller the value of this metric, the better the convergence toward the Pareto-optimal front. When all obtained solutions lie exactly on chosen solutions, this metric takes a value of zero. In all simulations performed here, we present the average and variance of this metric calculated for solution sets obtained in multiple runs. Even when all solutions converge to the Pareto-optimal front, the above convergence metric does not have a value of zero. The metric will yield zero only when each obtained solution lies ex- actly on each of the chosen solutions. Although this metric alone Fig. 4. Diversity metric 1. can provide some information about the spread in obtained so- lutions, we define an different metric to measure the spread in solutions obtained by an algorithm directly. The second metric measures the extent of spread achieved among the obtained solutions. Here, we are interested in getting a set of solutions that spans the entire Pareto-optimal region. We calculate the Euclidean distance between consecutive solutions in the ob- tained nondominated set of solutions. We calculate the average of these distances. Thereafter, from the obtained set of non- dominated solutions, we first calculate the extreme solutions (in the objective space) by fitting a curve parallel to that of the true Pareto-optimal front. Then, we use the following metric to cal- culate the nonuniformity in the distribution: (1) Here, the parameters and are the Euclidean distances be- tween the extreme solutions and the boundary solutions of the obtained nondominated set, as depicted in Fig. 4. The figure il- lustrates all distances mentioned in the above equation. The pa- rameter is the average of all distances , , assuming that there are solutions on the best nondomi- nated front. With solutions, there are consecutive distances. The denominator is the value of the numerator for the case when all solutions lie on one solution. It is interesting to note that this is not the worst case spread of solutions possible. We can have a scenario in which there is a large variance in . In such scenarios, the metric may be greater than one. Thus, the maximum value of the above metric can be greater than one. However, a good distribution would make all distances equal to and would make (with existence of extreme solutions in the nondominated set). Thus, for the most widely and uniformly spreadout set of nondominated solutions, the nu- merator of would be zero, making the metric to take a value zero. For any other distribution, the value of the metric would be greater than zero. For two distributions having identical values of and , the metric takes a higher value with worse distri- butions of solutions within the extreme solutions. Note that the above diversity metric can be used on any nondominated set of solutions, including one that is not the Pareto-optimal set. Using DEB et al.: A FAST AND ELITIST MULTIOBJECTIVE GA: NSGA-II 189 TABLE II M EAN (F IRST R OWS ) AND V ARIANCE (S ECOND R OWS ) OF THE C ONVERGENCE M ETRIC 7 TABLE III M EAN (F IRST R OWS ) AND V ARIANCE (S ECOND R OWS ) OF THE D IVERSITY M ETRIC 1 a triangularization technique or a Voronoi diagram approach [1] to calculate , the above procedure can be extended to estimate the spread of solutions in higher dimensions. tải về 0.7 Mb. Chia sẻ với bạn bè của bạn:
|