基于分治法的遍歷搜索算法和粒子群算法的改進對太陽影子坐標的地理定位和事件確定的研究 

黃鴻基++錢圳冰++馮帆++周行洲

[摘要]研究首先分析了經(jīng)度、緯度、桿子長度和日期這幾個變量的關(guān)系，通過太陽影子長度計算公式，結(jié)合誤差控制的相關(guān)理論，我們定義了最小誤差函數(shù)，并建立了一個目標規(guī)劃模型。對于多參數(shù)的情況，研究提出“基于分治法的遍歷搜索算法”，用于求解出影子的地理位置和日期。后研究對在目標規(guī)劃模型進行了合理的改進，建立了修正過的目標規(guī)劃模型。通過對所收集的視頻進行合理分析，以每三分鐘為一個采樣周期，得到了影長與時間的相關(guān)數(shù)據(jù)。同時，考慮到數(shù)據(jù)量大和算法復雜度高的因素，研究引入了粒子群（PSO）算法，并用遺傳算法（GA）對其進行了改進，形成了GA-PSO算法。

[關(guān)鍵詞]粒子群算法；遍歷搜索；最小誤差函數(shù)

[DOI]1013939/jcnkizgsc201718199

1引言

太陽影子的位置和時間的確定，在地理勘測和工程應用中有很高的應用價值。研究首先根據(jù)某固定直桿在水平地面上的太陽影子頂點靜態(tài)坐標數(shù)據(jù)，建立數(shù)學模型確定直桿所處的地點和日期。后通過太陽影子的動態(tài)變化視頻，判斷該視頻所發(fā)生的大致地點。從而推廣這兩種算法作為確定太陽影子發(fā)生地點和時間的方法。

2基于分治法的遍歷搜索算法確定靜態(tài)坐標下太陽影子發(fā)生地點和時間

21算法分析

研究根據(jù)相關(guān)數(shù)據(jù)給出的太陽影子頂點坐標數(shù)據(jù)，建立合理的數(shù)學模型來確定直桿所處的地點和日期。根據(jù)附件提供的坐標和其他數(shù)據(jù)，我們可以得到不同時間點所對應的太陽影子長度。很明顯，這是一個目標規(guī)劃問題。可以基于太陽影子長度公示，建立尋找地點和日期的規(guī)劃模型。同時，考慮到研究涉及的未知量較多，直接求解很難得到最優(yōu)的結(jié)果。因此，考慮緯度、經(jīng)度和桿長等因素，研究采用先模塊搜索后整體遍歷的思想，建立一個新的“基于分治法的遍歷算法”，尋找到準確的地理位置并確定它所對應的日期。

22算法模型的建立

步驟一：數(shù)據(jù)處理

定義四組變量α、β、h、N，分別代表經(jīng)度、緯度、桿子高度和年份。由數(shù)學分析的相關(guān)理論和地理學的相關(guān)知識可知，一組連續(xù)的變量可以看成一組間隔無限小的離散型隨機變量的線性組合。同時，在地球上，當兩個經(jīng)度之間相差1°時，它們之間的時間相差4分鐘，因此，我們對數(shù)據(jù)進行了離散化處理，并且在誤差范圍內(nèi)完全可以認為不會對模型的精確度造成影響。我們得到以下關(guān)系：

緯度：-90°≤α≤90°

高度：01≤001≤8，（m）

年份：1≤N≤365

步驟二：建立目標規(guī)劃模型

由問題一，研究得到計算太陽影子的計算公式。若我們定義Lestimatei為與視頻中所對應的第i個時刻代入經(jīng)緯度、高度、日期和時間得到的太陽影子長度，L附件i為通過對附件中的數(shù)據(jù)進行處理得到的第i個時刻的太陽影子長度。當所有時刻這兩個值的平方差最小時，這個地方將有最大的概率與視頻中的地點相吻合，因為同一個地點之間由于有著相同的地理參數(shù)，它們在同一時刻的太陽影子長度必定完全吻合。得到以下模型：

min=21i=1L附件i-Lestimatei）2

st-90°≤α≤90°

（300-15t2）°≤β≤（15904-15t1）°

01≤001≤8，（m）

1≤N≤365

最后，對min函數(shù)數(shù)值求解的精度進行限制，當誤差小于10-3時，停止遍歷搜索，認為得到了最優(yōu)的解決方案。

步驟三：建立基于分治法的遍歷算法進行優(yōu)化求解

（1）首先把四維向量空間劃分為四個一維向量空間，分模塊進行遍歷搜索。

（2）接著，研究按照分治法的思想，分別對四個一維變量進行遍歷搜索。同時進行全局搜索尋優(yōu)。

（3）將第二步遍歷尋優(yōu)的結(jié)果與模型中研究要求的精度進行比較。若第二步中尋優(yōu)的結(jié)果達到我們模型中所要求的精度要求時，遍歷結(jié)束，否則返回第二步，進行遞歸的遍歷求解。

