引用本文
张兆龙, 王跃钢, 腾红磊, 王乐. 一种基于遗传算法和BP神经网络的选星方法[J]. 物探与化探, 2017,41(5): 946-950.
ZHANG Zhao-Long, WANG Yue-Gang, TENG Hong-Lei, WANG Le. A satellite selection algorithm based on genetic algorithm and BP neural network[J]. Geophysical and Geochemical Exploration, 2017,41(5): 946-950.
Doi:10.11720/wtyht.2017.5.23  
Permissions
Copyright©2017, 物探与化探编辑部
《物探与化探》编辑部
一种基于遗传算法和BP神经网络的选星方法
张兆龙, 王跃钢, 腾红磊, 王乐
火箭军工程大学 304教研室,陕西 西安 710025

作者简介: 张兆龙(1993-),男,汉族,甘肃兰州人,研究生,研究方向为航空重力测量中的BDS/GPS精密单点定位算法。Email:zhang-zholong910@163.com

收稿日期: 2017-01-03
基金: 国家自然科学基金项目(61304001、61304239)
摘要

在BDS/GPS组合定位中,选择空间位置最优的卫星组合是第一步,也是十分重要的一步。传统选星算法在选取最佳卫星组合过程中涉及大量的矩阵乘法和求逆运算,计算量大,定位实时性低。为解决快速选星定位问题,综合考虑定位精度和实时性要求,提出一种新的选星算法,该算法将BP神经网络和遗传算法相结合,并将几何精度因子(GDOP)作为判断定位精度高低的依据。将应用该算法得到的GDOP和运算时间与最小几何精度因子法所得对应结果进行比较,实验结果表明,该算法在大大减小了计算量的同时保证了定位精度,具有良好的实时性和可行性。

关键词: 组合定位; 选星算法; BP神经网络; 遗传算法; 几何精度因子
中图分类号:P631 文献标志码:A 文章编号:1000-8918(2017)05-0946-05
A satellite selection algorithm based on genetic algorithm and BP neural network
ZHANG Zhao-Long, WANG Yue-Gang, TENG Hong-Lei, WANG Le
304 Unit,Rocket Force University of Engineering,Xi'an 710025,China
Abstract

In BDS/GPS combination positioning, it is a very important step to select the satellite combination with the best spatial location. The traditional satellite selection algorithm involves a large number of matrix multiplication and inversion operations, so the calculation is large and the real-time is low. For the problem of rapidly fixing position, the authors, considering the positioning accuracy and real-time requirements, propose a new satellite selection algorithm, which combines the BP neural network and genetic algorithm, and uses the geometric dilution of precision (GDOP) as the basis of judging positioning accuracy. Through the comparison of GDOP and the running time acquired by this algorithm and the method of minimum geometric dilution of precision, it is found that the proposed algorithm can greatly reduce the computational complexity and ensure the positioning accuracy, thus exhibiting good real-time and feasibility.

Keyword: combination positioning; satellite selection algorithm; BP neural network; genetic algorithm; geometric dilution of precision
0 引言

随着航空重力测量技术的不断发展, 在获取更高精度的重力异常有效值的同时, 对定位精度的要求也随之提高。近几年, 随着我国的北斗卫星导航定位系统和欧洲的伽利略系统的初步建成与完善, 多系统组合定位成为了众多学者研究的热点[1]。

多系统组合定位具有可见卫星数多、定位精度高等优点, 但是可见卫星数目的增加使得定位解算的运算量加大, 影响了定位的实时性[2]。所以, 如何快速、合理地选择定位卫星, 设计良好的选星算法, 在保证定位精度的同时减小计算量, 具有十分重要的意义。目前, 针对选星问题, 主要有传统选星算法、改进后的选星算法(基于仰角和方位角法、基于高度角和GDOP贡献值法、间接选星法等), 但是传统选星算法计算量大, 不利于快速选星; 改进后的选星算法不能很好地解决定位精度和快速定位之间的矛盾[3]。

