基于改進(jìn)離散粒子群算法的選星模型

趙 猛, 張金鑫, 韓佳穎, 張鶴慶

(1.天津理工大學(xué) 海運(yùn)學(xué)院， 天津 300384；2.鄭州輕工業(yè)學(xué)院 電氣信息工程學(xué)院， 鄭州 450002)

天文導(dǎo)航在遠(yuǎn)洋航行中的作用舉足輕重，隨著無線電導(dǎo)航技術(shù)的發(fā)展，尤其是全球定位系統(tǒng)(Global Positioning System,GPS)定位技術(shù)的產(chǎn)生，航海事業(yè)飛速發(fā)展[1]。GPS定位由于受到聲、光和電波的干擾不具有一定的獨(dú)立性和隱蔽性，而天文導(dǎo)航最大的特點(diǎn)是不受其他設(shè)備和信號(hào)的干擾，但需要完成大量查表和計(jì)算工作[2]。因此,利用計(jì)算機(jī)開發(fā)天文導(dǎo)航系統(tǒng)具有劃時(shí)代的意義。為有效履行《1978年海員培訓(xùn)、發(fā)證和值班標(biāo)準(zhǔn)國(guó)際公約》馬尼拉修正案，規(guī)范海船船員培訓(xùn)行為，根據(jù)《中華人民共和國(guó)船員條例》《中華人民共和國(guó)船員培訓(xùn)管理規(guī)定》的相關(guān)規(guī)定，交通運(yùn)輸部編制了《海船船員培訓(xùn)大綱(2016版)》，大綱明確要求二、三副學(xué)員掌握航海天文歷和天文航海計(jì)算軟件的相關(guān)內(nèi)容。這表明在未來的航海實(shí)踐中，電子天文航海起著重要作用。

20世紀(jì)80年代就出現(xiàn)了利用天文航海技術(shù)對(duì)船舶定位進(jìn)行指導(dǎo)。Omar Reis公司開發(fā)的Navigator軟件和大連海事大學(xué)研制的DMU Celestial Navigator軟件[3]，這些天文航海軟件都集成了選星和認(rèn)星的星圖顯示模塊。相比較而言，傳統(tǒng)索星卡[4]僅憑圖形版面即可提供同樣豐富的信息，且更直觀地體現(xiàn)測(cè)者位置、時(shí)間和星空三者間的關(guān)系。王任大等[5]設(shè)計(jì)并實(shí)現(xiàn)一種用戶界面與經(jīng)典的TS系列索星卡高度近似的仿真型索星卡軟件。施聞明等[6]在天文定位中利用模糊邏輯的方式建立選星模型。王鋒等[7]等提出在天文導(dǎo)航中建立基于線性加權(quán)的計(jì)算機(jī)選星建模。粒子群算法(Particle Swarm Optimization, PSO)具有收斂速度快、設(shè)置參數(shù)少、容易實(shí)現(xiàn)及能有效地解決復(fù)雜優(yōu)化問題等優(yōu)勢(shì)[8]。PSO被用于連續(xù)問題，隨著問題的不斷變化又出現(xiàn)了離散粒子群算法及改進(jìn)的離散粒子群算法，這些算法被廣泛應(yīng)用于一些工程領(lǐng)域[9-11]，受到人們?cè)絹碓蕉嗟年P(guān)注。

基于上述文獻(xiàn)的特點(diǎn)，本文根據(jù)建立模型的離散量運(yùn)算特點(diǎn)，對(duì)于離散的組合優(yōu)化問題，在變量有限的前提下將基于改進(jìn)的離散粒子群算法引入天文航海導(dǎo)航方面，實(shí)現(xiàn)自動(dòng)選取最優(yōu)的一組星；同時(shí)，首次將選星的結(jié)果顯示在索星卡界面上，更有助于海員觀察。

1 索星卡的仿真

1.1 索星卡的概述

