计算机科学 ›› 2022, Vol. 49 ›› Issue (7): 254-262.doi: 10.11896/jsjkx.210600184

• 计算机网络 • 上一篇    下一篇

基于自适应知识迁移与资源分配的多任务协同优化算法

唐枫, 冯翔, 虞慧群   

  1. 华东理工大学信息科学与工程学院 上海200237
    上海智慧能源工程技术研究中心 上海200237
  • 收稿日期:2021-06-28 修回日期:2021-10-18 出版日期:2022-07-15 发布日期:2022-07-12
  • 通讯作者: 冯翔(xfeng@ecust.edu.cn)
  • 作者简介:(1825548598@qq.com)
  • 基金资助:
    国家自然科学基金(61772200,61772201,61602175);上海市浦江人才计划(17PJ1401900);上海市经信委“信息化发展专项资金”(201602008)

Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation

TANG Feng, FENG Xiang, YU Hui-qun   

  1. School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China
    Shanghai Engineering Research Center of Smart Energy,Shanghai 200237,China
  • Received:2021-06-28 Revised:2021-10-18 Online:2022-07-15 Published:2022-07-12
  • About author:TANG Feng,born in 1997,postgra-duate.Her main research interests include evolutionary computation and swarm intelligence.
    FENG Xiang,born in 1977,Ph.D,professor,is a member of China Computer Federation.Her main research interests include artificial intelligence,swarm intelligence and evolutionary computing,and big data intelligence.
  • Supported by:
    National Natural Science Foundation of China(61772200,61772201,61602175),Shanghai Pujiang Talent Program(17PJ1401900) and Shanghai Economic and Information Commission “Special Fund for Information Development”(201602008).

摘要: 多任务优化算法在各任务单独优化的同时进行任务间的知识迁移,从而提升多个任务的综合性能。然而,在相似度较低的任务间进行负向知识迁移反而会导致整体性能下降,且为难度不同的任务分配同等的计算资源会造成资源浪费。此外,在任务的不同阶段采用固定的搜索步长容易陷入局部最优。为解决上述问题,提出了一种基于自适应知识迁移与动态资源分配的多任务协同优化(Multitask Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer and Resource Allocation,AMTO)算法。首先,每个任务用一个单独的种群进行优化,并将一个种群分成3个子种群,采用3种不同的搜索策略,增加搜索行为的多样性,并且在单个任务内根据个体成功率来动态更新搜索步长,增强自适应搜索能力,避免陷入局部最优;其次,利用多个任务间知识迁移的反馈结果在线计算任务间相似度,并依据相似度自适应地调整迁移概率,同时,在相似度较低的任务间进行迁移时还需减去任务偏差,减小负向知识迁移造成的性能下降程度,提升算法对任务间差异的感知能力;然后,通过评估任务性能的提升度来估计任务难度与优化状态,对不同难度与状态的任务动态按需分配资源,最大限度地提升资源的利用率,减少资源浪费;最后,在简单与复杂两类多任务优化函数上,将本文算法与经典的多任务算法进行对比实验,验证了本文算法中自适应迁移策略、动态资源分配策略及其综合的有效性。

关键词: 动态群搜索算法, 多任务协同优化, 计算资源分配, 任务间偏差, 自适应知识迁移

Abstract: Multi-task optimization algorithm optimizes each task separately and transfers knowledge among tasks at the same time to improve the comprehensive performance of multiple tasks.However,the negative knowledge transfer between tasks with low similarity leads to the overall performance degradation,and allocating the same computing resources to tasks with different difficulties will lead to resource waste.In addition,it is easy to fall into local optimum by using fixed search step size at different stages of the task.To solve these problems,a multi-task collaborative optimization(AMTO) algorithm based on adaptive know-ledge transfer and dynamic resource allocation is proposed.Firstly,each task is optimized by a single population,and a population is divided into three subpopulations.Three different search strategies are adopted to increase the diversity of search behavior.The search step size is dynamically updated according to the individual update success rate in a single task to enhance the adaptive search ability and avoid falling into local optimum.Secondly,the similarity between tasks is calculated online using the feedback results of knowledge transfer among multiple tasks,and the transfer probability is adjusted adaptively according to the similarity.At the same time,when the similarity between tasks is low,the task deviation should be subtracted to reduce the performance degradation caused by negative knowledge transfer and improve the perception ability of the algorithm to the differences between tasks.Then,the difficulty and optimization state of the task is estimated by evaluating the improvement degree of the task performance,and the resources are dynamically allocated on demand for the tasks with different difficulties and states to maximize the utilization value of resources and reduce the waste of resources.Finally,on the simple and the complex multi-task optimization functions,the proposed algorithm is compared with the classical multi-task algorithms to verify the effectiveness of the adaptive migration strategy,dynamic resource allocation strategy and synthesis.

