基于档案交叉的动态多目标粒子群优化算法

尤嘉兴，陈基漓，2＋，董明刚

（1.桂林理工大学 信息科学与工程学院，广西 桂林541004；2.桂林理工大学 广西空间信息与测绘重点实验室，广西 桂林541004）

0 引 言

在现实世界中存在着许多复杂的动态多目标优化问题（dynamic multi－objective optimization problem，DMOP），其优化目标和约束条件与时间因素息息相关，而这些问题亟需合适的算法来求解。目前针对动态多目标优化问题的研究成果仍较少，其中Deb 等［1］提出了动态NSGA－II算法；尚荣华等［2］根据免疫优势概念和抗体克隆选择学说提出了一种动态多目标免疫克隆优化算法；武燕等［3］通过对最优解的预测提出了一种新的多目标预测遗传算法；Koo等［4］采用了记忆方法，提出了动态多目标进化梯度搜索算法。尽管上述算法在求解的收敛性上效果不错，但对于解集的均匀性则考虑不足，特别是在三目标及以上的多目标优化问题中所得解集的个体分布不够均匀。考虑到上述问题，本文提出了一种改进的欧氏拥挤距离策略，在对解集的维护上综合考虑了解的均匀性、时间复杂度及算法实现复杂度；通过备份与恢复策略充分利用Pareto最优解的历史信息，使得种群可以快速适应历史上出现过的相似环境，同时算法对档案进行的交叉处理增强了种群多样性、促进了个体间的信息交流。

1 问题描述

本文考虑如下动态多目标优化问题

其中，t是时间变量；x＝ （x1，x2，…，xn）是决策变量；［L，V］＝ ｛x＝ （x1，x2，…，xn）｜li∈xi∈vi，i＝1，2，…，n｝是搜索空间，L＝ （l1，l2，…，ln），V＝ （v1，v2，…，vn）；目标f（x，t）包含m 个目标函数fi（x，t），i＝1，2，…，m，并随t离散变化。关于Pareto支配、动态Pareto最优前沿、动态Pareto最优解集的定义请参见文献［5］。

2 标准粒子群优化算法

标准的粒子群算法首先在搜索空间中初始化一定数量的粒子，每个粒子都代表问题的一个潜在解，粒子具有的特征有位置、速度和适应度值。适应度值表示粒子的好坏，所有个体通过追踪个体历史最优值pBest和种群最优值gBest来更新新的位置、速度和适应度值，在算出所有粒子新适应度值后更新个体历史最优位置和种群最优个体，不断重复这一过程直到满足算法停止条件。

标准粒子群优化算法在更新粒子速度及位置时采用以下公式

其中，w 为惯性权重，r1、r2为 ［0，1］间的随机数，c1、c2为学习因子，t为当前迭代次数。通常为防止粒子盲目搜索，对于粒子的搜索范围会给与一定的限制，其中主要是将v和x 限制在一定数值区间内。

3 基于档案交叉的动态多目标粒子群

3.1 改进的粒子群算法模型

相较于针对单目标问题的基础粒子群优化算法，本文算法更依赖档案集中的非支配解集。由于粒子群进化的过程与个体的速度无关［6］，且基础粒子群模型中的速度参数的作用在动态多目标环境中被进一步弱化，因此本文所采用的粒子群模型将速度变量剔除，将粒子群优化公式简化为

式中：archivet1、archivet2——从外部档案中随机选取的两个不同个体。对于新得到的粒子位置xt＋1，计算其所对应的适应度值并与前一位置所对应的适应度值相比较，若新适应度值不被旧适应度值所支配，则接受新的粒子位置，否则保留原粒子位置不变，即只有当新粒子位置不比原位置差时才接受新的解。相对于基础粒子群模型来说，新的模型除了将速度变量剔除外，还抛弃了个体历史最优值，转而从档案集中随机选取个体来充当全局最优。

3.2 档案维护策略

