2023年7月29日发(作者：)

水文模拟中并行参数优化算法

申蒙蒙;陆忠华;王彦棡

【摘 要】针对水文模拟中参数优化问题,提出一整套合理的并行参数优化算法.改进优化算法中的相关算子,提高算法的搜索效率;结合遗传算法、模拟退火算法、粒子群算法和差分进化算法4种算法,进一步提高算法的搜索效率;使用基于MPI

(message passing interface)通信子空间的双层主-从并行框架完成实现,减少算法的运行时间.通过调用SWAT (soiland water assessment tool)、HIMS (hydro

informatic modeling system)两大模型的参数优化过程进行实验,实验结果表明,该方法能够有效提高Nash-Suttcliffe系数和运行速度,提升了水文模拟中参数优化过程的效率.%A set of reasonable parallel optimization algorithm was

proposed to optimize the parameters of hydrological

search efficiency of the algorithm was increased by improving some

operators,and higher efficiency was achieved by combining various

optimization running time of the algorithm was reduced

using the double layer master-slave parallel framework based on

communicator in MPI (message passing interface).Extensive simulations

were conducted by invoking SWAT (soil and water assessment tool) and

HIMS (hydro informatic modeling system).Results show that the proposed

method can improve Nash-Suttcliffe coefficient and running

efficiency of optimizing parameters in hydrological simulation is increased

highly leveraging the proposed method.

【期刊名称】《计算机工程与设计》 【年(卷),期】2017(038)004

【总页数】6页(P1002-1007)

【关键词】水文模拟;水土评价工具模型;水循环综合模拟系统;参数优化算法;主-从并行框架

【作 者】申蒙蒙;陆忠华;王彦棡

【作者单位】中国科学院计算机网络信息中心超级计算中心,北京100190;中国科学院大学,北京100049;中国科学院计算机网络信息中心超级计算中心,北京100190;中国科学院计算机网络信息中心超级计算中心,北京100190

【正文语种】中 文

【中图分类】TP301.5

为了改善气候和水资源，水文研究者们历经几十年研究出多种优秀的水文模型，如SWAT[1]、HIMS[2]、GBHM[3]等模型，后来这些模型不断的成长、进化，功能越来越强大、适用范围越来越广，人们对水文模拟的精度、范围提出了比以往更高的期望，所模拟流域的尺度也与日俱增，大尺度模拟将是水文发展的趋势。而在实际应用中，参数优化成为模型首先考虑的问题，参数优化算法的效率(Nash-Suttcliffe系数和运行时间)则是水文工作者们最关心的。

由于水文模拟的参数优化过程往往都是强非线性的，直接求解较为困难，所以本文需要采用一些非数值类的优化算法。智能优化算法是一些针对非数值类问题提出的，是通过自然界已知的进化方法用程序来寻找最优解的过程，主要包括遗传算法、粒子群算法、模拟退火算法、差分进化算法等。近几年学者们对算法本身算子的改进以及算法结合的研究非常多，有些效果非常好，可以将此类算法用于参数优化过程中。

水文模型的参数优化模块在处理大规模水文模拟时，成千上万次的模拟过程对于计算机的性能提出了较高的要求。随着并行计算的快速发展，使得水文模拟也需要考虑并行以提高效率。

本文就是基于参数优化展开，将智能优化算法和并行计算技术结合起来，提出了一套合理的并行参数优化算法，可以调用水文模拟软件进行参数优化，从算法和并行两个方面提高参数优化的效率。用此方法调用SWAT、HIMS两个模型的具体参数优化过程进行验证，解决实际问题。

1.1 遗传算法

遗传算法(genetic algorithm，GA)[4]是根据生物界的进化规律(适者生存、优胜劣汰的遗传机制)推演出来的一种寻优方法。优点是具有并行性，全局寻优能力强；缺点是收敛速度较慢，局部寻优能力比较差。其计算流程如图1所示。

遗传算法有以下几个基本的操作：

(1)编码：主要有二进制编码和实数编码。本文采用实数编码。

(2)选择算子：选择过程主要体现了生物进化过程中“适者生存、优胜劣汰”的思想，而且能够使得优良基因通过遗传保留到下一代个体中。常见的方法为轮盘赌选择法，期望值选择法，确定式采样选择法等。本文采用轮盘赌选择法。

