本篇文章给大家谈谈遗传算法的基本原理和求解步骤，以及遗传算法原理图对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
基本遗传算法介绍
遗传算法是群智能优化计算中应用最为广泛、最为成功、最具代表性的智能优化方法。它是以达尔文的生物进化论和孟德尔的遗传变异理论为基础，模拟生物进化过程和机制，产生的一种群体导向随机搜索技术和方法。
遗传算法的基本思想：首先根据待求解优化问题的目标函数构造一个适应度函数。然后，按照一定的规则生成经过基因编码的初始群体，对群体进行评价、遗传运算（交叉和变异）、选择等操作。经过多次进化，获得适应度最高的一个或几个最优个体作为问题的最优解。
编码是对问题的可行解的遗传表示，是影响算法执行效率的关键因素的之一。遗传算法中，一个解 称为个体或染色体（chromosome），染色体由被称为基因（gene）的离散单元组成，每个基因控制颜色体的一个或多个特性，通常采用固定长度的0-1二进制编码，每个解对应一个唯一的二进制编码串编码空间中的二进制位串称为基因型（genotype）。而实际所表示问题的解空间的对应点称为表现型（phenotype）。
种群由个体构成，每个个体的染色体对应优化问题的一个初始解。
适应度函数是评价种群中个体对环境适应能力的唯一确定性指标，体现出“适者生存，优胜劣汰”这一自然选择原则。
遗传算法在每次迭代过程中，在父代种群中采用某种选择策略选择出指定数目的哥特体提进行遗传操作。最常用的选择策略是正比选择（proportional selection）策略。
在 交叉算子中，通常由两个被称为父代（parent）的染色体组合，形成新的染色体，称为子代（offspring）。父代是在种群中根据个体适应度进行选择，因此适应度较高的染色体的基因更有可能被遗传到下一代 。通过在迭代过程中不断地应用交叉算子，使优良个体的基因得以在种群中频繁出现，最终使得整个种群收敛到一个最优解。
在染色体交叉之后产生的子代个体，其基因位可能以很小的概率发生转变，这个过程称为变异。变异是为了增强种群的多样性，将搜索跳出局部最优解。
遗传算法的停止准则一般采用设定最大迭代次数或适应值函数评估次数，也可以是规定的搜索精度。
已Holland的基本GA为例介绍算法等具体实现，具体的执行过程描述如下：
Step 1： 初始化 。随机生成含有 个个体的初始种群 ，每个个体经过编码对应着待求解优化问题的一个初始解。
Step 2： 计算适应值 。个体 ，由指定的适应度函数评价其适应环境的能力。不同的问题，适应度函数的构造方式也不同。对函数优化问题，通常取目标函数作为适应度函数。
Step 3： 选择 。根据某种策略从当前种群中选择出 个个体作为重新繁殖的下一代群体。选择的依据通常是个体的适应度的高低，适应度高的个体相比适应度低的个体为下一代贡献一个或多个后代的概率更大。选择过程提现了达尔文“适者生存”原则。
Step 4： 遗传操作 。在选出的 个个体中，以事件给定的杂交概率 任意选择出两个个体进行 交叉运算 ，产生两个新的个体，重复此过程直到所有要求杂交的个体杂交完毕。根据预先设定的变异概率 在 个个体中选择出若干个体，按一定的策略对选出的个体进行 变异运算 。
Step 5： 检验算法等停止条件 。若满足，则停止算法的执行，将最优个体的染色体进行解码得到所需要的最优解，否则转到 Step 2 继续进行迭代过程。
遗传算法的基本原理
自然界是一个自适应的大系统［53，56～60］，自然系统中的大多数生物体通过自然选择和有性生殖这两种基本过程进行自身的演化，使自己逐步达到完美来适应大自然。遗传算法受生物进化与遗传的启发，形成一种独特的优化方式，遗传算法的运算原理常常与生物进化及遗传学说相吻合，而且其术语也常仿照生物学的术语。遗传算法的运算基础是字符串，先将搜索对象编码为字符串形式；字符串就相当于生物学中的染色体，由一系列字符组成；每个字符都有特定的含义，反映所解决问题的某个特征，这就相当于基因，亦即染色体DNA的片段。每个字符串结构被称为个体，每个个体都可以通过问题本身所具有的适应值度量来计算反映其适应性好坏的适应值，然后对一组字符串结构（被称为一个群体）进行循环操作。每次循环操作被称作一代，其中的操作包括：保存字符串组中适应性较好的那些字符串到下一代（对应于遗传学中的复制），使上一代中的优良个体得以生存下去，这类似于生物进化论中的自然选择。通过有组织的然而是随机的字符串间的信息交换来重新结合那些适应性好的字符串（对应于遗传学中的交叉），在每一代中利用上一代字符串结构中适应性好的位和段来生成一个新的字符串的群体；作为额外增添，偶尔也要在字符串结构中尝试用新的位和段来替代原来的部分（对应于遗传学中的变异），等等。遗传算法中这些操作只涉及字符串的某些片段，这就类似于遗传过程只涉及某些基因而不是整个染色体。遗传算法是一类随机算法，但它不是简单的随机走动，它可以有效地利用已有的信息来搜寻那些有希望改善解质量的字符串。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。
遗传算法[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)，遗传算法的性能较优。
与模拟退火反演算法相同，遗传算法与传统的线性反演方法相比，该方法具有:不依赖初始模型的选择、能寻找全局最小点而不陷入局部极小、在反演过程中不用计算雅克比偏导数矩阵等优点。另外，遗传算法具有并行性，随着并行计算和集群式计算机技术的发展，该算法将会得到越来越广泛的研究与应用。
但是遗传算法作为类蒙特卡洛算法同样需要进行大量的正演计算，种群个体数量越大，繁衍代数越多，则计算量越大。所以和前面的最小二乘法相比，速度不是它的优势。
遗传算法的主要步骤
为了使用遗传算法来解决优化问题，准备工作分为以下四步［56，57，61］。
7.4.1 确定问题的潜在解的遗传表示方案
在基本的遗传算法中，表示方案是把问题的搜索空间中每个可能的点表示为确定长度的特征串（通常是二进制串）。表示方案的确定需要选择串长l和字母表规模k。在染色体串和问题的搜索空间中的点之间选择映射有时容易实现，有时又非常困难。选择一个便于遗传算法求解问题的表示方案经常需要对问题有深入的了解。
7.4.2 确定适应值的度量
适应值度量为群体中每个可能的确定长度的特征串指定一个适应值，它经常是问题本身所具有的。适应值度量必须有能力计算搜索空间中每个确定长度的特征串的适应值。
7.4.3 确定控制该算法的参数和变量
控制遗传算法的主要参数有群体规模Pop-Size、算法执行的最大代数N-Gen、交叉概率Pc、变异概率Pm和选择策略R等参数。
（1）群体规模Pop-Size。群体规模影响到遗传算法的最终性能和效率。当规模太小时，由于群体对大部分超平面只给出了不充分的样本量，所以得到的结果一般不佳。大的群体更有希望包含出自大量超平面的代表，从而可以阻止过早收敛到局部最优解；然而群体越大，每一代需要的计算量也就越多，这有可能导致一个无法接受的慢收敛率。
（2）交叉率Pc。交叉率控制交叉算子应用的频率，在每代新的群体中，有Pc·Pop-Size个串实行交叉。交叉率越高，群体中串的更新就越快。如果交叉率过高，相对选择能够产生的改进而言，高性能的串被破坏得更快。如果交叉率过低，搜索会由于太小的探查率而可能停滞不前。
（3）变异率Pm。变异是增加群体多样性的搜索算子，每次选择之后，新的群体中的每个串的每一位以相等的变异率进行随机改变。对于M进制串，就是相应的位从1变为0或0变为1。从而每代大约发生Pm·Pop-Size·L次变异，其中L为串长。一个低水平的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。高水平的变异率产生的实质是随机搜索。
比起选择和交叉，变异在遗传算法中是次要的，它在恢复群体中失去的多样性方面具有潜在的作用。例如，在遗传算法执行的开始阶段，串中一个特定位上的值1可能与好的性能紧密联系，也就是说从搜索空间中某些初始随机点开始，在那个位上的值1可能一致地产生适应性度量好的值。因为越好的适应值与串中那个位上的值1相联系，复制作用就越会使群体的遗传多样性损失。当达到一定程度时，值0会从整个群体中的那个位上消失，然而全局最优解可能在串中那个位上是0。一旦搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是达到全局最优解所需的。这仅仅是一种说明搜索空间是非线性的方式，这种情形不是假定的，因为实际上所有我们感兴趣的问题都是非线性的。变异作用提供了一个恢复遗传多样性的损失的方法。
（4）选择策略R。有两种选择策略。一是利用纯选择，即当前群体中每个点复制的次数比与点的性能值成比例。二是利用最优选择，即首先执行纯选择，且具有最好性能的点总是保留到下一代。在缺少最优选择的情况下，由于采样误差、交叉和变异，最好性能的点可能会丢失。
通过指定各个参数Pop-Size、Pc、Pm和R的值，可以表示一个特定的遗传算法。
7.4.4 确定指定结果的方法和停止运行的准则
当遗传的代数达到最大允许代数时，就可以停止算法的执行，并指定执行中得到的最好结果作为算法的结果。
基本的遗传算法
1）随机产生一个由固定长度字符串组成的初始群体。
2）对于字符串群体，迭代地执行下述步骤，直到选择标准被满足为止。
①计算群体中的每个个体字符串的适应值；
②实施下列三种操作（至少前两种）来产生新的群体，操作对象的选取基于与适应度成比例的概率。
选择：把现有的个体串按适应值复制到新的群体中。
交叉：通过遗传重组随机选择两个现有的子串进行遗传重组，产生两个新的串。
变异：将现有串中某一位的字符随机变异产生一个新串。
3）把在后代中出现的最好适应值的个体串指定为遗传算法运行的结果。这一结果可以是问题的解（或近似解）。
基本的遗传算法流程图如图7-1所示。
遗传算法--GA
遗传算法（GA）属于 人工智能启发式算法 ，启发式算法的目标就是 寻找原始问题的最优解 ，该算法的定义为
人类通过直观常识和生活经验，设计出一种以搜索最优解为目的，通过仿真大自然规律的算法，该算法在可以在接受的花销（计算时间和存储空间）范围内找到问题实例的一个可行解，且该可行解和真实最优解的误差一般不可以被估计
当下主要有的启发式算法包括 遗传算法、退火法，蚁群算法、人工神经网络等 ，这篇文章主要介绍遗传算法
遗传算法的基本原理是模拟达尔文进化论 "物竞天择，适者生存" 的自然法则，其核心思想为
（1）将原始问题的参数，抽象为基因编码
（2）将原始问题的可行解，抽象为基因排列的染色体组合
（3）将原始问题的解集规模，抽象为一定数量染色体组成的种群
（4）寻找可行解的过程，抽象为种群的进化过程（染色体选择、交叉、变异等）
（5）比较可行解的优劣，抽象为量化比较不同种群对当前环境的适应程度
（6）逼近最优解的过程，抽象为淘汰适应度差的种群，保留适应度高的种群进行下一次进化
（7）问题的最优解，抽象为经过多次进化后，最终生存下来的精英种群
理论上，通过有限次种群进化，生存下来的种群都是 精英染色体 ，是最适合当前环境条件的种群，也就可以无限逼近原始问题的最优解
相关生物学术语：
为了大家更好了解遗传算法，在此之前先简单介绍一下相关生物学术语，大家了解一下即可。
基因型(genotype)：性状染色体的内部表现；
表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；
进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
适应度(fitness)：度量某个物种对于生存环境的适应程度。
选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；
变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
解码(decoding)：基因型到表现型的映射。
个体（individual）：指染色体带有特征的实体；
种群（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问题汇编。
参考：
遗传算法的基本原理和求解步骤的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于遗传算法原理图、遗传算法的基本原理和求解步骤的信息别忘了在本站进行查找喔。