An Enhanced Hybrid Genetic Annealing Algorithm for Anti-UAV Swarm Target Allocation

In modern warfare, the rapid proliferation of small tactical unmanned aerial vehicles (UAVs), both fixed-wing and rotary-wing, has escalated the threat of swarm-based saturation attacks against existing air defense systems. These anti-UAV scenarios present a formidable challenge, as traditional interception methods—such as soft-kill measures like deception jamming, laser suppression, or high-power microwave damage, and hard-kill means including anti-aircraft artillery and short-range surface-to-air missiles—exhibit significant limitations. Soft-kill approaches are often susceptible to complex electromagnetic environments, may be ineffective against UAVs with specific configurations or robust anti-jamming capabilities, and typically suffer from restricted effective ranges. Hard-kill methods, on the other hand, grapple with issues like low cost-effectiveness, high risks of collateral damage, and insufficient flexibility against highly maneuverable targets. In contrast, interceptor UAVs emerge as an ideal solution for countering modern UAV swarm threats, owing to their low cost, high mobility, rapid response capability, and, crucially, their potential for coordinated swarm operations. However, the core challenge in leveraging interceptor UAV swarms effectively lies in efficiently solving the dynamic, large-scale target allocation problem inherent in anti-UAV operations. This involves real-time optimal matching of our limited and variably configured interceptor UAV resources against numerous, fast-moving, and variably threatening hostile UAV targets in a highly dynamic battlefield environment. The goal is to maximize overall interception effectiveness while minimizing operational costs, subject to multiple strong constraints such as kill probability, time windows, resource consumption, and collision avoidance. This problem is characterized by high dimensionality, strong constraints, multi-objective nature, dynamic time-variance, and NP-hard complexity, rendering traditional optimization methods inadequate for real-time solutions.

Given the complexity and real-time requirements of anti-UAV target allocation, intelligent optimization algorithms, particularly genetic algorithms (GAs), have shown significant potential due to their robust global search capabilities, adaptability to complex constraints, and inherent parallel processing mechanisms. Recent research has made progress; for instance, some studies have developed improved GA models to address issues like the lack of multiple solution options or uncontrollable outcomes in greedy algorithms based on deep reinforcement learning. Others have proposed adaptive GAs to solve target allocation models for combined missile-artillery air defense with constraints like retargeting time and allocated target numbers, verifying improved solution speed. Hybrid genetic particle swarm algorithms have been applied to optimize anti-UAV fire allocation models based on interceptability factors, enhancing GA’s solving ability and convergence speed through the integration of particle swarm optimization. Optimized adaptive GAs have also been employed to solve anti-UAV target allocation mathematical models, demonstrating accelerated optimization search and effective avoidance of local optima. Despite these advancements, current research on anti-UAV swarm target allocation remains insufficient, especially regarding the use of interceptor UAVs to counter UAV swarms, making this area particularly valuable for investigation.

As research into genetic algorithms deepens, scholars have identified issues such as low initial population diversity, slow convergence speed, and poor solution quality when GAs are applied to anti-UAV swarm target allocation problems. A well-designed initialization process is a powerful means to address these shortcomings. Recent improvements in GA initialization have spanned multiple dimensions: some use human prior knowledge as heuristic information to enhance initial population quality and accelerate convergence; others employ artificial bee colony solutions as initial populations for algorithms like NSGA-III to boost overall quality and speed up convergence; parallel processing with multiple processors has been used to generate diverse initial subpopulations, increasing diversity; k-means clustering techniques have been applied to initialize populations, reducing function evaluations and improving GA performance on high-dimensional functions; and global minimum load selection methods have been proposed to produce initial populations, enhancing quality while preserving diversity and accelerating convergence. However, these methods often suffer from high computational complexity, poor adaptability to high dimensions, strong parameter sensitivity, and limitations in solution space distribution uniformity and ergodicity, making it difficult to balance convergence speed with global search capability. Especially in high-dimensional optimization problems, mechanisms to ensure initial population quality and diversity are notably inadequate, constraining further algorithm performance improvements.

