2.1 遗传算法(GA)简介
    20世纪60年代由J.Holland提出。GA是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法。与基于导数的解析方法和其他启发式搜索方式（如爬山算法，模拟退火算法，Monte Carlo方法）一样，GA在算法形式上也是一种迭代方法。它从选定的初始解出发，通过不断迭代改进当前解，直到搜索到优秀的解决方案或满意解。在GA中，迭代计算过程采用了模拟生物的进化机制，从一组解（种群）出发，采用类似于自然选择和繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能的下一代解种群。

    GA编码
    整个遗传算法GA的编码是通过基因链码来决定。何为基因链码？
    基因链码：生物的性状是由生物遗传基因的链码所决定。
    使用遗传算法时，需要把问题的每一个解编码成为一个基因链码。设1552是问题的一个解，我们可以用二进制形式11000010000来表示这个解所对应的基因链码，每个基因链码也被称作个体。
    一个群体是若干个体的集合。由于每个个体代表问题的一个解，所以一个群体就是问题的一些解的集合。

    GA编码方法
    编码方法：二进制编码、格雷码编码、浮点数编码、符号编码、多参数级联编码、多参数交叉编码。
    二进制编码可以是实数的二进制表示，也可以是按某种规则进行的二进制编码，但是要求二进制编码与实数之间一一对应。
    例1： 在[0,31]的整数上求F(x)=x2的最大值问题，可以直接利用实数的二进制表示，x={10111}表示16+4+2+1=23。问题转化为求解：

    GA交叉
    对两个相互配对的染色体按某种方式相互交换部分基因，从而形成两个新的个体。
    配对策略：随机配对，即将群体中的M个个体按随机的方式组成。对配对个体组随机确定交叉点的位置。
    基因交换方式：单点交叉、两个交叉
    交叉结果如下所示：
    A: x x x| x x x x A’: x x x y y y y
    B: y y y| y y y y B’: y y y x x x x
    GA变异
    将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成新的个体，称为变异。
例如，对于二进制编码的个体，其编码字符集为{0,1}，变异操作就是将个体在变异点上的基因值取反，即用0替换1，或用1替换0。
    01001101 01000101
    使用变异算子的目的：
    （1）改善GA的局部搜索能力。交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，这是再使用变异算子来调整个体编码串中的部分基因值，就可从局部角度出发使个体更逼近优秀的解决方案。
    （2）维持群体的多样性。变异算子用新的基因值替换原有基因值，从而可以改变个体编码结构，维持群体的多样性，防止早熟现象。

    适应度
    每个个体对应于优化问题的一个解xi,每个解xi对应于一个函数值fi,fi越大（如果优化问题要求取最大），则表明xi越好，即对环境的适应度越高，所以可用每个个体的函数值fi作为它对环境的适应度。

    遗传算法的不足之处
    （1）个体编码形式：固定长度、线形符号串、仅使用染色体表示问题；
    （2）必须对求解的问题编码，难！
    （3）个体是基因型和表现型的综合体（选择操作的目标，遗传信息的载体）；
    （4）对基因组的任何变动都会影响适应度和选择操作；
    （5）GA个体的二面性及其简单结构，导致不能用个体的某一部分来表示问题解，这将严重约束系统的性能；