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

1 综合性遗传算法用于水质模型参数估值摘要: 将一种具有更高收敛速度、更少迭代次数的综合性遗传算法应用于水环境模型参数估值之中, 通过与简单遗传算法计算结果的对比验证了新方法的有效性。关键词:遗传算法优化水质模型参数估值遗传算法(SGA) 应用于环境科学领域的研究主要集中在对各种非线性水质模型的参数估计[1]、水质及水污染非线性规划的求解[ 2 ]等,但简单的遗传算法在求解中存在不少问题[3], 尤其对类似水质非线性规划等复杂的多变量优化问题则效率并不高, 有时并不收敛或者出现“早熟现象”[4] ,故提出一种综合性遗传算法(MAGA) 。 1 遗传算法和综合遗传算法在利用遗传算法求解问题时,问题的每个可能的解都 2 被编码成一个“染色体”,即若干个体构成了群体( 所有可能解)。算法开始时总是随机地产生一些个体( 即初始解), 根据预定的目标函数对每个个体进行评价后得出一个适应度值; 基于此适应度值选择个体用来复制下一代, 选择操作体现了“适者”生存的原理, “好”的个体被复制, “坏”的则被淘汰; 然后选择出来的个体经交叉和变异进行再组合生成新一代, 这一群新个体由于继承了上一代的一些优良性状, 因而在性能上要优于上一代,这样逐步朝着更优解方向进化 5]。基本流程见图 1。尽管传统遗传算法可以找到全局最优,但在求解许多实际问题时其收敛速度还不尽人意, 且操作参数的选取对结果影响巨大,故许多学者对简单的遗传算法进行了改进[6、7] ,在此提出一种效率较高的综合遗传算法。①选择操作的改进利用基于马尔科夫链的定量的数学证明认为,简单的遗传算法不是全局收敛的, 而带有最优个体保留的遗传算法则是全局收敛的[6], 故在选择操作中采用杰出个体保护策略。蕌根据目标函数值决定将被复制的数字串, 设种群中有N 3 个个体,将这 N 个个体解码得 N 个适应性函数值 fi(i=1,2,3, …,N), 按下述步骤复制: P= 随机数×∑ fi则复制第 k 个数字串。将N 个个体 f 值先按从大到小的顺序排列, 复制出 N/2 个个体到匹配池中等待交叉操作, 将选出的 N/2 个个体进行交叉操作后放回到匹配池中, 顶替排在后面的 N/2 个个体(即将排在后面的 N/2 个个体清除掉) 。对匹配池中的 N 个个体重新按大到小的顺序排列, 采用杰出个体保护策略, 即将父代中最优个体放回到匹配池中顶替重新排列后的最后一个个体以保持种群中优秀个体的存在。②适应值函数调整蕌在遗传进化初期,通常会出现一些超常的个体,为避免“早熟现象”,应将适应函数值进行适当调整以降低选择强度,在此采用 Paul 提出的模拟退火法对适应值函数进行拉伸[ 7]: 式中 fi ——第i 个个体适合度蕌N ——种群个体总数蕌 4 g ——遗传代数序号蕌T ——温度蕌 T0 ——初始温度从式(1) 、(2) 可以看出,在温度高时( 即进化前期) ,适合度相近的个体产生后代的概率相近,而当温度不断下降后,拉伸作用加强使得适合度相近的个体适合度差异放大, 从而使优秀的个体优势更明显。③交叉操作的改进蕌以单点交叉、两点交叉和交叉位置的非等概率选取相结合作为交叉操作。当染色体位串长度较短时, 可采用整串的两点交叉操作; 而当染色体位串长度较长时, 特别是子串位数较多时可采用各个子串分别进行单点交叉操作, 并引进交叉位置的非等概率选取。④自适应调整 Pc和 Pm 在简单遗传算法中,交换概率 Pc 和变异概率 Pm 一般取为恒定值,在进行复杂多变量优化问题时,效率并不高, 主要是因为 Pc 越大个体被破坏的可能性就会增加,使得具有高适应值的个体结构很快被破坏, Pc 过小会使搜索缓慢而停滞不前; Pm 过大遗传算法就变成了纯粹的随机搜索算法, Pm 过小又不易产生新的个体,因此如何选择 Pc和 Pm 是保证算法成功的关键。有学者提出 Pc和 Pm 随适应度值自动改变的方法。对于高于平均适应值的解,令 Pc和 Pm 取值小一些,使解受 5 破坏的可能性小, 而对低于平均适应值的解,令 Pc和 Pm 取值大一些以防止遗传算法陷入局部解。因此按参考文献[8 ]提出的方法进行调整: 式中 Pc1=,Pc2=,Pm1=,Pm2= 。蕌⑤变量区间优化( 动态变量编码)蕌一般来说, 自变量参数( 即所求未知参数) 的范围越小搜索的速度就越快, 也就更加容易确定最优解。设新求出的优化变量值为x′,将-|x′|以及| x′|值作为下一次 x 求解的取值区间的上下限,重新进行计算。蕌⑥终止条件的选择经典的方法是固定遗传代数,到达后即终止,本文采用改进的方法, 即根据连续几代个体平均适合度不变( 其差小于某个极小的阈值) 作为终止的条件。 2 实例