基于遗传算法的曲面拟合参数辨识

第34卷第8期2009年8月武汉大学学报#信息科学版

Geo matics and Informat ion Science of W uhan U niver sity V ol. 34N o. 8A ug. 2009

文章编号:1671-8860(2009) 08-0983-04文献标志码:A

基于遗传算法的曲面拟合参数辨识

谷 川

1, 2

潘国荣

1, 3

施贵刚 陈兴权

1

1

(1 同济大学测量与国土信息工程系, 上海市四平路1239号, 200092) (2 上海市政工程设计研究总院, 上海市中山北二路901号, 200092) (3 现代工程测量国家测绘局重点实验室, 上海市四平路1239号, 200030)

摘 要:从参数辨识的角度来看, 曲面拟合需要求解出坐标平移、旋转以及标准曲面方程参数。利用遗传算法在该领域的优势, 对经典简单遗传算法的缺陷进行了一系列改进。用M A T L A B 语言实现了改进算法的程序包。在雷达天线椭圆抛物面表面检测的工程实例以及一个模拟复杂曲面算例中, 分别采用文章中的改进遗传算法和简单遗传算法进行了多次运算, 对结果进行了比较。应用和比较结果表明, 遗传算法能够较好地应用于空间曲面拟合, 且本改进算法更具优势。

关键词:曲面拟合; 参数辨识; 遗传算法; 坐标转换; 椭圆抛物面; 模拟复杂曲面中图法分类号:P34; P258

在工业检测与逆向工程中, 曲面拟合是一个经常涉及到的实际问题。由于实物的形状通常有严格的数学公式描述, 通过对其表面点进行三维坐标采样, 可以拟合出实物表面在空间坐标系中的几何方程。

目前, 已有的曲面拟合方法主要有基于插值和逼近的样条拟合、基于神经网络的曲面拟[3][4]合、格网法拟合等, 这些方法在曲面拟合中具有一定的应用价值, 但是, 无法拟合出曲面方程的参数。基础的多项式曲面拟合由于精度较低, 不适用于高精度工业检测和逆向工程领域。文献[5]提出了一种出了按特征值、旋转角和平移量为参数拟合二次曲面的拟合方法, 能够拟合出曲面方程的参数, 但是只能用于二次曲面的拟合, 通用性不够好。

对于平面拟合问题, 已经得到很好的解决, 但对于复杂曲面, 即便是简单的二次曲面的最小二乘拟合的研究也相对较少, 而且已有的拟合算法存在方程求解困难、有奇异值和算法不稳定等问题[6], 因此, 需要探索采用一种新的参数辨识方法。

遗传算法(g enetic algorithm, GA) 是一种基

收稿日期:2009-05-31。