To address these issues, I propose a chaos-enhanced hybrid genetic algorithm and simulated annealing (CE-HGASA) that integrates dual Logistic chaotic mapping for initialization. This algorithm is designed to tackle the dynamic target allocation problem in anti-UAV swarm defense operations. In the context of anti-UAV swarm target allocation, I establish a multi-constraint target allocation mathematical model that maximizes system interception effectiveness and minimizes overall interception cost, incorporating dynamic trajectory prediction of targets. By applying CE-HGASA to solve this model, I aim to validate its feasibility. Experimental results indicate that CE-HGASA, compared to traditional genetic algorithms and a baseline algorithm without chaotic mapping, reduces the average number of generations required to converge to the optimal solution by 36% and 20%, respectively, with the variance in convergence generations being an order of magnitude lower than that of traditional GA. This demonstrates that CE-HGASA effectively enhances solution speed and stability, providing an efficient and reliable approach for dynamic real-time target allocation in anti-UAV swarm operations.

Design of the Enhanced Hybrid Genetic Annealing Algorithm

The traditional genetic algorithm often employs random initialization for populations, which can lead to clustering and premature convergence to local optima. In the CE-HGASA algorithm, I address this by generating a high-diversity initial population using dual Logistic mapping, constructing a fitness function based on kill rate and cost-effectiveness ratio, and achieving comprehensive optimization through Pareto sorting. The flowchart of CE-HGASA is illustrated below, and I will describe the algorithm design in the context of anti-UAV defense target allocation.

Encoding

To avoid the normalization of decision variables and potential conversion errors associated with real-number encoding, I adopt binary encoding. Let the existing defender UAVs in the formation be denoted as i (i = 1, 2, …, n), and the UAVs to be engaged as j (j = 1, 2, …, m). The final allocation result is represented as an i × j dimensional matrix U = [uij], where uij is an element of the matrix. uij = 1 indicates that defender UAV i is assigned to target j, and uij = 0 indicates that target j is not assigned to defender UAV i. The matrix U is compressed into a one-dimensional vector in row-major order, representing a chromosome in the genetic algorithm, with each gene on the chromosome corresponding to a Boolean value for whether a defender UAV attacks a target. All chromosomes constitute the population in the genetic algorithm.

Population Initialization

The CE-HGASA algorithm employs a dual Logistic mapping strategy for population initialization to enhance the ergodicity and randomness of the initial population. This process involves two stages: first, the current sequence value zk is preliminarily evolved using a basic Logistic map to obtain an intermediate variable xk, expressed as:

$$ x_k = \mu z_k (1 – z_k), \quad z_k \in (0,1) $$

Subsequently, the intermediate variable xk is used as input, and the same Logistic mapping rule is applied again to obtain the next iteration’s sequence value zk+1. The second mapping and the entire dual mapping process are mathematically represented as:

$$ z_{k+1} = \mu \cdot x_k (1 – x_k) $$

$$ z_{k+1} = \mu [\mu z_k (1 – z_k)] \cdot (1 – \mu z_k (1 – z_k)) $$

where μ is the mapping parameter, ranging from [0, 4], and when 3.569945 ≤ μ ≤ 4, the Logistic map exhibits chaotic properties with good ergodicity. k is the mapping iteration number, with the total number determined by (population size × chromosome length), where population size is the number of chromosomes in a population and chromosome length is i × j. zk represents the current iteration’s sequence value, xk is the output of the first mapping used as input for the second, and zk+1 is the final output of the dual mapping.

Since binary encoding is used and the Logistic map generates continuous values, a threshold r = 0.5 is set: when zk ≥ r, the current sequence value is taken as 1, and when zk < r, it is taken as 0. The resulting binary sequence is then divided into groups according to population size and chromosome length, with each group forming a chromosome, thereby constructing the initial population. This dual mapping mechanism, through nonlinear superposition, mitigates the probability density distortion phenomenon (i.e., endpoint clustering effect) present in the original Logistic map at boundary regions, improving sequence ergodic uniformity.

Fitness Function

Based on the current information of attacker UAVs, defender UAVs have varying interception hit rates and kill rates against targets. In the algorithm, an interception success rate matrix P = [pij] is used, where pij represents the success rate of defender UAV i intercepting attacker UAV j:

$$ p_{ij} = R^i_h R^i_{da} $$

where Rih is the hit rate of defender UAV i against attacker UAV j, and Rida is the kill rate of defender UAV i against attacker UAV j.

