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

《基于模型的混合多目标算法的研究.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于模型的混合多目标算法的研究提纲研究背景及意义国内外研究现状模型多目标算法（RM-MEDA，MMEA）基于模型的混合多目标算法实验结果及分析总结与展望研究背景及意义传统多目标算法如NSGA-Ⅱ具有较好的全局搜索能力，而在算法后期由于采用交叉、变异算子使得较好解容易丢失，造成收敛速度过慢；模型多目标具有较好的局部搜索能力，而如果在算法初期种群还未形成一定规则的时候就对种群进行建模操作，可能会造成算法陷入局部最优。因此，本文将两种算法结合，充分发挥各自的优势，具有一定的研究意义。国内外研究现状1967年，Rosenberg在其博士论文中首次

2、提出采用遗传搜索的方法来求解多目标的优化问题。1984年以来，研究者们针对不同的实际问题，提出了各式各样的多目标进化算法（MOEA）。比较突出的就是Deb等提出的NSGA-Ⅱ以及Zitzler等提出的SPEA2。虽然NSGA-Ⅱ、SPEA2已经获得了很大的成功，但是它们都是采用交叉、变异算子进行子代繁殖，而忽略了这些算子对算法性能的影响。分布估计算法（EDA）采用统计学的方法对当前种群进行分析，建立一个概率模型，并从中取样产生新的子代。国内外研究现状（续）2005年，周爱民等首次提出了模型多目标优化算法用于解决两个目标问题。。2007年张

3、青富等提出RegularityModel-BasedMulti-objectiveEstimationofDistributionAlgorithm(RM-MEDA)。2008年周爱民等人又将多目标优化问题分为两类,并且提出解决第二类问题的MMEA算法。模型多目标算法—RM-MEDA多目标相关概念：一般MOP由n个决策变量参数，m个目标以及约束条件组成，目标函数、约束条件与决策变量之间是函数关系。最优化目标如下：minst.多目标优化问题的解就是寻求一个，使得在满足约束条件的情况下达到最优。若不存在一个使得，且至少一个是严格的不等式，则此

4、时的就称为多目标优化问题的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个目标的多目标优

5、化问题的Pareto解集（即ParetoSet，PS）在决策空间的分布是一个分段、连续的(m-1)维的流形。对于两个目标的优化问题，它的解集分布是一维流形，即主曲线。对于三个目标的优化问题，它的解集分布是一个二维的主曲面。RM-MEDA（续）算法基本思想：其中：是在流形上随机产生的点，，是恒等矩阵，RM-MEDA（续）算法基本流程：RM-MEDA（续）建模过程：1、利用LocalPCA聚类算法将种群划分为K个聚类2、对每一个聚类，计算它的数据点的平均值，以及中样本点的协方差矩阵，令为第个聚类第个主成分的方向（即聚类中所有个体解的协方差矩阵

6、的第大特征值对应的特征向量）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时，计算在种群中所有个体的拥挤度

7、距离，将拥挤度距离最小的个体从种群里面移除。模型多目标算法—MMEAMMEA算法是针对第二类问题提出的，第二类问题指的是目标空间的PF分布是一个(m-1)-D的流形，而决策空间的PS分布是一个高于(m-1)-D的流形,第二类问题较第一类问题更为复杂。MMEA算法是通过对目标空间PF的逼近来同时对决策空间PS进行逼近的。MMEAMMEA算法基本流程：设种群Pop的规模大小为N，演化代数为t，每个个体对应的目标函数值为算法的流程如下：1、初始化：随机产生一个初始种群P并计算P中个体的目标函数值；2、建立模型：为当前种群建立一个概率模型模拟种群

8、中P中个体的分布；3、子代繁殖：从步骤2的模型中取样产生新解的集合Q，并计算Q中个体的目标函数值；4、选择：从子代种群Q和父代种群P中产生N个解代替P中的所有个体；5、结束条件：如果结束条件满