基于种群分类的动态约束多目标进化算法

许 峰，季洪霄

（安徽理工大学理学院，安徽 淮南232001）

动态优化问题（Dynamic Optimization Problem，DOP）的特点是目标函数会随着时间（环境）动态变化。尽管动态进化算法的研究最早可追溯到1966年［1］，但直到20世纪80年代中期，动态进化算法的研究才逐渐形成热点［2-3］。

相比单目标动态优化问题，动态多目标优化问题（Dynamic Multiobjective Optimization Problem，DMOP）的早期研究并不多。2000年后，DMOP日益受到众多学者的重视，取得了一系列成果。Marco等［4］提出了一种邻域搜索算法；Deb等［5］在 NSGAII基础上提出了动态多目标进化算法DNSGAII；Iason等［6］提出了一种基于向前预测的动态多目标进化算法；Zhang等［7］提出了动态免疫多目标进化算法；Amato等［8］提出了基于人工生命的动态多目标进化算法；Bingul等［9］提出了自适应动态多目标进化算法。另外，动态多目标进化算法测试函数的研究成果也相继出现［10-11］。

动态约束多目标优化问题（Dynamic Constrained Multiobjective Optimization Problem，DCMOP）的研究难度较大，相关成果并不多［12-13］。本文将聚类分析引入动态约束多目标进化算法，用以处理约束条件，并对算法进行了性能测试。

1 多目标动态优化问题的相关概念

1．1 多目标动态优化问题及其最优解

记V0，VF和W 分别为n0维，nF维和mW维向量空间，则动态多目标优化问题可表述为

其中，g（v0，vF）≤0，h（v0，vF）＝0分别为不等式和等式约束，f：V0×VF→W 是目标向量函数，fi（v0，vF）为第i个子目标函数。

若令V是n维决策变量空间，W 是m维目标向量空间，参数VF是取值于实值空间T的参数，则（1）可描述为

其中，g（v，t）≤0，h（v，t）＝0分别为不等式和等式约束，f：V×T→W 是目标向量函数。

相比多目标静态优化问题而言，多目标动态优化问题的Pareto最优解和最优前沿不是固定的，而是可能随时间动态变化的。

1．2 最优解集的评价标准

（1）代间距离（Generation Distance，GD）

其中，n为最优前沿PFknown包含的向量个数，di为PFknown中的向量到最优前沿PFtrue的最短距离。

GD指标反映了计算最优前沿对理论最优前沿的近似程度，即算法的收敛性。

（2）错误率（Error Ration，ER）

其中，n为PFknown中的向量个数，且PFknown＝｛X1，X2，…，Xn｝，ei定义如下：

ER描述了PFknown对PFtrue的覆盖程度，即最优解集的分布性。

（3）分散性（Spaing，SP）

其中，n和di与代间距离中的定义相同。

显然，分散性就是di的标准差，它反映了Pareto解集的均匀性。

2 群体划分动态约束多目标进化算法

2．1 划分群体

2．1．1 按群体的可行性划分

由于在进化初期可行解的数量较少，此时进行Pareto运算意义不大，还会导致算法效率的降低。因此，在划分群体时，首先要将其划分为可行群体和非可行群体，提高Pareto运算的效率。

2．1．2 按Pareto性能划分

将群体划分为可行和不可行2个群体后，再对可行群体中的个体进行Pareto运算，找出所有的Pareto最优解。这样，就将可行群体划分为可行非Pareto群体与可行Pareto群体。

2．1．3 对可行Pareto群体进行聚类

由于进化算法并不限制相同或相似个体的数量，因此在算法的后期，可行Pareto群体中有可能会出现大量相同或类似的个体，从而影响解的分布性和均匀性。为了解决此问题，可以对可行Pareto群体进行聚类，即在每个聚类群体中随机挑选一个个体，将它们合并为一个群体。

通过上述4步划分，种群最终被划分为4个子种群：不可行子种群、非Pareto子种群、非聚类Pareto子种群和聚类Pareto子种群。