在先進(jìn)的航海定位技術(shù)中，由于利用GPS定位，受到的外界影響較大。因此，借助索星卡選星和認(rèn)星進(jìn)行船體定位能避免受外界影響GPS問題，該方法在船舶航行中具有不可取代的地位。索星卡由兩塊星圖底板和若干張透明地平坐標(biāo)網(wǎng)片組成[12](見圖1)。

1)星圖底板是天球的投影圖。圖1a)是按極方位等距投影原理投影而成的，每一個(gè)星圖底板上都印有天赤道和黃道，黃道上標(biāo)有表示視太陽位置的日期。星圖底板有兩圈讀數(shù)，內(nèi)圈是赤經(jīng)讀數(shù)，外圈是平太陽的日期刻度，索星卡星圖底板如圖1a)所示。

2)透明地平坐標(biāo)網(wǎng)片有13張，供0°～60°范圍內(nèi)的測(cè)者使用，每一網(wǎng)片標(biāo)有一個(gè)緯度值，它們是0°N(S)，5°N(S)，10°N(S)，15°N(S)，…，60°N(S)等，同一張網(wǎng)片南、北緯通用。在透明網(wǎng)片的真地平圈外側(cè)印有-6°和-12°高度線，用于確定民用和航海晨光始或昏影終的星空。圖1b)為透明地平坐標(biāo)網(wǎng)片。

1.2 運(yùn)用OpenGL實(shí)現(xiàn)索星卡的仿真

仿真型索星卡的設(shè)計(jì)是基于MFC平臺(tái)，利用OpenGL開發(fā)庫(kù)函數(shù)在Microsoft Visual C++實(shí)現(xiàn)的，在仿真的過程中需要紋理映射、紋理融合及坐標(biāo)變換。

索星卡的使用原理是將星圖底板和地平坐標(biāo)網(wǎng)片重合在一起，轉(zhuǎn)動(dòng)地平坐標(biāo)網(wǎng)片到合適的位置，從而進(jìn)行星的選擇。本設(shè)計(jì)中地平坐標(biāo)網(wǎng)片在RGB模式下映射成紋理圖像，并覆蓋到星圖底板的紋理上，利用OpenGL的庫(kù)函數(shù)將兩個(gè)紋理融合在一起，不遮擋底板上的信息。但由于屏幕的局限性，不能既清晰又完整地將索星卡展現(xiàn)在海員面前，所以需要對(duì)其進(jìn)行坐標(biāo)變換，通過對(duì)鼠標(biāo)和鍵盤的操作，可以清晰看到索星卡上詳細(xì)的內(nèi)容，達(dá)到更好的視覺效果。仿真型索星卡運(yùn)行效果圖見圖2。

2 建立選星模型

2.1 建立數(shù)據(jù)庫(kù)

模型計(jì)算需要有后臺(tái)數(shù)據(jù)支持。因此，本設(shè)計(jì)依據(jù)2016年TheNauticalAlmanac中的信息，利用MySQL建立star數(shù)據(jù)庫(kù)。在star數(shù)據(jù)庫(kù)中依據(jù)恒星視位置列表中的星等、恒星名稱、共軛赤經(jīng)、赤緯和日期建立stars列表，其中為159顆恒星設(shè)置了ID并把其作為主鍵。同時(shí)，根據(jù)不同時(shí)間的春分點(diǎn)格林時(shí)角時(shí)間建立time列表。具體如下:

1)以一月為例，利用MYSQL數(shù)據(jù)庫(kù)管理工具(Navicat for MySQL)，將恒星視位置列表中的詳細(xì)信息導(dǎo)入stars列表中。

2)將不同時(shí)刻的春分點(diǎn)格林時(shí)角導(dǎo)入到time列表中。

3)利用MATLAB平臺(tái)連接MySQL調(diào)用數(shù)據(jù)庫(kù)中數(shù)據(jù)，即可計(jì)算出每個(gè)時(shí)期恒星高度和方位。

2.2 基于改進(jìn)離散粒子群的選星模型

