引用本文

闵芬, 董文波, 丁炜超. 基于决策变量时域变化特征分类的动态多目标进化算法. 自动化学报, 2024, 50(11): 2154−2176 doi: 10.16383/j.aas.c230741

Min Fen, Dong Wen-Bo, Ding Wei-Chao. Dynamic multi-objective evolutionary algorithm based on classification of decision variable temporal change characteristics. Acta Automatica Sinica, 2024, 50(11): 2154−2176 doi: 10.16383/j.aas.c230741

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

关键词

傅里叶变换，动态多目标优化问题，决策变量分类，动态多目标进化算法，预测策略 

摘要

动态多目标优化问题(Dynamic multi-objective optimization problems, DMOPs) 广泛存在于科学研究和工程实践中, 其主要考虑在动态环境下同时联合优化多个冲突目标. 现有方法往往关注于目标空间的时域特征, 忽视了对单个决策变量变化特性的探索与利用, 从而在处理更复杂的问题时不能有效引导种群收敛. 为此, 提出一种基于决策变量时域变化特征分类的动态多目标进化算法(Dynamic multi-objective evolutionary algorithm based on classification of decision variable temporal change characteristics, FT-DMOEA). 所提算法在环境动态变化时, 首先基于决策变量时域变化特征分类方法将当前时刻决策变量划分为线性变化和非线性变化两种类型; 然后分别采用拉格朗日外插法和傅里叶预测模型对线性和非线性变化决策变量进行下一时刻的初始化操作. 为了更有效地识别非线性决策变量变化模式, 傅里叶预测模型通过傅里叶变换将历史种群数据从时域转换到频域, 在分析周期性频率特征后, 使用自回归模型进行频谱估计后再反变换至时域. 在多个基准数据集上和其他算法进行对比, 实验结果表明, 所提算法是有效的.

文章导读

动态多目标优化问题(Dynamic multi-objective optimization problems, DMOPs)是指其目标函数、约束条件和决策变量等可能随时间变化的一类优化问题[1]. 受真实世界中各种不定因素的影响, 在生产实践中广泛存在着DMOPs[2]. 例如生产应用领域的调度问题[3-4], 其中水火电力调度问题需要根据随时间变化的总电力需求, 将电力分配给所有相关单元, 并且在满足液压和电力系统网络约束的同时, 最小化热能发电总燃料成本. 因此, 最优电力调度问题实际上是一个在线动态优化问题, 当电力需求发生变化时, 必须迅速找到最优解. 某些路径规划问题[5-6]也可以视作DMOPs. 例如机器人技术中涉及到的动态障碍物路径规划问题, 该问题需要在动态障碍物环境下找到无碰撞最优路径的同时优化到达时间、通信稳健性等多个冲突目标. 多目标优化问题存在着多个性能指标相互冲突的目标, 通常难以找到满足所有条件的全局最优解[7-9]. 同时由于动态的存在, 任何环境变化都有可能引起目标函数、约束条件或一些重要参数的改变, 从而导致最优解也可能随着时间而改变[10-13]. 传统的多目标优化算法(Multi-objective optimization algorithms, MOAs) 面对具有复杂变化的DMOPs, 无法有效地追踪到最优解的变化, 所以需要设计出能够快速响应环境变化的增强技术. 

动态多目标进化算法(Dynamic multi-objective evolutionary algorithms, DMOEAs) 以其高度并行、广泛适应性和可扩展性等特征已成为处理DMOPs的主流方法. DMOEAs 将环境响应机制与可有效求解常规多目标优化问题的进化算法(Evolutionary algorithms, EAs) 相结合, 解决了EAs面对环境变化时造成的多样性损失和收敛困难的问题. 当检测到环境变化时, DMOEAs触发环境响应机制对当前种群进行合理调整或重新初始化, 以使其向最优解迁移; 在环境稳定时, DMOEAs采用EAs逐步逼近最优解, 直至下一次环境变化. 其中, 合适的环境响应机制对有效追踪到最优解尤为关键. 近年来, 许多响应策略已经被提出, 包括多样性保持、记忆策略、预测策略和迁移学习[14]. 其中预测策略作为环境响应机制的研究热点, 它能从历史演化信息中学习变化模式, 预测最优前沿迁移方向, 引导种群提前到达有潜力的搜索区域, 从而提升算法性能. 例如Hatzakis等[15]提出了一种向前预测策略, 该策略利用全局最优解的历史序列构建自回归模型预测新个体, 再与变化前的非支配解和随机解组成初始种群, 但是它忽略了最优前沿的分布信息, 降低了预测准确度. Koo等[16]设计了梯度预测策略, 它采用加权平均的方式处理历史解集数据, 得到下一次变化的方向和幅度的估计结果, 即预测梯度, 并使用预测梯度更新解集. 该策略无法适应环境变化快的问题, 需要设计更完善的模型提高预测能力. Zhou等[17]以追踪整体最优前沿为目标提出一种基于种群预测策略的算法, 它将种群分为中心点和副本两部分, 分别采用单变量自回归模型预测种群中心点和副本历史数据预测下一个副本. 新环境的初始种群由预测得到的中心点和副本估计得到. 需要指出, 该算法要求相邻环境之间存在一定相似性, 影响了适应性. Zou等[18]提出基于中心点和拐点的预测策略, 引入拐点数据更充分地利用历史最优解的统计信息, 提高了算法预测准确性. 一些工作[19-21]考虑到单一预测方法难以适应多变的环境, 设计了基于集成多种预测方法的策略提高收敛性能, 并取得了一定效果. Guo等[22]关注决策变量对约束的敏感性, 提出了一种基于决策变量分类的动态约束多目标进化算法, 它根据决策变量对收敛、分布和约束违反的影响将决策变量分为四类, 并采用混合策略处理相应的决策变量. 目前更多研究致力于使用更复杂先进的预测模型, 如支持回归向量机[23]、强化学习[24]、神经网络[25]等从历史数据中学习变化模式, 增强适应性. 当前大多数基于预测策略的DMOEAs倾向于将决策变量作为一个整体进行探索, 忽略了单个决策变量的变化特性, 从而在处理更复杂的问题时不能有效引导种群收敛. 此外, 在提取动态环境的变化模式时, 现有的DMOEAs单纯从时域角度分析, 无法深入探索变化的周期性和频率成分, 不能充分利用历史演化信息. 因此本文所提算法在变化响应阶段分析不同决策变量的时域变化特性, 并将其分成线性变化与非线性变化, 对于非线性变化的决策变量采用傅里叶预测模型从频域角度学习变化模式, 为算法搜索能力的提升提供了新方向. 

