遗传算法导图

❶ 遗传算法--GA

        遗传算法（GA）属于 人工智能启发式算法 ，启发式算法的目标就是 寻找原始问题的最优解 ，该算法的定义为

         人类通过直观常识和生活经验，设计出一种以搜索最优解为目的，通过仿真大自然规律的算法，该算法在可以在接受的花销（计算时间和存储空间）范围内找到问题实例的一个可行解，且该可行解和真实最优解的误差一般不可以被估计

        当下主要有的启发式算法包括 遗传算法、退火法，蚁群算法、人工神经网络等 ，这篇文章主要介绍遗传算法

        遗传算法的基本原理是模拟达尔文进化论 "物竞天择，适者生存" 的自然法则，其核心思想为

（1）将原始问题的参数，抽象为基因编码

（2）将原始问题的可行解，抽象为基因排列的染色体组合

（3）将原始问题的解集规模，抽象为一定数量染色体组成的种群

（4）寻找可行解的过程，抽象为种群的进化过程（染色体选择、交叉、变异等）

（5）比较可行解的优劣，抽象为量化比较不同种群对当前环境的适应程度

（6）逼近最优解的过程，抽象为淘汰适应度差的种群，保留适应度高的种群进行下一次进化

（7）问题的最优解，抽象为经过多次进化后，最终生存下来的精英种群

        理论上，通过有限次种群进化，生存下来的种群都是 精英染色体 ，是最适合当前环境条件的种群，也就可以无限逼近原始问题的最优解

相关生物学术语：

    为了大家更好了解遗传算法，在此之前先简单介绍一下相关生物学术语，大家了解一下即可。

基因型(genotype)：性状染色体的内部表现；

表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；

进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。

适应度(fitness)：度量某个物种对于生存环境的适应程度。

选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。

