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...

Full description

Saved in:
Bibliographic Details
Main Authors: Xi Chen, Yu Wan, Jingtao Qi, Zipeng Zhao, Yirun Ruan, Jun Tang
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