遗传算法f

1. 遗传算法

例如：[1,2,3]，[1,3,2]，[3,2,1]均是函数 3x+4y+5z<100 的可行解（代进去成立即为可行解），那么这些可行解在遗传算法中均称为“染色体”。可行解由 3 个元素构成，每个元素都称为染色体的一个基因。

遗传算法在运行过程中会进行 N 次迭代，每次迭代都会生成若干条染色体。适应度函数会给本次迭代中生成的所有染色体打个分，来评判这些染色体的适应度，然后将适应度低的染色体淘汰，只保留适应度高的染色体，从而讲过若干次迭代后染色体的质量将越来越好。

遗传算法每次迭代会生成 N 条染色体，在遗传算法中一次迭代被称为一次进化。每次进化新的染色体生成的方法——交叉。

每一次进化完成后，都要计算每一条染色体的适应度+适应度概率。在交叉过程中就需要根据这个概率来选择父母染色体。适应度高的染色体被选中的概率越高。（这就是遗传算法能够保留优良基因的原因）

交叉能保证每次进化留下优良的基因，但它仅仅是对原有的结果集进行选择，基因还是那么几个，只不过交换了它们的顺序。这只能保证 N 次进化后，计算结果更接近于局部最优解，而永远没办法达到全局最优解（？？？？？），为了解决这个问题，需引入变异。

假设每次进化都需要生成 N 条染色体，那么每次进化中，通过交叉方式需要生成 N-M 条，剩余的 M 条染色体通过复制上一代适应度最高的 M 条染色体而来。

本文的目标是使所有任务的总处理时间最少，时间越短适应度越大。适应度 = 1 / 所有任务的总处理时间

将任务从 0 开始编号，用一个一维数组存储每个任务的时长

tasks[i] ：表第 i 个任务的长度。
第 0 个任务的长度为 2；
第 1 个任务的长度为 4；
第 2 个任务的长度为 6；
第 3 个任务的长度为 8；

将处理器节点从 0 开始编号，用一个一维数组存储每个处理器的处理速度（单位时间内可处理的长度）

nodes[i] 表第 i 个节点的处理速度。
第 0 个节点的处理速度为 2；
第 1 个节点的处理速度为 1。

timeMatrix[i][j] 表第 i 个任务在第 j 个节点上处理的话，所需处理时间。

一个可行解就是一个染色体，就是一个一维数组

chromosome[i]=j 表将第 i 个任务分配到节点 j 上处理（任务编号从 0 开始；节点编号从 0 开始）

将任务 0 分配给 3 号节点处理；
将任务 1 分配给 2 号节点处理；
将任务 2 分配给 1 号节点处理；
将任务 3 分配给 0 号节点处理。

记录本次进化生成的 N 条染色体的适应度，将染色体从 0 开始编号。

adaptablility[i] 表第 i 个染色体的适应度

selectionProbability[i] 表第 i 个染色体的适应度概率，所有染色体的适应度概率和为 1 。

java中PriorityQueue优先级队列使用方法

第 2 次迭代结果

第 100 次迭代结果

2. 什么是遗传算法

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

3. 遗传算法特点

遗传算法有以下特点：不会产生无效的路径，但是在复杂的环境中，很难创建链接图。此外，遗传算法计算效率低，计算时间长，在遗传进化过程中需要大量的存储空间。

4. 遗传算法的优缺点

优点：

1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行操作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传操作算子的运用。

另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。

2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。

3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。

另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。

4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。

5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。

缺点：

1、遗传算法在进行编码时容易出现不规范不准确的问题。

2、由于单一的遗传算法编码不能全面将优化问题的约束表示出来，因此需要考虑对不可行解采用阈值，进而增加了工作量和求解时间。

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

4、遗传算法容易出现过早收敛的问题。

(4)遗传算法f扩展阅读

遗传算法的机理相对复杂，在Matlab中已经由封装好的工具箱命令，通过调用就能够十分方便的使用遗传算法。

函数ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最优解，fval是最优值，@fitnessness是目标函数，nvars是自变量个数，options是其他属性设置。系统默认求最小值，所以在求最大值时应在写函数文档时加负号。

为了设置options，需要用到下面这个函数：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通过这个函数就能够实现对部分遗传算法的参数的设置。

5. 遗传算法的基本原理

遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。

6. 关于遗传算法

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

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

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

7. 遗传算法

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

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

8. 遗传算法理解

遗传算法是一种进化算法，进化是什么哪？就是种群逐渐适应生存环境，种群中个体不断得到改良的过程。

