《遗传算法在平差中的应用.doc》由会员分享，可在线阅读，更多相关《遗传算法在平差中的应用.doc（6页珍藏版）》请在三一文库上搜索。
1、遗传算法在平差中的应用秦真珍，魏向辉，郭嗣琮 辽宁工程技术大学测绘与地理科学学院，辽宁阜新（123000） E-mail: qinzhen_摘要：在测量数据处理中,最小二乘原理一直是被广泛采用的平差处理方法，然而当模型病态时,虽然用最小二乘解算的结果是无偏的,但方差较大。若观测数据含有误差,参数估值与 真值就相差很大,而且估值表现出不稳定性。本文采用遗传算法对带有误差的观测值进行处 理，得到了比较好的结果，也说明了该方法的可行性。 关键词：测量数据，平差，遗传算法1. 引言测量数据的结果不可避免地存在着误差，因此，有效地处理带有误差的观测值，找出待 求量的最佳估值，成为测量平差学科的主要内容5
2、。遗传算法是一种概率搜索算法，它利用 简单的编码技术和进化繁殖机制来表现复杂的现象，进而提供了一种求解复杂系统优化问题 的通用框架。由于他不依赖问题的具体领域，不受搜索空间的限制性假设的约束，也不必要 求诸如连续性、可微性和单峰值等假设，甚至不要求一定具有目标函数的解析表达式，因此， 遗传算法应用的领域十分广泛。2. 遗传算法的基本原理遗传算法(Genetic Algorithms)是由美国密执根大学 Holland 教授在 20 世纪 60 年代末提 出的一种进化算法1。自 1985 年召开 GA 国际学术会议以来,遗传算法被越来越多的人所接 受并不断得到完善和发展,且广泛地应用于多个领域。
3、遗传算法(GA)是基于“适者生存”的一 种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程， 通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环 境”的个体，从而求得问题的最优解或满意解。其中选择、交叉和变异是遗传算法的三个主 要操作算子。具体操作步骤如下:1）编码。GA 在进行搜索之前先将解空间的数据表示成遗传空间的基因型串结构数据， 这些串结构数据的不同组合便构成了不同的点。2）初始群体的生成。随机产生几个初始串结构数据，每个串结构数据称为一个个体，N 个个体构成一个群体 GA 以这 N 个串结构数据作为初始点开始迭代。3）适应
4、性值评估检测。适应性函数表明个体或解的优劣性，问题不同，适应性函数的 定义方式也不同。4）选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为 下一代繁殖子孙。进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率 大，选择实现了达尔文的适者生存原则。5）交叉。交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个 体，新个体组合了其父辈个性的特性。交叉体现了信息交换的思想。6）变异。变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地 改变串结构中某个串的值。同生物界一样，GA 中变异发生的概率很低，通常取 0.0010.01 之间。变异
5、为新个体的产生提供了机会。- 6 -GA 是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条件的约束，其搜索过程是从问题解的一个集合开始的，而不是从单个个体开始的，具有隐含并行 搜索特性，也就大大减小了陷人局部极小值的可能。正是由于其具有以上突出的优点，遗传 算法几乎渗透到从工程到社会科学的各个领域。下面以一个简单的例子来说明遗传算法的主要内容2。 例如，利用遗传算法求二次函数最大值 maxf(x)=32x-x2,x0,32.不妨限定变量 x 仅取 032 间的整数，并将 x 用二进制数表示。这一工作在遗传算法中称做编码，即将可行解用字符串表示，它相当于遗传学中的染色体。对于
6、变量 x，随机产生几个初始值，设得到的 4 个初始种群 00101，01100，10011，11101， 其数值分别为 6，13，20，29.相应的目标函数值分别为 f(6)=156,f(13)=247,f(20)=240,f(29)=87.m = f ( x ) / 1f ( x )对于给定群体 x1，x2 xi ，称度。iink =1k，i=1，2，n.为个体 xi 的相对适应表 1 4 个个体相对适应度计算结果个体编号初始群体Xi适应度 f(xi)相对适应度 i10010161560.855201100132471.353310011202401.35141110129870.476由表
7、 1 看出，2 号个体相对适应度最高，4 号个体最低，按照“适者生存”的原则，复制2 号，删除 4 号。于是新的群体的 4 个个体为 00101，01100，01100，10011.按次序重新编 号为 1，2，3，4 号。此时，再进行交换运算，先随机确定字符串上交叉换位的位置，比如我们选择字符串左 起第三位。进行交换的个体对中每个个体对第三位以后的字符片段与其配对个体的相应字符 进行交换。如1 号：00101从第三位起交换 001002 号：01100011013 号:01100从第三位起交换 011114 号：1001110000旧群体新群体表 2 每个个体适应度和相对适应度个体编号复制后群
8、体Xi适应度 f(xi)交换对象交换后群体Xi适应度 f(xi)10010161562 号001005135201100132471 号0110114252301100132474 号0111116256410011202403 号1000017255为产生出新的个体，遗传算法还模仿基因突变，将个体字符串某位符号进行逆变(1 变为 0，0 变为 1).例如，将个体 011001 的第三位突变，则突变后的新个体为 01001.将上述的复制、交换、突变等操作不断循环执行下去，最终可逼近最优解（事实上，此列中已得到最优解 f(16)=256）。GA 是一种通用的优化算法，其编码技术和遗传操作比较简单
9、，优化不受限制性条件的 约束，其搜索过程是从问题解的一个集合开始的，而不是从单个个体开始的，具有隐含并行 搜索特性，也就大大减小了陷入局部极小值的可能。正是由于其具有以上突出的优点，遗传 算法几乎渗透到从工程到社会科学的各个领域3。3. 算列三角网（以附有参数的条件平差为列）的起算数据数据:X A =2798372.451, YA =523925.867X B =2793886.844, YB =528172.826S AB =6177.162，S AC =2307.8805 74 916 83图 1 测角网观测角值（同精度）列于表 3，选取ABD 的平差值为参数 X ，其近似值由三角函数计算
10、得 X0= 24o 3431.3 。表 3观测角值角号顶点观测角值1A35 19 16.22C1.9 47 28.83D34 53 12.0179 59 57.04A47 01 21.85E51 38 11.96D75 53 35.7180 00 01.57E51 38 11.98D61 31 30.59B66 50 19.2180 00 01.6X0B24 34 31.35+7E108 43 15.99- X0B42 15 47.96+8D137 25 06.28+ X0-5A29 00 57.8由附有参数的条件平差4知识知道：AV + B x) + W = 0（1）cn n1cu uic1
11、c1式中 V 为观测值 L 的改正数， x) 为参数近似值 X0 的改正数，即) ) o由此到法方程为：L = L + v ， X = X+ x)AQAT K + Bx) + W = 0B T K = 0即：（2） 3.000.000.000.00 0.003.000.000.351.790.00 1.090.00 ka k b 3.00 1.50 0.000.003.000.351.090.00 kc =1.60 0.000.350.355.292.653.29 kd 4.31 X 1.791.091.092.654.552.19 ke 0.07 0.000.000.003.292.190.
12、00 0.00 用遗传算法进行搜索，其中目标函数采用：nmin f ( x) = min absi vi =1 搜索变化范围为（-0.05，0.05），单位：秒。 得到结果为：K = 1.965851x) = 0.70110.20870.54661.59282.0981T ，将上述结果代入（1）式，得到改正数:V = 1.465912.584 1.0420.207 1.423 0.285 1.011 1.344 1.251T单位：秒。所得结果精度高，并且可以进行大规模的计算，避免了方差过大的弊端。4. 结束语遗传算法的全局寻优能力，是解决数值优化和组合优化等问题的可靠方法。本文在平差 处理时引
13、进了遗传算法，提高了以往用最小二乘法对平差处理的精度。计算结果表明，遗传 算法求解平差问题是可行的，本文仅一附有参数的条件平差为列进行了试验性的尝试，可以 推广到任何平差模型，同时随着计算机的发展，两个学科的结合将会越来越密切。参考文献1 王小平 曹立明。遗传算法-理论、应用与软件实现M，西安交大出版 2002。2 郭嗣琮 陈刚。科学计算方法中的软件计算方法M，东北大学出版社 2001。3 Nowostawski M,Poli R.Parallel Genetic Algorithm TaxonmyC.Proceedings of the Third International confere
14、nce on Knowledge based Intellingent Information Engineering System(KES99)Adelaide,Australia,1999。 4 靳祥胜。测量平差M,黄河水利出版社 2005。5 武汉大学测绘学院测量平差学科组编著，误差理论与测量平差基础M，武汉大学出版社 2003The using of Genetic Algorithms in the surveyingQin Zhenzhen, Wei Xianghui, Guo SicongLiaoning Technical University，Fuxin，Liaoning (
15、123000)AbstractIn the measurement data processing, the least square principle has been widely used , but when themodel is pathological, while the least-squares solution is unbiased results, and the large is variance. If observational data contains errors, the true value will be very different with the valuation, and the valuation showns instability. In this paper, using a genetic algorithm to treatment the error observed, the results have been quite good,and also shows that the method is feasible.Keywords: Date of measurement, Surveying, Genetic algorithm.作者简介：秦真珍，女，硕士研究生，主要研究方向：大地测量学与测量工程。