基于模型的混合多目标算法的研究

基于模型的混合多目标算法的研究提纲研究背景及意义国内外研究现状模型多目标算法（RM-MEDA，MMEA）基于模型的混合多目标算法实验结果及分析总结与展望研究背景及意义传统多目标算法如NSGA-Ⅱ具有较好的全局搜索能力，而在算法后期由于采用交叉、变异算子使得较好解容易丢失，造成收敛速度过慢；模型多目标具有较好的局部搜索能力，而如果在算法初期种群还未形成一定规则的时候就对种群进行建模操作，可能会造成算法陷入局部最优。因此，本文将两种算法结合，充分发挥各自的优势，具有一定的研究意义。国内外研究现状1967年，Rosenberg在其博士论文中首次提出采用遗传搜索的方法来求解多目标的优化问题。1984年以来，研究者们针对不同的实际问题，提出了各式各样的多目标进化算法（MOEA）。比较突出的就是Deb等提出的NSGA-Ⅱ以及Zitzler等提出的SPEA2。虽然NSGA-Ⅱ、SPEA2已经获得了很大的成功，但是它们都是采用交叉、变异算子进行子代繁殖，而忽略了这些算子对算法性能的影响。分布估计算法（EDA）采用统计学的方法对当前种群进行分析，建立一个概率模型，并从中取样产生新的子代。国内外研究现状（续）2005年，周爱民等首次提出了模型多目标优化算法用于解决两个目标问题。。2007年张青富等提出RegularityModel-BasedMulti-objectiveEstimationofDistributionAlgorithm(RM-MEDA)。2008年周爱民等人又将多目标优化问题分为两类,并且提出解决第二类问题的MMEA算法。模型多目标算法—RM-MEDA多目标相关概念：

一般MOP由n个决策变量参数，m个目标以及约束条件组成，目标函数、约束条件与决策变量之间是函数关系。最优化目标如下：

minst.多目标优化问题的解就是寻求一个，使得在满足约束条件的情况下达到最优。

若不存在一个使得，且至少一个是严格的不等式，则此时的就称为多目标优化问题的Pareto最优解。将所有满足Pareto最优解定义的组成的集合称为PS，而PS对应的目标空间的解集即为PF。

模型多目标算法—RM-MEDA个体支配关系：设p和q是进化群体Pop中的任意两个不同的个体，称p支配q，则必须满足下列条件：1、对所有的子目标，p不比q差，即fk(p)≤fk(q)(k=1,2,…m)。2、至少存在一个子目标，使得p比q好，即严格的不等式成立。其中：m为子目标的个数。RM-MEDA算法理论基础：

在光滑的条件下根据Karush-Kuhn-Tucker条件可以得出，一个连续的m个目标的多目标优化问题的Pareto解集（即ParetoSet，PS）在决策空间的分布是一个分段、连续的(m-1)维的流形。对于两个目标的优化问题，它的解集分布是一维流形，即主曲线。对于三个目标的优化问题，它的解集分布是一个二维的主曲面。RM-MEDA（续）算法基本思想：其中：是在流形

上随机产生的点，

，是恒等矩阵，RM-MEDA（续）算法基本流程：RM-MEDA（续）建模过程：

1、利用LocalPCA聚类算法将种群划分为K个聚类

2、对每一个聚类，计算它的数据点的平均值，以及中样本点的协方差矩阵，令为第个聚类第个主成分的方向（即聚类中所有个体解的协方差矩阵的第大特征值对应的特征向量）3、计算个体在各主成分方向上的范围：令4、计算：5、令为聚类

中样本点的协方差矩阵的第i大特征值，则RM-MEDA（续）子代繁殖：

1、随机产生一个整数

按照概率

2、随机产生一个新解，按照公式

，其中

是个产生于

的数据点，为一个服从

的噪声向量。

3、重复步骤1，步骤2直到产生N个新解。RM-MEDA（续）选择：

1、利用快速非支配排序算法将种群

划分为不同的前沿

，令Pop(t+1)=，k=0；2、执行下列步骤直到种群Pop(t+1)中的个体数目超过N，,

