|
Frontiers of Information Technology & Electronic Engineering
ISSN 2095-9184 (print), ISSN 2095-9230 (online)
2021 Vol.22 No.11 P.1477-1491
UAV search-and-rescue planning using an adaptive memetic algorithm
Abstract: The use of unmanned aerial vehicles (UAVs) is becoming more commonplace in search-and-rescue tasks, but UAV search planning can be very complex due to limited response time, large search area, and multiple candidate search modes. In this paper, we present a UAV search planning problem where the search area is divided into a set of subareas and each subarea has a prior probability that the target is present in it. The problem aims to determine the search sequence of the subareas and the search mode for each subarea to maximize the probability of finding the target. We propose an adaptive memetic algorithm that combines a genetic algorithm with a set of local search procedures and dynamically determines which procedure to apply based on the past performance of the procedures measured in fitness improvement and diversity improvement during problem-solving. Computational experiments show that the proposed algorithm exhibits competitive performance compared to a set of state-of-the-art global search heuristics, non-adaptive memetic algorithms, and adaptive memetic algorithms on a wide set of problem instances.
Key words: Memetic algorithm, Self-adaptive, Unmanned aerial vehicle (UAV), Search-and-rescue
1杭州师范大学信息科学与技术学院,中国杭州市,311121
2浙江工业大学计算机科学与技术学院,中国杭州市,310023
摘要:无人机在搜救任务中的应用日益广泛,然而由于响应时间有限、搜索区域广、搜索模式多样,无人机搜索规划也更加复杂。本文提出一类无人机搜索规划问题,其搜索区域被划分为一组子区域,且每个子区域中目标存在的先验概率已知。解决该问题需要确定这些子区域的搜索顺序以及每个子区域的搜索模式,使得最终搜索成功的概率最大化。提出一种自适应文化基因算法,它结合了遗传算法和一组邻域搜索策略,基于问题求解过程中的适应度提升和多样性提升指标,动态选择邻域搜索策略。在多个问题实例上的计算实验表明,与先进的全局搜索启发式算法以及非自适应文化基因算法相比,所提算法展现了出色性能。
关键词组:
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/FITEE.2000632
CLC number:
TP399
Download Full Text:
Downloaded:
7764
Download summary:
<Click Here>Downloaded:
1122Clicked:
6197
Cited:
0
On-line Access:
2021-11-15
Received:
2020-11-13
Revision Accepted:
2021-05-16
Crosschecked:
2021-09-01