前面我们已经对简单遗传算法SGA和针对组合优化的遗传算法AGGA进行了一些说明，如果理解这篇文章遇到困难，不妨先点击以下两个链接：

当结构设计遇到遗传算法，于是它学会了自己进化！

如何教会房子学会自己设计自己的基础——当结构设计遇到遗传算法（二）

下面先简单扒一扒多目标优化问题的历史

关于多目标优化问题最早要追溯到1881年的一本叫做《数学心理学》的书，作者为Francis Y Edgeworth，一位对数学，伦理学，哲学等感兴趣的牛津大学的老师，是一个著名家族男性一系的几乎最后一员，这里不深扒了。不起眼的一本150页的薄薄的将数学应用到道德科学中的书，书中所提到的多准则优化问题就是我们今天熟知的Pareto最优问题。

随后在1897年，意大利经济学家Pareto在对19世纪英国人的财富和收益模式的调查中，发现了我们现在熟知的二八定律。在研究经济效率的过程中，Pareto提出了以他名字命名的Pareto最优概念。

Pareto实际上和我们是一个专业的，是意大利铁路公司的工程师，并且在43岁之前成为了意大利铁路公司的总经理，43岁的时候读了《纯粹经济学原理》，立马转行了，不过他也没想到后来又有很多的人将他提出的概念应用到土木行业的优化中去。

在此之后，主要的工作是博弈论理论的扩充，Pareto最优是博弈论中的一个重要的概念。上世纪九十年代和新世纪之初，一些将进化算法和此概念相结合的学者开始比较活跃，很多相关的算法被提出，最突出的就是Deb大神提出的NSGA-Ⅱ，一种快速非支配排序和带精英策略的遗传算法，被引用2.3万余次。

在说明NSGA-Ⅱ之前，先回顾和熟悉一下SGA和NSGA-Ⅱ处理结构问题的一般流程。

SGA处理结构问题的一般流程：

NSGA-Ⅱ处理结构问题的一般流程：

可以发现，和SGA相比，NSGA-Ⅱ似乎少了定义适应度的环节，取而代之的是对解进行排序，同时增加了精英策略。

下面开始详细说明：

1.会首先结合建筑结构设计问题，简单介绍Pareto最优解的概念

2.然后介绍NSGA-Ⅱ所使用的寻找Pareto最优解的方法（快速非支配排序、拥挤排序）

3.接着会对为适配结构离散变量所使用的遗传算法编码、选择、交叉、变异操作和精英策略

4.以及NSGA-Ⅱ处理约束的方法进行说明：

一、如何通俗地解释「帕累托最优」（Pareto optimum）？

这里引用了知乎上的一个提问。

这是最高票的回答，答得非常短和准确，但是一下还是不能知道答主在说什么。我们看下第二高票徐老师的回答：

看完徐老师的回答，再细想一下我们结构师所面临的问题，比如说建筑师希望房子的柱子越细越好，但是结构的指标各种算不过。很多时候存在某些柱子细一点，指标不会变坏，甚至会变更好的情况，这相当于徐老师的举例2，这说明结构还有优化的空间，还未得到最优解。

因此对于结构设计来说，当我们得到一个解，无论对于什么组合方式，任何一根柱子再细一点，都会导致指标超限，那么这个解就是Pareto最优解，这就相当于徐老师的举例1，因为此时柱子要想越细必然会以超限为代价，非损结构师不能利建筑师。

那么如何找到Pareto最优解呢？

二、快速非支配排序

对于最小值优化问题，

假设有两个目标obv1，obv2

经过计算，得到一组解如下：

很明显，五个解，从①到⑤是越来越差的，

最优解明显为解①

假如得到的是这样另外一组解，请看下边

为了区分他们，用红色表示

我们将所有解都和解①进行比较

①和②相比，②为较优解

①和③相比，很难说哪一个解更好

①和④相比，也不好说

①和⑤相比，当然①为较优解

我们几乎轻而易举地得出了以上的结论，默默回顾一下，我们的大脑是经过什么样的计算而得到如此精准的结论的

当解不止5个，有甚至成千上万个的时候，我们的大脑开始抗拒了，因为它更希望将这个时间用于吃饭睡觉打排位。

于是没办法，我们要让电脑学会自己判断，为此，我们定义了支配关系和Pareto层级的概念。

对于求最小值的多目标优化问题，

当我们遇到解①和⑤这样的情况的时候，我们称解①支配解⑤

遇到解①和解②这样的情况的时候，我们称解①被解②支配。

也就是说，对于两个解，当其中一个解的所有目标值都优于另一个解的时候，则称这个解支配另一个解。

如果我们接着上面的工作，将解②和所有解进行比较，完事儿了之后接着比解③，直到所有解都比了一遍，这样我们会得到每个解的支配的解的集合以及此解被支配的总数n，

那么那些被支配数n都为0的解（就是谁也支配不了它们），就是这组解的最优解（前沿面）。

我们将这些解称为同一Pareto层级的解，且为第一级。

