基于人工鱼群算法的测量平差参数估计

田劲松,田劲杰

(1.安徽农业大学理学院,安徽合肥 230036； 2.杭州市拱墅区基础设施建设中心,浙江杭州 310000)

基于人工鱼群算法的测量平差参数估计

田劲松1∗,田劲杰2

(1.安徽农业大学理学院,安徽合肥 230036； 2.杭州市拱墅区基础设施建设中心,浙江杭州 310000)

介绍人工鱼群算法原理和算法设计的相关技术问题。把人工鱼群算法应用到测量平差中，解决平差过程中遇到的法方程系数阵秩亏、病态方程等问题。给出了在测量平差参数估计中利用人工鱼群算法，不对法方程求逆的情况下，

人工鱼群算法；测量平差；参数估计；目标函数；参数范围

1 引 言

在测量数据平差处理中,一个实际平差问题,都要选择建立某种函数模型,函数模型是描述观测量与未知量之间的数学关系的模型,是客观实际的本质或特征的模型,数据平差的目的就是为了最优估计函数模型的未知量[1]。经典平差中常用的函数模型有条件平差模型、间接平差模型等,这些函数模型的平差准则均为VTPV=min,在最小二乘原理要求下计算函数极值问题,共同的特点是对法方程系数进行求逆,在此过程中会遇到一些问题:

(1)若法方程系数阵不是满秩,无法解算法方程；

(2)法方程系数阵较大且条件数很大造成法方程是病态方程。间接平差时要选取参数的近似值,但近似值选取要与真值很接近才能利用最小二乘原理直接取泰勒展开式中的一次项并改换成线性模型[2]。

本文通过研究人工鱼群算法,求解测量平差中的参数。人工鱼群算法属于求解非线性最小二乘问题算法中的搜索算法[3]。与遗传算法、蚁群算法等算法类似,关键问题是如何确定有效的参数搜索范围。人工鱼群算法具有强鲁棒性、全局收敛性好的特点,在寻优的过程中跟踪记录个体的状态,进行分布处理,参数和初值具有很强的鲁棒性。把人工鱼群算法应用到测量平差中,解决平差过程中遇到的法方程系数阵秩亏、病态方程等问题。直接利用目标函数寻优法求解误差方程参数,从而避免了法方程系数求逆,使秩亏方程和病态方程问题的求解有了最优结果。通过实例模拟计算并与其他方法比较,证明该方法在最小二乘平差计算中是可行的和有效的,克服了线性化经典平差的不足。

2 人工鱼群算法简述

2.1 算法原理[3～5]

假设一条虚拟的人工鱼实体当前的位置为X,它的感知范围为Visual,在某时刻视点所在位置为Xv,如果该位置的食物浓度高于当前位置,则考虑向该位置方向前进一步,即达到位置Xnext；如果位置Xv不比当前位置食物浓度更高,则继续巡视视野内的其他位置。巡视的次数越多,则对视野中的状态了解的越全面,从而对周围的环境有一个全方位立体的认识,有助于做出相应的判断和决策。对于状态多和无限状态的环境也不必全部遍历,允许一定的不确定性对于摆脱局部最优,从而对寻找全局最优有帮助。

假设位置X=(x1,x2,…,xn),位置Xv=(xv1,xv2,…,xvn),则鱼群寻优过程可表示为:

式中:i=1,2,…,n,r是[-1,1]区间的随机数；Step是移动步长；Visual是人工鱼感知范围或距离。

由于环境中同伴的数目是有限的,因此在视野中感知同伴的位置,并相应调整自身位置。动物学家研究发现,鱼类通常具有以下几种行为:聚群行为、追尾行为和随机行为。鱼群算法是利用目标函数来区别个体的好坏,使用目标问题的函数值,对搜索空间有一定的适应能力[5]。

算法的实现涉及10个主要变量和参数:人工鱼数N,人工鱼个体的状态位置Xi,人工鱼当前所在位置的食物浓度目标函数Yi,个体之间的距离dij,感知距离Visual,人工鱼移动最大步长Step,拥挤度因子δ,觅食最大试探次数try_number,当前觅食行为次数n和最大迭代数MAXGEN。

