综合性遗传算法用于水质模型参数估值

李海英1，秦肖生2
(1.中南大学资源环境建筑工程学院，湖南长沙　410083；2.湖南大学环境工程系,湖南长沙　410082)

　　摘　要：将一种具有更高收敛速度、更少迭代次数的综合性遗传算法应用于水环境模型参数估值之中，通过与简单遗传算法计算结果的对比验证了新方法的有效性。
　　关键词： 遗传算法；优化；水质模型；参数估值
　　中图分类号：TU991.21
　　文献标识码：B
　　文章编号：1000-4602(2002)05-0028-03

　　遗传算法(SGA)应用于环境科学领域的研究主要集中在对各种非线性水质模型的参数估计［1］、水质及水污染非线性规划的求解［2］等，但简单的遗传算法在求解中存在不少问题［3］，尤其对类似水质非线性规划等复杂的多变量优化问题则效率并不高，有时并不收敛或者出现“早熟现象”［4］，故提出一种综合性遗传算法(MAGA)。

1　遗传算法和综合遗传算法

　　在利用遗传算法求解问题时，问题的每个可能的解都被编码成一个“染色体”，即若干个体构成了群体(所有可能解)。算法开始时总是随机地产生一些个体(即初始解)，根据预定的 目标函数对每个个体进行评价后得出一个适应度值；基于此适应度值选择个体用来复制下一代，选择操作体现了“适者”生存的原理，“好”的个体被复制，“坏”的则被淘汰；然后选择出来的个体经交叉和变异进行再组合生成新一代，这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解方向进化5］。基本流程见图1。
　　尽管传统遗传算法可以找到全局最优，但在求解许多实际问题时其收敛速度还不尽人意，且操作参数的选取对结果影响巨大，故许多学者对简单的遗传算法进行了改进^［6、7］，在此提出一种效率较高的综合遗传算法。

　　① 选择操作的改进
　　利用基于马尔科夫链的定量的数学证明认为，简单的遗传算法不是全局收敛的，而带有最优个体保留的遗传算法则是全局收敛的^［6］，故在选择操作中采用杰出个体保护策略。?
　　根据目标函数值决定将被复制的数字串，设种群中有N个个体，将这N个个体解码得N个适应性函数值fi(i=1,2,3,…,N),按下述步骤复制：
　　a.令P=随机数×∑fi?
　　
　　则复制第k个数字串。
　　将N个个体f值先按从大到小的顺序排列，复制出N/2个个体到匹配池中等待交叉操作，将选出的N/2个个体进行交叉操作后放回到匹配池中，顶替排在后面的N/2个个体(即将排在后面的N/2个个体清除掉)。对匹配池中的N个个体重新按大到小的顺序排列，采用杰出个体保护策略，即将父代中最优个体放回到匹配池中顶替重新排列后的最后一个个体以保持种群中优秀个体的存在。
　　② 适应值函数调整?
　　在遗传进化初期，通常会出现一些超常的个体，为避免“早熟现象”，应将适应函数值进行适当调整以降低选择强度，在此采用Paul L.Stoffa提出的模拟退火法对适应值函数进行拉伸［7］：

　　

　　式中 ?fi——第i个个体适合度?
　　　　　?N——种群个体总数?
　　　　　?g——遗传代数序号?
　　　　　?T——温度?
　　　　　?T₀——初始温度
　　从式(1)、(2)可以看出，在温度高时(即进化前期)，适合度相近的个体产生后代的概率相近，而当温度不断下降后，拉伸作用加强使得适合度相近的个体适合度差异放大，从而使优秀的个体优势更明显。
　　③ 交叉操作的改进?
　　以单点交叉、两点交叉和交叉位置的非等概率选取相结合作为交叉操作。当染色体位串长度较短时，可采用整串的两点交叉操作；而当染色体位串长度较长时，特别是子串位数较多时可采用各个子串分别进行单点交叉操作，并引进交叉位置的非等概率选取。　　④ 自适应调整Pc和Pm
　　在简单遗传算法中，交换概率Pc和变异概率Pm一般取为恒定值，在进行复杂多变量优化问题时，效率并不高，主要是因为Pc越大个体被破坏的可能性就会增加，使得具有高适应值的个体结构很快被破坏，Pc过小会使搜索缓慢而停滞不前；Pm过大遗传算法就变成了纯粹的随机搜索算法，Pm过小又不易产生新的个体，因此如何选择Pc和Pm是保证算法成功的关键。
　　有学者提出Pc和Pm随适应度值自动改变的方法。对于高于平均适应值 的解，令Pc和Pm取值小一些，使解受破坏的可能性小，而对低于平均适应值的解，令Pc和Pm取值大一些以防止遗传算法陷入局部解。因此按参考文献^［8］提出的方法进行调整：

　　　　