(3)交叉算子：起到共享优良基因的作用。常见的交叉方式有二进制编码的单点交叉、多点交叉、均匀交叉，实数编码的离散交叉、算术交叉、启发式交叉等。本文采用算术交叉。

(4)变异算子：模拟了自然界中基因突变的过程，使算法能够跳出局部最优，进行全局搜索。有二进制变异和实数变异。本文采用实数变异。

1.2 模拟退火算法

模拟退火算法(simulated annealing，SA)[5]是根据固体退火原理演化而来的。其主要优点是能快速找到局部最优点，缺点是收敛速度慢、全局寻优能力差。其计算流程如图2所示。

主要过程如下：

(1)初始化：一个具有较大值的温度T；迭代起始的解X；每个T值对应的迭代次数L。

(2)对k=1,2,3…L做第(3)步～第(6)步：

(3)产生新解X′(其中Xj′=Xj±rand()*T)。

(4)计算增量dE=F(X′)-F(X)，其中F(X)为评价函数。

(5)若dE>0(找最大值)则接受X′作为新的当前解，否则以Metropolis准则所描述的概率exp(dE/(kT))接受X′作为新的当前解。

(6)如果满足终止条件(通常取为连续若干个新解都没有被接受)则输出当前解作为最优解，结束程序。

(7)降温，T逐渐减少，且T>0，然后转第(2)步。

1.3 粒子群算法

粒子群算法(particle swarm optimization，PSO)[6]是受鸟群捕食行动中飞鸟集群活动的规律利用群体智能建立的模型。在每一次迭代中，粒子通过跟踪个体和全局两个“极值”来更新自己的速度和新的位置，以便于向最优值靠近，用下面的公式表示粒子每一次的更新过程

其中，Vij(t)和Xij(t)表示第t次迭代第i个粒子第j维的速度分量和位置分量，Pij为第i个粒子个体最优pBest的第j维分量，Gj为整个种群当前最优pBest的第j维分量，rand()是介于(0,1)之间的随机数，c1、c2是学习因子，通常c1=c2=2。w是惯性权重，较大的w值有利于算法进行全局搜索，而较小的w值有利于算法进行局部搜索。

PSO的主要优点也是能快速找到局部最优点，缺点是收敛速度慢、易陷入局部最优。其计算流程如图3所示。

1.4 差分进化算法

差分进化算法(differential evolution，DE)[7]的基本原理与遗传算法十分相似，也有3个算子：变异、交叉、选择。最大的不同就是DE的变异算子使用了差分策略，利用两个随机个体的向量差对将要变异的个体进行线性结合，从而实现此个体的变异。其计算流程如图4所示。

该算法迭代过程的3个算子如下：

(1)变异算子：DE是使用差分策略去进行个体的变异。最常用的差分策略是任意选择种群中两个相异的个体，求出这两个个体的向量差值，再与将要变异的个体进行一个线性的结合。结合公式为

式中：F为缩放因子，Xi(t)表示第t代种群中第i个个体，Vi(t+1)表示第i个个体变异后的中间体。

(2)交叉算子：对第t代种群{Xi(t)}的每个个体和其所变异的中间种群{Vi(t+1)}的每个个体进行相对应的交叉，得到实验种群{Ui(t+1)}。即

式中：CR为交叉概率，jrand为[1,2,..,N]的随机整数。

(3)选择算子：DE采用贪婪算法来选择进入下一代种群的个体

1.5 算子改进

1.5.1 改进遗传算法中的交叉概率

普通GA中交叉概率pc是定值，文献[8]中引入相似度s=c/D：两个父代种子参数相同的个数c占总参数D的比例。如果相似度小于交叉临界值s

1.5.2 改进粒子群算法中的速度更新公式和惯性权重 文献[9]中在粒子更新速度Vij时将D维参数分3部分单独学习：随机选取L维向全局最优G学习，剩下的D-L维根据学习概率pc向其它粒子最优Pk学习，其余的则向自己粒子最优Pi学习。更新公式为

普通PSO中惯性权重w是定值，文献[10]中将w改为自适应非线性递减，进化初期w较大有利于增加种群多样性，后期w较小有利于算法收敛。w递减公式为

1.5.3 改进差分进化算法变异算子中的缩放因子