笔者针对BDS/GPS组合导航定位系统, 首先用可见星仰角进行初步选星, 选出最大仰角和最小仰角的两颗卫星, 然后利用基于BP神经网络和遗传算法结合的选星算法选出最佳定位卫星组合, 最后通过算法仿真和实验结果对比分析, 得出了笔者所提出的算法在快速定位上的有效性。

1 选星的基本准则及化简

BDS/GPS组合定位的原理与单系统定位的原理相同[4,5], 但是不同的卫星系统之间存在系统差, 从而增加了钟差变量, 所以要实现组合定位至少需要5颗卫星。增加卫星数量会使GDOP值降低, 即在一定程度上可以提高定位精度, 但是卫星数量增加的同时也增加了计算量, 降低了定位的效率。在达到所需定位精度的同时为保证定位的实时性, 笔者选取5颗卫星进行定位。组合定位系统解算方程如下:

YBDSYGPS=HBDS1BDS0BDSHGPS1GPS0GPSX, (1)

其中:YBDS、YGPS为用户到卫星的伪距残差, HBDS、HGPS为几何观测阵, X是用户状态量:

H=l1m1n1l2m2n2⋮⋮⋮lNmNnN, (2)X=[ΔxΔyΔzΔtBDSΔtGPS], (3)

其中:li、mi、ni表示观测站与各卫星连线的坐标轴的方向余弦, N表示用于解算的卫星个数, Δ x、Δ y、Δ z为三维坐标修正量, Δ tBDS和Δ tGPS分别表示北斗系统和GPS系统的钟差。

在卫星导航定位中, 一般利用GDOP值的大小表征定位精度的高低, 它反映了由于卫星空间几何位置的影响而使伪距测量误差到用户位置误差间的比例系数, 实际上是伪距测量误差的放大因子, 对定位精度有很大影响, 当测距误差一定的情况下, GDOP值越小定位精度越高[6,7,8,9]。GDOP的定义式为:

GDOP=t(ATA)-1, (4)

其中:t表示矩阵求迹, A为观测矩阵(n× 5维矩阵):

A=HBDS1BDS0BDSHGPS1GPS0GPS, (5)

从式(4)可得, 每计算一次GDOP值就要进行一次矩阵乘法和矩阵求逆, 可见星数目的增加使运算量加大, 系统实时性降低, 因此可以运用矩阵知识简化(4)式:

GDOP=t(ATA)* |ATA|=t(ATA)* )‖A‖=‖A* ‖F‖A‖6

进一步化简得:

其中:aij为观测矩阵的伴随矩阵元, n为可见星数, 文中n=5。

根据以上分析, 选择定位卫星的基本原则就是使可选卫星组合的GDOP值最小, 从而使定位精度达到最高。

2 选星算法

卫星定位精度的高低可以由GDOP的大小表征, GDOP越小, 定位精度越高。根据卫星对用户位置和地面观测站的覆盖特性可得, 顶座可见星仰角

越大GDOP值越小, 底座可见星仰角越小GDOP值越小, 所以从所有可见星中选取的最佳星座组合中一定包含仰角最大和仰角最小的那两颗卫星[10,11]。

遗传算法是一种迭代算法, 主要用于全局优化搜索, 其模拟自然遗传和选择过程中发生的繁殖、交叉以及基因突变现象, 将生物进化过程抽象地描述为选择、交叉、变异3个算子[12-14] 。因为遗传算法在每一次迭代过程中都将具有竞争力的个体保留, 这就说明遗传算法的结果总是寻求某个评价函数意义下的最优解, 所以将遗传算法用于选星, 具有鲁棒性强、可靠性好、隐含并行性高和全局优化性好等优势[15], 但是遗传算法易发生未成熟收敛问题, 并且局部搜索能力较弱, 即其可以很快地确定全局最优解存在的区域, 却不能很快地得到最优解[16]。

