基于改进模拟退火算法的观察点设置问题研究

Research on Observer Sitting Problem Based on Improved Simulated Annealing Algorithm

观察点设置问题是地形可视性分析中的一类重要问题,在空间信息辅助决策、电信、野生动物保护等领域有着广泛的应用。在深入分析观察点设置问题特点的基础上,对经典模拟退火算法的状态产生过程和状态更新过程进行了问题相关的改进。状态函数的设计同时考虑了观察点的视域和彼此之间的距离影响,而退温函数的设计则实现了高温阶段的退温时间远长于低温阶段的退温时间,提高了计算效率。仿真实验表明,基于改进模拟退火算法的观察点设置问题计算时间比采用经典模拟退火算法减少了50%-95%,并且问题解决准确度也有一定提高。

The observer sitting problem is important in terrain visibility analysis and is widely used in spatial information aid decision, telecom, and animal protection and so on. Based on the analysis of observer sitting problem＇s characteristics, a problem related improvement of traditional simulated annealing algorithm was developed from state generation process and state update process aspects by re-designing new state function and new annealing function. The design of state function considered the effect of observers＇viewshed coverage and the distance among them. The design of annealing function made the annealing time of high temperature be much longer than that of low temperature which improved the commutating efficiency. Experiment results show that with a certain gain of accuracy, the time cost based on improved simulated annealing algorithm （ISA） reduces by 50%-95% when compared with the one using the traditional simulated annealing algorithm （SA）.