1.2.1　遗传算法

1975年，遗传算法被美国University of Michigan（密歇根大学）的John Holland教授提出，其基本理论主要以达尔文的自然进化论为基本依据，并借鉴了摩根和孟德尔的群体遗传学说。遗传算法的基本概念如下：通过评估染色体，并对染色体中的基因进行操作，现存的信息被用来指导下一代的染色体，目的是让它进化到更优秀的状态。这种算法不是简单的随机比较搜索，而是一种随机优化算法，在进行问题求解时，将染色体适者生存的过程看成问题的求解过程，通过选择、交叉、变异等基本的操作，从而能够淘汰劣质个体，保留优良个体，通过迭代搜索，可以得到问题的最优解。表1-3是标准的遗传算法的主要步骤。

表1-3　标准遗传算法步骤

在遗传算法中，染色体好坏的判断是根据对适应度函数值的衡量实现的。适应度函数是根据具体的求解问题而设定的，是作为衡量个体好坏而需要获取的唯一标准信息。为了在群体中搜寻到最优的个体，并使其有一定概率成为父代，同时为下一代繁殖子孙，根据选择规则，适应性较强的个体作为父体，为下一代贡献的概率相对来说会比较大。其中，交叉操作是遗传算法中最主要的遗传操作。通过交叉操作得到新一代的个体，新个体能够继承父辈个体的有效模式，进而产生新的优良个体。变异操作是通过随机改变个体中某些基因，从而产生新的个体，其主要作用是能够增加种群的多样性，使算法的"早熟收敛"的缺点能够被避免。