遗传算法是什么？？

1. 遗传算法是什么？？

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
遗传算法(Genetic Algorithms简称GA)是由美国Michigan大学的John Holland教授于20世纪60年代末创建的。它来源于达尔文的进化论和孟德尔、摩根的遗传学理论，通过模拟生物进化的机制来构造人工系统。遗传算法作为一种全局优化方法，提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对优化函数的要求很低并且对不同种类的问题具有很强的鲁棒性，所以广泛应用于计算机科学、工程技术和社会科学等领域。John Holland教授通过模拟生物进化过程设计了最初的遗传算法，我们称之为标准遗传算法。
标准遗传算法流程如下：
1）初始化遗传算法的群体，包括初始种群的产生以及对个体的编码。
2）计算种群中每个个体的适应度，个体的适应度反映了其优劣程度。
3）通过选择操作选出一些个体，这些个体就是母代个体，用来繁殖子代。
4）选出的母代个体两两配对，按照一定的交叉概率来进行交叉，产生子代个体。
5）按照一定的变异概率，对产生的子代个体进行变异操作。
6）将完成交叉、变异操作的子代个体，替代种群中某些个体，达到更新种群的目的。
7）再次计算种群的适应度，找出当前的最优个体。
8）判断是否满足终止条件，不满足则返回第3）步继续迭代，满足则退出迭代过程，第7）步中得到的当前最优个体，通过解码，就作为本次算法的近似最优解。

具体你可以到百度文库去搜索遗传算法相关的论文，很多的。
你也可以参考百度百科里对遗传算法的介绍。

2. 什么是遗传算法？

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。

说简单了，就是利用达尔文生物进化的原理，利用计算机编程，对问题进行优化求解的一种方法。生物体内遗传因子通过选择、交叉、变异之后，在经过多代的适者生存，是的最适应环境的遗传因子得以遗传到后代，而遗传算法通过一定的算法编写代码产生初始种群，之后利用遗传因子的原理使得初始种群中的代码逐渐接近所求问题得最优解，再根据编码原理解码，使代码还原为非计算机语言表示的真实问题。

3. 什么是遗传算法？

遗传算法（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）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

4. 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过编码（decoding），可以作为问题近似最优解。
5.4.1 非线性优化与模型编码
假定有一组未知参量
xi（i=1，2，…，M）
构成模型向量m，它的非线性目标函数为Φ（m）。根据先验知识，对每个未知量都有上下界αi及bi，即αi≤x≤bi，同时可用间隔di把它离散化，使
di=（bi-αi）/N （5.4.1）
于是，所有允许的模型m将被限制在集
xi=αi+jdi（j=0，1，…，N） （5.4.2）
之内。
通常目标泛函（如经济学中的成本函数）表示观测函数与某种期望模型的失拟，因此非线性优化问题即为在上述限制的模型中求使Φ（m）极小的模型。对少数要求拟合最佳的问题，求目标函数的极大与失拟函数求极小是一致的。对于地球物理问题，通常要进行杀重离散化。首先，地球模型一般用连续函数表示，反演时要离散化为参数集才能用于计算。有时，也将未知函数展开成已知基函数的集，用其系数作为离散化的参数集xi，第二次离散化的需要是因为每一个未知参数在其变化范围内再次被离散化，以使离散模型空间最终包含着有限个非线性优化可选择的模型，其个数为

地球物理数据处理教程

