遗传算法的基本原理和方法
一、编码
编码：将问题的可行解从其解空间转换到遗传算法的搜索空间的一种转换方法。
解码(Decoding):从遗传算法的解空间到问题空间的转换。
二进制编码的缺点是汉明悬崖，即一些相邻整数的二进制码之间存在很大的汉明距离，使得遗传算法的交叉和变异很难交叉。
隐式眼周码：相邻整数之间的汉明距离为1。
(更好)有意义的积木块编码规则：给定的编码应易于生成与待解决问题相关的短距离、低阶积木块；最小字符集编码规则，给定的编码应该采用最小字符集，这样问题才能自然表达或描述。
二进制码比十进制码具有更好的搜索能力，但不能保持种群的稳定性。
动态参数编码：为了得到高精度，让遗传算法从粗糙精度收敛。当遗传算法找到一个区域时，它会立即搜索该区域，重新编码，重新开始并重复这个过程，直到达到所需的精度。
编码方法：
1.二进制编码方法
缺点：连续函数离散化时存在映射错误。不能直接反映问题的结构特征，也不方便针对问题开发具有专门知识的遗传算子，难以满足积木式的编码原则。
2.隐式眼周桃码：两个连续整数对应的码之间只有一个码点不同，其他码点相同。
3.浮点编码法：用一定范围内的浮点数表示个体的每个基因值，个体的编码长度等于其决策变量的位数。
4.每个参数的级联编码：用多变量编码个体的方法。通常每个参数分别用某种编码方法进行编码，然后将它们的代码按照一定的顺序连接在一起，形成代表所有参数的单独代码。
5.多参数交叉编码：将在每个参数中起主要作用的编码位组合在一起，这样就不容易被遗传算子破坏。
评估编码的三个标准：完整性、可靠性和非冗余性。
二、选择
遗传算法中的选择操作是一种遗传操作，用于确定如何从父代群体中选择那些个体以一定的方式遗传给下一代群体，并确定重组或杂交的个体以及被选择的个体将产生多少后代个体。
常用的选择运算符：
1.轮盘赌选择：是一种回放随机抽样的方法。每个个体进入下一代的概率等于其适应值与整个种群中个体适应值之和的比值。选择错误很大。
2.随机锦标赛：一次对一对个体按轮盘选择，然后让两个个体竞争，选择适应性高的那个，以此类推，直到所有候选人都被选中。
3.最佳保留选择：首先按照轮盘赌选择方法进行遗传算法的选择操作，然后将当前种群中适应度最高的个体结构完全复制到下一代种群中。
4.不回放的随机选择(也称例外值选择):根据下一代群体中每个个体的生存预期进行随机选择操作。方法如下
(1)计算下一代群体中每个个体的期望数量n。
(2)如果选择一个个体参与交叉操作，其下一代的期望存活数减少0.5；如果一个个体没有被选中参与交叉操作，它在下一代的预期存活数将减少1.0。
(3)有了选择过程，如果个体的生存期望数小于0，个体将不再有被选择的机会。
5.确定性选择：按照一定的方式选择。具体操作流程如下：
(1)计算下一代种群中每个个体的预期存活数n。
(2)利用n的整数部分确定下一代种群中每个对应个体的存活数。
(3)以n的小数部分降序排列个体，取前m个个体以加入下一代群体。到目前为止，可以完全确定下一代群体中的M个个体。
6.无回放余数的随机选择：可以保证一些适应度大于平均适应度的个体可以传递给下一代种群，因此选择误差相对较小。
7.统一排序：对群体中所有个体的适合度进行排序，并根据这种排序分配每个个体被选中的概率。
8.最佳保存策略：当前种群中适应度最高的个体不参与交叉操作和变异操作，而是用它来代替交叉操作和变异操作后当前种群中适应度最低的个体。
9.随机联盟选择：一次在几个个体中选择一个体能最高的个体，传给下一代群体。
10.排除选择：新产生的后代将替代或排除相似的旧亲本个体，提高群体的多样性。
第三，交叉
遗传算法的交叉操作是指两对染色体以某种方式交换它们的一些基因，从而形成两个新的个体。
适用于二进制编码个体或浮点编码个体的交叉算子：
1.单点交叉：指在个体代码串中只随机设置一个交叉点，然后在该点交换两个配对个体的部分染色体。
2.两点相交和多点相交：
(1)两点交叉：在个体代码串中随机设置两个交叉点，然后进行部分基因交换。
(2)多点交叉
3.均匀交叉：以相同的交叉概率交换两个配对个体每个位点的基因，从而形成两个新个体。
4.算术交叉：两个人的线
性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体。四、变异
遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成以给新的个体。
以下变异算子适用于二进制编码和浮点数编码的个体：
1、基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。
2、均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）
3、边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。
4、非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。
5、高斯近似变异：进行变异操作时用符号均值为P的平均值，方差为P2的正态分布的一个随机数来替换原有的基因值。