Surrogate-Assisted Evolutionary Algorithms with Adaptive Constraint Evaluation

doi:10.3778/j.issn.1673-9418.2203078

Abstract

Abstract: Many real-world optimization problems have not only expensive objectives but also expensive constraints. However, most existing surrogate-assisted evolutionary algorithms (SAEAs) evaluate all constraints of the candidates. With limited number of evaluations, it is wasteful to constantly evaluate constraints whose feasible area is large. To solve this problem, this paper studies SAEAs for expensive constrained optimization problems, and proposes an adaptive constraint evaluation strategy. It can adaptively evaluate constraints with less feasible information according to the population evolution, saving expensive evaluations wasted on constraints with more feasible information. The algorithm can adaptively select and evaluate constraints within limited budget of expensive evaluation to better evolve the population. To verify the effectiveness and scalability of this strategy, this paper designs two Gaussian regression model-assisted differential evolution algorithms cooperated with the adaptive constraint evaluation strategy. Experiments demonstrate the proposed SAEAs perform better in 11 out of 15 problems. Besides, they can achieve more than 94% efficiency improvement with the time delay on evaluations. Specifically, the efficiency improvement is larger than 98% in 91.67% test cases. Experiments in 4 engineering optimization problems demonstrate that SAEAs with the adaptive constraint evaluation strategy have promising applications in real-world optimization problems.

Key words: surrogate model, differential evolution algorithm, expensive constrained optimization, adaptive constraint evaluation strategy

摘要： 很多现实优化问题不仅有昂贵目标也有昂贵约束，而现有求解昂贵优化问题的代理模型辅助演化算法（SAEAs）通常对候选解的所有约束进行评估，在评估次数有限的情况下，频繁评估可行域较大的约束不利于种群演化。针对这一问题，研究了求解昂贵约束优化问题的代理模型辅助算法，提出了一种自适应约束评估策略，根据种群演化情况评估可行域信息较少的约束，以节省在可行域较大的约束上的评估次数，在少量昂贵评估次数下自适应进行约束的选择及评估，更好地演化种群；为验证该策略的有效性和通用性，从两个思路设计了两种自适应约束评估的高斯过程回归模型辅助差分进化算法。这两种方法在15个约束优化测试函数中的11个取得显著优异效果；在利用时间延迟模拟昂贵评估次数的情况下，效率提升均在94%以上，其中91.67%的测试例子效率提升在98%以上。另外，这两种方法在4个工业应用问题中均取得优胜效果，表明其在昂贵工业约束优化问题中良好的应用前景。

关键词: 代理模型, 差分进化算法, 昂贵约束优化, 自适应约束评估策略