2．2 群体的R适应度

显然，在上述4类子种群中，不可行子种群的适应能力最差，依次递增，所以可以根据下列大小关系给上述4类子种群赋以R适应度：

R（不可行子种群）≪R（可行非Pareto子种群）≤R（非聚类Pareto子种群）≪R（聚类Pareto子种群）

除前几代外，选择操作均根据R适应度进行。

2．3 算法步骤

（1）对时间区间进行等距分割，记不同环境为t1，…，ts，令t＝t1；

（2）在环境ti（i＝1，2，…，s），随机产生初始种群，令k＝0；

（7）对群体进行基本遗传操作（比例选择、单点交叉、均匀变异）运算；

（8）若满足停止条件，输出优化结果，算法终止；否则转（3）。

3 算法性能测试

下面分别用种群分类动态多目标进化算法（IDMEA）、常规动态多目标进化算法（DMEA）动态NSGAII算法对2个动态约束多目标测试函数DMOP1和DMOP2进行数值优化计算，并利用2个性能度量指标函数C-measure和U-measure对算法进行定量评价。

（1）DMOP1测试函数

该函数的Pareto最优解集不随时间变化，但Pareto最优前端随时间变化。

（2）DMOP2测试函数

（2）DMOP2测试函数该函数的Pareto最优前端随时间变化。

数值实验参数为：群体规模为100，进化代数为50，交叉概率为0．9，变异概率为0．1。

图1～图4分别给出了由IDMEA和DMEA计算出的DMOP1和DMOP2当t＝0．25和0．5时的Perato最优前端。

为了消除算法的随机性，下面再根据算法的性能统计指标对IDMEA进行测评［14］。

图1 t＝0．25时DMOP 1的Perato最优前端

图2 t＝0．50时DMOP 1的Perato最优前端

图3 t＝0．25时DMOP 2的Perato最优前端

可以利用性能度量指标函数C-measure来进行解的收敛性评测，利用性能度量指标函数U-measure来进行解的分布性和均匀性评测。

图5中给出了DNSGAII、DMEA和IDMEA（分别记为1，2，3）3种算法对DMOP1和DMOP2在不同环境下C-measure值的统计盒图。其中，第1行前2个图为DMOP1在t＝0．25时的C-measure值盒图，后2个图为DMOP1在t＝0．50时的C-measure值盒图；第2行前2个图为DMOP2在t＝0．25时的C-measure值盒图，后2个图为DMOP2在t＝0．50时的C-measure值盒图。图中的C（i，j）表示第i种算法和第j种算法对同一问题分别求得的Pareto最优解集Ai和Bj的C-measure值。

图4 t＝0．50时DMOP 2的Perato最优前端

图5 3种算法对DMOP1和DMOP2在t＝0．25，0．50时C-measure值的统计盒图

图6 3种算法对DMOP1和DMOP2在t＝0．25，0．50时U-measure值的统计盒图

图6中给出了DNSGAII、DMEA和IDMEA这3种算法对DMOP1和DMOP2在不同环境下U-measure值的统计盒图。其中，第1行分别为DMOP1在t＝0．25和t＝0．50时的U-measure值盒图；第2行分别为DMOP2在t＝0．25和t＝0．50时的U-measure值盒图。

从图1～图4中可以很清楚地看出，IDMEA方法得到的Perato最优解不仅数量比较多，而且分布较为均匀。

从图5中可以看出，C（3，i）＞C（i，3）（i＝1，2），这意味着IDMEA在不同环境下对不同测试函数求得的Perato最优解的收敛性比其它2种算法所得的结果更好。

从图6中可以看出，IDMEA在不同环境下对不同测试函数求得的Perato最优解的U-measure值小于其它2种算法所得的结果，即算法IDMEA在不同环境下对不同测试函数求得的Perato最优解在Perato最优前端上的分布更广泛、均匀。

4 结语

