NSGAII基于非支配排序的多目标优化算法(中文翻译).doc

基于非支配排序的带有精英策略的多目标优化算法：NSGA-II摘要：使用非支配排序和共享变量方法的多目标进化算法近年来因为它的一些缺陷指责，主要是由于(i)这种算法的计算复杂度较高，到达了O(mn3)(其中m表示多目标优化中目标的数量，n表示种群的大小)，(ii)缺少精英策略，(iii)需要人为指定共享变量在本文中，提出了一种基于多目标进化算法的非支配排序方法〔我们将它称为非支配排序GA-II算法或者NSGA-II算法〕选择操作通过把父代和子代混合在一个交配库中，从中选择最优的N个个体〔根据适应度层级和拥挤度进展优劣排序〕通过5个复杂的测试函数进展测试得出的模拟结果说明，本文所提及的NSGA-II算法，在解决大局部问题是，比PAES和SPEA算法〔另外两种具有精英策略的多目标遗传算法，这两种算法在的优势在于创造多样的Pareto最优层级〕具有更好的分布，并且它的收敛性更接近实际中的Pareto最优层级因为NSGA-II算法具有较低的计算复杂度，带有精英策略和较少的共享参数参数，NSGA-II算法在最近几年内将应用在更多的领域1、 介绍在过去的十多年中，人们提出了大量的多目标进化算法〔MOEAs〕。

主要原因是它们在一次运行中找寻多值Pareto最优解的能力一个问题有多个最优解的主要原因是不可能同时优化多个对象时找到一个单独的最优解，所以一个能给出大量可供选择的最优解集的算法才是具有实际价值的由Srinivas和Deb教授提出的非支配排序遗传算法〔NSGA〕曾经是其中第一个这样的进化算法多年以来，对NSGA算法主要的批评如下：〔1〕.进展非支配排序时的计算复杂度高：NSGA进展非支配排序时的计算复杂度是O(mN3) (m为优化对象的个数，N为种群大小)，一旦当种群较大时，计算十分复杂，尤其是种群需要在每一代都进展非支配排序〔2〕．缺少精英策略：最近一些实验的结果说明，精英策略在相当程度上能够加速遗传算法的执行而且一旦满意解被找到，它也能防止这些满意解的丧失〔3〕.需要指定共享参数：传统的为了保证一个种群中的多样性，从而得到具有广泛多样性的等价解的方法主要依赖于共享的概念而这种方法的主要问题是它需要指定共享参数，尽管已经有一些方法能够动态的指定共享参数，但一个不需要共享参数的保持多样性的方法才是最需要的在本文中，我们解决了所有的这些问题，提出了一个更加优秀的NSGA版本，我们将它称为NSGA-II算法。

从对很多测试函数测试得出的仿真结果来看，NSGA-II算法总的来说是优于PAEs算法和SPEA算法——另外两种带有精英策略的多目标进化算法〔依据聚合在Pareto最优边界和在获得的解集中保持多样性〕，这些测试结果鼓励我们把NSGA-II应用在一些更复杂的应用和解决一些现实世界中的多目标优化问题2、 带有精英策略的多目标进化算法Zitzler，Deb和Theile教授通过研究发现，在多目标进化算法中精英策略能够帮助获得更好的收敛边界在所有提出的带有精英策略多目标进化算法中，Zitzler和Thiele教授提出的SPEA算法，Knowles和Gome教授提出的PAEs算法以及Rudolph教授提出的精英遗传算法〔elitist GA〕是最广为人知的Zitzler和Thiele教授在它们的非支配排序中提出了多重标准精英策略的概念他们表示如果在每一代的排序过程中，保持外部种群，则从初始种群开场所有的非支配解都能被发现这些外部种群参加遗传操作每一代，都有一个具有外围的合并的种群，这个种群是第一个被构造的在合并种群中的所有的非支配解都被根据它们支配解的数量分配了一个适应度，所有的支配解则被分配了一个比所有非支配解都差的适应度。

这种适应度的安排保证了直接在非支配解中寻找最优解集一种决定性的聚集技术被用来保证非支配解的多样性尽管实施说明计算复杂度是O〔MN〕，但通过簿记，SPEAs的计算复杂度可以降低到O〔MN2〕Knowles和Corne教授提出了另外一种简单的使用进化策略的多目标进化算法，这种算法，种群具有一个父代和一个子代，父代和子代进展比较，如果子代支配父代，则子代就作为下一个父代，如果父代支配子代，则子代就被抛弃，一个突变的解〔新的子代〕参加然而，如果子代和父代相互之间没有支配关系，则通过比较它们和所有已经发现的最优解，如果子代被发现支配最优解中的任何一个解，则子代被承受为新的父代，而被支配的最优解则从最优解集中删除如果子代不支配任何最优解，则检查父代和子代与最优解集的接近程度，如果子代存在于一个共享参数不密集的区域，则它被承受为新的父代参加到最优解集中这种算法的最差计算复杂度为O〔aMN〕，a表示最优解集的大小，由于最优解集通常是和种群大小N成比例的，所以这种算法总的计算复杂度是O〔MN2〕Rudolph教授提出的一个简单的通过系统的比较父代个体和后代的种群多目标优化算法后代种群中的非支配解和父代种群中的非支配解组成一个总的非支配解集，在下一次循环中，这个非支配解集成为新的父代，如果这个集合没有需要得到的种群大小大，其他独立的后代继续被参加。

