引用本文

张勇, 杨康, 郝国生, 巩敦卫. 基于相似历史信息迁移学习的进化优化框架. 自动化学报, 2021, 47(3): 652-665 doi: 10.16383/j.aas.c180515

Zhang Yong, Yang Kang, Hao Guo-Sheng, Gong Dun-Wei. Evolutionary optimization framework based on transfer learning of similar historical information. Acta Automatica Sinica, 2021, 47(3): 652-665 doi: 10.16383/j.aas.c180515

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180515

关键词

进化优化，迁移学习，粒子群优化，模型匹配 

摘要

现有进化算法大都从问题的零初始信息开始搜索最优解, 没有利用先前解决相似问题时获得的历史信息, 在一定程度上浪费了计算资源.将迁移学习的思想扩展到进化优化领域, 本文研究一种基于相似历史信息迁移学习的进化优化框架.从已解决问题的模型库中找到与新问题匹配的历史问题, 将历史问题对应的知识迁移到新问题的求解过程中, 以提高种群的搜索效率.首先, 定义一种基于多分布估计的最大均值差异指标, 用来评价新问题与历史模型之间的匹配程度; 接着, 将相匹配的历史问题的知识迁移到新问题中, 给出一种基于模型匹配程度的进化种群初始化策略, 以加快算法的搜索速度; 然后, 给出一种基于迭代聚类的代表个体保存策略, 保留求解过程中产生的优势信息, 用于更新历史模型库; 最后, 将自适应骨干粒子群优化算法嵌入到所提框架, 给出一种基于相似历史信息迁移学习的骨干粒子群优化算法.针对多个改进的典型测试函数, 实验结果表明, 所提迁移策略可以加速粒子群的搜索过程, 显著提高算法的收敛速度和搜索效率.

文章导读

进化优化是模拟生物进化行为和机制产生的一类迭代搜索算法, 目前已广泛应用于模式识别、经济管理、电气工程和生物学等众多领域[1]. 典型进化优化技术包含遗传算法(Genetic algorithm, GA)、进化策略(Evolution strategy, ES)和进化规划(Evolutionary programming, EP)等.由于同样启发于生物进化行为, 部分学者也将粒子群优化和蚁群优化等群体智能优化算法归为进化优化技术.该类算法都是从选定的初始种群出发, 通过不断迭代更新种群中个体位置, 直至搜索到最适合问题或任务的解.通常, 这些算法所依赖的初始种群都是在问题可行域中生成的随机位置.换句话说, 现有进化优化算法, 如文献[2-8], 都是从问题的零初始信息开始搜索, 并没有考虑是否以前优化过类似问题, 是否可以从历史信息中获得解决当前相似问题的能力.例如, 在车间调度问题中, 当前月份的生成任务可能与往年某一月份的任务相同或相似.在利用进化优化寻找当前月份最佳调度序列时, 如果能够充分利用相似任务的历史信息, 势必可以提高其搜索能力.

迁移学习(Transfer learning)是一种人性化的机器学习方法, 其目的是把一个领域(即源领域)的知识迁移到另外一个领域(即目标领域), 使得目标领域能够取得更好的学习效果, 即使用以前解决相似任务时获得的信息来帮助解决新问题[9].目前迁移学习已广泛应用于图形识别、文本分类、网页分类等诸多问题[10-15].但是, 将迁移学习应用于进化优化中, 相关研究仍然很少. Dinh等[16]和Koçer等[17]在使用遗传算法处理源域任务时, 保存得到的最优、中等和最差等个体; 当处理新的目标任务时, 迁移这些个体并随机代替初始种群中的部分个体; Feng等[18]将迁移学习融合到进化优化中, 提出了一种新的文化基因进化框架; 最近, Jiang等[19]成功地将迁移学习用于解决动态多目标优化问题, 显著提高了进化优化算法对环境变化的响应速度.

