之前学习了遗传算法对单目标函数的最优值求解，对于多目标问题。或者说是多目标函数的求解问题，我想再研究一下。正好，我也想改进一下之前的代码架构。不得不说，之前的代码是面向过程的架构，完全没有体现出python面向对象的特点。于是在上篇里更新了面向对象的程序。

一.举个多目标函数的简单例子

这里我们举个二元函数的最大值优化例子：

根据之前所学，

第一步，编码。这里我们采用二进制对个体基因型编码，将个体表现型编码为十进制。如，基因型x=100001对应的表现型是{4,1}。

第二步，初始生成种群。本例中，随机生成4个个体组成一个种群。如下，{011101}{101011}{011100}{111001}，其表现型为{3,5}{5,3}{3,4}{7,1}。

第三步，计算适应度。本例，直接用目标函数作为适应度函数。得到如下表格：

第四步，选择。适应度越高的个体，遗传到下一代的数量越多，这里采用轮盘赌方式。轮盘赌是典型的几何概率模型，其特点在于其选择概率与适应度大小成正比。在第三步中，计算了4个个体的适应度以及他所占总适应度值的比值将其组成一个概率区域，如下：

接下来，我们随机生成4个[0,1]之间的随机数，{0.15,0.35,0.89,0.75}。根据随机数的大小，来选择个体存活的数量。这里，有两个随机数落在了4#区间，分别有1个随机数落在了1#和2#区间。这样，我们就选出了下一代的个体。

第五步，交配。在这步中会个体间的基因互换，这里采取的是单点互换。首先，选择对群体进行随机配对，然后随机设置交换点的位置，最后互换基因。这里，我们将1-2,3-4,配对并且互换基因，如下：

第六步，变异。在这步中，我们随机选择一个个体，并且随机选择一个位置进行变异。将0变为1,或者将1变为0。

编号                                    基因型                            变异点                           变异结果

经过以上过程，我们得到了第二代，对其适应度计算如下：

此时，我们已经发现其解的适应度都得到了提升。实际上本轮已经得到了最佳的解{7,7}。

二. 复杂的多目标函数求解

以上我们的目标函数是不存在冲突的，但是有这样一种冲突的情况，两个目标函数一个要求最大，一个要求最小。某个目标函数的提高需要另一个函数降低作为代价，这样就出现了帕雷托解(pareto)。

我们使用遗传算法解决pareto解有以下几种方法：

1.权重系数转换法

对每个目标函数f(xi)(i=1,2,3,4...)赋予权重wi(i=1,2,3.....)，wi为目标函数重要程度。则得到如下线性组合：

这里我们就将多目标转化为单目标函数，将u作为评价函数。

2.并列选择法

主要步骤：(1)将种群按照目标函数个数等分为子种群，为每个子种群分配一个目标函数。(2)将子种群中的个体按照各自的目标函数选择出适应度高的个体，然后将其组成一个子种群。(3)再将子种群进行交配，变异，生成下一代父亲种群。然后，再重复第一步。

并列选择法的缺点在于易于生成单个目标函数的极端最优解，而较难生成一种多个目标在某种程度上都比较满意的折衷解。

3.排序选择法

排序选择法的基本思想是：基于“pareto最优个体”的概念对群体中的个体进行排序，然后根据这个次序进行种群选择。这样的话就能够让pareto最优个体有更多的机会遗传到下一代。这种方法的缺点是仅仅度量了各个个体之间的优越次序，而并未度量各个个体的分散程度，所以容易生成相似的解，而不是分布较广的多个最优解。

4.共享函数法

针对排序选择方法的缺点，即所求的几个最优解通常是集中于最优解集合的某一个小区域内，而不是分散在整个pareto最优解集合。由此，引出了基于共享函数的小生境技术。该算法对相同个体或类似个体是数目加以限制，以便能够产生出种类较多的不同的最优解。这就引出一个问题，怎么衡量两个个体之间的相似度？这就是小生境数。顾名思义，小生境就是在一个小环境中相似的个体种群。最常见的公式为：

