基于改进离散粒子群算法的选星模型

赵 猛, 张金鑫, 韩佳颖, 张鹤庆

(1.天津理工大学 海运学院， 天津 300384；2.郑州轻工业学院 电气信息工程学院， 郑州 450002)

天文导航在远洋航行中的作用举足轻重，随着无线电导航技术的发展，尤其是全球定位系统(Global Positioning System,GPS)定位技术的产生，航海事业飞速发展[1]。GPS定位由于受到声、光和电波的干扰不具有一定的独立性和隐蔽性，而天文导航最大的特点是不受其他设备和信号的干扰，但需要完成大量查表和计算工作[2]。因此,利用计算机开发天文导航系统具有划时代的意义。为有效履行《1978年海员培训、发证和值班标准国际公约》马尼拉修正案，规范海船船员培训行为，根据《中华人民共和国船员条例》《中华人民共和国船员培训管理规定》的相关规定，交通运输部编制了《海船船员培训大纲(2016版)》，大纲明确要求二、三副学员掌握航海天文历和天文航海计算软件的相关内容。这表明在未来的航海实践中，电子天文航海起着重要作用。

20世纪80年代就出现了利用天文航海技术对船舶定位进行指导。Omar Reis公司开发的Navigator软件和大连海事大学研制的DMU Celestial Navigator软件[3]，这些天文航海软件都集成了选星和认星的星图显示模块。相比较而言，传统索星卡[4]仅凭图形版面即可提供同样丰富的信息，且更直观地体现测者位置、时间和星空三者间的关系。王任大等[5]设计并实现一种用户界面与经典的TS系列索星卡高度近似的仿真型索星卡软件。施闻明等[6]在天文定位中利用模糊逻辑的方式建立选星模型。王锋等[7]等提出在天文导航中建立基于线性加权的计算机选星建模。粒子群算法(Particle Swarm Optimization, PSO)具有收敛速度快、设置参数少、容易实现及能有效地解决复杂优化问题等优势[8]。PSO被用于连续问题，随着问题的不断变化又出现了离散粒子群算法及改进的离散粒子群算法，这些算法被广泛应用于一些工程领域[9-11]，受到人们越来越多的关注。

基于上述文献的特点，本文根据建立模型的离散量运算特点，对于离散的组合优化问题，在变量有限的前提下将基于改进的离散粒子群算法引入天文航海导航方面，实现自动选取最优的一组星；同时，首次将选星的结果显示在索星卡界面上，更有助于海员观察。

1 索星卡的仿真

1.1 索星卡的概述

在先进的航海定位技术中，由于利用GPS定位，受到的外界影响较大。因此，借助索星卡选星和认星进行船体定位能避免受外界影响GPS问题，该方法在船舶航行中具有不可取代的地位。索星卡由两块星图底板和若干张透明地平坐标网片组成[12](见图1)。

1)星图底板是天球的投影图。图1a)是按极方位等距投影原理投影而成的，每一个星图底板上都印有天赤道和黄道，黄道上标有表示视太阳位置的日期。星图底板有两圈读数，内圈是赤经读数，外圈是平太阳的日期刻度，索星卡星图底板如图1a)所示。

2)透明地平坐标网片有13张，供0°～60°范围内的测者使用，每一网片标有一个纬度值，它们是0°N(S)，5°N(S)，10°N(S)，15°N(S)，…，60°N(S)等，同一张网片南、北纬通用。在透明网片的真地平圈外侧印有-6°和-12°高度线，用于确定民用和航海晨光始或昏影终的星空。图1b)为透明地平坐标网片。

1.2 运用OpenGL实现索星卡的仿真

仿真型索星卡的设计是基于MFC平台，利用OpenGL开发库函数在Microsoft Visual C++实现的，在仿真的过程中需要纹理映射、纹理融合及坐标变换。

索星卡的使用原理是将星图底板和地平坐标网片重合在一起，转动地平坐标网片到合适的位置，从而进行星的选择。本设计中地平坐标网片在RGB模式下映射成纹理图像，并覆盖到星图底板的纹理上，利用OpenGL的库函数将两个纹理融合在一起，不遮挡底板上的信息。但由于屏幕的局限性，不能既清晰又完整地将索星卡展现在海员面前，所以需要对其进行坐标变换，通过对鼠标和键盘的操作，可以清晰看到索星卡上详细的内容，达到更好的视觉效果。仿真型索星卡运行效果图见图2。

2 建立选星模型

2.1 建立数据库

模型计算需要有后台数据支持。因此，本设计依据2016年TheNauticalAlmanac中的信息，利用MySQL建立star数据库。在star数据库中依据恒星视位置列表中的星等、恒星名称、共轭赤经、赤纬和日期建立stars列表，其中为159颗恒星设置了ID并把其作为主键。同时，根据不同时间的春分点格林时角时间建立time列表。具体如下:

1)以一月为例，利用MYSQL数据库管理工具(Navicat for MySQL)，将恒星视位置列表中的详细信息导入stars列表中。

2)将不同时刻的春分点格林时角导入到time列表中。

3)利用MATLAB平台连接MySQL调用数据库中数据，即可计算出每个时期恒星高度和方位。

2.2 基于改进离散粒子群的选星模型

CLERC[13]指出建立离散粒子群算法的关键是为问题域定义和粒子的静态和动态行为的描述，根据粒子群[14]的基本思想构建离散粒子群求解离散优化问题。钟一文等[15]依据优化问题及离散量的特点对粒子的速度和运算进行重新的定义，并对粒子的运动方程进行修改，建立改进的离散粒子群算法。本文依据钟一文提出的改进离散粒子群算法，对选星问题进行优化求解。这种算法求解充分考虑了离散型组合优化的特点，利用这种算法既减少了冗余量，又提高了搜索效率。

