进化迁移优化算法综述

doi:10.19678/j.issn.1000-3428.0064756

摘要/Abstract

摘要： 进化算法是模拟自然界生物进化的启发式算法，具有良好的搜索能力和灵活性且广泛用于复杂优化问题的求解，但在求解过程中默认问题先验知识为零，然而由于问题很少孤立存在，解决单一任务积累的经验可迁移至其他相关任务。进化迁移优化算法利用相关领域的知识学习和迁移，实现了更好的优化效率和性能。介绍进化迁移优化算法的基本分类，从源任务选择、知识迁移、缩小搜索空间差异、进化算法搜索、进化资源分配等5个角度出发对主流进化迁移优化算法的核心策略和优劣势进行梳理和分析。通过中国知网和WOS平台对2014年至2021年的进化迁移优化相关文献进行检索，运用知识图谱进行数据挖掘、信息处理、知识计量和图形绘制，根据进化迁移优化的发展趋势和经验分析总结了其面临的主要挑战和未来研究方向。

关键词: 进化算法, 进化迁移优化, 进化多任务优化, 知识迁移, 迁移学习

Abstract: Evolutionary Algorithm(EA) are heuristic algorithms that simulate natural biological evolution and exhibit good searchability and flexibility.They have been successfully applied to solve complex optimization problems. However, while solving the problem, EA default the prior knowledge to zero.However, as target problems seldom exist in isolation, experience gained from a task can be transferred to other related tasks.Evolutionary Transfer Optimization(ETO) algorithms utilize knowledge learning and transferring in related fields to achieve improved optimization efficiency and performance.This study introduces a basic classification of ETO algorithms.The core strategies, advantages, and disadvantages of the mainstream ETO algorithms are sorted out and analyzed from five perspectives:source task selection, knowledge transfer, narrowing the search space difference, evolutionary algorithm search, and evolutionary resource allocation.Relevant papers on ETO published from 2014 to 2021 are retrieved through the China National Knowledge Infrastructure(CNKI) and Web of Science(WOS).The knowledge graph is used for data mining, information processing, knowledge measurements, and graph drawing.Based on the development trend of ETO and experience, the main challenges and future research directions are summarized.

Key words: Evolutionary Algorithm(EA), Evolutionary Transfer Optimization(ETO), Evolutionary Multitask Optimization(EMTO), knowledge transfer, Transfer Learning(TL)

中图分类号:

TP18

伍洲, 杨寒石, 邬俊俊, 张海军, 宋晴. 进化迁移优化算法综述[J]. 计算机工程, 2023, 49(1): 1-14.

WU Zhou, YANG Hanshi, WU Junjun, ZHANG Haijun, SONG Qing. Survey of Evolutionary Transfer Optimization Algorithms[J]. Computer Engineering, 2023, 49(1): 1-14.

http://www.ecice06.com/CN/Y2023/V49/I1/1

图/表 12

20230701174632

20230701174636

20230701174640

20230701174644

20230701174647

20230701174651

20230701174654

20230701174657

20230701174701

20230701174704

20230701174707

20230701174710

参考文献

