引用本文

李文桦, 明梦君, 张涛, 王锐, 黄生俊, 王凌. 考虑全局和局部帕累托前沿的多模态多目标优化算法. 自动化学报, 2023, 49(1): 148−160 doi: 10.16383/j.aas.c220476

Li Wen-Hua, Ming Meng-Jun, Zhang Tao, Wang Rui, Huang Sheng-Jun, Wang Ling. Multimodal multi-objective evolutionary algorithm considering global and local Pareto fronts. Acta Automatica Sinica, 2023, 49(1): 148−160 doi: 10.16383/j.aas.c220476

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

关键词

多模态多目标优化，局部收敛性，进化算法，种群多样性 

摘要

多模态多目标优化问题 (Multimodal multi-objective optimization problems, MMOPs)是指具有多个全局或局部Pareto解集(Pareto solution sets, PSs)的多目标优化问题 (Multi-objective optimization problems, MOPs). 在这类问题中, Pareto前沿(Pareto front, PF)上相距很近的目标向量, 可能对应于决策空间中相距较远的不同解. 在实际应用中全局或局部最优解的缺失可能导致决策者缺乏对问题的整体认识, 造成不必要的困难或经济损失. 大部分多模态多目标进化算法 (Multimodal multi-objective evolutionary algorithms, MMEAs) 仅关注获取尽可能多的全局最优解集, 而忽略了对局部最优解集的搜索. 为了找到局部最优解集并提高多模态优化算法的性能, 首先提出了一种局部收敛性指标 (ILC), 并设计了一种基于该指标和改进种群拥挤度的环境选择策略. 基于此提出了一种用于获取全局和局部最优解集的多模态多目标优化算法. 经实验验证, 该算法在对比的代表性算法中性能较好.

文章导读

多目标优化问题 (Multi-objective optimization problems, MOPs) 在现实世界中广泛存在[1]. 对于该类优化问题, 往往需要考虑存在互斥关系的多个优化目标, 并且不存在一个解能够最优化所有优化目标. 因此该类问题的最优解通常为一组互不支配的Pareto最优解集. 在工业应用和现实工程问题中, 决策者经常遇到多个不同的最优解其目标函数值相同的一类问题, 例如脑功能成像[2]、柴油机设计问题[3]、游戏地图生成问题[4]等. 对于Pareto前沿上的某个目标向量, 在决策空间中可以找到多个对应的决策向量. 这类问题通常称为多模态多目标优化问题[5](Multimodal multi-objective optimization problems, MMOPs). 图1展示了一个两目标两决策变量的MMOP, 从中可以看到, A点和B点都对应于Pareto前沿上的P点. 对于决策者来说, 如果能够获得待优化问题的全部最优解, 一方面可以更深入地了解该问题, 对于刻画问题属性、提出改进方向、寻找最优解等具有重要作用; 另一方面, 一旦其中一个最优解因环境变化等因素导致不可用, 决策者可以方便快速地转变到另一个最优解. 对于工业生产来说, 多个最优解意味着有更多的生产方案可供选择. 在某些情况下, 决策者甚至会接受目标值稍劣的解[6]. 例如某个解决方案要达到的加工条件较为苛刻, 或者对加工精度要求极高, 那么决策者将偏向于选择对条件要求不苛刻的解而接受其目标函数值上的劣势. 因此, 如何获得MMOPs的全部最优解成为亟待解决的问题之一.

图 1  两目标两决策变量多模态问题示意图 (左图和右图分别表示问题的决策空间和目标空间)

多目标进化算法 (Multi-objective evolutionary algorithms, MOEAs) 在求解非线性、决策类型多样、决策空间复杂的MOPs上的有效性已经得到了广泛的验证[7-8]. 鉴于MOEAs在MOPs的标准测试问题和实际工程问题上的优异性能, 多种MOEAs被拓展以用于解决MMOPs. 研究者将种群多样性保持机制与现有MOEAs结合, 以获得问题的全部最优解集, 这类算法统称为多模态多目标进化算法 (Multimodal multi-objective evolutionary algorithms, MMEAs). 但由于MMOPs比传统的MOPs具有更复杂的决策空间和映射关系, 目前所提出的MMEAs在求解MMOPs时仍存在许多困难[9], 例如, 如何平衡决策空间的多样性和目标空间的收敛性, 如何保留目标向量相似而决策向量相差较大的个体.

