遗传算法的主要步骤

遗传算法的主要步骤

为了使用遗传算法来解决优化问题，准备工作分为以下四步［56，57，61］。

7.4.1 确定问题的潜在解的遗传表示方案

在基本的遗传算法中，表示方案是把问题的搜索空间中每个可能的点表示为确定长度的特征串（通常是二进制串）。表示方案的确定需要选择串长l和字母表规模k。在染色体串和问题的搜索空间中的点之间选择映射有时容易实现，有时又非常困难。选择一个便于遗传算法求解问题的表示方案经常需要对问题有深入的了解。

7.4.2 确定适应值的度量

适应值度量为群体中每个可能的确定长度的特征串指定一个适应值，它经常是问题本身所具有的。适应值度量必须有能力计算搜索空间中每个确定长度的特征串的适应值。

7.4.3 确定控制该算法的参数和变量

控制遗传算法的主要参数有群体规模Pop-Size、算法执行的最大代数N-Gen、交叉概率Pc、变异概率Pm和选择策略R等参数。

（1）群体规模Pop-Size。群体规模影响到遗传算法的最终性能和效率。当规模太小时，由于群体对大部分超平面只给出了不充分的样本量，所以得到的结果一般不佳。大的群体更有希望包含出自大量超平面的代表，从而可以阻止过早收敛到局部最优解；然而群体越大，每一代需要的计算量也就越多，这有可能导致一个无法接受的慢收敛率。

（2）交叉率Pc。交叉率控制交叉算子应用的频率，在每代新的群体中，有Pc·Pop-Size个串实行交叉。交叉率越高，群体中串的更新就越快。如果交叉率过高，相对选择能够产生的改进而言，高性能的串被破坏得更快。如果交叉率过低，搜索会由于太小的探查率而可能停滞不前。

（3）变异率Pm。变异是增加群体多样性的搜索算子，每次选择之后，新的群体中的每个串的每一位以相等的变异率进行随机改变。对于M进制串，就是相应的位从1变为0或0变为1。从而每代大约发生Pm·Pop-Size·L次变异，其中L为串长。一个低水平的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。高水平的变异率产生的实质是随机搜索。

比起选择和交叉，变异在遗传算法中是次要的，它在恢复群体中失去的多样性方面具有潜在的作用。例如，在遗传算法执行的开始阶段，串中一个特定位上的值1可能与好的性能紧密联系，也就是说从搜索空间中某些初始随机点开始，在那个位上的值1可能一致地产生适应性度量好的值。因为越好的适应值与串中那个位上的值1相联系，复制作用就越会使群体的遗传多样性损失。当达到一定程度时，值0会从整个群体中的那个位上消失，然而全局最优解可能在串中那个位上是0。一旦搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是达到全局最优解所需的。这仅仅是一种说明搜索空间是非线性的方式，这种情形不是假定的，因为实际上所有我们感兴趣的问题都是非线性的。变异作用提供了一个恢复遗传多样性的损失的方法。

（4）选择策略R。有两种选择策略。一是利用纯选择，即当前群体中每个点复制的次数比与点的性能值成比例。二是利用最优选择，即首先执行纯选择，且具有最好性能的点总是保留到下一代。在缺少最优选择的情况下，由于采样误差、交叉和变异，最好性能的点可能会丢失。

通过指定各个参数Pop-Size、Pc、Pm和R的值，可以表示一个特定的遗传算法。

7.4.4 确定指定结果的方法和停止运行的准则

当遗传的代数达到最大允许代数时，就可以停止算法的执行，并指定执行中得到的最好结果作为算法的结果。

基本的遗传算法

1）随机产生一个由固定长度字符串组成的初始群体。

2）对于字符串群体，迭代地执行下述步骤，直到选择标准被满足为止。

①计算群体中的每个个体字符串的适应值；

②实施下列三种操作（至少前两种）来产生新的群体，操作对象的选取基于与适应度成比例的概率。

选择：把现有的个体串按适应值复制到新的群体中。

交叉：通过遗传重组随机选择两个现有的子串进行遗传重组，产生两个新的串。

变异：将现有串中某一位的字符随机变异产生一个新串。

3）把在后代中出现的最好适应值的个体串指定为遗传算法运行的结果。这一结果可以是问题的解（或近似解）。

基本的遗传算法流程图如图7-1所示。