文章目录
帕累托多目标遗传算法
代码实现
排序函数
查找所需索引函数
Pareto 法得到帕累托前沿函数
拥挤度计算
从父代和子代中选择下一个父代

帕累托多目标遗传算法
在优化领域，遗传算法绝对占得上一席之地，但由于在染色体选择阶段，俄罗斯轮盘赌法常被使用，因此遗传算法主要被用来解决单优化问题。
对于多目标优化问题，我们常常不知道如何判断两个解孰优孰劣从而难以在遗传算法的选择阶段进行合适的选择，帕累托优化应运而生解决了这一问题。
首先，需要对一下概念进行说明：


支配、非支配：当A所有目标都优于B时，就说A支配了B，否则A和B就是一个非支配的关系；


非支配前沿：种群中所有不被任何其他解支配的解构成了非支配前沿；


其计算步骤如下图所示：



具体来说：

0、随机初始化N个解（父代）；
1、经过交叉变异（与遗传算法中的方法相同）得到N个新解（子代）；
2、将父代与子代混合（精英策略），形成新的解集合S；
3、从S中找出非支配解集合，记为F1；
4、从解集合S中剔除F1，再找出新的非支配解集合，记为F2；
5、重复第四步，直到S为空集；
6、对非支配解进行排序：{F1, F2, …, Fn}；
7、按顺序从排序后的S中取出N个解；
8、假设取到F3集合时，如果F1、F2和F3中解的个数大于N，通过计算F3解集合中每个解的拥挤度由小到大为F3中的所有解排序；
9、按顺序从F3中取解，直到得到新的N个解集（新父代）。

其中，拥挤度计算规则为：

1、取单个前沿中个体按照一个目标上的值从小到大排序；
2、计算对于第m个优化目标的拥挤度：

【注】第一个和最后一个个体的拥挤距离设为无穷大。
3、计算第i个解的拥挤度：


4、拥挤度越大排序越靠前。解之间距离大的解比解之间距离小的解更好，拥挤距离排序用于保持解的多样性。

代码实现
排序函数
根据某个优化目标对解对应的两个目标进行排序：
def sort(F, axis):
    '''
    F：非支配解集合对应的结果
    axis：基于此目标函数对F进行排序
    F_sort：排序后的集合
    '''
    if axis == 0:
        F_sort = F[np.lexsort(F[:,::-1].T)]
    if axis == 1:
        F_sort = F[np.lexsort(F.T)]
    return F_sort

查找所需索引函数
def find_from_array(F, target): 
    '''
    F：非支配解集合
    target：需要在F中寻找的目标
    index：target在F中的索引
    '''
    index = 0
    for f in F:
        if list(f) == list(target):
            break
        index += 1
    if index != F.shape[0]:
        return index

Pareto 法得到帕累托前沿函数
def Pareto(S):
    '''
    S：所有解的集合
    S_small：每个非支配解集
    S_new：用于更新S（将非支配解集去除）
    S_final：包含所有非支配解集的列表
    '''
    Index = np.arange(S.shape[0])
    Index_final = []
    S_final = []  # 初始化包含所有非支配解集的列表
    while S.shape[0]:  # 如果解集合里有解
        Index_small = []
        S_small = []  # 初始化非支配解集
        Index_new = []
        S_new = []
        for i in range(S.shape[0]):  # 遍历解集合中的所有解
            for j in range(S.shape[0]):  # 用于每两个解间的比较
                if (S[i, 0] > S[j, 0] and S[i, 1] >= S[j, 1]) or (S[i, 0] >= S[j, 0] and S[i, 1] > S[j, 1]):
                    break  # 如果不是非支配解则不再考虑这个解
                if j == S.shape[0]-1:  # 如果没有break则这个解是非支配解
                    Index_small.append(Index[i])
                    S_small.append(list(S[i]))  # 将这个非支配解放入S_small
        Index_final.append(Index_small)
        S_final.append(S_small)  # 遍历完一次S后将得到的非支配解集放入S_final列表
        for k, s in zip(Index, S):  # 重新遍历解集合中的所有解
            if find_from_array(np.array(S_small), s) is None:  # 如果这个解不是之前找到的非支配解就将这个解放入S_new列表
                Index_new.append(k)
                S_new.append(s)
        Index = np.array(Index_new)
        S = np.array(S_new)  # 更新S
    return Index_final, S_final

