【摘要】 空间分析是实现各种应用的关键.视界覆盖问题是空间分析的一种.寻求最优部署点源网以覆盖视界工作是一个NP完全问题.提出了一种基于动态负载平衡的并行遗传算法来解决视界覆盖问题,以减少问题的求解时间.仿真实验表明,该算法的加速比已接近最优,求解时间得到了有效减少;与静态负载平衡相比,该算法可有效减少程序执行时间,提高加速比和并行计算效率.更多还原

【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.更多还原