上述方法的成功应用充分说明了利用迁移学习提高进化算法性能的可行性.然而, 相关研究起步较晚, 仍然存在如下不足或可改进之处: 1)在构造迁移学习的源域样本时, 已有工作仅保存种群中最优、中等或者最差的个体, 没有考虑所保存个体的多样性.受益于进化优化的优胜劣汰机制, 种群中的所有个体往往会收敛到搜索空间中的一个点或一个很小的区域.此时, 种群中的最优、中等和最差可能十分相似.在源域中保存诸多相似的个体, 不免造成样本空间分布的过拟合现象. 2)现有工作大都假设源域和目标域已经相似或匹配, 并未给出源域和目标域相似性或匹配程度的判断标准.通常决策者可以获得的相似历史问题或任务往往较多, 如何从众多的历史问题或任务中选出最为相似的一个, 将直接影响到迁移学习的效果; 相反, 当源域问题和目标域问题完全不同时, 强制迁移可能会污染目标域, 产生负面的影响[20]. 3)由源域到目标域的知识迁移方法研究不够.文献[16-17]将源域中保存的个体样本直接替代目标问题的初始种群, 没有考虑源问题与目标问题之间的差异性.尽管文献[18-19]所设计的知识迁移方法考虑了历史问题与目标问题之间的差异性(或映射关系), 但其所得成果皆立足于车辆路径规划和动态多目标优化问题的自身特点, 难以用于本文考虑的静态全局优化问题.

鉴于此, 本文研究一种基于历史相似信息迁移学习的进化优化框架, 用以解决复杂优化问题.针对某一待处理的新问题, 该方法首先从模型库中找到与其最为匹配的历史模型; 接着, 从历史模型对应的源域知识中提取有用信息, 构建源域到目标域的映射关系, 并基于该映射关系产生新问题下进化算法的初始种群.本文主要工作如下: 1)提出一种基于多分布估计的最大均值差异指标, 用来评价新问题与历史问题之间的相似程度; 2)基于模型的相似程度, 给出一种(历史问题对应的)源域到(待优化问题对应的)目标域的自适应知识迁移策略, 初始化当前进化种群中的部分个体, 加快进化算法的搜索速度; 3)为不断更新和丰富历史模型库, 给出一种基于迭代聚类的代表个体保存策略, 形成源域的样本集合, 同时保证个体样本的多样性和质量; 4)将自适应骨干粒子群优化算法嵌入到所提框架, 给出一种基于相似历史信息迁移学习的骨干粒子群优化算法.

本文结构如下: 第1节介绍相关工作, 包括迁移学习和粒子群优化的基本理论; 第2节给出所提基于历史相似信息迁移学习的进化优化框架, 以及基于迁移学习的改进粒子群优化算法; 第3节给出相应的对比实验, 验证算法的有效性; 第4节对本文工作进行总结.

图1 所提基于迁移学习的进化算法框架

图2 优化第1组测试函数时ABPSO和TL-ABPSO算法的收敛曲线

图4 在不同参数ck取值下, TL-ABPSO找到问题最优解所需平均迭代次数

本文研究了一种基于相似历史信息迁移学习的进化优化框架.针对框架中历史模型匹配、历史信息的迁移学习和模型库更新等关键算子, 分别提出了基于多分布估计最大均值差异的历史模型匹配策略、基于模型匹配程度的进化种群初始化策略, 以及于基于迭代聚类的模型库更新策略.通过从模型库中找到与新问题匹配的历史问题, 并将其知识迁移到新问题的进化优化过程中, 该框架明显提高了算法的搜索效率.将已有的粒子群优化算法和差分进化算法分别嵌入到所提进化优化框架, 给出了基于相似历史信息迁移学习的骨干粒子群优化算法和基于相似历史信息迁移学习的自适应差分进化算法.两种算法在10个典型测试问题上的应用表明, 本文所提基于相似历史问题的迁移学习机制, 不仅可以明显加速种群进化过程, 而且能够提高算法的求解质量.

然而, 不可否认, 本文所提策略需要历史和新问题同属一种问题, 而且它们应该具有相似的编解码策略和特性, 这限制了所提进化框架的应用范围.是否可以在两种不同问题(如背包问题和设施布局问题等)之间进行求解信息或求解规则的迁移, 将是我们今后研究的重点; 此外, 如何降低模型匹配等策略带来的计算复杂度问题, 也是今后需要研究的内容.

作者简介

张勇

中国矿业大学信息与控制工程学院教授. 2009年获控制理论与控制工程专业博士学位. 主要研究方向为群体智能和机器学习. E-mail: yongzh401@126.com

杨康

中国矿业大学硕士研究生. 主要研究方向为群体智能和机器学习. E-mail: zgkydxyk@sina.com

巩敦卫

中国矿业大学信息与控制工程学院教授. 1999年在中国矿业大学获博士学位. 主要研究方向为进化计算与应用. E-mail: dwgong@vip.163.com

郝国生

江苏师范大学计算机学院教授. 2009年获得控制理论与控制工程专业博士学位. 主要研究方向为进化计算和大数据应用. 本文通信作者. E-mail: hgskd@jsnu.edu.cn