3、种群Pop(t+1)中的个体数目超过N时，计算在种群

中所有个体的拥挤度距离，将拥挤度距离最小的个体从种群里面移除。模型多目标算法—MMEAMMEA算法是针对第二类问题提出的，第二类问题指的是目标空间的PF分布是一个(m-1)-D的流形，而决策空间的PS分布是一个高于(m-1)-D的流形,第二类问题较第一类问题更为复杂。MMEA算法是通过对目标空间PF的逼近来同时对决策空间PS进行逼近的。

MMEAMMEA算法基本流程：

设种群Pop的规模大小为N，演化代数为t，每个个体对应的目标函数值为

算法的流程如下：1、初始化：随机产生一个初始种群P并计算P中个体的目标函数值；2、建立模型：为当前种群建立一个概率模型模拟种群中P中个体的分布；3、子代繁殖：从步骤2的模型中取样产生新解的集合Q，并计算Q中个体

的目标函数值；4、选择：从子代种群Q和父代种群P中产生N个解代替P中的所有个体；5、结束条件：如果结束条件满足，返回在种群P中的所有解和其对应的目标函数值，否则返回步骤2。MMEA（续）建模过程：1、建立一个理想的PF(UtopianPF，UPF)：基于当前种群P的信息，在目标空间建立一个(m-1)-D的单形作为UPF。1.1、从种群P的非支配解集中选取在第i个目标函数

上有最大值的m个个体1.2、初始化单形S为目标空间的顶点为

的m-1维流形，将S沿其垂直方向移动到一个位置，使得：(a)S中没有一个点被P中的个体支配；(b)移动的距离尽可能的小；1.3、令为移动后的单形S的顶点，计算S的中心：然后通过移动S的顶点来扩展S，MMEA（续）2、计算子种群K，3、在建立的UPF上，均匀的选取K个点

作为参考点，用来将种群划分为K个聚类。4、主成分分析(PCA)及建模：

即保持80%的主成分，因为PS是比m-1维更高的流形，但不知道它具体多少维，所以不能保持所有的主成分。

基于模型的混合多目标算法算法提出的依据：基于模型的混合多目标算法（续）1代50代100代150代200代250代基于模型的混合多目标算法（续）基本流程：实验结果及分析度量准则：收敛性度量：多样性度量：IGD度量：第一类问题的实验结果及分析第一类问题的实验结果及分析第一类问题的实验结果及分析第一类问题的实验结果及分析第一类问题的实验结果及分析ZDT1实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析ZDT2实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析ZDT3实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析ZDT6实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析ZDT1.1实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析ZDT2.1实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析ZDT1.2实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析ZDT2.2实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析DTLZ2实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析DTLZ2.1实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一类问题的实验结果及分析DTLZ2.2实验结果图示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA针对标准的ZDT系列函数以及DTLZ2函数，NSGA-Ⅱ的效果要明显优于模型多目标算法，由于它们决策空间的PS分布相对简单，弱化了模型多目标算法的优势，同时，如果从算法开始就对种群进行建模操作，当种群的分布还未呈现出一定的规则时就进行建模，不利于子代的搜索，可能会造成收敛不到全局的最优解，而陷入局部最优。而将两者结合后的算法虽略差于NSGA-Ⅱ，但是却要明显优于两种模型多目标算法。

第一类问题的实验结果及分析针对改进的ZDT函数以及DTLZ2函数，由于它们的PS分布相对复杂，这时NSGA-Ⅱ算法就显得无能为力，而模型多目标算法的优势也渐渐显现出来。从实验数据中也可以看出，结合后的算法与模型多目标算法相差不大，而且在某些方面要更优于模型多目标算法。

为什么结合后的算法没有达到预期的效果呢？这主要是算法阶段的划分还不明确，何时采用建模的方式产生子代也有待进一步研究。第一类问题的实验结果及分析第二类问题的实验结果及分析第二类问题的实验结果及分析F3实验结果图示：

NSGA-ⅡMMEAN+MMEA