拥挤度计算
def crowding_distance(F):
    '''
    F：非支配解集合
    dist：每个解的拥挤度
    '''
    N = F.shape[0]
    dist_accuracy = np.zeros([N,], dtype=np.float32)  # 初始化基于准确率的拥挤度
    dist_gmean = np.zeros([N,], dtype=np.float32)  # 初始化基于Gmean的拥挤度
    F_accuracy = sort(F, axis=0)  # 基于准确率对F进行排序得到F_accuracy
    F_gmean = sort(F, axis=1)  # 基于Gmean对F进行排序得到F_gmean
    
    for i, f in enumerate(F):  # 遍历解集合F中的所有解
        index_accuracy = find_from_array(F_accuracy, f)  # 找到f解在F_accuracy中的位置
        index_gmean = find_from_array(F_gmean, f)  # 找到f解在F_gmean中的位置
        if index_gmean == 0 or index_gmean == N-1:
            dist_gmean[i] = 1e10
        else:
            dist_gmean[i] = (F_gmean[index_gmean+1, 0] - F_gmean[index_gmean-1, 0])/(F_gmean[N-1, 0] - F_gmean[0, 0])  
        if index_accuracy == 0 or index_accuracy == N-1:
            dist_accuracy[i] = 1e10
        else:
            dist_accuracy[i] = (F_accuracy[index_accuracy+1, 1] - F_accuracy[index_accuracy-1, 1])/(F_accuracy[N-1, 1] - F_accuracy[0, 1])
        
    dist = dist_gmean + dist_accuracy
    return dist

从父代和子代中选择下一个父代
def PopUpdate(Combination, S):
    '''
    S：所有解的集合
    POP：生成的子代
    '''
    POP = []
    S_sort = []
    Index_sort = []
    S_Combination = []
    for s, combination in zip(S, Combination):
        s_combination = []
        s_combination.append(s)
        s_combination.append(combination)
        S_Combination.append(s_combination)
    Index, F = Pareto(S)  # 计算得到所有非支配解集
    pop_size = POP_SIZE
    for index_set, f_set in zip(Index, F):  # 遍历所有非支配解集
        if pop_size == 0:
            break
        if len(index_set) <= pop_size:  # 如果该非支配解集中解的数量小于需要的解个数则直接把该非支配解集中的解放入子代
            S_sort += f_set
            Index_sort += index_set
            pop_size -= len(index_set)  # 更新需要的解的个数
        else:  # 如果该非支配解集中解的数量大于需要的解个数则先计算该非支配解集中每个解的拥挤度再依次放入子代
            dist = crowding_distance(np.array(f_set))  # 计算每个解的拥挤度
            sd = []  # 初始化[解，对应的拥挤度]列表
            for i, d in zip(index_set, dist):
                sd.append([i, d])
            sd_sort = sorted(sd, key=lambda m: m[-1], reverse=True)  # 按照拥挤度对该非支配解集中的解进行排序
            for i in range(pop_size):
                Index_sort.append(sd_sort[i][0])
                S_sort.append(S[sd_sort[i][0]])  # 将该非支配解集中的解按从大到小的顺序放入子代
            pop_size = 0
    for i_sort in Index_sort:
        POP.append(Combination[i_sort]) 
    return np.array(POP)

多目标遗传算法NSGA