遗传算法是一种对生物遗传的模拟、在算法中，初始化一个种群，种群中的每个染色体个体都是一种解决方案，我们通过适应性fitness来衡量这个解决方案的好坏。并对它们进行选择、变异、交叉的操作，找到最优的解决方案。

总结一下遗传算法的基本的步骤：

1.初始化一个种群，并评估每条染色体所对应个体的适应度。

2.选择、交叉、变异，产生新的种群

3.再评估每个个体的适应值，如果适应值达到要求或者达到最大循环次数，否则重复2，不断产生新种群。

知道了GA的大致流程之后、来具体分析一下细节，怎么实现吧

我们知道遗传算法起源于生物遗传，因此在种群中每个个体就是一个染色体，那如何对染色体进行编码，让它表示我们的解决方案那（就是把现实要优化的参数用编码表示成一个染色体）。这里就遇到了一个编码、解码的问题，我们将需要优化的目标编码成染色体，然后再解码为我们可以用来计算fitness的解；

一般在进行参数优化时，一般有两种方式：实数编码、二进制编码

实数编码：基因直接用实数进行表示，这样的表示方法比较简单，不用特意解码了，但是在交叉和变异时，容易过早收敛，陷入局部最优。

二进制编码：将基因用二进制的形式表示，将参数的值转化为二进制形式，这样交叉、变异时更好操作，多样性好，但是占用的存储空间大，需要解码。

染色体就称为个体。对于一次实验，个体就是需要优化参数的一种解、许多这样的个体就构成了种群。

在面对群体中那么多个体时，如何判断个体的好坏呢，就是通过适应值函数了，将解带入适应值函数，适应值越大、解越好。

在遗传算法中，我们怎么使得里面的个体变得越来越优秀呢？

核心思想就是：选择优秀的、淘汰不好的，并且为了生成更好的解，我们要尝试交叉、变异，带来新的解。

选择就是从当前的种群中选择出比较好的个体、淘汰不好的个体

常见的选择方法有：轮盘赌选择、锦标赛选择、最佳保留选择等等

轮盘赌选择就是根据每个个体fitness和种群所有fitness之和比较，确定每个个体被选中的概率，然后进行n次选择，选择n个个体构成新种群，是一种放回抽样的方式。

锦标赛就是每次从种群中选择m个个体，选择最优的，放入新种群，重复选择，直到新种群中个体数目达到n。

最佳保留选择就是在轮盘赌的基础上，将fitness个体先加进新种群，因为轮盘赌是一种概率模型，可能存在最优个体没有进入新种群的情况。

在选择之后，就要考虑产生新的、更优秀的解，为种群带来新的血液。遗传算法的思路是交叉两个优秀的解，往往get好的解。

交叉通过在经过选择的种群中，随机选择一对父母，将它们的染色体进行交叉，生成新的个体，替代原来的解。

常用的交叉方法有：单点交叉、多点交叉等等。

交叉就像生物里面，染色体交换基因一样的～但是并不是种群中所有个体都进行交叉的，实现时可以，设置一个交叉率和交叉概率，随机选择种群中两个体、随机一个数，小于交叉率就进行交叉操作，并根据交叉概率判断交叉的程度，从而生成新个体，反之就保留这两个体。

变异也是一种产生新个体的方式，通过改变个体上基因，期望产生更好的解。比如在以二进制编码的个体上，将里面的0、1进行等位变化啥的，就是0变1、1变0这样。同样也要考虑变异率、变异产生的新解是不可控的，可能很好，也可能很坏，不能像交叉一样，确保一定的效果，所以往往变异率设置的比较小。

9. 遗传算法^[1，]

遗传算法，又称基因算法(Genetic Algorithm，简称GA)，也是一种启发式蒙特卡洛优化算法。遗传算法最早是由Holland(1975)提出，它模拟了生物适者生存、优胜劣汰的进化过程，具有不依赖于初始模型的选择、不容易陷入局部极小、在反演过程中不用计算偏导数矩阵等优点。遗传算法最早由Stoffa和Sen(1991)用于地震波的一维反演，之后在地球物理资料的非线性反演中得到广泛的应用。GA算法对模型群体进行追踪、搜索，即模型状态通过模型群体传送，具有比模拟退火法更大、更复杂的“记忆”，潜力更大。

遗传算法在反演中的基本思路和过程是:

(1)将生物体看成模型，模型参数看成染色体，有多少个模型的参数就有多少个染色体。对每个模型的参数(染色体)用二进制进行编码，这个编码就是基因。

(2)随机生成一个模型群体(相当于生物的种群)，然后在模型群体中进行繁殖，通过母本的选择、交换和变异等遗传操作产生下一代，然后保留较好基因，淘汰较差基因。

