3.2　基于遗传程序设计的降水径流回归模型

3.2.1　遗传程序设计

遗传程序设计(Genetic Programming,简称GP),是一种从生物演化过程得到灵感的自动化生成和选择计算机程序来完成用户定义的任务的技术。从理论上讲,人类用遗传编程只需要告诉计算机“需要完成什么”,而不用告诉它“如何去完成”,最终可能实现真正意义上的人工智能。遗传编程是一种特殊的利用进化算法的机器学习技术,它开始于一群由随机生成的千百万个计算机程序组成的“人群”,然后根据一个程序完成给定任务的能力来确定某个程序的适合度,应用达尔文的自然选择(适者生存)确定胜出的程序,计算机程序间也模拟两性组合、变异、基因复制、基因删除等代代进化,直到达到预先确定的某个中止条件为止。遗传编程的首批试验由斯蒂芬·史密斯(1980年)和Nichael·克拉姆(1985年)发表,约翰·Koza(1992年)也写了一本著名的书,《遗传编程:用自然选择让计算机编程》,来介绍遗传编程。使用遗传编程的计算机程序可以用很多种编程语言来写成,早期(或者说传统)的GP实现中,程序的指令和数据的值使用树状结构的组织方式,所以那些本来就提供树状组织形式的编程语言最适合于GP,例如Koza使用的Lisp语言。其他形式的遗传程序也被提倡和实现,例如相对简单的适合传统编程语言(例如Fortran、BASIC和C语言)的线性遗传编程。有商业化的GP软件把线性遗传编程和汇编语言结合来获得更好的性能,也有的实现方法直接生成汇编程序。遗传编程所需的计算量非常之大(处理大量候选的计算机程序),以至于在20世纪90年代的时候它只能用来解决一些简单的问题。近年来,随着遗传编程技术自身的发展和中央处理器计算能力的指数级提升,GP开始产生了一大批显著的成果。该方法通过对运算符及基本函数进行编码并存储于节点之中,表达式由各节点联结而成的树结构存储,每棵树即为一条染色体,利用遗传算法的思想,经过初始染色体群的生成,交叉操作、变异操作,根据“优胜劣汰”的原则进行搜索和优化,自动生成最优的结构表达式,是一种自动化编程技术、一种智能算法,擅长于进行模型结构的自动搜索。

遗传算法的优化机理:在遗传算法里优化问题的解被称为个体,它表示为一个变量序列,叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串,不过也有其他的依赖于特殊问题的表示方法适用,这一过程称为编码。首先,算法随机生成一定数量的个体,有时候操作者也可以对这个随机产生过程进行干预,以提高初始种群的质量。在每一代中,每一个个体都被评价,并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序,适应度高的在前面。这里的“高”是相对于初始的种群的低适应度来说的。下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的,其中繁殖包括交配(crossover,在算法研究领域中我们称之为交叉操作)和突变(mutation)。选择则是根据新个体的适应度进行的,但同时并不意味着完全的以适应度高低作为导向,因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解,我们称之为早熟。作为折中,遗传算法依据原则:适应度越高,被选择的机会越高,而适应度低的,被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后,被选择的个体进入交配过程。一般的遗传算法都有一个交配概率(又称为交叉概率),一般是0.6～1,这个交配概率反映两个被选中的个体进行交配的概率。例如,交配概率为0.8,则80%的“夫妻”会生育后代。每两个个体通过交配产生两个新个体,代替原来的“老”个体,而不交配的个体则保持不变。交配父母的染色体相互交换,从而产生两个新的染色体,第一个个体前半段是父亲的染色体,后半段是母亲的,第二个个体则正好相反。不过这里的半段并不是真正的一半,这个位置叫做交配点,也是随机产生的,可以是染色体的任意位置。再下一步是突变,通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数(又称为变异概率),通常是0.1或者更小,这代表变异发生的概率。根据这个概率,新个体的染色体随机的突变,通常就是改变染色体的一个字节(0变到1,或者1变到0)。经过这一系列的过程(选择、交配和突变),产生的新一代个体不同于初始的一代,并一代一代向增加整体适应度的方向发展,因为最好的个体总是更多地被选择去产生下一代,而适应度低的个体逐渐被淘汰掉。这样的过程不断重复:每个个体被评价,计算出适应度,两个个体交配,然后突变,产生第三代。周而复始,直到终止条件满足为止。一般终止条件有以下几种:①进化次数限制;②计算耗费的资源限制(例如计算时间、计算占用的内存等);③一个个体已经满足最优值的条件,即最优值已经找到;④适应度已经达到饱和,继续进化不会产生适应度更好的个体;⑤人为干预;⑥以及以上两种或更多种的组合。

