引用本文

梁正平, 李辉才, 王志强, 胡凯峰, 朱泽轩. 自适应变化响应的动态多目标进化算法. 自动化学报, 2023, 49(8): 1688−1706 doi: 10.16383/j.aas.c210121

Liang Zheng-Ping, Li Hui-Cai, Wang Zhi-Qiang, Hu Kai-Feng, Zhu Ze-Xuan. Dynamic multi-objective evolutionary algorithm with adaptive change response. Acta Automatica Sinica, 2023, 49(8): 1688−1706 doi: 10.16383/j.aas.c210121

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

关键词

动态多目标优化，进化算法，自适应变化响应，预测，存档 

摘要

动态多目标优化问题(Dynamic multi-objective optimization problems, DMOPs)的目标函数发生变化时, 需要采取变化响应策略对种群进行重新初始化, 以快速追踪新环境中的最优解集. 现有动态多目标优化算法对不同个体、不同维度的决策变量缺乏针对性的变化响应, 导致重新初始化效果尚存在较大改进空间. 为此, 提出一种对不同个体、不同维度的决策变量分别进行自适应变化响应的动态多目标进化算法(Dynamic multi-objective evolutionary algorithm with adaptive change response, DMOEA-ACR). 该算法包括两个核心部分: 1)对t时间步最优种群和t−1时间步最优种群中对应个体各维度决策变量之间的差异进行计算, 自适应选择变异策略或预测策略重新初始化不同个体、不同维度的决策变量; 2)在每轮迭代或重新初始化后, 对非支配个体进行存档, 基于存档中心构建预测策略. 为验证DMOEA-ACR的有效性, 在最新测试问题集SDP和DF上, 将其与动态多目标优化领域的6种先进算法进行对比. 实验结果表明, DMOEA-ACR在求解动态多目标优化问题时, 具有明显优势.

文章导读

动态多目标优化问题(Dynamic multi-objective optimization problems, DMOPs)广泛存在于现实世界的各类实际应用中, 如疫苗接种安排[1]、任务规划[2]、卫星下行功率分配[3]、选矿原矿配置[4]等. 

多目标进化算法(Multi-objective evolutionary algorithm, MOEA)对于各类多目标优化问题的求解具有非常好的效果[7-8]. 近年来, 为充分利用MOEAs的优势, 学术界在MOEAs中引入各种类型的动态响应机制, 设计了一系列动态多目标进化算法(Dynamic multi-objective evolutionary algorithm, DMOEA)[9-13], 以满足各类DMOPs的处理需求. 每个DMOEA由静态优化框架、变化检测机制和变化响应策略三个部分组成. 其中, 静态优化框架通常采用某个成熟的MOEA, 在两次动态变化之间对问题进行优化; 变化检测机制用于对优化环境即目标函数是否发生改变进行检测; 变化响应策略通过重新初始化种群, 对改变的环境进行及时响应, 以快速追踪新环境的帕累托最优解集(Pareto optimal set, PS)和对应的帕累托前沿(Pareto front, PF). 变化响应策略是DMOEA的核心组件, 对DMOEA的性能具有决定性影响.

现有DMOEA采用的变化响应策略主要包括多样性相关策略[14-19]、记忆策略[20-22]、预测策略[23-32]和基于机器学习的策略[33-38]等. 不同的变化响应策略侧重不同方面, 具有不同优势. 其中, 多样性相关策略通过突变、引入随机个体、t−1时间步中具有良好多样性的个体等方式对变化作出响应, 以增加或维持种群在新环境中的多样性. 记忆策略通过重用历史上相同或相似环境中的最优解来加速种群的收敛. 预测策略基于种群历史信息来追踪新环境中的PS, 侧重于提高种群的收敛性. 基于机器学习的策略使用迁移学习等特定模型, 对种群进行重新初始化, 为解决DMOPs提供了新的思路. 近年来, 为充分发挥不同变化响应策略的协同效应, 融合多种变化响应方式的混合策略获得了广泛关注[39-47]. 现有变化响应策略虽在各类DMOPs处理上取得了一定效果, 但总体上仍存在较大改进空间[48-49].

