基于改進離散粒子群算法的選星模型

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

(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平臺上編寫計算程序，通過對參數的設定，優化選星模型的解；計算出最優的三顆星，從而驗證了該選星模型的可行性。

在三顆星的選定過程中，充分考慮所有星體的星等、高度、方位這三要素建立數學模型。對于這種在離散空間中運算，變量有限且有自己運算特點的組合優化問題，采用改進的離散粒子群算法進行選星實現船舶定位。該算法的參數設置少，減少了冗余量，收斂速度快且搜索效率高，準確、自動將選星結果在索星卡上顯示。因此，基于改進的離散粒子群算法的選星模型在航海天文定位中具有較大的發展潛力。