Let the cost of defender UAV i intercepting attacker UAV j be cij, and the threat degree of attacker UAV j be ωij. Then the cost-effectiveness ratio fij for interception can be expressed as:

$$ f_{ij} = \frac{\omega_{ij}}{c_{ij}} $$

The objective function aiming to maximize interception rate and minimize interception cost is thus:

$$ E = \max \sum_{i=1}^{M} \sum_{j=1}^{N} \left[ (\alpha p_{ij} + \gamma f_{ij}) u_{ij} \right] $$

where E is the objective function for maximizing overall interception effectiveness while minimizing interception cost. Additionally, before each iteration, the algorithm calculates the minimum fitness value of the population and sets a dynamic threshold at 120% of this value. All individuals with fitness below this threshold are regenerated randomly, introducing new solutions and significantly enhancing population diversity.

Selection Operation

According to the fitness function, the fitness values of all chromosomes in each iteration are calculated and sorted. An elite preservation strategy is employed during iteration: the bottom 20% of chromosomes are replaced with the best chromosomes preserved at that stage, i.e., the least fit 20% are replaced with the most fit, driving the population toward better adaptation.

Crossover Operation

In CE-HGASA, crossover uses multi-point crossover combined with an adaptive crossover rate strategy. Specifically, two parent chromosomes P1 and P2 are randomly selected from the population. Within the chromosome length range, m unique crossover points (m ∈ [2, 5]) are randomly generated, dividing the chromosome into m+1 gene segments. The gene segments of the parents are then alternately exchanged to produce offspring. For example, when m=4, crossover points divide the chromosome into five segments (S1, S2, S3, S4, S5). Offspring C1 inherits S1, S3, S5 from P1 and S2, S4 from P2, while offspring C2 inherits S1, S3, S5 from P2 and S2, S4 from P1. This design enhances perturbation in the solution space by increasing gene segment exchanges, avoiding the locality limitations of single-point crossover.

To dynamically balance global exploration and local exploitation, the crossover rate Pc is adaptively adjusted based on population diversity. Diversity is quantified using population gene entropy H:

$$ H = -\sum_{i=1}^{L} \sum_{j \in \{0,1\}} p_{ij} \log_2(p_{ij}) $$

where L is the chromosome length, and pij is the probability that the i-th gene takes value j. The crossover rate adjustment rule is as follows:

When population gene entropy falls below a set threshold (taken as 60% of the initial gene entropy), indicating a退化 trend, the crossover rate is increased to around 0.95 to promote new solution generation via enhanced gene recombination, avoiding local optima. When population gene entropy is high (above the threshold), the crossover rate is reduced to near the lower limit to minimize disruption to elite gene structures, ensuring stable inheritance of superior solutions. The specific calculation is:

$$ P_c = \begin{cases} P_{c,\text{max}} – a (H – H_{\text{threshold}}), & \text{if } H < H_{\text{threshold}} \\ P_{c,\text{min}} – b (H_{\text{threshold}} – H), & \text{otherwise} \end{cases} $$

where Pc,max is the upper limit, defined as 0.95; Pc,min is the lower limit, defined as 0.7; a and b are adjustment coefficients, with a=0.1, b=0.05; Hthreshold is the gene entropy threshold, defined as 0.6 times the initial population gene entropy.

Mutation Operation

In CE-HGASA, an initial mutation probability is set, and before each mutation, a random number between 0 and 1 is generated. If this number is less than the current mutation probability, mutation is performed. To control mutation intensity and enhance population diversity, a non-uniform mutation strategy is adopted. The perturbation amplitude is controlled by:

$$ \Delta(k) = \left( 1 – \frac{k}{K} \right)^b $$

where Δ(k) is the perturbation strength to mutation probability at the k-th iteration; k is the current iteration number; K is the maximum iteration count; b is the decay coefficient controlling probability decline speed, set to 2 in this study.

The mutation probability decay function is:

$$ y_k = y_{\text{min}} + \Delta(k) (y_{\text{max}} – y_{\text{min}}) $$

where yk is the mutation probability at current iteration; ymin is the final mutation probability, set to 0.1; ymax is the initial mutation probability, set to 0.3. The mutation rate decreases with iterations, aiding in early-stage search expansion and later-stage local convergence.

Simulated Annealing Mechanism

