第九章 最优化问题和遗传算法

遗传算法从一个代表优化问题解的一组初值进行搜索，这组解称为一个种群（population）。种群是由一定数量的通过基因编码的个体组成的，其中的个体称为染色体（chromosome），用一串代码来标识。不同的个体通过染色体的复制（copy）、交叉（crossover）或变异（mutation）生成新的后代（offspring）。后代也在一代一代地进化，在每一代中使用“适应度”（fitness）评估来检验染色体的优劣，根据适应度的大小选择淘汰部分劣质后代，选择部分优良品质（特征）后代得以保留和组合，使整个种群向优化的方向发展，经过若干代进化后最终得出条件最优的个体作为算法的收敛条件。遗传算法的基本内容是：
1）编码：先将解空间的解数据表示成遗传空间的基因型串结构数据，它们的不同组合就构成了不同的点。编码采用二进制向量形式，也可以根据具体优化问题选择浮点向量编码，编码的长度由优化计算所要求的精度来确定。
2）生成初始种群：采用随机方法产生若干个初始串结构数据，每个串结构数据代表一个个体，全体初始串结构数据构成了初始种群。初始种群的大小一般是20~100，这样既可以提高遗传算法的稳定性，又能够保证种群的多样性，容易获得全局最优解。
3）适应度评估：对于不同的优化问题，采用不同的适应度函数来评价个体的优劣性。
4）选择：按照适者生存的目的，从当前的种群中选择出适应度强的优良个体，使它们有机会作为父代繁殖下一代，增大为下一代贡献一个或多个后代的概率。
5）交叉：交叉算子根据交叉率将种群中两个个体随机地交换某些基因，从而产生新一代个体。新个体组合了父辈个体的特性，交叉体现了信息交换的思想。交叉率的选择是根据具体问题确定的，一般取0.25~0.75，这样既可以得到高适应度的结构，又可以保证搜索效率。
6）变异：变异算子根据变异率随机地在当前种群中选择一个个体，对其以一定的概率随机地改变串结构数据中某个串的数值，从而产生新一代个体。由于生物界产生变异的概率很低，因此变异率一般取0.01~0.20。
交叉和变异是遗传算法的重要内容。交叉是最主要的遗传算法，它在很大程度上决定了遗传算法的性能。交叉是同时对两个染色体进行操作，组合两者的特性产生新的后代。对于采用二进制向量形式编码的种群，交叉运算的最简单方法是在双亲的染色体上随机地选择一个断点，将断点的右段互相交换，从而产生两个新的后代。变异是基本的遗传算法，它在染色体上自发地产生随机变化。一种简单的变异方法是替换一个或多个基因，从而产生一个新的后代。