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

Abstract: 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.

Key words: spatial analysis, horizontal overcastting, load balancing, parallel computing, GIS