简单遗传算法的优化探讨

Holland提出的经典遗传算法一般被称为简单遗传算法（simple genetic algorithm，SGA），其伪代码如下所示（Srinivas and Patnaik，1994）：

在执行上述SGA之前，首先需要对优化问题的解进行编码（encoding）。解的编码称为染色体（chromosome），组成编码的元素称为基因（gene）。编码的目的是将解用合适的方式表达出来，以利于后续的遗传算法计算。对于同一个优化问题，可以设计不同的编码方案。因此，同一个解在不同的编码方案中就可以对应完全不同的染色体。常见的编码方式包括：二进制编码（Holland，1992）、Gray编码、实数编码、整数或字母排列编码，一般数据结构编码等（玄光南、程润伟，2004）。在函数优化和约束优化领域，一般认为实数编码比二进制编码和Gray编码更有效。排列编码（permutation encoding）对组合优化问题较有效。根据编码结构，还可以区分为一维编码（onedimensional encoding）和多维编码（multidimensional encoding）。

有了编码方案之后，还需要构造合适的适应函数（fitness function）。适应值（fitness value）是对染色体进行评价的一种指标，是遗传算法进行优化所用的主要信息，它与解的目标值存在一种对应关系，但不一定就是目标值。也可以将适应值标准化，限定在［0，1］区间内，以方便后续的选择算子（Srinivas and Patnaik，1994）。

在确定适应函数后，遗传算法需要构造初始种群。种群（population）由若干个体（individual）构成，种群规模（population size）即指其中的个体数量。种群规模直接关系到计算量和种群多样性，从而影响遗传算法的效率。对于组合优化问题，通常采用随机方式构造初始种群，也可以采用各种启发式算法构造初始种群。

在有了种群之后，可以根据适应函数对当前种群（current population）中的每一个个体进行评估（evaluation），然后进行选择（selection）。通常，是以适应值的大小决定染色体的生存概率，以实现优胜劣汰，逐步提高种群的平均适应值。

被选中的个体组成一个中间种群（intermediate population），用于繁衍下一代种群（next population）。在繁衍过程中，会以一定的概率进行交叉（crossover）和变异（mutation）。对于中间种群（父代）的两个个体，以交叉概率（probability of crossover，pc）进行染色体的交叉，从而产生新一代（子代）的两个个体。交叉操作使得子代能够继承父代的有效模式，从而有助于产生优良个体。对于单个个体，还以较小的变异概率（probability of mutation，pm）进行基因的变异，从而产生新一代的个体。变异操作有助于增加种群的多样性，避免早熟收敛。(www.xing528.com)

在完成上述遗传操作后，就得到了新一代种群，用于取代当前种群。新的种群可以继续评估、选择、交叉、变异的流程，从而在优化问题的解空间内不断搜索，直到达到终止条件。

从上述的SGA流程可以看出遗传算法是对生物繁殖过程的模拟，遗传算法中的概念可以和生物学概念一一对应，如表7.1所示（邢文训、谢金星，1999）。

表7.1　遗传算法与生物学的对应关系

从上述流程中也可以发现，遗传算法主要包括五大块内容（Michalewicz，1996）：编码方案、适应值函数、初始种群、遗传算子、参数设定。通常，编码方案、适应值函数及参数设定都非常依赖于优化问题。因此，本节后续主要对各类遗传算子进行介绍。