复制(reproction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。

交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；

变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。

编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。

解码(decoding)：基因型到表现型的映射。

个体（indivial）：指染色体带有特征的实体；

种群（population）：个体的集合，该集合内个体数称为种群

大体实现过程

遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。 遗传算法的实现过程实际上就像自然界的进化过程那样。

基本遗传算法概述

    1.[开始]生成n个染色体的随机群体（适合该问题的解决方案）

    2.[适应度]评估群体中每个染色体x的适应度f（x）

    3.[新种群]通过重复以下来创建新种群直到新种群完成的步骤

        3.1 [选择]根据种群的适合度选择两个亲本染色体（更好的适应性，更大的选择机会）

        3.2 [交叉]以交叉概率跨越父母形成新的后代（儿童） ）。如果没有进行交叉，后代就是父母的确切副本。

        3.3 [突变]突变概率突变每个基因座（染色体中的位置）的新后代。

    4.[接受]在新种群中放置新后代[替换]使用新生成的种群进一步运行算法

    5.[测试]如果满足结束条件，则停止并返回当前种群中的最佳解

    6。[循环]转到步骤2

影响GA的因素

    从遗传算法概述可以看出，交叉和变异是遗传算法中最重要的部分。性能主要受这两个因素的影响。在我们解释有关交叉和变异的更多信息之前，我们将给出一些有关染色体的信息。

染色体编码

染色体应该以某种方式包含它所代表的解决方案的信息。最常用的编码方式是二进制字符串。然后染色体看起来像这样：

每个染色体由二进制字符串表示。字符串中的每个位都可以表示解决方案的一些特征。另一种可能性是整个字符串可以表示一个数字 - 这已在基本的GA小程序中使用。当然，还有许多其他的编码方式。编码主要取决于解决的问题。例如，可以直接编码整数或实数，有时对某些排列等进行编码很有用。

染色体交叉

在我们确定了将使用的编码之后，我们可以继续进行交叉操作。 Crossover对来自亲本染色体的选定基因进行操作并产生新的后代。最简单的方法是随机选择一些交叉点，并在此点之前从第一个父项复制所有内容，然后在交叉点之后复制另一个父交叉点之后的所有内容。交叉可以说明如下:( |是交叉点）：

还有其他方法可以进行交叉，例如我们可以选择更多的交叉点。交叉可能非常复杂，主要取决于染色体的编码。针对特定问题进行的特定交叉可以改善遗传算法的性能。

4.染色体突变

在执行交叉之后，发生突变。突变旨在防止群体中的所有解决方案落入解决问题的局部最优中。突变操作随机改变由交叉引起的后代。在二进制编码的情况下，我们可以将一些随机选择的位从1切换到0或从0切换到1.突变可以如下所示：

突变（以及交叉）技术主要取决于染色体的编码。例如，当我们编码排列时，可以将突变作为两个基因的交换来进行。

GA的参数

    1.交叉和突变概率

    GA有两个基本参数 - 交叉概率和变异概率。

     交叉概率 ：交叉的频率。如果没有交叉，后代就是父母的精确副本。如果存在交叉，则后代由父母染色体的部分组成。如果交叉概率为100％，那么所有后代都是由交叉产生的。如果它是0％，那么全新一代都是从旧种群的染色体的精确拷贝制成的（但这并不意味着新一代是相同的！）。交叉是希望新染色体将包含旧染色体的良好部分，因此新染色体将更好。但是，将旧人口的一部分留给下一代是好的。

     突变概率 ：染色体部分突变的频率。如果没有突变，则在交叉（或直接复制）后立即生成后代而不进行任何更改。如果进行突变，则改变染色体的一个或多个部分。如果突变概率为100％，则整个染色体发生变化，如果是0％，则没有变化。突变通常会阻止GA陷入局部极端。突变不应该经常发生，因为GA实际上会改变为随机搜索。

    2.其他参数

     种群规模 ：种群中有多少染色体（一代）。如果染色体太少，GA几乎没有可能进行交叉，只探索了一小部分搜索空间。另一方面，如果染色体太多，GA会减慢。研究表明，经过一定的限制（主要取决于编码和问题），使用非常大的种群是没有用的，因为它不能比中等规模的种群更快地解决问题。

     3      选择

正如您从GA概述中已经知道的那样，从群体中选择染色体作为交叉的父母。问题是如何选择这些染色体。根据达尔文的进化论，最好的进化能够创造出新的后代。选择最佳染色体的方法有很多种。例如轮盘赌选择，Boltzman选择，锦标赛选择，等级选择，稳态选择和其他一些选择。

1.轮盘赌选择

父母根据他们的健康状况选择。染色体越好，它们被选择的机会就越多。想象一下轮盘赌轮，人口中的所有染色体都放在那里。轮盘中截面的大小与每条染色体的适应度函数的值成比例 - 值越大，截面越大。有关示例，请参见下图。

轮盘赌中放入一块大理石，并选择停止的染色体。显然，具有较大适应值的染色体将被选择更多次。

该过程可以通过以下算法来描述。

[Sum]计算总体中所有染色体拟合度的总和 - 总和S.

[Select]从区间（0，S）-r生成随机数。

[循环]遍历总体并从0 - 总和中求和。当总和s大于r时，停止并返回您所在的染色体。当然，对于每个群体，步骤1仅执行一次。

2.排名选择

当健身值之间存在很大差异时，先前的选择类型会出现问题。例如，如果最佳染色体适应度是所有拟合度总和的90％，那么其他染色体将很少被选择的机会。等级选择首先对群体进行排序，然后每个染色体接收由该等级确定的适合度值。最差的将是健身1，第二个最差的2等等，最好的将具有适应度N（人口中的染色体数量）。您可以在下面的图片中看到，在更改适应性与排名确定的数字后情况如何变化。

排名前的情况（适合度图）

排名后的情况（订单号图）

现在所有染色体都有机会被选中。然而，这种方法会导致收敛速度变慢，因为最好的染色体与其他染色体的差别不大。

3.稳态选择

这不是选择父母的特定方法。这种选择新种群的主要思想是染色体的很大一部分可以存活到下一代。稳态选择GA以下列方式工作。在每一代中，选择一些好的（具有更高适应性）染色体来创建新的后代。然后去除一些不好的（具有较低适合度）染色体并将新的后代放置在它们的位置。其余人口幸存下来。

4.精英

精英主义的想法已经被引入。当通过交叉和变异创建新的种群时，我们有很大的机会，我们将失去最好的染色体。精英主义是首先将最佳染色体（或少数最佳染色体）复制到新种群的方法的名称。其余人口以上述方式构建。精英主义可以迅速提高GA的性能，因为它可以防止丢失最佳找到的解决方案。

交叉(Crossover)和突变 (Mutation)

交叉和变异是GA的两个基本运算符。 GA的表现非常依赖于它们。运算符的类型和实现取决于编码以及问题。有多种方法可以执行交叉和变异。在本章中，我们将简要介绍一些如何执行多个编码的示例和建议。

1.二进制编码

交叉

单点交叉 - 选择一个交叉点，从第一个父项复制从染色体开始到交叉点的二进制字符串，其余从另一个父项复制

选择两点交叉 - 两个交叉点，从第一个父节点复制从染色体开始到第一个交叉点的二进制字符串，从第一个父节点复制从第一个交叉点到第二个交叉点的部分，其余的是再次从第一个父级复制

均匀交叉 - 从第一个父项或第二个父项中随机复制位

算术交叉 - 执行一些算术运算以产生新的后代

突变

位反转 - 选择的位被反转

2.置换编码

交叉

单点交叉 - 选择一个交叉点，将排列从第一个父项复制到交叉点，然后扫描另一个父项，如果该数字还没有在后代中，则添加它注意：还有更多方法如何在交叉点之后产生休息

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

变异

顺序更改 - 选择并交换两个数字

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

3.值编码

交叉

可以使用来自二进制编码的所有交叉

变异

添加一个小数字（用于实数值编码） - 将一个小数字添加到（或减去）所选值

（1.29 5.68 2.86 4.11 5.55）=>（1.29 5.68 2.73 4.22 5.55）

4.树编码

交叉

树交叉 - 在父母双方中选择一个交叉点，父母在该点被分割，交换点下面的部分被交换以产生新的后代

变异

更改运算符，数字 - 选定节点已更改

补充:

疑惑点：

初始种群是啥：

利用二进制（一般）表示最终解

例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}

用六位二进制数表示由x，y组成的解，例如：001100 表示x=1，y=4

001100 称为一条基因序列，表示的是该问题的一种解决 方案

种群是包含多个基因序列（解决方案/个体）的集合

适应度函数是啥，有什么作用：

适应度函数可以理解成“ 游戏 规则”，如果问题较为复杂，需要自定义适应度函数，说明如何区分优秀与不优秀的个体; 如果问题比较简单，例如上述求最大值的问题，则直接用此函数式作为适应度函数即可。作用：评定个体的优劣程度，从而决定其遗传机会的大小。

怎么选择：

定义“适者生存不适者淘汰”的规则，例如：定义适应度高的被选择的概率更大

怎么交叉：

利用循环，遍历种群中的每个个体，挑选另一个体进行交叉。例如，通过遍历为基因序列A挑选出B配对，则取A的前半部分，B的后半部分，组合成新的个体（基因序列）C

如何变异：

随机挑选基因序列上的某一位置，进行0-1互换

建议 GA的参数

如果您决定实施遗传算法，本章应该为您提供一些基本建议。这些建议非常笼统。您可能希望尝试使用自己的GA来解决特定问题，因为没有一般理论可以帮助您针对任何问题调整GA参数。

建议通常是对GA的经验研究的结果，这些研究通常仅在二进制编码上进行。

交叉率

交叉率一般应高，约为80％-95％。 （但是有些结果表明，对于某些问题，交叉率约为60％是最好的。）

突变率

另一方面，突变率应该非常低。最佳利率似乎约为0.5％-1％。

人口规模

可能令人惊讶的是，非常大的人口规模通常不会改善GA的性能（从找到解决方案的速度的意义上说）。良好的人口规模约为20-30，但有时大小为50-100是最好的。一些研究还表明，最佳种群规模取决于编码字符串（染色体）的大小。这意味着如果你有32位染色体，那么人口应该高于16位染色体。

选择

可以使用基本的轮盘赌选择，但有时排名选择可以更好。查看有关选择优缺点的章节。还有一些更复杂的方法可以在GA运行期间更改选择参数。基本上，这些表现类似于模拟退火。如果您不使用其他方法来保存最佳找到的解决方案，则应确保使用精英主义。您也可以尝试稳态选择。

编码

编码取决于问题以及问题实例的大小。查看有关编码的章节以获取一些建议或查看其他资源。

交叉和变异

运算符取决于所选的编码和问题。查看有关操作员的章节以获取一些建议。您还可以查看其他网站。

搜索空间

    如果我们正在解决问题，我们通常会寻找一些最好的解决方案。所有可行解决方案的空间（所需解决方案所在的解决方案集）称为搜索空间（也称为状态空间）。搜索空间中的每个点代表一种可能的解决方案。每个可能的解决方案可以通过其对问题的值（或适应度）进行“标记”。通过GA，我们在众多可能的解决方案中寻找最佳解决方案 - 以搜索空间中的一个点为代表。然后寻找解决方案等于在搜索空间中寻找一些极值（最小值或最大值）。有时可以很好地定义搜索空间，但通常我们只知道搜索空间中的几个点。在使用遗传算法的过程中，随着进化的进行，寻找解决方案的过程会产生其他点（可能的解决方案）。

    问题是搜索可能非常复杂。人们可能不知道在哪里寻找解决方案或从哪里开始。有许多方法可用于寻找合适的解决方案，但这些方法不一定能提供最佳解决方案。这些方法中的一些是爬山，禁忌搜索，模拟退火和遗传算法。通过这些方法找到的解决方案通常被认为是很好的解决方案，因为通常不可能证明最佳方案。

NP-hard Problems

NP问题是一类无法用“传统”方式解决的问题。我们可以快速应用许多任务（多项式）算法。还存在一些无法通过算法解决的问题。有很多重要问题很难找到解决方案，但是一旦有了解决方案，就很容易检查解决方案。这一事实导致了NP完全问题。 NP代表非确定性多项式，它意味着可以“猜测”解决方案（通过一些非确定性算法），然后检查它。如果我们有一台猜测机器，我们或许可以在合理的时间内找到解决方案。为简单起见，研究NP完全问题仅限于答案可以是或否的问题。由于存在输出复杂的任务，因此引入了一类称为NP难问题的问题。这个类并不像NP完全问题那样受限。 NP问题的一个特征是，可以使用一个简单的算法，可能是第一眼看到的，可用于找到可用的解决方案。但是这种方法通常提供了许多可能的解决方案 - 只是尝试所有可能的解决方案是非常缓慢的过程（例如O（2 ^ n））。对于这些类型问题的更大的实例，这种方法根本不可用。今天没有人知道是否存在一些更快的算法来提供NP问题的确切答案。对于研究人员来说，发现这样的算法仍然是一项重大任务（也许你！:-)）。今天许多人认为这种算法不存在，因此他们正在寻找替代方法。替代方法的一个例子是遗传算法。 NP问题的例子是可满足性问题，旅行商问题或背包问题。可以获得NP问题汇编。