基于拥挤距离对档案进行维护是档案维护策略中常见的一种，且为多数算法所采用。当外部档案所容纳的个体数N 超过档案上限M 时，通常的拥挤距离策略是先计算所有个体各自的拥挤距离值，根据拥挤距离排序，直接一次性从档案中删除超出档案容量的拥挤距离最小的N－M 个个体，这种方法快速且有效，然而由于每个个体的删除会导致其余个体的拥挤距离值变动，一次性删除大量个体容易导致解集中某个区域被整体截断，使得解集局部分布不均匀。另一种策略则是在每次只删除拥挤距离最小的一个个体，之后更新其余个体的拥挤距离，重复这个过程直到外部档案个体数小于档案容量限制，这种策略解决了解集分布不均匀的问题，但额外增加了计算量。

尽管采用传统拥挤距离来保持档案个体的均匀性在面对双目标时表现不错，但当面对三目标及以上的优化问题时则效果不佳，这种情况下采用欧氏距离法则可以有效控制个体之间的距离，保持解集的分布均匀，但是计算复杂度过高。基于此，本文提出一种基于快速欧氏拥挤距离的档案维护策略，具体步骤如下：

步骤1 计算每个个体i与其它个体j的欧氏距离Dist［i］［j］。

步骤2 对每个个体i的欧氏距离Dist［i］分别按从小到大排序。

步骤3 更新每个个体的拥挤距离，其值为与该个体最近的两个个体的欧距之和。

步骤4 将拥挤距离最小的个体标记并剔除，如果当前剩余个体数大于档案容量则返回步骤3，否则继续下一步。

步骤5 对仍存在的个体按拥挤距离从大到小排序并输出。

由于已在步骤2中排序过每个个体与其它个体的欧距，因此步骤3中只需将剩下的最小两个个体欧距值相加即可得该个体的拥挤距离。整个维护过程的计算量基本在步骤1，其时间复杂度为O（n2m），其中n指档案个体数，m 指优化目标维数。

3.3 环境变化检测

在动态多目标优化算法中，对于环境是否发生变化的判断是很重要的一点。由于本文只考虑目标函数的变化，因此采用如下检测方法：随机选取当前种群中20%的个体，计算新适应度值与原适应度值的欧距差，取平均值［7］其中n指随机选取的个体数，m 指目标维数，T 指当前环境，T－1指前一环境。设定阀值θ，如果环境变化程度值大于阀值θ，则判断环境已经发生变化，同时算法对此做出相应的反应。

3.4 环境备份

由于在动态多目标优化问题中可能出现的周期性环境变化，因此将当前环境备份以便算法能够在遇到相似环境时快速恢复是很有必要的。通常环境备份会将算法当前得到的非劣解集保存下来，但由于每个环境的非劣解集较大，完整保存下来需要消耗大量的存储空间。因此为了避免浪费过多的存储资源，可从中选取少量具有代表性的点并保存下来。

从原则上来讲，所选择的点应在尽量少的情况下最大近似地描述整个Pareto档案集中个体的分布，同时代表点的选取过程的时间复杂度不宜过高，以免影响整个算法的性能。在传统的聚类分析算法中，k－均值聚类［8］相较于其它聚类算法有着快速高效的优点，因此本文利用k－均值聚类算法将每一代的外部档案集中的个体划分为k 个部分，并分别得到k个聚类中心作为档案集的代表点。

通常在k－均值算法中k的值是事先给定的，而k值的选定是较难估计的，为简单起见，本文直接将k的大小定为，其中N 为每一代档案集中个体的个数。例如档案集大小设为100时，k值取7。尽管k－均值聚类算法还有着其它的缺点，但考虑到其简单、高效，且相对随机选取效果更好，因此本文最终决定采用该聚类算法来选取代表点。

算法具体描述如下：

步骤1 从档案集中随机选取k 个个体作为初始类中心。

步骤2 计算档案中每个个体到聚类中心点的欧氏距离，并分别将这些个体归类到离它最近的聚类中心所在的类。

步骤3 更新每个类的类中心点，其值为该类中所有个体的平均值。

步骤4 如果聚类中心发生变化，则返回步骤2，否则继续下一步。

步骤5 在档案集中分别找出离这k个聚类中心最近的k个个体，并将之作为聚类结果并保存到环境记忆池中。

