|
|
|
| A Multi-Objective Evolutionary Algorithm Based on Spatial Distance |
| LI Mi-Qing, ZHENG Jin-Hua, XIAO Gui-Xia, XIE Jiong-Liang |
| Institute of Information Engineering, Xiangtan University, Xiangtan 411105 |
|
|
|
|
Abstract To improve the convergence of multi-objective evolutionary algorithm, a measure based on distance is proposed. A density estimation metric-tree crowding distance is defined. The individual distance and the tree crowing distance are used as the selection criteria when the non-dominated front is considered. When the size of non-dominated solution set exceeds that of the population, a method based on neighboring distance is employed to truncate population. By examining of five performance metrics on six test problems, the proposed algorithm is demonstrated to be more competitive in uniformity and spread and performs better in converging to the pareto front, compared to NSGA-II and SPEA2.
|
|
Received: 11 April 2008
|
|
|
|
|
|
[1] Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. Chichester, UK: John Wiley & Sons, 2001
[2] Zheng Jinhua. Multi-Objective Evolutionary Algorithms and Applications. Beijing, China: Science Press, 2007 (in Chinese)
(郑金华.多目标进化算法及其应用.北京:科学出版社, 2007)
[3] Cui Xunxue. Multiobjective Evolutionary Algorithms and Their Applications. Beijing, China: National Defense Industry Press, 2006 (in Chinese)
(崔逊学.多目标进化算法及应用.北京:国防工业出版社, 2006)
[4] Schaffer J D. Some Experiments in Machine Learning Using Vector Evaluated Genetic Algorithms. Ph.D Dissertation. Nashville, USA: Vanderbilt University, 1984
[5] Knowles J D, Corne D W. Approximating the Nondominated Front Using the Pareto Archived Evolutionary Strategy. Evolutionary Computation, 2000, 8(2): 149-172
[6] Zitzler E, Thiele L. Multi-Objective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Trans on Evolutionary Computation, 1999, 3(4): 257-271
[7] Cui Xunxue, Li Miao, Fang Tingjian. A Multi-Objective Concordance Evolutionary Algorithm. Chinese Journal of Computers, 2001, 24(9): 979-984 (in Chinese)
(崔逊学,李 淼,方廷健.多目标协调进化算法研究.计算机学报, 2001, 24(9): 979-984)
[8] Li Miqing, Zheng Jinhua, Luo Biao. A Multi-Objective Evolutionary Algorithm Based on Minimum Spanning Tree. Journal of Computer Research and Development, 2009, 46(5): 803-813 (in Chinese)
(李密青,郑金华,罗 彪.一种基于最小生成树的多目标进化算法.计算机研究与发展, 2009, 46(5): 803-813)
[9] Deb K, Pratap A, Agrawal S, et al. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197
[10] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report, 103, Lausanne, Switzerland: Swiss Federal Institute of Technology. Computer Engineering and Networks Laboratory, 2001
[11] Knowles J, Corne D. Properties of an Adaptive Archiving Algorithm for Storing Nondominated Vectors. IEEE Trans on Evolutionary Computation, 2003, 7(2): 100-116
[12] Kukkonen S, Lampinen J. GDE3: The Third Evolution Step of Generalized Differential Evolution // Proc of the IEEE Congress on Evolutionary Computation. Edinburgh, Scotland, 2005: 443-450
[13] Zhang Qingfu, Zhou Aimin, Jin Yaochu. RM-MEDA: A Regularity Model-Based Multiobjective Estimation of Distribution Algorithm. IEEE Trans on Evolutionary Computation, 2008, 12(1): 41-63
[14] Deb K, Mohan M, Mishra S. Evaluating the Epsilon-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions. Evolutionary Computation, 2005, 13(4): 501-525
[15] Liu Liu, Li Minqiang, Lin Dan. The ε-Dominance Based Multi-Objective Evolutionary Algorithm and an Adaptive Epsilon Strategy. Chinese Journal of Computers, 2008, 31(7): 1063-1072 (in Chinese)
(刘 鎏,李敏强,林 丹.基于ε-支配的多目标进化算法及自适应调整策略.计算机学报, 2008, 31(7): 1063-1072)
[16] Zitzler E, Deb K, Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 2000, 8(2): 173-195
[17] Deb K, Thiele L, Laumanns M, et al. Scalable Test Problems for Evolutionary Multi-Objective Optimization // Jain L, Wu Xindong, Abraham A, et al, eds. Advanced Information and Knowledge Processing. Cambridge, USA: Springer, 2005: 105-145
[18] Li Miqing, Zheng Jinhua. Spread Assessment for Evolutionary Multi-Objective Optimization // Proc of the 5th International Conference on Evolutionary Multi-Criterion Optimization. Nantes, France, 2009: 216-230
[19] Knowles J, Thiele L, Zitzler E. A Tutorial on the Performance Assessment of Stochastic Multi-Objective Optimizers. Technical Report, 214, ETH Zurich, Switzerland: Swiss Federal Institute of Technology. Computer Engineering and Networks Laboratory, 2006
[20] van Veldhuizen D A, Lamont G B. Evolutionary Computation and Convergence to a Pareto Front // Late Breaking Papers at the Genetic Programming Conference. Stanford, USA: Stanford University Press, 1998: 221-228
[21] Schott J R. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master Dissertation. Cambridge, USA: Massachusetts Institute of Technology. Department of Aeronautics and Astronautics, 1995 |
|
|
|
2009, Vol. 22 