本文将聚类分析引入动态约束多目标进化算法，改进了约束条件的处理机制，数值实验结果和统计指标表明：与常规动态约束多目标进化算法相比，改进后算法具有较好的分布性。

需要指出的是，动态多目标进化算法与粒子群算法、蚁群算法、人工免疫系统、分布估计算法等均为近年来出现的新型进化范例，理论体系尚不完善，分布性和收敛性等关键理论问题有待进一步研究。本文对2个典型测试函数，基于对比实验研究了新算法的性能。由于如何衡量多次优化结果的一致性和稳定性等问题目前尚未解决，所以世代距离、错误率和分散性3个量化评价指标并不能完全反映多目标优化算法的性能，这在一定程度上影响了本文研究结论的普遍性。

［1］Fogel L J，Owens A J，Walsh M J．ArtificialIntelligence through Simulation Evolution［M］．New York：John Wiley，1966．

［2］Goldberg D E，Smith R E．Non-stationaryFunction Optimization Using Genetic Algorithms with Dominance and Diploids［C］．Proc．of the 2nd Int Conf．on Genetic Algorithms，Grefenstette J J（Eds．），1987：59-68．

［3］Krishnakumar K．Micro-geneticAlgorithms for Stationary and Non-stationary Function Optimization［J］．SPIE，Intelligent Control and Adaptive Systems，1989，289-296．

［4］Marco F，Deb K，Amato P．Dynamic Multiobjective Optimization Problems：Test Cases，Approximation，and Applications［C］．Proc．of the Evolutionary Multiobjective Optimization International Conference，Faro，Portugal，2003：311-326．

［5］Deb K，Bhadkara U R N，Karthik S．Dynamic Nultiobjective Optimization and Decision-making Using Modified NSGA-II：A Case on Hydro-thermal Power Scheduling［C］．Proc．of the 4th International Conference on Evolutionary Multi-Criterion Optimization，INCS 4403，Springer-Verlag，Matsushima，Japan，2007：803-817．

［6］Iason H，David W．Dynamic Multiobjective Optimization with Evolutionary Algorithms：A Forward-looking Approach［C］．Proc．of the GECCO'06，Washington USA，2006：1201-1208．

［7］Zhang Z H．MultiobjectiveOptimization Immune Algorithm in Dynamic Environment and Its Application to Greenhouse Control［J］．Applied Soft Computing，2008：959-971．

［8］Amato P，Farina M．An Life-Inspired Evolutionary Algorithm for Dynamic Multiobjective Optimization Problems［J］．Advances in Soft Computing，2005：113-125．

［9］Bingul Z，Sekmen A，Zein-Sabatto S．Adaptive Genetic Algorithms Applied to Dynamic Multi-objective Problems［C］．Proceedings of the Artificial Neural Networks in Engineering Conference（ANNIE'2000），Cihan H D，Anna L B，Joydeep G（EDs．）New York，ASME Press，2000：273-278．

［10］Jin Y C，Sendhoff B．Constructing Dynamic Optimization Test Problems Using the Multiobjective Optimization Concept．Proc．of the Evolutionary Workshops 2004，LNCS 3005，Springer-Verlag，Heidelberg，Germany，2004：525-536．

［11］Farina M，Deb K，Amato P．Dynamic Multi-objective Optimization Problems：Test Cases，Approximation，and Applications［J］．IEEE Transactions on Evolutionary Computation，2004，8（5）：311-326．

［12］Mei Y，Tang K，Yao X．Capacitated Arc Routing Problem in Uncertain Environments［C］．Proc．of the 2010 IEEE Congress on Evolutionary Computation（CEC2010），Barcelona，Spain，2010，18-23．

［13］刘淳安．动态多目标优化进化算法及其应用［M］．北京：科学出版社，2011．

［14］杨亚强，刘淳安．一类带约束动态多目标优化问题的进化算法［J］．计算机工程与应用，2012，48（21）：45-48．