NSGA-NSGA-I算法详解ppt课件

NSGA,NSGA-𝕀算法详解1以最小化问题为例，对于两个任意决策变量𝒙𝑨,𝒙𝑩∈𝑿𝒇（可行解集合）：(l)当且仅当∀𝒊=𝟏,𝟐,…,𝒌:𝒇𝒊(𝒙𝑨)𝒇𝒊(𝒙𝑩)时，称A占优于B(𝒙𝑨≻𝒙𝑩)(2)当且仅当∀𝒊=𝟏,𝟐,…,𝒌:𝒇𝒊(𝒙𝑨)≤𝒇𝒊(𝒙𝑩)且∃𝒊=𝟏,𝟐,…,𝒌:𝒇𝒊(𝒙𝑨)𝒇𝒊(𝒙𝑩)时，称A弱占优于B(𝒙𝑨≽𝒙𝑩)(3)当且仅当A不占优于B，且B不占优于A时，称A与B无差别此处是在有多个目标函数的情况下对两个解进行比较的，即如果Pareto占优，则该决策向量的所有目标函数值均应小于另一决策向量对应的各目标函数值。Pareto占优2对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解.Pareto最优解Pareto最优前沿对于组成Pareto最优解集的所有Pareto最优解，其对应目标空间中的目标矢量所构成的曲面称作Pareto最优前沿.3NSGA非支配排序遗传算法NSGA与简单的遗传算法的主要区别在于:该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别.NSGA采用的非支配分层方法，可以使好的个体有更大的机会遗传到下一代;适应度共享策略则使得准Pareto面上的个体均匀分布，保持了群体多样性，克服了超级个体的过度繁殖，防止了早熟收敛.4开始终止进化代数Gen=0,初始化种群Front=1进化代数Gen小于最大代数根据虚拟适应度进行复制交叉变异种群全部分级Gen=Gen+1识别非支配个体指定虚拟适应度值应用于适用度共享小生境Front=Front+1YNYN5通过非支配排序算法对这个规模为n的种群进行分层的具体步骤如下：（1）设i=1；（2）对于所有的j=1,2,,n且j≠i，按照以上定义比较个体𝒙𝒊和个体𝒙𝒋之间的支配与非支配关系；（3）如果不存在任何一个个体𝒙𝒋优于𝒙𝒊，则𝒙𝒊标记为非支配个体；（4）令i=i+1，转到步骤(2)，直到找到所有的非支配个体。通过上述步骤得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经标记的非支配个体(即这些个体不再进行下一轮比较)，再遵循步骤(1)-(4)，就会得到第二级非支配层。依此类推，直到整个种群被分层。非支配排序原理6种群分层结束后，需要给每级指定一个虚拟适应度值，级别越小，说明其中的个体越优，赋予越高的虚拟适应值，反之级别越大，赋予越低的虚拟适应值。这样可以保证在复制操作中级别越小的非支配个体有更多的机会被选择进入下一代，使得算法以最快的速度收敛于最优区域。比如第一级非支配层的个体标上虚拟适应值为1，第二级非支配层的个体标上虚拟适应值为0.9(或其他)，以此类推，直到所有的个体都被标上虚拟适应值。但是由于同一级非支配层中的个体拥有相同的适应度值，某些个体在遗传操作中可能被遗弃，导致最优解集不具有多样性，为了得到分布均匀的Pareto最优解集，就要保证当前非支配层上的个体具有多样性。7假设第p级非支配层上有𝒏𝒑个个体，每个个体的虚拟适应度值为𝒇𝒑，且令𝐢,𝒋=𝟏,𝟐,…,𝒏𝒑，则具体的实现步骤如下:（1）计算出同属于一个非支配层的个体𝒙𝒊和个体𝒙𝒋的欧几里得距离𝒅𝒊𝒋=𝑭𝒍𝒙𝒊−𝑭𝒍𝒙𝒋𝑭𝒍𝒖−𝑭𝒍𝒅𝑳𝒍=𝟏𝟐其中，L为问题空间的变量个数,𝑭𝒍𝒖,𝑭𝒍𝒅分别为𝑭𝒍的上、下界共享小生境技术8（2）共享函数是表示两个个体间关系密切程度的函数，两个个体𝒙𝒊与𝒙𝒋间的共享函数𝐬𝐡𝒅𝒊𝒋一般描述为：𝐬𝐡𝒅𝒊𝒋=𝟏−𝒅𝒊𝒋𝝈share𝒂，𝒅𝒊𝒋≤𝝈share𝟎，𝒅𝒊𝒋≤𝝈share，式中，𝝈share：小生境半径，是设定值𝒅𝒊𝒋：个体𝒙𝒊与𝒙𝒋之间的欧几里得距离a:用于对𝐬𝐡𝒅𝒊𝒋的调整注：①𝟎≤𝐬𝐡𝒅𝒊𝒋≤𝟏，𝐬𝐡𝒅𝒊𝒋大，表明二者关系密切，或者说个体之间相似的程度大；②每一个个体自身的𝐬𝐡𝒅𝒊𝒋=1；③当𝒅𝒊𝒋≥𝐬𝐡𝒅𝒊𝒋时，𝐬𝐡𝒅𝒊𝒋=0；④在𝝈share范围内的个体小生境半径相同，互相减小适应度，收敛在同一小生境内。𝝈share的值是影响搜索性能的关键因素。9（3）j=j+1，如果𝒋≤𝒏𝒑转到步骤(1)，否则计算出个体𝒙𝒊在(同一小生境内)种群中的共享度𝒄𝒊，即它与种群中的其他个体间共享函数值之和，描述为：𝒄𝒊=𝒔𝒉𝒅𝒊𝒋𝒏𝒑𝒋=𝟏,𝐢=𝟏,𝟐,…,𝒏𝒑（4）计算出个体𝒙𝒊的共享适应度值：𝒇𝒑′𝒙𝒊=𝒇𝒑𝒙𝒊𝒄𝒊使i=i+1，反复执行以上的步骤(1)-(4)可以得到每一个个体的共享适应度值，这样非支配层的每个个体都拥有各自不同的适应度值，进行接下来的遗传操作时，就可以保证最优解集的多样性。101）非支配排序的高计算复杂性。非支配排序遗传算法一般要进行次搜索𝒎𝑵𝟑(m是目标数量，N是种群大小)，搜索次数随着目标数量和种群大小的增大而增多。2）缺少精英策略。近年来的研究结果表明，精英策略可以加快GA的执行，还有助于防止好的解丢失。3）需要指定特殊的共享参数𝝈share，NSGA的保持种群和解的多样性的策略都是依赖于共享的概念，共享的主要问题就是需要有一个共享参数𝝈share。正是由于要对共享参数作额外的工作，所以就需要一种不依赖共享参数的方法。NSGA的缺点：11NSGA-II算法的改进：1）提出了快速非支配排序算法，降低了计算的复杂度，使算法的复杂度由原来𝒎𝑵𝟑的降到𝒎𝑵𝟐2）引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，保证某些优良的种群个体在进化过程中不会被丢弃，从而提高了优化结果的精度。并通过对种群中所有个体的分层存放，使得最佳个体不会丢失，迅速提高种群水平。3）采用拥挤度和拥挤度比较算子，不但克服了NSGA中需要人为指定共享参数的缺陷，而且将其作为种群中个体间的比较标准，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性。带精英策略的非支配排序遗传算NSGA-Ⅱ12开始输出进化代数Gen=1,初始化种群𝑹𝒕非支配排序形成非支配集ZGen=最大代数Gen=Gen+1交叉,变异新的子代种群𝑸𝒕+𝟏𝑷𝒕+𝟏个数等于N子代与父代种群合并形成2N大小种群𝑹𝒕𝒁𝒊…𝒁i+j进行拥挤度排序,拥挤度大的选入i=i+1YNYNi=1将𝒁𝒊放入新父代种群𝑷𝒕+𝟏(精英策略)𝒁𝒊=𝒁i+1=⋯=𝒁i+jYN13对于每个个体i都设有以下两个参数𝒏𝒊和𝒔𝒊,𝒏𝒊为在种群中支配个体i的解个体的数量，𝒔𝒊为被个体i所支配的解个体的集合。①找到种群中所有𝒏𝒊=0的个体，将它们存入当前集合𝒁𝟏；②对于当前集合𝒁𝟏中的每个个体j，考察它所支配的个体集𝑺𝒋，将集合𝑺𝒋中的每个个体k的𝒏𝒌减去1，即支配个体k的解个体数减1(因为支配个体k的个体j已经存入当前集𝒁𝟏)，如果𝒏𝒌-1=0,则将个体k存入另一个集H；③将𝒁𝟏作为第一级非支配个体集合，𝒁𝟏中的个体是最优的，它只支配个体而不被其他任何个体支配，赋予该集合内个体一个相同的非支配序𝒊𝒓𝒂𝒏𝒌，然后继续对H作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。快速非支配排序法14在原来的NSGA中，采用共享小生境技术以确保种群的多样性，但这需要由决策者指定共享半径𝝈share的值。为了解决这个问题，NSGA-II中提出了拥挤度的概念：拥挤度表示在种群中给定点的周围个体的密度，用𝒊𝒅表示，直观上用个体i周围包含个体i但不包含其余个体的最大长方形的长来表示。在带精英策略的非支配排序遗传算法中，拥挤度的计算是保证种群多样性的一个重要环节，其计算步骤如下：拥挤度比较算子--拥挤度的确定15①每个点的拥挤度𝒊𝒅置为0；②针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即𝒐𝒅=𝑰𝒅=∞；③对其他个体进行拥挤度的计算：𝒊𝒅=𝒇𝒋i+1−𝒇𝒋i−1𝒎𝒋=𝟏其中，𝒊𝒅表示i点的拥挤度，𝒇𝒋i+1表示i+1点的第j个目标函数值，𝒇𝒋i−1表示i-1点的第j个目标函数值。16经过前面的快速非支配排序和拥挤度计算之后，种群中的每个个体i都拥有两个属性：非支配排序决定的非支配序𝒊rank和拥挤度𝒊𝒅。依据这两个属性，可以定义拥挤度比较算子：个体i与另一个个体j进行比较，只要下面任意一个条件成立，则个体i获胜。①如果个体i所处非支配层优于个体j所处的非支配层，即𝒊rank𝒋rank②如果他们有相同的等级，且个体i比个体j有一个更大的拥挤距离，即𝒊rank=𝒋rank且𝒊𝒅𝒋𝒅第一个条件确保被选择的个体属于较优的非劣等级。第二个条件根据它们的拥挤距离选择由于在同一非劣等级而不分胜负的两个个体中位于较不拥挤区域的个体(有较大的拥挤度𝒊𝒅)。胜出的个体进入下一个操作。拥挤度比较算子--拥挤度比较算子17精英策略18首先将第t代产生的新种群𝑸𝒕与父代𝑷𝒕合并组成𝑹𝒕，种群大小为2N。然后𝑹𝒕进行非支配排序，产生一系列非支配集𝒁𝒊并计算拥挤度。由于子代和父代个体都包含在𝑹𝒕中，则经过非支配排序以后的非支配集𝒁𝟏中包含的个体是𝑹𝒕中最好的，所以先将𝒁𝟏放入新的父代种群𝑷𝒕+𝟏中。如果的大小小于N，则继续向𝑷𝒕+𝟏中填充下一级非支配集𝒁𝟐，直到添加𝒁𝟑时，种群的大小超出N，对𝒁𝟑中的个体使用拥挤度比较算子，取前num𝒁𝟑−（num𝑷𝒕+𝟏−𝑵）个个体，使𝑷𝒕+𝟏个体数量达到N。然后通过遗传算子(选择、交叉、变异)产生新的子代种群𝑸𝒕+𝟏19