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

Research on Observer Sitting Problem Based on Improved Simulated Annealing Algorithm

作　　者：吕品[1,2] 张金芳[2] 鲍冠伯[1,2] 袁麟[1,2] 

机构地区：[1]中国科学院软件研究所综合信息系统技术国家级重点实验室,北京100190 [2]中国科学院研究生院,北京100049

出　　处：《系统仿真学报》2009年第14期4328-4330,共3页Journal of System Simulation

基　　金：国家高技术研究发展计划(863)(2005AA121120);中科院知识创新工程(5206020)

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

关 键 词：观察点设置 改进模拟退火算法 状态函数 退温函数 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]