Key words: Adaptive knowledge transfer, Computing resource allocation, Dynamic group search algorithm, Inter-task deviation, Multi-task collaborative optimization

中图分类号: 

  • TP183
[1]GUPTA A,ONG Y,FENG L.Insights on Transfer Optimization:Because Experience is the Best Teacher[J].IEEE Transactions on Emerging Topics in Computational Intelligence,2017,2(1):51-64.
[2]GUPTA A,ONG Y,FENG L.Multifactorial Evolution:To-wards Evolutionary Multitasking[J].IEEE Transactions on Evo-lutionary Computation,2016,20(3):343-357.
[3]SONG H,QIN A,TSAI P,et al.Multitasking Multi-Swarm Optimization[C]//IEEE Congress on Evolutionary Computation.2019:1937-1944.
[4]FENG L,ZHOU W,ZHOU L,et al.An Empirical Study ofMultifactorial PSO and Multifactorial DE[C]//IEEE Congress on Evolutionary Computation.2017:921-928.
[5]LI G,ZHANG Q,GAO W.Multipopulation Evolution Frame-work for Multifactorial Optimization [C]//Proceedings of the Genetic and Evolutionary Computation Conference Companion.Association for Computing Machinery.2018:215-216.
[6]ZHOU Y,WANG T,PENG X.MFEA-IG:A Multi-Task Algorithm for Mobile Agents Path Planning[C]//IEEE Congress on Evolutionary Computation.2020:1-7.
[7]LIN J,LIU H,TAN K,et al.An Effective Knowledge Transfer Approach for Multiobjective Multitasking Optimization[J].IEEE Transactions on Cybernetics,2021,51(6):3238-3248.
[8]FENG L,HUANG Y,ZHOU L,et al.Explicit EvolutionaryMultitasking for Combinatorial Optimization:A Case Study on Capacitated Vehicle Routing Problem[J].IEEE Transactions on Cybernetics,2021,51(6):3134-3156.
[9]LIN J,LIU H,XUE B,et al.Multiobjective Multitasking Optimization Based on Incremental Learning[J].IEEE Transactions on Evolutionary Computation,2020,24(5):824-838.
[10]DING J,YANG C,JIN Y,et al.Generalized Multi-tasking forEvolutionary Optimization of Expensive Problems[J].IEEE Transactions on Evolutionary Computation,2019,23(1):44-58.
[11]GONG M,TANG Z,LI H,et al.Evolutionary MultitaskingWith Dynamic Resource Allocating Strategy[J].IEEE Transactions on Evolutionary Computation,2019,23(5):858-869.
[12]GUPTA A,ONG Y,FENG L,et al.Multiobjective Multifacto-rial Optimization in Evolutionary Multitasking[J].IEEE Transactions on Cybernetics,2017,47(7):1652-1665.
[13]YUAN Y,ONG Y,FENG L,et al.Evolutionary Multitaskingfor Multiobjective Continuous Optimization:Benchmark Problems,Performance Metrics and Baseline Results[J].arXiv:1706.02766,2017.
[14]LIANG Z,DONG H,LIU W,et al.Evolutionary Multitasking for Multiobjective Optimization With Subspace Alignment and Adaptive Differential Evolution[J].IEEE Transactions on Cybernetics,2020,52(4):2096-2109.
[15]BALI K,GUPTA A,ONG Y,et al.Cognizant Multitasking in Multiobjective Multifactorial Evolution:MO-MFEA-II[J].IEEE Transactions on Cybernetics,2021,51(4):1784-1796.
[16]YI J,BAI J,HE H,et al.A Multifactorial Evolutionary Algorithm for Multitasking Under Interval Uncertainties[J].IEEE Transactions on Evolutionary Computation,2020,24(5):908-922.
[17]SHENG W,WANG X,WANG Z,et al.Adaptive Memetic Differential Evolution with Niching Competition and Supporting Archive Strategies for Multimodal Optimization[J].Information Sciences,2021,573:316-331.
[18]BALI K,ONG Y,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.
[19]DA B,ONG Y,FENG L,et al.Evolutionary Multitasking for Single-objective Continuous Optimization:Benchmark Problems,Performance Metric,and Baseline Results[J].arXiv:1706.03470,2017.
[1] 潘燕娜, 冯翔, 虞慧群.
基于自适应资源分配池的竞争合作群协同优化算法
Competitive-Cooperative Coevolution for Large Scale Optimization with Computation Resource Allocation Pool
计算机科学, 2022, 49(2): 182-190. https://doi.org/10.11896/jsjkx.201200012
[2] 徐旭, 钱丽萍, 吴远.
基于移动边缘计算的区块链计算资源分配和收益分享研究
Computation Resource Allocation and Revenue Sharing Based on Mobile Edge Computing for Blockchain
计算机科学, 2021, 48(11): 124-132. https://doi.org/10.11896/jsjkx.201100205
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!