Ⅰ 优化算法笔记（六）遗传算法
遗传算法(Genetic Algorithms，GA)是一种模拟自然中生物的遗传、进化以适应环境的智能算法。由于其算法流程简单，参数较少优化速度较快，效果较好，在图像处理、函数优化、信号处理、模式识别等领域有着广泛的应用。
在遗传算法（GA）中，每一个待求问题的候选解被抽象成为种群中一个个体的基因。种群中个体基因的好坏由表示个体基因的候选解在待求问题中的所的得值来评判。种群中的个体通过与其他个体交叉产生下一代，每一代中个体均只进行一次交叉。两个进行交叉的个体有一定几率交换一个或者多个对应位的基因来产生新的后代。每个后代都有一定的概率发生变异。发生变异的个体的某一位或某几位基因会变异成其他值。最终将以个体的适应度值为概率选取个体保留至下一代。
遗传算法启发于生物的繁殖与dna的重组，本次的主角选什么呢？还是根据大家熟悉的孟德尔遗传规律选豌豆吧，选动物的话又会有人疑车，还是植物比较好，本次的主角就是它了。
遗传算法包含三个操作（算子）：交叉，变异和选择操作。下面我们将详细介绍这三个操作。
大多数生物的遗传信息都储存在DNA，一种双螺旋结构的复杂有机化合物。其含氮碱基为腺嘌呤、鸟嘌呤、胞嘧啶及胸腺嘧啶。
表格中表示了一个有10个基因的个体，它们每一个基因的值为0或者1。
生物的有性生殖一般伴随着基因的重组。遗传算法中父辈和母辈个体产生子代个体的过程称为交叉。
表中给出了两个豌豆的基因，它们均有10个等位基因（即编号相同的基因）。
遗传算法的交叉过程会在两个个体中随机选择1位或者n位基因进行交叉，即这两个个体交换等位基因。
如，A豌豆和B豌豆在第6位基因上进行交叉，则其结果如下
当两个个体交叉的等位基因相同时，交叉过程也有可能没有产生新的个体，如交叉A豌豆和B豌豆的第2位基因时，交叉操作并没有产生新的基因。
一般的会给群体设定一个交叉率，crossRate，表示会在群体中选取一定比例的个体进行交叉，交叉率相对较大，一般取值为0.8。
基因的变异是生物进化的一个主要因素。
遗传算法中变异操作相对简单，只需要将一个随机位基因的值修改就行了，因为其值只为0或1，那么当基因为0时，变异操作会将其值设为1，当基因值为1时，变异操作会将其值设为0。
上图表示了A豌豆第3位基因变异后的基因编码。
与交叉率相似，变异操作也有变异率，alterRate，但是变异率会远低于交叉率，否则会产生大量的随机基因。一般变异率为0.05。
选择操作是遗传算法中的一个关键操作，它的主要作用就是根据一定的策略随机选择个体保留至下一代。适应度越优的个体被保留至下一代的概率越大。
实现上，我们经常使用“轮盘赌”来随机选择保留下哪个个体。
假设有4个豌豆A、B、C、D，它们的适应度值如下：
适应度值越大越好，则它们组成的轮盘如下图：
但由于轮盘赌选择是一个随机选择过程，A、B、C、D进行轮盘赌选择后产生的下一代也有可能出现A、A、A、A的情况，即虽然有些个体的适应度值不好，但是运气不错，也被选择留到了下一代。
遗产算法的三个主要操作介绍完了，下面我们来看看遗传算法的总体流程：
前面我们说了遗传算法的流程及各个操作，那么对于实际的问题我们应该如何将其编码为基因呢？
对于计算机来所所有的数据都使用二进制数据进行存放，如float类型和double类型的数据。
float类型的数据将保存为32位的二进制数据：1bit（符号位） 8bits（指数位） 23bits（尾数位）
如-1.234567f，表示为二进制位
Double类型的数据将保存为64位的二进制数据：1bit（符号位） 11bits（指数位） 53bits（尾数位）
如-1.234567d，表示为二进制为
可以看出同样的数值不同的精度在计算机中存储的内容也不相同。之前的适应度函数 ，由于有两个double类型的参数，故其进行遗传算法基因编码时，将有128位基因。
虽然基因数较多，但好在每个基因都是0或者1，交叉及变异操作非常简单。
相比二进制编码，十进制编码的基因长度更短，适应度函数 有两个输入参数，那么一个个体就有2个基因，但其交叉、变异操作相对复杂。
交叉操作
方案1：将一个基因作为一个整体，交换两个个体的等位基因。
交换前
交换第1位基因后
方案2：将两个个体的等位基因作为一个整体，使其和不变，但是值随机
交换前
交换第1位基因后
假设A、B豌豆的第一位基因的和为40，即 ,第一位基因的取值范围为0-30，那么A、B豌豆的第一位基因的取值范围为[10,30],即 为[0,30]的随机数， 。
变异操作，将随机的一位基因设置为该基因取值范围内的随机数即可。
这个过程说起来简单但其实现并不容易。
我们要将它们的值映射到一个轴上才能进行随机选择，毕竟我们无法去绘制一个轮盘来模拟这个过程
如图，将ABCD根据其值按顺序排列，取[0,10]内的随机数r，若r在[0,1]内则选择A,在(1,3]内则选择B,在(3,6]内则选择C,在(6,10]则选择D。
当然这仍然会有问题，即当D>>A、B、C时，假如它们的值分布如下
那么显然，选D的概率明显大于其他，根据轮盘赌的选择，下一代极有可能全是D的后代有没有办法均衡一下呢？
首先我想到了一个函数，
不要问我为什么我不知道什么是神经什么网络的，什么softmax、cnn统统没听说过。
这样一来，它们之间的差距没有之前那么大了，只要个体适应度值在均值以上那么它被保留至下一代的概率会相对较大，当然这样缩小了个体之间的差距，对真正优秀的个体来说不太公平，相对应，我们可以在每次选择过程中保留当前的最优个体到下一代，不用参与轮盘赌这个残酷的淘汰过程。
最令人高兴的环节到了，又可以愉快的凑字数了。
由于遗传算法的收敛速度实在是太慢，区区50代，几乎得不到好的结果，so我们把它的最大迭代次数放宽到200代。
使用二进制编码来进行求解
参数如下：
求解过程如上图，可以看出基因收敛的很快，在接近20代时就图中就只剩一个点了，之后的点大概是根据变异操作产生。看一下最后的结果。
可以看出最好的结果已经得到了最优解，但是10次实验的最差值和平均值都差的令人发指。为什么会这样呢？
问题出在二进制编码上，由于double类型的编码有11位指数位和52位小数位，这会导致交叉、变异操作选到指数位和小数位的概率不均衡，在小数位上的修改对结果的影响太小而对指数为的修改对结果的影响太大，
如-1.234567d，表示为二进制为
对指数为第5位进行变异操作后的结果为-2.8744502924382686E-10，而对小数位第5为进行变异操作后的结果为-1.218942。可以看出这两部分对数值结果的影响太不均衡，得出较好的结果时大概率是指数位与解非常相近，否则很难得出好的结果，就像上面的最差值和均值一样。
所以使用上面的二进制编码不是一个好的基因编码方式，因此在下面的实验中，将使用十进制来进行试验。
使用:十进制编码来进行求解
参数如下：
我们可以看到直到40代时，所有的个体才收束到一点，但随后仍不断的新的个体出现。我们发现再后面的新粒子总是在同一水平线或者竖直线上，因为交叉操作直接交换了两个个体的基因，那么他们会相互交换x坐标或者y坐标，导致新个体看起来像在一条直线上。
我们来看看这次的结果。
这次最优值没有得到最优解，但是最差值没有二进制那么差，虽然也不容乐观。使用交换基因的方式来进行交叉操作的搜索能力不足，加之轮盘赌的选择会有很大概率选择最优个体，个体总出现在矩形的边上。
下面我们先改变轮盘赌的选择策略，使用上面的sigmod函数方案，并且保留最优个体至下一代。
使用:十进制编码来进行求解
参数如下：
看图好像跟之前的没什么区别，让我们们看看最终的结果：
可以看出，最优值没有什么变化，但是最差值和平均值有了较大的提升，说明该轮盘赌方案使算法的鲁棒性有了较大的提升。在每次保留最优个体的情况下，对于其他的个体的选择概率相对平均，sigmod函数使得即使适应度函数值相差不太大的个体被选到的概率相近，增加了基因的多样性。
使用:十进制编码来进行求解，改变交叉方案，保持两个个体等位基因和不变的情况下随机赋值。
参数如下：
上图可以看出该方案与之前有明显的不同，在整个过程中，个体始终遍布整个搜索空间，虽然新产生的个体大多还是集中在一个十字架型的位置上，但其他位置的个体比之前的方案要多。
看看结果，
这次的结果明显好于之前的所有方案，但仍可以看出，十进制的遗传算法的精度不高，只能找到最优解的附近，也有可能是算法的收敛速度实在太慢，还没有收敛到最优解。
遗传算法的探究到此也告一段落，在研究遗传算法时总有一种力不从心的感觉，问题可能在于遗传算法只提出了一个大致的核心思想，其他的实现细节都需要自己去思考，而每个人的思维都不一样，一万个人能写出一万种遗传算法，其实不仅是遗传算法，后面的很多算法都是如此。
为什么没有对遗传算法的参数进行调优，因为遗传算法的参数过于简单，对结果的影响的可解释性较强，意义明显，实验的意义不大。
遗传算法由于是模仿了生物的进化过程，因此我感觉它的求解速度非常的慢，而且进化出来的结果不一定是最适应环境的，就像人的阑尾、视网膜结构等，虽然不是最佳的选择但是也被保留到了今天。生物的进化的随机性较大，要不是恐龙的灭绝，也不会有人类的统治，要不是人类有两只手，每只手有5根手指，也不会产生10进制。
以下指标纯属个人yy,仅供参考
目录
上一篇 优化算法笔记（五）粒子群算法（3）
下一篇 优化算法笔记（七）差分进化算法
优化算法matlab实现（六）遗传算法matlab实现
Ⅱ 遗传算法 交叉的个数怎么确定
遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
Ⅲ 遗传算法<sup>[1，]</sup>
遗传算法，又称基因算法(Genetic Algorithm，简称GA)，也是一种启发式蒙特卡洛优化算法。遗传算法最早是由Holland(1975)提出，它模拟了生物适者生存、优胜劣汰的进化过程，具有不依赖于初始模型的选择、不容易陷入局部极小、在反演过程中不用计算偏导数矩阵等优点。遗传算法最早由Stoffa和Sen(1991)用于地震波的一维反演，之后在地球物理资料的非线性反演中得到广泛的应用。GA算法对模型群体进行追踪、搜索，即模型状态通过模型群体传送，具有比模拟退火法更大、更复杂的“记忆”，潜力更大。
遗传算法在反演中的基本思路和过程是:
(1)将生物体看成模型，模型参数看成染色体，有多少个模型的参数就有多少个染色体。对每个模型的参数(染色体)用二进制进行编码，这个编码就是基因。
(2)随机生成一个模型群体(相当于生物的种群)，然后在模型群体中进行繁殖，通过母本的选择、交换和变异等遗传操作产生下一代，然后保留较好基因，淘汰较差基因。
(3)通过一代一代的繁殖优胜劣汰的进化过程，最后所剩下的种群基本上都是最优的基因，种群趋于一致。所谓群体“一致”，即群体目标函数的方差或标准差很小，或者群体目标函数的均值接近于极值(可能是极大值或极小值)，从而获得非线性反演问题所对应的最优解或近似最优解。
下面以一个实例来简述遗传算法的基本过程。
[例1]设m是正整数，且0≤m≤127，求方程φ(m)=m2的极大值。
这个例子极为简单，只有一个模型参数，因此只有一条染色体，目标函数的极值是极大值(此例子来自阮百尧课件)。遗传算法通过以下7个步骤来实现:
(1)模型参数二进制编码。
每个模型参数就是一条染色体，把十进制的模型参数表示为二进制，这就是基因。首先确定二进制码的长度(基因的长度):
2N=[mmax(i)-mmin(i)]/Δm(i) (8.20)
其中:N为第i条染色体基因的长度(也就是第i个模型参数的二进制码位数);[mmin(i)，mmax(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(mi)为繁殖概率;φ(mi)为第i个模型的目标函数;φAVG为目标函数的平均值。对于极小化问题来说，规定目标函数值高于平均值的不传代;对于极大化问题来说，反之即可。
就[例1]来说，要求目标函数取极大值，所以规定目标函数小于平均值的模型不传代，大于它的可以传代。对第一代，为了防止基因丢失，可先不舍去繁殖概率小的模型，让它与概率大的模型配对。如:本例中70与56配对，101与15配对产生子代，见表8.2。
表8.2 基因交换表
(4)基因交换。
将配对的两个亲本模型的部分染色体相互交换，其中交换点可随机选择，形成两个新的子代(见表8.2)。两个染色体遗传基因的交换过程是遗传算法的“繁殖”过程，是母本的重组过程。
为了使染色体的基因交换比较彻底，Stoffa等人提出了一个交换概率px来控制选择操作的效果。如果px的值较小，那么交换点的位置就比较靠低位，这时的交换操作基本是低位交换，交换前后模型的染色体变化不是太大。如果px的值较大，那么交换点的位置就比较靠高位，此时的交换操作可以在较大的染色体空间进行，交换前后模型数值变化可以很大。
在[例1]中:15、101和56、70作为母本通过交换繁殖出子代5、6、111、120。所选择的基因交换位置见表8.2。有下划线的，是要交换的基因位置。
(5)更新。
母本模型和子本模型如何选择保留一定数量作为新的母本，就是模型更新。不同的策略会导致不同的结果。一般而言，若产生的新一代模型较好，则选择新一代模型而淘汰上一代模型。否则，则必须根据一定的更新概率pu来选择上一代模型来取代新一代中某些较劣的模型。
经过更新以后，繁殖时对子代再进行优胜劣汰的选择。对于极大值问题，大于目标函数平均值的子代可以繁殖，小于目标函数平均值的子代不能繁殖。由于新的种群能繁殖的个体数量减小了，所以要多繁殖几次，维持种群个体的数量保持平衡。
在[例1]中，子代较好，所以完全淘汰上一代模型，完全用子代作为新的母本。选择子代目标函数最大的两个模型进行繁殖，分别是111、120。
(6)基因变异。
在新的配对好的母本中，按一定比例随机选择模型进行变异，变异操作就是模拟自然界中的环境因素，就是按比较小的变异概率pm将染色体某位或某几位的基因发生突变(即将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、变异概率pm以及更新概率pu，这些参数的选择与设定目前尚无统一的理论指导，多数都视具体问题而定。Stoffa等(1991)的研究表明，适中的交换概率(px≈0.6)、较小的变异概率(pm≈0.01)和较大的更新概率(pu≈0.9)，遗传算法的性能较优。
与模拟退火反算法相同，遗传算法与传统的线性反演方法相比，该方法具有:不依赖初始模型的选择、能寻找全局最小点而不陷入局部极小、在反演过程中不用计算雅克比偏导数矩阵等优点。另外，遗传算法具有并行性，随着并行计算和集群式计算机技术的发展，该算法将会得到越来越广泛的研究与应用。
但是遗传算法作为类蒙特卡洛算法同样需要进行大量的正演计算，种群个体数量越大，繁衍代数越多，则计算量越大。所以和前面的最小二乘法相比，速度不是它的优势。
Ⅳ 遗传算法
参考文献： 知乎 遗传算法 编码解码知识
实现遗传算法的第一步就是明确对求解问题的编码和解码方式。对于函数优化问题，一般有两种编码方式，各具优缺点
实数编码：直接用实数表示基因，容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优
二进制编码：稳定性高，种群多样性大，但需要的存储空间大，需要解码且难以理解
对于求解函数最大值问题，我选择的是二进制编码。
以我们的目标函数 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 为例。
假如设定求解的精度为小数点后4位，可以将x的解空间划分为 (9-0)×(1e+4)=90000个等分。
2^16<90000<2^17，需要17位二进制数来表示这些解。换句话说，一个解的编码就是一个17位的二进制串。
一开始，这些二进制串是随机生成的。
一个这样的二进制串代表一条染色体串，这里染色体串的长度为17。
对于任何一条这样的染色体chromosome，如何将它复原(解码)到[0,9]这个区间中的数值呢？
对于本问题，我们可以采用以下公式来解码：
decimal( ): 将二进制数转化为十进制数
一般化解码公式：
lower_bound: 函数定义域的下限
upper_bound: 函数定义域的上限
chromosome_size: 染色体的长度
通过上述公式，我们就可以成功地将二进制染色体串解码成[0,9]区间中的十进制实数解。
染色体，就是指由 DNA 组成的聚合体，DNA 上的每个基因都编码了一个独特的性状，比如，头发或者眼睛的颜色
可以将他看作是一个优化问题，它可以尝试找出某些输入，凭借这些输入我们便可以得到最佳的输出值或者是结果
遗传算法要点：
1.初始化
初始化候选全体，随机初始化
2.查找适应函数
3.选择：物竞天择，适者生存
先选择能量强的个体，然后再进行随机选择，选出适应度虽然小，但是幸存下来的个体
4.交叉：
5.变异：根据需要进行选择
Ⅳ 遗传算法的编码方法有几种
常用的编码介绍
1、二进制编码：
（1）定义：二进制编码方法是使用二值符号集{0,1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
（2）举例：0≤x≤1023,精度为1,m表示二进制编码的长度。则有建议性说法：使
2m-1≤1000（跟精度有关）≤2m-1。取m=10
则X:0010101111就可以表示一个个体，它所对应的问题空间的值是x=175。
（3）优缺点
优点：符合最小字符集原则，便于用模式定理分析；
缺点：连续函数离散化时的映射误差。
2、格雷码编码
（1）定义：格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。它是二进制编码方法的一种变形。
十进制数0—15之间的二进制码和相应的格雷码分别编码如下。
二进制编码为：0000，0001，0010，001
1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷码编码为：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）举例：对于区间[0。1023]中两个邻近的整数X1=175和X2=176，若用长度为10位的二进制编码，可表示为X11：0010101111和X12
0010110000，而使用同样长度的格雷码，它们可分别表示为X21：0010101111和X22：0010101000。
（3）优点：增强了遗传算法的局部搜索能力，便于连续函数的局部控件搜索。
3、浮点数(实数)编码
（1）定义：浮点数编码是指个体的每个基因值用某一范围内的一个浮点数来表示，而个体的编码长度等于其决策变量的个数。因为这种编码方法使用的决策变量的真实值，也称之为真值编码方法。
（2）举例：
（3）优点：实数编码是遗传算法中在解决连续参数优化问题时普遍使用的一种编码方式，具有较高的精度，在表示连续渐变问题方面具有优势。
4、排列编码
排列编码也叫序列编码，是针对一些特殊问题的特定编码方式。排序编码使问题简洁，易于理解。该编码方式将有限集合内的元素进行排列。若集合内包含m个元素，则存在m!种排列方法，当m不大时，m!也不会太大，穷举法就可以解决问题。当m比较大时，m!就会变得非常大，穷举法失效，遗传算法在解决这类问题上具有优势。如解决TSP问题时，用排列编码自然、合理。
5、其它编码方式
多参数级联编码等
Ⅵ 遗传算法的基本原理
遗传算法的基本原理和方法
一、编码
编码：把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。
解码（译码）：遗传算法解空间向问题空间的转换。
二进制编码的缺点是汉明悬崖（Hamming Cliff），就是在某些相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变都难以跨越。
格雷码（Gray Code）：在相邻整数之间汉明距离都为1。
（较好）有意义的积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积木块；最小字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或描述。
二进制编码比十进制编码搜索能力强，但不能保持群体稳定性。
动态参数编码（Dynamic Paremeter Coding）：为了得到很高的精度，让遗传算法从很粗糙的精度开始收敛，当遗传算法找到一个区域后，就将搜索现在在这个区域，重新编码，重新启动，重复这一过程，直到达到要求的精度为止。
编码方法：
1、 二进制编码方法
缺点：存在着连续函数离散化时的映射误差。不能直接反映出所求问题的本身结构特征，不便于开发针对问题的专门知识的遗传运算算子，很难满足积木块编码原则
2、 格雷码编码滚如：连续的两个整数所对应的编码之间仅仅只有一个码位是不同的，其余码位都相同。
3、 浮点数编码方法：个体的每个基因值用某一范围内的某个浮点数来表示，个体的编码长度等于其决策变量的位数。
4、 各参数级联编码：对含有多个变量的个体进行编码的方法。通常将各个参数分别以某种编码方法进行编码，然后再将他们的编码按照一定顺序连接在一起就组成了表示全部参数的个体编码。
5、 多参数交叉编码：将各个参数中起主要作用的码位集中在一起，这样它们就不易于被遗传算子破坏掉。
评估编码的三个规范：完备性、健全性、非冗余性。
二、选择
遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。
常用的选择算子：
1、 轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。
2、 随机竞争选择（Stochastic Tournament）：每次按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。
3、 最佳保留选择：首先按轮盘赌选择方法执行遗传算法的选择操作，然后将当前群体中适应度最高的大宏启个体结构完整地复制到下一代群体中。
4、 无回放随机选择（也叫期望值选择Excepted Value Selection）：根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下
（1） 计算群体中每个个体在下一代群体中的生存期望数目N。
（2） 若某一个体被选中参与交叉运算，则它在下一代中的生存期望数目减去0.5，若某一个体未被选中参与交叉运算，则它绝配在下一代中的生存期望数目减去1.0。
（3） 随着选择过程的进行，若某一个体的生存期望数目小于0时，则该个体就不再有机会被选中。
5、 确定式选择：按照一种确定的方式来进行选择操作。具体操作过程如下：
（1） 计算群体中各个个体在下一代群体中的期望生存数目N。
（2） 用N的整数部分确定各个对应个体在下一代群体中的生存数目。
（3） 用N的小数部分对个体进行降序排列，顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中M个个体。
6、无回放余数随机选择：可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中，因而选择误差比较小。
7、均匀排序：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。
8、最佳保存策略：当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。
9、随机联赛选择：每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。
10、排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高群体的多样性。
三、交叉
遗传算法的交叉操作，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。
适用于二进制编码个体或浮点数编码个体的交叉算子：
1、单点交叉（One－pointCrossover）：指在个体编码串中只随机设置一个交叉点，然后再该点相互交换两个配对个体的部分染色体。
2、两点交叉与多点交叉：
（1） 两点交叉（Two－pointCrossover）：在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。
（2） 多点交叉（Multi－pointCrossover）
3、均匀交叉（也称一致交叉，UniformCrossover）：两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新个体。
4、算术交叉（ArithmeticCrossover）：由两个个体的线性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体。
四、变异
遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成以给新的个体。
以下变异算子适用于二进制编码和浮点数编码的个体：
1、基本位变异（SimpleMutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。
2、均匀变异（UniformMutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）
3、边界变异（BoundaryMutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。
4、非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。
5、高斯近似变异：进行变异操作时用符号均值为P的平均值，方差为P2的正态分布的一个随机数来替换原有的基因值。
Ⅶ 遗传算法
遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过编码（decoding），可以作为问题近似最优解。
5.4.1 非线性优化与模型编码
假定有一组未知参量
xi（i=1，2，…，M）
构成模型向量m，它的非线性目标函数为Φ（m）。根据先验知识，对每个未知量都有上下界αi及bi，即αi≤x≤bi，同时可用间隔di把它离散化，使
di=（bi-αi）/N （5.4.1）
于是，所有允许的模型m将被限制在集
xi=αi+jdi（j=0，1，…，N） （5.4.2）
之内。
通常目标泛函（如经济学中的成本函数）表示观测函数与某种期望模型的失拟，因此非线性优化问题即为在上述限制的模型中求使Φ（m）极小的模型。对少数要求拟合最佳的问题，求目标函数的极大与失拟函数求极小是一致的。对于地球物理问题，通常要进行杀重离散化。首先，地球模型一般用连续函数表示，反演时要离散化为参数集才能用于计算。有时，也将未知函数展开成已知基函数的集，用其系数作为离散化的参数集xi，第二次离散化的需要是因为每一个未知参数在其变化范围内再次被离散化，以使离散模型空间最终包含着有限个非线性优化可选择的模型，其个数为
地球物理数据处理教程
其中M为未知参数xi的个数。由此式可见，K决定于每个参数离散化的间隔di及其变化范围（αi，bi），在大多数情况下它们只能靠先验知识来选择。
一般而言，优化问题非线性化的程度越高，逐次线性化的方法越不稳定，而对蒙特卡洛法却没有影响，因为此法从有限模型空间中随机地挑选新模型并计算其目标函数 Φ（m）。遗传算法与此不同的是同时计算一组模型（开始时是随机地选择的），然后把它进行二进制编码，并通过繁殖、杂交和变异产生一组新模型进一步有限的模型空间搜索。编码的方法可有多种，下面举最简单的例说明之，对于有符号的地球物理参数反演时的编码方式一般要更复杂些。
假设地球为有三个水平层的层次模型，含层底界面深度hj（j=1，2，3）及层速度vj（j=1，2，3）这两组参数。如某个模型的参数值为（十进制）：
h1=6，h2=18，h3=28，单位为10m
v1=6，v2=18，v3=28，单位为 hm/s
按正常的二进制编码法它们可分别用以下字符串表示为：
地球物理数据处理教程
为了减少字节，这种编码方式改变了惯用的单位制，只是按精度要求（深度为10m，波速为hm/s）来规定参数的码值，同时也意味着模型空间离散化间距di都规格化为一个单位（即10m，或hm/s）。当然，在此编码的基础上，还可以写出多种新的编码字符串。例如，三参数值的对应字节顺序重排，就可组成以下新的二进制码串：
地球物理数据处理教程
模型参数的二进制编码是一种数学上的抽象，通过编码把具体的非线性问题和生物演化过程联系了起来，因为这时形成的编码字符串就相当于一组遗传基因的密码。不仅是二进制编码，十进制编码也可直接用于遗传算法。根据生物系统传代过程的规律，这些基因信息将在繁殖中传到下一带，而下一代将按照“适者生存”的原则决定种属的发展和消亡，而优化准则或目标函数就起到了决定“适者生存”的作用，即保留失拟较小的新模型，而放弃失拟大的模型。在传带过程中用编码表示的基因部分地交合和变异，即字符串中的一些子串被保留，有的改变，以使传代的过程向优化的目标演化。总的来说，遗传算法可分为三步：繁殖、杂交和变异。其具体实现过程见图5.8。
图5.8 遗传算法实现过程
5.4.2 遗传算法在地震反演中的应用
以地震走时反演为例，根据最小二乘准则使合成记录与实测数据的拟合差取极小，目标函数可取为
地球物理数据处理教程
式中：Ti，0为观测资料中提取出的地震走时；Ti，s为合成地震或射线追踪算出的地震走时；ΔT为所有合成地震走时的平均值；NA为合成地震数据的个数，它可以少于实测Ti，0的个数，因为在射线追踪时有阴影区存在，不一定能算出合成数据Tj，0。利用射线追踪计算走时的方法很多，参见上一章。对于少数几个波速为常数的水平层，走时反演的参数编码方法可参照上一节介绍的分别对深度和速度编码方法，二进制码的字符串位数1不会太大。要注意的是由深度定出的字符串符合数值由浅到深增大的规律，这一约束条件不应在杂交和传代过程中破坏。这种不等式的约束（h1＜h2＜h3…）在遗传算法中是容易实现的。
对于波场反演，较方便的做法是将地球介质作等间距的划分。例如，将水平层状介质细分为100个等厚度的水平层。在上地壳可假定波速小于6400 m/s（相当于解空间的硬约束），而波速空间距为100m/s，则可将波速用100m/s为单位，每层用6位二进制字符串表示波速，地层模型总共用600位二进制字符串表示（l=600）。初始模型可随机地选取24～192个，然后通过繁殖杂交与变异。杂交概率在0.5～1.0之间，变异概率小于0.01。目标函数（即失拟方程）在频率域可表示为
地球物理数据处理教程
式中：P0（ωk，vj）为实测地震道的频谱；ωk为角频率；vj为第j层的波速；Ps（ωk，vj）为相应的合成地震道；A（ωk）为地震仪及检波器的频率滤波器，例如，可取
A（ω）=sinC4（ω/ωN） （5.4.6）
式中ωN为Nyquist频率，即ωN=π/Δt，Δt为时间采样率。参数C为振幅拟合因子，它起到合成与观测记录之间幅度上匹配的作用。C的计算常用地震道的包络函数的平均比值。例如，设E［］为波动信号的包络函数，可令
地球物理数据处理教程
式中：tmax为包络极大值的对应时间；J为总层数。包络函数可通过复数道的模拟取得。
用遗传算法作波速反演时失拟最小的模型将一直保存到迭代停止。什么时候停止传代还没有理论上可计算的好办法，一般要显示解空间的搜索范围及局部密度，以此来判断是否可以停止传代。值得指出的是，由（5.4.4）和（5.4.5）式给出的目标函数对于有误差的数据是有问题的，反演的目标不是追求对有误差数据的完美拟合，而是要求出准确而且分辨率最高的解估计。
遗传算法在执行中可能出现两类问题。其一称为“早熟”问题，即在传代之初就随机地选中了比较好的模型，它在传代中起主导作用，而使其后的计算因散不开而白白浪费。通常，增加Q值可以改善这种情况。另一类问题正相反，即传相当多代后仍然找不到一个特别好的解估计，即可能有几百个算出的目标函数值都大同小异。这时，最好修改目标函数的比例因子（即（5.4.5）式的分母），以使繁殖概率Ps的变化范围加大。
对于高维地震模型的反演，由于参数太多，相应的模型字符串太长，目前用遗传算法作反演的计算成本还嫌太高。实际上，为了加快计算，不仅要改进反演技巧和传代的控制技术，而且还要大幅度提高正演计算的速度，避免对遗传算法大量的计算花费在正演合成上。