　　式中 ?Pc1=0.9,Pc2=0.7,Pm1=0.01,Pm2=0.001。?
　　⑤ 变量区间优化(动态变量编码)?
　　一般来说，自变量参数(即所求未知参数)的范围越小搜索的速度就越快，也就更加容易确定最优解。设新求出的优化变量值为?x′，将-｜x′｜以及｜x′｜值作为下一次x求解的取值区间的上下限，重新进行计算。?
　　⑥ 终止条件的选择
　　经典的方法是固定遗传代数，到达后即终止，本文采用改进的方法，即根据连续几代个体平均适合度不变(其差小于某个极小的阈值)作为终止的条件。

2　实例验证

　　利用文献^［9］中水质模型的参数估值一实例来比较综合遗传算法与简单遗传算法优化性能的不同。
　　某河流各断面溶解氧实测值如表1所示。

表1 某河流各断面溶解氧实测值 项目 断面(j) 1 2 3 4 x(km) 8 28 36 56 t(h) 2.0 7.0 9.0 14 Cj(mg/L) 8.5 7.0 6.1 7.2

　　水质参数为：饱和溶解氧浓度Cs=10mg/L，初始段面浓度C0=Cs，初始断面BOD浓度L0=20mg/L，流速u=4km/h要求估计BOD衰减系数K1、大气复氧系数K2，使得下式的优化准则函数取得极小值：?

　　

　　为运用综合遗传算法，参数设定如下［7］：
　　串长L=20；?
　　种群个数N=50；?
　　初始温度T0=50 ℃；
　　简单遗传算法Pc=0.6,Pm=0.003；
　　综合遗传算法Pc1=0.8，Pc2=0.5，Pm1=0.005,Pm²=0.001。
　　文献^［9］计算结果为Fmin=0.49,K1=0.056h^-1,K2=0.209 5h-1，本题将适应值函数的平均值不再变化作为算法的收敛判据。两种算法的计算 结果见表2，收敛率与遗传代数的关系曲线见图2。

表2 SGA、SGA-1、M AGA法计算结果 计算次数 30 30 30 30 30 30 30 30 遗传代数 5 10 15 20 25 30 35 40 收敛次数 SGA 3 6 6 9 12 10 15 18 SGA-1 6 13 15 18 22 24 18 21 MAGA 3 18 24 27 30 30 30 30 注：SGA-1为带最优个体保护的SGA。

　　由图2可见，经过25次迭代MAGA的收敛率达到100%，而SGA仅为40%，可见综合遗传算法既发挥了最优个体保护的优势，又克服了异常个体充斥群体的弊端，同时还进行了交换变异概率的自适应调整，收敛效率要高得多。另外为验证综合遗传算法的准确性，还与文献［6］中梯度法的计算结果进行了对比(见表3)。

表3 计算结果对比 项 目 梯度法 SGA算法 MAGA算法 K₁(h^-1) 0.0560 0.0530 0.0560 K₂(h^-1) 0.2095 0.2085 0.2096

　　从表3看出MAGA算法的精度非常高。

3 结论

　　 综合性遗传算法在交叉、变异、适应值函数等方面都对简单遗传算法的相关操作进行了改进，具有精度更高、收敛更快的特点。在水环境模型参数估值的应用实例中，其优势得到了验证。

参考文献：

　　［1］席裕赓.遗传算法综述［J］.控制理论与应用,1996,13(6):697-708.
　　［2］金菊良，杨晓华.非线性环境模型优化的一种数值方法［J］.环境科学进展,1997,12(增刊): 108-112.
　　［3］Dewdney K A.Exploring the field of genetic algorithms in primordial computer sea full of flibs［J］.Scientific American,1985,253(5):21-32.
　　［4］樊会元，王尚锦.遗传算法引入进化方向算子的一个改进及应用［J］.西安交通大学学报,19 99,33(5):45-48.
　　［5］王慧，刘宝坤.一种改进的遗传算法及应用［J］.天津理工学院学报,1998,14(4):62-66.
　　［6］段玉倩，贺家李.遗传算法及其改进［J］.电力系统及其自动化学报,1998,10(1):39-51.
　　［7］丁承民， 张传生，等.遗传算法纵横谈［J］.信息与控制，1997,26(1):40-48.
　　［8］Srinivas M,Patnaik L M.Adaptive probability of crossover and mutation in genetic algorithms［J］.IEEE Trans on SMC,1994,24(4):656-667.
　　［9］程声通，陈毓龄.环境系统分析［M］.北京：高等教育出版社，1996.

---

　　电　　话：(0731)8830832(H)?
　　收稿日期：2001-09-28