Multi-objective air defense kill chain scheduling via hybrid graph autoencoder and adaptive lamarckian memetic algorithm

This paper investigates the Air Defense Kill Chain Scheduling (ADKCS) problem, a typical large-scale, highly constrained, and multi-objective combinatorial optimization problem. First, a multi-objective optimization model is established to minimize the average kill chain closure time and resource load imbalance. Characterized by complex spatiotemporal constraints and tight resource coupling, ADKCS presents significant challenges to existing evolutionary algorithms, which often struggle with searching feasible solutions and suffer from slow convergence. To address these issues, we propose a Hybrid Graph Autoencoder-based Adaptive Lamarckian Memetic Algorithm (HGAE-ALMA). The proposed HGAE-ALMA integrates a graph representation learning mechanism with an adaptive infeasible solution repair strategy. Specifically, to mine the latent topological relationships between resources and targets, a Graph Autoencoder (GAE) is designed to learn low-dimensional embeddings of the problem structure via Graph Convolutional Networks (GCN) in an unsupervised manner, generating an Affinity Matrix to guide population mutation. Furthermore, an Adaptive Lamarckian Repair Strategy is introduced, combining heuristic correction of infeasible solutions with adaptive parameter control based on the population feasibility ratio. This strategy prioritizes feasible region exploration in the early evolutionary stages while preserving population diversity in the later stages. Large-scale computational experiments demonstrate that in high-intensity confrontation scenarios, the two proposed improvement strategies increase the Hypervolume (HV) indicator by 21.8% and 23.5%, respectively. Furthermore, HGAE-ALMA exhibits a significant advantage in feasible solution search efficiency (EFF), reducing the evaluations required to find the first valid schedule by up to 98.4% (representing a 24- to 62-fold reduction) compared to traditional evolutionary algorithms.