Chinese Journal of Computers   Full Text
Title	The ε-Dominance Based Multi-Objective Evolutionary Algorithm and an Adaptive ε Strategy
Authors	LIU Liu1) LI Min-Qiang1) LIN Dan2)
Address	1)(Institute of Systems Engineering, Tianjin University, Tianjin 300072) 2)(Department of Applied Mathematics, School of Science, Tianjin University, Tianjin 300072)
Year	2008
Issue	No.7(1063—1072)
Abstract &   Background	Abstract A novel multi-objective evolutionary algorithm, called ε-dominance multi-objective evolutionary algorithm(EDMOEA), is proposed in this paper. In the EDMOEA, pair-comparison selective and steady-state replacement are used to replace the conventional Pareto-ranking strategy, which could effectively improve the convergence rate of the algorithm and reduce the computation time. The main component of the new algorithm is the truncating method in archive population. Based on ε-dominance relationship, it maintains the diversity of the population and prevents the degradation of the Pareto front which often occurs in the conventional truncating strategies. Future more, a new adaptive ε setting method is incorporated into EDMOEA. Finally, five binary-objective functions are used to test the performance of the EDMOEA, the Adaptive-EDMOEA(AEDMOEA), and conventional algorithms such as NSGAII, SPEA2, and ε-MOEA. Experimental results demonstrate that the AEDMOEA and EDMOEA outperform other algorithms on these test functions. Keywords multi-objective optimization; ε-dominance; evolutionary algorithm; ε-adaptive; elitism strategy; steady-state strategy Background The research of this paper is supported by the National Science Foundation of China under grant Nos.70171002, 70571057 and the Program for New Century Excellent Talents in University of China under grant No.NCET-05-0253. The project No.70171002 made a detailed investigation on the theory of evolutionary computation; and the project No.70571057 and the NCET-05-0253 focus on co-evolution computation and the applications in handling multi-objective optimization problems. The evolutionary algorithms have been recognized as an efficient approach to solve the MOPs since 1985. The existing evolutionary algorithms for the MOPs employed mainly the Pareto domination relation to determine the fitness function so that the selection pressure was achieved to drive the population towards the true Pareto front. However, it is not easy to manipulate and computationally expensive. Recently, the steady-state evolutionary algorithms that make use of the pair-wise comparison instead of the fitness functions to bias the selection of parents are proposed. Further more, a relaxed form of the Pareto dominance, denoted as the ε-dominance, is becoming the popular mechanism to regulate convergence of multi-objective evolutionary algorithms. This paper adopts a simple truncating method based on the ε-dominance relationship in archive population, and presents the ε-dominance multi-objective evolutionary algorithm(EDMOEA)and adaptive EDMOEA(AEDMOEA). Both EDMOEA and AEDMOEA could guarantee the convergence of the population to the subset of the true Pareto optima and the preservation of boundary solutions.