因所读的一篇论文中，为了解决多目标的最优解问题，作者使用了一种称为NSGA-II(Improved Non-dominated Sorting Genetic Algorithm)的遗传算法，花了两天时间了解下，此为何物。其中NSGA以及NSGA-II的原理说明内容大部分取自2008年李莉的硕士论文《基于遗传算法的多目标寻优策略的应用研究》，故将此文定为转载。

首先需要了解一种称之为‘dominate’的关系： 

设一个最大化目标函数为F(x)=(F1(x),F2(x),...,Fk(x)), 因为是一个多目标最优的问题，所以这里的目标数量k≥2。假定x0, x1是解空间X中的两个解。如果∃i∈[1,k]使得Fi(x0)>Fi(x1)成立，并且∀i∈[1,k]时，Fi(x0)≥Fi(x1)也成立，那么就称解x0占优(dominate)x1。如果在所有的解空间X中找不到其他能占优x0的解，那么我们称解x0是一个efficient solution。该x0在空间中对应的点，称为 non-dominated point。个人感觉efficient solution其实就是一个Pareto最优解，即，不可能在使得至少一个人收益变得更好情况下而保证其他人的收益不变差。 

一般而言，在多目标优化的问题里， efficient solution往往不是唯一的，那么所有efficient solutions的集合，我们称为efficient set。相对应地，所有non-dominated points组成的点集，称为Pareto front(帕累托前沿)。

题外话：一般多目标规划问题，其实都可以建模为找Pareto 最优解的问题。

在一个庞大的解空间中找出所有的Pareto解(Pareto front)是一个NP-hard问题，因此一些有意思启发式算法就诞生了，而本文这里所讲的遗传算法(Genetic Algorithm)就是其中之一。



NSGA(Non-dominated Sorting Genetic Algorithm)

NSGA非支配排序遗传算法就是一种以基本遗传算法为基础的多目标寻优策略，因为其在多目标寻优领域的优势，成为人们的研究热点。

下面将简要说明NSGA的原理[[1]]。 

NSGA主要由三部分构成，分别为：

种群分层 

假定寻找最大化目标函数为F(x)=(F1(x),F2(x),...,Fm(x))，种群规模为n。 

(1)设i=1； 

(2)对于所有的j=1，2，…，n且j≠i，按照以上定义比较个体xi和个体xj之间的支 

配(dominate)与非支配(non-donimated)关系； 

(3)如果不存在任何一个个体xj优于xi，则xi标记为非支配个体； 

(4)令i=1+1，转到步骤(2)，直到找到所有的非支配个体。 

通过上述步骤得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经 

标记的非支配个体(即这些个体不再进行下一轮比较)，再遵循步骤(1)一(4)，就会得到第二 

级非支配层。依此类推，直到整个种群被分层。
共享小生境技术 

为了在演化过程中保持群体的多样性，NSGA中引入了共享小生境技术。 

假设第p级非支配层上有np个个体，每个个体的虚拟适应度值为fp。 

(1)算出同属于一个非支配层的个体xi和个体xj的欧几里得距离： 
dij=∑l=1l=m(Fl(xi)−Fl(xj)Ful−Fdl)2−−−−−−−−−−−−−−−−−⎷


其中m目标个数，Ful,Fdl分别为Fl的上界和下界。 

(2)共享函数(Sharing Function)是表示两个个体间关系密切程度的函数，两个个体xi和xj间的共享函数sh(dij): 
sh(dij)=⎧⎩⎨⎪⎪1−(dijσshare)α0,dij≤σsharedij>σshare

σshare的值表示了xi与xj群体的相似度。 
dij表示个体xi与xj间的欧式距离。 
α用于对sh(dij)的调整。 

由此可见： 
sh(dij)越大表明二者关系密切，即相似度高 

(3)然后我们计算出节点i与其他所有节点的累积相似度，称为共享度ci: 
ci=∑j=1npsh(dij),i=1,2,...,np


(4)计算出个体xi的共享适应度值: 
f′p(xi)=fp(xi)/ci


