摘 要: 粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点,同时一次运行可得到多个解,且能逼近非凸或不连续的 Pareto 最优前端,因而被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法从单目标问题扩展到多目标问题时,Pareto 最优解集的存储与维护、全局和个体最优解的选择以及开发与开采的平衡等问题亦随之出现.通过目标空间变换方法,采用 Pareto 前端在被称为平行格坐标系统的新目标空间中的分布熵及差熵评估种群的多样性及进化状态,并以此为反馈信息来设计进化策略,使得算法能够兼顾近似 Pareto 前端的收敛性和多样性.同时,引入格占优和格距离密度的概念来评估 Pareto 最优解的个体环境适应度,以此建立外部档案更新方法和全局最优解选择机制,最终形成了基于 Pareto 熵的多目标粒子群优化算法.实验结果表明:在 IGD 性能指标上,与另外 8 种对等算法相比,该算法在由 ZDT 和 DTLZ 系列组成的 12 个多目标测试问题集中表现出了显著的性能优势.
关键词: 多目标优化问题;粒子群优化;平行格坐标系统;Pareto 熵;自适应参数
大多数工程和科学问题都可以归结为多目标优化问题(multiobjective optimization problem,简称 MOP),其求解方法一直都是学术界和工程界共同关注的焦点.多目标优化问题通常存在多个彼此冲突的目标,其优化结果为 Pareto 最优解集.与数学规划方法相比,进化算法因一次运行可得到多个解,且能逼近非凸或不连续的 Pareto 最优前端,从而被认为是更适合求解多目标优化问题的智能方法.
粒子群优化算法(particle swarm optimization,简称 PSO)[1]是由 Kennedy 和 Eberhart 在 1995 年提出的仿生算法,它是受到飞鸟集群活动规律的启发,根据社会学和心理学而建立的群体智能模型.粒子群优化算法是一种具有形式简洁、收敛快速和参数调节机制灵活等优点的进化算法,并且已经成功应用于单目标优化问题,被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法从单目标问题扩展到多目标问题而形成多目标粒子群优化(multiple objective particle swarm optimization,简称 MOPSO)时,新的技术问题随之出现.多目标优化问题的 Pareto 最优解集特征和粒子群优化算法的快速收敛特征,使得多目标粒子群优化算法面临以下技术挑战:① 维护存储 Pareto最优解集的档案,使算法最终输出的 Pareto前端能够兼顾收敛性和多样性,这是第二代进化多目标算法的共性问题;② 从群体和个体的 Pareto 最优解集中分别选举全局最优解(gBest)和个体最优 解 (pBest),使这两个最优解引导粒子尽最大可能地发现高质量的新解 ;③ 平衡进化过程中的开采 (exploration)和开发(exploitation),使得种群既保持快速收敛的优点,但又尽可能地避免陷入局部 Pareto 前端或者收敛到单一解.后面两个挑战是多目标粒子群优化算法区别于其他多目标进化算法的特有问题.
本文将根据多目标优化问题和粒子群优化算法的特征,采用近似 Pareto 前端的分布熵及其变化来估计种群进化状态,并依据这些进化过程反馈信息设计具有动态平衡开采和开发能力的进化策略,形成基于 Pareto 熵的多目标粒子群优化算法.
为了内容相对独立以及统一本文术语和符号,本文第 1 节简要介绍多目标优化问题和粒子群优化算法的基本概念.第 2 节综述与本文内容相关的多目标粒子群优化算法的研究现状和存在的问题.第 3 节阐述 Pareto 熵的计算方法以及基于 Pareto 熵的种群进化状态检测方法.第 4 节描述本文算法的主要进化策略和完整的算法流程.第 5 节分析对比实验结果.最后,在第 6 节中给出全文结论.
2 相关研究工作
自 Coello 等人[2]于 2002 年提出采用粒子群算法来求解多目标优化问题以来,多目标进化领域中的成功经验被迅速借鉴到多目标粒子群优化算法中,出现了大量的阶段性研究成果,其中以 Coello 等人[3]采用超网格和变异方法的多目标粒子群优化算法最为经典.Reyes-Sierra[4]对 2006 年之前的多目标粒子群优化算法做了综述总结,随后,Padhye[5,6]做了一些专题比较研究.关于多目标进化算法的最新综述可参见文献[7,8].
对多目标粒子群优化算法的研究主要集中档案维护、全局最优解选择和种群多样性增加等方面,也有少部分工作对个体最优解选择和粒子变异方面进行了研究.
在外部档案维护策略方面,主要借鉴多目标遗传算法中档案维护的有效策略,如采用聚类、拥挤距离 (crowding distance)、自适应超网格(adaptive grid)、 -占优( -dominance)、最大化最小适应度(maximin fitness)、值等形成相应的多目标粒子群优化算法中的档案维护策略[9,10].这些不同的策略都是直接或间接地评估档案中每个个体的密度(拥挤度)或者占优强度.当档案中的 Pareto 最优解个数超出容量限制时,通常直接将个体适应度较好的新解来更新个体适应度较差的旧解,从而使得 Pareto 前端具有更好的分布性能.
在全局最优解选择策略方面,基于随机选择、值、拥挤距离、动态邻居、自适应超网格、聚类、占优树、非占优排序(non-dominated sorting)、Pareto 占优、超体积(hyper-volume)、最大化最小适应度、小生境(niche)、综合学习(comprehensive learning)等策略多目标粒子群优化算法被相继提出来[912].在这些方法中,大多数通过评估外部档案中的个体密度来选择那些处于相对稀疏区域的 Pareto 最优解作为全局最优解以降低选择压力, 避免收敛到单一解,以及增加 Pareto 前端的多样性;而另一部分基于“占优”概念的最优解选择策略则偏重算法的收敛性能,但容易导致过高的选择压力而容易收敛到局部极值.
在个体最优解选择策略方面,虽然绝大部分算法为了降低计算开销而仅保留一个 Pareto 最优解,但仅一个个体最优解不足以描述个体 Pareto 最优前端.Branke[13]和 Abido[14]分别研究了采用个体外部档案保存个体 Pareto 最优解的方法(类似种群外部档案保存种群 Pareto 最优解),获得了比单一个体 Pareto 最优解更好的性能. 另外,最大化最小个体间距离和加权和[13]等策略被用来作为选择个体最优解的标准.
在平衡开发与开采策略方面,如果不合理利用粒子群算法快速收敛的优点,则容易导致早熟而陷入局部极值.一些算法从种群角度提出平衡策略,如动态调整种群大小策略[15]和子群策略[1618];一些算法采用文化进化框架提出平衡策略[19,20];一些算法从粒子运动参数选择角度提出平衡策略,如线性下降惯性权重参数和自适应参数等[21];一些算法从粒子扰动(变异)角度提出平衡策略,自 Coello[3]在多目标粒子群算法中提出变异方法后, 后续多目标粒子群优化算法几乎都采用变异方法来增强种群多样性;还有一些算法采用混合平衡策略[22,23].
但是,多目标粒子群优化算法仍然面临一些技术挑战:
一方面,个体适应度评估决定了多目标粒子群优化算法中选择全局最优解和维护档案这两个关键策略.但当前的个体适应度都是单一度量标准,要么是基于密度的评估来考察个体的多样性潜力,要么是基于 Pareto 占优关系的评估来考察个体的收敛性潜力.因而导致在维护外部档案时不能兼顾 Pareto 最优前端的多样性和收敛性,而在选择全局最优解时不能兼顾平衡开发和开采.
另一方面,全局最优解频繁更换和快速收敛特征,使得开发与开采的平衡问题在多目标粒子群优化算法中更为突出:过度地开发将会导致收敛性不足而影响优化精度,而过度地开采将会导致多样性匮乏而陷入局部极值.虽然已经存在自适应单目标粒子群优化算法[24],但多目标问题的 Pareto 最优解集特征,使得在多目标空间中监测种群进化环境更为复杂.而当前已经存在的多目标粒子群优化算法缺乏种群进化环境的动态监测机制来获取反馈信息,难以决定算法“在何时调节何种进化策略到何种程度”.
熵在热力学中表示系统混乱状态,而在生态学中表示生物的多样性.本文将通过对目标空间变换来获得 Pareto 前端的熵,以此来度量多目标粒子群优化算法中种群的多样性,并利用差熵来估计种群的进化状态,从而为算法提供实时的进化环境反馈信息.同时,在变换后的目标空间中评估 Pareto 最优解的个体密度和格占优强度,为算法中外部档案更新和全局最优解选择提供决策依据.
3 Pareto 熵及进化状态检测
本节先介绍 Pareto 熵的计算方法,包括将采用平行格坐标系统映射目标空间映射的方法和 Pareto 熵及差熵的定义;然后,根据外部档案更新算法中 Pareto 熵的变化情况,分析不同进化状态的临界阈值;最后,归纳出种群进化状态的判定条件.
3.1 平行格坐标系统
平行坐标(parallel coordinates)[25]是一种广泛使用的多维数据分析和可视化方法.多目标优化问题的目标向量正是一种多维数据(在进化多目标优化计算社区中,通常将 2~3 个目标的优化问题称为 multi-objective optimization problem,简称 MOP,而将 4 个以上目标的优化问题称为 many-objective optimization problem,简称 MaOP).受这一方法启发,将存储在外部档案中的多维 Pareto 前端按照平行坐标方式转化到二维平面中,并将 Pareto 前端的笛卡尔坐标值映射成整数值坐标,从而多维 Pareto 前端被转换成一张二维平面网格.对应于笛卡尔坐标系统,在此将这种二维平面网格称为平行格坐标系统(parallel cell coordinates system,简称 PCCS).下面采用采用数学形式来描述这种映射方法.
3.2 Pareto熵及其差熵
熵是一种度量微观分布均匀性的方法.在热力学中,熵表示系统混乱状态,而在生态学中熵表示物种的多样性.当存储在外部档案中的近似 Pareto 前端被映射到 PCCS 后,可以采用熵来度量近似 Pareto 前端的分布均匀性,间接地表达当前种群的多样性特征.如果近似 Pareto 前端发生变化,则会引起 PCCS 中的对应的格坐标分量重新分布,从而引起熵发生变化.因此,可以采用差熵来表示近似 Pareto 前端在相邻迭代时刻的熵的变化大小:
差熵越大,意味着近似 Pareto 前端重新分布的范围越大,这可能由于:① 算法生成的新解占优了大量的旧解而引起 Pareto 前端发生大范围变化;② 新解引起了 max mf 或者 min mf 发生变化而导致第 k 列上的格坐标分量重新分布.
相反,差熵越小,近似Pareto前端重新分布的范围越小,这是因为在外部档案维护过程中,质量更好(如个体密度较小)的新解替换了质量较差(个体密度较大)的旧解而引起个别格坐标分量的重新分布. 从而,通过差熵可以推测当前种群的发现新解的潜力,进而估计种群所处的进化状态,如收敛状态、多样化状态和停滞状态.这种进化状态是设计开发和开采进化策略的依据. 由于采用熵来度量近似 Pareto 前端的分布特征,间接地评估对应的 Pareto 最优解集的性能.本文为了强调在 PCCS 中这种分布熵评估的对象是近似 Pareto 最优解集所对应的近似 Pareto 前端,故将其称为 Pareto 熵.
Pareto 熵及其差熵在进化过程中的变化趋势与待优化多目标问题的性质和优化算法的求解能力紧密相关. 对于单模态多目标优化问题,在进化过程的前期,优化算法通过发现的新解占优较多的旧解而推动种群向真实 Pareto 前端方向收敛,从而引起 Pareto 熵及其差熵发生较大变化;而在进化过程的后期,当种群逼近真实 Pareto 前端后,算法发现的新解只能占优其邻近的个别旧解,或者替换个别适应度较差(如个体密度较大)的旧解,仅能引起 Pareto 熵及其差熵发生很小的变化.但对于多模态多目标优化问题,当优化算法发现的新解跳出局部极值时,新解将会占优处于局部 Pareto 前端上的大量旧解,从而引起 Pareto 熵及其差熵发生急剧变化,直到种群重新聚集在新的局部 Pareto 前端附近为止.根据这一特点,利用 Pareto 熵及其差熵可以识别待优化问题的模态性质和估计种群所处的进化状态,从而动态地调整优化算法的进化策略.
为了说明 Pareto熵及差熵在不同模态下的变化特征,图 2给出了本文算法(详细内容见第4节)采集的 Pareto 熵及差熵变化曲线.其中,存储 Pareto 最优解集的外部档案的最大容量设定为 100.图 2(a)是由具有 3 个目标的单模态测试问题 DTLZ2 产生的 Pareto 熵及差熵变化曲线,图 2(b)是由具有 2 个目标的多模态测试问题 ZDT4 产生的 Pareto 熵及差熵变化曲线.在图 2(a)中的进化前期阶段(大约 Iteration<40,不同算法对同一优化问题可能会有不同的分界值),Pareto 熵及差熵发生较大幅度变化,表明算法产生的新解在不断占优外部档案中的旧解,导致近似 Pareto 前端发生大范围变化;而在图 2(a)中的进化后期阶段(Iteration>40),Pareto 熵及差熵仅发生小幅度变化,表明近似 Pareto 前端只发生局部小范围变化,算法产生的新解仅占优个别就解或替换个别质量较低的旧解. 对于单模态多目标优化问题,Pareto 熵及差熵在进化过程中只经历了一个周期的剧烈变化.而在图 2(b)中的进化前期阶段(约 Iteration<100),Pareto 熵及差熵经历了大约 8 个周期的较为明显的剧烈变化,表明算法在前期阶段产生的新解频繁地跳出局部 Pareto 前端,反映了算法具有很好的发现高质量新解的能力.
需要特别指出的是,Pareto 熵及差熵的剧烈变化周期个数并不等同于局部 Pareto 前端的个数,因为一个高质量的新解有时可以跳过多个局部 Pareto 前端;同时,具有极端边界值的新解有时可能引起 PCCS 的对应目标列中大量格坐标分量重新分布,而使 Pareto 熵及差熵产生一个剧烈变化周期.
3.3 进化状态检测
收敛速度和优化精度是基于概率寻优的进化算法的两个相互冲突目标:过分强调收敛速度往往会引起算法早熟而陷入局部极值;相反,过分注重收敛精度将会增加大量的函数评估次数而使得算法复杂度急剧提高.因此,需要有效地设计开发与开采的平衡策略来控制进化算法的多样性和收敛性.但在设计这种平衡策略之前,算法研究者需要回答“在何时采用何种策略到何种程度”的问题.然而在算法设计之前,通常缺乏对待优化问题的先验知识,并且算法还需要兼顾不同类型的待优化问题.这要求具有平衡开发与开采能力的算法在迭代进化过程中能够检测算法自身所处状态,如收敛状态(convergence status)、多样化状态(diversity status)和停滞状态 (stagnation status),然后根据不同进化状态来动态调节进化策略,使得算法能够适应不同特征的待优化问题,并在收敛速度和优化精度之间达到最佳平衡.
本质上,检测进化状态就是从种群所处的进化环境中获得实时反馈信息,从而为控制进化过程提供决策依据,并形成“检测调节检测…”的闭环控制过程.由于多目标优化问题的优化结果不再是单一解,而是由一组非占优解构成的 Pareto 最优解集,因此,多目标优化问题比单目标优化问题具有更加复杂的进化环境,不能简单地通过比较目标值的大小来判断进化状态,从而使具有自适应进化环境的多目标优化算法设计变得更加困难.有的多目标进化算法通过性能评估指标(如 hyper-volume)来评估进化环境,但这类综合性度量指标难以反映进化迭代中的占优与多样化过程细节.
通过上一小节的分析可知,Pareto 熵的变化是由于进化算法获得的新解占优了 Pareto 前端上的旧解,或者替换了质量较差的旧解而引起的.在采用外部档案存储 Pareto 最优解集的多目标进化算法中,通常认为个体密度较大的 Pareto 解的质量较差,在外部档案更新过程中,往往采用个体密度较小的 Pareto 新解替换个体密度较大的 Pareto 旧解,从而增强近似 Pareto 前端的多样性,包括分布均匀性和延展性.因此,通过评估进化过程中的 Pareto 差熵可以推测进化迭代过程中的占优与多样化细节,从而估计多目标进化算法所处的进化状态,为动态调整进化策略提供反馈信息.但是划分不同进化状态的 Pareto 差熵的分界值是这种方法的关键因素,不合理的分界值会导致进化状态的误判,从而可能诱导进化算法采用相反的进化策略.在此,本小节将从理论上分析划分进化状态的 Pareto 差熵临界阈值. ——论文作者：胡 旺 1,2, Gary G. YEN2 , 张 鑫 1