2.2 算法设计

(1)鱼群初始化设计

开始设定鱼群的数目为N个,目标函数中有t个待优化参数,则要产生t行N列的初始鱼群,每列表示一条人工鱼的t个参数。本文设计人工鱼数为N= 100,最大迭代次数为MAXGEN=200。

(2)觅食行为设计

设人工鱼当前位置状态为Xi,在其感知范围内随机选择一个状态Xj,如果Xi〉Xj,则向该方向前进一步；反之,则重新选择状态Xj,判断是否满足前进条件。这样反复尝试设定的最大试探次数后,如果仍不满足前进条件,则随机移动一步。本文设定最大觅食试探次数try_number=100,移动步长为Step=0.3。

(3)聚群行为设计

设人工鱼当前位置状态为Xi,探索当前领域内(即dij〈Visual)的伙伴数目nf及中心位置Xc,如果Yc/nf〉δ×Yi(δ为拥挤度因子),表明伙伴中心有较多的食物并且不太拥挤,则朝伙伴中心的位置方向前进一步；否则执行觅食行为。本文设计拥挤度因子δ为0.618。

(4)追尾行为设计

设人工鱼当前位置状态为Xi,探索当前领域内(即dij〈Visual)的伙伴数目nf及伙伴中食物浓度Yi最大的伙伴Xj,如果Yj/nf〉δYi(δ为拥挤度因子),表明伙伴Xj的状态具有较高的食物浓度并且周围不太拥挤,则朝着伙伴Xj的方向前进一步,否则执行觅食行为。

(5)随机行为设计

在视野中随机选择一个状态,然后该方向移动,它是觅食行为的一个缺省行为,即人工鱼当前位置状态为Xi的下一个位置Xinext为:Xinext=Xi+r×Visual。其中, r是[-10,10]区间的随机数；Visual为感知距离。

3 测量平差参数估计

3.1 函数模型与目标函数设计

通过人工鱼最终的分布情况确定最优解的分布,随着寻优过程的进展,人工鱼会聚集到极值点的周围,全局最优的极值点周围通常能聚集较多的人工鱼[6,7],现把这种思想应用到测量平差参数估计中。根据文献[1],一般情况下,测量平差模型中观测值真值与参数真值之间的关系为:

L=f(X1,X2,…,Xn)=BX+d(3)

式中:f(X1,X2,…,Xn)是由n个Xi的非线性函数组成的n×1维向量,L为观测值真值。

一般而言,误差方程组的一般形式为:

方程组中共有t个变量,n个误差方程,其中＾x1,＾x2,…,＾xt是待估计的未知系统变量。

用矩阵形式表示为:

解方程组,得到法方程为:

式中:Nbb=BTPB,We=BTPW。

在Nbb满秩的情况下,＾x有唯一解,得到待定参数解为:

将＾x代入到误差方程中,即可求得改正数V,从而求得平差结果。但是,在很多情况下,Nbb不是满秩的或者Nbb的条件数很大,是一个病态方程,无法对法方程系数Nbb求逆。本文利用人工鱼群算法,在不对法方程Nbb求逆的情况下,对误差方程直接进行寻优求解。

3.2 相关符号定义

根据误差方程一般形式,定义相关符号如下:

4 算例分析

(1)算例1(注:为了进行比较,该算例来源于文献[8])。已知一个水准网,如图1所示,测得每段高差为:h1=0.023 m,h2=1.114 m,h3=1.142 m,h4= 0.079 m,h5=0.099 m,h6=1.217 m。根据路线长度得到每段的权重为:p1=2,p2=2,p3=2,p4=1,p5=1,p6=1。各点高程的近似值为:X01=100.780 m,X02= 100.099 m,X03=100.000 m,X04=101.216 m。

图1 水准网路线图

在这个算例中,因为没有已知点高程,导致法方程系数Nbb秩亏[8],无法直接计算出结果,必须要假设参数的真值才能得到最终结果,现在采用人工鱼群算法迭代寻优,无须假设参数真值,迭代过程如图2所示。

人工鱼群算法求解误差方程的结果如表1所示(感知距离Visual=2.5,移动步长Step=0.3,拥挤度因子δ=0.618,迭代次数MAXGEN=200,程序执行次数number=5,待定参数解个数=4)。

