《综合性遗传算法用于水质模型参数估值》由会员分享,可在线阅读,更多相关《综合性遗传算法用于水质模型参数估值(6页珍藏版)》请在金锄头文库上搜索。
1、1综合性遗传算法用于水质模型参数估值摘要:将一种具有更高收敛速度、更少迭代次数的综合性遗传算法应用于水环境模型参数估值之中,通过与简单遗传算法计算结果的对比验证了新方法的有效性。关键词:遗传算法 优化 水质模型 参数估值 遗传算法(SGA)应用于环境科学领域的研究主要集中在对各种非线性水质模型的参数估计1、水质及水污染非线性规划的求解2等,但简单的遗传算法在求解中存在不少问题3,尤其对类似水质非线性规划等复杂的多变量优化问题则效率并不高,有时并不收敛或者出现“早熟现象”4,故提出一种综合性遗传算法(MAGA)。1 遗传算法和综合遗传算法在利用遗传算法求解问题时,问题的每个可能的解都被编码成一个
2、“染色体”,即若干个体构成了群体(所有可能解)。算法开始时总是随机地产生一些个体(即初始解),根据预定的 目标函数对每个个体进行评价后得出一个适应度值;基于此适应度值选择个体用来复制下一代,选择操作体现了“适者”生存的原理, “好”的个体被复制, “坏”的则被淘汰;然后选择出来的个体经交叉和变异进行再组合生成新一代,这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代,这样逐步朝着更优解方向进化 5。基本流程见图 1。尽管传统遗传算法可以找到全局最优,但在求解许多实际问题时其收敛速度2还不尽人意,且操作参数的选取对结果影响巨大,故许多学者对简单的遗传算法进行了改进6、7,在此提
3、出一种效率较高的综合遗传算法。 选择操作的改进利用基于马尔科夫链的定量的数学证明认为,简单的遗传算法不是全局收敛的,而带有最优个体保留的遗传算法则是全局收敛的6,故在选择操作中采用杰出个体保护策略。 根据目标函数值决定将被复制的数字串,设种群中有 N 个个体,将这 N 个个体解码得 N 个适应性函数值 fi(i=1,2,3,N),按下述步骤复制:a.令 P=随机数fi 则复制第 k 个数字串。将 N 个个体 f 值先按从大到小的顺序排列,复制出 N/2 个个体到匹配池中等待交叉操作,将选出的 N/2 个个体进行交叉操作后放回到匹配池中,顶替排在后面的 N/2 个个体(即将排在后面的 N/2 个
4、个体清除掉)。对匹配池中的 N 个个体重新按大到小的顺序排列,采用杰出个体保护策略,即将父代中最优个体放回到匹配池中顶替重新排列后的最后一个个体以保持种群中优秀个体的存在。 适应值函数调整 在遗传进化初期,通常会出现一些超常的个体,为避免“早熟现象”,应将适应函数值进行适当调整以降低选择强度,在此采用 Paul L.Stoffa 提出的模拟退火法对适应值函数进行拉伸7: 式中 fi第 i 个个体适合度 N种群个体总数 3g遗传代数序号 T温度 T0初始温度从式(1)、(2)可以看出,在温度高时(即进化前期),适合度相近的个体产生后代的概率相近,而当温度不断下降后,拉伸作用加强使得适合度相近的个
5、体适合度差异放大,从而使优秀的个体优势更明显。 交叉操作的改进 以单点交叉、两点交叉和交叉位置的非等概率选取相结合作为交叉操作。当染色体位串长度较短时,可采用整串的两点交叉操作;而当染色体位串长度较长时,特别是子串位数较多时可采用各个子串分别进行单点交叉操作,并引进交叉位置的非等概率选取。 自适应调整 Pc 和 Pm在简单遗传算法中,交换概率 Pc 和变异概率 Pm 一般取为恒定值,在进行复杂多变量优化问题时,效率并不高,主要是因为 Pc 越大个体被破坏的可能性就会增加,使得具有高适应值的个体结构很快被破坏,Pc 过小会使搜索缓慢而停滞不前;Pm 过大遗传算法就变成了纯粹的随机搜索算法,Pm
6、过小又不易产生新的个体,因此如何选择 Pc 和 Pm 是保证算法成功的关键。有学者提出 Pc 和 Pm 随适应度值自动改变的方法。对于高于平均适应值 的解,令 Pc 和 Pm 取值小一些,使解受破坏的可能性小,而对低于平均适应值的解,令 Pc 和 Pm 取值大一些以防止遗传算法陷入局部解。因此按参考文献8提出的方法进行调整: 式中 Pc1=0.9,Pc2=0.7,Pm1=0.01,Pm2=0.001。 变量区间优化(动态变量编码) 4一般来说,自变量参数(即所求未知参数)的范围越小搜索的速度就越快,也就更加容易确定最优解。设新求出的优化变量值为 x,将-x以及x值作为下一次 x 求解的取值区间
7、的上下限,重新进行计算。 终止条件的选择经典的方法是固定遗传代数,到达后即终止,本文采用改进的方法,即根据连续几代个体平均适合度不变(其差小于某个极小的阈值)作为终止的条件。2 实例验证利用文献9中水质模型的参数估值一实例来比较综合遗传算法与简单遗传算法优化性能的不同。某河流各断面溶解氧实测值如表 1 所示。表 1 某河流各断面溶解氧实测值项目 断面(j) 1 2 3 4x(km) 8 28 36 56t(h) 2.057.0 9.0 14Cj(mg/L) 8.5 7.0 6.1 7.2水质参数为:饱和溶解氧浓度 Cs=10mg/L,初始段面浓度 C0=Cs,初始断面BOD 浓度 L0=20m
8、g/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,Pm2=0.001。文献9计算结果为 Fmin=0.49,K1=0.056h-1,K2=0.209 5h-1,本题将适应值函数的平均值不再变化作为算法的收敛判据。两种算法的计算 结果见表 2,收敛率与遗传代数的关系曲线见图 2。表 2 SGA、SGA-1、M AGA
9、法计算结果计算次数630 30 30 30 30 30 30 30遗传代数5 10 15 20 25 30 35 40收敛次数SGA 3 6 6 9 12 10 15 18SGA-1 6 13 15 18 22 24 18 21MAGA 3718 24 27 30 30 30 30注:SGA-1 为带最优个体保护的 SGA。由图 2 可见,经过 25 次迭代 MAGA 的收敛率达到 100%,而 SGA 仅为 40%,可见综合遗传算法既发挥了最优个体保护的优势,又克服了异常个体充斥群体的弊端,同时还进行了交换变异概率的自适应调整,收敛效率要高得多。另外为验证综合遗传算法的准确性,还与文献6中梯
10、度法的计算结果进行了对比(见表 3)。表 3 计算结果对比项 目梯度法 SGA 算法 MAGA 算法K1(h-1) 0.0560 0.0530 0.0560K2(h-1) 0.2095 0.2085 0.2096从表 3 看出 MAGA 算法的精度非常高。83 结论综合性遗传算法在交叉、变异、适应值函数等方面都对简单遗传算法的相关操作进行了改进,具有精度更高、收敛更快的特点。在水环境模型参数估值的应用实例中,其优势得到了验证。参考文献:1席裕赓.遗传算法综述J.控制理论与应用,1996,13(6):697-708.2金菊良,杨晓华.非线性环境模型优化的一种数值方法J.环境科学进展,1997,1
11、2(增刊): 108-112.3Dewdney K A.Exploring the field of genetic algorithms in primordial computer sea full of flibsJ.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.8Srinivas M,Patnaik L M.Adaptive probability of crossover and mutation in genetic algorithmsJ.IEEE Trans on SMC,1994,24(4):656-667.9程声通,陈毓龄.环境系统分析M.北京:高等教育出版社,1996.