遗传算法作用

① 遗传算法--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

② 遗传算法的作用

与传统的优化相比，在求取符合运行要求的全局最优解时，遗传算法作为一种搜索的方法，已经成为成熟的具有良好收敛性、极高鲁棒性和广泛适用性的优化方法，很好的解决了电力系统的多变量、非线性、不连续、多约束的优化控制问题。

③ 基因算法和遗传算法的区别

遗传算法
一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。
Holland创建的遗传算法是一种概率搜索算法，它是利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些组成的进化过程。跗算法通过有组织地然而是随机地信息交换重新组合那些适应性好的串，在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。
遗传算法是一类随机化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串，类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来造反染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。
基因算法
一种生物进化的算法,实际上是一种多目标的探索法.能够用于计划与排程.它是非常新的技术,目前,还没有在商业中实际运用.
采用生物基因技术高级算法,处理日益复杂的现实世界,也是人工智能上,高级约束算法上的挑战. 基因算法是一种搜索技术，它的目标是寻找最好的解决方案。这种搜索技术是一种优化组合，它以模仿生物进化过程为基础。基因算法的基本思想是，进化就是选择了最优种类。基因算法将应用APS上，以获得“最优”的解决方案。

④ 遗传算法具体应用

1、函数优化

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。

2、组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。

此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。

3、车间调度

车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。

从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。

(4)遗传算法作用扩展阅读：

遗传算法的缺点

1、编码不规范及编码存在表示的不准确性。

2、单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

3、遗传算法通常的效率比其他传统的优化方法低。

4、遗传算法容易过早收敛。

5、遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

⑤ 关于遗传算法

遗传算法（Genetic Algorithm，简称GA）是美国 Michigan大学的 John Golland提出的一种建立在自然选择和群体遗传学机理基础上的随机、迭代、进化、具有广泛适用性的搜索方法。现在已被广泛用于学习、优化、自适应等问题中。图4-1 给出了 GA搜索过程的直观描述。图中曲线对应一个具有复杂搜索空间（多峰空间）的问题。纵坐标表示适应度函数（目标函数），其值越大相应的解越优。横坐标表示搜索点。显然，用解析方法求解该目标函数是困难的。采用 GA时，首先随机挑选若干个搜索点，然后分别从这些搜索点开始并行搜索。在搜索过程中，仅靠适应度来反复指导和执行 GA 搜索。在经过若干代的进化后，搜索点后都具有较高的适应度并接近最优解。

一个简单GA由复制、杂交和变异三个遗传算子组成：

图4-2 常规遗传算法流程图

⑥ 什么叫遗传算法，遗传算法有什么用希望通俗一点儿

首先有个很神奇的现象：人类以及动物的进化都是朝着好的方向发展，虽然有的往坏的方向发展了，但是总体肯定是往好的方向发展。这看似不奇怪，但是我们知道，人类的基因组合是随机的，没有上帝约束。这种随机过程的结果却是一致的！！！！！我们的遗传算法就是从这里得到启发！比如我要求y=x1+x2的最大值，两个变量，我不用传统的数学方法，就用幼儿园的方法，把所有可能取值带进去算，然后找出最大的就行了！但是，有时候取值是连续的，没关系！使其离散化，就像把模拟信号化成数字信号一样！还有个问题，如果取值太多咋办？这就是遗传算法的精髓！
首先，我不用取所有可能取值，我只取几十个或者几百个（自己定），然后进行处理，怎样处理呢？让我们回到刚开始的人类进化问题，虽然没有上帝的帮忙，但是我们知道，自然界遵循优胜劣汰的发贼，遵循交叉变异的法则，虽然不能数字化，但是这是个趋势！我们就是把这种法则数学化！所取的几十个值我要剩下哪些？要抛弃哪些？要处理哪些？这都要我们自己选择，肯定是选择最合适的取值留下，经过一系列的处理，就生成了新的群体，然后再处理，自己约定处理到第几次就可以了，取出现过的最大值
不用担心取到的是不是最大值，因为数学上已经有了证明，这种方法是收敛的，概率是1，所以尽管放心的做，具体的做法要参考相关书籍，不难的。
遗传算法的最大用处就是解决数学理论不能解决的问题！比如路径规划，调度问题……