同理我们可以计算出所有个体在小生境条件下的适应度，从而提高了种群在演化时的多样性，因为相似度高的种群，其适应度会得到适当地减小。
整体NSGA工作流程如下图所示(至于遗传算法的具体内容，如果以后接触到，再做详细地了解)： 

第九章 基于遗传算法的多目标最优化算法
基础理论
pareto最优解
多目标优化
NSGA一II算法的基本思想
(1) 基本原理
(2) 算法流程
(3) 算法缺陷
2. 带精英策略的非支配排序的遗传算法(NSGA-II)

基础理论
pareto最优解
带精英策略的快速非支配排序遗传算法 NSGA-II 算法

转载：

NSGA-II  pareto（帕累托）最优解

NSGA-II

Paerot支配关系



（较优的解支配次优解）

多目标问题：


帕累托的一个解释

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


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

非支配排序遗传算法(NSGA)

1995年，Srinivas和Deb提出了非支配排序遗传算法(Non-dominated Sorting Genetic Algorithms，NSGA)。这是一种基于Pareto最优概念的遗传算法。

(1) 基本原理
NSGA与简单的遗传算法的主要区别在于：该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别。
在选择操作执行之前，种群根据个体之间的支配与非支配关系进行排序：
首先，找出该种群中的所有非支配个体，并赋予他们一个共享的虚拟适应度值。得到第一个非支配最优层；
然后，忽略这组己分层的个体，对种群中的其它个体继续按照支配与非支配关系进行分层，并赋予它们一个新的虚拟适应度值，该值要小于上一层的值，对剩下的个体继续上述操作，直到种群中的所有个体都被分层。
算法根据适应度共享对虚拟适应值重新指定：
比如指定第一层个体的虚拟适应值为1，第二层个体的虚拟适应值应该相应减少，可取为0．9，依此类推。这样，可使虚拟适应值规范化。保持优良个体适应度的优势，以获得更多的复制机会，同时也维持了种群的多样性。
(2) 算法流程
NSGA采用的非支配分层方法，可以使好的个体有更大的机会遗传到下一代；适应度共享策略则使得准Pamto面上的个体均匀分布，保持了群体多样性，克服了超级个体的过度繁殖，防止了早熟收敛。算法流程如图所示：


(3) 算法缺陷
非支配排序遗传算法(NSGA)在许多问题上得到了应用。但NSGA仍存在一些问题：
a) 计算复杂度较高，为 $O(mN^{3})$ (m为目标函数个数，N为种群大小)，所以当种群较大时，计算相当耗时。
b) 没有精英策略；精英策略可以加速算法的执行速度，而且也能在一定程度上确保已经找到的满意解不被丢失。
c) 需要指定共享半径$\sigma_{share}$。
2. 带精英策略的非支配排序的遗传算法(NSGA-II)
2000年，Deb又提出NSGA的改进算法一带精英策略的非支配排序遗传算法(NSGA-II），针对以上的缺陷通过以下三个方面进行了改进：
a) 提出了快速非支配排序法，降低了算法的计算复杂度。由原来的$O(mN^{3})$降到$O(mN^{2})$，其中，m为目标函数个数，N为种群大小。
b) 提出了拥挤度和拥挤度比较算子，代替了需要指定共享半径的适应度共享策略，并在快速排序后的同级比较中作为胜出标准，使准Pareto域中的个体能扩展到整个Pareto域，并均匀分布，保持了种群的多样性。
c) 引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，并通过对种群中所有个体的分层存放，使得最佳个体不会丢失，迅速提高种群水平。
(1) 基本原理

快速非支配排序法：

NSGA-II对第一代算法中非支配排序方法进行了改进：对于每个个体 i 都设有以下两个参数 n(i) 和 S(i)，
n(i) 为在种群中支配个体 i 的解个体的数量。（别的解支配个体 i 的数量）
S(i) 为被个体 i 所支配的解个体的集合。（个体 i 支配别的解的集合）