CLERC[13]指出建立離散粒子群算法的關(guān)鍵是為問題域定義和粒子的靜態(tài)和動(dòng)態(tài)行為的描述，根據(jù)粒子群[14]的基本思想構(gòu)建離散粒子群求解離散優(yōu)化問題。鐘一文等[15]依據(jù)優(yōu)化問題及離散量的特點(diǎn)對(duì)粒子的速度和運(yùn)算進(jìn)行重新的定義，并對(duì)粒子的運(yùn)動(dòng)方程進(jìn)行修改，建立改進(jìn)的離散粒子群算法。本文依據(jù)鐘一文提出的改進(jìn)離散粒子群算法，對(duì)選星問題進(jìn)行優(yōu)化求解。這種算法求解充分考慮了離散型組合優(yōu)化的特點(diǎn)，利用這種算法既減少了冗余量，又提高了搜索效率。

2.2.1建立選星數(shù)學(xué)模型

為提高船舶定位的準(zhǔn)確性，在選星時(shí)應(yīng)遵循以下規(guī)則：

1)選擇足夠亮的星。

2)星體的高度要適中，星體高度一般選擇在20°～70°。

3)觀測(cè)兩星定位時(shí)，方位夾角應(yīng)接近90°；觀測(cè)三星定位時(shí)，三星方位分布應(yīng)大于180°，相鄰兩星體的方位夾角趨近120°為最好。

即在選星過程中要根據(jù)星等、高度和方位來確定，通過歐拉三角形公式可計(jì)算得到天體的高度和方位有

sinhc=sinφsinDec+cosφcosDeccosLHA

(1)

cosAc=cosφtanDeccscLHA-sinφcotLHA

(2)

式(1)和式(2)中:hc為天體高度;Ac為天體方位;φ為緯度;Dec為天體赤緯;LHA為天體地方時(shí)角。

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為在選星過程中采用的經(jīng)驗(yàn)權(quán)重值[7];F1、F2、F3分別為a1倍的3顆星的星等之和，a2倍的3顆星的高度之和，a3倍的3顆星的方位之和；x(i)為每行3顆星的星等；|x(j)-45°|為每組星的星體距離最優(yōu)高度的距離；|(x(a)-x(b))-120°|、|(x(c)-x(a))-120°|、|(x(c)-x(b))-120°|為每組星中相鄰兩星的方位夾角與最優(yōu)夾角120°的差距。

依據(jù)選星的要求對(duì)星體高度的范圍和三星分布的范圍分別進(jìn)行約束，設(shè)置約束條件：每組星中星體高度的范圍都在20°～70°；每組星的星體分布應(yīng)大于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基于改進(jìn)的離散粒子群算法求解

1)根據(jù)2.2.1節(jié)的約束條件對(duì)A矩陣中的每一行進(jìn)行篩選，保留符合條件的行，即可組成新的矩陣A1∈Rm×9。在矩陣A1的9維的搜索空間中，隨機(jī)選取P行，即種群的規(guī)模為P。初始化粒子的位置為：X[x11,x12,…,x19,x21,x22,…,x29,…,xP1,xP2,…,xP9]，同時(shí)粒子的速度V為一個(gè)9維的隨機(jī)向量；其中X中的每一個(gè)位置代表一個(gè)可行解；粒子的速度V是用來改變粒子的位置。

2)根據(jù)2.2.1節(jié)中建立的數(shù)學(xué)模型作為目標(biāo)函數(shù)，求出每個(gè)粒子的適應(yīng)值pbestvalue和全局極值fitnessbest。

3)依據(jù)鐘一文等[15]提出的改進(jìn)離散粒子群算法對(duì)粒子的位置和速度進(jìn)行更新。

4)比較每個(gè)粒子的適應(yīng)值和個(gè)體極值，適應(yīng)值和全局極值，尋找當(dāng)前最優(yōu)的個(gè)體極值和適應(yīng)值。

5)如果當(dāng)前的迭代次數(shù)達(dá)到預(yù)計(jì)最大的迭代次數(shù)M，算法結(jié)束。

