基于混合遗传算法的无人机森林防火巡护路径研究

Research on UAV Forest Fire Prevention Patrol Path Based on Hybrid Genetic Algorithm

本研究提出了一种混合遗传算法,即K-means聚类分析结合基于模拟退火改进的遗传算法,以优化无人机森林防火巡护路径规划。首先,通过K-means聚类分析对巡护点进行分类,有效降低解空间,并适应无人机的续航限制。接着,初始化种群时采用自然数编码表示每个巡护点,形成初始解集。在进化机制中,采用改进的顺序交叉(OX)技术进行基因交换,并通过模拟退火算法优化选择操作,增强局部寻优能力,防止陷入局部最优。文章以浙江省青田县腊口镇为例,实证结果表明,K-means聚类分析将腊口镇防火巡护点分为2个簇,使用改进的遗传算法对每个簇进行优化,均能达到全局最优解。仿真实验结果表明,改进后的混合遗传算法在不同规模的防火巡护点路径规划中表现出色:当巡护点规模为10个以下时,传统遗传算法和混合遗传算法没有明显差距,当巡护点规模增加20个以上时混合遗传算法优化结果优势明显。当巡护点规模为30个时,优化时间增加约3.37秒,但最优路径长度减少了23.90%。当巡护点规模为40个时,优化时间增加约4.83秒,但最优路径长度减少了30.18%。结论显示,K-means聚类分析有效降低了解空间并适应无人机续航限制,遗传算法的全局寻优与模拟退火的局部寻优相结合,显著提高了无人机巡护效率和资源配置效果,为无人机在森林防火中的应用提供了新思路。

This study proposes a hybrid genetic algorithm that combines K-means clustering analysis with a simulated annealing-improved genetic algorithm to optimize UAV forest fire prevention patrol paths.First,K-means clustering analysis is used to classify patrol points,effectively reducing the solution space and accommodating the UAV's range limitations.Then,the initial population is encoded using natural numbers to represent each patrol point,forming the initial solution set.In the evolutionary mechanism,an improved Order Crossover(OX)technique is used for gene exchange,and the selection operation is optimized with simulated annealing to enhance local search capability and prevent premature convergence.Using Lakou Town in Qingtian County,Zhejiang Province,as an example,empirical results show that K-means clustering divides the patrol points into two clusters,and the improved genetic algorithm optimizes each cluster,achieving global optimal solutions.Simulation results indicate that the improved hybrid genetic algorithm performs excellently in patrol path planning for different scales of patrol points:when the number of patrol points is less than 10,there is no significant difference between the traditional and hybrid genetic algorithms;however,when the number of patrol points exceeds 20,the hybrid genetic algorithm shows a clear advantage.For 30 patrol points,optimization time increased by approximately 3.37 seconds,but the optimal path length decreased by 23.90%.For 40 patrol points,optimization time increased by about 4.83 seconds,but the optimal path length decreased by 30.18%.The conclusions show that K-means clustering effectively reduces the solution space and accommodates UAV range limitations,while the combination of the genetic algorithm's global search and simulated annealing's local search significantly enhances UAV patrol efficiency and resource allocation,providing new insights for the application of UAVs in forest fire prevention.