基于模擬退火和自適應(yīng)遺傳算法的影子定位多參數(shù)優(yōu)化研究

李夢瑩 張祥攀 范夢雨 丁猛 曲凱揚(yáng)

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

關(guān)鍵詞：經(jīng)緯度；影子定位；模擬退火模型；遺傳算法

1 遺傳模擬退火算法

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

2 問題分析與模型建立

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

[參考文獻(xiàn)]

[1]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，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]朱建豐，徐世杰.基于自適應(yīng)模擬退火遺傳算法的月球軟著陸軌道優(yōu)化[J].航空學(xué)報(bào)，2007（4）：806-812.

[4]鄺航宇，金晶，蘇勇.自適應(yīng)遺傳算法交叉變異算子的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，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