通過M次尋優(yōu)計(jì)算，即可得到數(shù)學(xué)模型(目標(biāo)函數(shù))的最小值并記錄此時(shí)粒子的位置，粒子的位置是包含星等、高度和方位的一組數(shù)據(jù)；最后根據(jù)這些元素從數(shù)據(jù)庫(kù)中找到3顆恒星的星名。

3 仿真進(jìn)行選星驗(yàn)證

3.1 參數(shù)設(shè)定

該算法是從N=159顆恒星中選取三星進(jìn)行船舶定位；基于改進(jìn)的離散粒子群算法求解選星模型，種群在9維空間中搜索，解的初始值選擇為隨機(jī)性，即從A1矩陣中隨機(jī)選取P行。粒子的種群規(guī)模P的設(shè)定：較小的種群能充分探索解的空間，避免了過多的適應(yīng)值評(píng)估和計(jì)算時(shí)間，一般情況下選取10～40個(gè)就可解決問題，本文種群規(guī)模為P=20，即可取得較好的結(jié)果。迭代次數(shù)M的設(shè)定：若M太小，則粒子不能搜索到最優(yōu)位置；若M太大，則運(yùn)行時(shí)間較長(zhǎng)；經(jīng)過反復(fù)試驗(yàn)，迭代次數(shù)設(shè)置為1 000，即可達(dá)到效果。

3.2 選星驗(yàn)證

為驗(yàn)證本算法的可行性，采用三星定位的方法進(jìn)行星體選取。例如：2016年1月1日，世界時(shí)05:30:14(選星的時(shí)間設(shè)定在晨光時(shí)間)，推算船位的緯度θ=38°46′.1N，經(jīng)度λ=121°23′.2E。

選星數(shù)學(xué)模型利用改進(jìn)的離散粒子群算法進(jìn)行計(jì)算，即可得到當(dāng)目標(biāo)函數(shù)取最小值時(shí)最理想的一組恒星(御夫座α、天鵝座α、鯨魚座β)。為驗(yàn)證本模型選取結(jié)果的正確性，利用文獻(xiàn)[6]模糊控制的方法對(duì)事例進(jìn)行選星，其結(jié)果與本算法的結(jié)果一致，仍是御夫座α、天鵝座α、鯨魚座β。

因此，即可說明本文的選星模型具有可行性。利用改進(jìn)的離散粒子群算法在求解選星模型時(shí)具有粒子收斂速度較快，搜索效率高等優(yōu)點(diǎn)見圖3；同時(shí)利用本文的選星方法可以得到每顆恒星的高度和方位，有助于實(shí)現(xiàn)船舶定位，其結(jié)果所在的軟件界面見圖4。

4 結(jié)束語

在船舶天文定位中，星體的選擇是進(jìn)行定位的關(guān)鍵因素，因此提出基于改進(jìn)離散粒子群算法的選星模型并搭建了索星卡仿真系統(tǒng)。運(yùn)用OpenGL對(duì)索星卡進(jìn)行仿真；利用MySQL建立數(shù)據(jù)庫(kù)；根據(jù)選星的要求建立數(shù)學(xué)模型；利用改進(jìn)離散粒子群算法在MATLAB平臺(tái)上編寫計(jì)算程序，通過對(duì)參數(shù)的設(shè)定，優(yōu)化選星模型的解；計(jì)算出最優(yōu)的三顆星，從而驗(yàn)證了該選星模型的可行性。

在三顆星的選定過程中，充分考慮所有星體的星等、高度、方位這三要素建立數(shù)學(xué)模型。對(duì)于這種在離散空間中運(yùn)算，變量有限且有自己運(yùn)算特點(diǎn)的組合優(yōu)化問題，采用改進(jìn)的離散粒子群算法進(jìn)行選星實(shí)現(xiàn)船舶定位。該算法的參數(shù)設(shè)置少，減少了冗余量，收斂速度快且搜索效率高，準(zhǔn)確、自動(dòng)將選星結(jié)果在索星卡上顯示。因此，基于改進(jìn)的離散粒子群算法的選星模型在航海天文定位中具有較大的發(fā)展?jié)摿Α?/p>