A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocation
Abstract With the development of Unmanned Aerial Vehicle (UAV) technology towards multi-UAV and UAV swarm, multi-UAV cooperative task allocation has more and more influence on the success or failure of UAV missions. From the operational research point of view, such problems belong to high-dimensiona...
Saved in:
Main Authors: | , , , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
Springer
2025-01-01
|
Series: | Complex & Intelligent Systems |
Subjects: | |
Online Access: | https://doi.org/10.1007/s40747-024-01720-9 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
_version_ | 1823861471371591680 |
---|---|
author | Xi Chen Yu Wan Jingtao Qi Zipeng Zhao Yirun Ruan Jun Tang |
author_facet | Xi Chen Yu Wan Jingtao Qi Zipeng Zhao Yirun Ruan Jun Tang |
author_sort | Xi Chen |
collection | DOAJ |
description | Abstract With the development of Unmanned Aerial Vehicle (UAV) technology towards multi-UAV and UAV swarm, multi-UAV cooperative task allocation has more and more influence on the success or failure of UAV missions. From the operational research point of view, such problems belong to high-dimensional combinatorial optimization problems, which makes the solving process face many challenges. One is that the discrete and high-dimensional decision variables make the quality of the solution obtained with acceptable time not guaranteed. Second, the desired solution of real missions often needs to satisfy multiple objective functions, or a set of solutions for decision-making. Therefore, this paper constructs a Multi-objective Combinatorial Optimization in Multi-UAV Task Allocation Problem (MCOTAP) model, and proposes a Bi-subpopulation Coevolutionary Immune Algorithm (BCIA). The two coevolutionary mechanisms improve the lower limit of population diversity, and the evolutionary strategy pool integrating multiple strategies and the adaptive strategy selection mechanism enhance the local search ability in the late evolution. In the experiments, BCIA competes fairly with the mainstream multi-objective evolutionary algorithms (MOEAs), multi-objective immune algorithms (MOIAs) and the recently proposed multi-UAV mission planning algorithms. The experimental results on different test problems (including several multi-objective combinatorial optimization benchmark problems and the proposed MCOTAP model) show that BCIA has superior performance in solving multi-objective combinatorial optimization problems (MCOPs). At the same time, the effectiveness of each design component of BCIA has been comprehensively verified in the ablation study. |
format | Article |
id | doaj-art-644fdbc5f0ba431db8d45247740465d4 |
institution | Kabale University |
issn | 2199-4536 2198-6053 |
language | English |
publishDate | 2025-01-01 |
publisher | Springer |
record_format | Article |
series | Complex & Intelligent Systems |
spelling | doaj-art-644fdbc5f0ba431db8d45247740465d42025-02-09T13:00:55ZengSpringerComplex & Intelligent Systems2199-45362198-60532025-01-0111211910.1007/s40747-024-01720-9A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocationXi Chen0Yu Wan1Jingtao Qi2Zipeng Zhao3Yirun Ruan4Jun Tang5Laboratory for Big Data and Decision, National University of Defense TechnologyLaboratory for Big Data and Decision, National University of Defense TechnologyLaboratory for Big Data and Decision, National University of Defense TechnologyLaboratory for Big Data and Decision, National University of Defense TechnologyLaboratory for Big Data and Decision, National University of Defense TechnologyLaboratory for Big Data and Decision, National University of Defense TechnologyAbstract With the development of Unmanned Aerial Vehicle (UAV) technology towards multi-UAV and UAV swarm, multi-UAV cooperative task allocation has more and more influence on the success or failure of UAV missions. From the operational research point of view, such problems belong to high-dimensional combinatorial optimization problems, which makes the solving process face many challenges. One is that the discrete and high-dimensional decision variables make the quality of the solution obtained with acceptable time not guaranteed. Second, the desired solution of real missions often needs to satisfy multiple objective functions, or a set of solutions for decision-making. Therefore, this paper constructs a Multi-objective Combinatorial Optimization in Multi-UAV Task Allocation Problem (MCOTAP) model, and proposes a Bi-subpopulation Coevolutionary Immune Algorithm (BCIA). The two coevolutionary mechanisms improve the lower limit of population diversity, and the evolutionary strategy pool integrating multiple strategies and the adaptive strategy selection mechanism enhance the local search ability in the late evolution. In the experiments, BCIA competes fairly with the mainstream multi-objective evolutionary algorithms (MOEAs), multi-objective immune algorithms (MOIAs) and the recently proposed multi-UAV mission planning algorithms. The experimental results on different test problems (including several multi-objective combinatorial optimization benchmark problems and the proposed MCOTAP model) show that BCIA has superior performance in solving multi-objective combinatorial optimization problems (MCOPs). At the same time, the effectiveness of each design component of BCIA has been comprehensively verified in the ablation study.https://doi.org/10.1007/s40747-024-01720-9Coevolutionary algorithmMulti-objective combinatorial optimizationMulti-objective immune algorithmMulti-UAVTask allocation problem |
spellingShingle | Xi Chen Yu Wan Jingtao Qi Zipeng Zhao Yirun Ruan Jun Tang A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocation Complex & Intelligent Systems Coevolutionary algorithm Multi-objective combinatorial optimization Multi-objective immune algorithm Multi-UAV Task allocation problem |
title | A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocation |
title_full | A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocation |
title_fullStr | A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocation |
title_full_unstemmed | A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocation |
title_short | A bi-subpopulation coevolutionary immune algorithm for multi-objective combinatorial optimization in multi-UAV task allocation |
title_sort | bi subpopulation coevolutionary immune algorithm for multi objective combinatorial optimization in multi uav task allocation |
topic | Coevolutionary algorithm Multi-objective combinatorial optimization Multi-objective immune algorithm Multi-UAV Task allocation problem |
url | https://doi.org/10.1007/s40747-024-01720-9 |
work_keys_str_mv | AT xichen abisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT yuwan abisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT jingtaoqi abisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT zipengzhao abisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT yirunruan abisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT juntang abisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT xichen bisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT yuwan bisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT jingtaoqi bisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT zipengzhao bisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT yirunruan bisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation AT juntang bisubpopulationcoevolutionaryimmunealgorithmformultiobjectivecombinatorialoptimizationinmultiuavtaskallocation |