参考：

         https://www.jianshu.com/p/ae5157c26af9

        https://www.jianshu.com/p/b36b520bd187

❷ 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过编码（decoding），可以作为问题近似最优解。

5.4.1 非线性优化与模型编码

假定有一组未知参量

x_i（i=1，2，…，M）

构成模型向量m，它的非线性目标函数为Φ（m）。根据先验知识，对每个未知量都有上下界α_i及b_i，即α_i≤x≤b_i，同时可用间隔d_i把它离散化，使

d_i=（b_i-α_i）/N （5.4.1）

于是，所有允许的模型m将被限制在集

x_i=α_i+jd_i（j=0，1，…，N） （5.4.2）

之内。

通常目标泛函（如经济学中的成本函数）表示观测函数与某种期望模型的失拟，因此非线性优化问题即为在上述限制的模型中求使Φ（m）极小的模型。对少数要求拟合最佳的问题，求目标函数的极大与失拟函数求极小是一致的。对于地球物理问题，通常要进行杀重离散化。首先，地球模型一般用连续函数表示，反演时要离散化为参数集才能用于计算。有时，也将未知函数展开成已知基函数的集，用其系数作为离散化的参数集x_i，第二次离散化的需要是因为每一个未知参数在其变化范围内再次被离散化，以使离散模型空间最终包含着有限个非线性优化可选择的模型，其个数为