BP神经网络是目前最成熟也是应用最广泛的一种人工神经网络, 其基本思想是最小二乘学习算法。通常采用梯度下降法, 其学习过程是一种包括正反向两个传播阶段的修正加权系数的过程, 具体算法参见文献[17]。BP神经网络具有自适应能力强、容错性好等特点, 但是该算法在寻优过程中会产生“ 锯齿现象” , 易陷入局部最小, 全局搜索能力差[18], 不利于选取最优卫星组合。

结合遗传算法侧重于全局搜索, 局部搜索能力较差, 而BP神经网络易陷入局部最小, 全局搜索能力较差的特点, 利用遗传算法来训练BP神经网络[19], 提出基于BP神经网络和遗传算法的方法来获取最佳的可见星组合, 在保证定位精度的同时减小计算量。

具体的选星步骤为:

1) 从仰角大于5° 的所有可见星中, 选择仰角最大和最小的卫星作为第一、第二颗卫星。

2) 确定剩余可见星的编码方式。笔者采用实数编码方式, 即将GPS卫星从0~23分别编码, 将BDS卫星从24~38分别编码。

3) 计算适应度。笔者以GDOP值作为判断解的优劣的适应度函数。

4) 遗传操作。取初始种群规模M为100, 交叉概率Pc为0.9, 变异概率Pm为0.9, 截断阀值D为1, 遗传代数T为100, 经过交叉变异产生新一代群体。

5) BP神经网络训练。将遗传算法搜索到的最优局部空间作为BP神经网络训练开始样本, 由BP神经网络进行局部精确搜索, 从而输出最优解, 即最佳卫星组合。选星算法流程如图1。

图1 选星算法流程

3 算法仿真与结果分析

笔者使用Matlab编程实现选星算法, 程序中使用的数据为采集于西安某地的BDS/GPS原始数据, 双模接收机参数设置为:多普勒频率搜索区间为-10~10 000 Hz, 锁相环带宽为15 Hz, 锁频环带宽为5 Hz, 空间位置精度因子门限值为35, 信噪比门限值为35 dB/Hz。

在某一采样时段内捕获到14颗卫星, 其中北斗卫星6颗, GPS卫星8颗, 为选择最佳星座组合提供了足够的可见卫星。BDS/GPS可见卫星原始数据见表1。

表1 BDS/GPS可见卫星原始数据

根据表1可得:仰角最大的可见星是G11, 仰角最小的可见星是G13, 所以最佳卫星组合一定包括这两颗卫星。分别利用最小几何精度因子法和笔者提出的选星算法选取该时段内的最佳卫星组合, 并计算出相对应的GDOP值和算法运行时间, 具体结果见表2。

图2、3分别为最小几何精度因子法和笔者提出的选星算法在24 h内所选取的最佳卫星组合的GDOP值。

表2 某一采样时段内的选星结果对比

图2 最小几何精度因子法选星GDOP值

图3 本文提出的算法选星GDOP值

结合表2和图2、3可以看出, 笔者提出的选星算法选取的最佳卫星组合的GDOP值基本接近最小几何精度因子法选取的最佳卫星组合的GDOP值, 两者间的误差很小, 说明笔者提出的选星算法在一定程度上保证了定位精度。

最小几何精度因子法与笔者提出的选星算法在某30 min采样时间段内选取最佳卫星组合所用时间对比见图4、5, 设置数据更新频率为次/秒。

从图4、5可以看出, 笔者提出的选星算法选取最佳卫星组合所用时间小于最小几何精度因子法所用时间, 即笔者所提算法大大减小了运算量, 可以快速选择定位卫星的星座组合, 提高了定位的实时性。

图4 最小几何精度因子法选星所用时间

图5 本文提出的算法选星所用时间

4 结论

