《单纯形—模拟退火混合算法反求水文地质参数及其并行求解》由会员分享，可在线阅读，更多相关《单纯形—模拟退火混合算法反求水文地质参数及其并行求解（7页珍藏版）》请在金锄头文库上搜索。
1、书书书收稿日期： ； 改回日期： ； 责任编辑： 周健、 章雨旭。作者简介： 江思珉， 男， 年生。现为南京大学地球科学系水文学与水资源专业博士研究生。通讯地址： ， 南京大学地球科学系； ： ； 。单纯形模拟退火混合算法反求水文地质参数及其并行求解江思珉 ）， 朱国荣 ），胡西嘉 ），季月华 ） ）南京大学地球科学系， 南京， ； ）南京大学环境学院， 南京， 内容提要： 本文利用单纯形法局部搜索速度快和模拟退火算法全局寻优的特点， 同时为了克服各自算法的弊病， 提出采用单纯形模拟退火混合算法（ ） 进行水文地质逆问题的求解。论文详细描述了 算法的具体操作算子的实现， 并将该算法应用于一个大
2、型水源地的地下水模拟反演。计算结果表明， 算法在水文地质参数反演计算具有求解速度快， 精度高的特点， 而且易于实现并行运算。关键词： 模拟退火算法； 单纯形法； 水文地质参数； 逆问题； 并行求解地下水模型中的水文地质参数是确立地下水模型的基础和关键， 是地下水资源评价的第一阶段。这一阶段通常称为解水文地质逆问题（ 也称反演） 。实质上就是水文地质数学模型的参数识别过程， 亦即在一定的初始条件和边界条件下， 选取最佳的水文地质参数， 使所建立的地下水模型能够最大限度地与所研究的地下水流状况相吻合。这个过程与利用已知的地下水模型来预测地下水动态的正问题求解而言， 所得的解具有不适定性特点 （ 王
3、敏等， ； ， ， ， ；吴剑锋等， ） 。一般说来， 在地下水逆问题求解的时候， 人们往往采用人工识别和自动识别相结合的模型校正方法。所谓的人工识别方法就是通常所说的试估校正方法， 这是一种试算方法， 它通过比较计算水头值与实际观测水头值之间的误差来不断调整水文地质参数， 该方法的最大欠缺就是太费时间； 自动识别方法是借助计算机进行的， 可将其分为直接法和间接法两大类。直接解法是从反映地下水流运动的偏微分方程出发， 把水头的实际观测值作为已知数， 把水文地质参数作为待求的未知数直接求解。间接解法则把解逆问题化为解一系列的正问题。它是试估校正方法的自动化版本， 由计算机根据目标函数来调整参数的
4、最佳取值。然而， 到目前还没有一种自动识别过程可以实现参数的完全自动估值， 都需与人工识别方法相结合才能找到问题的最优解。从数学角度看， 水文地质逆问题的求解就是对决策变量为水文地质参数的最优化问题的求解。常规的优化方法如 法、 单纯形法、 共轭梯度法、 法、 方法等都是与初始点有关的优化方法， 所获得的解往往是局部最优解而不是全局最优（ ， ） 。问题的本意是希望得到给定条件下的全局最优解， 而求全局最优的方法在本质上就是启发式搜索方法。本文涉及到的模拟退火算法是受热力学物理退火过程启发而产生的一种启发式方法， 具有广泛的应用性， 允许任意选取初始解， 不易陷入局部极小点， 但是其缺陷是收敛
5、速度慢、 费时较多； 同时本文涉及的单纯形法是最早运用于水文地质参数优化的方法之一， 它具有算法简单， 收敛快速的求解特点， 存在的缺点是易于陷入局部最优点。因此， 本文针对单纯形法和模拟退火算法各自的优缺点， 提出采用单纯形模拟退火混合算法进行水文地质逆问题的求解。 单纯形法单纯形指的是 维空间中的具有 个顶点的多面体。通过计算单纯形各顶点的目标函数值并加以比较， 从中确定有利的搜索方向和步长， 找到一个较好的点取代单纯形中较差的点， 组成新的单纯形来代替原来的单纯形， 使单纯形不断向目标函数的极小点靠近， 直到搜索到极小点为止。这就是单地质论评第 卷第 期 年 月 纯形法的基本思想。单纯形
6、法属于最优化方法中的无约束类中的直接搜索法， 算法简单、 收敛速度较快， 适用范围广泛，无需通过计算目标函数的导数或梯度来寻求目标下降的最优方向。但单纯形法的求解性能依赖于初始点的选择， 同时采用的是确定性搜索机制， 算法陷入局部极值点后难以跳出。图 单纯形模拟退火混合算法流程图 相对于 法、 法等其他常规经典优化算法而言， 单纯形法具有群体搜索的特性， 算法在每一步的迭代过程中， 针对的是单纯形这一群体， 而不是单独的某个点， 因此具有很好的并行求解特性。 模拟退火算法 年， 等意识到固体退火过程与组合优化问题之间存在的类似性， 并受到 等对固体在恒定温度下达到热平衡过程的模拟的启迪， 提出
7、了模拟退火算法（ 王凌， ） 。模拟退火算法是将物理过程与组合优化相结合的一种随机迭代寻优算法。它由某一较高初始温度开始， 利用概率特性与抽样策略在解空间中进行随机搜索， 随着温度不断下降重复抽样， 用来优化问题解，最终得到问题的全局最优解。模拟退火算法的主要优点是： 不用求目标函数的偏导数及解大型矩阵方程组， 即能找到一个全局最优解， 而且易于加入约束条件， 编写程序简单。这种方法避免了参数估计的结果依赖初始模型的选取， 而容易导致解落入局部极小值的情况。但是， 为了寻到最优解， 算法通常需要较高的初温、 较慢的降温速率、 较低的终止温度以及各温度下足够多的抽样次数， 因而模拟退火算法往往过
8、程较长， 实现效率较低。显然， 在保证一定优化质量的前提下提高算法的搜索效率， 是对模拟退火算法进行改进的主要内容， 而与局部搜索算法结合正是有效的解决途经之一（ ， ） 。 单纯形模拟退火混合算法针对单纯形法（ ） 和模拟退火算法（ ） 的优缺点， 本文提出一种将两种方法的优点有机结合起来的新算法： 单纯形模拟退火混合算法（ ） 。其基本思想是利用 搜索到局部最小点， 然后利用 的突跳性搜索得到 新的初始解， 使它能跳出局部极小点， 伴随退温函数操作通过循环而趋近于全局最优解。近几年来， 国内不少学者结合 并行确定性搜索和 串行全局概率搜索机制， 设计出一些高效可靠的混合算法（ 王凌， ；
9、李树有等， ； 罗亚中等， ） 。本文在罗亚中等设计的 算法流程图基础上进行适当修改， 构建了图 所示的 算法流程图（ 罗亚中等， ） 。 搜索机制的混合 是确定性下降局部搜索方法， 是概率搜索全局算法， 选择机制上完全不同的两种类型算法进行混合， 丰富了搜索行为， 增强全局和局部意义下第 期江思珉等： 单纯形模拟退火混合算法反求水文地质参数及其并行求解的搜索能力和效率。 单纯形顶点的退火搜索的概率选择机制对单纯形群体的进化而言， 当前温度下的 抽样搜索类似于遗传算法中的多次连续变异操作， 其作用是要使得单纯形个体能够跳出局部极值点。由于单纯形群体的优良个体有自身的扩散能力， 因此从整个种群进
10、化的角度出发， 并非每个顶点都需要进行模拟退火操作， 可以依据一定的概率选择必要的顶点进行。本文采用的是选择概率策略（ 罗亚中等， ） 。 算法操作与参数设计 状态产生函数和接受函数 状态产生函数借鉴了实数编码的遗传算法的变异策略， 具体实现见 （ 王成栋等， ； 王登刚等， ） 。状态接受函数采用 ， （ ） （ ， ） 作为接受新状态的条件， 其中， 分别为新旧状态的目标值差和温度。 初始温度和退温函数这里首先设置“ 最佳个体在初温下接受最差个体的概率” 为 （ ， ） ， 当初始种群（ 即为单纯形法随机产生的 个状态） 产生后， 利用下述函数产生初始温度 （ ） （ ） ， 其中， 、
11、分别为种群中最佳和最差个体的目标值。由于考虑了初始种群的相对性能， 初温与种群性能存在一定的关系， 且容易通过调整 得到调整。因而此策略具有一定的普遍性和指导性， 它在一定程度上避免了初温低导致突跳不充分和初温高导致过多迂回搜索的缺点。退温函数采用了指数退温函数， ， 为退温速率， 取值在 之间。 抽样稳定与算法终止准则 抽样稳定准则又称为内循环终止准则， 该准则用于决定在各温度下产生候选解的数目，这里选择为固定步数法， 即在各温度下均以一定步数 进行抽样， 达到阈值就进行退温。 采用了 算法的 为终止条件， 若 ， 则退出算法。 应用实例 地下水数值模型本文将利用 算法对山东省某水源地的地下
12、水模拟的逆问题进行求解。水源地的地下水运动可用二维非均质各项异性来表达。其数学模型为： （ ） （ ） （ ， ， ）（ ， ） （ ， ， ） （ ， ， ） （ ） （ ， ） （ ） （ ， ） （ ， ， ） （ ）其中：， 为渗透系数在 ， 方向上的分量（ ） ； 为水头（ ） ； 为含水层的底板标高（ ） ， 为含水层的厚度； 为源汇项 （ ） ， 包括开采量， 降雨入渗量及河流渗透补给量；为潜水含水层的给水度； 为初始水头（ ） ； 为时间（ ） ； 为第一类边界； 为隔水边界； 为第二类补给边界； 为含水层一类边界水头标高（ ） ； 为第二类补给边界的单宽流量（ ） 。本文采用
13、有限单元法求解上述定解问题， 模拟区域 ， 模拟时间为 ， 区内有 口抽水井，地下水动态观测孔 口。由于研究区含水层具明显的非均质各项异性特征， 根据勘探获得的含水层分布规律， 可将研究区划分为三个参数分区（ 图 ） 。 水文地质逆问题 参数约束区间本次反演的水文地质参数为各分区的渗透系数和给水度。根据含水层的性质、 流场形态及水位变化等资料， 设定了各参数的约束区间， 表达式为： ， ， （ ）其中， 、 、 为第 区的水文地质参数 ， 和值； ， ， ， ， ， 为对应参数的上下限值。 目标函数 （ ， ， ） （ ） （ ） （ ）其中， 表示观测孔数目； 表示观测时段数； 为权地质论评
14、 年图 研究区地下水模拟剖分图 重； （ ） 表示 时刻的实测水头； （ ） 表示 时刻的计算水头； 为目标函数， 它反映了计算水头和实测水头之间的拟合程度。综上所述， 在水文地质逆问题的求解中， 目标函数的求解需要借助求解地下水数值模型正问题进行。因此， 由目标函数、 参数约束区间表达式和地下水数值模型方程组组成了水文地质逆问题， 这是一个复杂的非线性约束优化问题。 求解水文地质逆问题 约束条件的处理由于 算法中的单纯形法是一种求解无约束的优化方法， 无边界约束处理， 而水文地质参数寻优问题中对参数具有简单的约束条件。考虑对约束条件进行预处理和简化。根据以上的思路， 对于形如 ， ， ， ，
15、 的简单约束可以转化为 （ ） ， 这样， 约束优化问题就被当作无约束优化问题来求解（ 席少霖， ； 王敏等， ） 。 算法操作与参数 过程的状态产生函数如下描述： 当前水文地质参数为 （ ， ， ） ， 随机选取个分量 ， 产生随机扰动， 则扰动后的分量为 （ ， ）如果 （ ， ） （ ， ）如果 （ ， ） （ ）其中， ， ， ， ； ， 为选定的第 个参数的上下限； （ ， ） 为 ， 范围内的随机数； （ ， ） 表示 ， 范围内非均匀分布的随机数， 定义为：（ ， ） （ ） （ ）这里的 为 ， 内的随机数； 为系统参数，取值为 ； 为当前的步数。这样的 算法使得初期的邻域范围
16、（ 变异范围） 较大， 有利于随机搜索； 随着温度的降低， 搜索也就集中在最有希望的重点区域进行， 这样可以减少后期的无效搜索次数。最佳个体在初温下接受最差个体的概率 ； 为退温速率； 抽样步数 （ 并行抽样取值为 ） ； 。 的并行实现单纯形法（ ） 的并行求解特性决定了混合算法很容易由串行改为并行。因为每个单纯形顶点上的计算是独立的， 故只需将每个顶点上的计算分配给不同的处理器或者分布式系统中的不同结点机，即可实现并行求解。如图 的算法对单纯形顶点的退火操作就完全可以采用并行求解， 并且各个并行搜索的结果可以通过单纯形的反射、 扩张等操作有机地进行了搜索信息融合， 同时整个算法也具有较大规
17、模的并行粒度， 有利于并行计算的实现。本文中引入基于分布式机群计算技术和基于消息传递的 来实现 算法（ 李树有等， ； 王浩然等， ； 王浩然等， ； 刘信安等， ） 。 参数寻优结果按照以上的步骤和操作对 描述的水文地质逆问题进行了求解， 并将计算结果与单纯形法和模拟退火算法进行比较。计算成果见表 。从表 可以得到以下结果：（ ）从计算精度上看， 采用 算法计算的目标函数值最大， 平均到单个观测孔的每个时间段的拟合水头误差为 ， 串行算法误差最小，仅为 ， 算法的计算误差介于中间。究其原因认为 算法寻优为局部寻优， 未能探索到逆问题的全局最优点。而 算法的误差相对于 算法较大原因是 算法在局
18、部极小值附近的搜索效果差引起的。结果表明在三种算法中， 混合算法获得的最优解具有最小的拟合误差。（ ）从计算时间上看， 以 算法最快， 算法最慢， 串行算法介于其间。而 算法的计算耗时最少是以牺牲计算精度为代价的（ 目标函数值最大） 。第 期江思珉等： 单纯形模拟退火混合算法反求水文地质参数及其并行求解表 、 、 求解水文地质参数成果比较 ， 优化方法 （ 串行） （ 并行）参数分区 参数分区 参数分区 目标函数值 计算时间 结论综合以上两点， 可以认为 算法是一种识别地下水模型的高效寻优方法。表 的右边两列更加说明， 尽管 方法在 需求上不如单纯形法节省， 但由于算法本身具备的并行求解可能，
19、 在使用并行求解手段后却弥补了这一不足。当然， 如果使用更多的结点机来协同处理， 获得更高的求解速度是毋庸置疑的。表 的第四列所显示的结果是采用实验室内部网络中的 台机器并行计算得到的， 计算效率没有想当然的提高 倍， 实际的并行计算加速比为 。其原因分析如下：（ ）台计算机的性能差异， 其中性能最差的机器将迟滞并行计算速度， 解决办法是尽量使参加并行计算的计算机具有比较一致的性能。（ ）计算机之间的消息传递所需要的网络通信开销（ 目前使用的大多为 的通讯速率） ， 解决办法是采用高速局域网架构或者在每台计算机中安装多块网卡。（ ）机群中的非线性问题， 研究证明， 个 的并行计算效率小于 ；
20、对于机群计算来说， 即使计算机间的通讯造成的系统迟滞可以忽略， 个结点的并行计算效率也同样小于 ， 但非线性衰减量要小于 个 的情况。（ ）代码的并行优化有待继续研究。尽管如此， 方法还是在很大的程度上克服了 方法和 方法的弊端， 发挥了两者的所长， 保证了 方法能以远小于 方法所需的计算开销而又能获得比 和 方法优异得多的计算结果， 这对水文地质参数寻优工作来说无疑是非常有用的。另一方面， 必须指出的是， 本文采用的分布式机群并行计算机制是非常容易实现的， 只需要利用一个现成的局域网络（ 例如办公室的网络） ，再加上一套 软件就可以构成并行计算系统。并行求解机制的引入， 将使 方法获得更高的
21、求解速度， 达到推广应用的目的。参考文献 李树有， 都志辉， 吴梦月， 朱静， 李三立 模拟退火算法的并行实现及其应用物理学报， （ ） ： 刘信安， 李佳 基于 集群系统的 大规模并行计算实现和应用研究计算机与应用化学， （ ） ： 罗亚中， 唐国金 两层非线性规划问题的并行模拟退火全局优化系统仿真学报， （ ） ： 王成栋，张优云 基于实数编码的自适应伪并行遗传算法西安交通大学学报， （ ） ： 王登刚， 刘迎曦， 李守巨 求解不可微函数优化的一种混合遗传算法东北大学学报（ 自然科学版） ， （ ） ： 王浩然， 朱国荣， 赵金熙 基于区域分解法的地下水有限元与边界元耦合模型地质论评， （
22、 ） ： 王浩然， 朱国荣， 江思珉， 王敏 基于区域分解法的地下水有限元并行数值模拟南京大学学报（ 自然科学版） ， （ ） ： 王凌 智能优化算法及其应用 北京： 清华大学出版社， 施普林格出版社， ， 王敏， 朱国荣， 孔祥龙， 江思珉， 季月华 用 方法进行水文地质参数寻优的研究地质论评， （ ） ： 吴剑锋， 钱家忠， 朱学愚， 李竞生 基于连续不确定区域的遗传算法求解水文地质逆问题水利学报， （ ） ： 席少霖 非线性最优化方法北京： 高等教育出版社， ， ， （ ） ， ， ： ， （ ） ： ， ： ， ， ， （ ） ： ， ： ， （ ） ： ， ， ， （ ） ： 地质论
23、评 年 ）， ）， ）， ） ） ， ， ； ） ， ， ， ， ， ， ， ， ， ， ， ， ： ； ； ； ； 曾培炎副总理接见第三届黄汲清青年地质科技奖获得者并发表重要讲话 年 月 日上午， 中共中央政治局委员、 国务院副总理曾培炎同志在北京国际会议中心接见了第三届黄汲清青年地质科技奖获得者， 并发表重要讲话。国土资源部部长、 中国地质学会理事长、 黄汲清青年地质科技奖基金管理委员会主任孙文盛同志主持了会议。曾培炎同志首先代表党中央、 国务院向地质科技工作者致以亲切的问候！向获得第三届黄汲清青年地质科技奖的同志们表示祝贺！曾培炎同志说， 中国改革开放以后， 特别是近五年到十年以来， 经
24、济社会有了迅速的发展， 对地质工作的要求也越来越高。今年， 国务院专门研究、 而且下发了 关于进一步加强地质工作的决定 ， 专门召开了 全国地质工作会议 ， 当前应该说是地质战线发展的一个大好时机， 各级领导对地质工作都高度重视， 社会也非常关注， 各个方面的投资都不断增加。你们都是地质战线的佼佼者， 应该以邓小平理论、 三个代表重要思想为指导， 全面贯彻落实科学发展观， 更好地完成国家赋予你们的使命。他说， 借这个机会， 给大家提几点要求： 地质工作要面向经济社会发展。由于经济的高速发展， 这几年对基础原材料， 对能源需求越来越多， 要求也越来越高。地质工作者有责任， 寻找国家需要的矿产资源
25、， 通过努力要有所突破， 满足经济社会发展的需要。 青年地质工作者要有开拓创新的精神。希望青年地质工作者在成矿理论、 探矿技术方法有所创新， 真正把高新技术应用到地质工作中， 以最小的成本开发好我国的矿产资源。 发扬黄汲清等老一辈科学家热爱祖国、 为祖国的地质事业献身的精神； 继承他们爱岗敬业、对地质科学事业执着的拼搏精神； 学习他们不怕艰苦、 淡薄名利的高尚品质， 为祖国的发展作出新的贡献。各级政府及国土资源部门， 要为青年科学家成长提供好的环境， 让他们能够干成事业、 能够干出事业、 能够干好事业， 使我们地质工作兴旺发达， 也使我们地质工作后继有人。 希望第三届黄汲清青年地质科技奖获得者
26、能够在新的起点上， 继续发扬艰苦奋斗的精神， 戒骄戒躁， 作出新的贡献。孙文盛部长强调， 曾培炎副总理的接见， 是党中央、 国务院对同志们的关心， 也是对全国地质科技工作者的关心； 是对地质工作的关心， 也是对我们国土资源系统的关心； 是你们的光荣， 也是我们全系统的光荣。曾培炎副总理讲话很重要， 代表了党中央国务院对大家的问候， 给我们指明了方向；给我们提出了更高的要求， 我们今后怎么干， 更清楚了； 曾培炎副总理不仅是给同志们的要求， 也是给各级领导的要求，这更加坚定了我们的信心， 要求我们地质工作一定要面向社会主体， 主攻方向支援国家的经济建设， 要求我们要开拓创新， 要继承、 弘扬优良
27、的传统、 作风。各级国土资源部门， 要全面落实加强地质工作决定， 以优异的成绩报效祖国。国务院副秘书长张平， 国家发展改革委员会副主任张国宝， 财政部副部长朱志刚， 商务部部长助理傅自应， 国土资源部副部长李元、 鹿心社、 鵭小苏、 汪民、 王世元， 中纪委驻国土资源部纪检组组长王寿祥， 中国地质调查局局长、 中国地质学会常务副理事长孟宪来， 国家海洋局局长孙志辉， 国家土地副总督察（ 专职） 甘藏春， 国际地质科学联合会主席张宏仁， 中国地质学会副理事长闫学义、 杜金虎、 徐水师， 中国地质学会秘书长朱立新和黄汲清青年地质科技奖基金管理委员会部分委员等参加了接见。（ 禹启仁供稿） 第 期江思珉等： 单纯形模拟退火混合算法反求水文地质参数及其并行求解地质论评 年
