遗传算法精英保留

‘壹’ 详谈改进的遗传算法求解柔性作业车间调度问题论文

详谈改进的遗传算法求解柔性作业车间调度问题论文

0 引言

作业车间调度问题(Job-shop scheling problem，JSP)是研究生产线调度问题最常用的模型之一，也是实现先进制造和提高生产效率的基础和关键. 柔性作业车间调度问题( Flexible jobshopscheling problem，FJSP)是传统作业车间调度问题的扩展，在传统的作业车间调度问题中，每个工件的加工工序是确定的，每一道工序的加工机器和加工时间也是确定的，而在柔性作业车间调度问题中，每个工件的每一道工序可以在多个可选择的加工机器上进行加工，并且不同的加工机器所需要的加工时间是不同的，增加了调度的灵活性，比较符合生产的实际情况.

柔性作业车间调度问题已经被证明是更复杂的NP-Hard 问题，因而难以取得最优解. 目前，求解FJSP 的常用方法有禁忌搜索( TS)，模拟退火(SA)和遗传算法(GA)等. 其中遗传算法以其操作简单、鲁棒性强、搜索全局最优解速度快等特点，在生产调度领域得到了广泛的应用.

遗传算法是由美国J. Holland 教授于1975 年提出的，是一种模拟自然进化过程的一种优化算法. 由于传统的遗传算法存在着较大的缺陷，国内外学者已从不同角度对其进行了改进，本文对传统遗传算法的初始种群进行橡兆局了改进，以提高初始解的质量.

1 柔性作业车间调度模型设有n 个待加工工件J(J1，J2，…，Jn)，在m台设备上加工M(M1，M2，…，Mm)，每个工件Ji有Pi(Pi1，Pi2，…，Pin) 道工序，每道工序可在一台或多台设备上加工，同一道工序在不同设备上加工的时间可能不等，工序Pik的可选机器集为Mik(Mik 罬)，每台设备的加工时间从0 开始，加工完所有工件的完成时间为ETMi . 本文以最小化最大完工时间为性能指标，其目标函数为梁让:f(x) = min(max(ETMi))，1 ≤ i ≤ m模型需满足如下约束条件:(1)同一工件的工序加工顺序确定;(2)每道工序必须在它的上一道工序加工完成后才能开始加工;(3)每道工序只能选择一台设备进行操作;(4)每台设备在同一时间只能加工一个工件的一道工序;(5)每道工序在设备上操作时都不允许被中断;(6) 不同工件工序之间没有先后约束条件.一个包含3 个工件、5 台机器的FJSP 的问题.

2 算法的设计

(1) 基因编码

常用的遗传算法编码方案有二进制编码、格雷码编码、矩阵编码、自然数编码等，本文采用自然数编码，每条染色体表示一个可行解，同时采用双层编码，第一层编码为基于工件的工序编码，编码长度为所有工件工序之和，基因值代表工件号，基因值出现的次数代表该工件的工序总数，第二层编码为对应于第一层工件工序的机器编码，所以编码长度也为所有工件工序之和.染色体表示的工序顺序为(O31，O11，O12，O21，O22，O32，O13，O33)，染色体表示的机器序列为(M2，M4，M2，M1，M4，M5，M3，M4).

(2)产生初始种群

初始种群的优良对生物进化会产生很大的影响，本文对初始种群的机器选择进行了改进，首先随机生成初始猜灶种群的工序编码，工序编码生成后就要对应生成机器编码，每个工件工序在对应可选机器集中选择机器时，是以不同的概率的来选择不同的机器，机器加工时间短的以大概率被选择，相比之下，机器加工时间长的以小概率被选择，这样既保证了机器选择的随机性，也优化了初始种群.

(3)适应度函数的确定

本文以最小化最大完工时间为目标函数，故选择全部工件完工时间作为评价种群优劣的标准，设n 个待加工工件在m(M1，M2，…，Mm) 台设备上加工，所有加工工件工序在设备上的最后完工时间为ETMi(i = 1，2，…，m)，T = max(ETMi)，则适应度函数fi = 1 /T，T 越小，则适应度越大，即个体越优.

(4)选择

