笔记|遗传算法原理
这篇文章链接是https://www.jianshu.com/p/ae5157c26af9，我觉得它写得特别棒，所以特意保存了，这样以后打开今日头条软件就能轻松找到它了。我接下来还会创作一些运用实例和编程内容的文章，帮助大家更好地实践所学知识。
遗传算法的科学定义遗传算法的执行过程
遗传算法以一个种群为起点，这个种群由多个个体构成，每个个体都经过基因编码。个体是带有特征的染色体实体，染色体代表了解集的潜在可能。
遗传信息的核心载体是染色体，它包含了众多基因，其内部构成体现为基因型，即特定基因的搭配，这种搭配决定了生物体的外在形态，例如头发颜色的特征就源于染色体里控制该性状的基因组合，因此首要任务是完成从外部特征到基因构成的转换，也就是进行编码。鉴于模仿基因编码过程难度极大，我们通常采用简化的方法，比如二进制编码。
新种群形成之后，遵循强者存活弱者被淘汰的法则，通过代际更迭逐步优化出效果更佳的候选方案，每一代都要依据不同个体对环境的契合度来挑选对象，再运用生物遗传学的相关技术手段，实施配对结合与基因突变，从而生成代表全新可能性的下一代群体。
这个过程会促使群体后代比先代更适应当地环境，最终群体中的最佳成员通过解码，能够提供问题的近似最优方案。
遗传算法过程图解
基因构成决定生物体内部特征，外部形态则由基因决定，或由基因决定的外部形态，是基因构成的外部显现，或是个体根据基因构成呈现的外部状态，生物体不断适应生存环境，品质持续改善，这就是进化，进化是生物种群逐渐适应环境的过程，生物的进化以种群为基本单位。生存能力：衡量一种生物在特定环境中的生存状况。挑选：按照一定几率从群体中选出部分成员。通常，挑选环节是一个依靠生存能力进行筛选的淘汰机制。繁殖：在细胞分裂期间，遗传信息DNA通过复制传递给新生成的细胞，新细胞从而获得旧细胞的基因。交换：两条染色体的某个相同部位处基因链发生断裂，前后两段互相拼接，从而生成两条新的染色体链。这一过程也称作基因重配或杂交；改变：在复制过程中，极有可能出现某些复制失误，改变会形成新的染色体链，并显现出不同的生物特征；记录：遗传密码在DNA的长分子上，依照特定的序列进行组织。遗传密码可理解为从外部形态到遗传因子的对应关系。解读：遗传因子到外部形态的对应关系。生物体：指携带遗传特征的染色体单元；群体：由生物体构成的整体，其中生物体的数量称为群体规模，举例说明如何寻找这个函数的极值
求既定区间内该函数的最大值
高中数学课程的学习者都清楚，此前讨论的函数包含众多局部最高点和局部最低点，其中特定区间内的局部最高点中数值最大的那个就是全局最高点，而局部最低点则如同一个个洼地。从图形角度观察，局部最高点呈现山峰形态，局部最低点则呈现山谷形态，由此可以类比，遗传算法的运作方式就是在多变量函数中寻找最优解的过程。
那些山岭分别代表局部最优值，其中一座山岭的高度最为突出，这座山岭便对应着整体最优值。因此，遗传算法的目标是尽可能攀登至顶峰，避免被束缚在低矮的次级山岭之中。（倘若寻求最小值，那么核心任务就是尽量下探至最深的谷底，其原理完全相同）。
袋鼠跳
我们若将函数图像看作连绵起伏的山峦，其中包含诸多峰顶与谷底。每个解便可类比为袋鼠，我们期待它们持续向上跳跃，最终抵达最高峰顶。因此，寻找最大值的问题便转化为引导袋鼠完成跳跃之旅。
下面介绍介绍“袋鼠跳”的几种方式。
大体实现过程
遗传算法里的每一个基因序列，都代表一个可能的解决方法，通常借助评价函数来判定这个方法的好坏程度，因此基因序列和其对应解的评估值之间建立起关联关系，算法的运作方式与自然界生物的演变现象颇为相似。
下面我们用袋鼠跳中的步骤一一对应解释，以方便大家理解：
首先探索一种将问题潜在解进行“量化”表示的方法，即构建表现形式与基因结构之间的对应规则，接着随机设定一个初始种群，第一批袋鼠因此被无序地布置在山岭区域，种群中的每个成员都是这些量化后的符号，然后借助恰当的还原步骤，能够获取袋鼠的具体坐标位置。通过评估函数对每个基因个体进行评价，袋鼠爬得越高评价越好，因此评价越高。依据选择规则进行筛选，定期淘汰海拔较低的袋鼠，维持种群数量稳定。基因会发生变异，袋鼠会随机跳跃。接着繁衍后代开yun体育app入口登录，期望存活的袋鼠能够多生育，并养育子女。
遗传算法无法确保一定能找到最优解，不过它最大的好处是你无需钻研怎样去寻找最优解。（无需去教袋鼠往哪个方向跳，跳多远。）只需要简单淘汰掉表现不佳的个体即可。（把那些总往坡下走的袋鼠清除掉，这就是遗传算法的核心。）
由此我们可以得出遗传算法的一般步骤：
生成初始种群。评估每个成员的适应程度，看其是否满足目标要求，若达标，则显示最优成员及其最佳方案，程序终止。若未达标，则继续后续操作。根据适应度挑选双亲，适应力强的成员被选中的几率更大，适应力弱的成员被排除。通过双亲的基因片段依照特定方式重组，产生后代。对后代的基因片段实施变异处理。
由交叉和变异产生新一代种群，返回步骤2，直到最优解产生。
编码
编码关乎遗传算法的运用，也是算法设计中的核心环节，其方法选择决定了遗传算子的操作方式，进而显著影响遗传优化的成效。
到目前为止，人们已经构想出多种多样的编码方案，从整体上看，这些编码方案能够归纳为三个主要类别，分别是二进制编码法、浮点编码法、符号编码法，接下来将逐一进行阐述。
人类基因由AGCT四种碱基序列构成。但在此处仅采用0和1两种符号，将它们连接起来构成一条序列，用以模拟染色体。单个位置能够记录两种不同的状态信息，所以只要二进制序列足够长，就能编码出所有特征。这就是二进制编码的原理。例如：1110001010111
它由二进制符号0和1所组成的二值符号集。它有以下一些优点：
编码和解码过程十分便捷，交叉与变异等遗传操作容易完成，遵循最少数字符的编码规则，借助模式定理对算法展开理论性研究。
二进制编码存在不足之处，在处理连续函数的优化任务时，这种编码方式表现出局限性，原因是其内在的随机特性导致局部搜索效率不高，举例来说，面对一些要求精确度较高的情形（参照前文所述问题），一旦解值接近理想状态，编码的变异操作会造成输出结果发生剧烈波动，呈现不连贯特征，进而使得解值偏离最优值，难以实现稳定收敛。
二进制编码方式看似直接明了，然而，在将连续数值转化为离散值的过程中，不可避免地会产生转换偏差，个体表示的位数较少时，往往难以满足精确度标准，而若将个体编码的位数增加，虽然能够提升精确度，却同时也加大了译码的复杂程度，导致遗传算法的探索区域迅速膨胀。
浮点编码方法中，每个基因都用一段区间的实数来记录。这种表示方式要求基因值必须符合预设的边界条件。遗传算子如交叉和变异，在运算时产生的新个体基因，同样要满足这个边界条件。
1.2-3.2-5.3-7.2-1.4-9.7
浮点数编码方法有下面几个优点：
可用于表现数值跨度较宽的情况,适合对精确度有高标准的遗传运算,有助于在广阔的搜索领域中实施遗传过程,优化了遗传运算的计算难度,加快了计算进程,支持与常规优化手段的结合,利于构建融入特定问题领域知识的智能遗传算子,能够应对包含复杂约束条件的决策变量问题
符号表示法是让每个染色体中的基因选取自一个没有实际数值意义、仅有代号作用的字符集合例如｛A,B,C…｝。这种编码方式有个突出的好处在于：
依照积木编码的合理准则，有助于遗传算法运用问题的专有信息，有利于遗传算法与相关近似方法相结合，将袋鼠染色体进行编码
阐述了众多编码方法之后，接下来要探讨的是，怎样运用这些编码方案为袋鼠的染色体进行编码，必须首先认识到，编码的本质在于构建基因型与个体表现之间的对应规则，而个体表现可解释为生物体的各种属性，诸如体型大小、体重轻重、毛发颜色等，针对当前议题，我们着重关注的个体属性是袋鼠所在的空间位置，目的是为了淘汰那些生存环境不利的低海拔袋鼠袋鼠的外形如何，它偏爱的食物是什么。我们真正在意的始终是袋鼠的所在之处，而且一旦明确袋鼠的具体方位（具体方位即为相应的基因序列，能够经由解读获得），我们便能够：
在喜马拉雅山脉的图纸上标出目标坐标点，测量其高度数值。这等同于利用已知条件求出对应函数值。接着评估是否需要对袋鼠实施射击。能够得知基因重组和基因突变后袋鼠的坐标信息。
重新考虑3.1部分讨论的一元函数最优解问题，之前将极值比作山峰，那么袋鼠所在点的坐标可以看作某个区间的x值，根据x值利用函数关系式可以得出函数值，这相当于得到了袋鼠的基因序列，解码后获得位置坐标，在喜马拉雅山脉图上找到该坐标并计算出对应的海拔。这个x坐标代表一个具体数值，接下来，需要明确如何对它进行表示。下面我们以二进制方式编码为例进行说明，不过，这种方式下二进制编码相对麻烦些。（要是采用浮点数编码，其实就非常简单，直接用浮点数表示即可。）
我们曾提及，特定长度的二进制序列，所能呈现的浮点数精度是有限的。若需精确到小数点后六位，考虑到区间跨度为从负一至正二，总长为三，为确保达到该精度标准，就必须将区间细分为三乘以一千万等份。此外
2^21 = 2097152 < 3*10^6 < 2^22 = 4194304，所以编码的二进制串至少需要22位。
将一个由零和一组成的序列转换成指定区间内的具体数值，可以采用以下两种方法：首先确定该序列的长度，然后根据其构成元素计算最终结果。
将一个二进制串代表的二进制数转化为10进制数：
对应区间内的实数：
一个二进制序列，即1000101110110101000111，转换后对应的具体数值为0.637197。
这个编码方法仅作为示例，目的是帮助大家更清楚地明白，编码方法种类繁多，不断出现新形式，每个具体问题可能需要不同的编码方案，这一点需要大家特别注意。
评价个体的适应度-适应度函数
先前已经指出，适应度函数主要是依据个体特征来评估其适应程度。在本例的袋鼠跳跃情境下，我们只关注袋鼠所处的海拔高度，以此决定是否需要将其射杀。这样一来开yun体育官网入口登录app，该函数变得极为简明。只需输入袋鼠的位置坐标，再执行相应的查找操作，即可返回袋鼠当前所在位置的海拔数值。
评价函数又叫做适应度函数，是依据目标函数来设定的，用来分辨群体里个体优劣的依据。评价函数的值总是大于等于零，而目标函数的值可能是正也可能是负，因此在目标函数和评价函数之间必须进行转换。
评价个体适应度的一般过程为：
解码完个体编码串后，就能得到个体的具体形态，根据个体具体形态，可以算出它的目标函数值，依照最优化课题的不同，按照特定转换方式，把目标函数值转变为个体的适应度，淘汰掉部分适应度低的袋鼠开元ky888棋牌官网版，这是选择函数
遗传算法里的挑选环节，旨在明确从先辈集体中运用特定方式挑选哪些成员，使其能够遗传至下一代集体。挑选环节还负责决定哪些成员参与重组或交叉，并界定被选中成员将要繁衍多少子代。早先已经提及，我们期望身高的袋鼠能够存活，并且尽可能多地繁衍后代。众所周知，自然界里，繁殖能力强的袋鼠往往能留下更多后代，不过这只是个大概率的规律而已。实际上，有些繁殖能力相对较弱的袋鼠，也有可能不被我们察觉地成功繁衍。
那么，怎么建立这种概率关系呢？
下面介绍几种常用的选择算子：
轮盘赌挑选：属于一种模仿式随机取样的技术。每个成员能够进入下一代的机率，取决于它的适宜程度数值，相对于整个群体所有成员适宜程度数值的总和。这种方式挑选出来的误差通常很大。随机淘汰机制：每次运用轮盘法挑选一对生物体，二者展开角逐，适应度较强的胜出，不断重复，直至填补全部空缺。顶尖个体保留策略：采用轮盘选择方式完成遗传算法的挑选环节，并把当前种群里最优秀生物体的全部信息完整地传递给下一代群体。不带重播的随机挑选，又称为预期值挑选：依据每个生命体在下一代集体中的存活可能性开展随机挑选活动。操作步骤为：首先，测算集体里每个生命体在下一代集体中的存活可能数量N。某个个体若被挑中参与组合过程，其下一代中存活的预估数量会少半，若该个体没被挑中参与组合过程，其下一代中存活的预估数量会少一整。当筛选流程持续进行，某个体若存活的预估数量少于零，就失去被挑中的可能。固定方式选择：依照一个固定方法来执行挑选动作。具体实施步骤为：首先，推算出下一代群体里每个成员预计能存活的数量N。其次，以N的整数部分来决定各个个体在下一代群体中实际存活的数目。再者，将N的小数部分按从大到小排序，选取排名前M的个体，将这些个体补充进下一代群体。这样就能最终明确下一代群体中包含的M个成员。随机选取无返补余：能保证比平均适应度好的某些个体得以遗传给下一代，因此选择偏差不大。等距排列：将群体中所有个体按照适应度高低排序，然后依据这个次序来决定各个体被挑选的可能性。最优留存方式：当代群中表现最强的成员不参与配对和变异过程，而是用它来替换掉本代中经过配对、变异等处理后适应力最弱的成员。偶然淘汰制：每次从若干个体中挑选出适应力最强的那个，让其进入下一代群体。竞争排斥法：新产生的后代会取代或排挤与自身相似的旧个体，从而提升群体的多样性。
下面以轮盘赌选择为例给大家讲解一下：
假如有５条染色体，他们的适应度分别为５、８、３、７、２。
总适应度计算如下：先取5，再加8，然后加3，接着加7，最后加2，合计为25。
那么各个个体的被选中的概率为：
α1 = ( 5 / 25 ) * 100% = 20%
α2 = ( 8 / 25 ) * 100% = 32%
α3 = ( 3 / 25 ) * 100% = 12%
α4 = ( 7 / 25 ) * 100% = 28%
α5 = ( 2 / 25 ) * 100% = 8%
指针在转盘上转动，转动结束后，停顿的那个位置所对应的对象，就是被上天挑选出来的人选了。能够发现，那些更能适应环境变化的个体，被选中的可能性会更高一些。
开始产生后代（遗传，交叉函数Cross）
遗传算法中的配对基因重组，是将两个彼此对应的基因序列，依据特定规则交换部分遗传信息，由此产生两个全新的生物体。
适用于二进制编码个体或浮点数编码个体的交叉算子：
单点交叉是指个体编码串中随机选定一个位置作为交换点，之后在该位置处交换两个配对个体的部分基因片段。两点交叉与多点交叉情况如下：两点交叉是在个体编码串中随机确定两个位置作为交换点，接着在这两个点之间交换部分基因片段。多点交换，即一致交换，采取均等概率方式，在配对生物体基因位点间互换遗传因子，由此产生两个新生物体。算术交叉：通过两个个体的线性组合，可以创造出两个新个体，这些个体通常用浮点数编码来表示，该操作主要针对这类编码的个体进行
咳咳，按照通常做法，就拿一个最基础的二进制单点互换来说明一下。
二进制编码的基因重组过程，与高中生物里提及的同源染色体配对过程颇为相似，都是随机交换某些对应位置的编码片段，从而创造出新的基因型。
对应的二进制交叉
变异函数（基因突变）
遗传算法里的变异操作，是将群体中某个体基因序列里部分基因位点上的基因，换成该位点其它等位基因，由此产生出新个体。
例如下面这串二进制编码：
101101001011001
经过基因突变后，可能变成以下这串新的编码：
001101011011001
以下变异算子适用于二进制编码和浮点数编码的个体：
基础基因突变：针对群体编码序列里，依据变异几率，随机选取特定位置或少数位置，仅改变该位置原有数据。等概率变异：通过符合某区间内均匀分布的随机数值，以较低概率替换群体编码序列里所有基因点的当前数值。在算法刚开始执行的时候，边界变异是个不错的选择，它通过随机选取基因座上两个边界基因值中的任意一个来替换掉原来的基因值，这种方法特别适合那些最优解位于或接近于可行解边界的问题，可以更好地处理这类情况。另一种变异方式是非均匀变异，它会对原有的基因值进行随机扰动，把扰动后的数值当作新的基因值来使用。每个基因位点都等可能发生变异操作，这相当于整个解向量在解空间里经历了一次微小的调整。采用高斯近似变异方法，变异过程中用服从均值为P的平均值、方差为P的平方的正态分布的随机数来替代原有的基因数值。下一部分是具体实现的代码。