图2 迭代过程图

从图2中可以看出,采用人工鱼群算法寻找目标函数的极大值,整个寻优过程中,当迭代到60代以后,目标函数的极大值保持不变；从0到60代,曲线图比较陡。说明用本文介绍的方法在平差准则条件下,目标函数收敛速度很快,寻优过程稳定性很好。为了检验算法的稳定性,程序共运行了5次,得到5组参数估计值和目标函数值,每次计算结果如表1所示。另外,为了与其他算法计算结果进行比较,取5组参数估计值和目标函数值的平均值作为最终比较对象。

人工鱼群算法计算结果 表1

与文献[8]的计算结果比较如表2所示。

参数估计结果比较 表2

从表1和表2可以看出,在相同的起点上进行计算,本文介绍的方法计算结果与秩亏自由网平差计算结果接近,但精度明显要比秩亏自由网平差计算的精度要高,并且不用对法方程系数进行广义逆计算,计算速度更快。程序共运行5次,每次的参数估计值计算结果相差很小,目标函数值相同,说明人工鱼群算法稳定性很好

(2)算例2(注:为了进行比较,该算例来源于文献[9])设病态方程系数阵为:

共10个观测值,3个待定参数解。按间平差方法进行平差,共10个误差方程,模拟的权均为1,参数真值为X=[10.000 3.000 2.000]T,观测值Li、观测值与其近似值之差Wi如表3所示。寻优时,虽然也能迭代到比较理想的结果,但是出现寻优不稳定,目标函数的极大值变化较大的情况。

观测值与差值 表3

该方程的法方程系数的条件数为2 806,属于严重病态问题[9]。

在文献[9]中,作者分别用遗传算法、无偏最小二乘估计法、奇异值分解法和岭估计法计算出了3个待定参数的最优值。本文用人工鱼群算法对此例进行计算,迭代寻优过程如图3所示。

图3 迭代过程图

人工鱼群算法计算结果 表4

与其他方法计算结果比较如表5所示。

参数估计结果比较 表5

从表4和表5计算结果分析,人工鱼群法计算结果与真值接近,并且程序运行5次后,每次的改正值计算结果相差很小,目标函数值说明人工鱼群算法的稳定性很好,虽然遗传算法计算结果与真值差别很小,但是稳定性较差。由于法方程系数阵条件数很大,是严重的病态方程,用最小二乘法和奇异值分解法计算的结果与真值差别较大,

5 结 语

由以上讨论和两个算例的结果可以看出:

(1)算例1是利用人工鱼群算法解决测量平差模型中由于法方程系数阵秩亏时寻找出参数最优解的验证实例,算例2是利用人工鱼群算法解决由于法方程系数阵较大且条件数很大造成法方程是病态方程时寻找到参数最优解的验证实例。

(2)人工鱼群算法完全可以应用到测量平差计算中。算法直接针对测量平差中平差模型的目标函数进行优化计算,不管是线性和非线性模型均不需要进行复杂的求导计算。

(3)上述两个实例模型中,整个程序设计思路相同,仅目标函数形式不同,只需要修改对应的目标函数和参数个数,整个程序即可运行,所以人工鱼群算法具有对初值与参数搜索范围选择不敏感、鲁棒性强、收敛速度快和使用灵活等特点。

(4)人工鱼群算法属于求解非线性最小二乘问题算法中的搜索算法一类,与遗传算法、蚁群算法等算法类似,它们的关键问题如何确定有效的参数搜索范围,这限制了很多智能算法包括鱼群算法的应用。怎样选取优化方法(比如可以进行分段优化或者混合优化)、如何确定有效的参数搜索范围等问题都是后续值得研究的问题。

[1] 武汉大学测绘学院测量平差学科组.误差理论与测量平差基础[M].武汉：武汉大学出版社，2003.

[2] 王穗辉.遗传算法在非线性最小二乘平差中的应用[J].大地测量学与地球动力学，2006，26(2)：95～98.

[3] 李晓磊.一种新型的智能优化方法-人工鱼群算法[D].杭州：浙江大学，2003.