普通DE中F是定值，文献[11]中引入自适应变异：将缩放因子F由2F0随着代数增加减小为F0，算法初始时F具有较大值，能够保持种群多样性，避免早熟，后期F较小，避免最优解遭到破坏。缩放因子F随着代数变化公式为

1.6 算法结合

SA、PSO、DE算法优点是局部寻优能力较强，能够快速找到一个局部最优点，缺点是易于陷入局部最优，不能够往更优的方向搜索；而GA局部寻优能力较弱，但由于变异算子的存在能够跳出局部最优，全局搜索能力较强。本文针对这几种优化算法，从两方面改进优化算法的搜索效率。第一，将整个搜索过程分为两个阶段[12]：第一阶段将整个种群分为多个子种群，每个子种群单独执行SA、PSO、DE算法进行局部搜索，第二阶段整个种群一起执行GA算法，利用GA算法的交叉变异特性跳出局部最优进行全局搜索。第二，搜索过程的第一阶段各子种群搜索到多个局部最优，第二阶段会选出整个种群最优，然后将整个种群最优共享给各子种群用来引导别的种群也朝着更优的方向搜索。这样就得到了一种混合参数优化算法。

2.1 并行计算简介

并行计算(parallel computing)是相对于串行计算来讲的，是用多个处理器或者其它的一些计算单元一同执行任务，最终求解出有计算困难的复杂问题的解一个过程。复杂问题在并行计算中被划分为功能相似或者相对独立的一些子问题，在串行计算中这些子问题是按照顺序执行的。但是有些子问题之间是有关联的，比如后一个子问题的输入用到了前几个子问题的输出结果，这种情况下，就必须使用串行计算。但是有些子问题之间并没有关联，并且时间上是并列的，这样的一些子问题就可以使用并行计算；使用并行算法将这些子问题合理分配到多个处理器上，在同一时间执行，以减少整体的运行时间，提高计算效率。所以，并行计算最重要的就是子问题的划分以及研究并行分配算法将子问题分配到各处理器中去执行各自的任务，然后一同解决整个大的问题；而最根本的思想便是分而治之。当然，并行计算所使用的系统便可以有很多，一种是拥有众多处理器的高性能并行计算机，另一种是由一些个人计算机、小型计算机等互相连接在一起组成的集群系统。首先使用并行计算集群对数据进行处理，之后将得到的处理结果再返回给用户以完成特定的任务。

2.2 并行参数优化算法

MPI是一种基于消息传递的并行编程技术，而对等模式和主-从模式是并行计算的两种最基本的并行程序设计模式。上述探讨的智能优化算法非常适合主-从模式，可以利用MPI划分通信子空间的技术达到双层主-从并行框架[13]：将整个通信空间MPI_COMM_WORLD除了主进程的其它所有进程划分为一个单独的组newgroup，并将其创建新的通信空间newcomm，主进程与这个整个组就构成了外层主-从模式；newcomm内可以划分多个通信子空间，每个通信子空间又可以划分首进程和从进程构成内层主-从模式，并且各个通信子空间之间没有干扰；这样就形成了双层主-从并行框架。将上面讨论的多种算法结合的方法用MPI双层主-从并行框架实现如图5所示。其中从进程负责从首进程接收参数，然后调用接口计算结果(本文调用水文模拟的接口计算Nash-Suttcliffe系数)发给首进程；首进程接收从进程的结果，再给从进程分发新的参数，用各自算法更新下一代，并隔genGap代发给主进程子种群最优参数，从主进程接收参数和整个种群最优参数；主进程从首进程接收子种群最优，选出整个种群最优，再将整个种群用GA(遗传算法)执行一遍，最后将整个种群以及最优发给各个首进程。 本节将对本文所提算法在SWAT(天山北坡的数据)、HIMS(数据涉密)两个模型的具体参数优化过程进行数值实验，并对数值实验结果进行比较和分析，探讨算法效率以及并行性能。运行环境为中国科学院计算机网络信息中心超级计算机“元”，实验数值均为运行20次计算得出的平均值。本文设计了3个实验：

(1)算子改进的Nash-Suttcliffe效率系数对比实验(针对HIMS数据)结果如图6所示。

从图6可以看出算子的改进确实有一定的效果，Nash-Suttcliffe系数可以提高0.02以上。

(2)算法结合的Nash-Suttcliffe系数对比实验(针对HIMS数据)结果如图7所示。

