一个处理CMOPs的将多个约束处理方法集成的方法

Constrained multi-objective optimization algorithm with an ensemble of constraint handling methods

1.摘要

每种约束处理方法不可能在每个问题上都优于其他约束处理方法，同时在一个问题的不同时期也可能选择不同的约束处理方法更好。基于此，本文提出了一个约束处理方法集（ECHM）来处理约束。实验结果表明，ECHM总体性能优于单一约束处理方法。最后需要一提的是，使用了多目标差分进化算法进行优化。

2.介绍

这部分文章简单介绍了CMOPs，并提出怎么处理约束和处理不可行解是其核心问题。

3.约束处理方法

约束的方法分为四类：①保持解决方案的可行性、②惩罚函数、③分离可行和不可行的解决方案以及④混合方法。
在解决约束问题时，可以遇到以下三种情况之一：

1. 没有可行解的阶段
2. 至少一个可行解的阶段
3. 混在一起的父子代比下一代开始时的父代有更多可行解的阶段
   不同约束处理技术之间的区别在于如何在整个三个搜索阶段处理不可行的个体。
   考虑父-子群的组合，约束问题的搜索过程可分为三个阶段(Wang，2008)：（1）没有可行的解。 （2）至少一个可行的解决办法。 （3）与下一代父母群体的规模相比，结合的后代父母群体有更可行的解决办法。 不同约束处理技术之间的区别在于如何在整个三个搜索阶段处理不可行的个体。

3.1自适应罚函数法(SP)
Woldesenbet和Tessema（2007）提出了一个自适应惩罚函数。 该方法跟踪人口中可行个体的数量，以确定对不可行个体的惩罚程度。 自适应惩罚函数使用修正的目标函数值，而不是使用原始的目标值。而修正目标值有距离测度和自适应惩罚两个组成部分。这里可以去看我写的原文详细学习，这里就不粗略介绍了。

3.2可行解优先(SF)
适应度计算公式为：

其中，其中fmworst是所有可行解在第m个目标值上的最大值，v(X)是总体约束违反。如果当前总体中没有可行解，则fmworst=0。
不难发现，通过该方式计算的适应度，可行解永远优于不可行解。若比较双方都是可行解，则比较其目标值；若比较双方都是不可行解，则比较约束违反值。

3.3 ε约束(EC)
ε约束处理技术最早是由Takahama提出的(2005)。 其基本思想类似于可行解的优越性，其不同之处在于使用ε参数在搜索过程的早期阶段放松约束违反。 这种方法包括了更多在进化的早期阶段在种群中不可行的解，因为此时约束阈值不是0而是 ε值，只有超过阈值的才被认为是不可行解。 ε值随着生成计数器k更新，直到k=Tc。 在Tc代后，ε值设置为零，此时EC约束处理效果等同于SF。

v(Xθ)表示第θ个个体的约束违反值
3.4分析上述3个算法
在解决约束问题时，可以遇到以下三种情况之一：

1. 没有可行解的阶段
2. 至少一个可行解的阶段
3. 混在一起的父子代比下一代开始时的父代有更多可行解的阶段

SF

SF法对可行解的排序优于不可行解。 两个不可行的解仅基于它们的总体约束违规进行比较，而两个可行解仅基于它们的目标函数值进行比较。
因此，SF在阶段1中，从组合的父代和子代种群中选择总体约束违反更低的不可行解。 在阶段2中，首先选择所有可行的，然后选择约束违反最低的不可行的。 在阶段3中，只选择带有最好目标值的可行解。

SP

SP方法总是根据总体约束违反和目标值确定的值来选择个体。 因此，在阶段3中，可以选择具有较低总体约束违反和较高适应度的个体。

EC

ε约束(EC)方法选择类似于SF，但在EC中，如果其总体约束违反小于ε(K)，则认为解是可行的。

4.差分进化介绍

使用差分进化优化多目标问题的细节可以参考我的另一篇文献阅读：Multi-Objective Optimization with Modified Pareto Differential Evolution，本文只是在该基础上加入了约束处理。
本文使用到的变异向量Vp：

本文使用到的试验向量Up,i：

受约束的多目标差分进化算法流程图如下：

其中,方框部分进行会约束处理（处理方法就可以用前面提到的3种约束处理方法），生成新的适应度值，种群会根据新的适应度的值进行精英选择生成下一代。

5.使用约束处理方法集的差分算法

算法的具体流程图如下：

每个约束处理方法都有对应的种群。 每个种群根据差分算法产生其自己的后代种群。 对于三个后代种群中的每个后代，都计算目标值、约束函数值和总体约束违反。 将三个子代种群组合并同时根据三种CHMs进行不同的适应度修改过程。 在适应度修改过程之后，每个子代种群与各自的亲本种群相结合。 因此，目标和约束函数评估只执行一次每后代，而适应度修改执行三次根据CHMS。具体可以看上面的流程图更清楚。

6.实验结果

方法集的种群大小设置为50，单个约束处理方法设置为50和150。 最大外部存档大小设置为100，其他参数设定如下。

进行了7个不同方法的比较实验。

实验指标

实验结果

popsize=50


popsize=150

从表中的结果可以看出，约束处理方法集合的性能类似于单个约束处理方法或优于单个约束处理方法。 从最后一行显示的排名总和可以看出，集成约束处理方法相对于R指标来说优于所有单个约束处理方法。
数值−1、0、1表示所提出的ECHM在统计上优于、等于和劣于单一约束处理方法。 从结果来看，所提出的ECHM的性能要么更好，要么类似于所有三种单一约束处理方法。

7.总结

由于进化算法本质上是随机的，搜索过程在搜索过程中在不同的点上通过不同的阶段。 不同的约束处理方法可以在搜索过程的不同阶段有效。 约束处理方法的集成将为所有种群带来最合适的技术生成的最佳解决方案。 这样，搜索过程将继续使用最佳技术生成后代。 因此，与单个CHM相比，ECHM具有在不同问题上表现良好的潜力。 实验结果表明，ECHM总体性能优于所有三种单一约束处理方法。

返回受约束的多目标优化问题优秀论文及总结目录