基于分治法的遍歷搜索算法和粒子群算法的改進(jìn)對(duì)太陽(yáng)影子坐標(biāo)的地理定位和事件確定的研究 

黃鴻基++錢(qián)圳冰++馮帆++周行洲

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

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

[DOI]1013939/jcnkizgsc201718199

1引言

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

2基于分治法的遍歷搜索算法確定靜態(tài)坐標(biāo)下太陽(yáng)影子發(fā)生地點(diǎn)和時(shí)間

21算法分析

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

22算法模型的建立

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

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

緯度：-90°≤α≤90°

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

年份：1≤N≤365

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

由問(wèn)題一，研究得到計(jì)算太陽(yáng)影子的計(jì)算公式。若我們定義Lestimatei為與視頻中所對(duì)應(yīng)的第i個(gè)時(shí)刻代入經(jīng)緯度、高度、日期和時(shí)間得到的太陽(yáng)影子長(zhǎng)度，L附件i為通過(guò)對(duì)附件中的數(shù)據(jù)進(jìn)行處理得到的第i個(gè)時(shí)刻的太陽(yáng)影子長(zhǎng)度。當(dāng)所有時(shí)刻這兩個(gè)值的平方差最小時(shí)，這個(gè)地方將有最大的概率與視頻中的地點(diǎn)相吻合，因?yàn)橥粋€(gè)地點(diǎn)之間由于有著相同的地理參數(shù)，它們?cè)谕粫r(shí)刻的太陽(yáng)影子長(zhǎng)度必定完全吻合。得到以下模型：

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

st-90°≤α≤90°

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

01≤001≤8，（m）

1≤N≤365

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

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

（1）首先把四維向量空間劃分為四個(gè)一維向量空間，分模塊進(jìn)行遍歷搜索。

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

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

23算法的求解

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

測(cè)量所在地

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

32248143223814/429

21573961331220

3基于GA-PSO算法對(duì)動(dòng)態(tài)視頻中太陽(yáng)影子的大致地點(diǎn)的確定

31算法分析

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

32算法模型的建立

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

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

緯度：-90°≤α≤90°

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

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

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

st-90°≤α≤90°

675°≤β≤180°

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

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

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

Step1假定有一個(gè)S維目標(biāo)搜索空間，其中第i個(gè)粒子表示為一個(gè)S維的向量

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

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

微粒i當(dāng)前的最好位置可由下式確定：

pi（t+1）=

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

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

根據(jù)Kennedy和Eberhart提出的相關(guān)理論，對(duì)粒子群進(jì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分別為學(xué)習(xí)因子，rand（t）為產(chǎn)生隨機(jī)數(shù)的函數(shù)，服從[0，1]區(qū)間的均勻分布。

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

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

4算法推廣

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

參考文獻(xiàn)：

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

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

[基金項(xiàng)目]國(guó)家自然基金（項(xiàng)目編號(hào)：61322112）。

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