一种新的视界覆盖遗传算法  

A new genetic algorithm for horizontal overcastting

作　　者：孙宏元[1] 谢维信[2] 陆克中[2] 杨勋[1] 

机构地区：[1]西安电子科技大学电子工程学院,陕西西安710071 [2]深圳大学,广东深圳518060

出　　处：《西安电子科技大学学报》2007年第5期758-762,共5页Journal of Xidian University

基　　金：国家自然科学基金资助(60572102);深圳市科技计划项目资助(200506)

摘　　要：空间分析是实现各种应用的关键.视界覆盖问题是空间分析的一种.寻求最优部署点源网以覆盖视界工作是一个NP完全问题.提出了一种基于动态负载平衡的并行遗传算法来解决视界覆盖问题,以减少问题的求解时间.仿真实验表明,该算法的加速比已接近最优,求解时间得到了有效减少;与静态负载平衡相比,该算法可有效减少程序执行时间,提高加速比和并行计算效率.Spatial analysis is key to realizing space information application. The horizontal overcastting problem is one of its important application to optimize an observer network deploying. There is no effective approximate algorithm to solve this NP-complete problem yet. A parallel horizontal overcastting genetic algorithm is presented in the paper. To reduce computing time, a dynamic load balancing is employed in the algorithm. Simulation results show that the speedup ratio of the algorithm is close to the optimization and that computing time is reduced effectively. Also, compared to static load balancing, the dynamic algorithm can observably reduce the executing time, increase the speedup ratio and raise parallel efficiency.

关 键 词：空间分析 视界覆盖问题 负载平衡 并行计算 地理信息系统 

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