[4] 李晓磊，薛云灿，路飞等.基于人工鱼群算法的参数估计方法[J].山东大学学报·工学版，2004，34(3)：84～87.

[5] 李晓磊，路飞，田国会等.组合优化问题的人工鱼群算法应用[J].山东大学学报·工学版，2004，34(5)：64～67.

[6] 史峰，王辉，郁磊等.Matlab智能算法30个案例分析[M].北京：北京航空航天大学出版社，2011.

[7] 王冬冬，周永权.人工鱼群算法在求解非线性方程组中的应用[J].计算机应用研究，2007，24(6)：242～244.

[8] 卓力格图，詹洁晖.MATLAB软件在测量平差中的应用[J].地壳形变与地震，2000，20(3)：75～80.

[9] 曾群意，欧吉坤.用遗传算法解算病态方程[J].大地测量学与地球动力学，2003，23(8)：93～97.

[10] 屈利娜，任超，许本意等.基于免疫遗传算法解算GPS病态方程[J].海洋测绘，2011，31(5)：9～11.

[11] 张慧，彭志平，李国勇.粒子群算法在求解非线性方程组中应用[J].茂名学院学报，2008，18(3)：74～79.

宁波市测绘设计研究院中标海洋灾害风险及污染调查项目

(本刊讯)2013年11月13日,宁波市测绘设计研究院中标宁波市海洋与渔业执法支队海洋灾害风险及污染调查项目。

该项目调查范围位于宁波市北仑区。区内的宁波——舟山港已经发展成为国内沿海最大的液体化工储运基地,一批化学原料、化学制品制造企业及原油加工、仓储(含天然气)及石油制品制造企业纷纷落户宁波沿海,加之风暴潮、海啸、灾害性海浪等海洋灾害,给宁波海洋环境污染风险和防灾带来了很大压力。为此,宁波市海洋与渔业执法支队决定通过招标,进行陆源入海排污口普查,污染源监测等工作,收集相关数据资料进行对比分析,建设专题管理地理信息系统,掌握污染物来源及分布状况,掌握历年海洋灾害情况,依法开展海洋环境治理和保护。

该院中标后将发挥由本院建设与维护的“宁波市现代测绘基准体系”技术优势,实施调查区域的相关基础地理信息数据采集,并将海堤资料、业务资料、电子地图等图像数据汇集入库。建立地理信息管理平台,进行数据库的日常入库分析、维护和更新。应用三维仿真技术,建立基于风暴潮经验预报模型和风暴潮数值预报模型,实现对风暴潮、海啸的数值模拟,同时结合天文潮位数据和长周期海浪等数据,建立起风暴潮、海啸漫滩预报模型,满足北仑区流域对海洋灾害的风险评估和区划。

(宁波市测绘设计研究院顾开建供稿)

Adjustment Parameter Estimation Based on Artificial Fish-Swarm Algorithm

Tian Jinsong1,Tian Jinjie2
(1.Anhui Agricultural University,School of Science,Hefei 230036,China；2.Gongshu District Infrastructure Construction Center of Hangzhou city,Hangzhou 310000,China)

The relevant technology of the artificial fish algorithm principle and algorithm design problems are introduced in the paper.The artificial fish algorithm is applied to the measurement adjustment to solve encountered in the process of adjustment of normal equation coefficientmatrix rank,morbid equations and so on.The thought and steps of the error equation directly solving are given in measurement adjustment parameter estimation using artificial fish algorithm,wrongmethod equation under the condition of inversion,optimization was carried out on the error equation directly solving.Through the example simulation,proved that the method in the measurement adjustment calculation is feasible and effective.

artificial fish-swarm algorithm；measuring adjustment；parameter estimation；objective function；range of parameters

1672-8262(2013)06-134-05

P207

A

2013—06—17

田劲松(1975—),男,硕士,讲师,研究方向:智能算法与大地测量数据处理。

2013年度安徽高校省级自然科学研究项目(KJ2013Z082)；安徽农业大学2012年教学研究项目(JY2012064)。

对误差方程直接进行寻优求解的思想和步骤。通过实例模拟计算，证明该方法在测量平差计算中是可行的和有效的。