Variable Influence Space Based Uniformity Metric Method for Solution Sets of Multi-objective Evolutionary Algorithms
ZHENG Jin-Hua, HUANG Duan, WANG Kang, ZHANG Zuo-Feng
1.College of Information Engineering, Xiangtan University, Xiangtan 411105 2.Key Laboratory of Intelligent Computing and Information Processing, Ministry of Education, Xiangtan University, Xiangtan 411105
Abstract：Uniformity Evaluation of solutions is one of the most important issues of performance assessment. The views of facing individuals and facing space are combined to construct a variable influence space of solutions. A variable influence space based uniformity metric method for solution sets of multi-objective evolutionary algorithms is proposed in this paper. The metric can be used to compare the performance of different multi-objective optimization techniques by evaluating the relative degree of uniformity of a solution set in the influence space. Experimental results show the feasibility and effectiveness of the proposed metric.
[1] Deb K. Multi-objective Optimization Using Evolutionary Algorithms. New York, USA: John Wiley & Sons, 2001 [2] Gong M G, Jiao L C, Yang D D, et al. Research on Evolutionary Multi-objective Optimization Algorithms. Journal of Software, 2009, 20(2): 271-289 (in Chinese) (公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究.软件学报, 2009, 20(2): 271-289) [3] Li M Q, Yang S X, Zheng J H, et al. ETEA:A Euclidean Minimum Spanning Tree-Based Evolutionary Algorithm for Multi-objective Optimization. Evolutionary Computation, 2014, 22(2): 189-230 [4] Yang S X, Li M Q, Liu X H, et al. A Grid-Based Evolutionary Algorithm for Many-Objective Optimization. IEEE Trans on Evolutionary Computation, 2013, 17(5): 721-736 [5] Coello Coello C A. Evolutionary Multi-objective Optimization: A Historical View of the Field. IEEE Computational Intelligence Ma- gazine, 2006, 1(1): 28-36 [6] Zheng J H. Multi-objective Evolutionary Algorithms and Applications. Beijing, China: Science Press, 2007 (in Chinese) (郑金华.多目标进化算法及其应用.北京:科学出版社, 2007) [7] Van Veldhuizen D A, Lamont G B. Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art. Evolutionary Computation, 2000, 8(2): 125-147 [8] Schott J R. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master Dissertation. Cambridge, USA: Massachusetts Institute of Technology, 1995: 199-200 [9] Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197 [10] Farhang-Mehr A, Azarm S. An Information-Theoretic Entropy Me- tric for Assessing Multi-objective Optimization Solution Set Quality. Journal of Mechanical Design, 2004, 125(4): 655-663 [11] Bosman P A N, Thierens D. The Balance between Proximity and Diversity in Multiobjective Evolutionary Algorithms. IEEE Trans on Evolutionary Computation, 2003, 7(2): 174-188 [12] 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 [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 S Y, Cai Z H, Zhang Q, 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, Brockhoff D, Thiele L. The Hypervolume Indicator Revisited: On the Design of Pareto-Compliant Indicators via Weighted Integration // Proc of the 4th International Conference on Evolutionary Multi-criterion Optimization. Matsushima, Japan, 2007: 862-876 [16] Li M Q, Zheng J H. 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) [17] Li M Q, Zheng J H, Xiao G X, et al. A Diversity Metric for Multi-objective Evolutionary Algorithm. Pattern Recognition and Artificial Intelligence, 2008, 21(5): 695-703 (in Chinese) (李密青,郑金华,肖桂霞,等.一种多目标进化算法的分布度评价方法.模式识别与人工智能, 2008, 21(5): 695-703) [18] Zitzler E, Knowles J, Thiele L. Quality Assessment of Pareto Set Approximations // Branke J, Deb K, Miettinen K, et al., eds. Multiobjective Optimization. Berlin, Germany: Springer, 2008: 373-404 [19] Zheng J H, Wang K, Li M Q, et al. A Delaunay Triangulation Based Diversity Metric for Solution Set of Multi-objective Evolutio- nary Algorithms. Pattern Recognition and Artificial Intelligence, 2012, 25(6): 885-893 (in Chinese) (郑金华,王 康,李密青,等.基于Delaunay三角剖分的多目标进化算法解集分布度评价指标.模式识别与人工智能, 2012, 25(6): 885-893) [20] Li M Q, Yang S X, Liu X H. Shift-Based Density Estimation for Pareto-Based Algorithms in Many-Objective Optimization. IEEE Trans on Evolutionary Computation, 2014, 18(3): 348-365 [21] Li M Q, Zheng J H, Xiao G X. Uniformity Assessment for Evolutionary Multi-objective Optimization // Proc of the IEEE Congress on Evolutionary Computation. Hong Kong, China, 2008: 625-632 [22] Schütze O, Mostaghim S, Dellnitz M, et al. Covering Pareto Sets by Multilevel Evolutionary Subdivision Techniques // Proc of the 2nd International Conference on Evolutionary Multi-criterion Optimization. Faro, Portugal, 2003: 118-132 [23] Coello Coello C A, Cortés N C. Solving Multiobjective Optimization Problems Using an Artificial Immune System. Genetic Programming and Evolvable Machines, 2005, 6(2): 163-190 [24] Deb K, Mohan M, Mishra S. Evaluating the ε-Domination Based Multi-objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions. Evolutionary Computation, 2005, 13(4): 501-525 [25] Zhang Q F, Li H. MOEA/D: A Multi-objective Evolutionary Algorithm Based on Decomposition. IEEE Trans on Evolutionary Computation, 2007, 11(6): 712-731 [26] Li H, Zhang Q F. Multiobjective Optimization Problems with Complicated Pareto Sets, MOEA/D and NSGA-II. IEEE Trans on Evolutionary Computation, 2009, 13(2): 284-302 [27] Kukkonen S, Lampinen J. GDE3: The Third Evolution Step of Generalized Differential Evolution // Proc of the IEEE Congress on Evolutionary Computation. Edinburgh, UK, 2005, I: 443-450 [28] Bentley P J, Wakefield J P. Finding Acceptable Solutions in the Pareto-Optimal Range Using Multiobjective Genetic Algorithms // Chawdhry P K, Roy R, Pant R K, eds. Soft Computing in En- gineering Design and Manufacturing. London,UK: Springer, 1998: 231-240 [29] Li M Q, Zheng J H, Li K, et al. Enhancing Diversity for Average Ranking Method in Evolutionary Many-Objective Optimization // Schaefer R, Cotta C, Koodziej J, et al., eds. Parallel Problem Solving from Nature. Berlin, Germany: Springer, 2010: 647-656
2014, Vol. 27 
