第九章 基于遗传算法的多目标最优化算法

带精英策略的快速非支配排序遗传算法 NSGA-II 算法 转载： NSGA-II pareto（帕累托）最优解 NSGA-II Paerot支配关系 （较优的解支配次优解） 多目标问题：

帕累托的一个解释 1：解A优于解B（解A强帕累托支配解B）

假设现在有两个目标函数，解A对应的目标函数值都比解B对应的目标函数值好，则称解A比解B优越，也可以叫做解A强帕累托支配解B。

多目标优化问题与单目标优化问题有很大差异。当只有一个目标函数时,人们寻找最好的解,这个解优于其他所有解,通常是全局最大或最小,即全局最优解。而当存在多个目标时,由于目标之间存在冲突无法比较,所以很难找到一个解使得所有的目标函数同时最优,也就是说,一个解可能对于某个目标函数是最好的,但对于其他的目标函数却不是最好的,甚至是最差的。因此,对于多目标优化问题,通常存在一个解集,这些解之间就全体目标函数而言是无法比较优劣的,其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作Paerot最优解。

非支配排序遗传算法

NSGA与简单的遗传算法的主要区别在于：该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别。

在选择操作执行之前，种群根据个体之间的支配与非支配关系进行排序：

首先，找出该种群中的所有非支配个体，并赋予他们一个共享的虚拟适应度值。得到第一个非支配最优层；

然后，忽略这组己分层的个体，对种群中的其它个体继续按照支配与非支配关系进行分层，并赋予它们一个新的虚拟适应度值，该值要小于上一层的值，对剩下的个体继续上述操作，直到种群中的所有个体都被分层。

算法根据适应度共享对虚拟适应值重新指定：

比如指定第一层个体的虚拟适应值为1，第二层个体的虚拟适应值应该相应减少，可取为0．9，依此类推。这样，可使虚拟适应值规范化。保持优良个体适应度的优势，以获得更多的复制机会，同时也维持了种群的多样性。

NSGA采用的非支配分层方法，可以使好的个体有更大的机会遗传到下一代；适应度共享策略则使得准Pamto面上的个体均匀分布，保持了群体多样性，克服了超级个体的过度繁殖，防止了早熟收敛。算法流程如图所示：

非支配排序遗传算法(NSGA)在许多问题上得到了应用。但NSGA仍存在一些问题：

a) 计算复杂度较高，为 O ( m N 3 ) O(mN^{3}) O(mN3) (m为目标函数个数，N为种群大小)，所以当种群较大时，计算相当耗时。

b) 没有精英策略；精英策略可以加速算法的执行速度，而且也能在一定程度上确保已经找到的满意解不被丢失。

c) 需要指定共享半径 σ s h a r e \sigma_{share} σshare