基于模拟退火和自适应遗传算法的影子定位多参数优化研究

李梦莹 张祥攀 范梦雨 丁猛 曲凯扬

摘要：文章针对由多变量影子坐标确定拍摄地点的问题，提出了一种将模拟退火算法和遗传算法相结合的求解方法。首先全面分析所有的未知参量包括杆长、经纬度和坐标旋转角，确定未知参量与已知条件的数学关系，以实际坐标与理论计算坐标的误差最小为目标函数，将其倒数作为遗传算法的适应度函数，采用自适应变化的交叉变异算子并用模拟退火算法更新产生新个体，寻找全局最优解。实验结果表明该求解方法在计算速度和全局收敛方面都取得了理想的效果。

关键词：经纬度；影子定位；模拟退火模型；遗传算法

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