Optimal celestial positioning constellation combination based on genetic algorithm
-
摘要: 基于遗传算法, 引用GPS定位中的几何精度降低率理论, 建立了最优定位星座组合选择模型, 编制了计算软件, 以三星、四星天文定位为例, 从侯选定位星体中选择出最佳的星座组合。应用结果表明, 应用遗传算法进行最佳星座组合改变了传统的天文定位选星模式, 真正实现天文导航自动化。Abstract: Based on genetic algorithm, and using the definition of celestial positioning constellation GDOP (geometrical dilution of precision), the paper developed the optimal celestial positioning constellation combination model and its software. The results show that the model can select optimal stars combination, change the tradition celestial positioning constellation selection way, realize automatic celestial positioning.
-
Key words:
- celestial positioning /
- GDOP /
- optimal combination /
- genetic algorithm
-
0. 引言
0.1 传统天文定位星座选择
天文导航是一门古老的学科, 随着无线电导航技术的发展, 特别是GPS全球定位系统的出现, 由于计算的繁琐, 以及受气候条件的影响, 天文导航的地位有所下降。但是天文导航仍然有其他导航方法无法比拟的优点, 它的独立性、隐蔽性和仪器在一定使用条件下(当运载体高度大于20 km时) 的简单可靠, 使得天文导航仍然为各国航海人员所重视。特别是计算机技术的不断发展, 天文导航计算繁琐、实时性差的缺点也得到了根本的改变, 从而使天文导航焕发出新的生命力。计算机技术应用于天文航海, 可以实现观测数据记录、定位计算、时间换算的自动化, 解决了星历的自动计算, 使整个天文定位的方法向自动化的方向转变, 从而加快定位过程, 提高定位精度。
一般2颗星就可以进行天文定位, 为了提高精度, 通常选用3颗星, 甚至4颗星进行定位。考虑偶然误差和系统误差的影响, 观测天体的高度要求大于10°, 小于70°。两星定位时, 2个天体的方位差应在30°~150°之间, 以60°~70°为最佳; 三星定位时方位夹角互差120°最有利[1]。这些标准可以用来指导选星的工作, 但它并没给出一个衡量星座分布定位精度好坏的定量标准, 这种标准对计算机实现自动选星是非常有利的。
GPS采用了GDOP (Geometrical Dilution of Precision) 几何精度降低率来作选星的标准, GDOP的大小代表定位精度的好坏。原则上GDOP的值越小, 定位的精度越高。小于6适于用来定位, 大于10则是不可取的。GPS利用4颗卫星的距离测量来得到观测者的确切位置, 衡量所得到定位结果可信度的高低, 或者当天空中可以看到5颗以上卫星时, 比较不同4颗卫星分布的定位精度, 都需要有一个确切的标准。GPS接收机自带一个GDOP的计算程序用以判断定位的最佳卫星组合[2]。
通常都能同时看到多颗可用于定位的航用星体, 在天文定位中同样存在选星的问题, 传统的天文定位应用星球仪手工进行星体的选择, 并根据经验来确定最好的定位星体组合。为了自动选星的实现, 对星体的选取同样需要一个判断的标准。在此引入GDOP的定义, 以GDOP值作为最佳星座的定量判断标准, 实现最佳天文定位星体组合的选择。
0.2 应用遗传算法进行选星
在天文定位中根据观测者所在的地理位置和观测天体的时间, 就能够计算出观测者所能见到的全部星体, 再利用选星原则[1, 3]: 观测天体的高度要求大于10°, 小于70°, 星体的星等在二等星以上, 由计算机自动产生侯选星体, 从而最佳天文定位星座组合研究问题即转化为计算侯选星体中的不同组合的GDOP值(GDOP值越小越好), 即为组合最优化问题。每一个组合最优化问题都可以通过枚举的方法求得最优解。枚举是以时间为代价得, 有的枚举时间可以接受, 有的则不可能接受。
遗传算法使用群体搜索技术, 通过对当前群体施加选择、交叉、变异等一系列遗传操作, 从而产生出新一代的群体, 并逐渐使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受, 并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到广泛的应用。遗传算法是一类具有较强鲁棒性的优化算法, 特别是对于一些大型、复杂非线性系统, 更能表现出比其他传统优化方法更加独特和优越的性能。隐含并行性和全局搜索特性是遗传算法的两大显著特征[4~6]。
1. 最佳定位星座选择算法
基于遗传算法的最佳定位星座组合算法模型可以描述如下: 假设存在n个可观测星体, 根据定位所需的星体数(三星定位或四星定位), 选择3个或4个星体作为一个组合, 使得最佳组合的GDOP值最小。
1.1 染色体编码方法
在遗传算法的运行过程中, 它不对所求解问题的实际决策变量直接进行操作, 而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算。在遗传算法中如何描述问题的可行解, 即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。由于该模型由多个参数组成, 因此采用多参数级联编码方法。其基本思想是把每个参数先进行二进制编码得到子串, 再将这些子串连成一个完整的染色体。
1.1.1 确定子串长度及子串编码
天文定位中为了提高观测星求舰位的准确性, 应按下列条件进行选星: 选择明亮的行星和一等星; 选择高度在10°~70°之间的星体, 尽量不选择高度小于10°或大于70°的星体, 因此在某一特定的观测时间可供选择的观测星体约16个。由于各子串采取二进制编码, 因此子串长度为4, 例如选择1号星体, 则子串编码为0001;15号星体为1111。
1.1.2 确定染色体长度及编码
根据三星或四星定位方式, 采取三参数或四参数级联编码, 因此在三星或四星定位时, 各染色体长度分别为12位及16位。例如: 选择2号、10号、14号星体三星定位组合, 染色体编码为
00102号 101010号 111014号
而四星定位组合为
00102号 101010号 111014号 01117号
1.2 初始群体产生
遗传算法是对群体进行的进化操作, 需要给其准备一些表示起始搜索点的初始群体数据。当M取值较小时, 可提高遗传算法的运算速度, 但却降低了群体的多样性, 有可能会引起遗传算法的早熟现象; 当M取值较大时, 又会使得遗传算法的运行效率降低。经仿真试验决定取群体规模为80, 即群体由80个个体组成, 每个个体可通过随机方法产生。
1.3 适应度计算
遗传算法中也使用适应度度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率较大; 而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数(Fitness Function)。
1.3.1 GDOP理论[2]
GDOP几何精度降低率, 在GPS卫星定位中被用来当作衡量卫星分布对测定精度影响程度的标准。GPS利用4颗卫星的距离测量来得到观测者的确切位置, 衡量他们所得到定位结果可信度的高低; 或者当天空中可以看到5颗以上卫星时, 比较不同4颗卫星分布的定位精度, 都可应用GDOP值来进行评价和选择。GPS接收机自带一个GDOP的计算程序判断定位的最佳卫星组合。
1.3.2 GDOP在天文定位中的应用
在天文定位中同样存在选择星体组合的问题, 通常都能同时看到多颗可用于定位的航用星体, 对星体的选取同样需要一个判断的标准。在应用遗传算法选择最佳星体组合时, 将GDOP的计算函数作为适应度计算函数, 在天文定位中计算GDOP的流程如下。
(1) 从天文年历或计算机选星程序中获得参与计算的一组星体的赤经和赤纬。
(2) 经过2次坐标旋转得到观测者直角坐标系的坐标值。
(3) 由观测者直角坐标系坐标得到该星体的方向余弦, 即该星体与观测者直角坐标系3个坐标轴交角的余弦(cosα, cosβ, cosγ)。有了3颗星的方向余弦就得到了方位余弦矩阵Qq
Qq=(cosα1cosβ1cosγ1cosα2cosβ2cosγ2cosα3cosβ3cosγ3)
然后就可以由Qq计算GDOP的值为
GGDΟΡ=√Τr(QΤqQq)-1
1.4 选择和交叉变异算子[7,8]
1.4.1 选择算子
遗传算法使用选择算子对群体中的个体进行优胜劣汰操作: 适应度较高的个体被遗传到下一代群体中的概率较大; 适应度较低的个体被遗传到下一代群体中的概率较小。根据所需研究的问题, 采用的选择机制为比例选择机制。比例选择方法是一种回放式随机采样的方法, 其基本思想是: 各个个体被选中的概率与其适应度大小成正比。设群体大小为M, 个体i的适应度为Fi, 则个体i被选中的概率Pis为
Ρis=Fi/Μ∑i=1Fi
1.4.2 交叉变异算子
交叉算子采用单点交叉策略, 是指在个体编码串中只随机设置一个交叉点, 然后在该点相互交换2个配对个体的部分染色体。
单点交叉的重要特点是: 若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度, 则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。变异算子采用简单的位点变异方式。
2. 仿真举例
(1) 2003年7月7日, 观测者的地理经度为120°E, 纬度30°N, 观测时间为20:00, 仿真程序界面见图 1, 根据观测者经纬度、日期编程自动计算侯选星体。
(2) 参与遗传算法选择星体组合的星体为15颗, 见表 1, 星体高度在10°与70°之间。
表 1 参与遗传算法选择星体组合的星体Table 1. Stars of selecting star programe序号 星名 赤经/ (°) 赤纬/ (°) 0 木星 6.000 89.357 1 火星 12.000 0.000 2 北极星 2.575 89.274 3 狮子α 10.142 11.953 4 大熊α 11.065 61.738 5 室女α 13.423 -11.179 6 大熊η 13.795 49.301 7 半人马α 14.115 -36.389 8 天蝎α 16.494 -26.441 9 天蝎λ 17.564 -37.108 10 天龙γ 17.945 51.489 11 天琴α 18.618 38.786 12 人马σ 18.925 -26.293 13 天鹰α 19.849 8.876 14 天鹅α 20.693 45.290 (3) 以三星组合为例: 选择结果: 初始群体为80, 交叉概率为0.68, 变异概率为0.001。
经过仿真计算结果表明: 在所侯选的星体中, 天蝎座λ星、天龙座γ星和火星的组合为最佳。
3. 结语
本文在分析遗传算法的基础上, 阐述针对天文定位中应用遗传算法的几个关键问题, 并成功地将GPS定位理论中的GDOP计算模型作为遗传算法中的适应度函数。通过仿真实验, 证明基于遗传算法的天文定位最佳星体组合的选择是可行的。
(1) 改变了以往选星手工作业的模式, 能做到根据观测者的经纬度、时间及相关要素, 自动计算星空, 并根据选星原则, 自动生成侯选星体, 并应用本文的方法找到最佳星体组合。
(2) 能将现代优化计算方法引入古老的天文导航中, 这必将推动现代优化计算方法在天文导航定位中的应用。
(3) 本方法的研究为最佳星体组合自动跟踪技术奠定了理论基础, 从而实现真正意义上的天文定位、导航自动化。
-
表 1 参与遗传算法选择星体组合的星体
Table 1. Stars of selecting star programe
序号 星名 赤经/ (°) 赤纬/ (°) 0 木星 6.000 89.357 1 火星 12.000 0.000 2 北极星 2.575 89.274 3 狮子α 10.142 11.953 4 大熊α 11.065 61.738 5 室女α 13.423 -11.179 6 大熊η 13.795 49.301 7 半人马α 14.115 -36.389 8 天蝎α 16.494 -26.441 9 天蝎λ 17.564 -37.108 10 天龙γ 17.945 51.489 11 天琴α 18.618 38.786 12 人马σ 18.925 -26.293 13 天鹰α 19.849 8.876 14 天鹅α 20.693 45.290 -
[1] 王海亭. 天文航海[M]. 北京: 海潮出版社, 1998. [2] 赵洪涛, 许国昌. GPS应用程序设计[M]. 北京: 科学出版社, 2000. [3] 高善民, 张志新. 船舶定位与航法计算原理[M]. 北京: 海潮出版社, 1993. [4] 刑文训, 谢金星. 现代优化计算方法[M]. 北京: 清华大学出版社, 2000. [5] 张文修, 梁怡. 遗传算法的数学基础[M]. 西安: 西安交通大学出版社, 2003. [6] 李敏强, 寇纪凇, 林丹, 等. 遗传算法的基本理论与应用[M]. 北京: 科学出版社, 2003. [7] 陈国良, 王煦法, 庄镇泉, 等. 遗传算法及其应用[M]. 北京: 人民邮电出版社, 1999. [8] 周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版社, 1999. -