基因算法

    GA（Genetic Algorithm）基因算法，是1962年由john holland所提出来的，当时并没有得到应用,直到1983年他的学生goldberg将其实做，从此基因算法便发展开来，成为现在启发式最佳化中流行的方法之一。
    GA的优点就是很快收敛，得到较好的fitness的值，在生产排程、TSP等问题上运用广泛。
    在基因算法当中有很多基础的概念，包括chromosome(染色体),gene(基因),crossover(交配),mutation(突变)等等。
    （1）chromosome(染色体),它是一个DNA串，它可以是用字符串来表示也可以用个向量来表示。一个染色体包含了许多基本的DNA区块，每区块都有其独特的信息。
    （2）crossover（交配），在一个交配点，两个父带的染色体进行信息的交换，从而产生新的染色体。
    （3）mutation(突变)，对于一个染色体，进行信息的变动，在研究当中经常使用的是双点交换。
    （4）population(时代数)，比如说有100条染色体，population就为100
    （5）fitness:fitness的值决定了染色体信息的好坏，我们需要的是fitness好的染色体保留下来，不好的淘汰掉。
     例如运用GA来寻找max x的平方  -10<=x<=10规定染色体的长度为5，population为4，首先随机产生4条染色体分别是：01110、01111、10011、00100。precision of bit encoding:10-(-10)/2*2*2*2*2-1=0.645,下面分别计算其fitness的值：
x1=01110=0.645*(2+4+8)-10=-0.97——>x1的平方=0.94
x2=01111=0.645*(1+2+4+8)-10=-0.325——>x2的平方=0.11
x3=10011=0.645*(1+2+16)-10=2.26——>x3的平方=5.09
x4=00100=0.645*4-10=-7.42——>x4的平方=55.06
fitness的和为x1+x2+x3+x4=61.20
x1被选中的概率:0.94/61.20=0.02
x2被选中的概率:0.11/61.20=0.00
x3被选中的概率:5.09/61.20=0.08
x4被选中的概率:55.06/61.20=0.90
概率大的选中的几率就会大，假设选择了x1和x4,那么对他们进行crossover，假设位置为2
01110          01100
         ——>
00100          00110
交配后新产生的两个子代child1=01100,child2=00110它们对应的fitness分别是5.11和37.58，假设再选出两个父带经过mutation(变异)再产生出child3和child4，这四个子代和以前的父带进行比较，根据fitness的值进行删选，选出前四名，正是所谓的适者生存。
这样的方法一直进行下去，直到收敛找到最佳的population为止。