In CE-HGASA, simulated annealing is embedded after mutation to decide whether to accept newly generated individuals. After each generation’s genetic operations, the fitness of new individuals is compared with their parent individuals. If a new individual has better fitness, it is directly accepted, replacing the parent in the next generation. If worse, it is accepted with a probability based on the simulated annealing criterion, calculated as:

$$ P_{SA} = \exp\left( \frac{\Delta E}{T} \right) $$

where ΔE = Enew – Eparent is the fitness difference; T is the current annealing temperature. The temperature T gradually decreases with iteration k, typically using:

$$ T_{k+1} = \lambda \times T_k $$

where λ is the cooling coefficient, ensuring slow temperature reduction to gradually decrease the probability of accepting worse solutions, enhancing algorithm stability and convergence. An initial high temperature T0 is set to allow frequent acceptance of worse solutions early on, expanding search scope and escaping local optima.

Algorithm Workflow

The algorithm follows a “global fast positioning + local fine optimization” core strategy. Key steps include:

  1. Initialization: Set GA parameters (population size NP, max iterations K) and generate an evenly distributed initial population via dual Logistic mapping.
  2. Fitness Calculation and Sorting: Compute fitness for all chromosomes based on the multi-objective function (maximize interception effectiveness, minimize cost), incorporating threat degree, interception success rate, cost matrix, and dynamic trajectory prediction. Sort by fitness descending, retain top 80% elite individuals.
  3. Elite Preservation: Directly pass top 20% best individuals to next generation.
  4. Crossover and Mutation: Randomly pair remaining individuals for crossover with 2-5 points. For individuals with fitness below threshold (120% of current min fitness), apply mutation with decreasing probability (high early, low late) by randomly flipping gene bits to enhance local search.
  5. Simulated Annealing Acceptance: For mutated offspring, accept worse solutions with probability PSA (T0=100, decaying with iterations) to avoid local optima.
  6. Termination Check: If current iterations reach max or fitness change is less than 1% for 20 consecutive generations, output optimal allocation matrix (chromosome); otherwise, increment k and return to step 2.

Mathematical Model for Anti-UAV Swarm Target Allocation

To validate CE-HGASA’s feasibility and superiority in anti-UAV swarm defense, I construct the following mathematical model. In anti-UAV swarm defense, the challenge is to achieve rational and rapid target allocation based on limited defense resources against high-density, high-speed attacker UAV swarms, maximizing overall interception effectiveness while considering interception success rates, target threat levels, and weapon consumption. Due to the highly dynamic motion of enemy targets, real-time prediction of their future states is essential during allocation decisions to improve effectiveness and accuracy.

Let the number of defender UAVs be M and attacker targets be N. The task allocation strategy is defined as a decision matrix:

$$ U = [u_{ij}], \quad u_{ij} \in \{0,1\} $$

where uij = 1 indicates defender UAV i assigns target j. To evaluate allocation effectiveness, the following matrices are constructed:

  1. Interception Success Rate Matrix P = [pij], representing probability of defender UAV i successfully intercepting target j.
  2. Threat Level Matrix W = [ωij], representing threat weight of target j to the defense system. Threat weight is derived from distance to defense key area, speed, flight direction, and tactical level of attacker UAV j, weighted accordingly:

$$ \omega_{ij} = w_1 \cdot d_j + w_2 \cdot \nu_j + w_3 \cdot T_j $$

where dj is the inverse distance of attacker UAV j to the key defense area; νj is the velocity vector of UAV j at current time; Tj is the tactical level of attacker UAV; w1, w2, w3 are weight coefficients for each threat factor.

  1. Interception Cost Matrix C = [cij], representing cost (ammunition, distance, mission time) for defender UAV i to intercept target j:

$$ c_{ij} = \alpha \cdot A_i + \beta \cdot D_{ij} + \delta \cdot t_{ij} $$

where Ai is the cost of defender UAV i; Dij is the flight distance for defender UAV i to successfully intercept attacker UAV j; tij is the total mission time from takeoff to task completion for defender UAV i; α, β, δ are weight coefficients reflecting relative importance of each factor.

Additionally, considering dynamic trajectory prediction for target j, let its state at time t be:

$$ S_j(t) = [X_j(t), \nu_j(t)] $$

