GA参数与操作设计：控制方法研究

一般而言，GA的设计是按以下步骤进行：

①确定问题的编码方案；

②确定适应度函数计算方法；

③算法参数的选择；

④遗传算子的设计；

⑤确定算法的终止条件。

下面对关键参数和操作的设计做简单介绍[83，149，150]。

1.编码

编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应，这很大程度上依赖于问题的性质，并将影响遗传操作的设计。由于GA的优化过程不是直接作用于问题参数本身，而是在一定编码机制对应的码空间上进行的，因此，编码的选择是影响算法性能与效率的重要因素。

2.适应度函数

适应度函数用于对个体的评价，也是遗传优化的依据。但是如果评价过程占用了太多时间，则势必影响算法的整体优化性能。

为适应GA的优化操作，对于简单的最小化问题，一般直接将目标函数变换为适应度函数；对于复杂优化问题，往往需要构造合适的适应度函数。

由于适应度函数度量意义下的个体差异与目标函数值度量意义下的个体差异有所不同，因此，若适应度值函数设计不当，将难以体现个体的差异，选择操作的作用就很难体现出来，从而造成早熟收敛等问题。目前有多种方法对适应度函数进行改进，如线性变换和指数变换等，即通过某种变换改变原适配值间的比例关系。

3.算法参数

Grefenstette[146]对求解函数优化的标准GA定义了6个关键参数，分别是：种群数目（Population size，记作N）、交叉概率（Crossover rate，记作C）、变异概率（Mutation rate，记作M）、代沟（Generation gap，记作G）、尺度窗口（Scaling windows，记作W）和选择策略（Selection strategy，记作S）。因此，一种GA的实现对应了一种（N，C，M，G，W，S）参数组合。目前除了采用大量的试验或经验之外，理论性的结论至今还很少。

●种群数目N

种群数目是影响算法最终优化性能和效率的因素之一。通常，种群太小，不能提供足够的采样点，以致算法性能不好，甚至得不到可行解；种群太大，尽管增加了优化信息，但无疑增加了计算量，从而使收敛时间太长。在优化过程中种群数目是允许变化的。

●交叉概率C

交叉概率用于控制交叉操作的频率。标准GA中每一代有N×C个个体进行交叉。交叉概率太大，种群中串的更新很快，进而会使高适应度的个体很快被破坏；概率太小，交叉操作进行很少，从而会使搜索停滞不前。交叉是染色体进化的一个最关键步骤。

●变异概率M

变异概率是加大种群多样性的重要原因。一个低的变异概率足以防止整个种群中任一位置的基因一直保持不变。但是，变异概率太小则不会产生新个体，概率太大则使GA成为随机搜索。(www.xing528.com)

●代沟G

代沟用于控制每代中种群被替换的比例，即每代有N×（1-G）个父代个体被选中进入下一代种群。G=100%表示所有个体将被替换。也有些替换策略中G值跟新旧个体的适应度值高低有关而且是变化的。

●尺度窗口W

该参数用于作出由目标值到适应度函数值的调整。比如最大化函数优化问题，个体x的适应度值可定义为：u（x）=f（x）-fmin。其中，f（x）为其目标值，fmin为问题的最小目标值。然而，fmin通常是未知的，许多方法用算法当前的最小目标值f′min作为替代。

●选择策略S

通常有两种选择策略：其一为纯选择（Pure selection），即种群中每一个体根据其适应度值作比例选择；其二为保优选择（Elitist strategy），即先用纯选择进行选择，然后将适应度值最高的一个加入到下一代种群中，该策略可防止最优解的遗失。

由上可知，最佳的GA参数是有赖于问题本身的，而且上述结论一般仅针对标准GA的函数优化。尽管GA是一种有效的优化算法，但其最优参数的确定本身就是一个极其复杂的优化过程。

4.遗传操作

优胜劣汰是设计GA算法的基本思想，它应在选择、交叉、变异和种群替换等操作中得到体现，并考虑到对算法效率与性能的影响。

●种群初始化

通常初始种群是随机产生的，但考虑到搜索效率和质量，一方面要求尽量使初始种群分散地分布在解空间，另一方面可以采用一些简单方法快速产生一些解作为GA的初始个体。

●选择操作

选择操作用于避免有效基因的消失，使高性能的个体得以以更大的概率保存到下一代，从而提高全局收敛性和计算效率。最常用的有比例选择、基于排名的选择和锦标赛选择。

●交叉操作

交叉操作用于组合出新的个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率。

●变异操作

当交叉操作产生的后代适应度值不再进化且没有达到最优时，就意味着算法的早熟收敛。这种现象的原因在于有效基因的缺损，变异可在一定程度上客服这种情况，增加种群的多样性。

5.算法终止条件

GA的收敛理论证明了GA具有概率1收敛的极限性质，然而实际情况中GA难以实现理论上的收敛条件、运行时也不允许无限制的进行搜索、同时其最优解是个未知解，因此必须给定一些收敛条件来终止算法运行。

最常用的方法包括：给定一个最大进化步数、给定个体评价总数、给定最佳搜索解的最大滞留步数。