[1] MOLINA D, LATORRE A, HERRERA F.An insight into bio-inspired and evolutionary algorithms for global optimization:review, analysis, and lessons learnt over a decade of competitions[J].Cognitive Computation, 2018, 10(4):517-544.
[2] DANTZIG G B, THAPA M N.Linear programming 1:introduction[M].Berlin, Germany:Springer, 2006.
[3] BAZARAA M S, SHERALI H D, SHETTY C M.Nonlinear programming[M].Hoboken, USA:John Wiley & Sons, Inc., 2005.
[4] BUBECK S.Convex optimization:algorithms and complexity[J].Foundations and Trends in Machine Learning, 2015, 8(3/4):231-357.
[5] LIN M H, TSAI J F, YU C S.A review of deterministic optimization methods in engineering and management[J].Mathematical Problems in Engineering, 2012(6):1-15.
[6] KUMAR M, HUSAIN M, UPRETI N, et al.Genetic algorithm:review and application[EB/OL].[2022-04-13].https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3529843.
[7] CHAKRABORTY, UDAY K.Advances in differential evolution[M].Berlin, Germany:Springer, 2008.
[8] 魏德宾, 刘健, 潘成胜, 等.卫星网络中基于多QoS约束的蚁群优化路由算法[J].计算机工程, 2019, 45(7):114-120. WEI D B, LIU J, PAN C S, et al.Ant colony optimization routing algorithm based on multi-QoS constraints in satellite networks[J].Computer Engineering, 2019, 45(7):114-120.(in Chinese)
[9] KIZIELEWICZ B, SAŁABUN W.A new approach to identifying a multi-criteria decision model based on stochastic optimization techniques[J].Symmetry, 2020, 12(9):1551.
[10] BARATI H, SADEGHI M.An efficient hybrid MPSO-GA algorithm for solving non-smooth/non-convex economic dispatch problem with practical constraints[J].Ain Shams Engineering Journal, 2018, 9(4):1279-1287.
[11] ELLOUMI W, EL ABED H, ABRAHAM A, et al.A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP[J].Applied Soft Computing, 2014, 25:234-241.
[12] FALLAH M, TAVAKKOLI-MOGHADDAM R.A robust approach for a green periodic competitive VRP under uncertainty:DE and PSO algorithms[J].Journal of Intelligent & Fuzzy Systems, 2019, 36(6):5213-5225.
[13] TIAN Y, ZHANG X Y, WANG C, et al.An evolutionary algorithm for large-scale sparse multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation, 2020, 24(2):380-393.
[14] SALIH S Q, ALSEWARI A A.A new algorithm for normal and large-scale optimization problems:nomadic people optimizer[J].Neural Computing and Applications, 2020, 32(14):10359-10386.
[15] BACK T, HAMMEL U, SCHWEFEL H P.Evolutionary computation:comments on the history and current state[J].IEEE transactions on Evolutionary Computation, 1997, 1(1):3-17.
[16] TANABE R, ISHIBUCHI H.A review of evolutionary multimodal multiobjective optimization[J].IEEE Transactions on Evolutionary Computation, 2020, 24(1):193-200.
[17] 代瑞瑞, 马永杰, 摆玉龙, 等.基于动态模式搜索的差分进化算法[J].计算机工程, 2016, 42(9):163-167. DAI R R, MA Y J, BAI Y L, et al.Differential evolution algorithm based on dynamic pattern search[J].Computer Engineering, 2016, 42(9):163-167.(in Chinese)
[18] BENNIS F, BHATTACHARJYA R K.Nature-inspired methods for metaheuristics optimization[M].Berlin, Germany:Springer, 2020.
[19] MIRJALILI S, DONG J S, LEWIS A.Nature-inspired optimizers[M].Berlin, Germany:Springer, 2020.
[20] ONG Y S, GUPTA A.Evolutionary multitasking:a computer science view of cognitive multitasking[J].Cognitive Computation, 2016, 8(2):125-142.
[21] GUPTA A, ONG Y S, FENG L.Insights on transfer optimization:because experience is the best teacher[J].IEEE Transactions on Emerging Topics in Computational Intelligence, 2018, 2(1):51-64.
[22] XU Q Z, WANG N, WANG L, et al.Multi-task optimization and multi-task evolutionary computation in the past five years:a brief review[J].Mathematics, 2021, 9(8):864.
[23] TORREY L, SHAVLIK J.Transfer learning[M].Hershey, USA:IGI Global, 2010.
[24] SFERRAZZA C, D'ANDREA R.Transfer learning for vision-based tactile sensing[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS).Washington D.C., USA:IEEE Press, 2019:7961-7967.
[25] THUY M B H, HOANG V T.Fusing of deep learning, transfer learning and GAN for breast cancer histopathological image classification[M].Berlin, Germany:Springer, 2020.
[26] SHAO S Y, MCALEER S, YAN R Q, et al.Highly accurate machine fault diagnosis using deep transfer learning[J].IEEE Transactions on Industrial Informatics, 2019, 15(4):2446-2455.
[27] TAN K C, FENG L, JIANG M.Evolutionary transfer optimization-a new frontier in evolutionary computation research[J].IEEE Computational Intelligence Magazine, 2021, 16(1):22-33.
[28] WEI T Y, WANG S B, ZHONG J H, et al.A review on evolutionary multitask optimization:trends and challenges[J].IEEE Transactions on Evolutionary Computation, 2022, 26(5):941-960.
[29] OSABA E, DEL SER J, MARTINEZ A D, et al.Evolutionary multitask optimization:a methodological overview, challenges, and future research directions[J].Cognitive Computation, 2022, 14(3):927-954.
[30] XUE X M, YANG C E, HU Y, et al.Evolutionary sequential transfer optimization for objective-heterogeneous problems[J].IEEE Transactions on Evolutionary Computation, 2022, 26(6):1424-1438.
[31] GUPTA A, ONG Y S.Genetic transfer or population diversification?Deciphering the secret ingredients of evolutionary multitask optimization[C]//Proceedings of IEEE Symposium Series on Computational Intelligence.Washington D.C., USA:IEEE Press, 2016:1-7.
[32] DA B S, GUPTA A, ONG Y S, et al.Evolutionary multitasking across single and multi-objective formulations for improved problem solving[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2016:1695-1701.
[33] GUPTA A, ONG Y S, FENG L.Multifactorial evolution:toward evolutionary multitasking[J].IEEE Transactions on Evolutionary Computation, 2016, 20(3):343-357.
[34] LIAW R T, TING C K.Evolutionary many-tasking based on biocoenosis through symbiosis:a framework and benchmark problems[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2017:2266-2273.
[35] LIANG Z P, LIANG W Q, WANG Z Q, et al.Multiobjective evolutionary multitasking with two-stage adaptive knowledge transfer based on population distribution[J].IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2022, 52(7):4457-4469.
[36] 董浩.多目标多任务进化算法研究及其在边缘计算服务部署中的应用[D].深圳:深圳大学, 2020. DONG H.Research on multi-objective multi task evolutionary algorithm and its application in service deployment of edge computing[D].Shenzhen:Shenzhen University, 2020.(in Chinese)
[37] 张勇, 杨康, 郝国生, 等.基于相似历史信息迁移学习的进化优化框架[J].自动化学报, 2021, 47(3):652-665. ZHANG Y, YANG K, HAO G S, et al.Evolutionary optimization framework based on transfer learning of similar historical information[J].Acta Automatica Sinica, 2021, 47(3):652-665.(in Chinese)
[38] DA B S, GUPTA A, ONG Y S.Curbing negative influences online for seamless transfer evolutionary optimization[J].IEEE Transactions on Cybernetics, 2019, 49(12):4365-4378.
[39] YI J, BAI J R, HE H B, et al.A multifactorial evolutionary algorithm for multitasking under interval uncertainties[J].IEEE Transactions on Evolutionary Computation, 2020, 24(5):908-922.
[40] SHANG Q, ZHANG L, FENG L, et al.A preliminary study of adaptive task selection in explicit evolutionary many-tasking[C]//Proceedings of 2019 IEEE Congress on Evolutionary Computation(CEC).Washington D.C., USA:IEEE Press, 2019:2153-2159.
[41] HUANG S J, ZHONG J H, YU W J.Surrogate-assisted evolutionary framework with adaptive knowledge transfer for multi-task optimization[J].IEEE Transactions on Emerging Topics in Computing, 2021, 9(4):1930-1944.
[42] CHEN Y L, ZHONG J H, FENG L, et al.An adaptive archive-based evolutionary framework for many-task optimization[J].IEEE Transactions on Emerging Topics in Computational Intelligence, 2020, 4(3):369-384.
[43] HATZAKIS I, WALLACE D.Dynamic multi-objective optimization with evolutionary algorithms:a forward-looking approach[C]//Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation.Washington D.C., USA:IEEE Press, 2006:1201-1208.
[44] WANG Z Z, JIANG M, GAO X, et al.Evolutionary dynamic multi-objective optimization via regression transfer learning[C]//Proceedings of IEEE Symposium Series on Computational Intelligence.Washington D.C., USA:IEEE Press, 2019:2375-2381.
[45] JIANG M, WANG Z Z, QIU L M, et al.A fast dynamic evolutionary multiobjective algorithm via manifold transfer learning[J].IEEE Transactions on Cybernetics, 2021, 51(7):3417-3428.
[46] JIANG M, WANG Z Z, HONG H K, et al.Knee point-based imbalanced transfer learning for dynamic multiobjective optimization[J].IEEE Transactions on Evolutionary Computation, 2021, 25(1):117-129.
[47] JIANG M, WANG Z Z, GUO S H, et al.Individual-based transfer learning for dynamic multiobjective optimization[J].IEEE Transactions on Cybernetics, 2021, 51(10):4968-4981.
[48] JIANG M, HUANG Z Q, QIU L M, et al.Transfer learning-based dynamic multiobjective optimization algorithms[J].IEEE Transactions on Evolutionary Computation, 2018, 22(4):501-514.
[49] ZHOU L, FENG L, GUPTA A, et al.Solving dynamic vehicle routing problem via evolutionary search with learning capability[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2017:890-896.
[50] ZHANG F F, MEI Y, NGUYEN S, et al.Multitask genetic programming-based generative hyperheuristics:a case study in dynamic scheduling[J].IEEE Transactions on Cybernetics, 2022, 52(10):10515-10528.
[51] FENG L, ONG Y S, LIM M H, et al.Memetic search with interdomain learning:a realization between CVRP and CARP[J].IEEE Transactions on Evolutionary Computation, 2015, 19(5):644-658.
[52] FENG L, ONG Y S, TAN A H, et al.Memes as building blocks:a case study on evolutionary optimization + transfer learning for routing problems[J].Memetic Computing, 2015, 7(3):159-180.
[53] KNOWLES J D, WATSON R A, CORNE D.Reducing local optima in single-objective problems by multi-objectivization[C]//Proceedings of the 1st International Conference on Evolutionary Multi-Criterion Optimization.Washington D.C., USA:IEEE Press, 2001:269-283.
[54] ZHANG L J, XIE Y L, CHEN J J, et al.A study on multiform multi-objective evolutionary optimization[J].Memetic Computing, 2021, 13(3):307-318.
[55] YUAN Y, ONG Y S, GUPTA A, et al.Objective reduction in many-objective optimization:evolutionary multiobjective approaches and comprehensive analysis[J].IEEE Transactions on Evolutionary Computation, 2018, 22(2):189-210.
[56] SANTANA R, MENDIBURU A, LOZANO J A.Structural transfer using EDAs:an application to multi-marker tagging SNP selection[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2012:1-8.
[57] HUANG Z X, CHEN Z F, ZHOU Y R.Analysis on the efficiency of multifactorial evolutionary algorithms[M].Berlin, Germany:Springer, 2020.
[58] LI G H, LIN Q Z, GAO W F.Multifactorial optimization via explicit multipopulation evolutionary framework[J].Information Sciences, 2020, 512:1555-1570.
[59] ZHOU L, FENG L, TAN K C, et al.Toward adaptive knowledge transfer in multifactorial evolutionary computation[J].IEEE Transactions on Cybernetics, 2021, 51(5):2563-2576.
[60] FENG L, ONG Y S, JIANG S W, et al.Autoencoding evolutionary search with learning across heterogeneous problems[J].IEEE Transactions on Evolutionary Computation, 2017, 21(5):760-772.
[61] RUAN G, MINKU L L, MENZEL S, et al.When and how to transfer knowledge in dynamic multi-objective optimization[C]//Proceedings of IEEE Symposium Series on Computational Intelligence.Washington D.C., USA:IEEE Press, 2019:2034-2041.
[62] DING J L, YANG C E, JIN Y C, et al.Generalized multitasking for evolutionary optimization of expensive problems[J].IEEE Transactions on Evolutionary Computation, 2019, 23(1):44-58.
[63] BALI K K, GUPTA A, FENG L, et al.Linearized domain adaptation in evolutionary multitasking[C]//Proceedings of 2017 IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2017:1295-1302.
[64] NAZIF H, LEE L S.Optimised crossover genetic algorithm for capacitated vehicle routing problem[J].Applied Mathematical Modelling, 2012, 36(5):2110-2117.
[65] OCHOA G, WALKER J, HYDE M, et al.Adaptive evolutionary algorithms and extensions to the HyFlex hyper-heuristic framework[M].Berlin, Germany:Springer, 2012.
[66] CARRANO E G, FONSECA C M, TAKAHASHI R H C, et al.A preliminary comparison of tree encoding schemes for evolutionary algorithms[C]//Proceedings of IEEE International Conference on Systems, Man and Cybernetics.Washington D.C., USA:IEEE Press, 2007:1969-1974.
[67] MIN A T W, ONG Y S, GUPTA A, et al.Multiproblem surrogates:transfer evolutionary multiobjective optimization of computationally expensive problems[J].IEEE Transactions on Evolutionary Computation, 2019, 23(1):15-28.
[68] KNOWLES J.ParEGO:a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation, 2006, 10(1):50-66.
[69] LIU D N, HUANG S J, ZHONG J H.Surrogate-assisted multi-tasking memetic algorithm[C]//Proceedings of 2018 IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2018:1-8.
[70] LIANG Z P, ZHANG J, FENG L, et al.A hybrid of genetic transform and hyper-rectangle search strategies for evolutionary multi-tasking[J].Expert Systems with Applications, 2019, 138:112798.
[71] ZHANG F F, MEI Y, NGUYEN S, et al.Surrogate-assisted evolutionary multitask genetic programming for dynamic flexible job shop scheduling[J].IEEE Transactions on Evolutionary Computation, 2021, 25(4):651-665.
[72] CHAABANI A, SAID L B.Transfer of learning with the co-evolutionary decomposition-based algorithm-II:a realization on the bi-level production-distribution planning system[J].Applied Intelligence, 2019, 49(3):963-982.
[73] CHAABANI A, BECHIKH S, SAID L B, et al.An improved co-evolutionary decomposition-based algorithm for bi-level combinatorial optimization[C]//Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation.Washington D.C., USA:IEEE Press, 2015:1363-1364.
[74] JIN C, TSAI P W, QIN A K.A study on knowledge reuse strategies in multitasking differential evolution[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2019:1564-1571.
[75] TUAN N Q, HOANG T D, THANH BINH H T.A guided differential evolutionary multi-tasking with powell search method for solving multi-objective continuous optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2018:1-8.
[76] FENG L, ZHOU W, ZHOU L, et al.An empirical study of multifactorial PSO and multifactorial DE[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2017:921-928.
[77] CHEN Y L, ZHONG J H, TAN M K.A fast memetic multi-objective differential evolution for multi-tasking optimization[C]//Proceedings of 2018 IEEE Congress on Evolutionary Computation(CEC).Washington D.C., USA:IEEE Press, 2018:1-8.
[78] WEN Y W, TING C K.Parting ways and reallocating resources in evolutionary multitasking[C]//Proceedings of 2017 IEEE Congress on Evolutionary Computation(CEC).Washington D.C., USA:IEEE Press, 2017:2404-2411.
[79] GONG M G, TANG Z D, LI H, et al.Evolutionary multitasking with dynamic resource allocating strategy[J].IEEE Transactions on Evolutionary Computation, 2019, 23(5):858-869.
[80] YAO S S, DONG Z M, WANG X P, et al.A multiobjective multifactorial optimization algorithm based on decomposition and dynamic resource allocation strategy[J].Information Sciences, 2020, 511:18-35.
[81] GUPTA A, ONG Y S, FENG L, et al.Multiobjective multifactorial optimization in evolutionary multitasking[J].IEEE Transactions on Cybernetics, 2017, 47(7):1652-1665.
[82] WU Z, WU J J, ZHAO M B, et al.Two-layered ant colony system to improve engraving robot's efficiency based on a large-scale TSP model[J].Neural Computing and Applications, 2021, 33(12):6939-6949.
[83] 项小书.求解不确定环境下两类物流规划问题的进化算法研究[D].合肥:安徽大学, 2020. XIANG X S.Research on evolutionary algorithms for solving two logistics planning problems under uncertainty[D].Hefei:Anhui University, 2020.(in Chinese)
[84] 马华伟, 马凯, 郭君.考虑多投递的带无人机车辆路径规划问题研究[J].计算机工程, 2022, 48(8):299-305. MA H W, MA K, GUO J.Research on vehicle routing problem with drones considering multi-delivery[J]. Computer Engineering, 2022, 48(8):299-305.(in Chinese)
[85] TAN L Z, TAN Y Y, YUN G X, et al.An improved genetic algorithm based on k-means clustering for solving traveling salesman problem[C]//Proceedings of Conference on Computer Science, Technology and Application.Changsha, China:World Scientific, 2016:334-343.
[86] CHEN J F, WANG Y H, XUE X S, et al.Cooperative co-evolutionary metaheuristics for solving large-scale TSP art project[C]//Proceedings of IEEE Symposium Series on Computational Intelligence.Washington D.C., USA:IEEE Press, 2017:2706-2713.
[87] DENG W, SHANG S F, CAI X, et al.Quantum differential evolution with cooperative coevolution framework and hybrid mutation strategy for large scale optimization[J].Knowledge-Based Systems, 2021, 224:107080.
[88] YUAN Y, ONG Y S, FENG L, et al.Evolutionary multitasking for multiobjective continuous optimization:benchmark problems, performance metrics and baseline results[EB/OL].[2022-04-13].https://arxiv.org/abs/1706.02766.
[89] XU Z W, LIU X M, ZHANG K, et al.Cultural transmission based multi-objective evolution strategy for evolutionary multitasking[J].Information Sciences, 2022, 582:215-242.
[90] MIN A T W, SAGARNA R, GUPTA A, et al.Knowledge transfer through machine learning in aircraft design[J].IEEE Computational Intelligence Magazine, 2017, 12(4):48-60.
[91] OSABA E, MARTINEZ A D, GALVEZ A, et al.dMFEA-II:an adaptive multifactorial evolutionary algorithm for permutation-based discrete optimization problems[C]//Proceedings of 2020 Genetic and Evolutionary Computation Conference Companion.Washington D.C., USA:IEEE Press, 2020:1690-1696.
[92] BALI K K, ONG Y S, GUPTA A, et al.Multifactorial evolutionary algorithm with online transfer parameter estimation:MFEA-II[J].IEEE Transactions on Evolutionary Computation, 2020, 24(1):69-83.

选择文件类型/文献管理软件名称

选择包含的内容