where Xj(t) ∈ ℝ3 is current position and νj(t) ∈ ℝ3 is velocity vector. For real-time allocation, a prediction function is built:

$$ X_j(t + \Delta t) = f_j(x_j(t), v_j(t), \Delta t) $$

This function provides short-term dynamic prediction, ensuring interception decisions are based on future target states rather than static positions. The interception success rate pij depends on dynamic prediction results, i.e., it is adjusted based on predicted target position, speed, and UAV interception capabilities (e.g., range, maneuverability) to improve actual hit rate.

Based on the above, the optimization objective function is established to maximize overall interception effectiveness while minimizing cost, enhanced by dynamic trajectory prediction. To ensure feasibility, the following constraints are imposed:

$$ \sum_{i=1}^{M} u_{ij} \leq \gamma_j, \quad \forall j = 1, \dots, N $$

$$ \sum_{j=1}^{N} u_{ij} \cdot c_{ij} \leq R_i, \quad \forall i = 1, \dots, M $$

where γj is the maximum allowed interceptions for target j. The first constraint ensures task uniqueness (each enemy target can be intercepted by a limited number of UAVs), and the second is a resource上限 constraint (each UAV’s total resource consumption must not exceed its maximum capacity).

Simulation Experiments

To effectively verify the performance of the improved algorithm, ablation experiments were conducted comparing CE-HGASA, a traditional genetic algorithm (GA), and a hybrid genetic annealing algorithm without chaotic mapping (HGASA). Analysis focused on computational efficiency and algorithm robustness from two angles. To ensure scientific and reliable comparison, parameters for target UAVs and own UAVs were kept consistent. The experiment假设 that the enemy uses a Springknife-600 UAV swarm to launch saturation attacks on a defense area, while the defense side mobilizes its own UAVs for interception based on attacker swarm information. Software used the Python open-source evolutionary algorithm toolbox Geatpy2 for algorithm development. Hardware configuration: Intel(R) Core(TM) i5-1035G1 CPU at 1.19 GHz, 8 GB RAM.

Experiment 1: Ablation Study on Logistic Mapping

To investigate the impact of Logistic mapping initialization on CE-HGASA, a 20 vs. 20 UAV swarm对抗 mode was used. In a hypothetical air defense scenario, defender UAVs are deployed within a 50m radius centered at the origin. Attacker swarm initial positions are random points from [0,0,500] to [1000,1000,1000], simulating rapid incursion difficult to detect early. Attacker UAV initial positions, velocities, and threat degrees are as follows (example data):

ID Initial Coordinates Initial Velocity Threat Degree
1 [725, 541, 836] 10 0.35
2 [831, 599, 545] 10 0.43
3 [616, 806, 696] 10 0.35
4 [680, 818, 870] 10 0.28
5 [831, 575, 812] 10 0.32
6 [915, 730, 971] 10 0.21
7 [884, 752, 645] 10 0.31
8 [621, 544, 672] 10 0.44
9 [887, 553, 594] 10 0.38
10 [786, 765, 711] 10 0.32
11 [507, 641, 579] 10 0.47
12 [673, 552, 946] 10 0.32
13 [693, 901, 985] 10 0.21
14 [948, 627, 772] 10 0.29
15 [989, 769, 696] 10 0.26
16 [636, 824, 721] 10 0.33
17 [956, 952, 843] 10 0.18
18 [621, 556, 974] 10 0.32
19 [978, 686, 980] 10 0.20
20 [918, 627, 573] 10 0.35

Algorithm parameters are set as follows:

Algorithm CE-HGASA GA HGASA
Iterations 50 50 50
Population 200 200 200
Crossover Rate 0.70–0.95 0.90 0.70–0.95
Mutation Rate 0.30–0.01 0.05 0.30–0.01
Annealing Temperature 300 N/A 300

Algorithm convergence speed is quantified by iterations to reach optimal solution; fewer iterations indicate shorter solution time and higher efficiency under same scale. Fitness is the objective function value; higher fitness means better solution quality. The objective function变化 curves for the three algorithms show that CE-HGASA, HGASA, and GA required 14, 16, and 42 iterations, respectively, to converge to optimal solution, indicating CE-HGASA’s superior convergence speed and solution quality. For further comparison of stability and convergence speed, 50 Monte Carlo simulations were conducted. Statistics from these simulations are summarized below:

