2.6 遗传算法模型控制参数优选

遗传算法（Genetic Algorithm，简称GA）作为一种全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及高效实用等显著特点，在各个领域得到了广泛应用。遗传算法是以一组群体中的所有个体为对象，并利用随机化技术指导对一个编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作。参数编码、初始化群体的设定、适应度函数的设计、遗传操作的设计、控制参数的设定等5个要素组成了遗传算法的核心内容。

在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始阶段或群体进化过程中需要合理地选择和控制，以使GA以最佳的搜索轨迹达到最优解。许多学者进行了大量的实验研究，给出了最优参数的建议。De Jong（1975）通过研究遗传参数对目标函数的在线或离线性能的影响，得到最好的初始群体为50～100，最佳的单点交叉率为0.6，基本位变异率为0.001，这组参数在遗传算法参数设定中被广泛应用。Grefenstette（1986）通过对一目标函数的计算得到当最优的初始群体为30，交叉率为0.95，变异率为0.01时，目标函数的在线性能最好。J.David Schaffer et.al（1989）通过一系列遗传参数对函数数值优化的在线性能研究，得到最优遗传算法参数的选择根据问题的不同而不同，但建议最优初始群体取值范围为30～50，变异率为0.005～0.01，交叉率为0.75～0.95。Necati Canpolat（1997）通过不同遗传算法参数对优化灌溉模型的求解得到最优参数设定：初始群体大小为5～10，交叉率为0.6，变异率对该模型寻优过程影响不大。实际上，遗传参数与所研究问题的类型有着直接的关系，问题的目标函数越复杂，参数选择就越困难。从理论上讲，不存在一组适用于所有问题的最佳参数，随着问题特征的变化，有效参数的差异往往非常显著。如何设定遗传算法的控制参数使遗传算法的性能得到改善，需要结合实际问题深入研究，以及有赖于遗传算法理论研究的新进展。

本章利用遗传算法求解优化灌溉模型，通过分析不同遗传算法参数对寻优过程的影响，以及不同参数的组合对模型寻优过程的对比，得到一组作物灌溉模型的最优组合参数。同时在该组最优组合参数下，对模型的5种灌水量水平进行优化求解，得到了模型的最优解。

2.6.1 遗传算法的控制参数

遗传算法中需要选择的运行参数主要有编码串长度l、群体大小M、交叉概率P_c、变异概率P_m、终止代数T、代沟G等。这些参数对遗传算法的运行性能影响较大。许多学者进行了大量的实验研究，给出了最优参数建议。

（1）编码串长度。使用二进制编码来表示个体时，编码串长度l的选取与问题所要求的求解精度有关；使用浮点数编码来表示个体时，编码串长度l与决策变量的个数n相等；使用符号编码来表示个体时，编码串长度l由问题的编码方式来确定；另外，也可使用变长度的编码来表示个体。

（2）群体大小M。群体大小M表示群体中所含个体的数量。当M取值较小时，可提高遗传算法速度，但却降低了群体的多样性，有可能会引起遗传算法的早熟现象；而当M取值较大时，又会使得遗传算法的运行效率降低。一般建议的取值范围是20～100。

（3）交叉概率P_c。交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率一般取较大值。但若取值过大，它又会破坏群体中的优良模式，对进化运算反而产生不利的影响；若取值过小，产生新个体的速度又较慢。一般建议的取值范围为0.4～0.99。另外，也可使用自适应的思想来确定交叉概率P_c，如Davis提出：随着遗传算法在线性能的提高，可以增大交叉概率P_c的取值。

（4）变异概率P_m。变异概率P_m是保持群体多样性的有效手段，若取值较大，虽然能够产生出较多的新个体，但也有可能破坏掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若变异概率P_m取值太小，则变异操作产生新个体的能力和抑制早熟现象的能力就会变差。一般建议的取值范围是0.0001～0.1。另外，也可使用自适应的思想来确定。变异概率P_m，如Davis提出：随着遗传算法在线性能的下降，可以减小变异概率P_m的取值；而在Whitley提出的一种自适应变异策略中，P_m与其上一代群体间的海明距离成反比，其结果显示出这种方法能够有效地维持群体的多样性。

（5）终止代数T。终止代数T是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般建议的取值范围是100～1000。当然，遗传算法的终止条件，还可以利用某种判定准则，当判定出群体已经进化成熟，且不再有进化趋势时就可以终止算法的运行过程。常用的判定准则有：①连续几代个体平均适应度的差异小于某一个极小的阈值。②群体中所有个体适应度的方差小于某一个极小的阈值。

（6）代沟G。代沟G是表示各代群体之间个体重叠程度的一个参数，它表示每一代群体中被替换掉的个体在全部个体中所占的百分率，即每一代群体中有（M×G）个个体被替换掉。例如，G=1.0表示群体中的全部个体都是新产生的，这也是最常见的一种情况；G=0.7则表示70%的个体是新产生的，而随机保留了上一代群体中30%的个体。

实际上，上述参数与问题的类型有着直接的关系。问题的目标函数越复杂，参数选择就越困难，从理论上讲，不存在一组适用于所有问题的最佳数值，随着问题特征的变化，有效参数的差异往往非常显著。如何设定遗传算法的控制参数，并使遗传算法的性能得到改善，还需要结合实际问题深入研究，同时有赖于遗传算法理论研究的新进展。

2.6.2 群体规模对寻优过程的影响

