遗传算法代数

❶ 什么是遗传算法

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型：
遗传算法式中x为决策
变量，式2-1为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。
遗传算法的基本运算过程如下：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。
f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(indivial)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

❷ 遗传算法怎么回事

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型: 遗传算法式中为决策变量，为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。遗传算法的基本运算过程如下:a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算

❸ 遗传算法运行相同的代数可能得到不同的结果吗

是的，遗传算法是近似算法，每次运行得到的解都是近似最优解，所以它们有可能不同。
但只要算法设计合理，能收敛到最优解，那么每次运行都能得到相同的最优解，如果最优解唯一的话。

❹ 遗传算法的运算过程

遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。
遗传操作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。这三个遗传算子有如下特点：
个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。
遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。
其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法
显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。 在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：
a)实值重组（real valued recombination）
1)离散重组（discrete recombination）
2)中间重组（intermediate recombination）
3)线性重组（linear recombination）
4)扩展线性重组（extended linear recombination）。
b)二进制交叉（binary valued crossover）
1)单点交叉（single-point crossover）
2)多点交叉（multiple-point crossover）
3)均匀交叉（uniform crossover）
4)洗牌交叉（shuffle crossover）
5)缩小代理交叉（crossover with reced surrogate）。
最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：
个体A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新个体
个体B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新个体 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：
a)实值变异
b)二进制变异。
一般来说，变异算子操作的基本步骤如下：
a)对群中所有个体以事先设定的变异概率判断是否进行变异
b)对进行变异的个体随机选择变异位进行变异。
遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。
遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。
基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下：
基因位下方标有*号的基因发生变异。
变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001－0.1。 当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。

❺ 遗传算法

根据问题的目标函数构造一个适值函数，对一个由多个解（每个解对应一个染色体）构成的种群进行评估、遗传、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。

1，产生一个初始种群

2，根据问题的目标函数构造适值函数

3，根据适应值的好坏不断选择和繁殖

4，若干代后得到适应值最好的个体即为最优解

1.种群和种群大小

一般越大越好，但是规模越大运算时间越大，一般设为100~1000

2. 编码方法 （基因表达方法

3. 遗传算子

包括交叉和变异，模拟了每一代中创造后代的繁殖过程。是遗传算法的精髓

交叉：性能在很大程度上取决于交叉运算的性能，交叉率Pc：各代中交叉产生的后与代数与种群中的个体数的比。Pc越高，解空间就越大，越耗时/

变异:Pm:种群中变异基因数在总基因数中的百分比。它控制着新基因导入种群的比例。太低，一些有用的基因就难以进入选择；太高，后代就可能失去从双亲继承下来的良好特性，也就失去了从过去中搜索的能力。

4.选择策略

适者生存，优胜劣汰

5.停止准则

最大迭代数

初始种群的产生：随机产生，具体依赖于编码方法

编码方法 ：二进制编码法、浮点编码法、符号编码法。顺序编码，实数编码，整数编码。

适值函数 ：根据目标函数设计

遗传运算 ： 交叉 ：单切点交叉，双切点交叉，均匀交叉，算术交叉

变异 ：基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。

均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）

边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。

非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。

高斯近似变异：进行变异操作时用符号均值为P的平均值，方差为P**2的正态分布的一个随机数来替换原有的基因值。

选择策略 ：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，]

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

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

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

❼ 遗传算法 最大进化代数是什么

最大进化代数就是设置的循环的次数
变异概率就是一个个体变成另一个个体的概率
自变量离散精度就是数值的精度的意思

❽ 求问基因遗传算法

摘要 您好，很高兴为您解答问题。

❾ 遗传算法的主要步骤

为了使用遗传算法来解决优化问题，准备工作分为以下四步^{［56，57，61］}。

7.4.1 确定问题的潜在解的遗传表示方案

在基本的遗传算法中，表示方案是把问题的搜索空间中每个可能的点表示为确定长度的特征串（通常是二进制串）。表示方案的确定需要选择串长l和字母表规模k。在染色体串和问题的搜索空间中的点之间选择映射有时容易实现，有时又非常困难。选择一个便于遗传算法求解问题的表示方案经常需要对问题有深入的了解。