3.5 环境相似度计算

当检测环境变化之后需要对环境进行相似度计算，判断新的环境是否相似于之前某一环境以便进行环境恢复操作。环境相似度计算与环境变化检测计算方法类似，不同之处在于计算的是之前某一个环境保存下来的k个代表点的新适应度值与原适应度值间的欧距差其中k指第T’个环境时保存的代表点数目，m 指目标维数，T 指新环境。设定阀值η，如果结果值小于阀值η，则判断第T’个环境与当前新环境类似，在第T’个环境中备份的信息可以恢复到当前外部档案集中，使得算法能够快速适应新的环境。

3.6 对档案集进行交叉处理

由于每一次迭代过程中，当前最优的个体都保存在外部档案集中，且对于采用外部档案策略的优化算法来说外部档案在整个迭代过程起着很重要的作用。然而大多数动态多目标粒子群优化算法对于档案的利用并不充分，仅仅将之用来代替算法模型公式中的全局最优个体。在文献［9］中，实验证明了对Pareto前沿稀疏部分包含的粒子进行模拟二进制交叉有助于增加多样性分布。基于此，本文对外部档案个体进行了交叉处理，这一过程有助于加强解集的多样性并促进档案个体间的信息交流共享，进而改善解集的收敛性。

算法的具体实现如下：首先从外部档案中随机选取两个不同的个体，对这两个个体进行单点交叉处理，通过锦标赛选取新个体中支配关系占优势的一方，若两个新个体互不支配则任意选取其中一个，重复以上过程直到选取的个体数达到档案中的个体数。

尽管对外部档案集的交叉会增加额外的计算量，但由于这一操作可以极大的促进算法的收敛，同时增加种群的多样性，因此这一过程对于算法来说总体是有益的。

3.7 算法描述

基于以上各个模块的设计，基于档案交叉的动态多目标粒子群优化算法ACDMPSO 具体步骤描述如下：

步骤1 在搜索空间内随机产生规模为N 的初始种群P，计算种群个体的适应度值，并更新外部档案集。

步骤2 检测环境变化，如果环境变化程度值大于给定阀值θ，则转入下一步，否则转到步骤6。

步骤3 使用k－均值聚类算法从当前外部档案集中选取k个个体存入记忆池M（T）。

步骤4 从最近的环境开始，寻找与新环境相似的一个环境T’，将记忆池M（T’）中的个体添加到当前外部档案集中。若无相似环境，则直接转到下一步。

步骤5 更新新环境下种群、外部档案个体的适应度值，更新外部档案。

步骤6 对外部档案进行交叉处理，并排除其中被支配的个体。

步骤7 更新种群个体的位置，并计算种群个体的新适应度值。

步骤8 将当前种群中的非支配个体添加到外部档案中，更新维护档案集。

步骤9 判断算法是否满足停止条件，若不满足则迭代数加1，并返回步骤2。

4 仿真实验

为验证本文所提算法的性能，我们将本文算法ACDMPSO 与DNSGA－II算法进行对比实验。鉴于没有DNSGA－II的源代码，在这里我们参照文献 ［1］自己编程实现。测试函数的环境总数T＝8，环境变化强度nt＝10，环境变化频率τt＝50，种群规模为100，ACDMPSO 算法的外部档案容量以及DNSGA－II的优秀个体保存集也均为100，ACDMPSO 中学习因子c1、c2取值为1，环境监测阀值θ为1E－6，环境相似度阀值η为1E－2，DNSGA－II算法的其它参数取自文献 ［1］，算法对每个测试函数独立运行20次。

4.1 测试问题

本文采用FDA系列问题作为测试问题，其中包括多种环境变化类型，双目标、多目标优化问题。具体测试问题见表1。

表1 动态多目标优化的测试问题

4.2 性能度量指标

为测试动态多目标优化问题的相应算法的性能，本文采用以下性能度量准则作为评价标准：

（1）世代距离指标GD （generational distance）［10］