笔者针对遗传算法和BP神经网络各自的特点, 将可见星仰角和基于BP神经网络的改进型遗传算法相结合, 应用于航空重力测量中的选星定位中, 同时将选星准则(GDOP值)进行了化简。算法仿真结果表明, 提出的选星算法在保证了定位精度的同时, 减小了运算量, 在航空重力测量中具有良好的可行性和实效性。

The authors have declared that no competing interests exist.

参考文献
[1] Ma R, Ma Y L. Study on positioning algorithm for the combined galileo/GPS system[J]. J Telemetry Tracking & Command , 2009, 30(1): 7-11. [本文引用:1]
[2] 霍航宇, 张晓林. 组合卫星导航系统的快速选星方法[J]. 北京航空航天大学学报, 2015, 41(2): 273-282. [本文引用:1]
[3] 马宏阳, 程鹏飞, 李冉, 等. 一种多系统组合导航快速选星方法[J]. 测绘工程, 2016, 25(1): 59-64. [本文引用:1]
[4] Dong S H. A closed-form formula for GPS GDOP Computation[J]. GPS Solutions, 2009, 13(3): 183-190. [本文引用:1]
[5] 吴甜甜, 张云, 刘永明, 等. 北斗/GPS组合定位方法[J]. 遥感学报, 2014, 18(5): 1087-1097. [本文引用:1]
[6] 方群, 袁建平, 邓谔. 卫星定位导航基础[M]. 西安: 西北工业大学出版社, 1999. [本文引用:1]
[7] 张强, 张晓林, 李宏伟. 组合卫星接收机中的选星算法[J]. 北京航空航天大学学报, 2007, 33(12): 1424-1428. [本文引用:1]
[8] Phatak M S. Recursive method for optimum GPS satellite selection[J]. Aerospace and Electrical Systems, 2016, 37(2): 751-754. [本文引用:1]
[9] 何晓峰, 胡小平, 吴姜平. 基于MEMIMU辅助的高动态GPS选星方法设计[J]. 中国惯性技术学报, 2007, 15(6): 716-720. [本文引用:1]
[10] 张昕, 何柳, 李燕敏, 等. 一种基于高度角和GDOP贡献值的改进型选星算法[J]. 软件导刊, 2016, 15(8): 16-20. [本文引用:1]
[11] 田安红, 付承彪, 孔德剑. 一种新的基于加权行列式的选星算法[J]. 弹箭与制导学报, 2014, 34(4): 155-157. [本文引用:1]
[12] 黄继拯, 刘红, 赵艳. GPS/北斗的组合选星算法研究[J]. 舰船电子工程, 2011, 31(8): 81-83. [本文引用:1]
[13] 柯小平, 王勇, 许厚泽. 三维密度分布的遗传算法反演[J]. 大地测量与地球动力学, 2009, 29(1): 41-45. [本文引用:1]
[14] 夏传甲, 徐辉, 万晓云, 等. 基于实数编码遗传算法的GPS短基线整周模糊度搜索[J]. 大地测量与地球动力学, 2012, 32(1): 136-140. [本文引用:1]
[15] 宋丹, 许承东, 胡春运. 基于遗传算法的多星座选星方法[J]. 宇航学报, 2015, 36(3): 300-308. [本文引用:1]
[16] H Shirdel G, Abdolhosseinzadeh M. A genetic algorithm for the arrival probability in the stochasticnetworks[J]. SpringerPlus, 2016, 5(1): 1-14. [本文引用:1]
[17] 朱文龙. 基于遗传算法的BP神经网络在多目标优化中的应用研究[D]. 哈尔滨: 哈尔滨理工大学, 2009. [本文引用:1]
[18] Wen H, Xie W X, Pei J H, et al. An incremental learning algorithm for the hybrid RBF-BP network classifier[J]. Springer Journal, 2016, 32(1): 1-15. [本文引用:1]
[19] 王崇骏, 陈兆乾, 谢俊元. 一种基于遗传算法的BP神经网络算法及应用[J]. 南京大学学报: 自然科学, 2003, 39(5): 459-466. [本文引用:1]