2.2.1建立选星数学模型

为提高船舶定位的准确性，在选星时应遵循以下规则：

1)选择足够亮的星。

2)星体的高度要适中，星体高度一般选择在20°～70°。

3)观测两星定位时，方位夹角应接近90°；观测三星定位时，三星方位分布应大于180°，相邻两星体的方位夹角趋近120°为最好。

即在选星过程中要根据星等、高度和方位来确定，通过欧拉三角形公式可计算得到天体的高度和方位有

sinhc=sinφsinDec+cosφcosDeccosLHA

(1)

cosAc=cosφtanDeccscLHA-sinφcotLHA

(2)

式(1)和式(2)中:hc为天体高度;Ac为天体方位;φ为纬度;Dec为天体赤纬;LHA为天体地方时角。

minF=F1+F2+F3

(3)

F1=∑a1x(i),i=1,4,7

(4)

F2=∑a2|x(j)-45°|,j=2,5,8

(5)

(6)

式(4)～式(6)中:a1、a2、a3为在选星过程中采用的经验权重值[7];F1、F2、F3分别为a1倍的3颗星的星等之和，a2倍的3颗星的高度之和，a3倍的3颗星的方位之和；x(i)为每行3颗星的星等；|x(j)-45°|为每组星的星体距离最优高度的距离；|(x(a)-x(b))-120°|、|(x(c)-x(a))-120°|、|(x(c)-x(b))-120°|为每组星中相邻两星的方位夹角与最优夹角120°的差距。

依据选星的要求对星体高度的范围和三星分布的范围分别进行约束，设置约束条件：每组星中星体高度的范围都在20°～70°；每组星的星体分布应大于180°。

1) 20°≤x(j)≤70°,j=2,5,8；

|x(a)-x(c)|>180°&|x(b)-x(c)|≤180°

|x(b)-x(c)|>180°,a=3,b=6,c=9

2.2.2基于改进的离散粒子群算法求解

1)根据2.2.1节的约束条件对A矩阵中的每一行进行筛选，保留符合条件的行，即可组成新的矩阵A1∈Rm×9。在矩阵A1的9维的搜索空间中，随机选取P行，即种群的规模为P。初始化粒子的位置为：X[x11,x12,…,x19,x21,x22,…,x29,…,xP1,xP2,…,xP9]，同时粒子的速度V为一个9维的随机向量；其中X中的每一个位置代表一个可行解；粒子的速度V是用来改变粒子的位置。

2)根据2.2.1节中建立的数学模型作为目标函数，求出每个粒子的适应值pbestvalue和全局极值fitnessbest。

3)依据钟一文等[15]提出的改进离散粒子群算法对粒子的位置和速度进行更新。

4)比较每个粒子的适应值和个体极值，适应值和全局极值，寻找当前最优的个体极值和适应值。

5)如果当前的迭代次数达到预计最大的迭代次数M，算法结束。

通过M次寻优计算，即可得到数学模型(目标函数)的最小值并记录此时粒子的位置，粒子的位置是包含星等、高度和方位的一组数据；最后根据这些元素从数据库中找到3颗恒星的星名。

3 仿真进行选星验证

3.1 参数设定

该算法是从N=159颗恒星中选取三星进行船舶定位；基于改进的离散粒子群算法求解选星模型，种群在9维空间中搜索，解的初始值选择为随机性，即从A1矩阵中随机选取P行。粒子的种群规模P的设定：较小的种群能充分探索解的空间，避免了过多的适应值评估和计算时间，一般情况下选取10～40个就可解决问题，本文种群规模为P=20，即可取得较好的结果。迭代次数M的设定：若M太小，则粒子不能搜索到最优位置；若M太大，则运行时间较长；经过反复试验，迭代次数设置为1 000，即可达到效果。

3.2 选星验证

为验证本算法的可行性，采用三星定位的方法进行星体选取。例如：2016年1月1日，世界时05:30:14(选星的时间设定在晨光时间)，推算船位的纬度θ=38°46′.1N，经度λ=121°23′.2E。

选星数学模型利用改进的离散粒子群算法进行计算，即可得到当目标函数取最小值时最理想的一组恒星(御夫座α、天鹅座α、鲸鱼座β)。为验证本模型选取结果的正确性，利用文献[6]模糊控制的方法对事例进行选星，其结果与本算法的结果一致，仍是御夫座α、天鹅座α、鲸鱼座β。

因此，即可说明本文的选星模型具有可行性。利用改进的离散粒子群算法在求解选星模型时具有粒子收敛速度较快，搜索效率高等优点见图3；同时利用本文的选星方法可以得到每颗恒星的高度和方位，有助于实现船舶定位，其结果所在的软件界面见图4。

4 结束语

在船舶天文定位中，星体的选择是进行定位的关键因素，因此提出基于改进离散粒子群算法的选星模型并搭建了索星卡仿真系统。运用OpenGL对索星卡进行仿真；利用MySQL建立数据库；根据选星的要求建立数学模型；利用改进离散粒子群算法在MATLAB平台上编写计算程序，通过对参数的设定，优化选星模型的解；计算出最优的三颗星，从而验证了该选星模型的可行性。

在三颗星的选定过程中，充分考虑所有星体的星等、高度、方位这三要素建立数学模型。对于这种在离散空间中运算，变量有限且有自己运算特点的组合优化问题，采用改进的离散粒子群算法进行选星实现船舶定位。该算法的参数设置少，减少了冗余量，收敛速度快且搜索效率高，准确、自动将选星结果在索星卡上显示。因此，基于改进的离散粒子群算法的选星模型在航海天文定位中具有较大的发展潜力。