(。

[1, 2]

于种群搜索的优化算法, 其思想是随机产生初始种群, 通过选择、交叉和变异等遗传算子的共同作用使种群不断进化, 最终得到最优解, 特别适合

于解决其他学科技术无法解决或难以解决的复杂和非线性问题[8]。

习惯上, 将以上提出的遗传算法称为简单遗传算法(simple g enetic algorithm, SGA ) 。SGA 作为一种通用的自适应随机搜索算法, 还存在着早熟收敛和收敛速度慢这两个缺陷, 而且较难克服。

[7]

1 遗传算法的改进

计算适应度, 需先构造适应度函数。本文的适应度函数是基于顺序的基础, 构造方法是先将种群中所有个体按目标函数值的好坏进行排序。设参数B I (0, 1) , 定义基于顺序的适应度函数为:

eval (X c i ) =B (1-B ) i-1, i =1, 2, , , m (1) 式中, X c i 为种群个体按优劣排序后的第i 个个体; B 一般在0. 01~0. 3之间取值。

选择和交叉算子, 放弃赌轮选择, 采用基于种

984

武汉大学学报#信息科学版2009年8月

群的按个体适应度大小排序的选择算法代替赌轮选择方法。交叉率按照式(2) 进行自适应调整:

P c =

k 1max , f c \f ave

f max -f ave k 2, f

式中, f max 为群体中最大的适应度值; f ave 为每代群体的平均适应度值; f c 为要交叉的两个个体中较大的适应值。此处, 只要设定k 1、k 2(在[0, 1]取值) 的值, P c 即可进行自适应调整。

在选择出父本和母本后, 按照交叉方法(单点、多点、一致交叉) 进行n 次交叉, 产生2n 个个体, 再从这2n 个个体中选出最优的两个个体加入到新的种群中。如此, 既保留了父母的基因, 又在进化过程中保留了种群中个体的平均性能。

对于变异算子, 本文采用动态确定变异概率的方法, 具体的自适应调整的公式为:

P m =

k 3max , f \f ave

f max -f ave k 4, f

式中, f max 为群体中最大的适应度值; f ave 为每代群体的平均适应度值; f c 为要变异个体的适应度值。此处, 只要设定k 3、k 4(在[0, 1]取值) 的值, P m 即可进行自适应调整。

将初始种群和产生的子代种群放在一起, 形成新的种群, 然后计算新的种群各个体的适应度, 将适应度排在前面的m 个个体保留, 将适应度排在后面的m 个个体淘汰, 种群便得到了进化。

每进化一次便计算下个个体的目标函数值, 当相邻两次进化平均目标函数之差小于等于某一给定精度E 时, 即满足如下条件:

F (X

(t+1)

故完全可认为比例因子r =1。于是, 需要辨识的参数有3个旋转参数U X 、U Y 、U Z , 3个平移参数X 0、Y 0、Z 0以及曲面标准方程参数, 其个数由曲面标准方程本身决定。为了保证结果的惟一性和合理性, 可以允许对曲面方程标准参数作一些合理的规定。

2. 2 基于遗传算法的曲面拟合参数辨识

1) 在正交映射关系下基于最小二乘原理建立目标函数:

i=1

(2)

E

N

f

2

X c , Y c , Z =min (5)

2) 初始化种群, 一般采用正交化方式建立初始种群, 初始值在约束范围内均匀采样。旋转角R X 、R Y 、R Z 的取值范围约束为(-P , P ]内, 平移参数X 0、Y 0、Z 0以及标准曲面的表达参数的取值范围可根据经验、采样数据特点、方程参数本身特点等加以约束。根据笔者的经验, 对参数的取值范

(3)

围进行一定的约束, 对于加快进化速度、缩短寻优时间以及增加收敛到全局最优的概率具有积极的意义。

3) 设置算法中的选项, 例如最大进化代数、进化目标精度等。

4) 完成所有准备工作后, 开始进行种群进化, 直至得出最终的寻优结果。

2. 3 雷达天线曲面方程拟合的参数辨识

预先知道, 需检测的雷达天线表面为椭圆抛物面。由空间解析几何理论可知, 椭圆抛物面的标准方程为:

+=2Z P Q

性, 规定0

雷达天线表面曲面拟合的数据通过SOK -KIA NET 1200全站仪以免棱镜方式采集得到, 共采集了72个点, 坐标系为任意坐标系。全站仪采集得到的部分采样点数据如表1所示。

表1 雷达天线表面检测采样数据

T ab. 1 Sampled Data of t he Radar Antenna Surface

点点

X /m Y /m Z /m X /m Y /m Z /m 号号

17. 55011. 6206-4. 4991377. 78682. 0207-4. 084627. 59431. 6467-4. 51453837. 56441. 6525-4. 48233947. 51301. 5576-4. 52034057. 55811. 4550-4. 623741

,

7. 55481. 9292-3. 90087. 25201. 5921-4. 00227. 13451. 2830-4. 10297. 16541. 0420-4. 2749

2

2

(6)

