遗传算法的基本原理
遗传算法的基本原理和方法
一、编码
编码：把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。
解码（译码）：遗传算法解空间向问题空间的转换。
二进制编码的缺点是汉明悬崖（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－point Crossover）：指在个体编码串中只随机设置一个交叉点，然后再该点相互交换两个配对个体的部分染色体。
2、两点交叉与多点交叉：
（1） 两点交叉（Two－point Crossover）：在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。
（2） 多点交叉（Multi－point Crossover）
3、均匀交叉（也称一致交叉，Uniform Crossover）：两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新个体。
4、算术交叉（Arithmetic Crossover）：由两个个体的线性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体。
四、变异
遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成以给新的个体。
以下变异算子适用于二进制编码和浮点数编码的个体：
1、基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。
2、均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）
3、边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。
4、非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。
遗传算法通常的实现方式，就是用程序来模拟生物种群进化的过程。对于一个求最优解的问题，我们可以把一定数量的候选解（称为个体）抽象地表示为染色体，使种群向更好的解来进化。大家知道，使用算法解决问题的时候，解通常都是用数据或者字符串等表示的，而这个数据或字符串对应到生物中就是某个个体的“染色体”。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价其在整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的种群，该种群在算法的下一次迭代中成为当前种群。其具体的计算步骤如下：
编码：将问题空间转换为遗传空间；
生成初始种群：随机生成P个染色体；
种群适应度计算：按照确定的适应度函数，计算各个染色体的适应度；
选择：根据染色体适应度，按照选择算子进行染色体的选择；
交叉：按照交叉概率对被选择的染色体进行交叉操作，形成下一代种群；
突变：按照突变概率对下一代种群中的个体进行突变操作；
返回第3步继续迭代，直到满足终止条件。
创建一个随机的初始状态
初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。
评估适应度
对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。
繁殖(包括子代突变)
带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。
下一代
如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。
并行计算
非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。
遗传是一种生物从其亲代继承特性和性状的现象。继承的信息由基因携带，多个基因组成染色体，纂因在染色体中的位置为基因座(Locus )。同一基因座可能有的全部基因为等位基因(Alleles，等位基因和基因座决定了染色体的特征，也决定了生物个体的特性。从染色体的表现形式看，有两种相应的表示模式，分别为基因型(Genotype)和表现型( Phenotype)。表现型是指生物个体表现出来的性状，而基因型则是指与表现密切相关的基因组成。同一基因型的生物个体在不同的环境条件下有不同的表现型。因此，表现型是基因型与环境相互作用的结果。
在遗传算法中染色体对应的是一系列符号序列，在标准的遗传算法(即基本遗传算法)中，通常用0, 1组成的位串表示，串上各个位置对应基因座，各位置上的取值对应等位基因。遗传算法对染色体进行处理，染色体称为基因个体。一定数量的基因个体组成基因种群。种群中个体的数目为种群的规模，各个体对环境的适应程度称为适应度(Fitness )。
