afastandelitistmultiobjectivegeneticalgorithm : nsga-ii中文翻译
目录
1. NSGA-II概述
2. NSGA-II详细信息
3. NSGA-II模拟结果
4 .参数设置问题
5 .约束处理方法
1. NSGA概述NSGA-II适用于复杂的多目标优化问题。 中小学教授于2002年在论文： afastandelitistmultiobjectivegeneticalgorithm 3360 nsga-ii，中提出。 论文提出的NSGA-II解决了NSGA的主要缺陷，实现了快速准确的搜索性能。 NSGA非支配排序的时间复杂度为o(Mn3 ) o(Mn3 ) )，种群规模n较大时排序速度变慢。 NSGA-II使用带精英战略的快速非支配排序，时间复杂度为o(m(2n )2) o (m ) 2n )，排序速度大幅提高。 另外，运用精英策略，使找到的最优解不被舍弃，提高了搜索性能。 另一方面，NSGA使用共享函数使解的分布均匀。 该函数依赖于共享参数share s h a r e的选择，而且共享函数的复杂度高达o(n2 ) o(n2 )。 NSGA-II新定义了拥塞距离而不是共享参数。
2. NSGA-II详细介绍1 .高速非支配排序
根据支配比较进行种群快速非支配排序，排序分为两部分
将群体个体能够支配的个体作为一个集合Sp S p，记录个体支配的个体数NPNPp，将np==0 n p==0的个体作为最初的上位集合F1 F 1，将1代入个体的等级rank。 从Fi F i中取出各个个体，对该个体的Sp S p集合中的个体，进行将np n p减少1，如果np==0 n p==0，则判断为添加到集合Fi 1 F i 1的操作。 2 .多样性保护1 .拥挤距离(关闭距离) )。
NSGA在使种群收敛于pareto-optimal-solutions的同时，还需要利用共享参数使解能相对均匀分布，即尽量保持解的多样性。 然而，由于共享函数的复杂度(o ) n^2) )太高，这里使用拥塞距离代替共享参数。 对两个目标函数的拥挤距离如下图所示
会聚距离等于各目标函数方向上解的前后两个解的距离。 对于二维，它是图标矩形周长的一半。
拥挤距离的伪代码为note : 如果某个方向上的距离很大，就会很大程度上影响总的距离的大小。为了使每个方向上的目标函数对拥挤距
离有等效的影响力，需要每个目标函数上的距离要规则化normalized。2.拥挤比较操作（crowded-comparison-operator)
在选择算子是基于非支配比较操作区选择个体
3.NSAG-II的实现过程
首先：对种群 Pt P t 执行选择、交叉、变异操作，形成新种群 Qt Q t 。
然后：合并这两个种群并对合并后的种群执行非支配排序
最后：根据个体rank形成的前列面 Fi F i ，从低到高依次加入下一代种群 Pt+1 P t + 1 ,当 Fi F i 加入使种群大小越界时，依据拥挤距离从大到小，将个体加入种群。
we use a binary tournament selection operator on crowded_comparison operator
复杂度分析：worst case
fast_nondominated_sort complexity: O(M(2N)2) O ( M ( 2 N ) 2 )
crowding_distance_assign complexity: O(M(2N)log(2N)) O ( M ( 2 N ) l o g ( 2 N ) )
sorting on nondominated_operator complexity: O((2N)log(2N)) O ( ( 2 N ) l o g ( 2 N ) ) (such as quick sort)
选择合适参数设置进行测试，虽然不是最佳的参数设置，但是为了体现NSGA-II相比其他算法的优越性，应该是对各种问题表现都相对均衡的参数。参数设置如下
population size：250
probability for crossover：0.9
probability for mutation： 1nvariesor1nbits 1 n v a r i e s o r 1 n b i t s
distribution index for crossover and mutation: nc=20 nm=20 n c = 20 n m = 20
binary code ： single point crossover， bitwise mutation
real code : SBX , polynomial mutation
测试结果：
可见除了ZDT3 和ZDT6，NSGA-II性能都是最好的。
大多数情况下，浮点数编码的NSGA-II比其他任何算法都有更好的解分布，包括二进制编码的NSGA-II.
只是以进化次数和变异分布指数为例，简单说明参数的影响，并不对最优参数设置做深入的研究。
增加进化次数到500 ：可以得到离最优解更近的收敛，和更均匀的解分布
减少变异分布指数： 可以使多项式变异产生变化更大的解
例如：ZDT4有很多局部最优解，为了跳出zdt4的局部最优解，自变量要有大变化才可能。这里使用了更小的distribution index for mutation： nm=10 n m = 10 ，结果convergence metric 减小到0.02，diversity metric 减小到0.498