遗传算法的定义

    遗传算法通常实现为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进 制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中 随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

遗传算法的机理

    在遗传算法里，优化问题的解被称为个体，它表示为一个参数列表，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的表示方法 适用。一开始，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在每一代中，每一个个体都被评价， 并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。这里的“高”是相对于初始的种群的低适应度来说的。

    下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的，其中繁殖包括杂交和突变。选择则是根据新个体的适应度进行的，适应度越高，被选择的 机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入杂交过程。一般的遗传算法 都有一个杂交率的参数，范围一般是0.6~1，这个杂交率反映两个被选中的个体进行杂交的概率。例如，杂交率为0.8，则80%的“夫妻”会生育后代。每 两个个体通过杂交产生两个新个体，代替原来的“老”个体，而不杂交的个体则保持不变。杂交父母的染色体相互交错，从而产生两个新的染色体，第一个个体前半 段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段不是真正的一半，这个位置叫做杂交点，也是随机产生的，可以是染色体的任意位 置。再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数，通常是0.01或者更小，这代表突变发生的概率。根据这个概率， 新个体的染色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。

    经过这一系列的过程（选择、杂交和突变），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去 产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体杂交，然后突变，产生第三代。周而复始，直到 终止条件满足为止。一般终止条件有以下几种：

·  进化次数限制；

·  计算耗费的资源限制（例如计算时间、计算占用的内存等）；

·  一个个体已经满足最小值的条件，即最小值已经找到；

·  适应度已经达到饱和，继续进化不会造成适应度更好的个体；

·  人为干预；

·  以及以上两种或更多种的组合；