其中M为未知参数xi的个数。由此式可见，K决定于每个参数离散化的间隔di及其变化范围（αi，bi），在大多数情况下它们只能靠先验知识来选择。
一般而言，优化问题非线性化的程度越高，逐次线性化的方法越不稳定，而对蒙特卡洛法却没有影响，因为此法从有限模型空间中随机地挑选新模型并计算其目标函数 Φ（m）。遗传算法与此不同的是同时计算一组模型（开始时是随机地选择的），然后把它进行二进制编码，并通过繁殖、杂交和变异产生一组新模型进一步有限的模型空间搜索。编码的方法可有多种，下面举最简单的例说明之，对于有符号的地球物理参数反演时的编码方式一般要更复杂些。
假设地球为有三个水平层的层次模型，含层底界面深度hj（j=1，2，3）及层速度vj（j=1，2，3）这两组参数。如某个模型的参数值为（十进制）：
h1=6，h2=18，h3=28，单位为10m
v1=6，v2=18，v3=28，单位为 hm/s
按正常的二进制编码法它们可分别用以下字符串表示为：

地球物理数据处理教程

为了减少字节，这种编码方式改变了惯用的单位制，只是按精度要求（深度为10m，波速为hm/s）来规定参数的码值，同时也意味着模型空间离散化间距di都规格化为一个单位（即10m，或hm/s）。当然，在此编码的基础上，还可以写出多种新的编码字符串。例如，三参数值的对应字节顺序重排，就可组成以下新的二进制码串：

地球物理数据处理教程

模型参数的二进制编码是一种数学上的抽象，通过编码把具体的非线性问题和生物演化过程联系了起来，因为这时形成的编码字符串就相当于一组遗传基因的密码。不仅是二进制编码，十进制编码也可直接用于遗传算法。根据生物系统传代过程的规律，这些基因信息将在繁殖中传到下一带，而下一代将按照“适者生存”的原则决定种属的发展和消亡，而优化准则或目标函数就起到了决定“适者生存”的作用，即保留失拟较小的新模型，而放弃失拟大的模型。在传带过程中用编码表示的基因部分地交合和变异，即字符串中的一些子串被保留，有的改变，以使传代的过程向优化的目标演化。总的来说，遗传算法可分为三步：繁殖、杂交和变异。其具体实现过程见图5.8。

图5.8 遗传算法实现过程

5.4.2 遗传算法在地震反演中的应用
以地震走时反演为例，根据最小二乘准则使合成记录与实测数据的拟合差取极小，目标函数可取为

地球物理数据处理教程

式中：Ti，0为观测资料中提取出的地震走时；Ti，s为合成地震或射线追踪算出的地震走时；ΔT为所有合成地震走时的平均值；NA为合成地震数据的个数，它可以少于实测Ti，0的个数，因为在射线追踪时有阴影区存在，不一定能算出合成数据Tj，0。利用射线追踪计算走时的方法很多，参见上一章。对于少数几个波速为常数的水平层，走时反演的参数编码方法可参照上一节介绍的分别对深度和速度编码方法，二进制码的字符串位数1不会太大。要注意的是由深度定出的字符串符合数值由浅到深增大的规律，这一约束条件不应在杂交和传代过程中破坏。这种不等式的约束（h1＜h2＜h3…）在遗传算法中是容易实现的。
对于波场反演，较方便的做法是将地球介质作等间距的划分。例如，将水平层状介质细分为100个等厚度的水平层。在上地壳可假定波速小于6400 m/s（相当于解空间的硬约束），而波速空间距为100m/s，则可将波速用100m/s为单位，每层用6位二进制字符串表示波速，地层模型总共用600位二进制字符串表示（l=600）。初始模型可随机地选取24～192个，然后通过繁殖杂交与变异。杂交概率在0.5～1.0之间，变异概率小于0.01。目标函数（即失拟方程）在频率域可表示为

地球物理数据处理教程

式中：P0（ωk，vj）为实测地震道的频谱；ωk为角频率；vj为第j层的波速；Ps（ωk，vj）为相应的合成地震道；A（ωk）为地震仪及检波器的频率滤波器，例如，可取
A（ω）=sinC4（ω/ωN） （5.4.6）
式中ωN为Nyquist频率，即ωN=π/Δt，Δt为时间采样率。参数C为振幅拟合因子，它起到合成与观测记录之间幅度上匹配的作用。C的计算常用地震道的包络函数的平均比值。例如，设E［］为波动信号的包络函数，可令

