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

Wu Yupeng; Qian Hong; Wang Weiye; Zhang Yangwenhui; Zhou Aimin

doi:10.7544/issn1000-1239.202330463

Journal of Computer Research and Development > 2025 > 62(2): 458-471. > DOI: 10.7544/issn1000-1239.202330463 CSTR: 32373.14.issn1000-1239.202330463

Wu Yupeng, Qian Hong, Wang Weiye, Zhang Yangwenhui, Zhou Aimin. A Framework for Evolutionary Large-Scale Multi-Objective Security Games Based on Priority Priors[J]. Journal of Computer Research and Development, 2025, 62(2): 458-471. DOI: 10.7544/issn1000-1239.202330463

Citation:

PDF (1540 KB)

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

Wu Yupeng^1,,
Qian Hong^{1, 2, ,},
Wang Weiye^1,,
Zhang Yangwenhui^1,,
Zhou Aimin^{1, 2,}

1.
School of Computer Science and Technology, East China Normal University, Shanghai 200062
2.
Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062

Funds: This work was supported by the Scientific and Technological Innovation 2030 Major Projects (2018AAA0100902), the Natural Science Foundation of Shanghai (21ZR1420300), and the National Natural Science Foundation of China (62106076).

More Information

Author Bio:
Wu Yupeng: born in 1999. Master candidate. Student member of CCF. His main research interests include evolutionary optimization and security games

Qian Hong: born in 1991. PhD, associate professor. Member of CCF. His main research interests include derivative-free optimization, evolutionary learning, and intelligent education

Wang Weiye: born in 2002. Undergraduate. His main research interest includes evolutionary optimization. (10215102506@stu.ecnu.edu.cn)

Zhang Yangwenhui: born in 1999. Master Candidate. Student member of CCF. His main research interests include evolutionary optimization and learning, and Bayesian optimization. (51215901086@stu.ecnu.edu.cn)

Zhou Aimin: born in 1978. PhD, professor, PhD supervisor. Member of CCF. His main research interests include evolutionary optimization and learning, and intelligent education. (amzhou@cs.ecnu.edu.cn)
Received Date: June 05, 2023
Revised Date: January 02, 2024
Accepted Date: March 05, 2024
Available Online: March 06, 2024

Graphical Abstract

Abstract

Abstract

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, we exploit and utilize 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 the 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.
- large-scale evolutionary security games,
- Stackelberg games,
- multi-objective evolutionary optimization,
- priority prior,
- local search

FullText(HTML)

References (32)

References