针对现有DMOEA中变化响应策略的不足, 本文提出一种基于变化差异对不同个体、不同维度的决策变量分别进行自适应变化响应的动态多目标进化算法(Dynamic multi-objective evolutionary algorithm with adaptive change response, DMOEA-ACR). 该算法首先将t时间步最优种群和t−1时间步最优种群中对应个体各维度决策变量之间的差异进行计算. 若某个体、某维决策变量的差异值小于该维决策变量的差异平均值, 说明该个体、该维决策变量在PS上对应的最优值较大概率存在于当前决策变量值附近, 此时采用有利于提升多样性的变异策略进行变化响应; 反之, 若某个体、某维决策变量的差异值大于该维决策变量的差异平均值, 说明需要在较大的范围内搜索, 才能找到该个体、该维决策变量在PS上对应的最优值, 此时采用有利于提升收敛性的预测策略进行变化响应. 此外, DMOEA-ACR在每轮迭代或重新初始化后, 对种群中的非支配个体进行存档, 并将存档中心作为预测策略的核心要素. 由于种群中的非支配个体都是对应时间步收敛性最好的个体, 基于非支配个体存档中心的预测策略有利于快速追踪新环境的PS. 总之, DMOEA-ACR基于每个个体、每维决策变量的差异自适应选择变异策略或预测策略, 一方面可提升变化响应的针对性, 另一方面可促进收敛性和多样性的平衡, 从而极大改善算法的整体性能.

本文主要贡献如下.

1)提出一种基于决策变量变化差异自适应选择变化响应策略的方法;

2)提出一种基于非支配个体存档中心的预测策略;

3)将DMOEA-ACR与6种先进的DMOEA方法, 在最新SDP和DF测试问题集上进行对比实验, 实验结果表明DMOEA-ACR具有明显的竞争力.

本文结构如下: 第1节介绍本文的相关工作; 第2节详细介绍本文算法的框架和核心模块; 第3节介绍本文的实验方案, 并对实验结果进行分析; 第4节总结全文并展望未来的工作.

图 1  二维决策空间最理想情形下的重新初始化示意图

图 2  自适应变化响应示意图

图 3  基于存档中心进行预测策略示意图

针对现有DMOEA中变化响应策略的不足, 本文基于t时间步最优种群和t−1时间步最优种群中对应个体各维度决策变量之间的差异, 提出了一个可对每个决策变量进行针对性自适应变化响应的动态处理策略, 可较好地平衡重新初始化后种群的收敛性和多样性. 与此同时, 本文基于非支配个体存档的中心, 提出一个过程简洁但性能优异的变化响应预测策略. 与6个先进DMOEA在SDP和DF测试问题集上的对比实验表明, 本文提出的DMOEA-ACR方法在处理各类DMOPs时具有明显的竞争优势. 未来工作中, 将进一步深入研究变化响应的自适应选择策略, 以更好地吻合不同类型问题的实际变化情况. 同时, 继续探索如何将记忆策略、基于机器学习的策略等融入自适应的变化响应框架中和对预测策略准确性的进一步提升. 此外, 由于现实中的优化问题基本上都带有约束, 对带约束动态多目标优化进行研究具有重要的理论和应用价值, 在未来工作中将进行进一步研究.

作者简介

梁正平

深圳大学计算机与软件学院副教授. 2006年获得武汉大学博士学位. 主要研究方向为计算智能和大数据分析与应用. E-mail: liangzp@szu.edu.cn

李辉才

深圳大学计算机与软件学院硕士研究生. 主要研究方向为计算智能与应用. E-mail: 1810273028@email.szu.edu.cn

王志强

深圳大学计算机与软件学院教授. 主要研究方向为计算智能, 大数据分析与应用和多媒体技术与应用. E-mail: wangzq@szu.edu.cn

胡凯峰

深圳大学信息中心工程师. 2019年获得深圳大学硕士学位. 主要研究方向为计算智能及其应用. E-mail: kaifeng@szu.edu.cn

朱泽轩

深圳大学计算机与软件学院教授. 2008年获得南洋理工大学博士学位. 主要研究方向为计算智能, 机器学习和生物信息学. 本文通信作者. E-mail: zhuzx@szu.edu.cn