基于改進遺傳算法的定位問題研究

陳一鳴

（河海大學水利水電學院，南京　210098）

基于改進遺傳算法的定位問題研究

陳一鳴

（河海大學水利水電學院，南京210098）

本文提出了一種基于物體影子隨時間變化關系進行定位的新型定位方法。通過物體影長的模型與時間的函數關系，建立了基于最小二乘法的優化模型，并采用了遺傳算法進行尋優求解，同時對遺傳算法進行了一定改進，得到了較傳統遺傳算法更優的解答，得到的定位精度也較高。

空間定位；最小二乘法；改進的遺傳算法

0　引 言

物體定位技術已經由傳統的自然規律發展到現代的GPS定位和雷達定位等，而利用物體的影子進行定位即是將自然規律與現代科技相結合而形成的一種新型定位方法。物體的影子作為直觀的視覺信息，研究影子的定位方法是一項新興主題實用技術。該項技術對視頻圖像資料的定位提供了解決辦法，而且也為刑偵以及失蹤人員偵察等工作在相當程度上創造了真實便利。由于物體在不同地點、不同日期和不同時間的影子長度和角度會發生變化，本文針對影子坐標等數據建立最小二乘優化模型，在傳統遺傳算法的基礎上，加入了尋優范圍的約束建立改進遺傳算法，對比2種算法，可以得到后者搜索結果殘差平方和最小，說明改進遺傳算法具有很好的魯棒性。

1　數學模型

1.1問題描述

影子定位問題可以描述為：某一日期不同時刻t的一直桿影子的頂點坐標為（x，y），要求定位出此時刻的直桿經緯度。本文所采用數據為2015年數模競賽A題附件1［1］。當地實際時間ts與北京時間t的時間差用Δt來表示，桿長為h。當地的緯度（φ）、太陽高度角（α）、太陽赤緯角（δ）、時角（ω）的相關公式如下：

（1）時角ω（度）［2］公式：

（2）太陽赤緯角δ［3］公式：

（3）太陽高度角α［4］公式：

由此可以得出影長L與太陽運動參數的關系如下：

1.2最小二乘優化模型

針對上述問題，要確定多個未知參數需采用最小二乘的思想建立優化模型，設研究中共有m組數據（x，y，t），令z= L2，則以殘差平方和為目標函數建立規劃模型如下：

2　遺傳算法設計

遺傳算法（Genetic Algorithm，簡稱GA）是美國密執安大學J.H.Holland教授于20世紀70年代中期首次提出的一種基于生物遺傳和進化機制的適合復雜系統優化計算的自適應概率優化技術。作為一種智能優化算法，其魯棒性較強，簡單通用，具有較強容錯能力，通過選擇、交叉、變異等操作能極大限度地向最優解進行逼近。同時，變異等操作的引入可防止結果陷入局部最優解，增加搜索的靈活性。對于每一位個體，采用適應度函數對其評價。

基于上文建立的最小二乘優化模型，可以看作是染色體組（φ，h，Δt）在滿足式（6）的約束條件下，通過評價函數對其進行評價，使評價值較高的個體進入到產生下一代的運算中，直至滿足終止條件。遺傳算法流程如圖1所示。

圖1　遺傳算法流程圖Fig.1 Genetic algorithm flowchart

2.1遺傳編碼

比較常見的遺傳算法編碼方式是二進制編碼、格雷編碼及符號編碼等。本文采用二進制進行編碼，并將染色體向量記為V=（φ，h，Δt）。然而，由于實際的算子存在小數，如果直接轉化為二進制，可能會因此而出現無窮小數。針對這一狀況，可將精度確定于小數點后三位，轉換成二進制整數后再進行編碼、運算，并將運算結果轉化為十進制后再除以1 000即可。例如，對于染色體向量V=（0.213，2.986，0.721），得到1 000 V=（213，298 6，721），轉為二進制V=［11010101，101110101010，1011010001］2。

2.2適應度函數

適應度函數是評價個體性能優劣的唯一指標。在本次研究中，基于最小二乘的思想，目標函數的結果值越小，表明擬合的程度越好，即所求得的經緯度更接近原始目的地。因此需將目標函數轉換為適應度函數，以便進行個體優劣的目標判斷。此時，可用適應度Gi表示第i位個體的優良程度：

其中，Q（Xi）是第i個母體的修正值。同時，由于該問題是帶有約束的優化問題，則需在適應度上加入懲罰項。修正后的計算公式如下：

其中，f（Xi）即為式（5）的最小二乘殘差平方和，M為懲

2.3選擇算子

如何選擇參與運算的個體是遺傳算法中的執行實施重點，本文中采用輪盤賭的方法進行選擇。實現過程如下：

1）計算出現在種群中所有個體的適應度Gi以及所有適應度值的倒數總和S。

2）劃分區間［0，1/G1S），［1/G1S，1/G2S）……［1/GnS，1），表示輪盤各扇區的面積。設置生成一個隨機數N∈［0，1），根據N所在的區間進行交叉算子的選擇。如N∈［1/G1S，1/G2S），則選擇第2位個體進行運算。

2.4交叉運算

