A fast and elitist multiobjective genetic algorithm: nsga-ii evolutionary Computation, ieee transactions on
tải về 0.7 Mb. Chế độ xem pdf
|
| A. Proposed Constraint-Handling Approach (Constrained
NSGA-II) This constraint-handling method uses the binary tournament selection, where two solutions are picked from the population and the better solution is chosen. In the presence of constraints, each solution can be either feasible or infeasible. Thus, there may be at most three situations: 1) both solutions are feasible; 2) one is feasible and other is not; and 3) both are infeasible. For single objective optimization, we used a simple rule for each case. Case 1) Choose the solution with better objective function value. Case 2) Choose the feasible solution. Case 3) Choose the solution with smaller overall constraint violation. Since in no case constraints and objective function values are compared with each other, there is no need of having any penalty parameter, a matter that makes the proposed constraint-handling approach useful and attractive. In the context of multiobjective optimization, the latter two cases can be used as they are and the first case can be resolved by using the crowded-comparison operator as before. To maintain the modularity in the procedures of NSGA-II, we simply modify the definition of domination between two solutions and . Definition 1: A solution is said to constrained-dominate a solution , if any of the following conditions is true. 1) Solution is feasible and solution is not. 2) Solutions and are both infeasible, but solution has a smaller overall constraint violation. 3) Solutions and are feasible and solution dominates solution . The effect of using this constrained-domination principle is that any feasible solution has a better nondomination rank than any infeasible solution. All feasible solutions are ranked according to their nondomination level based on the objective function values. However, among two infeasible solutions, the solution with a smaller constraint violation has a better rank. Moreover, this modification in the nondomination principle does not change the computational complexity of NSGA-II. The rest of the NSGA-II procedure as described earlier can be used as usual. The above constrained-domination definition is similar to that suggested by Fonseca and Fleming [9]. The only difference is in the way domination is defined for the infeasible solutions. In the above definition, an infeasible solution having a larger overall constraint-violation are classified as members of a larger nondomination level. On the other hand, in [9], infeasible solu- tions violating different constraints are classified as members of the same nondominated front. Thus, one infeasible solution violating a constraint marginally will be placed in the same nondominated level with another solution violating a different constraint to a large extent. This may cause an algorithm to wander in the infeasible search region for more generations be- fore reaching the feasible region through constraint boundaries. Moreover, since Fonseca–Fleming’s approach requires domina- tion checks with the constraint-violation values, the proposed approach of this paper is computationally less expensive and is simpler. B. Ray–Tai–Seow’s Constraint-Handling Approach Ray et al. [17] suggested a more elaborate constraint-han- dling technique, where constraint violations of all constraints are not simply summed together. Instead, a nondomination check of constraint violations is also made. We give an outline of this procedure here. DEB et al.: A FAST AND ELITIST MULTIOBJECTIVE GA: NSGA-II 193 TABLE V C ONSTRAINED T EST P ROBLEMS U SED IN T HIS S TUDY All objective functions are to be minimized. Three different nondominated rankings of the population are first performed. The first ranking is performed using objec- tive function values and the resulting ranking is stored in a -di- mensional vector . The second ranking is performed using only the constraint violation values of all ( of them) con- straints and no objective function information is used. Thus, constraint violation of each constraint is used a criterion and a nondomination classification of the population is performed with the constraint violation values. Notice that for a feasible solution all constraint violations are zero. Thus, all feasible so- lutions have a rank 1 in . The third ranking is performed on a combination of objective functions and constraint-violation values [a total of values]. This produces the ranking . Although objective function values and constraint viola- tions are used together, one nice aspect of this algorithm is that there is no need for any penalty parameter. In the domination check, criteria are compared individually, thereby eliminating the need of any penalty parameter. Once these rankings are over, all feasible solutions having the best rank in are chosen for the new population. If more population slots are available, they are created from the remaining solutions systematically. By giving importance to the ranking in in the selection op- erator and by giving importance to the ranking in in the crossover operator, the investigators laid out a systematic multi- objective GA, which also includes a niche-preserving operator. For details, readers may refer to [17]. Although the investiga- tors did not compare their algorithm with any other method, they showed the working of this constraint-handling method on a number of engineering design problems. However, since nondominated sorting of three different sets of criteria are re- quired and the algorithm introduces many different operators, it remains to be investigated how it performs on more complex problems, particularly from the point of view of computational burden associated with the method. In the following section, we choose a set of four prob- lems and compare the simple constrained NSGA-II with the Ray–Tai–Seow’s method. tải về 0.7 Mb. Chia sẻ với bạn bè của bạn:
|