A fast and elitist multiobjective genetic algorithm: nsga-ii evolutionary Computation, ieee transactions on
tải về 0.7 Mb. Chế độ xem pdf
|
| 1) Density Estimation: To get an estimate of the density of
solutions surrounding a particular solution in the population, we calculate the average distance of two points on either side of this point along each of the objectives. This quantity serves as an estimate of the perimeter of the cuboid formed by using the nearest neighbors as the vertices (call this the crowding distance). In Fig. 1, the crowding distance of the th solution in its front (marked with solid circles) is the average side length of the cuboid (shown with a dashed box). The crowding-distance computation requires sorting the pop- ulation according to each objective function value in ascending order of magnitude. Thereafter, for each objective function, the boundary solutions (solutions with smallest and largest function values) are assigned an infinite distance value. All other inter- mediate solutions are assigned a distance value equal to the ab- solute normalized difference in the function values of two adja- cent solutions. This calculation is continued with other objective functions. The overall crowding-distance value is calculated as the sum of individual distance values corresponding to each ob- jective. Each objective function is normalized before calculating the crowding distance. The algorithm as shown at the bottom of the page outlines the crowding-distance computation procedure of all solutions in an nondominated set . Here, refers to the th objective function value of the th individual in the set and the parameters and are the maximum and minimum values of the th objective func- tion. The complexity of this procedure is governed by the sorting algorithm. Since independent sortings of at most solu- tions (when all population members are in one front ) are in- volved, the above algorithm has computational complexity. After all population members in the set are assigned a distance metric, we can compare two solutions for their extent of proximity with other solutions. A solution with a smaller value of this distance measure is, in some sense, more crowded by other solutions. This is exactly what we compare in the proposed crowded-comparison operator, described below. Although Fig. 1 illustrates the crowding-distance computation for two objectives, the procedure is applicable to more than two objectives as well. 2) Crowded-Comparison Operator: The crowded-compar- ison operator ( ) guides the selection process at the various stages of the algorithm toward a uniformly spread-out Pareto- optimal front. Assume that every individual in the population has two attributes: 1) nondomination rank ( ); 2) crowding distance ( ). We now define a partial order as if or and That is, between two solutions with differing nondomination ranks, we prefer the solution with the lower (better) rank. Other- wise, if both solutions belong to the same front, then we prefer the solution that is located in a lesser crowded region. With these three new innovations—a fast nondominated sorting procedure, a fast crowded distance estimation proce- dure, and a simple crowded comparison operator, we are now ready to describe the NSGA-II algorithm. C. Main Loop Initially, a random parent population is created. The pop- ulation is sorted based on the nondomination. Each solution is assigned a fitness (or rank) equal to its nondomination level (1 is the best level, 2 is the next-best level, and so on). Thus, mini- mization of fitness is assumed. At first, the usual binary tourna- ment selection, recombination, and mutation operators are used to create a offspring population of size . Since elitism - - 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 186 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002 is introduced by comparing current population with previously found best nondominated solutions, the procedure is different after the initial generation. We first describe the th generation of the proposed algorithm as shown at the bottom of the page. The step-by-step procedure shows that NSGA-II algorithm is simple and straightforward. First, a combined population is formed. The population is of size . Then, the population is sorted according to nondomination. Since all previous and current population members are included in , elitism is ensured. Now, solutions belonging to the best non- dominated set are of best solutions in the combined popu- lation and must be emphasized more than any other solution in the combined population. If the size of is smaller then , we definitely choose all members of the set for the new pop- ulation . The remaining members of the population are chosen from subsequent nondominated fronts in the order of their ranking. Thus, solutions from the set are chosen next, followed by solutions from the set , and so on. This procedure is continued until no more sets can be accommodated. Say that the set is the last nondominated set beyond which no other set can be accommodated. In general, the count of solutions in all sets from to would be larger than the population size. To choose exactly population members, we sort the solutions of the last front using the crowded-comparison operator in descending order and choose the best solutions needed to fill all population slots. The NSGA-II procedure is also shown in Fig. 2. The new population of size is now used for se- lection, 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 crowded-comparison operator . Since this operator requires both the rank and crowded distance of each solution in the pop- ulation, we calculate these quantities while forming the popula- tion , as shown in the above algorithm. Consider the complexity of one iteration of the entire algo- rithm. The basic operations and their worst-case complexities are as follows: 1) nondominated sorting is ; 2) crowding-distance assignment is ; 3) sorting on is . The overall complexity of the algorithm is , which is governed by the nondominated sorting part of the algorithm. If Fig. 2. NSGA-II procedure. performed carefully, the complete population of size need not be sorted according to nondomination. As soon as the sorting procedure has found enough number of fronts to have mem- bers in , there is no reason to continue with the sorting pro- cedure. The diversity among nondominated solutions is introduced by using the crowding comparison procedure, which is used in the tournament selection and during the population reduction phase. Since solutions compete with their crowding-distance (a measure of density of solutions in the neighborhood), no extra niching parameter (such as needed in the NSGA) is re- quired. Although the crowding distance is calculated in the ob- jective function space, it can also be implemented in the param- eter space, if so desired [3]. However, in all simulations per- formed in this study, we have used the objective-function space niching. IV. S IMULATION R ESULTS In this section, we first describe the test problems used to compare the performance of NSGA-II with PAES and SPEA. For PAES and SPEA, we have identical parameter settings as suggested in the original studies. For NSGA-II, we have chosen a reasonable set of values and have not made any effort in finding the best parameter setting. We leave this task for a future study. combine parent and offspring population - - - all nondominated fronts of and until until the parent population is filled - - calculate crowding-distance in include th nondominated front in the parent pop check the next front for inclusion Sort sort in descending order using choose the first elements of - - use selection, crossover and mutation to create a new population increment the generation counter DEB et al.: A FAST AND ELITIST MULTIOBJECTIVE GA: NSGA-II 187 TABLE I T EST P ROBLEMS U SED IN T HIS S TUDY All objective functions are to be minimized. tải về 0.7 Mb. Chia sẻ với bạn bè của bạn:
|