从图7可知混合参数优化算法效果非常明显，Nash-Suttcliffe系数可以达到0.84以上，完全达到了HIMS模拟软件要求的Nash-Suttcliffe系数0.8以上。

(3)MPI并行时间对比实验

SWAT模拟100次，种子数120个，运行结果如图8所示(进程数除去主进程和首进程)。

HIMS模拟2000次，种子数120个，运行结果如图9所示(进程数除去主进程和首进程)。

由此实验可知，使用120个CPU核时，SWAT和HIMS运行加速比分别为11.6和108.8，使得整个混合参数优化算法运行时间大大减少。

本文通过对优化算法中算子改进和算法结合的研究，将多种优化算法相结合并用基于MPI通信子空间的双层主-从并行框架实现出来，用于水文模型中的参数优化模块。针对SWAT、HIMS两大模型的参数优化实验结果表明，此方法求出的Nash-Suttcliffe系数有明显提高，运行时间更是成百倍的减少，加速比非常高。并且此方法只要更改接口格式就可以用于其它需要参数优化的场景中，具有很强的可扩展性。下一步的工作主要是将此种参数优化算法利用Hadoop等分布式平台实现出，使算法不再依赖于超级计算机，普通机器也可使用。

【相关文献】

[1]Arnold JG,Moriasi DN,Gassman PW,et :Model use,calibration,and

validation[J].Transactions of the ASABE,2012,55(4):1491-1508.

[2]Liu CM,Zheng HX,Wang ZG,et -scale integrated simulation of hydrological

processes using HIMS with verified case studies[J].Journal of Beijing Normal

University(Natural Science),2010,46(3):268-272.

[3]Alam ZR,Rahman MM,Islam ment of climate change impact on the meghna

river basin using geomorphology based hydrological model[C]//3rd International

Conference on Water & Flood Management,2011.

[4]Man KF,TANG KS,Kwong c algorithms:Concepts and designs[M].Springer

Science & Business Media,2012.

[5]Dowsland KA,Thompson ted annealing[M]//Handbook of Natural

er Berlin Heidelberg,2012:1623-1655.

[6]Bai is of particle swarm optimization algorithm[J].Computer and Information

Science,2010,3(1):180-184.

[7]Neri F,Tirronen advances in differential evolution: A survey and experimental

analysis[J].Artificial Intelligence Review,2010,33(1-2):61-106.

[8]CAO ch and applications based on improved genetic

algorithm[D].Hefei:Anhui University,2010(in Chinese).[曹道友.基于改进遗传算法的应用研究[D].合肥:安徽大学,2010.]

[9]LIN Guohan,ZHANG Jing,LIU Zhaohua,et ter identification of PMSM using

improved comprehensive learning particle swarm optimization[J].Electric Machines and

Control,2015,19(1):51-57(in Chinese).[林国汉,章兢,刘朝华,等.改进综合学习粒子群算法的PMSM参数辨识[J].电机与控制学报,2015,19(1):51-57.]

[10]REN ch of train energy-efficient strategy based on improved particle

swarm optimization algorithm[D].Beijing:Beijing Jiaotong University,2015(in Chinese).[任啸宇.基于优化粒子群算法的列车节能策略研究[D].北京:北京交通大学,2015.]

[11]XIONG Weili,CHEN Minfang,WANG Xiao,et identification method for

Hammerstein model based on improved differential evolution algorithm[J].Journal of

Nanjing University of Science and Technology,2013,37(4):536-542(in Chinese).[熊伟丽,陈敏芳,王肖,等.运用改进差分进化算法辨识Hammerstein模型[J].南京理工大学学报,2013,37(4):536-542.]

[12]ZHANG improved GA-PSO algorithm for wireless sensor network routing[J].Computer and Modernization,2015(12):31-34(in Chinese).[张慧.基于改进GA-PSO的无线传感网络路由算法[J].计算机与现代化,2015(12):31-34.]

[13]LI Qiang,LU Zhonghua,WANG Yangang,et al. Parallel framework for SWAT sensitivity

analysis based on high performance computing[J].Application Research of

Computers,2015,32(1):41-44(in Chinese).[李强,陆忠华,王彦棡,等.基于高性能计算的SWAT参数敏感度分析并行框架[J].计算机应用研究,2015,32(1):41-44.]