最优解集"/>

帕累托最优解集

帕累托最优解集

• A、==帕累托最优的若干定义==：
• • 1）支配与非支配
  • 2）帕累托最优前沿
• B、==帕累托非支配排序的遗传算法NSGA-Ⅱ==
• • 1）非支配排序
  • 2）拥挤度

A、帕累托最优的若干定义：

1）支配与非支配

如上图所示，若表示为机票，既要考虑飞行时长也要考虑机票价格，保证出行最便捷。
A与C相比，A耗时为2，花费为7.5；C耗时为3，花费也为7.5，那么方案A要比C优秀，那么A支配C。
但是，纵观全部解，没有在耗时和花费两者全部比A优秀的方案，那么就称A为非支配。

2）帕累托最优前沿

A的耗时为2，花费为7.5；B的耗时为3，花费为6。那么两者进行对比，A只能在时间上获胜，B只能在花费上获胜，但是两者没有既在时间又在花费上获胜的情况。且纵观全局，没有在耗时和花费两者全部比A、B优秀的方案，那么A、B就组成了帕累托最优前沿，D、F类似。因此，得到了下图。

B、帕累托非支配排序的遗传算法NSGA-Ⅱ

1）非支配排序

非支配排序，如图所示，A、B、D、F判定为帕累托前沿后，将他们放到一边，暂时不考虑。再在剩下的方案中，再选一组帕累托前沿，依此类推。

2）拥挤度

由上述可知，第一帕累托前沿上面的解一般为最优解，但是有很多个，如何进行解的选取。
需要依靠解的拥挤度，总的原则是，为了保证解的多样性，尽量选择人口稀少的地区的解。

拥挤度公式如上图所示，对于i点的拥挤度计算，需要计算i-1与i+1两点的函数差值与（Xmax与Xmin函数差值）的比值，比值越大，表示i的拥挤度越低。

而对于特殊情况，如上图所示的A、F两点，两侧无解，则视为无穷大，那么A、F两点必被选中。其次再考虑B、D两点的拥挤度。