WEI Fengfeng, CHEN Weineng. Surrogate-Assisted Evolutionary Algorithms with Adaptive Constraint Evaluation[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(6): 1301-1320.

魏凤凤, 陈伟能. 自适应约束评估的代理模型辅助演化算法[J]. 计算机科学与探索, 2023, 17(6): 1301-1320.

References

[1] 刘琛, 林盈, 胡晓敏. 差分演化算法各种更新策略的对比分析[J]. 计算机科学与探索, 2013, 7(11): 983-993.
LIU C, LIN Y, HU X M. Analyses and comparisons of different update strategies for differential evolution[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(11): 983-993.
[2] LIU Z Z, WANG Y. Handling constrained multiobjective optimization problems with constraints in both the decision and objective spaces[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 870-884.
[3] 雍龙泉, 拓守恒, 史加荣. 约束处理技术及应用[J]. 计算机科学与探索, 2018, 12(6): 1013-1020.
YONG L Q, TUO S H, SHI J R. Constraint-handling technique and applications[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(6): 1013-1020.
[4] LIU B, GIELEN G G E, Fernández F V. Automated design of analog and high-frequency circuits[M]//Studies in Computational Intelligence. Berlin, Heidelberg: Springer, 2014.
[5] JIN Y C. Surrogate-assisted evolutionary computation: recent advances and future challenges[J]. Swarm and Evolutionary Computation, 2011, 1(2): 61-60.
[6] JIN Y C, WANG H D, CHUGH T, et al. Data-driven evolutionary optimization: an overview and case studies[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(3): 442-458.
[7] LIU B, ZHANG Q F, GIELEN GEORGES G E. A Gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 180-192.
[8] WEI F F, CHEN W N, YANG Q, et al. A classifier-assisted level-based learning swarm optimizer for expensive optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(2): 219-233.
[9] 杜欣, 吴晓斌, 倪友聪, 等. 代理模型帮助的SA层性能差分演化优化算法[J]. 计算机科学与探索, 2017, 11(11): 1733-1746.
DU X, WU X B, NI Y C, et al. Surrogate model assisted differential evolutionary for performance optimization at SA level[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(11): 1733-1746.
[10] 季新芳, 张勇, 巩敦卫, 等. 异构集成代理辅助的区间多模态粒子群优化算法[J]. 自动化学报, 2021. DOI:10.16383/j.aas.c210223.
JI X F, ZHANG Y, GONG D W, et al. Interval multimodal particle swarm optimization algorithm assisted by heterogeneous ensemble surrogate[J]. Acta Automatica Sinica, 2021. DOI: 10.16383/j.aas.c210223.
[11] SASENA MICHAEL J, PAPALAMBROS P, GOOVAERTS P. Exploration of metamodeling sampling criteria for constrained global optimization[J]. Engineering Optimization, 2002, 34(3): 263-278.
[12] YANNOU B, SIMPSON TIMOTHY W, BARTON RUSSELL R. Towards a conceptual design explorer using metamodeling approaches and constraint programming[C]//Proceedings of the 2003 ASME Design Engineering Technical Conference and Computers and Information in Engineering Conference. Chicago: ASME, 2003: 605-614.
[13] SINGH H K, RAY T, SMITH W. Surrogate assisted simulated annealing (SASA) for constrained multi-objective optimization[C]//Proceedings of the 2010 IEEE Congress on Evolutionary Computation, Barcelona, Jul 18-23, 2010. Piscataway: IEEE, 2010: 1-8.
[14] REGIS ROMMEL G. Evolutionary programming for high-dimensional constrained expensive black-box optimization using radial basis functions[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 326-347.
[15] SINGH H K, ASAFUDDOULA M, RAY T. Solving problems with a mix of hard and soft constraints using modified infeasibility driven evolutionary algorithm (IDEA-M)[C]//Proceedings of the 2014 IEEE Congress on Evolutionary Computation, Beijing, Jul 6-11, 2014. Piscataway: IEEE, 2014: 983-990.
[16] XUE F, LIU L, CHEN X X, et al. Crude oil distillation optimization using surrogate-aided constrained evolutionary optimization[C]//Proceedings of the 2019 IEEE Congress on Evolutionary Computation, Wellington, Jun 10-13, 2019. Piscataway: IEEE, 2019: 1118-1125.
[17] SINGH P, COUCKUYT I, FERRANTI F, et al. A constrained multi-objective surrogate-based optimization algorithm[C]//Proceedings of the 2014 IEEE Congress on Evolutionary Computation, Beijing, Jul 6-11, 2014. Piscataway: IEEE, 2014: 3080-3087.
[18] KAZEMI M, WANG G G, RAHNAMAYAN S, et al. Metamodel-based optimization for problems with expensive objective and constraint functions[J]. Journal of Mechanical Design, 2011, 133(1): 014505.
[19] WANG H D, JIN Y C. A random forest-assisted evolutionary algorithm for data-driven constrained multiobjective combinatorial optimization of trauma systems[J]. IEEE Transactions on Cybernetics, 2018, 50(2): 536-549.
[20] HANDOKO S D, KWOH C K, ONG Y S. Feasibility structure modeling: an effective chaperone for constrained memetic algorithms[J]. IEEE Transactions on Evolutaionry Computation, 2010, 14(5): 740-758.
[21] WANG Y, YIN D Q, YANG S X, et al. Global and local surrogate-assisted differential evolution for expensive constrained optimization problems with inequality constraints[J]. IEEE Transactions on Cybernetics, 2019, 49(5): 1642-1656.
[22] HABIB A, SINGH H K, CHUGH T, et al. A multiple surrogate assisted decomposition-based evolutionary algorithm for expensive multi/many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(6): 1000-1014.
[23] SUN C L, LI Z, JIN Y C. Surrogate-assisted expensive evolutionary many-objective optimization[J]. Acta Automatica Sinica, 2022, 48(4): 1119-1128.
孙超利, 李贞, 金耀初. 模型辅助的计算费时进化高维多目标优化[J]. 自动化学报, 2022, 48(4): 1119-1128.
[24] 刘晓路, 陈盈果, 贺仁杰, 等. Kirging代理模型在对地观测卫星系统优化中的应用[J]. 自动化学报, 2012, 38(1): 120-127.
LIU X L, CHEN Y G, HE R J, et al. Application of Kriging surrogate model to optimization of earth observation satellite system[J]. Acta Automatica Sinica, 2012, 38(1): 120-127.
[25] 周爱民, 张青富, 张桂戌. 一种基于混合高斯模型的多目标进化算法[J]. 软件学报, 2014, 25(5): 913-928.
ZHOU A M, ZHANG Q F, ZHANG G X. Multiobjective evolutionary algorithm based on mixture Gaussian models[J]. Journal of Software, 2014, 25(5): 913-928.
[26] RASMUSSEN C E, NICKISCH H. Gaussian processes for machine learning (GPML) toolbox[J]. Journal of Machine Learning Research, 2010, 11: 3011-3015.
[27] RASMUSSEN C E. Gaussian processes in machine learning[C]//LNCS 3176: Advanced Lectures on Machine Learning ML Summer Schools 2003. Berlin, Heidelberg: Springer, 2004: 63-71.
[28] DENNIS J, TORCZON V. Managing approximation models in optimization[J]. Multidisciplinary Design Optimization State-of-the-Art, 1997, 5: 330-347.
[29] DAS S, SUGANTHAN P N. Differential evolution: a survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 4-31.
[30] DAS S, MULLICK S S, SUGANTHAN P N. Recent advances in differential evolution—an updated survey[J]. Swarm and Evolutionary Computation, 2016, 27: 1-30.
[31] WANG Y, CAI Z X. Combining multiobjective optimization with differential evolution to solve constrained optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(1): 117-134.
[32] WANG Y, WANG B C, LI H X, et al. Incorporating the feasibility rule for constrained evolutionary optimization[J]. IEEE Transactions on Cybernetics, 2015, 46(12): 1-15.
[33] WANG B C, LI H X, LI J P, et al. Composite differential evolution for constrained evolutionary optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 49(7): 1482-1495.
[34] WOLDESENBET Y G, YEN G G, TESSEMA B G. Constraint handling in multiobjective evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 514-525.
[35] LIANG J J, RUNARSSON T P, MEZURA M, et al. Problem definitions and evaluation criteria for the CEC 2006 special session on real-parameter optimization[J]. Journal of Applied Mechanics, 2006, 41(8): 1-24.
[36] SINGH H K. Development of optimization methods to deal with current challenges in engineering design optimization[J]. AI Commununications, 2016, 29(1): 219-221.
[37] RAHI K H, SINGH H K, RAY T. Partial evaluation strategies for expensive evolutionary constrained optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(6): 1103-1117.
[38] YANG Z, QIU H, GAO L, et al. Surrogate-assisted classification-collaboration differential evolution for expensive constrained optimization problems[J]. Information Sciences, 2020, 508: 50-63.
[39] MALLIPEDDI R, SUGANTHAN P N. Problem definitions and evaluation criteria for the CEC 2010 competition on constrained real-parameter optimization[R]. Singapore: Nanyang Technological University, 2010: 1-16.