|
|
|
| A Delaunay Triangulation Based Diversity Metric for Solution Set of Multi-Objective Evolutionary Algorithms |
| ZHENG Jin-Hua, WANG Kang, LI Mi-Qing, XIE Zhun-Zhi |
| College of Information Engineering,Xiangtan University,Xiangtan 411105 |
|
|
|
|
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.
|
|
Received: 05 March 2012
|
|
|
|
|
|
[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 