地球物理数据处理教程

其中M为未知参数x_i的个数。由此式可见，K决定于每个参数离散化的间隔d_i及其变化范围（α_i，b_i），在大多数情况下它们只能靠先验知识来选择。

一般而言，优化问题非线性化的程度越高，逐次线性化的方法越不稳定，而对蒙特卡洛法却没有影响，因为此法从有限模型空间中随机地挑选新模型并计算其目标函数 Φ（m）。遗传算法与此不同的是同时计算一组模型（开始时是随机地选择的），然后把它进行二进制编码，并通过繁殖、杂交和变异产生一组新模型进一步有限的模型空间搜索。编码的方法可有多种，下面举最简单的例说明之，对于有符号的地球物理参数反演时的编码方式一般要更复杂些。

假设地球为有三个水平层的层次模型，含层底界面深度h_j（j=1，2，3）及层速度v_j（j=1，2，3）这两组参数。如某个模型的参数值为（十进制）：

h₁=6，h₂=18，h₃=28，单位为10m

v₁=6，v₂=18，v₃=28，单位为 hm/s

按正常的二进制编码法它们可分别用以下字符串表示为：

地球物理数据处理教程

为了减少字节，这种编码方式改变了惯用的单位制，只是按精度要求（深度为10m，波速为hm/s）来规定参数的码值，同时也意味着模型空间离散化间距d_i都规格化为一个单位（即10m，或hm/s）。当然，在此编码的基础上，还可以写出多种新的编码字符串。例如，三参数值的对应字节顺序重排，就可组成以下新的二进制码串：

