算法系列——NSGAII算法介绍[原创哦]

monder

本文链接http://www.simwe.com/forum/post/edit?bid=102&id=516817&done=%2Fforum%2Fpost%2Fview%3Fbid%3D102%26id%3D516817%26sty%3D1
如需转载，请注明出处，谢谢。

NSGAII是modefrontier的优秀算法，为了让用户更多的了解此算法，我公司推出系列算法介绍。modefrontier的NSGAII算法是经过严格测试和修改的，所以效果比Deb2002年发表的算法要好。
介绍NSGAII之前，先从NSGA谈起。

发展史：
年  作者  算法名称                       缺点
1983年  Chankong  提出Pareto-optimal solutions  
1984年  Schaffer  VEGA (Vector Evaluated GA)  对Pareto的某部分有偏见
1988年  Hans  提出nondominated solutions  
1989年  Goldberg
  NSGA (Nondominated Sorting GA)  
1993年  Fonesca和Fleming  NSGA  
1994年
  Horn、Nafpliotis、Goldberg  NSGA
  
1995年  Deb.  NSGA  好
2002年  Deb.  NSGAII（Elitist NSGA）  更好

===================

NSGA与普通的GA区别仅在于选择（selection）方法上，杂交和变异没什么区别。选择之前，按个体的不被支配解（nondominated individual）排序，然后不被支配解被赋予一个大的虚（dummy）适应值。所有不被支配解的虚适应值相同，这样可以给所有不被支配解相同的繁殖能力。同时，为了保持种群的多样性，这些分类的个体与他们的虚适应值被共享。Goldberg和Richardson在1987年，Deb在1989年都讨论了共享方法。共享是通过降低适应值（原来的量除以一个与周围个体个数成正比的量）进行选择来完成的，这样多个优化点就可以共同存在而不被淘汰。共享后，这些不被支配解暂时被放在一边，用同样的方法处理种群的其它部分，找出第二批不被支配解，即Pareto前沿。分配给这个解集的虚适应值始终比前一个Pareto前沿的虚适应值要小。循环重复这个过程，直到整个人群分成几个前沿。

种群是按照虚适应值进行繁殖的，因为第一个前沿的个体适应值最大，所以他们的后代比其它的个体多，这种策略的收敛速度快，而且共享方式能够保证在区域上广泛搜索。NSGA强调不被支配的解，NSGA的效率取决于使用不被支配解排序过程的虚适应值函数。

monder

排序选择方法，保留好的点。
小生境方法，保证好的点所在子种群的稳定性。

N. Srinivas and K. Deb, "Multiobjective optimization using nondominated
sorting in genetic algorithms," Evolutionary Computaton, vol. 2, pp. 221-248, 1994.

monder

NSGA算法的复杂度是O(mN3)，NSGAII的复杂度是O(mN2)。

NSGAII假设初始种群包括N个个体。
对第i个个体来说，令支配i的个体数定义为ni，令i所支配的个体集合定义为Si。
1首先找到ni=0的所有个体，组成集合F1，为当前的Pareto前沿
2对于F1集合中的所有个体的Si个体集合，将该集合中所有ni=1的个体选出，为集合H
3集合H作为当前Pareto前沿

产生不被支配排名（non-domination ranking）。
K. Deb, A. Pratap, S. Agrawal, and T. Meyarivan, "A fast and elitist
multiobjective genetic algorithm: NSGA-II," IEEE Transaction on Evolutionary Computation, vol. 6, pp. 182-197, 2002.
------------------------------
点的疏密用拥挤距离（crowding distance）来表征，第i个点拥挤距离等于如图所示长方形的平均边长。

拥挤算子（Crowded Comparison Operator）能够保证Pareto前沿点均匀分布。

产生拥挤排名（Local Crowding Distance Ranking）

对于属于同一个前沿的两个点，我们选择不被支配排名低的。
如果两个点的不被支配排名相同，选择拥挤距离大的。

daisy_tu79

斑竹，有几个问题不是很了解阿，不被支配解和支配解是如何区分的阿，两个个代表什么意思，还有就是“NSGA算法的复杂度是O(mN3)，NSGAII的复杂度是O(mN2)”复杂度O（mN3）O(mN2)什么意思啊？还望指教：）

monder

看图。水平和垂直两条线相交的点为O，那么C就是O所支配的解，ABD都是不被O支配的解。
  A  |    B
--------------
  C  |     D

3和2是“上标”，这里没办法输入格式。NSGA比NSGAII的算法复杂。

daisy_tu79

呵呵，谢谢，明白了

fangdao886

好贴，学习