-F(X ) [E

(t +1)

t

t

(4)

式中, PQ >0。本文为保证参数识别结果的惟一

可终止进化。式中, F(X 为第t +1次进化后

种群的平均目标函数值; F (X ) 为第t 次进化后种群的平均目标函数值。

笔者采用MAT LAB 编程语言, 实现了本文提出的改进遗传算法的程序包Im pro vedGA 。

2 曲面方程拟合参数辨识

2. 1 曲面方程拟合的几何描述

绝大多数情况下, 检测仪器坐标系统与检测对象坐标系统不是统一的, 事实上也无法直接统一, 必须对检测点坐标进行坐标转换, 使其统一到检测对象坐标系。最常用的坐标转换方法为七参数法。

第34卷第8期谷 川等:基于遗传算法的曲面拟合参数辨识

985

法以及传统SGA 算法进行了多次该曲面方程拟合的参数辨识, 并且进行了比较, 其比较结果如表2所示。

表2 参数辨识结果比较

T ab. 2 Result Compare o f Par amet er Identification

采用方法SGA Improved GA

平均遗传代数>600

平均计算时间/s >400

有无陷入

平均

局部极小RM S E/mm

有>4

无

2. 4 模拟复杂曲面拟合的参数辨识

为了证明遗传算法能用于复杂曲面的拟合参

数辨识, 又由于截至目前笔者还未接触到一般复杂曲面的工程实例, 故采用一个模拟算例。为了方便数据模拟, 采用的曲面方程形式可表示为:Z =f X , Y

采用的模拟复杂曲面的表达方程为:

z =ae

-bx 2-cy 2

(7) (8)

+d cos ex y

每一次计算求得的参数值也是均在最后数位上略有差异。本文采用改进遗传算法计算得到的参数值的平均值分别为:U X =-0. 627099rad, U Y =0. 585252rad, U Z =1. 451805rad; X 0=5. 9946m, Y 0=4. 3828m, Z 0=2. 5645m; P =0. 9776, Q =1. 2224。

采用文献[5]的方法得到的曲面拟合结果为P c =0. 9762, Q c =1. 2228, 拟合中误差为2. 6mm 。经过比较认为, 文献[5]的方法与采用遗传算法得到的拟合结果基本一致。从拟合中误差来看, 文献[5]的方法略优于简单遗传算法, 而本文改进后的遗传算法从拟合中误差的指标上来看, 略具优势。

统一到全站仪坐标系中, 采集的坐标数据和拟合得到的曲面如图1

所示。

式中, a 、b 、c 、d 、e 为参数, 且满足a 、b 、c 、d 、e >0。该模拟算例中的取值为:a =1. 5, b =0. 6, c =0. 8, d =1. 0, e =1. 5。

x 、y 的取值范围为[-2m, 2m], 采样间隔为0. 4m , 网格化后得到X 、Y 。X 、Y 均为11@11的矩阵。为了接近真实的测量采样过程, 给X 、Y 分别加入大小为0. 05m 的随机噪声。按式(8) 得出X 、Y 对应的矩阵Z 。对X 、Y 、Z 均加入0. 005m 的随机噪声。沿X 、Y 、Z 轴的旋转角分别为-P /3、+P /4、-P /6, 平移距离分别为5m 、10m 、15m , 建立模拟算例样本集, 图形如图2所示, 部分采样数据如表3所示。

由于本文采用的模拟算例为一对称图形, 为保证拟合结果的惟一性与合理性, 合理规定a 、b 、c 、d 、e >0, b

P P /2]。

图1 雷达天线表面曲面拟合结果Fig. 1 Cur ve F itting Result on the Sur face o f

a Radar A ntenna

图2 模拟复杂曲面

Fig. 2 Simulat ed Complex Sur face

表3 模拟复杂曲面采样数据

T ab. 3 Sampled Data o n Simulated Complex Surface

点号12345

X /m 3. 74933. 56502. 93222. 37791. 6799

Y /m -10. 5548-10. 5792-10. 2573-10. 0481-9. 7499

,

Z /m -15. 5876-15. 7012-15. 6083-15. 4424-15. 2471

点号6263646566

X /m 0. 83310. 85310. 89810. 91970. 8937,

Y /m -7. 7914-7. 7988-7. 9125-8. 0453-8. 0272

Z /m -15. 0839-15. 4492-15. 9471-16. 3808-16. 8722

同样地, 在同一台PC 上分别采用本文的改进遗传算法以及传统SGA 算法进行了多次该曲

面方程拟合的参数辨识, 并且进行了比较, 其比较结果如表4所示。

986

表4 参数辨识结果比较

武汉大学学报#信息科学版2009年8月

m, Z 0=15. 0007m; a =1. 501029, b =0. 602165, c =0. 799654, d =1. 000151, e =1. 498582。

拟合得出的参数值与参数理论值的比较如表5所示。

从表5的比较结果可以看出, 基于遗传算法的曲面拟合方法能够比较有效地拟合出空间复杂曲面的参数值, 且精度较高, 拟合出的参数值与理论值比较接近。可以认为, 遗传算法用于空间复杂曲面的参数拟合是行之有效的。

T ab. 4 Result Compare o f Par amet er Identification

采用方法SGA Improved GA

平均遗传代数>750

平均计算时间/s >500

有无陷入平均RM SE 局部极小

有

无

/mm >30

同样, 每一次计算求得的参数值也是均在最后数位上略有差异。本文采用改进遗传算法计算得到的参数值的平均值分别为:U X =0. 523649rad, U Y =-0. 785501rad, U Z =1. 047166rad; X 0=4. 9989m, Y 0=-10. 0008

表5 参数值拟合结果比较

T ab. 5 Co mpar ison of F itted Par amet er V alues

参数名称理论值拟合值较差参数名称理论值拟合值较差

平移参数

X 054. 9989-1. 1mm

Y 0-10-10. 0008-0. 8m m

Z 01515. 00070. 7mm

X 0. 5235990. 52364910. 3d

旋转参数

Y -0. 785398-0. 785501-21. 2d

Z 1. 0471981. 047166-6. 6d

曲面方程表达参数

a

1. 51. 5010290. 001029

b 0. 60. 6021650. 002165

c 0. 80. 799654-0. 000346

d 1. 01. 0001510. 000151

e 1. 51. 498582-0. 001418

参 考 文 献

[1] Wang W, Po ttmann H , L iu Y. F itting B -spline

Cur ves to Point Clouds by Curv ature -based Squared Distance M inimizat ion [J]. A CM T ransactions on G raphics, 2006, 25(2) :214-238

[2] Wang L Z, Zhu X X. Lo cal Interpolation Blended B -spline Surfaces and Its Conversio n to N U RBS Sur -face [J ]. Computer A ided Dr afting, D esign and M anufactur ing , 1994, 4(2) :5-17

[3] 刘成龙, 杨天宇. 基于BP 神经网络的GPS 高程拟

合方法的探讨[J].西南交通大学学报, 2007, 42(2) :148-151

[3] L iu Cheng lo ng , Yang T ianyu. Study on M ethod o f

G PS H eig ht Fit ting Based o n BP A r tificial N eural N etwo rk[J]. Journal of Southwest Jiaotong U niv er -sity, 2007, 42(2) :148-151

[4] Wu Jianhuang , L iu Weijun, W ang T ianran, et al.

A F itting A lg or ithm o f Subdivision Surface fro m N oising and Dense T riang ular M eshes[J]. Jour nal

of So ftwar e, 2007, 18(2) :442-452

[5] 王解先. 工业测量中一种二次曲面的拟合方法[J].

武汉大学学报#信息科学版, 2007, 32(1) :47-50[6] 顾步云, 周来水, 刘胜兰, 等. 逆向工程中二次曲面

拟合方法的研究[J]. 机械制造与研究, 2004, 33(1) :11-14

[7] H olland J. A daptation in N atur al and A rtif icial Sys -tems[M ].M ichg an:U niv ersit y o f M ichg an Pr ess, 1975

[8] 王福林, 王吉权, 吴昌友, 吴秋峰. 实数遗传算法的

改进研究[J]. 生物数学学报, 2006, 21(1) :153-158

[9] 黄绪明. 一类改进的遗传算法[J].长沙大学学报,

2005, 19(5) :1-4

第一作者简介:谷川, 博士, 工程师, 主要研究方向为精密工程测量、工业测量与测量数据处理。E -m ail:gu chuanhaha@163. com

(下转第991页)

第34卷第8期王 伟等:大坝统计预警模型的改进粒子群耦合方法

991

Statistical Early Warning Model for Dam Based on Improved

Particle Swarm Coupled Method

WAN G Wei 1 SH EN Zhenz hong 1

(1 College of Water Conservan cy and Hyd ropow er E ngineering, H oh ai University, 1Xikang Road, Nanjing 210098, Ch ina)

Abstract:Because the dam safety influencing indexes are complex, sometimes the results are bad when the statistical model is applied to early warning evaluation for dam. Suppose regression coeff-i cients is transformed to the linear programming question. The coefficients of mult-i statistic regres -sion can be determined by the particle swarm optimization algorithm. But w hen the PSO algorithm was applied to high dimension space optimization question, the convergence rate w ould be slow and the calculations could easily fall into local extreme points. In order to overcome these shortcomings, the PSO is improved, and a new sel-f adapting strategy is proposed. T he coupled method combines a new sel-f adapting strategy and simulated annealing algorithm, and the statistical early w arning model for dam is based on it (SA -APSOR) . A pplicatio ns in practical engineering show that this metho d can im pr ove the convergence ability of PSO, and can avoid the alg orithm falling into the local ex trem e points. H ence, the co nverg ence rate of this metho d is quick. Further -m ore, com pared w ith the traditio nal least square r eg ression, the for ecast precision of this model based o n SA -APSOR is high and its early w arning evaluation results alm ost co rre -spo nd w ith the practice operating conditio n.

Key words:PSO; SA; statistical ear ly w arning m odel for dam; LSM

About the first author:WANG Wei, Ph . D candidate, m ajors in Hydraulic structu re safety monitoring m eth ods. E -m ail:wwgi555@163. com

(上接第986页)

Parameter Identification of Surface Fitting Based on Genetic Algorithm

G U Chuan

1, 2

PA N G uor ong

1, 3

SH I Guig ang CH EN X ingquan

11

(1 Department of S urveyin g and Geo -Informatics, Tongji Un iversity, 1239S iping Road, S hang hai 200092, C hina) (2 S han ghai M un icipal E ngineering Design &Resear ch Institute, 901North Zhan gsan er Road, S hanghai 200092, China)

(3 Key Laboratory of M odern Engineering Su rveying of SBSM , 1239Siping Road, S han ghai 200030, China)

Abstract:View ing from the aspect of parameter identification, the parameter s of coo rdinate tr anslation, rotation and the standar d curv ed surface equation ar e to be estimated. Genetic algorithms hav e particular advantag es in this field. A ser ies of modifications are made aiming at several defects of the classic simple genetic algo rithms, and an im pr oved alg orithm is rea-l ized using MA TLAB. Both algor ithms are used many tim es in an engineering examples and a simulated complex surface ex ample, and the calculation results are com pared. Applications and co mparisous show that the genetic alg orithm can be w ell used in the field of spatial sur -face fitting, and the improved algor ithm is better.

Key words:surface fitting; parameter identification; g enetic alg orithm; co ordinate transfor -m ation; elliptic parabo loid; simulated complex surface

Ab ou t th e first author:G U Ch ua n, Ph . D, e ng in eer, majors in precise en gin ee ring su rvey, in du strial me asu rem en t a nd su rvey da ta processin g. E -