地球物理数据处理教程

模型参数的二进制编码是一种数学上的抽象，通过编码把具体的非线性问题和生物演化过程联系了起来，因为这时形成的编码字符串就相当于一组遗传基因的密码。不仅是二进制编码，十进制编码也可直接用于遗传算法。根据生物系统传代过程的规律，这些基因信息将在繁殖中传到下一带，而下一代将按照“适者生存”的原则决定种属的发展和消亡，而优化准则或目标函数就起到了决定“适者生存”的作用，即保留失拟较小的新模型，而放弃失拟大的模型。在传带过程中用编码表示的基因部分地交合和变异，即字符串中的一些子串被保留，有的改变，以使传代的过程向优化的目标演化。总的来说，遗传算法可分为三步：繁殖、杂交和变异。其具体实现过程见图5.8。

图5.8 遗传算法实现过程

5.4.2 遗传算法在地震反演中的应用

以地震走时反演为例，根据最小二乘准则使合成记录与实测数据的拟合差取极小，目标函数可取为

地球物理数据处理教程

式中：T_i，0为观测资料中提取出的地震走时；T_i，s为合成地震或射线追踪算出的地震走时；ΔT为所有合成地震走时的平均值；N_A为合成地震数据的个数，它可以少于实测T_i，0的个数，因为在射线追踪时有阴影区存在，不一定能算出合成数据T_j，0。利用射线追踪计算走时的方法很多，参见上一章。对于少数几个波速为常数的水平层，走时反演的参数编码方法可参照上一节介绍的分别对深度和速度编码方法，二进制码的字符串位数1不会太大。要注意的是由深度定出的字符串符合数值由浅到深增大的规律，这一约束条件不应在杂交和传代过程中破坏。这种不等式的约束（h₁＜h₂＜h₃…）在遗传算法中是容易实现的。

对于波场反演，较方便的做法是将地球介质作等间距的划分。例如，将水平层状介质细分为100个等厚度的水平层。在上地壳可假定波速小于6400 m/s（相当于解空间的硬约束），而波速空间距为100m/s，则可将波速用100m/s为单位，每层用6位二进制字符串表示波速，地层模型总共用600位二进制字符串表示（l=600）。初始模型可随机地选取24～192个，然后通过繁殖杂交与变异。杂交概率在0.5～1.0之间，变异概率小于0.01。目标函数（即失拟方程）在频率域可表示为

地球物理数据处理教程

式中：P₀（ω_k，v_j）为实测地震道的频谱；ω_k为角频率；v_j为第j层的波速；P_s（ω_k，v_j）为相应的合成地震道；A（ω_k）为地震仪及检波器的频率滤波器，例如，可取

A（ω）=sinC⁴（ω/ω_N） （5.4.6）

式中ω_N为Nyquist频率，即ω_N=π/Δt，Δt为时间采样率。参数C为振幅拟合因子，它起到合成与观测记录之间幅度上匹配的作用。C的计算常用地震道的包络函数的平均比值。例如，设E［］为波动信号的包络函数，可令

地球物理数据处理教程

式中：t_max为包络极大值的对应时间；J为总层数。包络函数可通过复数道的模拟取得。

用遗传算法作波速反演时失拟最小的模型将一直保存到迭代停止。什么时候停止传代还没有理论上可计算的好办法，一般要显示解空间的搜索范围及局部密度，以此来判断是否可以停止传代。值得指出的是，由（5.4.4）和（5.4.5）式给出的目标函数对于有误差的数据是有问题的，反演的目标不是追求对有误差数据的完美拟合，而是要求出准确而且分辨率最高的解估计。

遗传算法在执行中可能出现两类问题。其一称为“早熟”问题，即在传代之初就随机地选中了比较好的模型，它在传代中起主导作用，而使其后的计算因散不开而白白浪费。通常，增加Q值可以改善这种情况。另一类问题正相反，即传相当多代后仍然找不到一个特别好的解估计，即可能有几百个算出的目标函数值都大同小异。这时，最好修改目标函数的比例因子（即（5.4.5）式的分母），以使繁殖概率P_s的变化范围加大。