接着我们将所有解的被支配的解总数n都减1，这样又得到一组被支配数都为0的解，这些解就是第二层级的解

以此类推，直到所有解的n都≤0，快速非支配排序就完成了。

之所以称之为快速非支配排序，是因为与Deb大神和他的学生最先提出的NSGA相比，NSGA-Ⅱ排序的计算复杂度小了一个量级，好奇的朋友可以看论文。

三、小生镜

在了解NSGA-Ⅱ的拥挤排序之前，我们先了解一下生物学上的小生境概念。

小生境是指特定环境下的一种生存环境。生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代；如果离开了此特定的环境之后，往往无法继续生存。

例如：

热带鱼不能在较冷的地带生存，而北极熊也不能在热带生存。

蜜蜂离开花粉则无法生存，老鹰离开小鸡也会不开心。

我们人类则可以说是个奇异解，因为我们不仅站在食物链的顶端，还可以上刀山下火海哈哈哈

在实际的多目标优化问题上，我们要避免最后得到的一组解全部是热带鱼而没有北极熊，我们希望能够得到丰富多样的解。

那么如何做到热带鱼和北极熊兼得呢？

Goldberg等在1987年模仿小生境的现象，提出了基于共享机制（Sharing）的小生境实现方法，通过共享函数来评价个体之间的相似程度，以此为基础调节个体的适应度，越相似的个体，其适应度就越小，NSGA就是采用的这种方法维持种群的多样性，感兴趣的朋友可以直接看论文。

那么NSGA-Ⅱ如何实现维持种群多样性？

四、拥挤排序

为了能够保持解的多样性，Deb大神和他的学生们提出了拥挤距离指标用以度量每个解周围不被其他解占有的搜索空间，以此为基础对解进行比较排序。

与共享函数相比，此方法不需要人定义任何参数，而且计算复杂度较小。

上图为以两个目标函数值为坐标轴的搜索空间，实心圆点为第一层级的解（前沿面），第i个解的拥挤距离即图示虚线矩形的周长。

经过前述的快速非支配排序后，每个解的优秀程度已经被按照Pareto层级归好类了，接着为了保持解的多样性，对每个层级的个体，首先赋予边界解的拥挤距离为无穷大，确保边界解总是被保留，然后依据每个解拥挤距离的大小进行排序，距离越大则越靠前。

至此所有解都按照支配关系以及拥挤距离排好序，层级数为1的解肯定优层级数为2的解，同一层级的解，则拥挤距离越大越优秀。

四、编码

为了和结构问题大量的离散变量相适配，采用实数编码

算法首先接收到用户定义的一个属性列表

列表包括每个属性的下界和上界以及属性可以调整的步长：[下界，上界，步长]

例如[[-2000, 2000, 100], [0, 4000, 200]]

上例用户定义了两个变量，这可以是结构建模信息中的任何属性

比如某个梁高和某组墙厚

第一个属性，下界和上界为-2000和2000，规定了属性可以调整的范围，步长为100，表示此属性将以100为模数进行调整

然后算法会根据用户定义的种群规模N随机生成第一代种群

比如N为100

算法就会随机生成100组像[-1500,1600]这样的数，每一组代表种群中的一个个体，每一个个体对应一个结构计算模型

这些数均以用户指定的步长生成，并且在边界范围内

有时会出现用户定义的属性的边界和步长不匹配的情况，例如[0, 220, 50]

此时算法就会自动修改上界为[0,200,50]

我们采用二单元锦标赛选择法：

和基于比例选择的轮盘赌选择法不同，锦标赛选择顾名思义，算法首先从种群中选择一定数量的一组解，让他们比赛，然后选出其中的最好的放入新种群，接着重复这个操作，直到新种群的规模达到用户指定的规模。

二单元锦标赛选择顾名思义，就是每次选择的一组解的数量为2。

六、交叉

交叉操作是遗传算法中一个很重要的操作，因为它会在每一代被选出的优秀种群内的每一个个体附近进行搜索，不断产生新的种群，

这样可以确保种群不断地向最优解进化，最终收敛于最优解，而不是处于无序发散的状态。

在说明本算法所采用的交叉算子之前，先来认识一下传统二进制编码下的单点或多点交叉操作。

随机给出两个二进制个体：

110110001

对应十进制：433

011010110

对应十进制：214

看完上面的例子相信各位工程师已经大概了解二进制编码下的交叉算子，是如何实现在解的附近进行搜索的了，但是我们采用的十进制编码

Deb等人提出了一种针对十进制编码的模拟二进制单点交叉操作的算子Simulated binary crossover (SBX)，并应用于NSGA-Ⅱ。

首先给出两个父代个体：

要通过SBX计算得到两个子代个体：

先定义分布参数：

再定义概率分布函数：

得到概率分布

之后，通过下式计算得到后代：

从上图可以看出，概率分布函数中的参数

取得越大，得到的子代个体则越接近父代（局部搜索），越小则越远离父代（多样性搜索）