近年来, 傅里叶变换在各个领域的应用逐渐增多, 包括图像处理[26]、 数字信号处理[27]和机器学习[28]等. 其基本思想是, 将原领域难以求解的问题转换到另一个领域, 从而可以相对容易地求解, 最后再转换回原领域[29]. 基于此思想, 诸多学者结合傅里叶变换建立预测模型来解决相关领域的问题. 例如确定性海浪预测技术使用傅里叶变换估计器对采集的样本进行处理, 可以建立更精准的海浪模型[30]; 在医学领域, 利用结合傅里叶变换的预测模型可以更准确地预测放化疗反应[31]; 利用语音信号的时变特性, 结合短时傅里叶变换和多通道线性预测可以实现高效语音去混响[32]. 从以上研究可以看出, 结合傅里叶变换的预测模型在许多问题上表现出良好的性能. 而现实世界的动态多目标优化问题如电力调度或者金融投资组合优化问题等, 由于人类行为模式、市场波动等因素使问题发生周期性变化. 在进行动态多目标优化时, 考虑到这些周期性变化可以达到更好的优化效果. 傅里叶变换在处理动态数据方面具有很好的应用潜力, 它可以将信号从时域转换到频域, 揭示了变化的频率成分和周期性. 在处理DMOPs时, 可以将目标函数或者决策变量的变化视为信号, 并利用傅里叶变换来分析其周期性等频域特征. 通过对DMOPs进行傅里叶变换分析, 可以识别出频率较高或显著的变化模式, 帮助优化算法更好地适应复杂的动态变化. 因此本文首次将傅里叶变换应用到DMOPs, 旨在利用傅里叶变换的频域分析能力来解决DMOPs中决策变量动态变化带来的困难. 在处理DMOPs时常见的困难包括以下三个方面: 1) DMOPs具有多个彼此冲突的优化目标, 在求解过程中, 除了关注收敛性能还需要保证解集的多样性; 2) 由于DMOPs的目标函数、约束条件和决策变量等随时间变化导致难以快速收敛到新环境的帕累托(Pareto) 前沿; 3) 对于具有较大搜索空间、高维决策变量或者复杂地形的DMOPs, 其问题特性的变化程度差异大, 导致单一方法的收敛性能下降. 

为了解决以上所提到的难点, 本文提出了一种基于决策变量时域变化特征分类的动态多目标进化算法(Dynamic multi-objective evolutionary algorithm based on classification of decision variable temporal change characteristics, FT-DMOEA), 旨在有效求解动态多目标优化问题. 相比其他预测模型, 所提算法具有以下优势: 1) 该算法在每次动态变化时, 基于决策变量时域变化特征分类方法, 从时域角度分析决策变量在相邻环境变化前后的相关性, 将当前时刻决策变量划分为线性变化和非线性变化两种类型, 在重新生成初始种群时采用不同策略处理对应类型的决策变量. 这样的处理方式使得决策变量在迭代过程中尽可能地服从Pareto最优解随时间的分布, 平衡了种群的收敛性和多样性. 2) 算法中提出的傅里叶预测模型用于处理非线性变化类型的决策变量, 它将决策变量的变化视为信号, 并利用傅里叶变换分析其频域特征, 识别出变化规律、周期性以及重要的频率成分, 为后续自回归模型预测提供指导. 具体而言, 傅里叶预测模型将种群的历史数据通过傅里叶变换转化为频域表示, 并利用自回归模型对频域数据进行预测; 然后通过将预测结果反变换回时域, 得到下一时刻决策变量的预测结果. 相比其他传统预测模型, 傅里叶预测模型能更好地捕捉动态变化的周期性, 在分析和理解信号特性方面具有独特的优势, 使种群能够快速收敛到新环境的Pareto前沿. 3) 针对具有复杂变化的DMOPs, 算法集成了两种预测方法增强对环境的适应性, 其中采用傅里叶预测模型处理非线性变化的决策变量, 采用拉格朗日外插法处理线性变化的决策变量. 在实验部分使用了两组动态多目标测试函数集对FT-DMOEA进行综合评估, 实验结果验证了所提的三种机制可以有效应对上文出现的问题. 