选择操作的目的是为了保留优良个体，使他们可以遗传到下一代. 本文采用精英保留策略和轮盘赌法相结合的方法，对父代个体和子代个体进行选择时直接将最优个体和次优个体遗传到下一代，然后对剩余的个体采用轮盘赌法进行选择，选择出p - 2 个个体到下一代进行遗传操作. 若种群规模为p，个体i 的适应度为fi，则个体i 被选择的概率pi为pi = fi /Σpk = 1fk即适应度越高的个体被选择的概率就越大.

(5)交叉

交叉操作是产生新个体的主要方法，提高全局搜索能力. 本文采用单点交叉方式，即随机产生一个交叉点，交换交叉点后的基因. 从种群中随机选择两个个体，交换两个个体工序编码的交叉点后面的基因，将交叉后工件多余的工序替换为其他工件缺失的工序;机器部分则按交叉前工件工序所选择的机器进行相应调整以保证其子代染色体的`合法性.

(6)变异

变异操作的目的是改变算法的局部搜索能力，有助于维持进化群体的多样性，防止过早陷入局部最优. 本文采用互换方式，即随机产生两个变异点，交换两点的基因值. 从种群中随机选择一个个体，对该个体的工序编码部分随机产生两个变异点，交换两点的基因值，同时将交换的基因位所对应的机器号也进行交换.

3 仿真实例分析

6 × 6(6 个工件，6 台机器) FJSP的加工工序，机器选择和加工时间矩阵表. 分别用标准遗传算法和本文提出的改进遗传算法对工件最小化最大完工时间进行优化计算，并分析优化计算结果.

遗传算法采用以下参数:种群规模为100，进化代数为100，交叉概率Pc = 0. 8，变异概率Pm =0. 1. 算法运行10 次，标准遗传算法的最大完工时间为20，收敛代数为75 代左右;改进遗传算法的最大完工时间为16，收敛代数为35 代左右. 改进遗传算法既缩短了工件完工时间，也加快了收敛代数. 从而验证了改进遗传算法的可行性

4 结论

传统遗传算法在进行种群初始化时采用的大多是随机选择方式，而本文提出了一种新的种群初始化方法，提高了种群初始解的质量. 最后对改进遗传算法进行了仿真实验，并将结果与标准遗传算法进行比较，结果表明了本算法的优越性和可行性.

‘贰’ 遗传算法--GA

        遗传算法（GA）属于 人工智能启发式算法 ，启发式算法的目标就是 寻找原始问题的最优解 ，该算法的定义为

         人类通过直观常识和生活经验，设计出一种以搜索最优解为目的，通过仿真大自然规律的算法，该算法在可以在接受的花销（计算时间和存储空间）范围内找到问题实例的一个可行解，且该可行解和真实最优解的误差一般不可以被估计

        当下主要有的启发式算法包括 遗传算法、退火法，蚁群算法、人工神经网络等 ，这篇文章主要介绍遗传算法

        遗传算法的基本原理是模拟达尔文进化论 "物竞天择，适者生存" 的自然法则，其核心思想为

（1）将原始问题的参数，抽象为基因编码

（2）将原始问题的可行解，抽象为基因排列的染色体组合

（3）将原始问题的解集规模，抽象为一定数量染色体组成的种群

（4）寻找可行解的过程，抽象为种群的进化过程（染色体选择、交叉、变异等）

（5）比较可行解的优劣，抽象为量化比较不同种群对当前环境的适应程度

（6）逼近最优解的过程，抽象为淘汰适应度差的种群，保留适应度高的种群进行下一次进化

（7）问题的最优解，抽象为经过多次进化后，最终生存下来的精英种群

        理论上，通过有限次种群进化，生存下来的种群都是 精英染色体 ，是最适合当前环境条件的种群，也就可以无限逼近原始问题的最优解

相关生物学术语：

    为了大家更好了解遗传算法，在此之前先简单介绍一下相关生物学术语，大家了解一下即可。

基因型(genotype)：性状染色体的内部表现；

表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；

进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。

适应度(fitness)：度量某个物种对于生存环境的适应程度。

选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。

复制(reproction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。

交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；

变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。

编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。

解码(decoding)：基因型到表现型的映射。

个体（indivial）：指染色体带有特征的实体；

种群（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问题汇编。

参考：

         https://www.jianshu.com/p/ae5157c26af9

        https://www.jianshu.com/p/b36b520bd187

‘叁’ 遗传算法工具箱中设置了elite count不为零的，但是算法运行过程中为什么还会出现目标值下降

我最近也是刚刚拦历看了一点这方面的东西，可能回答得也不对，就给你提供一个思路吧……简正搜精英保留指的是在复制过程中保留最优个体，之后染色体组还要经历重组和变异，在这个过程中经营染色体可能被破坏。不知道你是不是把重组和变异的概率设置得比较大，如果概率比较小并且世代数不特别大的话应该不会总是出现这样的情况吧。我觉得你也不用太担心这个，毕竟如果目清正标函数比较光滑GA还是能找到解的

‘肆’ 遗传算法中的排序选择策略选择最优的复制到下一代是不是已经包含了精英保留策略的作用

这得看你的排序选择策略是怎样的。
一种排序是只对当代种群进行排序，这种排序选择方式并不包含精英保留策略的作用。
另一种排序是把上一次种群放一直排序，这种方式包含了精英保留策略的作用。
例如有初始种群包含个体为A1,A2,A3,A4，经过适应度计算后得知最优个体为顺序为A2,A1,A3,A4，经过排序选择后为A2,A2,A1,A3，然后经过交叉和变异后的变为B1,B2,B3,B4，而B1,B2,B3,B4的适应度均没有A2大，那么如果采用第一种排序方式，只对B1-B4排序选择，那么将丢失A2这一优良个体，所以并不包含精英保留作用。如果将B1-B4与A1-A2一起排序，那么由于A2适应度最大，因此必然会选到A2，等效于精英保留策略。

‘伍’ an elitist non-dominated sorting genetic algorithm是什么意思

一个带精英策略的非支配排序遗樱返传算法

The basic principle and method of genetic algorithm and an updating genetic algorithm-elitist non-dominated sorting genetic algorithm& elitist non-dominated sorting genetic algorithm ( NSGA-ⅱ) are introced.
本文阐述了遗传算法的基本原理和方法，并着脊伍饥重介绍了一种改进的遗传算法&精橘厅英保留非劣排序遗传算法（NSGA-Ⅱ），并将其应用于化工中的多目标优化。

‘陆’ 遗传算法精英保留策略

你知道一楼的回答为什么局衫没说完吗？因为他是复制粘贴过来的，很不负责任的做法。
你后来的理解大部分正确，但有一点，就是前代的最优个体保存了以后，不参与交叉和变异，拿过来要替代后代的最差个体。然后再从后代个体中重新选出最优个体，这个最优个体就不一定是前代的那个最优个体了。 其实这个过程中已经与前代最优个体进行比较了。
以上是书中的思想。
但有些人是不这么做的，他们会将前代最优个体保存，同时允许前代最优个体参与交搜纤叉和变异。接下来的过程桐漏腔是一样的。

‘柒’ 遗传算法原理简介

遗传算法（Genetic Algorithm, GA）是一种进化计算（Evolutionary Computing）算法，属于人工智能技术的一部分。遗传算法最早是由John Holland和他的学生发明并改进的，源于对达芬奇物种进化理论的模仿。在物种进化过程中，为了适应环境，好的基因得到保留，不好的基因被淘汰，这样经过很多代基因的变化，物种的基因就是当前自然环境下适应度最好的基因。该算法被广泛应用于优化和搜索中，用于寻求最优解（或最优解的近似），其最主要的步骤包括交叉（crossover）和突变（mutation）。

所有的生物体都由细胞组成，每个细胞中都包含了同样的染色体（chromosome）。染色体由一串DNA组成，我们可以简单地把一个生物个体表示为一条染色体。每条染色体上都包含着基因，而基因又是由多个DNA组成的。每个基因都控制着个体某个性状的表达，例如眼睛的颜色、眼皮的单双等。在物种繁衍的过程中，首先发生交叉，来自于父母的染色体经过分裂和重组，形成后代的染色体。之后，后代有一定概率发生基因突变，即染色体上某个位置处的基因以一定概率发生变化。之后，对每一代都重复进行交叉和突变两个步骤。对于每一个后代，我们可以通过一定的方式测量其适应度。适应度越好的个体，在下一次交叉中被选中的概率越大，它的基因越容易传给下一代。这样，后代的适应度就会越来越好，直到收敛到一个稳定值。

在优化问题中，可行解总是有很多个，我们希望寻找一个最优解，它相对于其他可行解来说具有更好的适应度（即目标函数值更大或更小）。每个可行解就是一个“生物个体”，可以表示为状态空间中的一个点和适应度。每个解都是一个经过编码的序列，已二进制编码为例，每个解都是一个二进制序列。这样每个染色体就是一个二进制序列。遗传算法从从一组可行解开始，称为population，从population中随机选择染色体进行交叉产生下一代。这一做法的基于下一代的适应度会好于上一代。遗传算法的过程如下：

终止条件可以是达到了最大迭代次数，或者是前后连续几代的最优染色体的适应度差值小于一个阈值。以上算法描述也许还不够直观，我们举例说明。假设解可以用二进制编码表示，则每个染色体都是一个二进制序列。假设序列长度为16，则每个染色体都是一个16位的二进制序列：

首先，我们随机生成一个population，假设population size为20，则有20个长度为16的二进制序列。计算每个染色体的适应度，然后选取两个染色体进行交叉，如下图所示。下图在第6为上将染色体断开再重组，断开的位置是可以随机选择的。当然，断裂位置也可以不止一个。可以根据具体问题选择具体的交叉方式来提升算法性能。

之后，随机选取后代染色体上某个基因发生基因突变，突变的位置是随机选取的。并且，基因突变并不是在每个后代上都会发生，只是有一定的概率。对于二进制编码，基因突变的方式是按位取反：

上述例子是关于二进制编码的，像求解一元函数在某个区间内的最大最小值就可以使用二进制编码。例如，求解函数f(x)=x+sin(3x)+cos(3x)在区间[0,6]内的最小值。假设我们需要最小值点x保留4位小数，那么求解区间被离散成60000个数。因为2 {15}<60000<2 {16}，所以，需要16位二进制数来表示这60000个可能的解。其中0x0000表示0，0x0001表示0.0001，以此类推。针对这个例子，文末给出了demo code．

然而，在排序问题中无法使用二进制编码，应该采用排列编码（permutation encoding）。例如有下面两个染色体：

交叉：随机选取一个交叉点，从该出将两个染色体断开。染色体A的前部分组成后代1的前部分，然后扫描染色体B，如果出现了后代1中不包含的基因，则将其顺序加入后代1中。同理，染色体B的前部分组成了后代2的前部分，扫描染色体A获得后代2的后部分。注意，交叉的方式多种多样，此处只是举出其中一种方式。

( 1 5 3 2 6 | 4 7 9 8) + ( 8 5 6 7 2 | 3 1 4 9) => ( 1 5 3 2 6 8 7 4 9) + ( 8 5 6 7 2 1 3 4 9)

突变：对于一个染色体，随机选中两个基因互换位置。例如第3个基因和倒数第2个基因互换：

(1 5 3 2 6 8 7 4 9) => (1 5 4 2 6 8 7 3 9)

此外还有值编码（value encoding）和树编码（tree encoding）等，具体例子可以参考这个链接： http://obitko.com/tutorials/genetic-algorithms/encoding.php

在实际的遗传算法中，往往会保留上一代中的少数几个精英（elite），即将上一代population中适应度最好的几个染色体加入到后代的poulation中，同时去除后代population中适应度最差的几个染色体。通过这个策略，如果在某次迭代中产生了最优解，则最优解能够一直保留到迭代结束。

用GA求函数最小值的demo code： https://github.com/JiaxYau/GA_test

参考资料 ：

[1] Introction to Genetic Algorithm, http://obitko.com/tutorials/genetic-algorithms/index.php

[2] Holland J H. Adaption in natural and artificial systems

‘捌’ 请问遗传算法精英保留策略就是指精英选择吗怎么在联赛选择中加入精英策略，请问大致思想是什么

不管采用哪种选择方法，目的是将对结果有利的基因选出来，参加下一次进化。

如果，算法中采用概率类的选择方法，可能会导致本次计算最优的基因（精英）没有被选上。

通常，采用精英保留策略，就是直接将这些（或这个）最优基因，不通过选择，直接参加下一次进化。

理解了，其实是比较好实现的。

但是一定要选择合适的比例。比例太大，进化太慢。

‘玖’ 遗传算法精英保留策略

我个人认为。直接复制本代的最优解到下一代的这种方法虽然会有益于形成较优解，但是违背了遗传规律。个人见解，哈哈。