首先，找到种群中所有 n(i)=0 的个体（种群中所有不被其他个体至配的个体 i），将它们存入当前集合F(1)；（找到种群中所有未被其他解支配的个体）


然后对于当前集合 F(1) 中的每个个体 j，考察它所支配的个体集 S(j)，将集合 S(j) 中的每个个体 k 的 n(k) 减去1，即支配个体 k 的解个体数减1(因为支配个体 k 的个体 j 已经存入当前集 F(1) )；（对其他解除去被第一层支配的数量，即减一）


如 n(k)-1=0则将个体 k 存入另一个集H。最后，将 F(1) 作为第一级非支配个体集合，并赋予该集合内个体一个相同的非支配序 i(rank)，然后继续对 H 作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。其计算复杂度为$O(mN^{2})$，m为目标函数个数，N为种群大小。（按照1）、2）的方法完成所有分级）


确定拥挤度：

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



拥挤度比较算子:
从图中我们可以看出 $i_{d}$值较小时表示该个体周围比较拥挤。为了维持种群的多样性，我们需要一个比较拥挤度的算予以确保算法能够收敛到一个均匀分布的Pareto面上。
由于经过了排序和拥挤度的计算，群体中每个个体 i 都得到两个属性：非支配序 $i(rank)$和拥挤度 $i_{d}$，则定义偏序关系$\prec _{n}$：当满足条件 $i(rank) <  i_{d}$，或满足 $i(rank) = i_{d}$ 且 $i_{d}> j_{d}$。时，定义$i\prec _{n}j$。也就是说：

如果两个个体的非支配排序不同，取排序号较小的个体(分层排序时，先被分离出来的个体)；如果两个个体在同一级，取周围较不拥挤的个体。
(2) 算法流程


首先，随机初始化一个父代种群P(0)，并将所有个体按非支配关系排序且指定一个适应度值，如：可以指定适应度值等于其非支配序 i(rank)，则1是最佳适应度值。然后，采用选择、交叉、变异算子产生下一代种群Q(0)，大小为N。



如图，首先将第 t 代产生的新种群Q(t)与父代P(t)合并组成R(t)，种群大小为2N。然后R(t)。进行非支配排序，产生一系列非支配集 F(t) 并计算拥挤度。由于子代和父代个体都包含在 R(t) 中，则经过非支配排序以后的非支配集 F(1) 中包含的个体是 R(t) 中最好的，所以先将 F(1) 放入新的父代种群 P(t+1) 中。如果 F(1) 的大小小于N，则继续向 P(t+1) 中填充下一级非支配集 F(2)，直到添加 F(3) 时，种群的大小超出N，对 F(3) 中的个体进行拥挤度排序$(sort(F(3),\prec _{n}))$，取前$N-\left | P(t+1)) \right |$个个体，使 $P(t+1)$ 个体数量达到N。然后通过遗传算子(选择、交叉、变异)产生新的子代种群 $Q(t+1)$。
算法的整体复杂性为$O(mN^{2})$，由算法的非支配排序部分决定。
通过介绍非支配排序遗传算法(NSGA)及其改进算法NSGA-II的基本原理和流程，我们了解到NSGA-II解决了NSGA中存在的3个问题：降低了计算复杂度；引入精英策略；采用拥挤度及其比较算子代替了共享半径。使得NSGA-Ⅱ在处理多目标优化问题上有更好的性能。

遗传算法
        遗传算法在多目标优化问题处理中应用广泛，它的基本特征是通过在代与代之间维持由潜在解组成的种群来实现多向性和全局搜索，通过种群基于遗传的进化，实现潜在解向最终解的演变，这种种群到种群的方法在搜素Pareto解时是很有用的。
        遗传算法可以处理所有类型的目标函数和约束，不受制于他们的数学属性，可以在不考虑特定内部工作方式的前提下搜索解，因此在求解复杂问题解上比传统优化算法应用更多，可用性也更广。遗传算法作为启发式算法在处理单目标优化问题表现很好，后来逐渐的被引入多目标优化问题处理，现如今基于遗传算法的改进算法蓬勃发展，所以学习了解遗传算法是有必要的。