地球物理数据处理教程

式中：tmax为包络极大值的对应时间；J为总层数。包络函数可通过复数道的模拟取得。
用遗传算法作波速反演时失拟最小的模型将一直保存到迭代停止。什么时候停止传代还没有理论上可计算的好办法，一般要显示解空间的搜索范围及局部密度，以此来判断是否可以停止传代。值得指出的是，由（5.4.4）和（5.4.5）式给出的目标函数对于有误差的数据是有问题的，反演的目标不是追求对有误差数据的完美拟合，而是要求出准确而且分辨率最高的解估计。
遗传算法在执行中可能出现两类问题。其一称为“早熟”问题，即在传代之初就随机地选中了比较好的模型，它在传代中起主导作用，而使其后的计算因散不开而白白浪费。通常，增加Q值可以改善这种情况。另一类问题正相反，即传相当多代后仍然找不到一个特别好的解估计，即可能有几百个算出的目标函数值都大同小异。这时，最好修改目标函数的比例因子（即（5.4.5）式的分母），以使繁殖概率Ps的变化范围加大。
对于高维地震模型的反演，由于参数太多，相应的模型字符串太长，目前用遗传算法作反演的计算成本还嫌太高。实际上，为了加快计算，不仅要改进反演技巧和传代的控制技术，而且还要大幅度提高正演计算的速度，避免对遗传算法大量的计算花费在正演合成上。

5. 遗传算法

根据问题的目标函数构造一个适值函数，对一个由多个解（每个解对应一个染色体）构成的种群进行评估、遗传、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。
  
 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.排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高群体的多样性。
  
 
  
  
 
  
  
  之前在网上看到的一个比方，觉得很有趣： 
  
 {
  
 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰。所以求最大值的过程就转化成一个“袋鼠跳”的过程。
  
 下面介绍介绍“袋鼠跳”的几种方式。
  
 爬山算法：一只袋鼠朝着比现在高的地方跳去。它找到了不远处的最高的山峰。但是这座山不一定是最高峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
  
 模拟退火：袋鼠喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高峰跳去。这就是模拟退火算法。
  
 遗传算法：有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。
  
 }
  
  （把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！） 
  
  遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！） 
  
 改进与变形
  
 编码方法：

6. 遗传算法

参考文献： 知乎    遗传算法     编码解码知识 
  
 实现遗传算法的第一步就是明确对求解问题的编码和解码方式。对于函数优化问题，一般有两种编码方式，各具优缺点
  
 实数编码：直接用实数表示基因，容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优
  
 二进制编码：稳定性高，种群多样性大，但需要的存储空间大，需要解码且难以理解
  
 对于求解函数最大值问题，我选择的是二进制编码。
  
 
  
                                          
 以我们的目标函数 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 为例。
  
 假如设定求解的精度为小数点后4位，可以将x的解空间划分为 (9-0)×(1e+4)=90000个等分。
  
 2^16<90000<2^17，需要17位二进制数来表示这些解。换句话说，一个解的编码就是一个17位的二进制串。
  
 一开始，这些二进制串是随机生成的。
  
 一个这样的二进制串代表一条染色体串，这里染色体串的长度为17。
  
 对于任何一条这样的染色体chromosome，如何将它复原(解码)到[0,9]这个区间中的数值呢？
  
 对于本问题，我们可以采用以下公式来解码：
  
 decimal( ): 将二进制数转化为十进制数
  
 一般化解码公式：
  
 lower_bound: 函数定义域的下限
  
 upper_bound: 函数定义域的上限
  
 chromosome_size: 染色体的长度
  
 通过上述公式，我们就可以成功地将二进制染色体串解码成[0,9]区间中的十进制实数解。
  
 染色体，就是指由 DNA 组成的聚合体，DNA 上的每个基因都编码了一个独特的性状，比如，头发或者眼睛的颜色
  
 
  
                                          
 
  
                                          
 可以将他看作是一个优化问题，它可以尝试找出某些输入，凭借这些输入我们便可以得到最佳的输出值或者是结果
  
 遗传算法要点：
  
 1.初始化
  
 初始化候选全体，随机初始化
  
 2.查找适应函数
  
 3.选择：物竞天择，适者生存
  
 先选择能量强的个体，然后再进行随机选择，选出适应度虽然小，但是幸存下来的个体
  
 4.交叉：
  
 
  
                                          
 5.变异：根据需要进行选择