世代距离指标GD 是衡量算法所得Pareto前沿与真实Pareto前沿之间的距离，其公式定义如下式中：K——算法运行次数，T——环境个数，n——个体数，di——算法所得Pareto解中第i个个体的目标函数向量与真实Pareto前沿中最近个体的欧氏距离。GD 描述了算法所得Pareto前沿与真实Pareto前沿的逼近程度，值越小说明算法所得解集越逼近真实Pareto前沿。

（2）空间度量指标SP （spacing）［10］

空间度量指标是度量算法所得Pareto前沿解分布的均匀性，值越小说明解分布得越均匀，其公式定义如下

其中，K、T、n与GD 中的公式定义意义相同，此处的di为算法所得解中第i个个体的目标函数向量与所得解中最近个体的欧氏距离，珚d 是di的均值。

（3）平均C－度量［11］

平均C－度量是度量分析算法所得Pareto前沿对解集的覆盖程度，其公式定义如下

式中：K——计算次数，对C－度量公式描述如下

式中：X、Y——两个不同的Pareto解集，C（X，Y）——集合X 对集合Y 的覆盖程度，若珚C（X，Y）＞珚C（Y，X）则代表解集X 在覆盖范围上优于解集Y。

5 实验结果与分析

5.1 性能评价指标的统计结果对比

表2和表3是ACDMPSO 和DNSGA－II两种算法求解不同DMOPs测试问题时所获得解集的性能评价指标的统计结果。

表2 两种算法对FDA1～FDA5求得的平均C－度量值

表3 两种算法获得解集的GD、SP的均值与标准差

表2显示ACDMPSO 算法所获得的解集与DNSGA－II所获得的解集相互之间的覆盖程度，其中A 表示ACDMP－SO，B表示DNSGA－II。由表中数据可以看出，本文算法所得解集比DNSGA－II算法所得解集的质量好，特别是在双目标优化测试问题FDA1～FDA3中，本文算法所得解在收敛程度上占有极大的优势。

表3统计两种算法对测试问题所得Pareto最优解的世代距离指标GD、空间度量指标SP 值。从表中可以看出，本文算法在整个环境中所得解集的收敛程度及分布均匀程度相比算法DNSGA－II有着不小的优势。

5.2 所得解集的分布图对比

图1中 （a）～ （f）为两种算法在一次运行后所得的8个环境的非劣解的分布图。由于FDA1和FDA2的Pareto最优解集不随时间发生变化，为了能够清楚地看到每一环境的预测点，在图中将FDA1、FDA2中的目标函数f1和f2都分别增加0.2t。由图可以看出，随着环境的变化，两种算法所得Pareto前沿面均能够收敛向真实的Pareto 前沿面。相比较而言本文所提算法所得Pareto前沿面比DNSGA－II得到的Pareto前沿面更宽广，更重要的是本文算法所得非劣解分布均匀程度更好，且对于每一次环境的变化都能跟踪并收敛良好。

图2、图3分别绘制了两种算法在3 个不同时刻求解FDA4、FDA5所获得的解集。这两个测试函数的目标维数m 等于3，其中FDA4的真实Pareto前沿为1／8 球面，球半径固定为1，而FDA5的真实Pareto前沿也为1／8球面，不同的是该球面半径大小随时刻t在1～2之间不断变化。图中显示两种算法均能跟踪不同时刻的Pareto前沿，但主要差别在于，ACDMPSO 所得解集的分布性相比DNSGAII所得解集来说占有极大的优势，从图中可以看出前者所得解集中个体之间保持足够均匀的距离，且整个解集均匀覆盖了真实Pareto前沿面，这提现了改进的欧氏拥挤距离策略所起到的作用。

6 结束语

本文以外部档案为核心，提出了一种基于档案交叉的动态多目标粒子群优化算法。设计了一种改进的拥挤距离档案维护策略以保持解集的均匀性，对外部档案的交叉处理增强了种群的多样性、提高了档案个体间的信息交流，设计了一种环境备份、恢复策略，能够利用少量的过去最优解对新的环境变化做出有效的响应。为了证明算法的有效性，通过对经典的FDA 系列测试问题进行测试，并与DNSGA－II算法作比较，仿真结果表明，新算法在对不同的动态多目标优化函数的求解上非常有效，在多样性、解集均匀性方面都体现出了很好的效果。下一步的研究工作在于保持解集均匀性的同时进一步降低算法的计算复杂度，提高算法运行效率。