根据模式定理，群体规模对遗传算法的性能影响很大，若群体规模为n，则遗传算子可以从这n个个体中生成和检测O（n³）个模式，并在此基础上不断形成和优化建筑模块，直到找到问题的最优解。群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小。但随着群体规模增大，计算量也显著增加。若群体规模太小，可提高遗传算法的运算速度，但却降低了群体的多样性，使遗传算法的搜索空间受到限制，则可能产生未成熟收敛的现象。专家建议的群体规模取n=20～200。

优化灌溉模型在求解过程中，为了提高搜索速度，减少个体适应性评价的计算量，在能搜索到最优解的前提下，尽量减少群体规模。文中采用最优保留策略，即找到当前群体中适应度最高的个体和适应度最低的个体，若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的最好个体，同时用迄今为止最好个体替换当前群体中的最差个体。采用最优保留策略的遗传算法一定能搜索到目标函数的最优解。

在优化灌溉模型求解过程中，针对灌水量在240mm和260mm两种水平下，分别对群体规模为n=5、10、15和20进行模型求解，通过寻优过程曲线确定最佳群体规模。对应的寻优曲线如图2-9、图2-10所示。

图2-9 240mm灌水量寻优曲线

从图2-9和图2-10可见，在不同灌溉水平下，通过对不同群体规模寻优结果的对比，得到群体规模n=15和n=20时，遗传算法都能搜索到模型的最优解，但群体规模为n=20时，搜寻速度较快。故模型的群体规模取n=20。

图2-10 260mm灌水量寻优曲线

2.6.3 交叉率对寻优过程的影响

交叉操作是进化算法中遗传算法具备的原始的独有特征。一般包括如下步骤：①从交配池中随机选取出要交配的一对个体。②根据位串长度L，对要交配的一对个体，随机选取［1，L-1］中一个或多个的整数k作为交叉位置。③根据交叉率P_c（0＜P_c≤1），配对个体在交叉位置处，相互交换各自的部分内容，从而形成一对新的个体。一点交叉的信息量比较小，交叉点位置的选择可能带来较大偏差，同时一点交叉不利于长距模式的保留和重组，而且位串末尾的重要基因总是被交换，所以在实际应用中多采用两点交叉。多点交叉算子的交叉点数和位置的选择有多种方法，对于实参数优化问题采用二进制编码，一般交叉点的数量不宜低于实参数的维数。

交叉概率P_c控制着交叉算子的应用频率，在每一代新的群体中，需要对P_c×n个个体的染色体结构进行交叉操作。交叉频率越高，群体中新结构的引入越快，已获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则可能导致搜索滞阻。一般取P_c=0.6～1.0

优化灌溉模型在240mm灌水量条件下，交叉率取P_c=0.3、0.4、0.5、0.6、0.7和0.8，通过不同的交叉率寻优结果的对比，确定本模型最佳的交叉率。不同交叉率寻优曲线如图2-11所示。

图2-11 240mm灌水量条件下不同交叉率的寻优曲线

通过对不同的交叉率寻优过程的对比，可得到交叉概率在P_c=0.5和0.6时，都能搜索到模型的最优解，但P_c=0.5时，搜索速度明显快于P_c=0.6时，因而本模型取P_c=0.5。

2.6.4 变异率对寻优过程的影响

遗传算法中，变异算子按变异概率P_m随机反转某位等位基因的二进制字符值来实现。从第t代群体中由选择、交叉所生成的交配池中，依次选择个体，随机变异操作的一般形式表示为p‴（t）=m[P″（t），P_m]。对于给定的染色体位串s=a₁a₂…a_L，可表示为

生成新的个体s′=a′₁a′₂…a′_L。其中，x_i是对应于每一个基因位产生的均匀随机变量，x_i∈［0，1］，为了保证个体变异后不会与其父代产生太大的差异，变异概率一般取值较小，以保证群体发展的稳定性。

在遗传算法中使用变异算子主要有以下两个目的：①改善遗传算法的局部搜索能力。遗传算法使用交叉算子，已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时若使用变异算子来调整个体编码串中的部分基因，就可以从局部的角度更加接近最优解，从而提高遗传算法的局部搜索能力。②维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有的基因值，从而可以改变个体编码串的结构，维持群体的多样性。

优化灌溉模型在280mm灌水量下，变异概率取P_m=0.01、0.03、0.05、0.07、0.09和0.1时，分别搜索模型的最优解，寻优曲线结果如图2-12所示。

从图2-11的优化灌溉模型寻优曲线可以看出，变异概率P_m=0.01和0.07时，遗传算法都能搜索到最优解，一般变异概率取值较小，以防个体变异后子代与其父代产生太大的差异，本模型中取P_m=0.01。

2.6.5 模型的优化组合参数寻优过程

从上面的群体规模、交叉概率和变异概率对遗传算法寻优过程的影响可选出一组对应该模型最优的组合参数，即群体规模n=20，交叉概率P_c=0.5，变异概率P_m=0.01，同时在该组参数下，在灌水量为250mm、280mm、310mm、340mm和370mm 5种灌溉水平下，求得了模型的最优解，寻优结果曲线如图2-13所示。

图2-12 280mm灌水量条件下不同变异率寻优曲线

图2-13 不同灌溉水平下寻优结果的对比曲线

从图2-13可以看出，对应不同灌水量模型求解结果来看，对应不同的灌水量，当模型迭代到一定步数时，模型的解达到恒定，即在该组遗传控制参数下，模型总能寻优到最优解。随着灌溉水量的增加，灌溉收益增加。