通过这种策略，能够证明Pareto最优边界虽然这种算法比较优秀，但它缺少解决第二个问题，保持解集多样性的方法3、 带有精英策略的非支配排序遗传算法〔NSGA-II〕非支配排序遗传算法由Srinivas和Deb教授在1994提出，由于它的一些前面提及的问题遭到了批评在这一节中，我们提出了NSGA-II算法，减轻了这些困难接下来我们将分几个板块介绍NSGA-II算法3.1. 快速非支配排序方法为了对大小为N的种群根据非支配层级进展排序，每一个解必须和种群中的其他解都进展比较，从而得出它是否被支配，这需要O〔MN〕的计算复杂度，M是优化对象的数量当这一步骤进展完毕后，继续找出所有第一个非支配层级的个体，总的计算复杂度是O〔MN2〕在这一步中，所有在第一个非支配层级的个体都被找到为了找出下一个支配层级的个体，属于第一个非支配层级的个体暂时不被计入，继续进展前面的操作，重复如上操作一直到找到后来的所有非支配层级上的个体可以看到最差的情况下〔每一个层级上只有一个个体〕，在没有任何簿记的情况下，计算复杂度是O〔MN3〕而下面将介绍的快速非支配排序则在最差情况下，计算复杂度是O(MN2)这个方法与上面介绍的方法大局部是相类似的，但它有更好的簿记策略。

所有种群中的解与一个局部填满的种群比较支配关系开场时，先将第一个解参加集合P’，其后P种群中的其它解都和P’集合中的解比较，如果P集合中的任何个体支配P’中的任何个体q，此时将P’集合中的个体q移除通过这种方法，所有的非支配个体都被保存否则，如果个体p被P’中的所有个体支配，则不将p包含进P’中fast-nondominant-sort(Rt)P' = {1} //将第一个成员参加到P'中for each p∈P ∧ p∈/P' //每次选择一个不在P'中的pP' = P' U {p} //将p临时性的包含值P’中for each q∈P' ∧ q∈/ P //将p与P'中的其它成员比较if p＜q, then P' = P'\{q] //如果支配 P' 中的任何一个成员 则删除P' 中的该成员qelse if q＜p, then = P'\{p}//如果p被P' 中的所有成员支配 则不将p 包含在P' 中为了找到其他非支配层级，P’中的成员将不被再次计入，再重复上面的循环操作我们发现，第二个个体只需要和P’中的一个个体进展比较，第三个个体则需要与两个个体进展比较，在最坏的情况下，即当P中的所有个体均为非支配个体时，比较的总次数为：N2/2。

所以算法的时间复杂度均为O〔N2〕3.2 拥挤度计算 为了计算每个解周围的其它解的分布情况，我们得出该个体周围只包含个体本身的区域的最大长方形的长的平均长度〔我们称之为拥挤度〕如图1所示crowding-distance-assignment〔Fi)l= |I | //个体的个数为Ifor each i, set I[i]distance = 0 //初始化所有的拥挤度值为0for each objective m I = sort(I, m) //基于每个目标函数对种群进展排序I[l]distance = I[i]distance =∞//令两个边界个体的拥挤度为无穷for i = 2 to (l — 1) //对于其他的个体I[i]distance = i[i]distance + (I[i+1].m – I[i-1].m) //计算每个个体的拥挤度3.3 拥挤度比较算子定义拥挤度算子 用符号〔〕来表示，该种群中的每个个体都拥有如下两个属性：1. 非支配排序层级()2. 拥挤度()可以定义拥挤度算子如下：i j 表示 〔 < 或者 =〕 并且 >此算子的含义是，当两个解，属于不同的非支配排序的层级时，选择非支配层级较低的解，当两个解属于同一个非支配层级的时候，选择拥挤度较大的解，即此解周围的个体较少，所在区域解的分布较为稀疏。

3.4 主流程 开场时，创立一个随机的父代种群，种群进展快速非支配排序，每一个解都被分配一个和非支配层级〔1是最优层级〕相应的适应度值因此，最小的适应度值是假定的然后进展二进制锦标赛选择，重新组合，变异算子用来创造新的大小为N的子代种群从第一代开场，进展的步骤是不同的：Rt = PtU Qt //将父代种群和子代种群合并F= fast-nondominant-sort(Rt) F = (F1, .F2,...) //将合并后的种群进展非支配排序Pt+i = ｛空集｝ //初始化 Pt+1 父代种群until |Pt+i | < N //直到Pt+1父代种群填满，进展以下的循环{crowding-distance-assignment〔Fi) //计算第i层级上的所有个体的拥挤度Pt+1 = Pt+1 ∪ Fi //将第i层级中的个体并入Pt+1父代种群中i= i+1}Sort(Pt+1,

获得的阶级的第一个非支配层级和一个一致分布相比较，得到它的偏差如下：为了保证这个计算把解在整个分布的扩散性，我们包含了非支配层级的边界，F1-对于离散的Pareto最优边界，我们计算每一个离散区域的加权平均数Di是欧几里德距离参数d是这些距离的平均值1、表一比较了通过NSGA-II，PAES和SPEA三种算法得出的平均值和方差的区别2、表二比较了通过NSGA-II，PAES和SPEA三种算法得出到真实的Pareto最优边界的距离和它的标准偏差3、通过比较MOP4测试函数得到的Pareto最优边界图形可以看出，NSGA-II得出更好，更清晰的分布如图2和图3所示。