为了更准确地指导决策变量逼近Pareto最优解, 所提方法关注每种决策变量在时域上的变化, 基于相邻时刻种群决策变量的相关性将决策变量区分为线性变化和非线性变化. 同时针对两种变化类型, 采用不同的策略处理决策变量, 其中使用傅里叶变换深入挖掘历史数据中的频域信息, 帮助算法更全面地理解变量的变化趋势. 本文的主要贡献包括: 1) 提出一种基于决策变量时域变化特征分类方法, 与其他分类方法不同的是, 该方法通过分析相邻环境变化前后决策变量的相关性将决策变量分为线性变化和非线性变化, 对不同变化类型的决策变量采用对应的预测方法, 保证了解集的多样性. 2) 为探索傅里叶变换与动态多目标进化算法结合的有效性, 设计了傅里叶预测模型分析决策变量变化模式, 引导种群收敛到新的Pareto最优解. 其中傅里叶预测模型通过傅里叶变换将历史种群数据从时域转换到频域, 然后使用自回归模型进行频谱估计后再反变换至时域得到预测结果. 3) 集成了两种预测方法来应对多变的环境. 对于线性变化, 采用拉格朗日外插法进行预测; 对于非线性变化, 采用傅里叶预测模型进行处理. 与多种类型的动态多目标进化算法的对比实验结果表明, FT-DMOEA表现最优, 具备良好的收敛性能; 此外结果还显示算法中所提出的环境响应策略有较强的泛化能力, 在进化后期也能保证稳定的搜索能力. 

本文的第1节简要介绍动态多目标优化问题基本概念, 包括其定义、 一般形式、分类以及Pareto相关定义. 第2节详细描述FT-DMOEA的算法框架和构成组件, 重点解释了每个模块的数学模型和实现方法. 第3节是论文的仿真实验与结果分析, 通过不同实例下数据的对比分析, 验证所提出算法的有效性和性能优势. 第4节是结束语, 总结了文章的主要贡献, 并对未来的研究方向进行展望. 

图 1  FT-DMOEA的流程图

图 2  FT-DMOEA与其他算法在测试函数集上的表现性能显著性差异(越接近白色表示均值差异越明显)

图 3  DMOA、SGEA和FTMOA在FDA1、FDA2和FDA3上获得的POFs

本文提出了一种基于决策变量时域变化特征分类方法的动态多目标进化算法. 该方法首先基于决策变量时域变化特征分类方法分析时域相邻环境决策变量的相关性, 并以此将决策变量分为线性变化和非线性变化两种变化类型. 对于线性决策变量引入拉格朗日外插法进行处理; 对于非线性变化决策变量, 设计了傅里叶预测模型, 其使用傅里叶变换从频域角度分析种群演化历史数据, 可以更有效地识别非线性变化决策变量的变化模式. 傅里叶预测模型首先使用傅里叶变换将时域历史种群数据转换到频域, 然后结合自回归模型进行频谱估计后再反变换得到时域的预测结果. 所提算法与多种动态多目标进化算法在具有不同动态特征和变化强度的动态多目标测试问题上进行了对比实验. 实验结果表明FT-DMOEA在大多数测试实例中表现出色, 可以有效跟踪变化的Pareto最优解, 具有良好的收敛性和多样性. 此外实验结果还表明了所提算法具有良好的泛化能力并且可以保证进化后期也能具有稳定的预测能力. 在未来研究工作中, 将开发自适应参数调节优化器来加速算法收敛; 同时将关注决策变量之间的相关性, 以提升所提算法对高维动态优化问题的适应性. 另外, 也将考虑非周期变化的动态特性, 引入其他策略提高算法普适性. 

作者简介

闵芬

华东理工大学信息科学与工程学院硕士研究生. 2018年获得安徽大学学士学位. 主要研究方向为多目标优化及其应用. E-mail: minfen@mail.ecust.edu.cn

董文波

华东理工大学信息科学与工程学院讲师. 主要研究方向为多视图机器学习, 深度高斯过程和多目标优化. E-mail: wbdong@ecust.edu.cn

丁炜超

华东理工大学信息科学与工程学院副教授. 2019年获得华东理工大学计算机应用技术博士学位. 主要研究方向为群体智能与演化计算, 多目标优化算法和模式识别. 本文通信作者. E-mail: weich@ecust.edu.cn