(3)通过一代一代的繁殖优胜劣汰的进化过程，最后所剩下的种群基本上都是最优的基因，种群趋于一致。所谓群体“一致”，即群体目标函数的方差或标准差很小，或者群体目标函数的均值接近于极值(可能是极大值或极小值)，从而获得非线性反演问题所对应的最优解或近似最优解。

下面以一个实例来简述遗传算法的基本过程。

[例1]设m是正整数，且0≤m≤127，求方程φ(m)=m²的极大值。

这个例子极为简单，只有一个模型参数，因此只有一条染色体，目标函数的极值是极大值(此例子来自阮百尧课件)。遗传算法通过以下7个步骤来实现:

(1)模型参数二进制编码。

每个模型参数就是一条染色体，把十进制的模型参数表示为二进制，这就是基因。首先确定二进制码的长度(基因的长度):

2^N=[m_max(i)-m_min(i)]/Δm(i) (8.20)

其中:N为第i条染色体基因的长度(也就是第i个模型参数的二进制码位数);[m_min(i)，m_max(i)]为第i个模型参数的取值范围;Δm(i)为第i个模型参数的分辨率。这样就把模型参数离散化了，它只能按Δm(i)的整数倍变化。基因的长度按下式计算:

地球物理反演教程

其中:c为实数;N为基因长度，是整数;int[ ]为取整函数。上式表示如果c不是整数，那么基因长度N就是对c取整后加1，这样保证最小分辨率。

基因的编码按下式进行:

地球物理反演教程

其中:式(8.22)是编码公式;k为基因编码的十进制数，是整数;int[ ]为取整函数。把k转化为二进制就是基因的编码。解码是按照式(8.23)进行的。首先把一个基因的二进制编码转化为十进制数k，然后按式(8.23)可以计算出第i个模型参数m(i)的十进制值。

例如:电阻率参数ρ(1)，它的变化范围为10~5000Ω·m，分辨率为2Ω·m，设当前参数ρ(1)=133Ω·m，按式(8.21)计算得

c=11.28482，N=12

所以二进制基因长度为13位。

利用式(8.22)计算基因编码k的十进制数:

k=int[(133-10)/2]=61

把它转化为二进制数为:000000111101。所以ρ(1)=133 的二进制基因编码为:000000111101。

解码过程就是把二进制基因编码变为十进制数k后用式(8.23)计算:

ρ(1)=10+61×2=132(Ω·m)

注意:基因编码并不是直接把电阻率值变为二进制。此外，133这个值在基因里不会出现，因为分辨率是2，所以表示为最接近的132。

对于[例1]问题来说，选分辨率为1，0~127用二进制编码需7位。

(2)产生初始模型种群。

生物繁殖进化需要一定数量的生物体种群，因此遗传算法开始时需要一定数量的初始模型。为保证基因的多样性，随机产生大量的初始模型作为初始种群，按照上面的编码方式进行编码。个体在模型空间中应分布均匀，最好是模型空间各代表区域均有成员。初始模型群体大，有利于搜索，但太大会增加计算量。

为保证算法收敛，在初始模型群体中，有时候应增加各位都为0和都为1的成员。遗传算法就是在这个初始模型种群的基础上进行繁殖，进化求解的。

对于[例1]问题来说，模型空间是0~127个数字，这样初始种群最多具有128个个体。为了简单，随机选择4个个体作为初始种群。初始种群的编码、目标函数值见表8.1。

表8.1 初始种群编码表

(3)模型选择。

为了生成新一代模型，需要选择较优的个体进行配对。生物进化按照自然选择、优胜劣汰的准则进行。对应地，遗传算法按照一定的准则来选择母本(两个)，然后进行配对繁殖下一代模型，这个选择称为模型选择。模型配对最基本的方法是随机采样，用各模型的目标函数值对所有模型目标函数的平均值的比值定义繁殖概率，即

地球物理反演教程

其中:p(m_i)为繁殖概率;φ(m_i)为第i个模型的目标函数;φ_AVG为目标函数的平均值。对于极小化问题来说，规定目标函数值高于平均值的不传代;对于极大化问题来说，反之即可。

就[例1]来说，要求目标函数取极大值，所以规定目标函数小于平均值的模型不传代，大于它的可以传代。对第一代，为了防止基因丢失，可先不舍去繁殖概率小的模型，让它与概率大的模型配对。如:本例中70与56配对，101与15配对产生子代，见表8.2。

表8.2 基因交换表

(4)基因交换。