交叉運算是遺傳算法中目標實現的關鍵所在。其本質是模擬自然界中生物優勝劣汰的原則。即優良的個體將有更大的機會產生后代，從而后代性能必然不斷趨近于更加優秀。在本例中，基于前述采用的是二進制編碼，這里采用了單點交叉的方法。隨機生成3個交叉點位，對選定的染色體組執行交叉運算。如生成的交叉點位向量Y=（5，3，6），對于染色體向量pop1和pop2，操作過程如圖2所示。交叉運算以后產生后代pop1＇和pop2＇，存入下一代中，母代的個體則繼續參與其后的變異運算，從而保證了種群的多樣性。

圖2　交叉運算示意圖Fig.2 Schematic diagram of cross-operation

2.5變異運算

變異運算是模擬自然界中生物進化時的產生的偶發的基因突變。事實上，在用遺傳算法求取最優解問題中，變異運算一定程度上保證了種群不會陷入局部最優解，增強了遺傳算法對全局最優解的搜索能力。本文采用的變異方式有旋轉變異以及位變異2種。

對于旋轉變異，操作方式如下：選取pm1·pop個母體，對于所選的染色體組中的3個染色體，隨機選擇3個位置，并分別以其為分界點，將每個染色體左右的基因互換，完成旋轉變異。如對于染色體組pop：

進行旋轉變異后的結果為：

至此，完成了對旋轉變異的操作。對于位變異，類似于旋轉變異，先選取pm2·pop個母體在生成變異位的基礎上，將所對應的基因進行取反處理，即若基因為1，則取為0，反之即取為1，其他位不變。本文取變異概率pm1=0.1，pm2=0.1。

2.6 終止條件

由于本研究是一個最小二乘的優化問題，對精度要求較高才能搜索到滿意最優解，設置終止條件為進化代數generation=1 000。

2.7遺傳算法的改進

為了得到精度更高的最佳結果，可以采用改進的遺傳算法搜索可行解。通過傳統遺傳算法計算可得的解集V=（φ，h，Δt）是有一定范圍的，其中h的范圍為［1.86，1.946］，φ的范圍為［0.3，0.319］，△t的范圍為［0.56，0.645］，因此可以認定實際上的最優解應在這些范圍附近。通過重新設置變量V=（φ，h，Δt）的范圍，再進一步實施遺傳算法尋優，可以顯著提升算法效率，從而得到更加精確的總體可行解。

設置一個放大系數λ，將上述所求解的范圍記為：

則得到新的范圍：

此處取λ=1.3，并將新的范圍作為約束條件代入改進的遺傳算法程序。

2.8改進的遺傳算法與遺傳算法的實例比較

本文采用全國大學生數學建模競賽A題目附件1的數據［1］，利用最小二乘模型，分別采用2種遺傳算法編程，求解結果如表1所示，進化情況分別為圖3和圖4所示。

表1　遺傳算法與改進遺傳算法結果比較Tab.1 Comparison of GA and improved GA

圖3　遺傳算法進化圖Fig.3 Evolutionary graph of GA

圖4　改進后的遺傳算法進化圖Fig.4 Evolutionary graph of improved GA

由上述結果可得，采用遺傳算法進行計算得到的目標函數值在10-5左右，但是所求的各組h、φ、Δt值之間偏差較大，無法得到一個確定、且較優的解答。通過表1對比可得，改進后的遺傳算法獲得的最優解要遠遠優于之前的遺傳算法，所得到的解集V=（φ，h，Δt）則更加趨向于一固定值，并且算法時間復雜度也僅是呈現為線性增加，因此具有較強的通用性。研究最后，可以定位出物體所在經緯度為（N21°36′1.83″，E108°49′30″）。

3　結束語

影子的存在能夠為光線估計、姿態估計、目標大小估計、深度估計、立體匹配等計算機視覺任務提供重要的線索。本文主要采用桿影日照原理，借助已知影子的軌跡可以反演出桿影目標地點的具體經緯度方位。研究中建立了影長模型和最小二乘優化模型，同時采用遺傳算法來求解直桿相關參數的可行解，并對傳統意義上的遺傳算法提出了一定改進，縮小了遺傳算法的搜索范圍，大大提高了算法的效率以及結果的精度，對于精確定位具有一定的現實重要意義。

［1］中國工業與應用數學學會.2015高教社杯全國大學生數學建模競賽A題［EB/OL］.［2015-09-12］.http：//www.mcm.edu.cn/ html_cn/node/ac8b96613522ef62c019d1cd45a125e3.html.

［2］方榮生.太陽能應用技術［M］.北京：中國農業機械出版社，1985.［3］陳曉勇，鄭科科.對建筑日照計算中太陽赤緯角公式的探討［J］.浙江建筑，2011，28（9）：6-8，12.

［4］維基百科.太陽高度角［EB/OL］.［2014-12-06］.http：//zh. wikipedia.org/zh-cn/.

Research on location problem based on improved genetic algorithm

CHEN Yiming
（Institute of Water Conservancy and Hydroelectric Power，Hehai University，Nanjing 210098，China）

The paper proposes a new method based on the relationship of object shadow with time.The optimization model based on the least square method is established by means of function relation between the model and the time of object shadow，and the genetic algorithm is used to solve the optimization.At the same time，the genetic algorithm is improved to get the solution better than the traditional genetic algorithm，which has the higher positioning accuracy.

spatial location；least square method；improved genetic algorithm

TP391

A

2095-2163（2016）03-0055-03

2016-04-23

陳一鳴（1994-），男，本科生，主要研究方向：水利水電工程。