算法介绍
1. 算法结构
        算法过程如下：



        算法整体结构：





2. 结构分析
①初始种群的生成
       遗传算法是对种群进行操作的，初始种群的选择影响着算法的最终性能，所以初始种群的选择尤关重要。在处理实际问题时，问题的最优解在解空间的分布情况是不清楚的，所以设计初始种群时尽量设计成在解空间均匀分布（想法：参考自然界的进化规律，地球生物演化的起点是简单单细胞生物，是否可以以此参照设计初始种群，如从单个种群开始保持高突变率来演化成多种群，这样计算复杂度肯定高了但是否性能会变好？）。初始种群的个数是种群规模，依据问题复杂性，问题越复杂，目标空间维数越高，种群规模越大，反之亦然。常规的种群生成规则如下：
       有先验知识：利用先验知识在决策空间的生成均匀分布的初始种群。

       无先验知识：首先随机生成一定规模的初始种群，然后选取一部分适应度最好的，一小部分最差的，一小部分适中的个体，如此循环，直到种群规模满足要求。
②个体编码
       编码就是把实际问题变量转化成计算处理的决策空间变量，反之，把决策空间的解转成问题空间的解叫解码。编码的要求有三：
       （1）完备性：问题空间的任意解可以单射到决策空间。

       （2）健全性：决策空间的解可单射到问题空间的解。

       （3）非冗余性：问题空间的解和决策空间的解相互满射。
       编码的方法有多种，最有效最常用的是实数编码，其基因型空间中的拓扑结构与其表现型空间中的拓扑结构一致，因此很容易借鉴传统优化方法中的技术。根据实数编码，种群$P(t)$可以描述为：
       $P(t)=${$x_{t,1},x_{t,2}\cdots x_{t,pop}$}

       $x_{t,j}=${$(x_{t,j,1},x_{t,j,2}\cdots x_{t,j,n})|x_{t,j,1},x_{t,j,2}\cdots x_{t,j,n}{ \in }\ min+(max-min)rand(1)$

       $j\in1,2,\cdots,pop$
       $pop$是种群规模，种群中的每个个体$x_{t,j}$由$n$个参数衡量，且这$n$个参数有上下限。$rand(1)$表示0到1随机数。
③评估函数设计
       评估函数是计算评估个体的适应度，从而决定个体是否参与杂交或繁殖其他操作的。适应度是进化论里的概念，表示的是个体对环境的适应程度，在算法中，就是表示个体解的优劣性。适应度越高，表示个体存活的概率越大，也就是更可能参与繁殖。评估函数的形式取自于具体的优化函数，具体有以下要求：
       性质：非负，连续，满射，单点极值。

       简单：尽可能减少计算量

       可拓展性：争对具体问题设计的评估函数可以被其他问题使用。

       有效性：能过区分种群个体的优劣性。
       评估实际就是个体做标签，作为给算法进行下步处理的参考依据。评估函数计算得出的适应度是可以调整的，如共享函数，可以用来降低个体的适应度来控制种群的多样性。
④繁殖机制
       整个繁殖机制包括选择，杂交和变异三部分。
       选择：按照一定策略从当代种群中选取一部分个体进行下部操作。如上文所说的，依照适应度，通过诸如轮盘赌，$(\mu +\lambda)$选择，锦标联赛，Pareto支配关系，共享等方式，以生成待繁殖群。选择方式的特征有随机性和确定性两种，前者表现为对当代种群的个体，无论适应值好坏，都有被选择的概率。如轮盘赌，依据适应值比例确定个体的被选概率；后者表现为对当代种群个体的选择是依据适应度而确定的，适应度坏的个体不会被选择。大多选择方式是两者特征的结合，如锦标联赛方式，从随机选择的个体中选取适应度好的。
       选择过程在整个繁殖机制的基础，它指明着种群的未来进化方向。也就是说，选择的好坏影响着算法解的收敛性和分布性。各种选择方式都遵循“精英保留”原则，保留有前途的个体，这是保证收敛性的操作，然而这种操作也有可能发生有限解收敛到同一个最优解（在单目标问题中，表现为陷入局部最优）的情况，共享方式就是争对这种情况在选择阶段做出改进的方式。通过共享函数，降低聚集区域个体的适应度，从而提高其他个体的被选概率。选择结果的理想状况应是：选取的个体群尽可能表现最好，尽可能分散，尽可能全域覆盖。
       杂交：通过当代选择个体群（父代）产生下代种群（子代）。仿照生物界的有性生殖（无性繁殖可不可以仿照？区别于变异的单点进化，如父代首先自我变异，然后父子代个点自我交叉。），产生的子代继承了父代的优良基因，在算法上表现为计算之后的点可能会更加地接近理论最优值，也可能会偏离，但不会严重偏离，同时这种偏离也可能会产生另一个Pareto最优解，因此杂交也体现着算法的收敛性和多样性。对不用的编码方式，杂交算子的设计不同，算子的设计也有随机和确定两种特征。这里介绍NSGA-Ⅱ中基于实数编码的随机算子设计方式：算数杂交。
       根据凸集理论：如果可行域是凸的，则可行域中两点连线上的点也在可行域中。对于向量$x_1$,$x_2$，它们的加权平均为  $\lambda_1$$x_1$+$\lambda_2$$x_2$，乘子限制为 $\lambda_1$+$\lambda_2=1$。算数杂交定义的两个向量组合是：
                                                                                         $x_1^{'}=\lambda_1$$x_1$+$\lambda_2$$x_2$

                                                                                         $x_2^{'}=\lambda_1$$x_2$+$\lambda_2$$x_1$
       其中$\lambda_1$，$\lambda_2$的设计为
                                                                                         $\lambda_1=0.5(1+bq)$

                                                                                         $\lambda_2=0.5(1-bq)$



        $mu=20$是杂交分布指数。
       变异：子代个体的随机变化。杂交之后的子代可能会发送陷入同一最优，过早收敛或不成熟收敛的情况，变异算子可以有效解决上述问题。还是以NSGA-Ⅱ中的变异算子为例，对于向量$x$，变异方式为：
                                                                                    $x^{'}=x+\delta$

                                                                         $\delta=|2rand(1)^{\frac{1}{mum+1}}-1|$
        $mum=20$是变异分布指数。
       整个繁殖机制是算法的核心，可以看出机制的设计处处体现了算法的收敛性和多样性，这也是整个算法的核心思想，大多的基于遗传算法的改进也是从这两方面入手的。宏观上来说，繁殖机制是解计算中的搜索阶段，算法设计原则是更快更好更分散的计算出最终解。杂交过程的作用是在编码空间中进行全局搜索，以最快速度找到PF面上各点（单目标中是全局最优），变异过程提供了加快每个PF点的收敛速率的可能（主要还是保证多样性），提高了算法的局部搜素能力。



3.总结
       对于问题解的搜索，有两种行为模式，一种是全局搜素：广泛搜索整个解空间并且向同一最优逃离；令一种是局部搜索：深度搜索最优解并且向局部最优爬山。显然遗传算法是一种结合两种模式的通用搜易方法，因此在多目标优化问题中得到了最为广泛的应用。


Tips：
通过类比，更好理解多目标优化与单目标优化的联系和区别：




单目标优化
多目标优化




局部最优
有限解集收敛到同一最优解


全局最优
有限解集分散构成PF面