遗传算法精度 遗传算法精度是几位数的

优化算法笔记（六）遗传算法

遗传算法(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，表示为二进制位10111111100111100000011001001011

Double类型的数据将保存为64位的二进制数据：1bit（符号位） 11bits（指数位） 53bits（尾数位）

如-1.234567d，表示为二进制为1011111111110011110000001100100101010011100110111000100010000111

可以看出同样的数值不同的精度在计算机中存储的内容也不相同。之前的适应度函数 ，由于有两个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，表示为二进制为1011111111110011110000001100100101010011100110111000100010000111

对指数为第5位进行变异操作后的结果为-2.8744502924382686E-10，而对小数位第5为进行变异操作后的结果为-1.218942。可以看出这两部分对数值结果的影响太不均衡，得出较好的结果时大概率是指数位与解非常相近，否则很难得出好的结果，就像上面的值和均值一样。

所以使用上面的二进制编码不是一个好的基因编码方式，因此在下面的实验中，将使用十进制来进行试验。

使用:十进制编码来进行求解

参数如下：

我们可以看到直到40代时，所有的个体才收束到一点，但随后仍不断的新的个体出现。我们发现再后面的新粒子总是在同一水平线或者竖直线上，因为交叉操作直接交换了两个个体的基因，那么他们会相互交换x坐标或者y坐标，导致新个体看起来像在一条直线上。

我们来看看这次的结果。

这次值没有得到解，但是值没有二进制那么，虽然也不容乐观。使用交换基因的方式来进行交叉操作的搜索能力不足，加之的选择会有很大概率选择个体，个体总出现在矩形的边上。

下面我们先改变的选择策略，使用上面的sigmod函数方案，并且保留个体至下一代。

使用:十进制编码来进行求解

参数如下：

看图好像跟之前的没什么区别，让我们们看看终的结果：

可以看出，值没有什么变化，但是值和平均值有了较大的提升，说明该方案使算法的鲁棒性有了较大的提升。在每次保留个体的情况下，对于其他的个体的选择概率相对平均，sigmod函数使得即使适应度函数值相不太大的个体被选到的概率相近，增加了基因的多样性。

使用:十进制编码来进行求解，改变交叉方案，保持两个个体等位基因和不变的情况下随机赋值。

参数如下：

上图可以看出该方案与之前有明显的不同，在整个过程中，个体始终遍布整个搜索空间，虽然新产生的个体大多还是集中在一个十字架型的位置上，但其他位置的个体比之前的方案要多。

看看结果，

这次的结果明显好于之前的所有方案，但仍可以看出，十进制的遗传算法的精度不高，只能找到解的附近，也有可能是算法的收敛速度实在太慢，还没有收敛到解。

遗传算法的探究到此也告一段落，在研究遗传算法时总有一种力不从心的感觉，问题可能在于遗传算法只提出了一个大致的核心思想，其他的实现细节都需要自己去思考，而每个人的思维都不一样，一万个人能写出一万种遗传算法，其实不仅是遗传算法，后面的很多算法都是如此。

为什么没有对遗传算法的参数进行调优，因为遗传算法的参数过于简单，对结果的影响的可解释性较强，意义明显，实验的意义不大。

遗传算法由于是模仿了生物的进化过程，因此我感觉它的求解速度非常的慢，而且进化出来的结果不一定是适应环境的，就像人的阑尾、视网膜结构等，虽然不是佳的选择但是也被保留到了今天。生物的进化的随机性较大，要不是恐龙的灭绝，也不会有人类的统治，要不是人类有两只手，每只手有5根手指，也不会产生10进制。

以下指标纯属个人yy,仅供参考

目录

上一篇 优化算法笔记（五）粒子群算法（3）

下一篇 优化算法笔记（七）分进化算法

优化算法matlab实现（六）遗传算法matlab实现

蚁群算法和遗传算法那个精度高

遗传算比较强全局搜索能力特别交叉概率比较能产量新体提高全局搜索范围遗传算适合求解离散问题具备数理论支持存着汉明悬崖等问题

蚁群算适合图搜索路径问题计算销

两者都随机算遗传算仿算；蚁群算数算应用目前广算 针同研究向所体现优缺点两算混合优势互补提高优化性能并且别求解离散空间连续空间优化问题

基本遗传算法介绍

遗传算法是群智能优化计算中应用为广泛、为成功、代表性的智能优化方法。它是以达尔文的生物进化论和孟德尔的遗传变异理论为基础，模拟生物进化过程和机制，产生的一种群体导向随机搜索技术和方法。

遗传算法的基本思想：首先根据待求解优化问题的目标函数构造一个适应度函数。然后，按照一定的规则生成经过基因编码的初始群体，对群体进行评价、遗传运算（交叉和变异）、选择等操作。经过多次进化，获得适应度的一个或几个个体作为问题的解。

编码是对问题的可行解的遗传表示，是影响算法执行效率的关键因素的之一。遗传算法中，一个解 称为个体或染色体（chromosome），染色体由被称为基因（gene）的离散单元组成，每个基因控制颜色体的一个或多个特性，通常采用固定长度的0-1二进制编码，每个解对应一个的二进制编码串编码空间中的二进制位串称为基因型（genotype）。而实际所表示问题的解空间的对应点称为表现型（phenotype）。

种群由个体构成，每个个体的染色体对应优化问题的一个初始解。

适应度函数是评价种群中个体对环境适应能力的确定性指标，体现出“适者生存，优胜劣汰”这一自然选择原则。

遗传算法在每次迭代过程中，在父代种群中采用某种选择策略选择出指定数目的哥特体提进行遗传操作。常用的选择策略是正比选择（proportional selection）策略。

在 交叉算子中，通常由两个被称为父代（parent）的染色体组合，形成新的染色体，称为子代（offspring）。父代是在种群中根据个体适应度进行选择，因此适应度较高的染色体的基因更有可能被遗传到下一代 。通过在迭代过程中不断地应用交叉算子，使优良个体的基因得以在种群中频繁出现，终使得整个种群收敛到一个解。

在染色体交叉之后产生的子代个体，其基因位可能以很小的概率发生转变，这个过程称为变异。变异是为了增强种群的多样性，将搜索跳出局部解。

遗传算法的停止准则一般采用设定迭代次数或适应值函数评估次数，也可以是规定的搜索精度。

已Holland的基本GA为例介绍算法等具体实现，具体的执行过程描述如下：

Step 1： 初始化 。随机生成含有 个个体的初始种群 ，每个个体经过编码对应着待求解优化问题的一个初始解。

Step 2： 计算适应值 。个体 ，由指定的适应度函数评价其适应环境的能力。不同的问题，适应度函数的构造方式也不同。对函数优化问题，通常取目标函数作为适应度函数。

Step 3： 选择 。根据某种策略从当前种群中选择出 个个体作为重新繁殖的下一代群体。选择的依据通常是个体的适应度的高低，适应度高的个体相比适应度低的个体为下一代贡献一个或多个后代的概率更大。选择过程提现了达尔文“适者生存”原则。

Step 4： 遗传操作 。在选出的 个个体中，以事件给定的杂交概率 任意选择出两个个体进行 交叉运算 ，产生两个新的个体，重复此过程直到所有要求杂交的个体杂交完毕。根据预先设定的变异概率 在 个个体中选择出若干个体，按一定的策略对选出的个体进行 变异运算 。

Step 5： 检验算法等停止条件 。若满足，则停止算法的执行，将个体的染色体进行解码得到所需要的解，否则转到 Step 2 继续进行迭代过程。

遗传算法^[1，]

遗传算法，又称基因算法(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)，遗传算法的性能较优。

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

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

为什么个体数目增加会导致遗传算法精度降低

你没有理解选择操作。

选择结果这一列与初始群体这一列并不是一一对应的关系。

选择结果这一列说明，第一次轮法选择到了第1个个体，第二次轮法选择到了第4个个体，第三次轮法选择到了第2个个体，第四次轮法选择到了第4个个体。

轮法的随机性使得选择结果也可能如下：

111001

011101

111001

101011