前期围绕MMOPs的大部分工作是获得此类问题的多个全局最优解集, 不考虑问题的局部最优解集. 在火箭任务规划问题[6]中, 对于相距较远的两个火箭发射窗口, 其空间飞行时间和有效载荷相差非常小, 因此对于决策者来说, 获得这两个不同的解具有重要意义. 最新的研究也指出, 在现实问题中, 存在多个全局最优Pareto区域较为罕见. 更普遍的情况是, 多个全局最优与局部最优区域同时存在. 从另一个角度来说, 多个全局最优是存在局部最优的一种特殊情况, 因此, 同时获得问题的全局最优和局部最优区域更为重要[10]. 遗憾的是, 针对此类问题的研究目前还比较少, 仍处于初期阶段. 为了进一步提升MMEAs在具有局部最优解集的MMOPs上的性能, 本文进行了积极的探索, 创新性体现在以下几个方面:

1) 提出了一种局部收敛性指标 (ILCILC). 具体来说, 区别于全局收敛性指标, 局部收敛性指标只要求个体与它附近的个体进行对比. 在进化过程中, 基于局部收敛性指标可以保留问题的局部最优解. 另外, 该指标可以方便地嵌入到已有的MOEAs中, 从而使算法具有搜索问题局部最优Pareto区域的能力.

2) 为了增强算法保持种群多样性的能力, 提出了一种考虑目标空间和决策空间多样性的指标, 并以此为依据, 设计了一种能够同时获得问题的全局和局部Pareto最优解的环境选择策略.

3) 结合局部收敛性指标和环境选择策略, 提出了一种多模态多目标优化算法用以获得MMOPs的全局和局部Pareto解集. 通过对比其他代表性算法在测试问题上的表现, 验证了所提算法的有效性.

本文内容安排如下: 第1节介绍多模态多目标优化的相关概念以及该类问题的求解难点; 第2节详细介绍本文所提的局部收敛性指标以及基于该指标的多模态多目标优化算法; 第3节通过实验对所提算法的有效性进行验证; 第 4 节对本文研究进行总结, 并提出未来可能的研究方向.

图 2  具有局部帕累托前沿的两目标多模态问题 (左图和右图分别表示问题的决策空间和目标空间)

图 3  MMF12 (左)和MMF15 (右)问题的PF和PS示意图

获得MMOPs的全部PS对于决策者具有重要意义. 然而, 由于目标空间多样性与决策空间多样性存在一定的冲突, 因此, 获得全部PS仍然是进化计算领域面临的一个巨大挑战. 此外, 搜索并保留决策者能接受的局部最优PS可以认为是保留全部全局PS的更普遍情况. 这是因为, 拥有多个全局最优PS的问题是具有局部最优PS的一个特例. 研究具备搜索局部PS能力的算法可以更好地解决MMOPs. 在本文中, 提出了局部收敛性指标和基于双空间的拥挤距离, 并通过实验验证了所提方法的有效性, 说明关注问题的局部PS可以更好地解决MMOPs.

目前, 针对MMOPs的研究大多聚焦在连续型优化上[5, 9], 且问题的决策空间较小 (决策变量个数较少), 已有算法重点考虑了解集的分布性而没有重视算法的搜索能力. 然而实际问题的决策变量可能是多类型或大规模的. 近期, CEC会议举办了针对路径规划的多模态多目标竞赛[40-41], 公开了一系列测试集, 研究了多模态多目标优化算法在离散型问题上的性能, 取得了较多的关注. 另一方面, 针对多模态多目标优化算法的实际应用还比较少. 这是因为, 决策者难以确定待优化问题是否属于多模态优化问题; 并且, 已有的MMEAs在实际问题上的效果还有待检验. 因此决策者更倾向于选择传统的MOEAs对问题进行求解, 这对理解问题的决策空间属性造成了一定的障碍. 因此, 如何快速表征某个问题是否为多模态多目标优化问题是推广此类算法的关键. 另外, 未来的研究方向将聚焦于提升多模态多目标优化算法在大规模决策变量问题上的性能以及推动多模态多目标优化算法的实际应用.