遗传算法在解决优化问题过程中有如下特点:①遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优,而不能达到全局最优。②初始种群的数量很重要,如果初始种群数量过多,算法会占用大量系统资源,如果初始种群数量过少,算法很可能忽略掉最优解。③对于每个解,一般根据实际情况进行编码,这样有利于编写变异函数和适应度函数(Fitness Function)。④在编码过的遗传算法中,每次变异的编码长度也影响到遗传算法的效率,如果变异代码长度过长,变异的多样性会受到限制,如果变异代码过短,变异的效率会非常低下,选择适当的变异长度是提高效率的关键。⑤变异率也是一个重要的参数。⑥对于动态数据,用遗传算法求最优解比较困难,因为染色体种群很可能过早地收敛,而对以后变化了的数据不再产生变化,对于这个问题,研究者提出了一些方法增加基因的多样性,从而防止过早的收敛。其中一种是所谓触发式超级变异,就是当染色体群体的质量下降(彼此的区别减少)时增加变异概率,另一种叫随机外来染色体,是偶尔加入一些全新的随机生成的染色体个体,从而增加染色体多样性。⑦选择过程很重要,但交叉和变异的重要性存在争议,一种观点认为交叉比变异更重要,因为变异仅仅是保证不丢失某些可能的解,而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新,对于初期的种群来说,交叉几乎等效于一个非常大的变异率,而这么大的变异很可能影响进化过程。⑧遗传算法很快就能找到良好的解,即使是在很复杂的解空间中。⑨遗传算法并不一定总是最好的优化策略,优化问题要具体情况具体分析,所以在使用遗传算法的同时,也可以尝试其他算法,互相补充,甚至根本不用遗传算法。⑩遗传算法不能解决那些“大海捞针”的问题,所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题,使得算法的进化失去导向。􀃋􀁊􀁔对于任何一个具体的优化问题,调节遗传算法的参数可能会有利于更好的更快的收敛,这些参数包括个体数目、交叉率和变异率,例如太大的变异率会导致丢失最优解,而过小的变异率会导致算法过早的收敛于局部最优点,对于这些参数的选择,现在还没有实用的上下限。

本章将这种方法用到降水径流回归模型上,与传统的BP神经网络模型、线性回归模型等进行拟合精度比较,获得了满意的效果。

3.2.2　遗传程序设计的步骤

遗传程序设计的具体步骤如下。

步骤1 明确目标函数。假设X={(x11,x12,…,x1m),(x21,x22,…,x2m),…,(xn1,xn2,…,xnm)}为输入样本系列,X'={x'1,x'2,…,x'n}为输出样本系列。遗传程序计算的目的就是最终寻找最佳函数表达式G(c,x1,…,xm),使误差极小化

式中c——实常数。

步骤2 表达式编码。将变量x、常数c、运算符和基本函数进行编码,并形成集合D,其可细分为终端集T和函数集F。终端集T的元素为变量x、常数c,函数集F的元素为运算符以及基本函数关系,这里为算术运算{+,-,×,÷}和初等函数{sin,cos,arctan,arccot}。表3.1为本书的编码方案,即如果出现编码值为0则在区间[-1,1]上随机的选取一个数;如果出现编码值为1,那么程序随机选择xi(i=1,2,…,m)。称函数G(c,x1,…,xm)为遗传程序设计问题的染色体,可以使用二叉树的形式进行表示,如图3.1所示。