⑦ 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（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的变化范围加大。

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

⑧ TSP遗传算法的作用是什么

你是问为什么要用遗传算法求解TSP？那么答案就是，TSP问题如果用穷举的方法搜索，会由于可行解太多而无法在有效时间之内完成，而遗传算法则是不使用穷举的方法之一。
如果你是想问为什么要求解TSP，那么就是因为两个原因，一个是TSP本身是实际问题抽象而来的，而且和tsp近似的还有很多不同的最短路径问题，都是实际生活中会出现的，不管是规划人的路径还是机械手臂的路径，都会用到。第二个原因是tsp是NP完全问题，和很多其他问题一样，都是NP完全的，这就意味着，只要其中一个问题解决了，另外的NP完全问题也能够解决，所以研究它也具有理论价值。

⑨ 遗传算法

优化的算法有很多种，从最基本的梯度下降法到现在的一些启发式算法，如遗传算法(GA)，差分演化算法(DE)，粒子群算法(PSO)和人工蜂群算法(ABC)。

举一个例子，遗传算法和梯度下降：

梯度下降和遗传算法都是优化算法，而梯度下降只是其中最基础的那一个，它依靠梯度与方向导数的关系计算出最优值。遗传算法则是优化算法中的启发式算法中的一种，启发式算法的意思就是先需要提供至少一个初始可行解，然后在预定义的搜索空间高效搜索用以迭代地改进解，最后得到一个次优解或者满意解。遗传算法则是基于群体的启发式算法。

遗传算法和梯度下降的区别是：

1.梯度下降使用误差函数决定梯度下降的方向，遗传算法使用目标函数评估个体的适应度
2.梯度下降是有每一步都是基于学习率下降的并且大部分情况下都是朝着优化方向迭代更新，容易达到局部最优解出不来；而遗传算法是使用选择、交叉和变异因子迭代更新的，可以有效跳出局部最优解
3.遗传算法的值可以用二进制编码表示，也可以直接实数表示

遗传算法如何使用它的内在构造来算出 α 和 β ：

主要讲一下选择、交叉和变异这一部分：
1.选择运算:将选择算子作用于群体。选择的目的是把优秀（适应值高）的个体直接遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

2.交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。交叉算子是将种群中的个体两两分组，按一定概率和方式交换部分基因的操作。将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。例如：（根据概率选取50个个体，两两配对，交换x,y，比如之前两个是(x1,y1),(x2,y2)，之后变成了（x1,y2）,(x2,y1)）

3.变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。（x2可能变为x2+δ，y1变为y1+δ）
种群P(t)经过选择、交叉、变异运算之后得到下一代种群P(t+1)。

遗传算法就是通过对大量的数据个体使用选择、交叉和变异方式来进化，寻找适合问题的最优解或者满意解。

遗传算法参数的用处和设置：

1.编码选择：通常使用二进制编码和浮点数编码，二进制适合精度要求不高、特征较少的情况。浮点数适合精度高、特征多的情况
2.种群：种群由个体组成，个体中的每个数字都代表一个特征，种群个体数量通常设置在40-60之间；迭代次数通常看情况定若计算时间较长可以在100内，否则1000以内都可以。
3.选择因子：通常有轮盘赌选择和锦标赛选择，轮盘赌博的特点是收敛速度较快，但优势个体会迅速繁殖，导致种群缺乏多样性。锦标赛选择的特点是群多样性较为丰富，同时保证了被选个体较优。
4.交叉因子：交叉方法有单点交叉和两点交叉等等，通常用两点交叉。交叉概率则选择在0.7-0.9。概率越低收敛越慢时间越长。交叉操作能够组合出新的个体，在串空间进行有效搜索，同时降低对种群有效模式的破坏概率。
5.变异因子：变异也有变异的方法和概率。方法有均匀变异和高斯变异等等；概率也可以设置成0.1。变异操作可以改善遗传算法的局部搜索能力，丰富种群多样性。
6.终止条件：1、完成了预先给定的进化代数；2、种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进；3、所求问题最优值小于给定的阈值.