将配对的两个亲本模型的部分染色体相互交换，其中交换点可随机选择，形成两个新的子代(见表8.2)。两个染色体遗传基因的交换过程是遗传算法的“繁殖”过程，是母本的重组过程。

为了使染色体的基因交换比较彻底，Stoffa等人提出了一个交换概率p_x来控制选择操作的效果。如果p_x的值较小，那么交换点的位置就比较靠低位，这时的交换操作基本是低位交换，交换前后模型的染色体变化不是太大。如果p_x的值较大，那么交换点的位置就比较靠高位，此时的交换操作可以在较大的染色体空间进行，交换前后模型数值变化可以很大。

在[例1]中:15、101和56、70作为母本通过交换繁殖出子代5、6、111、120。所选择的基因交换位置见表8.2。有下划线的，是要交换的基因位置。

(5)更新。

母本模型和子本模型如何选择保留一定数量作为新的母本，就是模型更新。不同的策略会导致不同的结果。一般而言，若产生的新一代模型较好，则选择新一代模型而淘汰上一代模型。否则，则必须根据一定的更新概率p_u来选择上一代模型来取代新一代中某些较劣的模型。

经过更新以后，繁殖时对子代再进行优胜劣汰的选择。对于极大值问题，大于目标函数平均值的子代可以繁殖，小于目标函数平均值的子代不能繁殖。由于新的种群能繁殖的个体数量减小了，所以要多繁殖几次，维持种群个体的数量保持平衡。

在[例1]中，子代较好，所以完全淘汰上一代模型，完全用子代作为新的母本。选择子代目标函数最大的两个模型进行繁殖，分别是111、120。

(6)基因变异。

在新的配对好的母本中，按一定比例随机选择模型进行变异，变异操作就是模拟自然界中的环境因素，就是按比较小的变异概率p_m将染色体某位或某几位的基因发生突变(即将0变为1或将1变为0)。

变异操作的作用是使原来的模型发生某些变化，从而成为新的个体。这样可使群体增加多样性。变异操作在遗传算法中也起着至关重要的作用。实际上，由于搜索空间的性质和初始模型群体的优劣，遗传算法搜索过程中往往会出现所谓的“早熟收敛”现象，即在进化过程中早期陷入局部解而中止进化。采用合适的变异策略可提高群体中个体的多样性，从而防止这种现象的出现，有助于模型跳出局部极值。表8.3为[例1]的基因变异繁殖表。

表8.3 基因变异繁殖表

在[例1]中，用111、120分别繁殖两次，形成4个子代，维持种群数量平衡。随机选择120进行变异，变异的位数也是随机的。这里把它的第2位进行变异，即从1变为0，繁殖后形成子代为:70、110、121、127。可以看出新的子代比初始种群要好得多，其中甚至已经出现了最优解。如果对于地球物理的极小值问题，我们可以预先设置一个拟合精度，只要在种群中出现一个达到拟合精度的模型就可以终止反演了。

(7)收敛。

重复(3)~(6)的步骤，模型群体经多次选择、交换、更新、变异后，种群个体数量大小不变，模型目标函数平均值趋于稳定，最后聚集在模型空间中一个小范围内，则找到了全局极值对应的解，使目标函数最大或最小的模型就是全局最优模型。

对于具有多解性的地球物理反演问题来说，通过这一步有可能找到满足拟合精度的多个模型，对于实际反演解释、推断具有较高的指导意义。

遗传算法中的各种概率包括交换概率px、变异概率p_m以及更新概率p_u，这些参数的选择与设定目前尚无统一的理论指导，多数都视具体问题而定。Stoffa等(1991)的研究表明，适中的交换概率(p_x≈0.6)、较小的变异概率(p_m≈0.01)和较大的更新概率(p_u≈0.9)，遗传算法的性能较优。

与模拟退火反算法相同，遗传算法与传统的线性反演方法相比，该方法具有:不依赖初始模型的选择、能寻找全局最小点而不陷入局部极小、在反演过程中不用计算雅克比偏导数矩阵等优点。另外，遗传算法具有并行性，随着并行计算和集群式计算机技术的发展，该算法将会得到越来越广泛的研究与应用。

但是遗传算法作为类蒙特卡洛算法同样需要进行大量的正演计算，种群个体数量越大，繁衍代数越多，则计算量越大。所以和前面的最小二乘法相比，速度不是它的优势。

10. 遗传算法原理简介