步骤3 初始化染色体。通过选择集合D、T、F元素产生初始染色群体,即二叉树,树的根节点我们从函数集F所对应的编码值中随机进行选取,其中间结点则在集合D对应的编码值中随机进行选择,而叶节点就在终端集T所对应的编码值中随机进行选择。假设染色体群体规模是N,则将生成N棵二叉树,取这些树的最大深度(即层数)在4～6之间,其目的是方便对表达式进行分析解释。

步骤4 评价父代群体。将初始父代染色群体解码后,代入式(3.1),计算出各染色体所对应的目标函数值f(i),i=1,2,…,N,根据f(i)的大小判断染色体的优劣,函数值小的个体为较优秀个体,根据优劣情况对染色体群进行排序,优良染色体排在前面,则定义第i个父代染色体的适应度函数值F(i)为

步骤5 遗传运算。对父代染色体进行选择、交叉、变异的遗传运算。其中选择操作按比例从父代中选取染色体,父代个体i被选择的概率按下式计算:

设:p(0)=0,p(i)=s(1)+s(2)+…+s(N)。利用计算机生成均匀分布随机数u∈[0,1],如果u属于区间[p(i-1),p(i)]中,则第i个染色体被选取。此外,为提高全局搜索的能力,本书直接选取最优秀的5个父代染色体复制到子代中。

交叉操作是要随机的在两棵父代二叉树选取交叉点,而后把以交叉点为根节点的子树进行相互交换。

变异操作是在选取的染色体中随机产生一个变异点,以变异点为根节点,将其以下的子树(包括变异点)按照步骤3的方式随机产生一棵子树来代替。

各种遗传操作都依据相应的操作概率执行:假设选择操作概率为ps,交叉操作概率为pc,那么变异操作概率就是pm=1-ps-pc。利用计算机生成均匀分布随机数u∈[0,1],如果u≤ps,则进行遗传运算进行选择操作,如果ps<u≤(ps+pc),则遗传运算进行交叉操作,如果u>(ps+pc)则进行变异操作。进行N-5次操作,就完成1次进化迭代过程,生产出新的染色体群。

步骤6 寻优最佳染色体。每次迭代中保留最佳染色体,并且产生新的子代染色体群,然后依据步骤4,进行反复演化,一直到其进化迭代次数大于之前的预设值,或目标函数值优于预设值,这时结束程序运行,计算过程完成。此时的最佳染色体即为寻优结果。

3.2.3　基于遗传程序设计的产流预报模型

由于难以全面掌握流域各项物理参数,根据降水径流关系进行产流计算是常用方法。影响降雨径流关系的主要因素有前期影响雨量Pa,降雨历时,降雨强度,暴雨中心位置等,可以通过流域中分布的各个雨量站测得的雨情分析流域平均面雨量,并根据历史数据,利用遗传程序设计建立面雨量、前期影响雨量与径流深R的关系,即P—Pa—R模型,逐时段计算变化的前期影响雨量Pa的值,逐时段计算出净雨,即径流深R,得出净雨过程。具体模型如下。

(1)计算流域时段t平均面雨量。

式中 Pt——流域t时段平均面雨量,mm;

Pi,t——流域t时段第i个雨量站实测雨量,mm;

wi——第i个雨量站的权重。

(2)计算流域前期影响雨量。如果流域内前后两天无雨,则前期影响雨量由式(3.5)计算:

式中 Pa,t——流域t时段前期影响雨量,mm;

K——土壤含水量的消退系数。

若第t-1时段内有降水Pt-1,但未形成径流,则:

若第t-1时段内有降水Pt-1,并形成径流Rt-1,则:

(3)基于遗传程序建立回归模型。

式中 f(·)——遗传程序形成的降水径流关系函数。