[1]	王震,袁勇,安波,等. 安全博弈论研究综述[J]. 指挥与控制学报,2015,1(2):121−149 Wang Zhen, Yuan Yong, An Bo, et al. An overview of security games[J]. Journal of Command and Control, 2015, 1(2): 121−149 (in Chinese)
[2]	Cooney S, Wang Kai, Bondi E, et al. Learning to signal in the goldilocks zone: Improving adversary compliance in security games[C]//Proc of the 23rd Joint European Conf on Machine Learning and Knowledge Discovery in Databases. Berlin: Springer, 2019: 725−740
[3]	Pita J, Jain M, Ordóñez F, et al. Using game theory for Los Angeles airport security[J]. AI Magazine, 2009, 30(1): 43−57 doi: 10.1609/aimag.v30i1.2173
[4]	Tsai J, Rathi S, Kiekintveld C, et al. IRIS—A tool for strategic security allocation in transportation networks[C]//Proc of the 8th Int Conf on Autonomous Agents and Multiagent Systems-Industry Track. Berlin: Springer, 2009: 37−44
[5]	Pita J, Tambe M, Kiekintveld C, et al. GUARDS—Innovative application of game theory for national airport security[C]//Proc of the 22nd Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2011: 2710−2715
[6]	Yin Zhengyu, Jiang A X, Tambe M, et al. TRUSTS: Scheduling randomized patrols for fare inspection in transit systems using game theory[J]. AI Magazine, 2012, 33(4): 59−72 doi: 10.1609/aimag.v33i4.2432
[7]	Shieh E A, An Bo, Yang Rong, et al. PROTECT: A deployed game theoretic system to protect the ports of the United States[C]//Proc of the 11th Int Joint Conf on Autonomous Agents and Multiagent Systems. Berlin: Springer, 2012: 13−20
[8]	李赫,印莹,李源,等. 基于多目标演化聚类的大规模动态网络社区检测[J]. 计算机研究与发展,2019,56(2):281−292 doi: 10.7544/issn1000-1239.2019.20170751 Li He, Yin Ying, Li Yuan, et al. Large-scale dynamic network community detection by multi-objective evolutionary clustering[J]. Journal of Computer Research and Development, 2019, 56(2): 281−292 (in Chinese) doi: 10.7544/issn1000-1239.2019.20170751
[9]	Brown M, An Bo, Kiekintveld C, et al. Multi-objective optimization for security games[C]//Proc of the 11th Int Joint Conf on Autonomous Agents and Multiagent Systems. Berlin: Springer, 2012: 863−870
[10]	Brown M, An Bo, Kiekintveld C, et al. An extended study on multi-objective security games[J]. Autonomous Agents and Multi-Agent Systems, 2014, 28(1): 31−71 doi: 10.1007/s10458-012-9209-6
[11]	Zhou Aimin, Qu Boyang, Li Hui, et al. Multiobjective evolutionary algorithms: A survey of the state of the art[J]. Swarm and Evolutionary Computation, 2011, 1(1): 32−49 doi: 10.1016/j.swevo.2011.03.001
[12]	He Linjun, Ishibuchi H, Trivedi A, et al. A survey of normalization methods in multiobjective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(6): 1028−1048 doi: 10.1109/TEVC.2021.3076514
[13]	Wu Yupeng, Qian Hong, Qin Rongjun, et al. Scaling multi-objective security games provably via space discretization based evolutionary search[J]. arXiv preprint, arXiv: 2303.15821, 2023
[14]	Blank J, Deb K. Pymoo: Multi-objective optimization in Python[J]. IEEE Access, 2020, 8: 89497−89509 doi: 10.1109/ACCESS.2020.2990567
[15]	Lin Xuan, Ahn M S, Hong D. Designing multi-stage coupled convex programming with data-driven McCormick envelope relaxations for motion planning[C]//Proc of the 38th IEEE Int Conf on Robotics and Automation. Piscataway, NJ: IEEE, 2021: 9957−9963
[16]	Kiekintveld C, Jain M, Tsai J, et al. Computing optimal randomized resource allocations for massive security games[C]//Proc of the 8th Int Joint Conf on Autonomous Agents and Multiagent Systems. Berlin: Springer, 2009: 689−696
[17]	Conitzer V, Sandholm T. Computing the optimal strategy to commit to[C]//Proc of the 7th ACM Conf on Electronic Commerce. New York: ACM, 2006: 82−90
[18]	Paruchuri P, Pearce J P, Marecki J, et al. Playing games for security: An efficient exact algorithm for solving Bayesian Stackelberg games[C]//Proc of the 7th Int Joint Conf on Autonomous Agents and Multiagent Systems. Berlin: Springer, 2008: 895−902
[19]	姜伟,方滨兴,田志宏,等. 基于攻防随机博弈模型的防御策略选取研究[J]. 计算机研究与发展,2010,47(10):1714−1723 Jiang Wei, Fang Binxing, Tian Zhihong, et al. Research on defense strategies selection based on attack-defense stochastic game model[J]. Journal of Computer Research and Development, 2010, 47(10): 1714−1723 (in Chinese)
[20]	Mutzari D, Gan J, Kraus S. Coalition formation in multi-defender security games[C]//Proc of the 35th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2021: 5603−5610
[21]	Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting Approach, Part I: Solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577−601 doi: 10.1109/TEVC.2013.2281535
[22]	Zhang Qingfu, Li Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712−731 doi: 10.1109/TEVC.2007.892759
[23]	Fleischer M. The measure of Pareto optima applications to multi-objective metaheuristics[C]//Proc of the 2nd Int Conf on Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2003: 519−533
[24]	Jaszkiewicz A. Many-objective Pareto local search[J]. European Journal of Operational Research, 2018, 271(3): 1001−1013 doi: 10.1016/j.ejor.2018.06.009
[25]	Drugan M M, Thierens D. Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies[J]. Journal of Heuristics, 2012, 18(5): 727−766i doi: 10.1007/s10732-012-9205-7
[26]	Ishibuchi H, Masuda H, Tanigaki Y, et al. Modified distance calculation in generational distance and inverted generational distance[C]//Proc of the 8th Int Conf on Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2015: 110−125
[27]	Zitzler E. Evolutionary algorithms for multiobjective optimization: Methods and applications[D]. Zürich: University of Zürich, 1999
[28]	Bosman P A N, Thierens D. The balance between proximity and diversity in multiobjective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 174−188 doi: 10.1109/TEVC.2003.810761
[29]	Shang Ke, Ishibuchi H, He Linjun, et al. A survey on the hpervolume idicator in eolutionary mltiobjective otimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 1−20 doi: 10.1109/TEVC.2020.3013290
[30]	Audet C, Bigeon J, Cartier D, et al. Performance indicators in multiobjective optimization[J]. European Journal of Operational Research, 2021, 292(2): 397−422 doi: 10.1016/j.ejor.2020.11.016
[31]	Chan T M. Klee’s measure problem made easy[C]//Proc of the 54th Annual IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2013: 410−419
[32]	Knowles J D, Corne D. On metrics for comparing nondominated sets[C]//Proc of the 9th Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2002: 711−716