遗传算法数据太少

1. 遗传算法

优化的算法有很多种，从最基本的梯度下降法到现在的一些启发式算法，如遗传算法(GA)，差分演化算法(DE)，粒子群算法(PSO)和人工蜂群算法(ABC)。

举一个例子，遗传算法和梯度下降：

梯度下降和遗传算法都是优化算法，而梯度下降只是其中最基础的那一个，它依靠梯度与方向导数的关系计算出最优值。遗传算法则是优化算法中的启发式算法中的一种，启发式算法的意思就是先需要提供至少一个初始可行解，然后在预定义的搜索空间高效搜索用以迭代地改进解，最后得到一个次优解或者满意解。遗传算法则是基于群体的启发式算法。

遗传算法和梯度下降的区别是：

1.梯度下降使用误差函数决定梯度下降的方向，遗传算法使用目标函数评估个体的适应度
2.梯度下降是有每一步都是基于学习率下降的并且大部分情况下都是朝着优化方向迭代更新，容易达到局部最优解出不来；而遗传算法是使用选择、交叉和变异因子迭代更新的，可以有效跳出局部最优解
3.遗传算法的值可以用二进制编码表示，也可以直接实数表示

遗传算法如何使用它的内在构造来算出 α 和 β ：

主要讲一下选择、交叉和变异这一部分：
1.选择运算:将选择算子作用于群体。选择的目的是把优秀（适应值高）的个体直接遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

2.交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。交叉算子是将种群中的个体两两分组，按一定概率和方式交换部分基因的操作。将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。例如：（根据概率选取50个个体，两两配对，交换x,y，比如之前两个是(x1,y1),(x2,y2)，之后变成了（x1,y2）,(x2,y1)）

3.变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。（x2可能变为x2+δ，y1变为y1+δ）
种群P(t)经过选择、交叉、变异运算之后得到下一代种群P(t+1)。

遗传算法就是通过对大量的数据个体使用选择、交叉和变异方式来进化，寻找适合问题的最优解或者满意解。

遗传算法参数的用处和设置：

1.编码选择：通常使用二进制编码和浮点数编码，二进制适合精度要求不高、特征较少的情况。浮点数适合精度高、特征多的情况
2.种群：种群由个体组成，个体中的每个数字都代表一个特征，种群个体数量通常设置在40-60之间；迭代次数通常看情况定若计算时间较长可以在100内，否则1000以内都可以。
3.选择因子：通常有轮盘赌选择和锦标赛选择，轮盘赌博的特点是收敛速度较快，但优势个体会迅速繁殖，导致种群缺乏多样性。锦标赛选择的特点是群多样性较为丰富，同时保证了被选个体较优。
4.交叉因子：交叉方法有单点交叉和两点交叉等等，通常用两点交叉。交叉概率则选择在0.7-0.9。概率越低收敛越慢时间越长。交叉操作能够组合出新的个体，在串空间进行有效搜索，同时降低对种群有效模式的破坏概率。
5.变异因子：变异也有变异的方法和概率。方法有均匀变异和高斯变异等等；概率也可以设置成0.1。变异操作可以改善遗传算法的局部搜索能力，丰富种群多样性。
6.终止条件：1、完成了预先给定的进化代数；2、种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进；3、所求问题最优值小于给定的阈值.

2. 遗传算法的基本原理

遗传算法的基本原理和方法

一、编码

编码：把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。

解码（译码）：遗传算法解空间向问题空间的转换。

二进制编码的缺点是汉明悬崖（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的正态分布的一个随机数来替换原有的基因值。

3. 遗传算法-总结

