Diversity Based Surrogate-assisted Evolutionary Algorithm for Expensive Multi-objective Optimization Problem
Author:
Affiliation:

Clc Number:

TP18

Fund Project:

Science & Technology Support Plan of Jiangsu Province (BE2013879)

  • Article
  • | |
  • Metrics
  • |
  • Reference [33]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    The surrogate-assisted evolutionary algorithm (SAEA) is an effective way to solve expensive problems. This study proposed a diversity-based surrogate-assisted evolutionary algorithm (DSAEA) to solve the expensive multi-objective optimization problem. DSAEA approximates each objective with the Kriging model to replace the original objective function evaluation, accelerating the optimization process of the evolutionary algorithm. It decomposes the problem into several subproblems with the reference vectors. The correlation between the solution and the reference vector is established according to the angle between them. Then the minimum correlative solution set is computed. Based on it, the candidate producing operator and the selection operator tend to preserve the solutions of diversity. In addition, as the training set, Archive A is updated after each iteration, deleting the little value samples according to diversity to reduce the modeling time. In the experiment section, large scale 2- and 3-objective comparative experiments for DSAEA and several current popular SAEAs were done. Each algorithm on different test problems ran 30 times independently, and the inverted generational distance (IGD), hypervolume (HV), and running time were calculated and collected. At last, rank sum test was used to analyze the experimental results. The results show that DSAEA performs better on the most experimental test problems, therefore, it is effective and feasible.

    Reference
    [1] Gong MG, Jiao LC, Yang DD, et al. Research on evolutionary multi-objective optimization algorithms. Ruan Jian Xue Bao/Journal of Software, 2009,20(2):271-289(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3483.htm[doi:10.3724/SP. J.1001.2009.03483]
    [2] Jin Y, Wang H, Chugh T, et al. Data-driven evolutionary optimization:An overview and case studies. IEEE Trans. on Evolutionary Computation, 2019,23(3):442-458.
    [3] Tapia MGC, Coello CAC. Applications of multi-objective evolutionary algorithms in economics and finance:A survey. In:Proc. of the 2007 IEEE Congress on Evolutionary Computation (CEC 2007). Singapore:IEEE, 2007.532-539.[doi:10.1109/cec.2007.4424516]
    [4] Arias-Montano A, Coello CAC, Mezura-Montes E. Multiobjective evolutionary algorithms in aeronautical and aerospace engineering. IEEE Trans. on Evolutionary Computation, 2012,16(5):662-694.[doi:10.1109/tevc.2011.2169968]
    [5] Ponsich A, Jaimes AL, Coello CAC. A survey on multiobjective evolutionary algorithms for the solution of the portfolio optimization problem and other finance and economics applications. IEEE Trans. on Evolutionary Computation, 2013,17(3):321-344.[doi:10.1109/TEVC.2012.2196800]
    [6] Zhang J, Xing L. A survey of multiobjective evolutionary algorithms. In:Proc. of the 2017 IEEE Int'l Conf. on Computational Science and Engineering (CSE) and IEEE Int'l Conf. on Embedded and Ubiquitous Computing (EUC). Guangzhou:IEEE, 2017.93-100.[doi:10.1109/CSE-EUC.2017.27]
    [7] Zitzler E, Laumanns M, Thiele L. SPEA2:Improving the strength Pareto evolutionary algorithm for multiobjective optimization. TIK-Report, 2001,103:1-21.[doi:10.3929/ethz-a-004284029]
    [8] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2002,6(2):182-197.
    [9] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I:Solving problems with box constraints. IEEE Trans. on Evolutionary Computation, 2014,18(4):577-601.
    [10] Zhang Q, Li H. MOEA/D:A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2008,11(6):712-731.
    [11] Zitzler E, Künzli S. Indicator-based selection in multiobjective search. In:Yao X, et al. ed. Proc. of the Parallel Problem Solving from Nature-PPSN VⅢ (PPSN 2004). LNCS 3242, Berlin, Heidelberg:Springer-Verlag, 2004.832-842.
    [12] Beume N, Naujoks B, Emmerich M. SMS-EMOA:Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 2007,181(3):1653-1669.
    [13] Jin Y. Surrogate-assisted evolutionary computation:Recent advances and future challenges. Swarm and Evolutionary Computation, 2011,1(2):61-70.
    [14] Wang H, Jin Y, Janson JO. Data-driven surrogate-assisted multi-objective evolutionary optimization of a trauma system. IEEE Trans. on Evolutionary Computation, 2016,20(6):939-952.
    [15] Knowles J. ParEGO:A hybrid algorithm with on-line landscape approximation for expension multiobjective optimization problems. IEEE Trans. on Evolutionary Computation, 2006,10(1):50-66.
    [16] Ponweiser W, Wagner T, Biermann D, et al. Multiobjective optimization on a limited budget of evaluations using model-assisted s-metric selection. In:Rudolph G, Jansen T, Beume N, Lucas S, Poloni C, eds. Proc. of the Parallel Problem Solving from Nature-PPSN X (PPSN 2008). LNCS 5199, Berlin, Heidelberg:Springer-Verlag, 2008.784-794.
    [17] Zhang Q, Liu W, Tsang E, et al. Expensive multiobjective optimization by MOEA/D with Gaussian process model. IEEE Trans. on Evolutionary Computation, 2010,14(3):456-474.
    [18] Chugh T, Jin Y, Miettinen K, et al. A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization. IEEE Trans. on Evolutionary Computation, 2016,22(1):129-142.
    [19] Jones DR, Schonlau M, Welch WJ. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 1998,13(4):455-492.
    [20] Zhang Q, Zhou A, Jin Y. RM-MEDA:A regularity model-based multiobjective estimation of distribution algorithm. IEEE Trans. on Evolutionary Computation, 2008,12(1):41-63.
    [21] Liu B, Zhang Q, Gielen GGE. A Gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems. IEEE Trans. on Evolutionary Computation, 2014,18(2):180-192.
    [22] Pan L, He C, Tian Y, et al. A classification based surrogate-assisted evolutionary algorithm for expensive many-objective optimization. IEEE Trans. on Evolutionary Computation, 2019,23(1):74-88.
    [23] Das I, Dennis JE. Normal-boundary intersection:A new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 1998,8(3):631-657.
    [24] Morris, Max D. The design and analysis of computer experiments. Journal of the American Statistical Association, 2004,99(468):1203-1204.
    [25] Mckay MD, Beckman RJ, Conover WJ. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 2000,42(1):55-61.
    [26] Rasmussen CE. Gaussian processes in machine learning. In:Bousquet O, von Luxburg U, Rätsch G, eds. Proc. of the Advanced Lectures on Machine Learning (ML 2003). LNCS 3176, Berlin, Heidelberg:Springer-Verlag, 2004.64-71.
    [27] Agrawal RB, Deb K, Agrawal RB. Simulated binary crossover for continuous search space. Complex Systems, 2000,9(3):115-148.
    [28] Deb K, Goyal M. A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and Informatics, 1996, 26(4):30-45.
    [29] Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms:Empirical results. Evolutionary Computation, 2000,8(2):173-195.
    [30] Deb K, Thiele L, Laumanns M, et al. Scalable multi-objective optimization test problems. In:Proc. of the 2002 Congress on Evolutionary Computation (CEC 2002). IEEE, 2002.825-830.[doi:10.1109/CEC.2002.1007032]
    [31] 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.
    附中文参考文献:
    [1] 公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究.软件学报,2009,20(2):271-289. http://www.jos.org.cn/1000-9825/3483.htm[doi:10.3724/SP.J.1001.2009.03483]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

孙哲人,黄玉划,陈志远.面向多目标优化的多样性代理辅助进化算法.软件学报,2021,32(12):3814-3828

Copy
Share
Article Metrics
  • Abstract:1024
  • PDF: 3461
  • HTML: 2255
  • Cited by: 0
History
  • Received:February 21,2020
  • Revised:June 07,2020
  • Online: December 02,2021
  • Published: December 06,2021
You are the first2044796Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063