Algorithm Mean Fitness Value Mean Convergence Generations Mean Run Time (s) Variance of Convergence Generations
CE-HGASA 3.24 23.3 6.43 4.11
GA 3.19 36.58 10.09 36.11
HGASA 3.19 29.45 7.22 6.05

Simulation measurements show that CE-HGASA, GA, and HGASA have computational complexity in the same order. Given this, subsequent experiments use iterations to convergence as the core metric for real-time assessment. Data indicate CE-HGASA reduces convergence generations by 36% compared to traditional GA and by 20% compared to HGASA without Logistic mapping, with variance an order of magnitude lower than traditional GA, validating dual advantages in convergence speed and stability. Considering the time complexity of Logistic mapping initialization O(2N×D) versus pure random initialization O(N×D) only adds one addition operation, the extra overhead is justified by significant convergence performance improvement, making Logistic mapping initialization valuable for engineering.

The experiment demonstrates that CE-HGASA exhibits faster convergence and more stable convergence generations due to the dual Logistic mapping mechanism in initialization, generating a more uniformly distributed initial population and significantly enhancing diversity, laying a solid foundation for subsequent optimization in anti-UAV operations.

Experiment 2: Impact of μ in Logistic Mapping

To verify the optimal value of parameter μ in Logistic mapping, a controlled experiment was designed. By setting μ ∈ [3.7, 4.0] with step 0.01, algorithm fitness and convergence generations under different parameters were compared. Simulations produced fitness function curves for different μ values, showing significant differences in convergence generations, though most μ values could converge to global optimal fitness. Statistical results from 20 Monte Carlo simulations are presented below for average best fitness and average convergence generations across μ values.

Algorithm performance metrics for different μ values are summarized in the following table (selected data for brevity):

μ Value Average Best Fitness Std Dev of Best Fitness (σ₁) Average Convergence Generations Std Dev of Convergence Generations (σ₂)
3.70 3.16 0.19 29.50 4.54
3.72 3.16 0.06 17.35 16.18
3.79 3.19 0.06 19.85 14.51
3.90 3.16 0.05 24.65 7.95
3.98 3.17 0.06 25.55 3.26
4.00 3.17 0.08 24.65 3.57

From the table and analysis, CE-HGASA performance shows significant parameter dependence. At μ=3.72, the lowest average convergence generations (17.35) are achieved, but with high standard deviation (16.18), indicating large波动. At μ=3.79, the highest average fitness (3.19) is attained, yet convergence stability (σ₂=14.51) is still inferior to specific configurations. Notably, at μ=3.98, the algorithm exhibits balanced superiority: average best fitness is 3.17 (top 25% in parameter sequence), while maintaining very low fitness standard deviation (0.06) and convergence generations standard deviation (3.26). This combination makes this parameter point a Pareto optimal solution, with fitness improved by 9.7% over the lowest value and convergence stability 5 times better than the worst parameter (μ=3.71, σ₂=14.51). Based on convergence curve characteristics, μ=3.98 ensures task allocation quality (high fitness) while significantly enhancing algorithm robustness (low standard deviation) and timeliness (stable convergence at 25.55 generations) in anti-UAV real-time decision scenarios.

Conclusion

In this work, I proposed an improved genetic algorithm that integrates dual Logistic mapping initialization and simulated annealing, referred to as CE-HGASA. By establishing a target allocation model for anti-UAV swarm operations, I validated the algorithm’s convergence efficiency and solution quality. Simulation results demonstrate that CE-HGASA significantly enhances solution efficiency for anti-UAV target allocation through the fusion of Logistic chaotic mapping and simulated annealing mechanisms. Its convergence speed is improved by 36% compared to traditional genetic algorithms and by 20% compared to the baseline without chaotic mapping, with stability enhanced by an order of magnitude. The parameter μ=3.98 is identified as the globally optimal configuration, achieving a balance of high fitness and low variance. This algorithm effectively突破 the bottleneck of high real-time decision-making in dynamic battlefields, providing a reliable solution for UAV swarm interception in anti-UAV operations. Future work may explore further hybridization with other metaheuristics or adaptation to more complex, multi-domain anti-UAV scenarios.

Scroll to Top