最近在做遗传算法的项目，简单记录一下。
遗传算法是模拟自然界生物进化机制的一种算法，在寻优过程中有用的保留无用的去除。包括3个基本的遗传算子：选择（selection）、交叉（crossover）和变异（mutation）。遗传操作的效果与上述3个遗传算子所取的操作概率、编码方法、群体大小、初始群体，以及适应度函数的设定密切相关。
1、种群初始化
popsize 种群大小，一般为20-100，太小会降低群体的多样性，导致早熟；较大会影响运行效率；迭代次数一般100-500；交叉概率：0.4-0.99，太小会破坏群体的优良模式；变异概率：0.001-0.1，太大搜索趋于随机。编码包括实数编码和二进制编码，可以参考遗传算法的几个经典问题，TSP、背包问题、车间调度问题。
2、选择
目的是把优化个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代，我大部分采用了轮盘赌的方法。具体可参考 http://my.oschina.net/u/1412321/blog/192454 轮盘赌方法各个个体的选择概率和其适应值成比例，个体适应值越大，被选择的概率也越高，反之亦然。在实际问题中，经常需要最小值作为最优解，有以下几种方法进行转换
a、0-1之间的数据，可以用1-该数值，则最小值与最大值互换；
b、 求倒数；
c、求相反数；
以上几种方法均可以将最大值变为最小值，最小值变为最大值，便于利用轮盘赌选择最优个体，根据实际情况来确定。
3、交叉
交叉即将两个父代个体的部分结构加以替换重组而生成新个体的操作，通过交叉，遗传算法的搜索能力得以飞跃提高。根据编码方法的不同，可以有以下的算法：
a、实值重组
离散重组、中间重组、线性重组、扩展线性重组
b、二进制交叉
单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉
4、变异
基本步骤：对群中所有个体以事先设定的变异概率判断是否进行变异；对进行变异的个体随机选择变异位进行变异。根据编码表示方法的不同，有实值变异和二进制变异
变异的目的：
a、使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部搜索能力可以加速向最优解收敛。显然该情况下变异概率应取较小值，否则接近最优解的积木块会因为变异遭到破坏。
b、使遗传算法可维持多样性，以防止未成熟收敛现象。此时收敛概率应取较大值。
变异概率一般取0.001-0.1。
5、终止条件
当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设代数一般为100-500。
6、其它
多变量：将多个变量依次连接
多目标：一种方法是转化为单目标，例如按大小进行排序，根据排序和进行选择，可以参考 https://blog.csdn.net/paulfeng20171114/article/details/82454310

4. 遗传算法、数值算法、爬山算法、模拟退火 各自的优缺点

遗传算法：其优点是能很好地处理约束，跳出局部最优，最终得到全局最优解。缺点是收敛速度慢，局部搜索能力弱，运行时间长，容易受到参数的影响。

模拟退火：具有局部搜索能力强、运行时间短的优点。缺点是全局搜索能力差，容易受到参数的影响。

爬山算法：显然爬山算法简单、效率高，但在处理多约束大规模问题时，往往不能得到较好的解决方案。

数值算法：这个数值算法的含义太宽泛了，指的是哪种数值算法，阵列算法与爬山算法一样，各有优缺点。

(4)遗传算法数据太少扩展阅读：

注意事项：

遗传算法的机制比较复杂，在Matlab中已经用工具箱中的命令进行了打包，通过调用可以非常方便的使用遗传算法。

函数GA：［x，Fval，reason］＝GA（＠fitnessfun，Nvars，options）x为最优解，Fval为最优值，＠Fitnessness为目标函数，Nvars为自变量个数，options为其他属性设置。系统的默认值是最小值，所以函数文档中应该加上一个减号。

要设置选项，您需要以下函数：options＝GaOptimset（＇PropertyName1＇，＇PropertyValue1＇，＇PropertyName2＇，＇PropertyName3＇，＇PropertyValue3＇…）通过该函数，可以确定一些遗传算法的参数。

5. 遗传算法能处理大量数据吗

遗传算法精髓是你看的fitnessFunction怎么写的，能不能处理大数据量，不是算法决定的，是你的计算机性能和你的代码决定的。遗传算法本身是一种搜索的算法，实际上皮早是试出来的。行的可以，不行的淘汰。能不能处理大数据量，实际上看你的种群数量有多大，每一个单独的序列有多长。如果很者散大，你的算法就要费心思设计，否则要么很慢，要么运行不了。
遗传算法是没办法的时候才用的，在枚燃嫌雀举或者逆向算法是在无法完成这么大运算量的时候用的，能节约时间，找到一个相对可以接受的解而已。

6. 遗传算法

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

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

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

遗传算法(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实现

8. 为什么遗传算法优化后反而效果变差了

遗传算法优化时，可能会遇到过早收敛的问题，也就是算法在早期阶段就裤棚开始陷入局部最优解，导致后续的求解过程无法得到更好的结果。过早收敛的主要原因可能有以下几种：
1. 种群规模太小：在遗传算法中，种群规模的大小会影响算法的收敛速度和质量。如果种群规模太小，算法容易陷入局部最优解。
2. 选择算子不合适：选择算子是遗传算法中比较重要的部分，它直接决定了种群中父代和子代的选择情况。若选择算子的设计不当，可能会导胡中则致早期阶段种群快速收敛到一个较小的范围内。
3. 变异率太小：变异是遗传算法中使种群具有多样性和避免早期收敛的重要方法之一。如果变异率太小，种群中的培薯多样性就会越来越小，趋向于收敛到一个较小的范围内。
4. 初始种群设计不合理：如果初始种群的设计不合理，可能会导致算法在早期阶段陷入局部最优解而无法跳出。
综上所述，如果遗传算法优化后效果变差，可能存在算法参数不适合或设计不当的问题，需要重新调整及优化算法参数或方法，避免过早收敛等问题，以进一步优化遗传算法的效果。

9. 遗传算法的优缺点

优点：

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

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

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

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

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

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

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

缺点：

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

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

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

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

(9)遗传算法数据太少扩展阅读

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

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

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