对于高维地震模型的反演，由于参数太多，相应的模型字符串太长，目前用遗传算法作反演的计算成本还嫌太高。实际上，为了加快计算，不仅要改进反演技巧和传代的控制技术，而且还要大幅度提高正演计算的速度，避免对遗传算法大量的计算花费在正演合成上。

❸ 遗传算法在数学上的应用

应用遗传算法搜索边坡最小安全系数的研究
陆峰 陈祖煜 李素梅
（中国水利水电科学研究院结构材料所）

提 要
本文简要介绍了滑坡滑裂面搜索问题和遗传算法，并试用遗传进化算法从边坡任意形状滑裂面组合中搜索最有可能的滑裂面，也就是使安全系数最小的滑裂面。作为实例，分析了遗传算法在天生桥二级电站首部枢纽进水口右岸滑坡分析中的应用。

关键词 边坡；安全系数；遗传算法；EMU程序。

1．前言

在应用条分法进行边坡稳定分析的过程中，从可能的滑裂面集合中确定相应最小安全系数的临界滑裂面是很关键的一步。这是一个确定安全系数这个泛函对滑裂面形状这个自变函数的极小值问题。由于实际情况的复杂性，求这一极小值的解析方法很难付诸实施。从实用角度出发，基于最优化原理发展起来的求边坡最小安全系数的方法是比较有效而且便于应用。这些方法有"穷举法"、"黄金分割法"、"鲍威尔法"等，但它们都只能应用于圆弧形滑裂面或圆弧-直线形（改良圆弧法）滑裂面的情形。对于比较符合岩质边坡的具有多个自由度的折线形滑裂面情形，孙君实用复形法取得较好的效果；陈祖煜提出了单纯形法，使最优化方法搜索边坡最危险滑裂面更加有效，且不会漏掉可能的最小值。单纯形法程序已在国内外多家工程、科研和教育单位得到应用，并不断随着应用工程案例数量的增加而不断完善[1]。单纯形法使最优化方法应用于岩质边坡稳定性分析的研究和应用前进了一大步。同为最优化方法，遗传算法是最近发展起来的一种仿生寻优算法。国内外已有一些学者试图将遗传算法应用于搜索安全系数最小的边坡滑裂面，以期获得更优的结果。文献[2]将此算法应用于基于圆弧滑裂面假定的任意形状坡面的非均质土坡情况，搜索的目标是使边坡安全系数最小的圆弧滑裂面圆心和半径。本文将在文献[1]和文献[2]的基础上，应用遗传算法搜索边坡安全系数最小的任意形状滑裂面，根据工程实践经验，主要是折线组合的滑裂面。 2．遗传算法及其应用于岩土工程的基础

如前所述，搜索边坡最危险滑裂面问题是安全系数对滑裂面形状的泛函极值问题。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。
生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法（GA）。算法中称遗传的生物体为个体（indivial），个体对环境的适应程度用适应值（fitness）表示。适应值取决于个体的染色体（chromosome），在算法中染色体常用一串数字表示，数字串中的一位对应一个基因（gene）。一定数量的个体组成一个群体（population）。对所有个体进行选择、交叉和变异等操作，生成新的群体，称为新一代（new generation）。
遗传算法计算程序的流程可以表示如下[3]：
第一步 准备工作
（1）选择合适的编码方案，将变量（特征）转换为染色体（数字串，串长为m）。通常用二进制编码。
（2）选择合适的参数，包括群体大小（个体数M）、交叉概率PC和变异概率Pm。
（3）确定适应值函数f（x）。f（x）应为正值。
第二步 形成一个初始群体（含M个个体）。在边坡滑裂面搜索问题中，取已分析的可能滑裂面组作为初始群体。
第三步 对每一染色体（串）计算其适应值fi，同时计算群体的总适应值 。
第四步 选择
计算每一串的选择概率Pi=fi/F及累计概率 。选择一般通过模拟旋转滚花轮（roulette，其上按Pi大小分成大小不等的扇形区）的算法进行。旋转M次即可选出M个串来。在计算机上实现的步骤是：产生[0，1]间随机数r，若r<q1，则第一串v1入选，否则选v2，使满足qi-1<r<qi（2≤i≤m）。可见适应值大的入选概率大。
第五步 交叉
（1） 对每串产生[0，1]间随机数，若r>pc，则该串参加交叉操作，如此选出参加交叉的一组后，随机配对。
（2） 对每一对，产生[1，m]间的随机数以确定交叉的位置。
第六步 变异
如变异概率为Pm，则可能变异的位数的期望值为Pm ×m×M，每一位以等概率变异。具体为对每一串中的每一位产生[0，1]间的随机数r，若r<Pm，则该位发生反转，如对染色体二进制编码为数字0变为1，1变为0。
如新个体数达到M个，则已形成一个新群体，转向第三步；否则转向第四步继续遗传操作。直到找到使适应值最大的个体或达到最大进化代数为止。
由于选择概率是由适应值决定的，即适应值大的染色体入选概率也较大，使选择起到"择优汰劣"的作用。交叉使染色体交换信息，结合选择规则，使优秀信息得以保存，不良信息被遗弃。变异是基因中得某一位发生突变，以达到产生确实有实质性差异的新品种。遗传算法虽是一种随机算法，但它是有导向的，它所使用的"按概率随机选择"方法是在有方向的搜索方法中的一种工具。正是这种独特的搜索方法，使遗传算法自然地避开了其它最优化算法常遇到的局部最小陷阱。遗传算法搜索最优结果的效果在数学上还没有严格的证明，但它的有效性已在许多专业的应用的得到体现。对于岩质边坡安全系数对滑裂面形状这样不可微的泛函极值问题，就目前的科学认识水平来讲，遗传算法不失为一种可以信赖的方法。 3．用遗传算法搜索安全系数最小的边坡任意形状滑裂面