23算法的求解

利用計算機模擬，我們得到已知數(shù)據(jù)中測量所在地數(shù)據(jù)如下表所示。

測量所在地

緯度（°N）經(jīng)度（°E）桿高（m）日期

32248143223814/429

21573961331220

3基于GA-PSO算法對動態(tài)視頻中太陽影子的大致地點的確定

31算法分析

研究在兩種不同的情況下研究太陽影子的定位問題。首先，根據(jù)視頻，研究可以得到在各個時間段所對應的太陽影子長度。接著，對于研究已有日期的視頻部分，在目標規(guī)劃模型的基礎(chǔ)上進行改進，基于太陽影子長度公式，從而建立合理的規(guī)劃模型。

32算法模型的建立

步驟一：數(shù)據(jù)處理

基于問題三建模的相關(guān)思路，我們定義兩組變量α、β，分別代表經(jīng)度和緯度。對數(shù)據(jù)進行了離散化處理，我們得到了以下關(guān)系：

緯度：-90°≤α≤90°

步驟二：建立目標規(guī)劃模型

在問題三我們建立的目標規(guī)劃模型的基礎(chǔ)上，我們進行了適當?shù)母倪M。若我們定義L′i為與視頻中所對應的第i個時刻代入經(jīng)緯度得到的太陽影子長度，Li為在視頻中讀出的第i個時刻的太陽影子長度。我們得到以下模型：

min=22i=1（Li-L′i）2

st-90°≤α≤90°

675°≤β≤180°

同時，對于min的精度要求，我們定義，當誤差小于10-3時，我們停止搜索，認為已經(jīng)得到了最優(yōu)解。

步驟三：用遺傳算法優(yōu)化粒子群算法（GA-PSO）以求得步驟二的最優(yōu)解

在本算法中，為了得到最優(yōu)解，我們設(shè)定了迭代次數(shù)為1000次。

Step1假定有一個S維目標搜索空間，其中第i個粒子表示為一個S維的向量

xi=xi1，x12，…，xiS，i=1，2，…，22

每一個粒子是一個潛在的解。將xi代入（3），我們可以算出它的適應值。第i個粒子飛翔的速度為S維向量，記為[AKV→]=Vi1，Vi2，…，ViS。在這里，我們設(shè)定每一個粒子存儲了2個參數(shù)。同時，通過遺傳算法的選擇、交叉和遺傳過程對所有變量進行初始化，記下第i個粒子迄今為止搜索到的最優(yōu)位置為PiS[TX→]=PiS，…，PiS，整個粒子群搜索到的最優(yōu)位置為PbestS[TX→]=PbestS，…，PbestS。

微粒i當前的最好位置可由下式確定：

pi（t+1）=

pi（t）→min（xi（t+1））≥min（xi（t））

Xi（t+1）→min（xi（t+1））

根據(jù)Kennedy和Eberhart提出的相關(guān)理論，對粒子群進行以下操作：

v=1min

v（t+1）=v（t）+c1rand1（t）（piS（t）-xis（t））+c2rand2（pbestS（t）-xis（t））

xis（t+1）=xis（t）+v（t+1）

其中，

i=[1，22]，s=[1，S]；

c1，c2分別為學習因子，rand（t）為產(chǎn)生隨機數(shù)的函數(shù)，服從[0，1]區(qū)間的均勻分布。

根據(jù)上述方程組，分別對粒子群的速度和位置進行更新，若滿足終止條件，則輸出解，否則返回重新進行下一步的尋優(yōu)。

最終，我們便可以得到視頻拍攝地點的經(jīng)度和緯度，從而進行比較精確的定位。

4算法推廣

本模型所提出的“GA-PSO”算法對于解決大數(shù)據(jù)量的算法復雜度較高的問題有著較高的實用價值。該算法可以推廣到人口相關(guān)數(shù)據(jù)的統(tǒng)計已經(jīng)生產(chǎn)力的評估等多個領(lǐng)域。

參考文獻：

[1]司守奎，孫兆亮數(shù)學建模算法與應用北京國防工業(yè)出版社，2016（1）

[2]卓金武，李必文，魏永生，等MATLAB在數(shù)學建模中的應用[M]北京北京航空航天大學出版社，2014（9）

[基金項目]國家自然基金（項目編號：61322112）。

[作者簡介]黃鴻基（1995—），男，漢族，江蘇南京人，南京郵電大學本科生。研究方向：5G通信和智能算法；錢圳冰（1996—），男，漢族，江蘇泰州人，南京郵電大學本科生。研究方向：計算機科學與技術(shù)；馮帆（1995—），男，漢族，江蘇南京人，南京郵電大學本科生。研究方向：5G通信和智能算法；周行洲（1995—），男，漢族，江蘇南京人，南京郵電大學本科生。研究方向：5G通信和智能算法。