?注释：是学习之余整理的资料，如有不足的地方还请指教，十分感谢！
目录
遗传算法概述
遗传算法（Genetic? Algorithm）是一种进化算法，原理是仿效生物界的“物竞天择，适者生存”的演化法则。最早由美国Michigan大学的J.Holland教授1967年提出。遗传算法主要特点就是概率化的寻优方法，可自动获取和指导优化。简单遗传算法（Simple Genetic Algorithms，GA)又称简单遗传算法或标准遗传算法），是一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。
搜索机制：遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 遗传算法的原理：
遗传算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息传递规律的启发，所提出的一种智能优化算法。通过程序迭代模拟自然界生物进化的过程，把要解决的问题看作环境，在一些可能的解组成的种群中，通过不断进化寻求最优解。遗传算法通过初始化种群、复制操作、交叉操作、变异操作几个步骤，模拟自然界生物进化过程中的繁殖行为与竞争行为，衍生出下一代的个体，再根据适应度的大小进行个体的优胜劣汰，提高新一代群体的质量，在经过反复多次迭代，逐步逼近复杂工程技术问题的最优解。
遗传算法的搜索策略不是盲目搜索，也不是穷举搜索，而是以目标函数为指导的搜索方式。遗传算法一般采用天然的并行结构，且借助交叉和变异产生新个体，不断产生新个体，扩大搜索范围，因此它不易于陷入局部最优点，并能以较大的概率找到全局最优点。
首先要初始种群，也就是进化的第一代，种群规模要根据问题的规模而定。初始种群的选择会影响算法的收敛速度和结果，多样性较好的种群有利于算法的全局搜索。初始化种群的方式一般为随机产生，产生了初始种群后要进行编码，也可以直接在产生种群的时候就是用编码的方式产生的。基因的编码方式有很多，这也取决于要解决的问题本身。
常见的编码方式有：
1、二进制编码
基因用0或1表示（常用于解决01背包问题）。
如：基因A：00100011010 (代表一个个体的染色体)
优点：编码、解码操作简单易行；交叉、变异操作便于实现；符合最小字符集编码原则；便于利用模式定理对算法进行理论分析。
缺点：存在着连续函数离散化时的映射误差。不能直接反映出所求问题的本身结构特征，不便于开发针对问题的专门知识的遗传运算算子，很难满足积木块编码原则。
2、格雷码编码
连续的两个整数所对应的编码之间仅仅只有一个码位是不同的，其余码位都相同。
3、实数(浮点数)编码
个体的每个基因值用某一范围内的某个浮点数来表示，个体的编码长度等于其决策变量的位数。
4、符号编码
5、互换编码
用于解决排序问题，如旅行商问题和调度问题。
如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。
6、树形编码
用于遗传规划中的演化编程或者表示。
如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。编码方法：基因就是树形结构中的一些函数。
7、值编码
二进制编码不好用时，解决复杂的数值问题。
在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。
8、各参数级联编码：
对含有多个变量的个体进行编码的方法。通常将各个参数分别以某种编码方法进行编码，然后再将他们的编码按照一定顺序连接在一起就组成了表示全部参数的个体编码。
9、多参数交叉编码：
将各个参数中起主要作用的码位集中在一起，这样它们就不易于被遗传算子破坏掉。
遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数选择的越好，解的质量越高。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
停止准则有两个，一个是最大迭代次数，一个就是适应度变化的大小。最大代数,一般取为500~1000，这是为了防止出现迭代次数过多，或者不收敛的情况，所设定的最大的执行次数。当适应度值变化小于某个值时，进化停止，如果始终达不到这个条件，就达到最大迭代次数时停止进化迭代。
选择操作：
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。
常见的选择操作有：
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个个体加入到下一代群体中。至此可完全确定出下一代群体中Ｍ个个体。
6、无回放余数随机选择：
可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中，因而选择误差比较小。
7、均匀排序：
对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。
8、最佳保存策略：
当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。
9、随机联赛选择：
每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。
10、排挤选择：
新生成的子代将代替或排挤相似的旧父代个体，提高群体的多样性。
交叉操作：
所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在GA中起关键作用，是产生新个体的主要方法。
常见的交叉操作：
1、单点交叉：
指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。
2、两点交叉与多点交叉：
（1）两点交叉：在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。
（2）多点交叉
3、均匀交叉（也称一致交叉）：
两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新个体。
4、算术交叉：
由两个个体的线性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体。例如：第k个基因w_k和第l个基因w_l在j位的交叉操作分别为：
w_kj=w_kj (1-b)+w_lj b,
w_lj=w_lj (1-b)+w_kj b
其中b为[0,1]间的随机数.
5、基于“ 与/或 ”交叉法 （用于二进制编码）
对父代按位"与”逻辑运算产生一子代A;按位”或”逻辑运算产生另一子代B。该交叉策略在解背包问题中效果较好。
如：交叉前：
01001011
11011101
交叉后：
01001001
11011111
6、单交叉点法 （用于互换编码）
选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。
如：交叉前：
? 87213 | 09546
? 98356 | 71420
交叉后：
? 87213 | 95640
? 98356 | 72104
7、部分匹配交叉（PMX）法（用于互换编码）
先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
父代A：872 | 130 | 9546
父代B：983 | 567 | 1420? 变为：
TEMP A: 872 | 567 | 9546
TEMP B: 983 | 130 | 1420
对于 TEMP A、TEMP Ｂ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>５ ３<——>６ ７<——>０
子代Ａ：802 | 567 | 9143
子代Ｂ：986 | 130 | 5427
8、顺序交叉法(OX) （用于互换编码）
从父代Ａ随机选一个编码子串，放到子代Ａ的对应位置；子代Ａ空余的位置从父代Ｂ中按Ｂ的顺序选取（与己有编码不重复）。同理可得子代Ｂ。
父代A: 872 | 139 | 0546
父代B: 983 | 567 | 1420
交叉后：
子代A: 856 | 139 | 7420
子代B: 821 | 567 | 3904
9、循环交叉（CX）法（用于互换编码）
CX同OX交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：OX中来自第一个亲代的编码子串是随机产生的，而CX却不是，它是根据两个双亲相应位置的编码而确定的。
父代Ａ：1 2 3 4 5 6 7 8 9
?| |? | |? ?|
父代Ａ：5 4 6 9 2 3 7 8 1
可得循环基因：1->5->2->4->9->1
用循环的基因构成子代Ａ，顺序与父代Ａ一样
1 2 4 5? 9
用父代Ｂ剩余的基因填满子代Ａ：
1 2 6 4 5 3 7 8 9
子代Ｂ的编码同理。（循环基因 5->1->9->4->2->5）
变异操作：
变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。GA中的变异运算是产生新个体的辅助方法，它决定了GA的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
注：变异概率Pm不能太小，这样降低全局搜索能力；也不能太大，Pm > 0.5，这时GA退化为随机搜索。变异概率,一般取为0.001~0.1
遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。
常见的变异操作：
1、基本位变异：
对个体编码串中以变异概率、随机指定的某一位或某几位基因做变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。
2、均匀变异：
分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）
3、边界变异：
随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。
4、非均匀变异：
对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。
5、高斯近似变异：
进行变异操作时用符号均值为Ｐ的平均值，方差为Ｐ２的正态分布的一个随机数来替换原有的基因值。
6、逆转变异算子（用于互换编码）
在个体中随机挑选两个逆转点，再将两个逆转点间的基因交换。
如：变异前：
1346798205
变异后：
1246798305
7、二元变异算子（用于二进制编码）
传统的变异算子执行的是一元操作，即操作只需要一个基因。对于由二进制字符串组成的染色体，我们将数字技术的二元逻辑算子（同或/异或运算）引入到遗传算法中，对传统的变异方式进行彻底变异。即采用二元交叉算子，二元变异操作需要两条染色体参与。
示例如下：
01101011 01000101 “同或”运算
11010001 10111010 “异或”运算
遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。所以，广泛应用于很多学科，主要有函数优化问题、路径优化问题、生产调度问题、自动控制领域、机器人学、图像处理、机器学习以及数据挖掘等方面。
① 群体搜索，易于并行化处理；
② 不是盲目穷举，而是启发式搜索；
③ 适应度函数不受连续、可微等条件的约束，适用范围很广。
④ 容易实现。一旦有了一个遗传算法的程序，如果想解决一个新的问题，只需针对新的问题重新进行基因编码就行；如果编码方法也相同，那只需要改变一下适应度函数就可以了。
① 早熟收敛。这是最大的缺点，即算法对新空间的探索能力是有限的，也容易收敛到局部最优解。
② 计算复杂度高。涉及到大量个体的计算，当问题复杂时，计算时间是个问题。
③ 处理规模小。目前对于维数较高的问题，还是很难处理和优化的。
④ 难于处理非线性约束。对非线性约束的处理，大部分算法都是添加惩罚因子，这是一笔不小的开支。
⑤ 稳定性差。因为算法属于随机类算法，需要多次运算，结果的可靠性差，不能稳定的得到解。