在边坡（尤其是岩质边坡）最危险滑裂面搜索问题中，滑裂面的实际形状是很复杂的，起控制作用的是岩体的主要结构面和边坡的体型。从以往实际工程经验看，可以总结出岩质边坡滑裂面在顺滑方向上的剖面形状为折线，由岩体结构面和局部岩土材料的剪切破坏面连接而成。这样，搜索最危险滑裂面的问题就可以简化为从折线滑裂面组合中寻优的问题。本文用遗传进化算法解决这个问题。
（1） 定义遗传算法的目标函数
目标函数定义为边坡的安全系数，用安全系数的大小表示解的适应值。在边坡最危险滑裂面搜索问题中，解的安全系数越小，适应性能越好。
（2） 初始群体的确定
根据边坡的工程地质调查记录，根据经验初步拟定出一批滑裂面形状。如图1所示，滑裂面由点序列Ai（xi，yi）（i=1，?，N）表示。将点序列AI的坐标（xi，yi）依次排列成x1y1x2y2?xNyN的形式，经二进制编码形成一条染色体。对于拟定的滑裂面形状，其对应的安全系数用EMU程序[4]进行计算。
（3） 确定搜索范围
根据经验对每个点Ai，确定其坐标（xi，yi）的可能变化范围。在此范围内搜索导致最小安全系数的边坡滑裂面形状。
（4） 计算
将初始种群的所有拟定滑裂面形状（染色体）交给遗传算法程序进行计算。具体过程参见前文。

4．算例分析[4]

图1 天生桥二级电站首部枢纽进水口右岸滑坡示意图

选用天生桥二级电站首部枢纽进水口右岸滑坡作为算例，图1为其计算简图。滑坡高约30m，总方量为7000余m3，主要为第四系冲坡积物和施工堆碴。物理力学参数见表1。

表1 各土层物理力学性能指标
土层 密度（g/cm3） 抗剪强度指标
内摩擦角 凝聚力（kPa）
① 施工弃碴 1.85 21.8° 19.6
② 坡积土 1.85 21.8° 0.0
③ 砂土 1.85 21.8° 29.4
④ 砂质淤泥 1.85 20.8° 34.3
⑤ 河卵石、砾石 1.90 24.2° 0.0

滑坡发生前，靠近坡脚处因修建挡土墙被开挖而削弱边坡的整体稳定性，可以断定滑坡的滑裂面将从此经过。本例题还将忽略实际工程中坡顶张裂缝的影响。选用5个点的折线来模拟滑裂面形状，初步确定AiBiCiDiE（i=1~4）为可能的滑裂面。滑裂面上端点Ai的y坐标已受限制，下端点E的x、y坐标均已确定，故滑裂面只有7个自由度。按遗传算法的要求将滑裂面表示成如下形式：
xAxByBxCyCxDyD
四个模拟滑裂面的坐标和由EMU程序分析的安全系数列于表2。
表2 模拟滑裂面坐标及安全系数（坐标单位 m）
滑裂面 xA xB yB xC yC xD yD 安全系数
A1B1C1D1E 35.44 27.69 16.82 18.79 9.25 11.39 4.49 0.92
A2B2C2D2E 38.15 30.60 20.69 23.14 14.60 14.12 8.37 0.99
A3B3C3D3E 39.02 34.18 18.47 26.28 10.41 16.07 4.58 1.02
A3B3C4D4E 39.02 34.18 18.47 25.12 11.39 14.70 4.97 1. 03

