非线性模型参数估计的大洪水算法.doc

滨江学院 毕业论文题 目 非线性模型参数估计的大洪水算法院 系 大气与遥感系 专 业 测绘工程 学生姓名 刘少东 学 号 20092350012 指导教师 王永弟 职 称 讲师 二一三年 五月二十日- 10 -目录引言- 1 -2 非线性模型参数估计- 1 -3 基本大洪水算法- 2 -4 大洪水算法改进- 3 -5 大洪水算法的应用实例- 4 -6 结束语- 6 -参考文献- 7 -致谢- 8 -Abstract- 9 -非线性模型参数估计的大洪水算法刘少东南京信息工程大学滨江学院测绘工程专业，南京 210044摘要：经过两百多年的发展，线性模型参数估计理论已经非常成熟，成果丰硕。但现实中的实际模型往往并非线性模型，而是非线性模型。用线性模型来解算非线性模型，常常会带来很多问题，得出结论会与现实有较大差距。因此，现实中非线性模型该用非线性科学的方法解算。用大洪水直接搜索算法解算非线性模型，无需求导，适用范围广，具有较为理想的全局寻优效果，以及较好的计算精度及较高的效率。关键字：非线性模型，参数估计，最小二乘法，大洪水算法引言参数估计是数理统计中的一个名词，其含义是根据含有误差的观测向量，依据一定的数学模型和准则求解未知数，就是实际测量中的平差问题。通常情况下，包括测量工作中，非线性模型的出现要比线性模型频繁得多，因而，非线性模型参数估计的使用也频繁的多。1993年，Gunter Dueck最早提出了大洪水算法，那是一种受自然界启发，通过模拟洪水上涨的过程来进行全局优化的算法。Dueck在对阈值接收算法(Threshold Accepting)进行研究的过程中，又发现了大洪水算法（Great Deluge Algorithm）和记录更新法（Record-to-Record Travel)这两种行之有效的启发式算法。大洪水算法与爬上算法（The hill-climbing algorithm）、模拟退火算法（The simulated annealing algorithm）颇为相似。用个形象的比喻来说，洪水不断上涨，淹没大地高山，某人不断向上攀登，他能任意移动。他必须不断找到更高处以求躲避洪水生存下去，他最终会到达最高点，即得到最优解。大洪水算法有着简单的结构，较强的操作性，是一种新兴的启发性寻优算法，非线性模型也在现实生产生活中被更加广泛的应用，文章将研究大洪水算法在解算非线性问题中，是否依旧适用高效。2 非线性模型参数估计参数估计(Parameter Estimation)是一种基本的统计推断形式，也是数理统计学的一个重要分支，更是测量数据处理(Surveying Data Processing)理论的重要组成部分。由于迄今为止，参数估计的一系列成果主要集中在线性模型(Line Model),线性模型参数估计理论是非线性模型(Nonlinear Model)参数估计的基础1。线性模型是数理统计学中发展比较早的分支之一2，关于它的参数估计问题，可以追溯到18世纪，发展至今已十分完善。从二十世纪60年代，数理统计中对非线性参数估计的研究才开始进行。但初期并没有取得很好的研究成果。1980年，两个加拿大的统计学家Bates和Watts在非线性模型中加入了曲率度量，这时，对于非线性模型的研究才取得了较大的进步3。测量学上对非线性模型参数估计的深入研究始于上个世纪80年代后期。1985年之后，国际著名大地测量学家P.J.G.Teunissen在非线性模型参数估计领域做出了效果显著的研究。他先后研究了非线性模型的最小二乘估计一、二阶矩。阐明了关于度量非线性强度的指标、非线性模型的识别以及非线性模型曲率的几何意义等等。他又经过反复试验，通过研究非线性模型展开式中舍去项造成的函数模型偏差，提出从舍去项中来发现了其对函数模型和参数的影响，然后又对参数估计的估值和函数模型进行改良修正。之后，测量学者Blaha对非线性最小二乘的无迭代求解理论4进行了较为系统地研究 。学者Lohse系统地研究了非线性模型的参数估计理论。Athanasios Dermanis和Fernando Sanso研究了可容许和不可容许的非线性估计原理，提出了非线性估计的贝叶斯方法5。测绘领域也非常的重视非线性科学。1994年，在由国家自然科学基金委员会调整的关于自然科学学科发展战略的调查报告大地测量学（国家自然科学基金委员会，1994）6中，明确提出：非线性模型参数估计理论是研究测量学的重要方法，是今后研究大地测量学科的重大基础理论问题之一。这是由于学者在对非线性模型使用传统的线性化解算方法中发现，很多理论在非线性模型中可用，但在非线性模型中并不适用；很多结论在线性模型中成立，但在非线性模型中却不一定能成立；一些优良的统计性质在线性模型中存在，但在非线性模型中不一定存在。比如说，在求解线性模型参数估计问题中，随机误差满足正态分布时，未知参数X的最小二乘估计Xls 具有一致无偏性和方差最小性，但如果在求解非线性模型参数估计的问题中，即便是随机误差严格满足了正太分布，未知参数X的非线性最小二乘估计XNLS 也是有偏的。其方差一般都不能达到CR下界。其实我们很难再现实生产生活中见到严格的线性模型，更多的是非线性模型。随着近代统计学和科学技术飞速的发展，统计学家面前出现的是越来越多的，不能简单化为线性模型的非线性模型。很多非线性模型以及其他非线性统计的问题在生物、农业、经济、工程技术等各个部门被提出来。在测量学上，大量的测量数据数学模型也是非线性模型。通常将其线性近似，在测量学上称这种做法为线性化。在过去，观测精度不高，对测量精度的要求也不高，模型误差可以忽略不计，将非线性模型线性化是一种较为可行的方法。但如今观测精度大幅提高，对测量精度的要求也随之提高，传统的线性化方法引起的模型误差已不容忽视。常用的方法有两大类：第一种需要对函数进行求导计算，该方法在函数比较复杂时会很困难，遇到不可导函数时将不再使用。第二种是无需求导直接搜索算法，该方法无需求导，适用范围广，是近年来颇受关注的方法。大洪水算法即是一种直接搜索算法，本文将结合实例研究该算法在处理测量数据上是否具优于其他算法。3 基本大洪水算法 1993年，Gunter最早提出大了洪水算法7。大洪水算法提出的灵感源于大自然，它进行全局优化的过程好比洪水上涨，淹没高山寻找山脉的最高点。在结构上，大洪水算法与另一种寻优方法模拟退火法较为相似，区别在于迭代中候选解不一样的接受规则。后来，Gunter成功地运用大洪水算法解算出了经典旅行商问题。随后，受此启发，国外一些学者相继对大洪水算法进行改进优化，广泛地研究应用，将其运用于求解复杂系统可靠性优化8,工件排序问题和课程时间表问题等NP-Hard类的问题等等，成果斐然。国内的学者对大洪水算法的研究不多，但也取得了一些不错的成就。比如，魏欣和马良成功地将大洪水算法运用在了多目标旅行商问题的求解上，盛虹平用其解算最小比率旅行商问题，也取得了较为不错的成果 9。大洪水算法的遍历过程与圣经里诺亚洪水的传说有着相似之处，其寻优思想可以描述为：假想有一群高低不平的高山群，一个救生船藏在这其中某座高山的山顶，一个有着特殊能力的攀登者正在高山群中的某位置，他能任意从高山中一处去到另外一处。假如此刻大洪水爆发上涨，洪水迅速地奔涌而来淹没山脚，向上蔓延。攀岩者必须不断地向上寻找最高点以求脱险。随着洪水上涨逐渐逼近，攀岩者最终将会找这群藏在高山最高点的救生艇，脱离大洪水的威胁10。大洪水算法不但可以解算极大函数优化问题，也能解算极小函数优化问题。当要对函数进行极小优化时，可将大洪水算法理解为大旱算法（great drought algorithm）。假设有一片海洋受到旱灾的侵袭，海水蒸发，海平面逐渐下降，某海洋生物不断地向下，寻找能让它继续生存下去海水。下面为解算极小化函数优化问题的基本大洪水算法，即大旱算法的步骤。（1） 初始化count迭代次数；it(迭代因子)；up海平面下降水位高度；产生0-1均匀分布的伪随机数，映射至X0 区间；WaterLevelf(X0)(海平面高度)；（2）对X0 进行领域搜索，得到一个新的解X； 计算对应的目标函数f（X）； 如果f（X）WaterLevel,则 X0 X WaterLevelWaterLevel-up(3) it it + 1;若itcount，转（2）输出X0 和f（X0）；大洪水算法思想非常简单，因为每轮都只允许从洪水水平面以上的点进行选代（大旱算法从水平面以下的点进行迭代），所以有着很高的解算效率。与模拟退火发等其他启发式算法相比较，大洪水算法只依赖于唯一的一个参数up，操作简单。up值决定运算速度，并且影响最终结算结果。若up值取的过大，算法运算速度会加快，但结算结果的精确性会降低；若up值取的过小，那么结算结果精度会较高，但需经过较长时间的解算。Gunter在大地测试中得出该参数还可以动态赋值，即最好的up应不超过目标值f(X)和WaterLevel差值的1%11。4 大洪水算法改进大洪水算法是一种迭代算法，依赖于领域结构。大洪水算法实施关键是怎样设计寻找下一候选解的领域函数式。针对连续优化问题，可以理解领域函数为在距离空间中通过附加扰动构造而成。下面给出对大洪水算法进行改进而成的三种不同构造策略。 （1）策略1：Logistic映射函数混沌拗动构造定义1：令Tt1,t2为Logistic映射函数产生的混沌序列，满足： （2）当u=4,0ti1时，混沌序列完全处于混沌状态。此时，优化变量X的取值范围a,b与该混沌序列T的取值范围0,1的映射公式分别为： （3） （4）策略2：圆周扰动构造定义2：对于二维连续优化问题，当前解（ x，y）的领域函数为圆周扰动构造，则满足。策略3 逻辑自映射函数混沌扰动构造定义3 令Tt1,t2为逻辑自映射函数产生的混沌序列，则满足： （5）优化变量X的取值范围a,b与该混沌序列T的取值范围-1,1的映射与逆映射公式分别为： （6） （7）策略2与策略3中主要是基于混沌优化思想的领域函数设计，也就是将优化变量映射到混沌序列的取值范围中，这样得到的混沌序列与优化变量有着相同的数目。然后选择合适的混沌模型进行迭代，迭代之后的混沌序列又逆向映射到优化变量的取值范围中。无论是策略1，策略2还是策略3，都要求预先知道优化变量的取值范围a,b 12。5 大洪水算法的应用实例 在处理解算测量数据的方法中，我们熟悉的线性观测方程的一般形式为： （8）其矩阵形式为： （9）式子中，表示的观测向量；n为观测值的个数；X表示未知参数向量；t为必要观测的个数；为的常数向量； 为的观测误差向量；B为的设计矩阵，即 （10） 比如水准测量中，当不设尺度比参数，且以待定高程为未知参数时，其观测方程就是（9）式所示的线性形式。然而，测量中更多的观测方程是非线性方程。一般的，用L表示的观测向量，用X表示的未知参数向量，用表示的观测误差向量，则非线性观测方程可写为 （11） 式中，是由n个X的非线性函数组成的的向量，（11）式就是我们所要讨论的一般非线性模型。 求（11）的最小二乘估计量，即求参数X的估值，得： （12） 由于LL是一个常量，所以（12）等价于目标函数非线性无约束最优化问题。例：已知一个非线性模型。参数，的真值为X=（5.420136187 -0.25436189），有5个真值（用参数的真值X算得）和相应的5个同精度独立观测值列于表1。表1 的真值和相应的观测值I1 2 3 4 5真值观测值4.202834 3.258924 2.527006 1.959469 1.5193944.2 3.25 2.52 1.95 1.51分别运用单纯形法，模拟退火法，大洪水算法对例题进行求解得到计算结果列于表2。表2 计算结果计算方法 真值单纯形态法模拟退火法大洪水算法5.420136187 -0.254361890 -5.427324646 -0.255898000 0.00745.423806309 -0.255871001 0.0045.422807188 -0.255678285 0.003由表2的计算结果可以看出，大洪水算法的为三种算法中最小，即与真值的距离最小。由此说明在解算此非线性方程中，大洪水算法的结果最接近真值，是三种算法中效果最好的。对比解算精度与大洪水算法想近的模拟退火算法。模拟退火法需一个内循环和一个外循环的控制，大洪水算法只有一个迭代次数t的循环控制，因而大洪水算法解算速度会快很多。理论上满足模拟退火法退火三原则（即初始温度做够高、降温速度足够慢、终止温度足够低），即初始点足够好、markov链足够长、计算时间足够长时，模拟退火法以概率1达到全局最优解。而大洪水算法的精度只依赖参数up的值，up值足够小，迭代次数t足够多，解算精度就越接近最优解。在对两算法解算进行严密控制时，两者解算进度相近。但模拟退火法需过长的解算时间，在算法控制方面，markov链长度无限，所以模拟退火法很难保证收敛到全局最优解。由此可见，大洪水算法在解算效率上由于模拟退火法。6 结束语 大洪水算法解算无需进行求导，结构简单，且只依赖于一个参数，便于理解，易于执行。具体解算过程中，可以通过人为比较选择，或事先设定一个集合，记录当前已得非劣解，然后用新得到的解与之进行比较，判断是否已经改进非劣解，再决定是否停止运算，输出结果。本文以解算非线性模型参数估计问题为例，与模拟退火法以及单纯形法想比较，体现了大洪水算法运行效率和算法性能的优越性。可见大洪水算法在非线性优化领域是一种很好的求解手段。目前，人们对大洪水算法的研究还不多，研究文献非常有限，所以将之改进并运用到更多领域，将有很大发展空间。参考文献1 王新洲，非线性模型参数估计理论与应用M.武汉大学出版社，2002.6.28-29.2 成平，陈希孺，陈桂景，参数估计M.上海科学技术出版社，1985.3 韦博成，近代非线性回归分析M.东南大学，1989.4Blaha.G.Non-iterative approach to nonlinear least-squares adjustment.Manuscript Geodaetica.1994(19),pp.199-212.5 Athanasios Dermanis and Fernando Sanso.A study of non-linear estimation, IUGG 交流论文，1995.6 国家自然科学基金委员会.大地测量学M.国防科技大学出版社，1994.7 GUNTER D. New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-record travel J. Journal of Computational Physics，1993，104( 1) : 86-92.8 RAVIV. Optimazation of Complex System Reliability by a Modified Great Deluge AlgorithmJ. Asia-Pacific Journal of Operational Research，2004，21( 4) : 487-497.9 王永弟.丁海永.非线性模型参数估计的大洪水算法j.地理信息空间，2012,1672-4623（2012）.10 盛虹平.马良.混沌大洪水算法求解函数优化问题J.计算机应用研究，2011,28(5):1626-1627.11 陈小兰.熊立华.万民.宏观进化多目标遗传算法在梯级水库调度中的应用J.水利发电学报,2009,28（3）：6-9,58.12 盛虹平，马良.大洪水算法在平面选址问题中的应用J.数学的实践与认识，2011,41（15）.致谢 随着毕业论文落下最后一个句号，四年大学里的最后一个学习任务也就要完成了。闭上眼，静静回忆，回忆学年论文的写作过往，选题、写作、修改、初稿，定稿，再到毕业论文，写作、初稿、定稿，在这半年时间里，给我帮助最大，最要感谢的人是我的导师王永弟老师。当初，我嫩头嫩脑地拿到论文题目时，一脸茫然，不知所措，无从下手，王永弟老师耐心的给我解释什么是非线性，什么是大洪水算法，大洪水算法有什么用。我仿佛迷失于草木茂密的陌生丛林中，王老师给我指出了走出去的方向。选到这样的论文题目，大概就是去学习一门新的学科，开始学习新的东西不是件容易的事情，那要把一个人从不会教到会，那人如果脑子不灵光，那就难上加难了。王永弟老师带着他的细心，耐心，决心，责任心做着这件难上加难的事。对着我乱七八糟的论文，王老师一次又一次耐心地审阅，找出问题所在，格式，内容，就连那些隐藏字里行间的错别字都一一挑出，没有责骂，没有嫌烦，总是耐心的讲解，细心的挑错，就这样一点一点地帮助我写出像样的论文，完成大学学习画面的最后一篇一块拼版。感谢王永弟老师！大学不比高中，没有班主任定下严密的条条框框去规范你该干嘛，生活学习全靠自己把握，感谢我的辅导员韩静老师，在大学这充满自由与诱惑的海洋中，规范引导我行驶在正确的航道上。在写论文这大学里最重要的学习过程中，韩老师及时的传递给我们最新的论文动态，提醒督促我们玩乐实习之余，记得写论文是不能忽视、重中之重的大事，让我们一直看清楚什么时候什么事最重要。感谢辅导员！大学中陪伴我最多的不是辅导员，不是导师，是我的同学。王永弟老师很忙，不是每时每刻都有时间帮助我解决论文问题，不能找到老师的情况下，同学会尽力的无保留帮助我，大家互相帮助，互相启发，共同进步。感谢我的同学们！出门在外，家人即便不在身边，他们却是最关心我的人，家人的关心是我前进的最大动力，我每做成的一件事都有家人全力的支持，感谢家人！大学就快结束，学生时代也即将终结，我很幸运，遇到好的老师，好的辅导员，好的同学，还有不离不弃的家人，在完成论文结束大学最后一次学习任务时，再次表达我的感谢！谢谢你们，王永弟老师，韩静老师，亲爱的同学，最爱的家人！Great Deluge Algorithm for Parameter Estimation Of Nonlinear ModelLiu Shaodong(School of Nanjing University of Information Science and Technolo