基于模擬退火和自適應遺傳算法的影子定位多參數優化研究

李夢瑩 張祥攀 范夢雨 丁猛 曲凱揚

摘要：文章針對由多變量影子坐標確定拍攝地點的問題，提出了一種將模擬退火算法和遺傳算法相結合的求解方法。首先全面分析所有的未知參量包括桿長、經緯度和坐標旋轉角，確定未知參量與已知條件的數學關系，以實際坐標與理論計算坐標的誤差最小為目標函數，將其倒數作為遺傳算法的適應度函數，采用自適應變化的交叉變異算子并用模擬退火算法更新產生新個體，尋找全局最優解。實驗結果表明該求解方法在計算速度和全局收斂方面都取得了理想的效果。

關鍵詞：經緯度；影子定位；模擬退火模型；遺傳算法

1 遺傳模擬退火算法

遺傳算法（GA）是由Holland教授提出的，是一種隨機的優化方法，該算法可以同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時算法本身易于實現并行化，但在實際應用中存在收斂速度慢和早熟等問題，局部搜索能力不強。模擬退火算法（SAA）最早是由 Kirkpatrick等提出的，它是一種啟發式隨機搜索算法，具有很強的局部搜索能力和“爬山”能力。結合兩種算法對影子坐標定位問題進行優化求解，可在提高了定位的精度的同時加快運算速度。

2 問題分析與模型建立

在未知桿長的情況下，給出一段時間中若干個時間點的桿影頂點坐標變化情況，確定拍攝的地點，是一個較為復雜的數學建模問題。其未知參量為3個：經度、緯度、桿長。為了直觀地看出不同緯度隨不同時間的影長分布規律，本文繪制了時間、緯度和影長與桿長比值的三維模型圖（見圖1）。

[參考文獻]

[1]周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社，2005.

[2]Metropolis N，Rosenbluth A，Rosenbluth M，et al.Equation of state calculations by fast computing machines[J].Journal of Chemical Physics，1953（21）： 1087-1092.

[3]朱建豐，徐世杰.基于自適應模擬退火遺傳算法的月球軟著陸軌道優化[J].航空學報，2007（4）：806-812.

[4]鄺航宇，金晶，蘇勇.自適應遺傳算法交叉變異算子的改進[J].計算機工程與應用，2006（12）：93-96.

Research on Optimization of Multiple Parameters for Shadow Localization Based on Adaptive Genetic Simulated Annealing Algorithm

Li Mengying， Zhang Xiangpan， Fan Mengyu， Ding Meng， Qu Kaiyang（Henan Normal University， Xinxiang 453007， China）

Abstract：To solve the problem existing in multivariate shadow coordinates to determine the location. A kind ofadaptive geneticalgorithm， which is combined with simulated annealing algorithm is proposed. At first， we draw comprehensive analysis of all the unknown parameters including length， latitude， longitude coordinates and rotation Angle，Then determine mathematical relation between the unknown parameter and the known condition.The objective function is to minimize the error between the actual coordinate and the theory， and the reciprocal of the objective function is used as the fitness function of the genetic algorithm. We adopt adaptive variation of crossover and mutation operator and simulated annealing algorithm to generate new individuals， finding the global optimal solution. The experimental results show that the proposed method has a good effect on both computational speed and global convergence.

Key words：latitude and longitude；shadow positioning； simulated annealing model； genetic algorithm