s(d)为共享函数，是表示群体中两个个体之间密切关系程度的一个函数。d(X,Y)为个体X,Y之间的hanmin距离，也是用于衡量个体间相似度的一个函数。在计算出小生境数后，可以是小生境数较小的个体能够有更多的机会被选中，遗传到下一代群体中，即相似程度较小的个体能够有更多的机会被遗传到下一代群体中。

其缺点是：每次选择操作时都需要进行大量的个体之间的优越关系的评价和比价较运算，是算法搜索效率较低。

5.Horn和Nafploitis印的基于小生境pareto多目标遗传算法(NPGA)

类似于上面的并列选择法将每一代个体划分为若干类，每个类别选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，然后交配变异产生新一代种群。基于这种小生境的遗传算法（Niched Genetic Algorithms，NGA），可以更好的保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题。

6.Srinvivas和Deb的非支配排序遗传算法NSGA

1980年提出的，在遗传算法的基础上对选择再生方法进行改进：将每个个体按照他们的支配与非支配关系进行再分层，再做选择操作，从而达到目的。这里有几个概念要介绍一下：

pareto支配关系

分层

我理解的分层意思就是取出种群中的非支配个体组成一个小种群(第一个非支配最优层)，并赋予其中所有个体一个共享的虚拟适应度值。然后在取出个体后的种群中继续取出非支配个体，再将它们组成一个小种群(第二个非支配最优层)，并赋予所有个体一个共享的虚拟适应度值。重复以上步骤，直到原始种群分配完毕，这就叫分层，也叫非支配型排序。伪代码如下：

上面说到，我们要指定共享适应度，算法根据适应度共享对虚拟适应度要重新指定。因而需要引出个体共享后的适应度值，以及共享函数和共享半径。具体的公式这里就不展开了，具体想了解可阅读参考文献3的25页。

因此可以发现，非支配型排序遗传算法有如下问题：

1.计算复杂度较高，O(MN**3)M为目标函数个数，N为种群大小。

2.没有精英策略。精英策略可以一定程度上加速算法执行程度，而且在一定程度上保证已经找到的满意解不会丢失。

3.需要指定共享半径。

针对以上问题有学者(k.Deb 2002)提出了用精英策略快速非支配的遗传算法来解决。

7.带精英策略的非支配排序遗传算法一NSGAII

1).采用快速非支配型排序，降低了算法复杂度。其复杂度降为了O(MN**2)。

2).提出了拥挤度和拥挤度比较算子，代替需要指定共享半径的适应度共享策略。并在快速排序后的同级比较中作为胜出标准。使准pareto解中的个体能扩展到整个pareto域中，并均匀分布，保持了种群的多样性。

3).引入精英策略，扩大采样空间。将父代种群和子代种群合并，保证优良个体能够留存下来。

其算法步骤如下：1.首先随机产生数量为n的初始种群，然后对其进行非支配型排序。接下来，就是常规的选择，交叉，变异操作产生第一代子代种群。2.然后，从第二代开始，将父代和子代合并。然后对其进行快速非支配型排序，同时计算每个非支配层的个体进行拥挤度的计算。然后根据非支配关系和拥挤度来选择合适的个体组成新的父代种群。最后通过再通过选择，交叉，变异产生子代。3.接下来，重复第二步。

这里有几个主要的关键技术需要解释一下：

1).快速非支配型排序

2).拥挤度

在原来的NSGA中，我们采用共享函数来确保多样性，但需要共享半径。为了解决这个问题，我们提出了拥挤度的概念：在种群种群中的给定点的周围个体密度，用id表示。它指出了在个体i周围包含个体i本身但不包含其他个体的最小的长方形。

拥挤度计算伪代码：

3).拥挤比较算子

经过快速非支配排序和拥挤度计算，种群中的每一个个体都得到了两个属性：非支配序rankn和拥挤度。利用这两个属性，我们可以区分种群中间任意两个个体间的支配和非支配关系。定义拥挤度比较算子，当且仅当irank>jrank或irank=jrank且id>jd，有个体i优于个体j。

4).精英选择策略

将父代优秀的个体与子代合并。

三.NSGAII的实现

算法流程

代码实现：