基于LGN-VNS的多卫星区域目标覆盖算法

Multi-satellite Regional Target Coverage Algorithm Based on LGN-VNS

针对多卫星区域目标覆盖(Multi-satellite Regional Target Coverage,MSRTC)问题,提出了一种基于局部网格嵌套的变邻域搜索算法(Variable Neighborhood Search Algorithm Based on Local Grid Nesting,LGN-VNS)。分析了区域目标处理中网格离散精度对覆盖方案的最优性和求解复杂度的影响,设计了一种降低计算复杂度的局部网格嵌套(Local Grid Nesting,LGN)策略;针对LGN策略的特性,引入变邻域搜索(Variable Neighborhood Search,VNS)框架形成LGN-VNS算法。LGN-VNS算法通过对目标覆盖区域进行局部逐级划分,逐步扩大覆盖方案选择范围,在拓展搜索空间的同时避免了大量冗余计算。将LGN-VNS算法应用到以最大覆盖范围为目标的卫星区域目标覆盖问题中。仿真结果表明,LGN-VNS算法在初始覆盖方案的基础上平均提升覆盖率可达29.73%,与传统VNS算法16.38%的提升率相比表现出了显著的提升效果。与遗传算法相比,LGN-VNS算法能够在36.44%的时间内获得收益值更高的覆盖方案,验证了LGN-VNS算法的有效性和高效性。

A Variable Neighborhood Search Algorithm Based on Local Grid Nesting(LGN-VNS)is proposed for Multi-satellite Regional Target Coverage(MSRTC).Firstly,the influence of grid discretization accuracy on the optimality and solution complexity of the coverage scheme is analyzed,and a Local Grid Nesting(LGN)strategy is designed to reduce computational complexity.Secondly,according to the characteristics of LGN strategy,the Variable Neighborhood Search(VNS)framework is introduced to form LGN-VNS algorithm.The LGN-VNS algorithm gradually expands the range of coverage scheme selection by dividing the target coverage area locally,and avoids redundant calculation while expanding the search space.The LGN-VNS algorithm is applied in satellite regional target coverage with maximum coverage as purpose.The test results show that the average coverage improvement rate of LGN-VNS algorithm can reach 29.73%on the basis of the initial coverage scheme,which shows a significant improvement effect as compared with the traditional VNS algorithm’s improvement rate of 16.38%.Compared with GA algorithm,LGN-VNS algorithm can obtain a coverage scheme with higher benefit value in 36.44%of the time,which verifies the effectiveness and efficiency of LGN-VNS algorithm.