图1 两种算法对FDA1～FDA3的求解

图2 两种算法对FDA4在3个不同时刻T 求得的解

图3 两种算法对FDA5在3个不同时刻T 求得的解

［1］Deb K，Karthik S.Dynamic multi－objective optimization and decision－making using modified NSGA－II：A case study on hydro－thermal power scheduling ［C］／／Evolutionary Multi－Criterion Optimization.Springer Berlin Heidelberg，2007：803－817.

［2］SHANG Ronghua，JIAO Licheng，GONG Maoguo，et al.An immune clonal algorithm for dynamic multi－objective optimization ［J］.Journal of Software，2007，18 （11）：2700－2711（in Chinese）.［尚荣华，焦李成，公茂果，等.免疫克隆算法求解动态多目标优化问题 ［J］.软件学报，2007，18 （11）：2700－2711.］

［3］WU Yan，LIU Xiaoxiong，CHI Chengzhi.Predictive multiobjective genetic algorithm for dynamic multiobjective optimization problems［J］.Control and Decision，2013，28 （5）：677－682（in Chinese）.［武燕，刘小雄，池程芝.动态多目标优化的预测遗传算法 ［J］.控制与决策，2013，28 （5）：677－682.］

［4］Koo W T，Goh C K，Tan K C.A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment［J］.Memetic Computing，2010，2 （2）：87－110.

［5］HU Chengyu，YAO Hong，YAN Xuesong.Multiple particle swarms coevolutionary algorithm for dynamic multi－objective optimization problems and its application ［J］.Journal of Computer Research and Development，2013，50 （6）：1313－1323（in Chinese）.［胡成玉，姚宏，颜雪松.基于多粒子群协同的动态多目标优化算法及应用 ［J］.计算机研究与发展，2013，50 （6）：1313－1323.］

［6］HU Wang，LI Zhishu.Simpler and more effective particle swarm optimization algorithm ［J］.Journal of Software，2007，18 （4）：861－868 （in Chinese）.［胡旺，李志蜀.一种更简化而高效的粒子群优化算法 ［J］.软件学报，2007，18 （4）：861－868.］

［7］CHEN Shanlong，ZHANG Zhuhong.Dynamic multi－objective optimization immune algorithm based on immune mechanisms［J］.Journal of Guizhou University（Natural Science Edition），2007，24 （5）：487－492 （in Chinese）.［陈善龙，张著洪.基于免疫机制的动态多目标优化免疫算法 ［J］.贵州大学学报：自然科学版，2007，24 （5）：487－492.］

［8］HAN Xiaohong，HU Yu.Research of K－means algorithm［J］.Journal of Taiyuan University of Technology，2009，40（3）：236－239 （in Chinese）. ［韩晓红，胡彧.K－means聚类算法 的 研 究 ［J］.太 原 理 工 大 学 学 报，2009，40 （3）：236－239.］

［9］LIU Yanmin，NIU Ben，ZHAO Qingzhen.Multi－objective particle swarm optimization based on crossover and mutation［J］.Journal of Computer Applications，2011，31 （1）：82－84（in Chinese）.［刘衍民，牛奔，赵庆祯.基于交叉和变异的多目标粒子群算法 ［J］.计算机应用，2011，31 （1）：82－84.］

［10］LIU Chun’an.A dynamic multi－objective optimization evolutionary algorithm based on estimation of core distribution ［J］.Journal of Shandong University （Engineering Science Edition），2011，41 （1）：167－172 （in Chinese）. ［刘淳安.基于核分布估计的动态多目标优化进化算法 ［J］.山东大学学报：工学版，2011，41 （1）：167－172.］

［11］QIAN Shuqu，WU Huihong.Dynamic multi－objective immune algorithm and its application ［J］.Computer Engineering，2012，38 （10）：171－174 （in Chinese）.［钱淑渠，武慧虹.动态多目标免疫算法及其应用 ［J］.计算机工程，2012，38 （10）：171－174.］