从上图还可以看出，概率分布是个连续平滑的曲线，这意味着得到的后代也是随机连续的个体，但是我们的编码是针对带步长的离散变量，怎么办？

交叉也可以称重组，交叉实际上属于重组的一种，

其实针对实数编码和离散变量的重组方法有很多，比如重组算法的代表：离散重组法

离散重组法直接在交配过程中交换个体的变量值，这符合交叉的本意，例如：

父个体1：13 24 5

父个体2：124 3 24

生成的子个体可以是：124 24 24。

很明显离散重组法，无法产生子代和父代个体所包含的变量值以外的变量，搜索能力较弱

除了离散重组法，还有经典的实数值重组法，它包括中间重组、线性重组等也称整体算术交叉，线性算术交叉，前述的模拟二进制交叉法（SBX）也属于实数值重组（算术交叉）

下面是中间重组生成子代的计算公式：

其中αi是[-d,1+d]之间的随机数

和模拟二进制交叉（SBX）相比其实类似，只不过中间重组法产生的子代不会以事先定义好的概率分布函数产生，而是会随机均匀分布在由αi确定的区间内

当d取为0的时候，子代可能的区域就和父代所包括的区域一致，各位工程师可以随机取两个值试一下，

由于生成初始种群时，不可能每次都能得到位于边界的个体，随着进化的进行，会出现搜索空间不断缩小的现象，当d取为0.25时，则在统计学上能够保证子代个体的搜索范围和父代相比不会变小。这样可能的后代会如下图所示：

线性重组则和中间重组类似：

区别在于线性重组只有一个α，而不是一组随机数，这样会导致可能的后代呈线性分布：

看到这里细心的工程师会发现，不论是何种算术交叉，都是会对子代预先定义一个分布规律，线性重组则按线性分布，模拟二进制交叉的（SBX）则以实现定义好的概率分布函数分布，当然也可以采用其他概率分布函数，例如当采用标准正态分布函数时，就成了“正太分布交叉”。

为了和结构离散变量相适应，暂时选用中间重组法，并且取d为0.25，也称整体扩展算术交叉。

同时，为了保证随机生成的子代能和用户定义的属性列表保持一致，即按照事先定义好的边界范围内按步长生成，本算法对随机数αi以及越界个体进行了处理，使其能够随机生成满足结构变量离散且带步长需求的子代。

七、变异

变异操作在遗传算法中提供全局搜索的能力，避免进化进入局部最优

当选择机制和交叉操作共同工作，不断趋近于一个最优解的的时候，光靠它们两个算子是没办法跳脱那个局部最优的，因为交叉只能在父代决定的搜索空间进行搜索，这个时候就该基因突变了，变异算子开始起作用，变异意味着会在整个搜索空间随机生成一个个体，若发现更好的解，便成功跳脱了局部最优。

本算法采用和前述采用的实数编码方法匹配的变异算子。

八、精英策略

由于父代经过随机的选择、交叉、变异后产生的子代，很可能导致原父代的最优个体被破坏流失，为了增加进化的收敛能力引入精英策略

精英策略顾名思义，就是将父代最好的个体即精英保留，并加入子代种群继续参与进化。

NSGA-Ⅱ采用的精英策略思路为：

将子代和父代种群合并，产生一个2N规模的种群，然后对其进行支配排序和拥挤排序，分出优劣后，

将最优的前N个个体提取，以产生子代种群继续进化。

九、约束处理

看完前面的，已经基本掌握了本算法的工作原理，但是在我们实际的优化问题中，往往存在约束条件，怎么处理约束条件呢？

Deb和他的学生提供了一个很好的思路。

当存在约束的时候，如果从种群中随机提取出两个解，会出现最多三种情况：

1.两个解都是可行的

2.一个解可行，另一个解超限

3.两个解都超限

模仿前面的Pateto支配关系的定义，Deb和他的学生重新定义了一个约束支配关系：

现在有两个解a和b：

如果存在下面三种情况中的任何一种：

1.a 是可行的，b是超限的

2.a 和b都是超限的，但是b对所有约束条件的违反程度之和大于a

3.a 和b都是可行的，但是在Pateto支配关系中，a支配着b

则说明解a支配b

本算法会将用户定义的约束条件全部转换为≤0的形式，形成一个约束矩阵，当矩阵所有元素值都小于0则代表可行，否则超限，并可计算出违反程度。

对于具体的建筑结构优化问题，任何指标限值可以被用户定义为优化目标，也可以被定义为约束。

当定义为优化目标时：

比如说，同时定义材料用量和层间位移角为优化目标：材料用量希望最小，层间位移角目标值是1/550，

此时算法就会将目标转换为求最小值问题进行优化，比如将目标转换为层间位移角的计算结果与1/550之差的绝对值。

当定义为约束时，

优化结果会优先将不超限的解保留，层间位移角将不会被作为优化的目标，此时不论层间位移角多么保守，只要出现材料用量更小的解，则为更优。