Abstract A Delaunay triangulation based metric (DTDM) is proposed for assessing the diversity metric in multi-objective evolutionary algorithms (MOEAs) by analyzing the characteristics and shortcomings of the current diversity metrics. The proposed metric is introduced by combining the neighborhood-based ideology and distance-based ideology. The metric independently searches the neighborhood by using the properties of the nearest and adjacent neighborhood of Delaunay triangulation net. The non-dominated relationship is eliminated according to a space mapping technique. The experimental results show that the proposed metric accurately evaluates the diversity of the solution set obtained by MOEAs.
ZHENG Jin-Hua,WANG Kang,LI Mi-Qing等. A Delaunay Triangulation Based Diversity Metric for Solution Set of Multi-Objective Evolutionary Algorithms[J]. , 2012, 25(6): 885-893.
[1] Deb K.Multi-Objective Optimization Using Evolutionary Algorithms.Chichester,UK: John Wiley Sons,2001 [2] Okabe T,Jin Yaochu,Sendhoff B.A Critical Survey of Performance Indices for Multi-Objective Optimization // Proc of the Congress on Evolutionary Computation.Offenbach,Germany,2003: 878-885 [3] Gong Maoguo,Jiao Licheng,Yang Dongdong,et al.Research on Evolutionary Multi-Objective Optimization Algorithms.Journal of Software,2009,20(2): 271-289 (in Chinese) (公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究.软件学报,2009,20(2): 271-289) [4] van Veldhuizen D A,Lamont G B.Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art.Evolutionary Computation,2000,8(2): 125-147 [5] Zheng Jinhua.Multi-Objective Evolutionary Algorithms and Applications.Beijing,China: Science Press,2007 (in Chinese) (郑金华.多目标进化算法及其应用.北京:科学出版社,2007) [6] Schott J R.Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization.Master Dissertation.Boston,USA: Massachusetts Institute of Technology,1995 [7] Coello C C A,Lamont G B,van Veldhuizen D A.Evolutionary Algorithms for Solving Multi-Objective Problems.2nd Edition.New York,USA: Springer,2007 [8] Zitzler E,Thiele L.Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach.IEEE Trans on Evolutionary Computation,1999,3(4): 257-271 [9] Zitzler E,Knowles J,Thiele L.Quality Assessment of Pareto Set Approximations // Branke J,Deb K,Miettinen K,et al,eds.Multiobjective Optimization: Interactive and Evolutionary Approaches.New York,USA: Springer,2008: 373-404 [10] Deb K,Pratap A,Agarwal S,et al.A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ.IEEE Trans on Evolutionary Computation,2002,6(8): 182-197 [11] Farhang-Mehr A,Azarm S.An Information-Theoretic Entropy Metric for Assessing Multi-Objective Optimization Solution Set Quality.Journal of Mechanical Design,2003,125(4): 655-663 [12] Li Kangshun,Li Yuanxiang,Kang Lishan,et al.A MOP Evolutionary Algorithm Based on Transportation Theory.Chinese Journal of Computers,2007,30(5): 796-805 (in Chinese) (李康顺,李元香,康立山,等.一种基于运输理论的多目标演化算法.计算机学报,2007,30(5): 796-805) [13] Deb K,Jain S.Running Performance Metrics for Evolutionary Multi-Objective Optimization // Proc of the 4th Asia-Pacific Conference on Simulated Evolution and Learning.Singapore,Singapore,2002: 13-20 [14] Zeng Sanyou,Cai Zhenhua,Zhang Qing,et al.A Novel Method for Assessing the Diversity of Approximation Pareto Fronts.Journal of Software,2008,19(6): 1301-1308 (in Chinese) (曾三友,蔡振华,张 青,等.一种评估近似Pareto前沿多样性的方法.软件学报,2008,19(6): 1301-1308) [15] Zitzler E,Thiele L,Laumanns M,et al.Performance Assessment of Multi-Objective Optimizers: An Analysis and Review.IEEE Trans on Evolutionary Computation,2003,7(2): 117-132 [16] Knowles J,Thiele L,Zitzler E.A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers.Technical Report,214.Zurich,Switzerland: Computer Engineering and Networks Laboratory (TIK),2006 [17] Li Miqing,Zheng Jinhua.An Indicator for Assessing the Spread of Solutions in Multi-Objective Evolutionary Algorithm.Chinese Journal of Computers,2011,34(4): 647-664 (in Chinese) (李密青,郑金华.一种多目标进化算法解集分布广度评价方法.计算机学报,2011,34(4): 647-664) [18] Wu J,Azarm S.Metrics for Quality Assessment of a Multiobjective Design Optimization Solution Set.Journal of Mechanical Design,2001,123(1): 18-25 [19] Lizárraga G,Hernández A,Botello S.G-Metric: An M-ary Quality Indicator for the Evaluation of Non-dominated Sets // Proc of the Genetic and Evolutionary Computation Conference.Georgia,USA,2008: 665-672 [20] Schuetze O,Equivel X,Lara A,et al.Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multi-Objective Optimization.IEEE Trans on Evolutionary Computation,2012,16 (4): 504-522 [21] Zitzler E,Laumanns M,Thiele L.SPEA2: Improving the Strength Pareto Evolutionary Algorithm.TIK-Report,103.Lausanne,Switzerland: Swiss Federal Institute of Technology,2001 [22] Kukkonen S,Lampinen J.The Third Evolution Step of Generalized Differential Evolution: GDE3 // Proc of the IEEE Congress on Evolutionary Computation.Edinburgh,UK,2005: 443-450 [23] Cignoni P,Montani C,Scopigno R.DeWall: A Fast Divide Conquer Delaunay Triangulation Algorithm in Ed.Computer-Aided Design,1998,30(5): 333-341
2012, Vol. 25 