7.4.2 确定适应值的度量

适应值度量为群体中每个可能的确定长度的特征串指定一个适应值，它经常是问题本身所具有的。适应值度量必须有能力计算搜索空间中每个确定长度的特征串的适应值。

7.4.3 确定控制该算法的参数和变量

控制遗传算法的主要参数有群体规模Pop-Size、算法执行的最大代数N-Gen、交叉概率P_c、变异概率P_m和选择策略R等参数。

（1）群体规模Pop-Size。群体规模影响到遗传算法的最终性能和效率。当规模太小时，由于群体对大部分超平面只给出了不充分的样本量，所以得到的结果一般不佳。大的群体更有希望包含出自大量超平面的代表，从而可以阻止过早收敛到局部最优解；然而群体越大，每一代需要的计算量也就越多，这有可能导致一个无法接受的慢收敛率。

（2）交叉率P_c。交叉率控制交叉算子应用的频率，在每代新的群体中，有P_c·Pop-Size个串实行交叉。交叉率越高，群体中串的更新就越快。如果交叉率过高，相对选择能够产生的改进而言，高性能的串被破坏得更快。如果交叉率过低，搜索会由于太小的探查率而可能停滞不前。

（3）变异率P_m。变异是增加群体多样性的搜索算子，每次选择之后，新的群体中的每个串的每一位以相等的变异率进行随机改变。对于M进制串，就是相应的位从1变为0或0变为1。从而每代大约发生P_m·Pop-Size·L次变异，其中L为串长。一个低水平的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。高水平的变异率产生的实质是随机搜索。

比起选择和交叉，变异在遗传算法中是次要的，它在恢复群体中失去的多样性方面具有潜在的作用。例如，在遗传算法执行的开始阶段，串中一个特定位上的值1可能与好的性能紧密联系，也就是说从搜索空间中某些初始随机点开始，在那个位上的值1可能一致地产生适应性度量好的值。因为越好的适应值与串中那个位上的值1相联系，复制作用就越会使群体的遗传多样性损失。当达到一定程度时，值0会从整个群体中的那个位上消失，然而全局最优解可能在串中那个位上是0。一旦搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是达到全局最优解所需的。这仅仅是一种说明搜索空间是非线性的方式，这种情形不是假定的，因为实际上所有我们感兴趣的问题都是非线性的。变异作用提供了一个恢复遗传多样性的损失的方法。

（4）选择策略R。有两种选择策略。一是利用纯选择，即当前群体中每个点复制的次数比与点的性能值成比例。二是利用最优选择，即首先执行纯选择，且具有最好性能的点总是保留到下一代。在缺少最优选择的情况下，由于采样误差、交叉和变异，最好性能的点可能会丢失。

通过指定各个参数Pop-Size、P_c、P_m和R的值，可以表示一个特定的遗传算法。

7.4.4 确定指定结果的方法和停止运行的准则

当遗传的代数达到最大允许代数时，就可以停止算法的执行，并指定执行中得到的最好结果作为算法的结果。

基本的遗传算法

1）随机产生一个由固定长度字符串组成的初始群体。

2）对于字符串群体，迭代地执行下述步骤，直到选择标准被满足为止。

①计算群体中的每个个体字符串的适应值；

②实施下列三种操作（至少前两种）来产生新的群体，操作对象的选取基于与适应度成比例的概率。

选择：把现有的个体串按适应值复制到新的群体中。

交叉：通过遗传重组随机选择两个现有的子串进行遗传重组，产生两个新的串。

变异：将现有串中某一位的字符随机变异产生一个新串。

3）把在后代中出现的最好适应值的个体串指定为遗传算法运行的结果。这一结果可以是问题的解（或近似解）。

基本的遗传算法流程图如图7-1所示。

❿ matlab 遗传算法 如何寻找最优值出现的代数

matlab不自带这两种算法，没法给您具体的流程好或者代码。如果是自己编写的话，那么将每次迭代的结果都记录下来，于是就可以知道首次出现最优解的代数了