国科大中科院算法讲义遗传算法1210.ppt

遗传算法的收敛性(2) 交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。 变异操作是对种群模式的扰动，有利于增加种群的多样性 。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。 遗传算法的本质 遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。 遗传算法的特点 （1）群体搜索，易于并行化处理； （2）不是盲目穷举，而是启发式搜索； （3）适应度函数不受连续、可微等条件的约束，适用范围很广。 遗传算法的改进 遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。 遗传算法的改进途径 （1）对编码方式的改进 （2）对遗传算子 的改进 （3）对控制参数的改进 （4）对执行策略的改进 编码方式 在设计遗传算法时，编码表示与遗传算子尤其是杂交算子是同步考虑的，如果编码处理不当，在遗传空间中因杂交而生成的个体映射到问题空间时，有可能成为无用解，我们称形成无用解的染色体为致死因子。同时，即使逆映射到问题空间的是有用解，但也可能是和双亲完全无缘的解。编码要避免在问题空间中形成这些不适当的个体。评估编码策略常采用以下3个规范： 1. 完备性(completeness)：问题空间中的所有点(候选解)都能作为演化空间中的点(染色体)表现； 2. 健全性(soundness)：演化空间中的染色体能对应所有问题空间中的候选解； 3.非冗余性(nonredundancy)：染色体和候选解一一对应。 二进制编码（Binary Encoding） 将原问题的解空间映射到位串空间{0,1}l上，然后在位串空间上进行演化操作。结果再通过解码过程还原成其表现型以进行适应值的评估。很多数值与非数值问题都可以用二进制编码以应用演化算法。 二进制编码有如下优点： 二进制编码类似于生物染色体的组成，算法易于用生物遗传理论来解释并使得演化操作如杂交、变异很容易实现； 采用二进制编码时，算法处理的模式数最多； 这种编码方式便于模式定理进行分析，因为模式定理就是以二值编码为基础的。 二进制编码在求解连续数值优化问题时的缺点： 相邻整数的二进制编码可能具有较大的Hamming距离，这种缺陷将降低演化算子的搜索效率，二进制编码的这一缺点有时称为Hamming悬崖（Hamming Cliffs）； 二进制编码时，所需解的精度确定后，串长也就确定了，当需要改变精度时，很难在算法执行过程中进行调整，从而使算法缺乏微调的功能； 当应用于高维、高精度数值问题时，产生的二进制位串很长，搜索空间非常大，从而使算法的搜索效率很低。 格雷编码（Gray Encoding） 格雷编码也称为反射二进制编码，其目的是克服二进制编码的Hamming悬崖的缺点。 格雷编码使得两个相邻的整数的编码只差一个二进制位。 二进制串与格雷串的转换关系如下： 设二进制串 对应的格雷串为 ，则它们之间有如下的变换关系： 其中 表示模2加法运算。 格雷编码（Gray Encoding） Binary Code Gray Code 000 000 001 001 010 011 011 010 100 110 101 111 110 101 111 100 引入了另一种形式的cliff! 实数编码 为了克服二进制编码的缺点，对于问题的变量是实向量的情形，可以直接采用实进制进行编码。这样，便可直接在解的表现型上进行遗传操作。从而便于引入与问题领域相关的启发式信息以增加遗传算法的搜索能力。 “在人工遗传和演化搜索方案中，实型编码或浮点基因的使用已经有很长的历史了，尽管是有争议的，但它们在以后的使用趋势仍在上升。这种上升的使用趋势多少有些使熟知基本遗传算法(GA)理论的研究者感到惊讶，因为简单的分析似乎建议通过使用低基数性的字母表可以增强模式的处理，而来自于实算的结论似乎直接反驳了这种观点，实型编码在许多实际问题里工作得较好。”（ Goldberg ） 对实数编