基于改进遗传算法的多无人机任务分配  

Multi-UAVs task allocation based on improved genetic algorithm

作　　者：王垚 石永康 WANG Yao;SHI Yongkang(School of Mechanical Engineering,Xinjiang University,Urumqi 830017,China)

机构地区：[1]新疆大学机械工程学院,新疆乌鲁木齐830017

出　　处：《现代电子技术》2023年第4期139-146,共8页Modern Electronics Technique

基　　金：国家自然科学基金项目(51965056);2019年度自治区高校科研计划项目(61021800081);自治区高层次人才项目(100400027)。

摘　　要：为解决传统遗传算法在求解多无人机任务分配问题时易陷入局部最优和收敛速度较慢的问题,文中提出一种融合模拟退火思想的改进遗传算法。首先描述多无人机任务分配问题,将其转化为多旅行商问题,并建立数学模型;然后在传统的遗传算法中引入Metropolis准则,对选择、交叉、变异后的子代种群进行优化调整,使算法可以跳出局部最优并快速收敛;最后进行仿真实验,采用TSPLIB数据库对改进算法进行有效性验证,分别求解不同规模的多旅行商问题,对算法的优越性进行验证,求解任务分配算例以验证改进算法解决多无人机任务分配问题的可行性。实验结果表明,改进的遗传算法能跳出局部最优,收敛速度显著提升,在求解多无人机任务分配问题时,寻优效果优于改进前的算法。In order to solve the problem that the traditional genetic algorithm is easy to fall into the local optimization and has slow convergence when solving the task assignment problem of multi-UAVs,an improved genetic algorithm incorporating the idea of simulated annealing is proposed. The multi-UAVs task allocation problem is described and transformed into the multiple travelling salesman problem(MTSP),and the mathematical model is established. The Metropolis rule is introduced into the traditional genetic algorithm to optimize and adjust the population of the selected,crossed and mutated offspring,so as to make the algorithm jump out of local optimum and converge quickly. The simulation experiment is carried out to verify the effectiveness of the improved algorithm by means of TSPLIB database,and the superiority of the algorithm is verified by solving different scale MTSP respectively. The feasibility of the improved algorithm to solve the multi-UAVs task allocation problem is verified by solving the task allocation example. The experimental results show that the improved genetic algorithm can jump out of the local optimum,and the convergence speed is improved obviously. When solving the multi-UAVs task allocation problem,the optimization effect is better than the improved algorithm.

关 键 词：遗传算法 多无人机 任务分配 多旅行商问题 模拟退火算法 METROPOLIS准则 仿真实验 

分 类 号：V279[航空宇航科学与技术—飞行器设计] V249.1