最新高维多目标进化算法总结

高维多目标进化算法二、文献选读内容分析及思考（一）Borg算法Borg算法是基于ε-MOEA算法（Deb，2003）的一种全新改进算法[32]，下面将从创新点、原理、算法流程和启发思考四方面进行阐述。1.创新点1）在ε支配关系的基础上提出ε盒支配的概念，具有能同时保证算法收敛性与多样性的特点。2）提出了ε归档进程，能提高算法计算效率和防止早熟。3）种群大小的自适应调整。4）交叉算子的自适应选择。由于处理实际问题时，是不知道目标函数具有什么特性，前沿面如何，在具有多个交叉算子的池子里，根据进程反馈，选择不同的交叉算子，使产生的后代具有更好的特性针对要研究的问题。2.Borg算法原理1）ε盒支配：通过对目标空间向量的每一维除以一个较小的ε，然后取整后进行pareto支配比较。这样的支配关系达到的效果是把目标空间划分成以ε为边长的网格（2目标时），当点处于不同的网格时，按pareto支配关系比较；当处于同一网格时，比较哪个点距离中心点（网格最左下角）最近。这样一来，网格内都只有一个点。2）ε归档进程如图1所示，黑点表示已经归档的，想要添加到档案集的新解用×表示，阴影表示归档解支配的区域。当新解的性能提升量超过阈值ε才属于ε归档进程。比如解1、解2加入归档集属于ε归档进程，解3加入归档集就不属于ε归档进程。图1ε支配网格在这个过程中设置了一个参数c，表示每一代中加入归档集解得个数，每隔一定迭代次数检测c有没有增加，如果没有增加表明算法停滞，重启机制启动。3）重启自适应种群大小：重启后的种群大小是根据归档集的大小设置。γ表示种群大小与归档集大小的比值，这个值也用于第二步中，如果γ值没超过1.25，重启机制也启动。启动后，γ人为设定为固定值，种群被清空，填充归档集的所有个体，不足的个体是随机选取归档集中个体变异所得。与之相匹配的锦标赛比较集大小是归档集大小乘以固定比值τ。4）交叉算子的自适应选择摒弃以往采用单一的交叉算子，采用包含各类交叉算子的池子，比如有K种交叉算子，选择概率最开始是相等的，设n表示各类交叉算子产生的后代属于ε归档进程所得个数，个数越多，选取相应交叉算子的概率就越大，逐渐趋于选择解决未知现实问题的交叉算子。3.Borg算法总体流程通过交叉算子的自适应选择选择一种交叉算子，假设所选交叉算子需要K个父代，1个父代在归档集中按均匀分布选择，K-1个父代从种群中按锦标赛选择（大小按上述第3步中计算），交叉产生一个后代，如果这个后代pareto支配种群中一个或多个个体，则随机的取代一个；如果被种群中的任一个体支配，则不能加入种群；如果互不支配，也是随机的取代种群中的一个。而加入归档集，是按照上述第2步实施的。如此循环一定代数之后，看达没达到第3步重启的条件，达到则重启过程开始，直至满足终止条件。4.思考1）ε盒支配时，同一网格内的点只是比较离中心点距离最近的，这就有一个不足，最近的不一定是非支配解，离的远的点有可能还支配它，我觉得还需要比较一下哪个解优的目标维数多。2）设计一种云交叉算子，加入到交叉算子的池子里，或是参数控制云交叉算子替换其中的能达到类似效果的几种算子，便于统一。（二）基于模糊支配的高维多目标进化算法1.算法简介基于模糊支配的高维多目标进化算法[33]是对模糊支配关系的一种改进，2005年M.Farina首次提出的模糊支配，其隶属函数是一条正态分布函数，如图2所示，而此文的隶属函数是一条半正态分布函数，表达的概念更加清晰。图2正态隶属函数对于最小化问题，归一化后的解A（a1,a2,...,aM），B（b1,b2,...,bM）如果目标向量的某一维上的差量（ai-bi）达到-1，则ai好于bi的程度为1，即pareto支配关系下ai支配bi；如果差量（ai-bi）是1，则pareto支配关系下bi支配ai。A模糊支配B程度为每一维差量映射下的隶属度之积，与种群中其他解进行比较，所得隶属度相加即为A解在整个中群众的性能好坏程度，相当于NSGA-II中的非支配排序，只是这里的等级程度更加细分，然后还得设置一个阈值α，即模糊支配隶属度达到多少才能是最优解，也就是NSGA-II中的非支配排序等级为1的解。设定这个值是关键，此文献也对这个值得选取进行了实验说明，针对不同的问题选取不同的值，但是还没能达到根据问题特性自适应调整。2.思考1）既然隶属度函数不是一成不变的，想用云模型确定隶属度，借鉴张国英《高维云模型及其在多属性评价中的应用》构造一M维云模型，它的作用是输入M维差量映射为一维的模糊支配隶属度u，无需像上文中求出每一维隶属度再相乘。2）由于阈值α不好确定，可不可以根据归档集的大小取前N个，找到使个体数量大于等于N的u值为α。（三）基于网格支配的高维多目标进化算法GrEA[34]也是针对ε-MOEA算法进行改进的，作者认为ε-MOEA算法中的网格划分是基于个体的，如果个体分配不均匀，也就不能得到分布性好的最优前沿，而且网格的大小也不能随着目标空间的特性而自适应调整。1.支配关系创新grid-dominance，这种支配关系是基于空间区域划分网格，就是在当代种群中找出每一个目标函数上的最大值与最小值（下图上行），然后根据这两个值计算出这个目标函数的网格上下界值（下图下行）。人为设定每一个目标函数需划分的段数div,是一个固定的值，这样就使得收敛性与多样性的要求随着算法进程自适应调整，比如说刚开始时目标空间的个体分布比较广，就需要大的网格来选择个体，随着算法深入，个体更加集中于Pareto前沿区域，就需要小的网格区分个体，更加强调个体的多样性，因此这样动态的网格划分更能体现算法的进程。另外，ε-支配强调个体生死，只有非支配才能加入归档集；而griddominance不同，它更强调个体的先后，非支配个体只是先于支配个体进入归档集，支配个体还是有机会加入归档集，这在一定程度上保留了边界点，而ε-MOEA算法会丢失边界点。图3网格分段示意图2.适应度值指派创新本文提出了适应度值指派的三个指标gridranking(GR)、gridcrowdingdistance(GCD)和gridcoordinatepointdistance(GCPD)，GR和GCPD是收敛性评价指标，GCD是多样性评价指标，网格指标如图4所示。GR表示个体所处网格各维目标函数坐标之和，相当于将目标向量各维相加，只不过这里是将函数值映射为所处网格坐标值之和。比如下图A点的网格坐标为（0,4），则GR=0+4=4。GCD是网格拥挤距离，以往的网格拥挤距离都是在一个网格之内的，这样就不能反映分布性了，此处的GCD还考虑临近网格的个体，用网格坐标的差量之和评估，之和越小的GCD值就越大，多样性就越差。如下图C的邻居是B、D，F的邻居是E、G。GCPD表示的是同一网格内与中心点的距离，这一点与ε-MOEA中相同。比较的先后准则是GR，GR相同比较GCD，GR、GCD都相同则比较GCPD。图4网格指标示意图3.归档策略的改进以往的归档策略都是基于适应度值的支配关系选择删除，这样会导致解集多样性的缺失，因为相邻的点具有相似的适应度值，会使他们同时被选择或删除，比如上图的E、F、G，这样多样性会得不到保证。本文作者对归档策略进行了改进，就是当一个个体加入归档集时，在归档集中和它相关的个体GR值会受到惩罚，相关的个体包括：1.处于同一网格坐标2.被网格支配的3.邻域个体，惩罚力度依次减小。（四）基于坐标转换的高维多目标进化算法针对原始的密度评估算子在高维多目标中会出现不能很好的兼顾收敛性与多样性，解集往往会有很好的多样性而收敛性差的缺点，论文设计了一种包含收敛性的密度评估算子shift-baseddensityestimation(SDE)[35]。比如图5中的A点，按照基于pareto支配的多目标优化算法来看，是非支配解切多样性好于B、C、D，但很明显得看出A点收敛性不及BCD。SDE是将各维目标函数上小于A点对应维的值转化为A点那一维的函数值，如下图所示。转换之后A点的密度值较大，而BCD密度值较小，符合所考虑的情况图5坐标转换示意图从图6的四图中可以看出，只有收敛性和多样性都好的个体，其SDE值小，即其值不仅体现密度信息，而且将收敛性信息也包含在内。SDE是一种通用的密度评估算子，可以将其植入NSGA-II，SPEA2和PESA-II中。图6拥挤密度示意图（五）基于角点排序的高维多目标进化算法本文是在非支配排序上的改进。在高维多目标优化问题中，随着目标维数的增加，非支配解之间的比较次数是非常大的，因此论文提出了角点支配。所谓的角点指的是在M维目标空间中只考虑其中k个目标，在本文中只考虑一个目标函数上的，因为在一个目标函数上最好的点肯定是非支配解。二维、三维角点分别如下图所示。图7二维、三维角点示意图找到角点后，所有被角点支配的点就不用比较了，大大减少评价次数。而且本文还指出非支配解排序的比较次数应该是精确到每一维的目标函数的比较上，因为每两个解之间目标函数的比较次数从2到M，也就是说不同的两个解之间比较所花费的计算量是不同的，只计算一个解与其他解的比较次数是不对的。角点支配排序大致过程如图8所示。图8角点非支配排序图8是2维目标函数的情况，首先得找出每一维目标函数上最好的点，如上图A中的白点，标记他们所支配的点如上图阴影区域，这些点在当前等级中就不考虑排序了，在剩下的点中再寻找两个角点，直到将所有的点都标记，如图B，B中白点表示等级1，等级2、3依次进行。（六）NSGA-III算法系列文献1.MO-NSGA-II为了适合解决高维多目标问题，KalyanmoyDeb针对NSGA-II的缺点，提出了MO-NSGA-II（many-objectiveNSGA-II），这是NSGA-III的雏形。MO-NSGA-II的基本框架和NSGA-II差不多，不同之处在于精英选择机制上，因为原有的选择机制对快速增加的非支配解已经没有选择压力。MO-NSGA-II是一种基于参考点的多目标算法，放置分布性好的参考点，使得到的非支配解靠近这些参考点，就能得到分布性好的最优前端。让我们回顾一下NSGA-II，有一个大小为N的当前种群Pt，由他产生的子代种群Qt，大小也为N，然后对Pt、Qt的合集Rt进行快速非支配排序F1、F2...Fi,将这些点按等级加入下一代种群Pt+1，通过对Fl中个体计算拥挤距离按降序排列，依次加入Pt+1，直到种群大小为N。参考点的设置就是从这里开始，取代原有的拥挤距离。均匀分布的参考点可以通过一些特定的系统产生。1）超平面的建立。设F1、F2...Fi的合集为St，在这个集合中找到每一个目标函数值最小的点组成理想点minminminmin12(,,...,)Mzzzz，将目标函数值转化为相对的min()=()ziiiffuu‘，然后种群中的点通过一个聚集函数求最小值（它是相对于在某一维坐标轴上的参考点的）把它当成这一维的端点，通过这M个端点构造超平面，根据这个超平面重新计算参考点，这个超平面在每一代中都不同，所以它是可以根据种群特性自适应调整。2）选取低拥挤度的解。为了确定解集拥挤度，需要把所有的点投影到超平面上（如图9左图），找到与之距离最近的参考点，这样每个参考点就会有一定数量的解与之相关联（如图9右图）。选择参考点周围个体最少的参考点，选出Fi解集中在这个参考点下ASF最小的点加入Pt+1。再选出个体数次最少的参考点，选出Fi解集中在这个参考点下ASF最小的点加入Pt+1，直到加满Pt+1。图9关联操作3）锦标赛选择。当Pt+1形成，用锦标赛方法产生后代Qt+1，具体操作是从Pt+1任意挑选两个解，比较策略是如果一个解的非支配等级小于另一个解，选择前一个解；如果同处一个非支配等级但是所属参考点的拥挤度不同，选拥挤度小的点；如果非支配等级和所属参考点的拥挤度都相同，则选ASF值小的。然后采用模拟二进制交叉算子，产生后代Qt+1，然后在合并进行第一步，依次循环。2.NSGA-III本文作者针对上文提出的MO-NSGA-II作了适当改进，提出了NS