A Framework for Evolutionary Large-Scale Multi-Objective Security Games Based on Priority Priors

Multi-objective security games (MOSGs) aim to simultaneously optimize the defender's payoff against multiple heterogeneous attackers, which is of great importance in practical applications. Recently, the space discretization based evolutionary search (SDES) framework has been proposed to transform the constrained high-dimensional step function optimization problem in MOSG into a low-dimensional combinatorial optimization problem and to solve the combinatorial optimization task using a greedy strategy. Although SDES can address large-scale MOSG tasks in time, it is difficult for SDES to converge to the optimal Pareto front, especially in the large-scale scenario. On the one hand, the convergence assumption of the greedy strategy of SDES becomes difficult to be satisfied with the scale of MOSG tasks. On the other hand, SDES uses multiple number of stage components, including spatial discretization, evolutionary optimization, evaluation, and refinement components. This poses a risk of stage coupling, where upstream components' optimization quality directly affects downstream components' performance. To address these issues, this paper exploits and utilizes the priority prior of the protected targets in MOSG task to improve the quality of solutions and simplify the SDES framework, resulting in the SDES-P framework. SDES-P redesigns the evaluation component, which is the core component of SDES, and removes the refinement component. Specifically, SDES-P starts from the infeasible solution with the maximum resources. Then, SDES-P divides the protected targets into two groups based on the priority prior, and the higher-priority group gradually releases resources to find feasible solutions. Finally, SDES-P contains an evolutionary local search strategy combined with priority prior knowledge to enhance the quality of the final Pareto front. We reveal that SDES-P can maintain the advantages of low sample complexity and strong scalability of SDES, and experimental results show that, regardless of whether the convergence assumption is satisfied, SDES-P can find high-quality Pareto fronts with better convergence and diversity compared with SDES.