遗传算法（Genetic Algorithm, GA）是一种进化计算（Evolutionary Computing）算法，属于人工智能技术的一部分。遗传算法最早是由John Holland和他的学生发明并改进的，源于对达芬奇物种进化理论的模仿。在物种进化过程中，为了适应环境，好的基因得到保留，不好的基因被淘汰，这样经过很多代基因的变化，物种的基因就是当前自然环境下适应度最好的基因。该算法被广泛应用于优化和搜索中，用于寻求最优解（或最优解的近似），其最主要的步骤包括交叉（crossover）和突变（mutation）。

所有的生物体都由细胞组成，每个细胞中都包含了同样的染色体（chromosome）。染色体由一串DNA组成，我们可以简单地把一个生物个体表示为一条染色体。每条染色体上都包含着基因，而基因又是由多个DNA组成的。每个基因都控制着个体某个性状的表达，例如眼睛的颜色、眼皮的单双等。在物种繁衍的过程中，首先发生交叉，来自于父母的染色体经过分裂和重组，形成后代的染色体。之后，后代有一定概率发生基因突变，即染色体上某个位置处的基因以一定概率发生变化。之后，对每一代都重复进行交叉和突变两个步骤。对于每一个后代，我们可以通过一定的方式测量其适应度。适应度越好的个体，在下一次交叉中被选中的概率越大，它的基因越容易传给下一代。这样，后代的适应度就会越来越好，直到收敛到一个稳定值。

在优化问题中，可行解总是有很多个，我们希望寻找一个最优解，它相对于其他可行解来说具有更好的适应度（即目标函数值更大或更小）。每个可行解就是一个“生物个体”，可以表示为状态空间中的一个点和适应度。每个解都是一个经过编码的序列，已二进制编码为例，每个解都是一个二进制序列。这样每个染色体就是一个二进制序列。遗传算法从从一组可行解开始，称为population，从population中随机选择染色体进行交叉产生下一代。这一做法的基于下一代的适应度会好于上一代。遗传算法的过程如下：

终止条件可以是达到了最大迭代次数，或者是前后连续几代的最优染色体的适应度差值小于一个阈值。以上算法描述也许还不够直观，我们举例说明。假设解可以用二进制编码表示，则每个染色体都是一个二进制序列。假设序列长度为16，则每个染色体都是一个16位的二进制序列：

首先，我们随机生成一个population，假设population size为20，则有20个长度为16的二进制序列。计算每个染色体的适应度，然后选取两个染色体进行交叉，如下图所示。下图在第6为上将染色体断开再重组，断开的位置是可以随机选择的。当然，断裂位置也可以不止一个。可以根据具体问题选择具体的交叉方式来提升算法性能。

之后，随机选取后代染色体上某个基因发生基因突变，突变的位置是随机选取的。并且，基因突变并不是在每个后代上都会发生，只是有一定的概率。对于二进制编码，基因突变的方式是按位取反：

上述例子是关于二进制编码的，像求解一元函数在某个区间内的最大最小值就可以使用二进制编码。例如，求解函数f(x)=x+sin(3x)+cos(3x)在区间[0,6]内的最小值。假设我们需要最小值点x保留4位小数，那么求解区间被离散成60000个数。因为2 {15}<60000<2 {16}，所以，需要16位二进制数来表示这60000个可能的解。其中0x0000表示0，0x0001表示0.0001，以此类推。针对这个例子，文末给出了demo code．

然而，在排序问题中无法使用二进制编码，应该采用排列编码（permutation encoding）。例如有下面两个染色体：

交叉：随机选取一个交叉点，从该出将两个染色体断开。染色体A的前部分组成后代1的前部分，然后扫描染色体B，如果出现了后代1中不包含的基因，则将其顺序加入后代1中。同理，染色体B的前部分组成了后代2的前部分，扫描染色体A获得后代2的后部分。注意，交叉的方式多种多样，此处只是举出其中一种方式。

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

突变：对于一个染色体，随机选中两个基因互换位置。例如第3个基因和倒数第2个基因互换：

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

此外还有值编码（value encoding）和树编码（tree encoding）等，具体例子可以参考这个链接： http://obitko.com/tutorials/genetic-algorithms/encoding.php

在实际的遗传算法中，往往会保留上一代中的少数几个精英（elite），即将上一代population中适应度最好的几个染色体加入到后代的poulation中，同时去除后代population中适应度最差的几个染色体。通过这个策略，如果在某次迭代中产生了最优解，则最优解能够一直保留到迭代结束。

用GA求函数最小值的demo code： https://github.com/JiaxYau/GA_test

参考资料 ：

[1] Introction to Genetic Algorithm, http://obitko.com/tutorials/genetic-algorithms/index.php

[2] Holland J H. Adaption in natural and artificial systems