限制搜索范围为每个自由度可在2.0m范围内变化。将4个排列好的数字串作为输入数据交给遗传算法程序进行编码、计算。经过大量运算，最后在最大种群代数（1000）群体中找到使安全系数最小的坐标数字串，经译码形成如下坐标：
（36.89，30.07）（33.25，21.52）（21.71，9.34）（13.54，5.07）（0.0，0.0）
即为图1中的ABCDE滑裂面。由遗传算法求出其相应的安全系数为0.90。滑裂面形式和安全系数都比较接近实际情况。

5．结语

遗传算法是一种高效的寻优算法，而且能有效地解决局部最小问题、非线性映射关系的表示、非线性映射关系不可微等普通优化算法常遇到的问题。算例的成果证明了这一特点。将遗传算法应用于滑坡滑裂面搜索问题，主要的工作是将工程问题简化成遗传算法需要的形式，简化时需详细参考地质调查资料和工程经验，务使简化的形式接近实际情况。对于简化的搜索样本，其安全系数的计算必须可靠，为此可应用一些比较成熟的计算程序，如EMU等。充分考虑实际工程地质情况和选取切合实际的搜索样本后，遗传算法程序必将能为滑坡搜索出最有可能的滑裂面。

参考文献

1 陈祖煜，邵长明，最优化方法在确定边坡最小安全系数方面的应用，岩土工程学报，Vol.10, No.4, 1998.7。
2 肖专文，张奇志，梁力，林韵梅，遗传进化算法在边坡稳定性分析中的应用，岩土工程学报，Vol.20, No.1, 1998.1。
3 周明，孙树栋，遗传算法原理及应用，国防工业出版社，1999.6。
4 陈祖煜，岩质高边坡稳定分析程序EMU，1995.5。

Research on Searching Least Factor of Safety of Slopes with Genetic Algorithm

Lu Feng Chen Zuyu Li Sumei
(Department of Structure and Material, IWHR)

Abstract

The problem of searching least factor of safety of slopes and the theory of Genetic Algorithm have been introced in this paper. This theory has been employed to solve this problem to find the most possible slide of slopes. As an example, the application of genetic algorithm on the Tianshengqiao Power Station Right Bank Slide has been presented.

Keywords: Slope, Factor of Safety, Genetic Algorithm, EMU Program.

❹ 遗传算法的核心是什么！

遗传操作的交叉算子。

在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。

(4)遗传算法导图扩展阅读

评估编码策略常采用以下3个规范：

a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。

b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。

c)非冗余性(nonrendancy):染色体和候选解一一对应。

目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。

而二进制编码是目前遗传算法中最常用的编码方法。即是由二进制字符集{0,1}产生通常的0,1字符串来表示问题空间的候选解。

❺ 遗传算法路径规划是什么原理

遗传算法有相当大的引用。遗传算法在游戏中应用的现状在遗传编码时, 一般将瓦片的坐标作为基因进行实数编码, 染色体的第一个基因为起点坐标, 最后一个基因为终点坐标, 中间的基因为路径经过的每一个瓦片的坐标。在生成染色体时, 由起点出发, 随机选择当前结点的邻居节点中的可通过节点, 将其坐标加入染色体, 依此循环, 直到找到目标点为止, 生成了一条染色体。重复上述操作, 直到达到指定的种群规模。遗传算法的优点：1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行操作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传操作算子的运用。另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。遗传算法的缺点：遗传算法在进行编码时容易出现不规范不准确的问题。

❻ 遗传算法对生活的启示

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作:适应度高的个体被遗传到下一代群体中的概率大。

遗传算法（Genetic Algorithm，GA）最早是由美国的John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

20世纪80年代后,遗传算法进入兴盛发展时期，被广泛应用于自动控制、生产计划、图像处理、机器人等研究领域。由于遗传算法不能直接处理问题空间的参数,因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。这一转换操作就叫做编码，也可以称作（问题的）表示。