7. 遗传算法

优化的算法有很多种，从最基本的梯度下降法到现在的一些启发式算法，如遗传算法(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、所求问题最优值小于给定的阈值.

8. 遗传算法

例如：[1,2,3]，[1,3,2]，[3,2,1]均是函数  3x+4y+5z<100  的可行解（代进去成立即为可行解），那么这些可行解在遗传算法中均称为“染色体”。可行解由 3 个元素构成，每个元素都称为染色体的一个基因。
  
 遗传算法在运行过程中会进行 N 次迭代，每次迭代都会生成若干条染色体。适应度函数会给本次迭代中生成的所有染色体打个分，来评判这些染色体的适应度，然后将适应度低的染色体淘汰，只保留适应度高的染色体，从而讲过若干次迭代后染色体的质量将越来越好。
  
 遗传算法每次迭代会生成 N 条染色体，在遗传算法中一次迭代被称为一次进化。每次进化新的染色体生成的方法——交叉。
                                          
 每一次进化完成后，都要计算每一条染色体的适应度+适应度概率。在交叉过程中就需要根据这个概率来选择父母染色体。适应度高的染色体被选中的概率越高。（这就是遗传算法能够保留优良基因的原因）
  
 交叉能保证每次进化留下优良的基因，但它仅仅是对原有的结果集进行选择，基因还是那么几个，只不过交换了它们的顺序。这只能保证 N 次进化后，计算结果更接近于局部最优解，而永远没办法达到全局最优解（？？？？？），为了解决这个问题，需引入变异。
  
 假设每次进化都需要生成 N 条染色体，那么每次进化中，通过交叉方式需要生成 N-M 条，剩余的 M 条染色体通过复制上一代适应度最高的 M 条染色体而来。
                                          
 本文的目标是使所有任务的总处理时间最少，时间越短适应度越大。适应度 = 1 / 所有任务的总处理时间
  
 将任务从 0 开始编号，用一个一维数组存储每个任务的时长
  
  tasks[i] ：表第 i 个任务的长度。
   第 0 个任务的长度为 2；
   第 1 个任务的长度为 4；
   第 2 个任务的长度为 6；
   第 3 个任务的长度为 8；
  
 将处理器节点从 0 开始编号，用一个一维数组存储每个处理器的处理速度（单位时间内可处理的长度）
  
  nodes[i]  表第 i 个节点的处理速度。
   第 0 个节点的处理速度为 2；
   第 1 个节点的处理速度为 1。
  
  timeMatrix[i][j]  表第 i 个任务在第 j 个节点上处理的话，所需处理时间。
  
 一个可行解就是一个染色体，就是一个一维数组
  
  chromosome[i]=j  表将第 i 个任务分配到节点 j 上处理（任务编号从 0 开始；节点编号从 0 开始）
  
 将任务 0 分配给 3 号节点处理；
   将任务 1 分配给 2 号节点处理；
   将任务 2 分配给 1 号节点处理；
   将任务 3 分配给 0 号节点处理。
  
 记录本次进化生成的 N 条染色体的适应度，将染色体从 0 开始编号。
  
  adaptablility[i]  表第 i 个染色体的适应度
  
  selectionProbability[i]  表第 i 个染色体的适应度概率，所有染色体的适应度概率和为 1 。
  
  java中PriorityQueue优先级队列使用方法 
  
 第 2 次迭代结果
  
 第 100 次迭代结果