Article(id=1327012462018277690, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327012311115608215, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202330463, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1685980800000, receivedDateStr=2023-06-06, revisedDate=1704211200000, revisedDateStr=2024-01-03, acceptedDate=1709654400000, acceptedDateStr=2024-03-06, onlineDate=1794314025644, onlineDateStr=2026-11-10, pubDate=1738339200000, pubDateStr=2025-02-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794314025644, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794314025644, creator=13701087609, updateTime=1794314025644, updator=13701087609, issue=Issue{id=1327012311115608215, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='2', pageStart='285', pageEnd='541', issueExtLink='null', onlineDate='null', pubDate='1738339200000', pubDateStr='2025-02-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794313989665, creator='13701087609', updateTime=1794376696965, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275325060395748, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327012311115608215, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275325060395749, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327012311115608215, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=458, endPage=471, ext={EN=ArticleExt(id=1327012462219604283, articleId=1327012462018277690, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=A Framework for Evolutionary Large-Scale Multi-Objective Security Games Based on Priority Priors, columnId=1325493671541474142, journalTitle=Journal of Computer Research and Development, columnName=Network and Information Security, runingTitle=null, highlight=null, articleAbstract=

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.

, authors=Yupeng Wu1, Hong Qian1, 2, *, Weiye Wang1, Yangwenhui Zhang1, Aimin Zhou1, 2, authorsList=Yupeng Wu, Hong Qian, Weiye Wang, Yangwenhui Zhang, Aimin Zhou, authorCompany=null, correspAuthors=Hong Qian, authorNote=

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

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

born in 2002. Undergraduate. His main research interest includes evolutionary optimization. ()

born in 1999. Master Candidate. Student member of CCF. His main research interests include evolutionary optimization and learning, and Bayesian optimization. ()

born in 1978. PhD, professor, PhD supervisor. Member of CCF. His main research interests include evolutionary optimization and learning, and intelligent education. ()

, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1327012465495355724, articleId=1327012462018277690, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=基于优先级先验的演化大规模多目标安全博弈框架, columnId=1325493672690713440, journalTitle=计算机研究与发展, columnName=网络与信息安全, runingTitle=null, highlight=null, articleAbstract=

多目标安全博弈(multi-objective security game,MOSG)旨在同时最优化防御者应对多个异质攻击者获得的收益,在实际应用中具有重要意义. 近期提出的基于空间离散化的演化搜索(space discretization based evolutionary search,SDES)框架将MOSG中的带约束的高维阶梯函数优化问题转换为低维组合优化问题,并使用贪心策略解决组合优化任务. 虽然SDES能够在有限时间内处理大规模MOSG任务,但是SDES难以收敛到大规模MOSG任务对应的最优Pareto前沿上. 一方面,SDES的贪心策略的收敛性假设随问题规模扩大而变得愈发难以满足;另一方面,SDES过多的阶段组件(空间离散化、演化优化、评估、解的精炼)存在阶段耦合的风险,即上游组件的优化质量直接影响下游组件的表现. 因此,挖掘并利用MOSG任务中被保护对象的优先级(priority)先验知识,旨在提高解的质量并简化SDES框架,从而提出了SDES-P框架. SDES-P重新设计了SDES的核心组件——评估组件,并移除解的精炼组件. 具体而言,SDES-P从具有最大资源的不可行解开始,根据被保护对象优先级先验将被保护对象分成2 组,优先级较高的一组对象会逐渐释放资源以找到可行解. 最后,SDES-P包含了一种结合优先级先验的演化局部搜索策略,增强最终Pareto前沿的质量. 分析出SDES-P可保持SDES所具有的样本复杂度低、规模可扩展性强的优势,并且用实验结果表明,无论MOSG任务是否满足收敛假设,SDES-P可以找到相较于SDES收敛性、多样性更优的高质量Pareto前沿.

, authors=吴宇鹏1, 钱鸿1, 2, *, 王为业1, 张杨文辉1, 周爱民1, 2, authorsList=吴宇鹏, 钱鸿, 王为业, 张杨文辉, 周爱民, authorCompany=null, correspAuthors=钱鸿, authorNote=

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化、安全博弈

1991年生. 博士,副教授. CCF会员. 主要研究方向为无梯度优化、演化学习、智能教育

2002年生. 本科生. 主要研究方向为演化优化

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化与学习、贝叶斯优化

1978年生. 博士,教授,博士生导师.CCF会员. 主要研究方向为演化优化与学习、智能教育

, correspAuthorsNote=
钱鸿()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=4nJTTq9VbWSvhkqrmqIrKg==, magXml=vr4g9078nEV8zVj8NiW1jg==, pdfUrl=null, pdf=EaD2/06Khc2XEJ/OyPE3hw==, pdfFileSize=1577446, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=0a8vRPjfC0sVLIM9JTwBmw==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=uUjPc3IGCSHn+kJnN/MeBg==, mapNumber=null, fund=null)}, authors=[Author(id=1327012465973506388, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=51215901031@stu.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012466053198166, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012465973506388, language=EN, stringName=Yupeng Wu, firstName=Yupeng, middleName=null, lastName=Wu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466128695639, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012465973506388, language=CN, stringName=吴宇鹏, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1华东师范大学计算机科学与技术学院 上海 200062, bio={"img":"/r3dOv0QYYfweoXE9C5gWg==","content":"

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化、安全博弈

"}, bioImg=/r3dOv0QYYfweoXE9C5gWg==, bioContent=

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化、安全博弈

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)])]), Author(id=1327012466195804505, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=hqian@cs.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012466267107676, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466195804505, language=EN, stringName=Hong Qian, firstName=Hong, middleName=null, lastName=Qian, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062
2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466342605149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466195804505, language=CN, stringName=钱鸿, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1华东师范大学计算机科学与技术学院 上海 200062
2华东师范大学上海智能教育研究院 上海 200062, bio={"img":"4ZOovmT8J8d5DXl9gNrFQQ==","content":"

1991年生. 博士,副教授. CCF会员. 主要研究方向为无梯度优化、演化学习、智能教育

"}, bioImg=4ZOovmT8J8d5DXl9gNrFQQ==, bioContent=

1991年生. 博士,副教授. CCF会员. 主要研究方向为无梯度优化、演化学习、智能教育

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)]), AuthorCompany(id=1327012465847677264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=2, ext=[AuthorCompanyExt(id=1327012465860260177, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465885426002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2华东师范大学上海智能教育研究院 上海 200062)])]), Author(id=1327012466401325407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=10215102506@stu.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012466476822881, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466401325407, language=EN, stringName=Weiye Wang, firstName=Weiye, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062, bio={"content":"

born in 2002. Undergraduate. His main research interest includes evolutionary optimization. ()

"}, bioImg=null, bioContent=

born in 2002. Undergraduate. His main research interest includes evolutionary optimization. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466552320354, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466401325407, language=CN, stringName=王为业, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1华东师范大学计算机科学与技术学院 上海 200062, bio={"img":"I5mJzJH9xdSIXOlq91fEuA==","content":"

2002年生. 本科生. 主要研究方向为演化优化

"}, bioImg=I5mJzJH9xdSIXOlq91fEuA==, bioContent=

2002年生. 本科生. 主要研究方向为演化优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)])]), Author(id=1327012466611040612, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=51215901086@stu.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012466703315302, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466611040612, language=EN, stringName=Yangwenhui Zhang, firstName=Yangwenhui, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062, bio={"content":"

born in 1999. Master Candidate. Student member of CCF. His main research interests include evolutionary optimization and learning, and Bayesian optimization. ()

"}, bioImg=null, bioContent=

born in 1999. Master Candidate. Student member of CCF. His main research interests include evolutionary optimization and learning, and Bayesian optimization. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466762035559, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466611040612, language=CN, stringName=张杨文辉, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1华东师范大学计算机科学与技术学院 上海 200062, bio={"img":"xZ+fBVLpZ5yDlsRz3WnoZg==","content":"

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化与学习、贝叶斯优化

"}, bioImg=xZ+fBVLpZ5yDlsRz3WnoZg==, bioContent=

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化与学习、贝叶斯优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)])]), Author(id=1327012466921419113, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=amzhou@cs.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012467051442540, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466921419113, language=EN, stringName=Aimin Zhou, firstName=Aimin, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062
2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062, bio={"content":"

born in 1978. PhD, professor, PhD supervisor. Member of CCF. His main research interests include evolutionary optimization and learning, and intelligent education. ()

"}, bioImg=null, bioContent=

born in 1978. PhD, professor, PhD supervisor. Member of CCF. His main research interests include evolutionary optimization and learning, and intelligent education. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012467131134317, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466921419113, language=CN, stringName=周爱民, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, address=1华东师范大学计算机科学与技术学院 上海 200062
2华东师范大学上海智能教育研究院 上海 200062, bio={"img":"/Aw7XKufychf5MFLsNAeZQ==","content":"

1978年生. 博士,教授,博士生导师.CCF会员. 主要研究方向为演化优化与学习、智能教育

"}, bioImg=/Aw7XKufychf5MFLsNAeZQ==, bioContent=

1978年生. 博士,教授,博士生导师.CCF会员. 主要研究方向为演化优化与学习、智能教育

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)]), AuthorCompany(id=1327012465847677264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=2, ext=[AuthorCompanyExt(id=1327012465860260177, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465885426002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2华东师范大学上海智能教育研究院 上海 200062)])])], keywords=[Keyword(id=1327012468892741999, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, orderNo=1, keyword=large-scale evolutionary security games), Keyword(id=1327012468968239472, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, orderNo=2, keyword=Stackelberg games), Keyword(id=1327012469077291377, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, orderNo=3, keyword=multi-objective evolutionary optimization), Keyword(id=1327012469161177458, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, orderNo=4, keyword=priority prior), Keyword(id=1327012469224092020, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, orderNo=5, keyword=local search), Keyword(id=1327012469299589493, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, orderNo=1, keyword=大规模演化安全博弈), Keyword(id=1327012469375086966, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, orderNo=2, keyword=Stackelberg博弈), Keyword(id=1327012469438001527, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, orderNo=3, keyword=多目标演化优化), Keyword(id=1327012469517693304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, orderNo=4, keyword=优先级先验), Keyword(id=1327012469584802169, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, orderNo=5, keyword=局部搜索)], refs=[Reference(id=1327012470901813638, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=王震,袁勇,安波,等. 安全博弈论研究综述[J]. 指挥与控制学报,2015,1(2):121−149, articleTitle=null, refAbstract=null), Reference(id=1327012470968922504, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=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), articleTitle=null, refAbstract=null), Reference(id=1327012471031837065, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471090557322, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471170249099, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471254135180, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471321244045, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471384158606, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471442878863, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=李赫,印莹,李源,等. 基于多目标演化聚类的大规模动态网络社区检测[J]. 计算机研究与发展,2019,56(2):281−292, articleTitle=null, refAbstract=null), Reference(id=1327012471522570640, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=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), articleTitle=null, refAbstract=null), Reference(id=1327012471598068114, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471673565588, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471732285845, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012471786811798, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012473481310615, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012473556808088, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Blank J, Deb K. Pymoo: Multi-objective optimization in Python[J]. IEEE Access, 2020, 8: 89497−89509, articleTitle=null, refAbstract=null), Reference(id=1327012473636499867, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012473728774556, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012473795883421, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012473879769502, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012473963655583, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=姜伟,方滨兴,田志宏,等. 基于攻防随机博弈模型的防御策略选取研究[J]. 计算机研究与发展,2010,47(10):1714−1723, articleTitle=null, refAbstract=null), Reference(id=1327012474039153056, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=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), articleTitle=null, refAbstract=null), Reference(id=1327012474114650529, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012474194342306, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012474290811299, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Qingfu, Li Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712−731, articleTitle=null, refAbstract=null), Reference(id=1327012474366308772, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012474454389157, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Jaszkiewicz A. Many-objective Pareto local search[J]. European Journal of Operational Research, 2018, 271(3): 1001−1013, articleTitle=null, refAbstract=null), Reference(id=1327012474521498022, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Drugan M M, Thierens D. Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies[J]. Journal of Heuristics, 2012, 18(5): 727−766i, articleTitle=null, refAbstract=null), Reference(id=1327012474580218279, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012474647327144, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Zitzler E. Evolutionary algorithms for multiobjective optimization: Methods and applications[D]. Zürich: University of Zürich, 1999, articleTitle=null, refAbstract=null), Reference(id=1327012474710241705, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012474781544874, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012474861236651, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Audet C, Bigeon J, Cartier D, et al. Performance indicators in multiobjective optimization[J]. European Journal of Operational Research, 2021, 292(2): 397−422, articleTitle=null, refAbstract=null), Reference(id=1327012474919956908, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327012474999648685, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)]), AuthorCompany(id=1327012465847677264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=2, ext=[AuthorCompanyExt(id=1327012465860260177, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465885426002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2华东师范大学上海智能教育研究院 上海 200062)])], figs=[ArticleFig(id=1327012469714825594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, label=Figure 1, caption=The process of SDES-P framework and the core evaluation component, figureFileSmall=ec6Qp+1XCK3UZYchXvWcDQ==, figureFileBig=0a8vRPjfC0sVLIM9JTwBmw==, tableContent=null), ArticleFig(id=1327012469798711675, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, label=图1, caption=SDES-P框架和核心评估组件的流程, figureFileSmall=ec6Qp+1XCK3UZYchXvWcDQ==, figureFileBig=0a8vRPjfC0sVLIM9JTwBmw==, tableContent=null), ArticleFig(id=1327012469995843964, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, label=Figure 2, caption=Ranking distribution of $ IG{D}^{+} $ and $ HV $ indicators of six algorithms on 21 MOSG tasks with different scales in 30 min, figureFileSmall=dE6ZXNNigKg9BekRG7g+VQ==, figureFileBig=9yenAQw91KJPtlwIK3ItAQ==, tableContent=null), ArticleFig(id=1327012470062952829, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, label=图2, caption=六种算法在30 min内在21种不同规模的MOSG任务上的$ IG{D}^{+} $和$ HV $指标的排序分布, figureFileSmall=dE6ZXNNigKg9BekRG7g+VQ==, figureFileBig=9yenAQw91KJPtlwIK3ItAQ==, tableContent=null), ArticleFig(id=1327012470134255998, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, label=Figure 3, caption=Solving time of the six algorithms under large-scale protected objects and large-scale attackers, figureFileSmall=dtHhU1Ln0Vm7gSDygEyNfA==, figureFileBig=8pDjfVp6HTbqxHlAD2bdww==, tableContent=null), ArticleFig(id=1327012470192976255, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, label=图3, caption=6种算法在大规模保护对象和大规模攻击者下的求解时间, figureFileSmall=dtHhU1Ln0Vm7gSDygEyNfA==, figureFileBig=8pDjfVp6HTbqxHlAD2bdww==, tableContent=null), ArticleFig(id=1327012470255890816, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, label=Table 1, caption= $ {\boldsymbol{I}\boldsymbol{G}\boldsymbol{D}}^{+} $ Indicator Comparison of SDES and SDES-P about T in the N=3 MOSG Task in 30 min, figureFileSmall=null, figureFileBig=null, tableContent=
算法$ T=25 $$ T=50 $$ T=75 $$ T=100 $$ T=200 $
注:黑体数值表示最优值.
SDES$ 0.44\pm 0.02 $$ 0.39\pm 0.04 $$ 0.27\pm 0.16 $$ 0.28\pm 0.12 $$ 0.32\pm 0.02 $
SDES-P$ {\mathbf {0.31}}\pm {\mathbf {0.02}} $$ \mathbf {0.22}\pm \mathbf{0.03} $$ \mathbf{0.18}\pm \mathbf{0.01} $$ \mathbf{0.17}\pm \mathbf{0.04} $$ \mathbf{0.15}\pm \mathbf{0.00} $
算法$ T=400 $$ T=600 $$ T=800 $$ T=1\;000 $
SDES$ 0.32\pm 0.03 $$ 0.42\pm 0.04 $$ 0.42\pm 0.08 $$ 0.44\pm 0.01 $
SDES-P$ \mathbf{0.20}\pm \mathbf{0.01} $$ \mathbf{0.25}\pm \mathbf{0.03} $$ \mathbf{0.12}\pm \mathbf{0.01} $$ \mathbf{0.20}\pm \mathbf{0.03} $
), ArticleFig(id=1327012470318805377, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, label=表1, caption=

SDES与SDES-P在30 min内N=3的MOSG任务上针对T的IGD+指标对比

, figureFileSmall=null, figureFileBig=null, tableContent=
算法$ T=25 $$ T=50 $$ T=75 $$ T=100 $$ T=200 $
注:黑体数值表示最优值.
SDES$ 0.44\pm 0.02 $$ 0.39\pm 0.04 $$ 0.27\pm 0.16 $$ 0.28\pm 0.12 $$ 0.32\pm 0.02 $
SDES-P$ {\mathbf {0.31}}\pm {\mathbf {0.02}} $$ \mathbf {0.22}\pm \mathbf{0.03} $$ \mathbf{0.18}\pm \mathbf{0.01} $$ \mathbf{0.17}\pm \mathbf{0.04} $$ \mathbf{0.15}\pm \mathbf{0.00} $
算法$ T=400 $$ T=600 $$ T=800 $$ T=1\;000 $
SDES$ 0.32\pm 0.03 $$ 0.42\pm 0.04 $$ 0.42\pm 0.08 $$ 0.44\pm 0.01 $
SDES-P$ \mathbf{0.20}\pm \mathbf{0.01} $$ \mathbf{0.25}\pm \mathbf{0.03} $$ \mathbf{0.12}\pm \mathbf{0.01} $$ \mathbf{0.20}\pm \mathbf{0.03} $
), ArticleFig(id=1327012470381719938, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, label=Table 2, caption= $ {\boldsymbol{I}\boldsymbol{G}\boldsymbol{D}}^{+} $ Indicator Comparison of SDES and SDES-P about N in the T=25 MOSG Task in 30 min, figureFileSmall=null, figureFileBig=null, tableContent=
算法$ N=3 $$ N=4 $$ N=5 $$ N=6 $$ N=7 $$ N=8 $
注:黑体数值表示最优值.
SDES$ 0.44\pm 0.02 $$ 0.32\pm 0.02 $$ \mathbf{0.29}\pm \mathbf{0.07} $$\mathbf {0.49}\pm \mathbf{0.04} $$ {0.58}\pm {0.03} $$ 0.83 \pm 0.03 $
SDES-P$ \mathbf{0.31}\pm \mathbf{0.02} $$ \mathbf{0.30}\pm \mathbf {0.03} $$ 0.65\pm 0.15 $$ 0.53\pm 0.17 $$ \mathbf{0.57}\pm\mathbf{0.04} $$ \mathbf{0.72}\pm \mathbf{0.06} $
算法$ N=9 $$ N=10 $$ N=11 $$ N=12 $$ N=13 $$ N=14 $
SDES$ 1.54\pm 0.29 $$ 0.96\pm 0.03 $$ 1.60\pm 0.22 $$ 1.86\pm 0.26 $$ 1.48\pm 0.12 $$ 1.81\pm 0.39 $
SDES-P$ \mathbf{0.76}\pm \mathbf{0.17} $$ \mathbf{0.64}\pm \mathbf{0.03} $$ \mathbf{1.29}\pm \mathbf{0.09} $$ \mathbf{1.03}\pm \mathbf{0.17} $$ \mathbf{1.08}\pm \mathbf{ 0.35} $$ \mathbf{1.21}\pm \mathbf{0.29} $
算法$ N=15 $$ N=16 $$ N=17 $$ N=18 $$ N=19 $$ N=20 $
SDES$ 2.18\pm 0.30 $$ 2.06\pm 0.41 $$ 2.36\pm 0.38 $$ 2.27\pm 0.32 $$ 2.24\pm 0.27 $$ 2.37\pm 0.26 $
SDES-P$ \mathbf{1.42}\pm \mathbf{0.14} $$ \mathbf{1.39}\pm \mathbf{0.34 }$$ \mathbf{1.38}\pm \mathbf{0.32} $$ \mathbf{1.34}\pm \mathbf{0.35} $$ \mathbf{1.49}\pm \mathbf{0.39 }$$ \mathbf{ 1.45}\pm \mathbf{0.37} $
), ArticleFig(id=1327012470461411715, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, label=表2, caption=

SDES与SDES-P在30 min内T=25的MOSG任务针对N的IGD+指标对比

, figureFileSmall=null, figureFileBig=null, tableContent=
算法$ N=3 $$ N=4 $$ N=5 $$ N=6 $$ N=7 $$ N=8 $
注:黑体数值表示最优值.
SDES$ 0.44\pm 0.02 $$ 0.32\pm 0.02 $$ \mathbf{0.29}\pm \mathbf{0.07} $$\mathbf {0.49}\pm \mathbf{0.04} $$ {0.58}\pm {0.03} $$ 0.83 \pm 0.03 $
SDES-P$ \mathbf{0.31}\pm \mathbf{0.02} $$ \mathbf{0.30}\pm \mathbf {0.03} $$ 0.65\pm 0.15 $$ 0.53\pm 0.17 $$ \mathbf{0.57}\pm\mathbf{0.04} $$ \mathbf{0.72}\pm \mathbf{0.06} $
算法$ N=9 $$ N=10 $$ N=11 $$ N=12 $$ N=13 $$ N=14 $
SDES$ 1.54\pm 0.29 $$ 0.96\pm 0.03 $$ 1.60\pm 0.22 $$ 1.86\pm 0.26 $$ 1.48\pm 0.12 $$ 1.81\pm 0.39 $
SDES-P$ \mathbf{0.76}\pm \mathbf{0.17} $$ \mathbf{0.64}\pm \mathbf{0.03} $$ \mathbf{1.29}\pm \mathbf{0.09} $$ \mathbf{1.03}\pm \mathbf{0.17} $$ \mathbf{1.08}\pm \mathbf{ 0.35} $$ \mathbf{1.21}\pm \mathbf{0.29} $
算法$ N=15 $$ N=16 $$ N=17 $$ N=18 $$ N=19 $$ N=20 $
SDES$ 2.18\pm 0.30 $$ 2.06\pm 0.41 $$ 2.36\pm 0.38 $$ 2.27\pm 0.32 $$ 2.24\pm 0.27 $$ 2.37\pm 0.26 $
SDES-P$ \mathbf{1.42}\pm \mathbf{0.14} $$ \mathbf{1.39}\pm \mathbf{0.34 }$$ \mathbf{1.38}\pm \mathbf{0.32} $$ \mathbf{1.34}\pm \mathbf{0.35} $$ \mathbf{1.49}\pm \mathbf{0.39 }$$ \mathbf{ 1.45}\pm \mathbf{0.37} $
), ArticleFig(id=1327012470574657924, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=EN, label=Table 3, caption=Ablation Experiments on the Large-Scale MOSG Task with $ \boldsymbol{N}=5,\boldsymbol{T}=200 $, figureFileSmall=null, figureFileBig=null, tableContent=
算法$ HV $(排名)$ IG{D}^{+} $(排名)
SDES$ 6.80\mathrm{E}5\pm 1.71\mathrm{E}4(4) $$ 0.90\pm 0.05(4) $
SDES-P移除优先级先验$ 6.83\mathrm{E}5\pm 2.39\mathrm{E}4(2) $$ 0.66\pm 0.06(2) $
SDES-P移除局部搜索$ 6.81\mathrm{E}5\pm 1.02\mathrm{E}4(3) $$ 0.89\pm 0.05(3) $
SDES-P$ 6.85\mathrm{E}5\pm 1.63\mathrm{E}4(1) $$ 0.61\pm 0.04(1) $
), ArticleFig(id=1327012470641766789, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, language=CN, label=表3, caption=

在$ \boldsymbol{N}=5,\boldsymbol{T}=200 $的大规模MOSG任务上的消融实验

, figureFileSmall=null, figureFileBig=null, tableContent=
算法$ HV $(排名)$ IG{D}^{+} $(排名)
SDES$ 6.80\mathrm{E}5\pm 1.71\mathrm{E}4(4) $$ 0.90\pm 0.05(4) $
SDES-P移除优先级先验$ 6.83\mathrm{E}5\pm 2.39\mathrm{E}4(2) $$ 0.66\pm 0.06(2) $
SDES-P移除局部搜索$ 6.81\mathrm{E}5\pm 1.02\mathrm{E}4(3) $$ 0.89\pm 0.05(3) $
SDES-P$ 6.85\mathrm{E}5\pm 1.63\mathrm{E}4(1) $$ 0.61\pm 0.04(1) $
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330463, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330463, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202330463, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202330463, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1738339200000, fullTextJson=null, articleText=null, reference=null)
收藏切换
基于优先级先验的演化大规模多目标安全博弈框架
吴宇鹏 1 , 钱鸿 1, 2, * , 王为业 1 , 张杨文辉 1 , 周爱民 1, 2
计算机研究与发展 | 网络与信息安全 2025,62(2): 458-471
收起
收藏切换
计算机研究与发展 |网络与信息安全 2025 , 62 (2) : 458 -471
基于优先级先验的演化大规模多目标安全博弈框架
全屏
[Author(id=1327012465973506388, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=51215901031@stu.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012466053198166, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012465973506388, language=EN, stringName=Yupeng Wu, firstName=Yupeng, middleName=null, lastName=Wu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466128695639, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012465973506388, language=CN, stringName=吴宇鹏, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1华东师范大学计算机科学与技术学院 上海 200062, bio={"img":"/r3dOv0QYYfweoXE9C5gWg==","content":"

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化、安全博弈

"}, bioImg=/r3dOv0QYYfweoXE9C5gWg==, bioContent=

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化、安全博弈

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)])]), Author(id=1327012466195804505, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=hqian@cs.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012466267107676, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466195804505, language=EN, stringName=Hong Qian, firstName=Hong, middleName=null, lastName=Qian, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062
2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466342605149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466195804505, language=CN, stringName=钱鸿, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1华东师范大学计算机科学与技术学院 上海 200062
2华东师范大学上海智能教育研究院 上海 200062, bio={"img":"4ZOovmT8J8d5DXl9gNrFQQ==","content":"

1991年生. 博士,副教授. CCF会员. 主要研究方向为无梯度优化、演化学习、智能教育

"}, bioImg=4ZOovmT8J8d5DXl9gNrFQQ==, bioContent=

1991年生. 博士,副教授. CCF会员. 主要研究方向为无梯度优化、演化学习、智能教育

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)]), AuthorCompany(id=1327012465847677264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=2, ext=[AuthorCompanyExt(id=1327012465860260177, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465885426002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2华东师范大学上海智能教育研究院 上海 200062)])]), Author(id=1327012466401325407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=10215102506@stu.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012466476822881, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466401325407, language=EN, stringName=Weiye Wang, firstName=Weiye, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062, bio={"content":"

born in 2002. Undergraduate. His main research interest includes evolutionary optimization. ()

"}, bioImg=null, bioContent=

born in 2002. Undergraduate. His main research interest includes evolutionary optimization. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466552320354, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466401325407, language=CN, stringName=王为业, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1华东师范大学计算机科学与技术学院 上海 200062, bio={"img":"I5mJzJH9xdSIXOlq91fEuA==","content":"

2002年生. 本科生. 主要研究方向为演化优化

"}, bioImg=I5mJzJH9xdSIXOlq91fEuA==, bioContent=

2002年生. 本科生. 主要研究方向为演化优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)])]), Author(id=1327012466611040612, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=51215901086@stu.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012466703315302, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466611040612, language=EN, stringName=Yangwenhui Zhang, firstName=Yangwenhui, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062, bio={"content":"

born in 1999. Master Candidate. Student member of CCF. His main research interests include evolutionary optimization and learning, and Bayesian optimization. ()

"}, bioImg=null, bioContent=

born in 1999. Master Candidate. Student member of CCF. His main research interests include evolutionary optimization and learning, and Bayesian optimization. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012466762035559, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466611040612, language=CN, stringName=张杨文辉, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1华东师范大学计算机科学与技术学院 上海 200062, bio={"img":"xZ+fBVLpZ5yDlsRz3WnoZg==","content":"

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化与学习、贝叶斯优化

"}, bioImg=xZ+fBVLpZ5yDlsRz3WnoZg==, bioContent=

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化与学习、贝叶斯优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)])]), Author(id=1327012466921419113, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=amzhou@cs.ecnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012467051442540, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466921419113, language=EN, stringName=Aimin Zhou, firstName=Aimin, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, address=1School of Computer Science and Technology, East China Normal University, Shanghai 200062
2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062, bio={"content":"

born in 1978. PhD, professor, PhD supervisor. Member of CCF. His main research interests include evolutionary optimization and learning, and intelligent education. ()

"}, bioImg=null, bioContent=

born in 1978. PhD, professor, PhD supervisor. Member of CCF. His main research interests include evolutionary optimization and learning, and intelligent education. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012467131134317, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, authorId=1327012466921419113, language=CN, stringName=周爱民, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, address=1华东师范大学计算机科学与技术学院 上海 200062
2华东师范大学上海智能教育研究院 上海 200062, bio={"img":"/Aw7XKufychf5MFLsNAeZQ==","content":"

1978年生. 博士,教授,博士生导师.CCF会员. 主要研究方向为演化优化与学习、智能教育

"}, bioImg=/Aw7XKufychf5MFLsNAeZQ==, bioContent=

1978年生. 博士,教授,博士生导师.CCF会员. 主要研究方向为演化优化与学习、智能教育

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012465747013965, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=1, ext=[AuthorCompanyExt(id=1327012465755402574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science and Technology, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465767985487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465747013965, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1华东师范大学计算机科学与技术学院 上海 200062)]), AuthorCompany(id=1327012465847677264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, xref=2, ext=[AuthorCompanyExt(id=1327012465860260177, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062), AuthorCompanyExt(id=1327012465885426002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012462018277690, companyId=1327012465847677264, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2华东师范大学上海智能教育研究院 上海 200062)])])]
吴宇鹏1 , 钱鸿1, 2, * , 王为业1 , 张杨文辉1 , 周爱民1, 2
作者信息
  • 1华东师范大学计算机科学与技术学院 上海 200062
  • 2华东师范大学上海智能教育研究院 上海 200062
通讯作者:
作者简介:

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化、安全博弈

1991年生. 博士,副教授. CCF会员. 主要研究方向为无梯度优化、演化学习、智能教育

2002年生. 本科生. 主要研究方向为演化优化

1999年生. 硕士研究生. CCF学生会员. 主要研究方向为演化优化与学习、贝叶斯优化

1978年生. 博士,教授,博士生导师.CCF会员. 主要研究方向为演化优化与学习、智能教育

A Framework for Evolutionary Large-Scale Multi-Objective Security Games Based on Priority Priors
Yupeng Wu1 , Hong Qian1, 2, * , Weiye Wang1 , Yangwenhui Zhang1 , Aimin Zhou1, 2
Affiliations
  • 1School of Computer Science and Technology, East China Normal University, Shanghai 200062
  • 2Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062
  • born in 1999. Master candidate. Student member of CCF. His main research interests include evolutionary optimization and security games

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

    born in 2002. Undergraduate. His main research interest includes evolutionary optimization. ()

    born in 1999. Master Candidate. Student member of CCF. His main research interests include evolutionary optimization and learning, and Bayesian optimization. ()

    born in 1978. PhD, professor, PhD supervisor. Member of CCF. His main research interests include evolutionary optimization and learning, and intelligent education. ()

出版时间: 2025-02-01 doi: 10.7544/issn1000-1239.202330463
文章导航
收藏切换

多目标安全博弈(multi-objective security game,MOSG)旨在同时最优化防御者应对多个异质攻击者获得的收益,在实际应用中具有重要意义. 近期提出的基于空间离散化的演化搜索(space discretization based evolutionary search,SDES)框架将MOSG中的带约束的高维阶梯函数优化问题转换为低维组合优化问题,并使用贪心策略解决组合优化任务. 虽然SDES能够在有限时间内处理大规模MOSG任务,但是SDES难以收敛到大规模MOSG任务对应的最优Pareto前沿上. 一方面,SDES的贪心策略的收敛性假设随问题规模扩大而变得愈发难以满足;另一方面,SDES过多的阶段组件(空间离散化、演化优化、评估、解的精炼)存在阶段耦合的风险,即上游组件的优化质量直接影响下游组件的表现. 因此,挖掘并利用MOSG任务中被保护对象的优先级(priority)先验知识,旨在提高解的质量并简化SDES框架,从而提出了SDES-P框架. SDES-P重新设计了SDES的核心组件——评估组件,并移除解的精炼组件. 具体而言,SDES-P从具有最大资源的不可行解开始,根据被保护对象优先级先验将被保护对象分成2 组,优先级较高的一组对象会逐渐释放资源以找到可行解. 最后,SDES-P包含了一种结合优先级先验的演化局部搜索策略,增强最终Pareto前沿的质量. 分析出SDES-P可保持SDES所具有的样本复杂度低、规模可扩展性强的优势,并且用实验结果表明,无论MOSG任务是否满足收敛假设,SDES-P可以找到相较于SDES收敛性、多样性更优的高质量Pareto前沿.

大规模演化安全博弈  /  Stackelberg博弈  /  多目标演化优化  /  优先级先验  /  局部搜索

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
吴宇鹏, 钱鸿, 王为业, 张杨文辉, 周爱民. 基于优先级先验的演化大规模多目标安全博弈框架. 计算机研究与发展, 2025 , 62 (2) : 458 -471 . DOI: 10.7544/issn1000-1239.202330463
Yupeng Wu, Hong Qian, Weiye Wang, Yangwenhui Zhang, Aimin Zhou. 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
安全博弈[1](security game,SG)是一种特殊的Stackelberg博弈[2],Stackelberg博弈中的追随者和领 导者分别对应于安全博弈中的攻击者和防御者. 安全博弈在自然资源保护、交通运输系统、网络安全等领域受到了广泛关注[3-8]. 多目标安全博弈[9-10](multi-objective security game,MOSG)是安全博弈论中的重要研究方向,旨在探索单个防御者如何在同时面对多个异质攻击者的情况下最大化获得的利益. 由于安全领域的特殊性,MOSG要求找到一个收敛性和多样性都良好的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿[9]. 目前,MOSG已在洛杉矶警力资源分配(将有限警力资源分配到对洛杉矶不同潜在犯罪类型的防御上)等现实任务[9-10]中得以成功应用,展现了MOSG在安全博弈上的潜力. 然而,受限于算法的问题规模可扩展性,不少现有的MOSG算法难以在更大规模的问题(如自然资源保护、公共基础设施保护等)上得到广泛应用.
MOSG的潜力来自于其对异质攻击者场景进行多目标优化[11-12]建模的思想. MOSG将异质攻击者造成的每个损失视为单独的优化目标,在优化时同时追求每个目标的最优,而不是如传统安全博弈算法一样将异质的损失加权合并成单目标函数进行寻优. 多目标优化异质损失更符合现实任务的需求,例如,同时最优化盗窃造成的财产损失和恐怖袭击造成的人员伤亡这2类异质损失时,传统算法一般将异质损失转化为可加权合并的损失类型,如经济损失. 然而从安全角度,人员伤亡不应该仅用经济损失衡量,这表明以多目标方式同时优化多类异质损失是更合理且必要的. 因此,设计求解规模扩展性强且求解质量高的算法是MOSG的研究重点[9-10, 13]. 其中,具有代表性的一类$ \epsilon $-约束算法[9-10]能够解决中小规模(异质攻击者/类型3~5个,防御者几十个)MOSG问题,并通过误差上界限制$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $近似集与$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $参考集之间的差距在可控范围内. 另一类最新的基于演化算法的求解框架SDES[13]能高效求解大规模MOSG. 对于要在限定时间内完成的大规模MOSG问题,SDES框架能在规定时间内完成,而$ \epsilon $-约束算法往往会超时.
虽然现有的算法[10, 13-14]分别在MOSG任务的求解质量和规模可扩展性方面取得了一定的进展,但很少有算法能够在这2方面都取得令人满意的结果. 在求解质量方面,MOSG需要算法提供具有良好收敛性和多样性的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿(PF)集合. 以ORIGAMI-M和ORIGAMI-A为代表的一类$ \epsilon $-约束框架[9-10]为$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿的收敛性提供了理论保证. 然而,为满足该收敛性保证,算法的样本复杂度会随攻击者数量呈指数级增长. 因此,在大规模攻击者的情况下,$ \epsilon $-约束框架在有限时间内难以提供具有良好收敛性和多样性的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿. 在规模可扩展性方面,一类称为SDES的空间离散化框架[13]可以快速处理大规模MOSG任务. SDES框架包含离散化、优化、评估和解的精炼等4个组件. SDES使用离散化组件将MOSG任务转化为组合优化问题,优化组件采用贪心策略解决组合优化问题. SDES使用了评估组件以满足收敛假设的要求,然而,贪心策略收敛到最优Pareto前沿的假设条件随问题规模的扩大而愈发难以满足,这使得SDES在大规模场景中有时难以找到高质量的Pareto前沿. SDES最后使用解的精炼组件在一定程度上补救收敛性假设不被满足的情形. 此外,SDES是一个多阶段优化模型,阶段组件过多会引发阶段耦合的风险[15],从而影响算法优化的性能. 一方面,阶段耦合导致下游组件的优化效果依赖上游组件,上游组件的优化效果波动会对下游组件造成明显影响,降低了模型的稳定性. 另一方面,阶段耦合会累积上游组件的优化误差,愈加影响下游组件的效果. 综上所述,对于大规模多目标安全博弈任务,SDES框架在提升求解质量和降低框架复杂度方面有较大提升空间,亟需强化.
有鉴于此,本文提出了一种基于优先级先验的演化大规模多目标安全博弈框架SDES-P,该框架可以在平衡求解质量和可扩展性的同时简化SDES框架. 在SDES-P中,我们通过安全博弈的先验知识重新设计了SDES的核心组件——评估组件. 新的评估组件包含完全冷漠初始化策略、基于优先级的可行解搜索策略以及演化局部搜索策略. 具体而言,已有研究表明,SDES[13]基于贪心策略的评估组件更倾向于选取资源数量更多的候选集. 因此,SDES-P将解初始化为消耗最多资源但不一定可行的解. 此外,现有研究[16]发现在安全博弈任务中,不同被保护对象收益的上下界决定了其获取保护资源的优先级. 为释放尽可能多的资源使解可行化,被保护对象可以分为释放资源优先级高和释放资源优先级低2组. 由于优先级高的被保护对象收益不可观,不容易被攻击者关注,因此释放其资源时对防御者收益的影响较小. 基于优先级先验,SDES-P能在保持求解质量的同时将不可行解转化为可行解. 最后,从可行解开始,演化局部搜索策略借助优先级先验筛选非支配解集,构建收敛性和多样性良好的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿解集. 相较于SDES框架,SDES-P保留了离散化和优化组件,重新设计了评估组件,移除解的精炼组件,精简了框架的构成部分. 与此同时,SDES-P可保持SDES所具有的样本复杂度低、规模可扩展性强的优势. 此外,各种规模下的MOSG对比实验表明,在MOSG任务不满足收敛假设时,SDES-P可以找到相较于SDES收敛性、多样性更优的高质量Pareto前沿. 消融实验验证了SDES-P框架中各组件的必要性与贡献. 一言以蔽之,SDES-P是一个同时考虑了求解质量和规模可扩展性的MOSG简化求解框架.
本文后续内容组织如下:介绍安全博弈相关工作,回顾基础知识,详细介绍本文提出的基于优先级先验的演化大规模多目标安全博弈框架,分析实验结果,最后总结全文. 附录部分是对正文细节的补充说明.
安全博弈论研究如何在安全领域中高效地利用有限资源来保护目标,防御潜在攻击者. 按照目标的建模方式,安全博弈论可以分为基于加权合并的单目标安全博弈SG[16]以及基于多目标建模与优化的多目标安全博弈MOSG[9]. 本节主要回顾现有安全博弈论算法的优势与不足,同时阐述本文所提出的SDES-P与现有算法之间的联系和区别.
在单目标安全博弈中,以贝叶斯安全博弈[16–18]为代表的标量决策方法因建模方式简单而在现实任务中得到广泛应用,包括用于机场保护的ARMOR,IRIS,GUARDS[3–5],用于运输系统保护的TRUSTS[6],用于海岸防护的PROTECT[7]以及用于网络安全的随机博弈模型[19]. 贝叶斯安全博弈使用贝叶斯方法依据概率将多目标函数值合并成单目标标量,在同类方法中具有明显的效率优势. DOBSS[15]是第1个成功应用于ARMOR[3]系统的算法,它利用攻击者的独立性将几个线性规划问题转化为混合整数线性规划问题,并通过有效的编程方法来解决. 此外,ERASER[16]直接在混合整数线性规划公式中解决SG问题,并使目标维度不再影响求解效率. 虽然标量决策方法可以高效地产生最优配置方案,但标量决策方法不适用于包含多个不可合并的异质攻击者的场景. 例如,财产和生命的损失并不具有相同的重要性[9],将异质目标加权合并会由于不合实际从而求解质量差. 本文设计的SDES-P框架能够独立建模异质的攻击者,同时最优化多个异质目标.
在多目标安全博弈中,以$ \epsilon $-约束框架[9-10]为代表的精确求解算法在中小规模(异质攻击者/类型3~5个,防御者几十个)MOSG任务上的求解质量良好. 通过利用问题特性[16]、剪枝[9]和其他方法[10],该框架能够在不破坏其他目标的前提下,逐一优化每个目标. 在不限制时间的情况下,$ \epsilon $-约束框架是一类可以保证$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿质量的精确算法. 然而,由于它维护$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿多样性的样本复杂度会随着攻击者数量的增加呈指数增长,在大规模情况下,该算法难以在规定时间内找到满足要求的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿. 本文提出的SDES-P求解框架能够在快速求解大规模MOSG任务的同时保证求解质量.
以空间离散化框架[13]为代表的近似求解算法在处理大规模MOSG问题方面表现良好. 在这种算法中,MOSG任务被转化为一个组合优化问题. 其中,SDES[13]基于收敛假设,通过贪心决策解决组合优化问题. 当收敛假设成立时,SDES可以在限定时间内处理大规模MOSG任务并保证求解质量. 然而,由于SDES会贪心地针对每个攻击目标优化最优解,这使得满足收敛假设的难度会随攻击目标数的增加快速增长. 因此,在保护对象为大规模的场景下,SDES算法很难提供一个收敛性良好的解. 在MOSG任务不满足收敛假设的情况下,SDES中解的精炼组件会对求解质量进行一定程度上的补救. 然而,上述收敛假设难以满足的问题是由评估组件采用贪心策略导致的,解的精炼组件并不能从根本上解决该问题. 本文提出的SDES-P框架尝试从根本上解决大规模场景下假设难以满足的问题,重点改进了评估组件,同时移除解的精炼组件以简化框架.
本文所提算法主要涉及多目标安全博弈MOSG的建模和MOSG任务的求解框架SDES,下面就相关概念和基本知识加以介绍.
MOSG是一种特殊的防御者-攻击者Stackelberg博弈,由$ T $个被保护对象、1个防御者$ D $和$ N $个异质的攻击者$ {A}_{i} $组成,其中$ i\in \{1,2,…,N\} $. 资源总量为$ r\times T $,由于资源受限,资源比例$ r \ll 1 $. 防御者$ D $的连续策略可以表示为覆盖向量$ \boldsymbol{c}=\left({c}_{1},{c}_{2},…,{c}_{T}\right)\in {\left[0,1\right]}^{T} $,其中$ {\left\|\boldsymbol{c}\right\|}_{1}\le r\times T $,$ {c}_{t} $表示给第$ t $个被保护对象的资源量和成功覆盖保护对象$ t $的概率[20]. 覆盖向量的解空间被定义为$ C=\left\{\boldsymbol{c}\in {\left[\mathrm{0,1}\right]}^{T}\mid {\left\|\boldsymbol{c}\right\|}_{1}\le r\times T\right\} $. 攻击者$ {A}_{i} $的离散策略可以表示为$ {\boldsymbol{a}}_{i}=({a}_{i1},{a}_{i2},…,{a}_{iT})\in {\left\{\mathrm{0,1}\right\}}^{T} $. 防御者在某个保护对象$ t $上成功防御攻击者$ {A}_{i} $的攻击会获得一定收益,MOSG的目标即为找到防御者$ D $最优的资源分配方案,以获得$ D $的最优收益. 由于MOSG包含$ N $个不可合并的异质攻击者$ {A}_{1},{A}_{2},…,{A}_{N} $,因此MOSG任务需要在多个攻击者的攻击下尽可能最大化收益,其目标函数形式化为式(1),其中$ {U}_{i}^{\mathrm{d}}\left(\boldsymbol{c}\right) $为防御者$ D $成功防御攻击者$ {A}_{i} $获得的收益.
$ \underset{\boldsymbol{c}\in C}{\mathrm{m}\mathrm{a}\mathrm{x}}\boldsymbol{F}\left(\boldsymbol{c}\right)=\left({U}_{1}^{\mathrm{d}}\left(\boldsymbol{c}\right),{U}_{2}^{\mathrm{d}}\left(\boldsymbol{c}\right),…,{U}_{N}^{\mathrm{d}}\left(\boldsymbol{c}\right)\right). $
在多目标优化中算法可能会找到多个解,但只有满足定义1中的帕累托支配(Pareto dominance)的解才满足要求. 定义2中的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $最优性和$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $解的概念被广泛用于解的比较和选择.
定义1. $ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $支配. 给定$ \boldsymbol{F}\left(\boldsymbol{c}\right) $与$ \boldsymbol{F}({\boldsymbol{c}'}) $,若$ {U}_{i}^{\mathrm{d}}\left(\boldsymbol{c}\boldsymbol{'}\right)\le {U}_{i}^{\mathrm{d}}\left(\boldsymbol{c}\right) $对于所有$ i\in \{1,2,…,N\} $都成立,则称$ \boldsymbol{c} $弱支配$ \boldsymbol{c}' $或$ \boldsymbol{F}\left(\boldsymbol{c}\right) $弱支配$ \boldsymbol{F}({\boldsymbol{c}'}) $,表示为$ \boldsymbol{c}\succcurlyeq {\boldsymbol{c}}' $. 若$ \boldsymbol{c}\succcurlyeq {\boldsymbol{c}}' $,并且存在$ j\in \{1,2,…,N\} $使得$ {U}_{j}^{\mathrm{d}}\left(\boldsymbol{c}\boldsymbol{'}\right) < {U}_{j}^{\mathrm{d}}\left(\boldsymbol{c}\right) $,则称$ \boldsymbol{c} $支配$ \boldsymbol{c}' $或$ \boldsymbol{F}\left(\boldsymbol{c}\right) $支配$ \boldsymbol{F}({\boldsymbol{c}'}) $,表示为$ \boldsymbol{c}\succ {\boldsymbol{c}}' $.
定义2. $ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $最优性和$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $解. 若不存在其他满足$ \boldsymbol{c}\boldsymbol{'}\succ \boldsymbol{c} $的$ {\boldsymbol{c}'}\in C $,则称覆盖向量$ \boldsymbol{c} $为$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $解. 非支配的覆盖向量集合称为$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $集,相应的收益向量集合在目标空间中的分布称为$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿.
在双人Stackelberg博弈中,$ {U}_{i} $包含$ {A}_{i} $的综合收益$ {U}_{i}^{\mathrm{a}}(\boldsymbol{c},{\boldsymbol{a}}_{i}) $和$ D $的综合收益$ {U}_{i}^{\mathrm{d}}(\boldsymbol{c},{\boldsymbol{a}}_{i}) $,分别表示对给定的策略$ (\boldsymbol{c},{\boldsymbol{a}}_{i}),{A}_{i} $或$ D $在$ T $个被保护对象上的收益.
$ U_i^{\mathrm{a}}\left(\boldsymbol{c},\boldsymbol{a}_i\right)=\displaystyle\sum_{t=1}^Ta_{it}U_i^{\mathrm{a}}\left(c_t\right), $
$ U_i^{\mathrm{d}}\left(\boldsymbol{c},\boldsymbol{a}_i\right)=\displaystyle\sum_{t=1}^Ta_{it}U_i^{\mathrm{d}}\left(c_t\right), $
其中,式(2)(3)中的$ {U}_{i}^{\mathrm{a}}\left({c}_{t}\right) $和$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $分别表示$ {A}_{i} $和$ D $在单个保护对象$ t $上的收益. $ {U}_{i}^{\mathrm{a}}\left({c}_{t}\right) $或$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $是关于覆盖概率$ {c}_{t} $的线性函数[16],如式(4)(5)所示. 如果被攻击对象$ a{t}_{i} $被完全覆盖(即$ {c}_{t}=1 $),$ {A}_{i} $或$ D $的收益记为$ {U}_{i}^{\mathrm{c},\mathrm{a}}\left(t\right) $或$ {U}_{i}^{\mathrm{c},\mathrm{d}}\left(t\right) $. 如果$ a{t}_{i} $完全未被覆盖(即$ {c}_{t}=0 $),$ {A}_{i} $或$ D $的收益记为$ {U}_{i}^{\mathrm{u},\mathrm{a}}\left(t\right) $或$ {U}_{i}^{\mathrm{u},\mathrm{d}}\left(t\right) $. 具体线性关系为
$ U_i^{\mathrm{a}}\left(c_t\right)=c_tU_i^{\mathrm{c},\mathrm{a}}\left(t\right)+\left(1-c_t\right)U_i^{\mathrm{u},\mathrm{a}}\left(t\right), $
$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right)={c}_{t}{U}_{i}^{\mathrm{c},\mathrm{d}}\left(t\right)+{\left(1-{c}_{t}\right)U}_{i}^{\mathrm{u},\mathrm{d}}\left(t\right). $
式(4)(5)中,由于$ {U}_{i}^{\mathrm{c},\mathrm{a}},{U}_{i}^{\mathrm{c},\mathrm{d}} $和$ {U}_{i}^{\mathrm{u},\mathrm{a}},{U}_{i}^{\mathrm{u},\mathrm{d}} $满足假设$ {U}_{i}^{\mathrm{c},\mathrm{a}}\le {U}_{i}^{\mathrm{u},\mathrm{a}} $和$ {U}_{i}^{\mathrm{c},\mathrm{d}}\ge {U}_{i}^{\mathrm{u},\mathrm{d}} $,因此$ {A}_{i} $不希望$ a{t}_{i} $被覆盖,而防御者则相反.
在完全理性的安全博弈中,给定$ \boldsymbol{c} $,$ {A}_{i} $和$ D $的最佳响应(best response)定义为最大化它们的收益的策略集合. 具体而言,$ {A}_{i} $的最佳响应$ {BR}_{i}^{\mathrm{a}}\left(\boldsymbol{c}\right) $被定义为$ T $个被保护对象中最具吸引力的保护对象的集合,而$ D $的最佳响应$ {BR}_{i}^{\mathrm{d}}\left(\boldsymbol{c}\right) $被定义为$ {BR}_{i}^{\mathrm{a}}\left(\boldsymbol{c}\right) $中对$ D $最有利的目标的集合.
$ BR_i^{\mathrm{a}}\left(\boldsymbol{c}\right)=\left\{t\mid U_i^{\mathrm{a}}\left(c_t\right)\ge U_i^{\mathrm{a}}\left(c_{t'}\right)\right\}, $
$ BR_i^{\mathrm{d}}\left(\boldsymbol{c}\right)=\left\{t|U_i^{\mathrm{d}}\left(c_t\right)\ge U_i^{\mathrm{d}}\left(c_{t'}\right)\right\}, $
式(6)(7)分别对集合$ \{1,2,…,N\} $和集合$ {BR}_{i}^{\mathrm{a}}\left(\boldsymbol{c}\right) $做了取最大元素的$ \mathrm{m}\mathrm{a}\mathrm{x} $操作,而$ \mathrm{m}\mathrm{a}\mathrm{x} $操作是不可微的. 同时,$ B{R}_{i}^{\mathrm{d}} $不止受$ {c}_{t} $的影响,还受到隐式变量$ B{R}_{i}^{\mathrm{a}} $的影响,这使得$ {BR}_{i}^{\mathrm{d}}\left(\boldsymbol{c}\right) $的优化十分复杂,大规模场景下尤甚. 式(6)刻画了对$ {A}_{i} $最有吸引力的被保护对象的集合$ {BR}_{i}^{\mathrm{a}}\left(\boldsymbol{c}\right) $,也被记为$ {\varGamma }_{i}\left(\boldsymbol{c}\right) $. $ {\varGamma }_{i}\left(\boldsymbol{c}\right) $在后文中简写为$ {\varGamma }_{i},\left|{\varGamma }_{i}\right|\subseteq \{\mathrm{1,2},…, T\} $. SDES[13]指出,只有分配资源给$ {\varGamma }_{i} $中的目标才会增加$ D $的收益$ {U}_{i}^{\mathrm{d}}\left(\boldsymbol{c}\right) $.
式(2)(3)描述了$ {A}_{i} $和$ D $策略与收益之间的关系. 式(6)(7)描述了$ {A}_{i} $和$ D $相互之间的最佳响应. 在完全理性的假设下,基本的SG过程如下所述:
1) $ D $在$ T $个被保护对象上分配覆盖向量,记作$ \boldsymbol{c} $;
2) $ {A}_{i} $攻击$ {BR}_{i}^{\mathrm{a}}\left(\boldsymbol{c}\right) $中的$ t $,返回$ \underset{t\in \{\mathrm{1,2},…,T\}}{\mathrm{max}}{U}_{i}^{\mathrm{a}}\left({c}_{t}\right) $,其中$ {A}_{i} $选择的保护对象称为被攻击对象$ {at}_{i} $;
3) $ {A}_{i} $获得收益$ \underset{t\in \{\mathrm{1,2},…,T\}}{\mathrm{max}}{U}_{i}^{\mathrm{a}}\left({c}_{t}\right) $;
4) 在$ {A}_{i} $采取最佳响应后,$ D $从$ {\varGamma }_{i} $中选择$ t $,以最大化收益$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $;
5) $ D $获得收益$ \underset{t\in {\varGamma }_{i}}{\mathrm{max}}{U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $.
本文基于SDES展开了进一步深入研究. SDES包含离散化、优化、评估和解的精炼等4个组件. 具体而言,离散化组件负责将MOSG任务从高维阶梯函数[13]优化问题转化为低维离散组合优化问题. 优化组件采用多目标演化算法NSGA-III[21]来求解低维组合优化问题. 评估组件采用贪心决策将低维解还原成高维解,以在原始解空间中评估对应解的收益. 最后,解的精炼组件尝试改进解集的收敛性.
算法1. SDES框架.
输入:随机初始化的$ T $-长度的连续解$ \boldsymbol{c} $;
输出:高质量的$ T $-长度的连续解$ \boldsymbol{c} $.
① 使用离散化组件将$ T $-长度高维连续解离散化 为$ N $-长度低维离散解,其中$ N\ll T $;
② while 未达到终止条件
③ 使用优化组件的NSGA-III算法优化低维离  散解;
④ 通过贪心决策逐位优化将低维解还原为高  维连续解;
⑤ 评估高维连续解并将解的适应度返回给优  化组件;
⑥ end while
⑦ 使用解的精炼组件精炼最终输出的高维连续 解的集合;
⑧ return 高质量的高维连续解的集合.
SDES提供了解大规模MOSG问题的可行思路:
1) 资源分配$ {c}_{t} $的原搜索域是$ [0,1] $,但是SDES可以将搜索域从连续域转换到$ N $-长度的离散集合$ {\pi }_{{c}_{t}} $,并保证最优解$ {c}_{t}^{*} $存在于$ {\pi }_{{c}_{t}} $中(具体的离散化方案参见SDES[13]). MOSG问题被转换为组合优化问题,便于启发式方法求解.
2) MOSG任务扩展时,SDES的评估组件使用贪心策略规避了组合爆炸问题. 具体来说,SDES利用资源分配的独立性逐位优化$ {c}_{t} $. 贪心策略使模型复杂度从$ O\left({N}^{T}\right) $降至$ O\left(NT\right) $. 此外,贪心策略还提供了找到最优解的收敛性理论假设,称为分割假设,参见假设1.
假设1. 分割假设[13]. 贪心策略在第$ t $轮优化$ {c}_{t} $时,假设其在攻击集并集$ U=\underset{i=1}{\stackrel{N}{\cup }}{\varGamma }_{i} $中选中的对应的候选集$ {\pi }_{{c}_{t}} $是最小的候选集之一.
SDES想要最终找到$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿上的解要求贪心决策在$ T $轮中都满足假设1. 但是随着攻击者数量$ N $和保护对象数量$ T $的增加,贪心策略越来越难以保证找到最优解. 因此在大规模情况下,贪心策略可能无法保证收敛. 虽然SDES框架额外设计了解的精炼组件来解决上述问题,但这使SDES框架变得更加复杂.
大规模多目标博弈任务是一个高维约束优化问题[9-10]. SDES[13]使用完全冷漠[16](complete indifference)将MOSG问题转化为组合优化问题[13],其可以通过常规的启发式方法[21-22]来解决. 完全冷漠描述了攻击者关注被保护对象的偏好,详见引理1.
引理1. 完全冷漠[16]. 攻击者$ {A}_{i} $对于$ {\varGamma }_{i} $中的$ t $表现出相同的兴趣,但对于$ \{\mathrm{1,2},…,T\}\setminus {\varGamma }_{i} $中的$ t' $表现出完全冷漠.
1)动机. 虽然MOSG问题被转化为一个组合优化问题,但随着问题规模的增大,求解难度也急剧增加. 例如,分量$ {c}_{i} $的搜索空间大小为$ N $,因此SDES框架下的MOSG问题的样本复杂度是一个$ O({T}^{N}) $的组合优化问题. 为缓解维数灾难,SDES框架采用贪心策略来解决组合优化问题. 然而,贪心策略要求假设1在$ T $次迭代中都能够满足. 随着MOSG任务规模的扩大,假设1变得难以满足. 为消除大规模问题中贪心策略的负面影响,SDES框架设计了一个额外的解的精炼组件. 然而,包含太多阶段性组件的框架面临阶段耦合的风险,这增加了框架的复杂性和不稳定性. 因此,在大规模 MOSG 任务中解决组合优化问题的贪心策略可能并不是一个好方案.
基于SDES框架[13],本文提出了基于优先级的演化大规模多目标安全博弈框架SDES-P. 相较于SDES框架,SDES-P保留了离散化和优化组件,重新设计了评估组件,并且移除解的精炼组件,详见图1(a). 现有研究[13,16]表明,MOSG先验在解决组合优化问题时具有潜在的优势. 具体包括:①使用更多资源的解更有可能获得更优的收益[13];②释放不被攻击者关心的保护对象的资源对收益的影响较小[16]. 基于先验①,本文首先设计了基于完全冷漠定理的解初始化策略. 基于先验②,本文分别设计了基于优先级的可行解搜索策略和基于优先级的演化局部搜索策略. 评估组件的3个策略如图1(b)所示. 通过这3个策略的组合,SDES-P的样本复杂度在保持与SDES相近的前提下,能找到一个多样性和收敛性更好的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿. 本文提出的SDES-P框架比SDES更为精简,降低了阶段耦合的风险.
2)目标. 与SDES框架相比,得益于优先级先验知识[13,16],SDES-P具有更简单的框架和更强大的评估组件. SDES-P能够实现以下目标:
①探索MOSG先验知识的影响. 即使没有贪心策略,使用MOSG优先级先验的SDES-P也可以有效地解决组合优化问题,并获得高质量解.
②简化SDES框架并降低阶段耦合风险. 借助新设计的评估组件,SDES-P可以在不依赖解的精炼组件的情况下找到具有良好收敛性和多样性的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿,降低不同组件之间高度耦合带来的风险.
③提升求解质量的同时保持算法的可扩展性. 我们力求SDES-P在大规模MOSG任务中提高收敛性以及求解质量,并且保持SDES框架的规模可扩展性优势.
本节首先利用定理1缩小解初始化的范围,然后利用从SDES中获得的先验知识制定了一个启发式的解初始化策略.
定理1[13]. 如果 $ t\in \bar{U} $,则$ {c}_{t}=0 $,否则$ {c}_{t}\in {\pi }_{{c}_{t}} $.
定理1提供了一种解的初始化思路. 在定理1中,我们定义$ U=\underset{i\in \{\mathrm{1,2},…,N\}}{\cup {\varGamma }_{i}} $和$ \bar{U}=\{\mathrm{1,2},…,T\}\setminus U $. 由引理1可知,$ D $的综合收益$ ({U}_{1}^{\mathrm{d}}\left(\boldsymbol{c}\right),{U}_{2}^{\mathrm{d}}\left(\boldsymbol{c}\right),…,{U}_{N}^{\mathrm{d}}(\boldsymbol{c}\left)\right) $仅受到$ U $中目标资源配置的影响. 因此,$ \bar{U} $中的保护对象拥有的资源在初始化时分配为$ 0 $. 对于$ U $中的保护对象$ t $,最佳资源分配方案$ {c}_{t}^{*} $的搜索域从连续空间$ [0,1] $离散化为集合$ {\pi }_{{c}_{t}} $,其中$ \left|{\pi }_{{c}_{t}}\right|\le N $.
另一方面,SDES框架的贪心策略发现在各种问题规模中,高质量的解$ \boldsymbol{c} $都倾向于选择备选集$ {\pi }_{{c}_{t}} $中具有最大资源的备选方案$ {c}_{t} $. 因此,一个可行的想法是将每个组成部分$ {c}_{t} $初始化为资源最多的备选方案.
$ {c}_{t}=\left\{\begin{aligned}& {\mathrm{max}}\left({\pi }_{{c}_{t}}^{1},…,{\pi }_{{c}_{t}}^{N}\right),t\in U.\\ & 0,其他.\end{aligned}\right. $
式(8)展示了每个组成$ {c}_{t} $的完全冷漠初始化策略. 对于所有$ t\in U $,其对应的$ {c}_{t} $被初始化为$ {\pi }_{{c}_{t}} $中资源数最大值. 根据式(3),单目标函数$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $与资源$ {c}_{t} $成正比. 因此,以最大资源初始化的备选方案在多目标任务中更有潜力.
3.1节启发式策略将解初始化为具有最大资源数量的解,通常会得到违反总资源限制的解,即$ {\left\|\boldsymbol{c}\right\|}_{1} > r\times T $. 因此,本文提出一种基于优先级的搜索策略来寻找可行解. 根据引理1,攻击者对$ \bar{U} $中的保护对象表现出完全的冷漠,因此$ U $中的保护对象的优先级高于$ \bar{U} $中的保护对象. 一个高优先级的保护对象具有以下特点:它可以释放资源的同时保持多目标优化的质量,因此释放高优先级保护对象拥有的资源可以使得初始解更接近可行解. 定义3定义了每次资源释放时可以释放的最小资源量$ {\varDelta }_{{c}_{t}} $,定理2从理论上保证了资源以最小资源释放量释放能最小化对单个防御者目标收益的影响. 进而该资源释放方式对防御者整体目标收益的影响有可能保持在可控范围内.
定义3. 最小资源释放量. 假设当前$ {c}_{t} $=$ {\pi }_{{c}_{t}}^{i},{c}_{t} $的最小资源释量记作$ {\varDelta }_{{c}_{t}}={\pi }_{{c}_{t}}^{i}-{\pi }_{{c}_{t}}^{i+1} $.
定理2. 释放资源影响最小化. 假设只有1个分量$ {c}_{t} $在每次更新$ \boldsymbol{c} $时发生变化,且资源以最小资源释放量被释放,$ \boldsymbol{c} $的这种更新方式对$ D $的收益$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $的影响最小.
证明. 由式(5)得知,$ D $的单个目标$ i $的收益$ {U}_{i}^{\mathrm{d}} $与资源分配量$ {c}_{t} $的关系为$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right)={c}_{t}{U}_{i}^{\mathrm{c},\mathrm{d}}\left(t\right)+\left(1-{c}_{t}\right)\times U_{i}^{\mathrm{u},\mathrm{d}}\left(t\right)$. 经过简单的恒等变换得到$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right)=({U}_{i}^{\mathrm{c},\mathrm{d}} \left(t\right)- {U}_{i}^{\mathrm{u},\mathrm{d}}(t\left)\right){c}_{t}+{U}_{i}^{\mathrm{u},\mathrm{d}}\left(t\right) $,其中防御者保护成功的收益$ {U}_{i}^{\mathrm{c},\mathrm{d}}\left(t\right) $一定不小于保护失败的收益$ {U}_{i}^{\mathrm{u},\mathrm{d}}\left(t\right) $.
在定理2中,假设分量$ {c}_{t}={\pi }_{{c}_{t}}^{i},\mathrm{其}\mathrm{中}{\pi }_{{c}_{t}}^{i} $表示当前第$ i $大的候选集. 若$ {c}_{t} $以定义3的最小资源释放量更新,相比于其他更小的候选集{$ {\pi }_{{c}_{t}}^{i+1},{\pi }_{{c}_{t}}^{i+2},…,{\pi }_{{c}_{t}}^{N} $},最小资源释放量策略对$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $的影响是最小的. 证毕.
注意:定义3中,上标$ i $表示$ {\pi }_{{c}_{t}}^{i} $是$ {\pi }_{{c}_{t}} $中第$ i $大的元素. 定理2中更新方式的基本思想是,只有被$ {A}_{i} $选择的保护对象$ t $对$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $的计算有贡献[13],所有的$ {c}_{{t}'} $($ {t}'\ne t $)对防御者的收益没有影响. 因此,每次只更改1个分量不会对防御者的收益产生剧烈的影响. 值得注意的是,为了防止$ {c}_{t} $的资源减少过多而引起其余$ {A}_{i} $的注意,$ {c}_{t} $应以最小资源量$ {\varDelta }_{{c}_{t}} $释放资源.
SDES-P的基于优先级的可行解搜索策略见算法2. SDES-P采用了随机无重复采样的方式探索所有保护对象. 在选择更新的分量时,$ t\in \bar{U} $具有更高的优先级(行③). 每次更新$ \boldsymbol{c} $时,只更新其中1个分量$ {c}_{t} $,更新$ {c}_{t} $时以最小资源释放量$ {\varDelta }_{{c}_{t}} $(定义3)进行更新(行④). 更新过程直到找到一个可行解 $ \tilde{\boldsymbol{c}} $为止. $ \tilde{\boldsymbol{c}} $是一个资源使用量大的高质量可行解.
算法2. 基于优先级的可行解搜索算法.
输入:完全冷漠初始化的解$ \boldsymbol{c} $,资源总量$ r\times T,\boldsymbol{c} $所有分量的备选集$ \{{\pi }_{{c}_{1}},{\pi }_{{c}_{2}},…,{\pi }_{{c}_{T}}\} $;
输出:高质量的可行解 $ \tilde{\boldsymbol{c}} $.
① while $ {\left\|\boldsymbol{c}\right\|}_{1} > r\times T $
② 以$ \boldsymbol{c} $更新$ U $与$ \bar{U} $,见式(6);
③ 分别随机打乱$ U $与$ \bar{U} $,生成有序集合$ {\varGamma }_{\mathrm{p}\mathrm{r}\mathrm{i}}\leftarrow $   $\bar{U}\cup U $. 在生成的有序集合$ {\varGamma }_{\mathrm{p}\mathrm{r}\mathrm{i}} $中,要求优  先级高的$ \bar{U} $的$ t\mathrm{'} $排列在优先级低的$ U $的$ t $  之前,$ \forall {t'}\in \bar{U}, \forall t\in U $;
④ 寻找$ {\varGamma }_{\mathrm{p}\mathrm{r}\mathrm{i}} $中第1个没被选中过的$ t,{c}_{t}\leftarrow {c}_{t}-{\varDelta }_{{c}_{t}} $;
⑤ end while
⑥ return 高质量的可行解 $ \tilde{\boldsymbol{c}} $.
3.2节策略找到了一个资源使用量较大的可行解$ \tilde{\boldsymbol{c}} $,这与安全博弈的直觉相符,因为更高的资源分配可能会获得更好的综合收益. 然而,在异质攻击者的情况下,过多的资源分配可能会对综合收益造成负面影响. 具体而言,当分配大量资源给保护对象$ t $,期望通过防御$ {A}_{i} $以追求更高收益$ {U}_{i}^{\mathrm{d}}\left({c}_{t}\right) $时,由于资源有限,其他$ t' $会因为资源不足而遭到其他$ {A}_{j} $的攻击,从而降低综合收益. 这是因为分配的资源$ {c}_{t} $可能会使得保护对象$ t $对于$ {A}_{j} $不再具有吸引力,从而导致$ {A}_{j} $攻击其他分配了较少资源的保护对象$ {t}' $,最终$ D $获得的$ {U}_{j}^{\mathrm{d}}\left({c}_{{t}'}\right) $低于$ {U}_{j}^{\mathrm{d}}\left({c}_{t}\right) $. 这种性质使得贪心SDES框架很难满足假设1,并且假设达成难度随着问题规模的扩大而增加. 上述问题源于$ {A}_{i} $的异质性,即防御者$ D $需要指定不同分配方案防御$ {A}_{i} $,但$ D $最终只能采用其中一种方案. $ D $的选择会由于$ {A}_{i} $的异质性产生冲突,并随问题规模扩大而愈发严重. 总之,在异质攻击者的情况下,$ D $不能仅通过增加资源分配来提高综合收益,使用大量资源的可行解不一定是最优解.
一种最大化综合收益的可行方法是基于高质量可行解的局部搜索策略. 局部搜索策略能改善$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿的质量,包括收敛性和多样性[23–25]. 本节介绍了基于优先级的演化局部搜索算法,详见算法3. 首先,算法3从算法2找到的可行解出发探索使用更少资源的解. 在资源使用较少的方向上进行探索,不仅可以确保新解是可行解,还有可能找到更高质量的新解[13].
算法3. 基于优先级的演化局部搜索算法.
输入:可行解搜索算法找到的高质量可行解$ \tilde{\boldsymbol{c}} $,资源总量$ r\times T $,$ \boldsymbol{c} $分量的备选集$ \{{\pi }_{{c}_{1}},{\pi }_{{c}_{2}},…,{\pi }_{{c}_{T}}\} $;
输出:$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿$ C' $.
① $ C'\leftarrow $ $ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿初始化$ \left\{\tilde{\boldsymbol{c}}\right\} $;
② 以$ \tilde{\boldsymbol{c}} $更新$ U $与$ \bar{U} $;
③ 随机打乱$ U $与$ \bar{U} $,若$ \bar{U}\ne \varnothing $,则$ {\varGamma }_{\mathrm{p}\mathrm{r}\mathrm{i}}=\bar{U} $,否则 $ {\varGamma }_{\mathrm{p}\mathrm{r}\mathrm{i}}=U $;
④ for ${t} $ in $ {\varGamma }_{\mathrm{p}\mathrm{r}\mathrm{i}} $
⑤  $ \boldsymbol{c}'\leftarrow $ 只更新 $ \tilde{\boldsymbol{c}} $ 的一个分量$ {\tilde{c}}_{t} $,$ {\tilde{c}}_{t}\leftarrow {\tilde{c}}_{t}-{\varDelta }_{{\tilde{c}}_{t}} $;
⑥  $ C'\leftarrow $ 保留$ {C}'\cup \left\{\boldsymbol{c}\boldsymbol{'}\right\} $中的非支配解;
⑦ end for
⑧ return $ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿$ C' $.
算法3的关键思想是一步减少$ \tilde{\boldsymbol{c}} $中的某个分量以得到一个新的可行解$ {\boldsymbol{c}}' $. 类似于基于优先级的可行解搜索策略,优先级先验体现在$ U $与$ \bar{U} $的分组(见定理1)和最小资源释放量$ {\varDelta }_{{\tilde{c}}_{t}} $(见定义3)上,能够引导算法选择要减少的分量以及量化减少的数量. 具体来说,行③中,演化局部搜索策略优先探索$ t\in \bar{U} $,除非$ \bar{U}=\mathrm{\varnothing } $. 此外,行⑤资源$ {\tilde{c}}_{t} $的减少量遵循定义3. 最后,$ {\boldsymbol{c}}' $和$ \tilde{\boldsymbol{c}} $的非支配解被保留为$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿$ {C}' $.
本节首先讨论了SDES-P和SDES之间在组件级别上的关系,包括相似和差异之处. 然后给出了SDES-P中评估组件的伪代码,并展示了SDES-P在解决组合优化问题上的优越性. 最后展示了SDES-P和SDES在$ O\left(NT\right) $采样复杂度方面的相似之处.
SDES-P和SDES之间组件层面的关系为SDES[13] 包括离散化、优化、评估和解的精炼等4个组件,而SDES-P 使用了除解的精炼组件外的同功能组件,并对评估组件进行了深刻改进. 具体而言,SDES-P和SDES都以低维优化、高维评估的思想处理大规模问题. 因此,2个框架都包含离散化、优化和评估组件. 此外,2个框架的评估组件都面临组合爆炸的问题,但是它们的解决方式不同. 特别地,SDES-P在优先级的指导下搜索高质量的解. 在大规模MOSG中,SDES-P比SDES更不容易违反假设1. 此外,SDES-P不依赖于解的精炼组件,比SDES更简单、耦合风险更小. 这些差异将在下面详细介绍.
SDES-P的优越性在于解决组合优化问题时使用了MOSG的优先级先验. 对于SDES,贪心策略避免了组合优化的$ O\left(NT\right) $样本复杂度,但随着问题规模的增加,假设1愈加难以满足. 对于SDES-P,MOSG先验信息被用来解决组合优化问题. 具体而言,定理1表明算法寻优中只需搜索$ t\in U $,且$ t\in \bar{U} $上分配的资源具有更高的释放优先级. 定义3指定了需要释放的最小资源量. 此外,SDES-P首先找到高质量的可行解,然后基于可行解进行局部探索以获得更高质量的解. 因此SDES-P不像SDES一样面临假设1随着问题规模增加而变得难以满足的问题. 此外,SDES中的贪心策略只返回1个非支配解,而SDES-P中的演化局部搜索策略可以返回一个包含多个非支配解的非支配解集$ C' $.
算法样本复杂度的量级同阶. SDES-P 评估组件的伪代码展示在算法4中. 在算法4中,评估组件的每次迭代都经过完整的完全冷漠初始化策略、基于优先级的可行解搜索策略和基于优先级的演化局部搜索策略. 其中复杂度最高的策略是可行解搜索策略,参见算法2. 具体而言,更新长度为$ T $的$ \boldsymbol{c} $时,每次只能更改一个分量$ {c}_{t} $. 同时定理2表明,每次算法2更新$ {c}_{t} $时,使用的$ {\pi }_{{c}_{t}} $元素都比当前的$ {c}_{t} $小,并且由于所有$ {c}_{t} $的初始值都设置为$ {\pi }_{{c}_{t}} $中的最大值以及$ \left|{\pi }_{{c}_{t}}\right|\le N $,因此整个评估组件的最差时间复杂度为 $ O\left(NT\right) $,因此SDES-P的评估组件与SDES 框架的评估组件具有相似的样本复杂度.
算法4. SDES-P的评估组件.
输入:$ \boldsymbol{c} $所有分量的备选集{$ {\pi }_{{c}_{1}},{\pi }_{{c}_{2}},…,{\pi }_{{c}_{T}} $};
输出:$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿$ C' $.
① 以完全冷漠初始化策略初始化解$ \boldsymbol{c} $,见式(8);
② $ \boldsymbol{c}\leftarrow $ 以基于优先级的可行解搜索策略寻找资 源使用量大的可行解,见算法2;
③ $ C'\leftarrow $ 基于优先级的演化局部搜索策略,见算 法3;
④ return $ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿$ C' $.
SDES-P的实验环境与SDES[13]保持同阶. 所有实验都在随机拟真MOSG基准测试集[9-10,16]上进行. 以下所有MOSG任务都为最小化任务. 主要的实验设置包括:
1) MOSG问题规模主要受到目标数量$ T $和攻击者数量$ N $的影响,分别满足约束条件:$ 3\le N\le 20 $,$ T\in \{25,50,75,100,200,400,600,800,1\;000 $}.
2) 随机生成的MOSG问题的配置包括资源比$ r$、防御者D和攻击者$ {A}_{i} $的成功和失败的收益分布. 资源比$ r $控制资源总量$ r\times T $. 由于资源有限,通常资源比$ r \ll 1$,我们的实验中选择$ r=0.2 $. 此外,$ D $和$ A_i $的成功收益遵循[1, 10]的均匀整数分布,而失败收益遵循[$ - $10, $ - $1]的均匀整数分布.
3) 其余实验设置包括终止条件和编程细节. 算法的运行时间以该算法从开始到收敛的时钟时间为准. 本文在具体实验中会设置最大等待时间,若算法收敛所需的时间超过最大等待时间,则认为算法超时. 编程语言为Python,硬件条件为255 AMD EPYC 7742 64-Core处理器.
本文同时比较了6种算法,包括基于$ \epsilon $-约束框架的4种精确算法和基于SDES框架的2种近似算法. $ \epsilon $-约束算法包括ORIGAMI-M[9]和ORIGAMI-A[9] 、ORIGAMI-M-BS[10]和DIRECT-MIN-COV[10]. 所有$ \epsilon $-约束算法都使用步长$ \epsilon=1 $. ORIGAMI-A使用阈值$ \alpha =0.001 $进行二分搜索决定是否终止. SDES算法包括SDES基线算法[13]和本文提出的SDES-P.
定义2中的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $支配关系是单个解比较时的评估准则,本节介绍的反转世代距离+ (modified inverted generational distance,IGD+)[26]和超体积(hypervolume,HV)[27]是$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $集合的评估准则,用于算法评估. $ IG{D}^{+} $衡量参考$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿到$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $近似前沿的距离,而$ HV $衡量$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿的收敛性和多样性.
1)$ IG{D}^{+} $. $IG{D}^{+} $[26]是$ IGD $[28]的改进版. 在$ IGD\left(C{'}\right)= \dfrac{1}{\left|Z\right|} \left( \displaystyle\sum_{i=1} ^{\left|Z\right|}{\hat{d}}_{i}^{p} \right)^{ \tfrac{1}{p}} $中,$ IGD $计算从参考$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{前}\mathrm{沿}Z $到$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $近似前沿$ C' $的欧几里得距离. 具体来说,$ IGD $将$ Z $中每个点分别与$ C' $中的最近点组成点对,并计算所有点对的欧几里得距离,形式化为 $ {\hat{d}}_{i} = \sqrt{ (\boldsymbol{c}'_1 -{\boldsymbol{z}}_1)^2+ … +(\boldsymbol{c}'_{\rm T}-{\boldsymbol{z}}_{\rm T})^2} $如式(9)所示,$ IG{D}^{+} $规定只有正距离的分量才能做出贡献,形式化为
该改进保证了$ IG{D}^{+} $满足弱$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $条件,而$ IGD $则不能保证满足这一条件[26]. 在本文指定P=1.
$ {IGD}^+\left(C{'}\right)=\frac{1}{\left|Z\right|}{\sum _{i=1}^{\left|Z\right|}{{d}_{i}}}. $
2)$ HV $. $HV $[27]描述了被$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $近似前沿支配的空间体积,可以表示为
$ HV\left(C{'},\boldsymbol{r}\right)=\mathcal{L}\left(\underset{{\boldsymbol{c}}'\in {C'}}{\cup }\left\{\boldsymbol{b}|{\boldsymbol{c}}'\succcurlyeq \boldsymbol{b}\succcurlyeq \boldsymbol{r}\right\}\right), $
其中$ {C}' $为待评估算法找到的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $近似前沿,$ \boldsymbol{r} $为事先准备好的参考点,$ \mathcal{L}(\cdot ) $为集合的勒贝格测度$ \mathcal{L}\left(B\right)= {\int }_{\boldsymbol{b}\in B}^{}{I}_{B}\left(\boldsymbol{b}\right)\mathrm{d}\boldsymbol{b} $. $ {I}_{B} $为集合$ B $的特征函数,若$ \boldsymbol{b}\in B $,则$ {I}_{B}\left(\boldsymbol{b}\right)= 1 $,否则$ {I}_{B}\left(\boldsymbol{b}\right)=0,{\boldsymbol{c}}'\succcurlyeq \boldsymbol{b} $表示$ {\boldsymbol{c}}' $支配$ \boldsymbol{b} $,见定义1.
$ HV $优点是:1)$ HV $是唯一满足$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $条件的单位指标[29]. 这表示$ HV $是严格单调的[30],即能确保最大化$ HV $的解集是$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿. 较劣算法只会获得更小的$ HV $指标,但反之不成立[23]. 2)在计算$ HV $时只需要提供一个参考点,而$ IG{D}^{+} $需要整个$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿. 3)$ HV $可以同时评估算法的收敛性和多样性. 此外,其缺点是:1)虽然有许多$ HV $的实现,但其复杂度通常较高,已知的复杂度上限为$ O\left({\left|{Y}_{N}\right|}^{m/3}\mathrm{p}\mathrm{l}\mathrm{o}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}\right|{Y}_{N}\left|\right) $[31],其中ploy表示多项式复杂度. 2)不同算法的$ HV $相对关系受到参考点选择的影响[32],当算法性能相似时尤为明显.
为了找到一个具有良好收敛性和多样性的近似$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿,实验选择定量指标$ HV $和$ IG{D}^{+} $来评估算法的收敛性和多样性. 然而,$ IG{D}^{+} $评估需要参考$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿,而随机生成的MOSG任务无法提供参考$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿. 构建参考$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿的一种可行方法是收集所有求解器$ s\in S $产生的一组$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿,即$ P{F}_{S}^{p}=\underset{s\in S}{\cup }P{F}_{s}^{p} $,并删除$ P{F}_{S}^{p} $中的所有被支配解. 求解器$ S $包括2种基于SDES的算法和4种$ \epsilon $-约束算法.
SDES是解决大规模MOSG问题的有效框架[13]. 如3.4节所述,SDES-P框架的样本复杂度与SDES框架同级. 因此,本节讨论SDES-P框架在$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿质量方面相较于SDES框架的优越性. 性能实验包括:1)比较所有算法在所有MOSG问题规模上的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿质量与求解效率(见4.2.1节和4.2.3节);2) 仅改变目标数量或保护对象数量,随着MOSG问题规模的增加,研究所有算法发现的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿质量的变化(见4.2.2节). 需要说明的是,实验1)只展示所有算法都能完成的问题规模,而实验2)则没有这个限制,它展示算法在各个维度上的极限规模.
本实验展示了6种算法在21种MOSG问题上的结果,这些任务涵盖了各种问题规模. 21种问题规模分别包括:1) $ N=3 $时,$ T\in \{200,400,600,800,1\;000\} $;2) $ N=\mathrm{4,5},6 $时,$ T\in \{25,50,75,100 $}. 其中规模1) 考虑了大规模的被保护对象$ T $的场景,而规模2) 在保持中等规模$ T $的同时还考虑了中等规模的异质攻击者数量$ N $. 算法在求解每个问题规模时,只有在等待时间30 min内收敛才被记录为完成任务,否则记为超时. 图2显示了6种算法在21个问题规模下的$ IG{D}^{+} $和$ HV $指标上的排序分布.
首先就求解质量而言,SDES-P在大部分规模上能取得第一名,SDES次之,不过$ \epsilon $-约束算法也在少数几个问题上表现良好. 可以发现, $ \epsilon $-约束算法在中等规模$ N=5 $上的表现优于SDES系列的算法. 在中等规模问题中,所有算法都能在规定时间内完成任务,并且任务求解难度普遍大于小规模任务,因此精确算法凭借良好的收敛性能获得较高的$ IG{D}^{+} $和$ HV $指标评分. 同时,在各种规模上的实现也表明了$ \epsilon $-约束算法的特性与局限,即ORIGAMI-M-BS和DIRECT-MIN-COV算法虽然超时次数少但是求解质量低,而ORIGAMI-M和ORIGAMI-A算法虽然在中等问题上表现良好但是难以向大规模问题扩展. 而SDES系列算法则同时达成了求解质量与规模可扩展性的目标. 其次就规模可扩展性而言,SDES-P与SDES能按时完成所有任务的求解,SDES-P在$ IG{D}^{+} $和$ HV $上的总和表现超过了SDES. 这充分说明MOSG先验知识与优化技巧的重要贡献. 后文的消融性实验中还会详细分析本文核心工作的有效性.
SDES-P相比于SDES,使用了MOSG优先信息并降低了阶段耦合的风险. 在4.2.1节中,我们展示了SDES-P相比于在21个各种规模的MOSG任务中的优势. 4.2.1节讨论的任务很少涉及大规模场景. 事实上SDES-P在大规模MOSG任务中更具优势. 本实验分析了随着MOSG规模的增加(包括目标数和攻击者数量)的所有算法的性能表现. 由于$ \epsilon $-约束框架的算法难以在规定时间内完成大规模MOSG任务,参与对比的算法只有SDES,其中$ IG{D}^{+} $是最小化指标,$ HV $是最大化指标. $ IG{D}^{+} $和$ HV $的相对大小受任务难度影响[27],而任务难度不完全由问题规模决定,所以$ IG{D}^{+} $和$ HV $指标与问题规模间不存在严格的单调性. 因此,本节的实验结果采用表格呈现而非折线图. 此外由于$ HV $指标的计算复杂度随目标数增加指数级变化,因此结果展示中只分析了所有算法在$ {IGD}^{+} $指标上的表现.
表1和表2显示SDES-P分别在2个任务中取得了9/9和16/18个最优. 在中小规模的场景下,SDES-P和SDES各具优势,但是随着$ T $和$ N $扩大,SDES找到的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿质量快速下降,而SDES-P找到的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿质量存在下界保证,例如在表2的$ N=15\sim 20 $大规模实验中. 综上,$ T $和$ N $这2个维度单独变化的实验结果统计表明SDES-P相比SDES在求解质量上有很大的改进. 结合3.4节样本复杂度的分析,我们能看出SDES-P具备SDES的样本复杂度低、规模可扩展性强的优势,尤其在大规模场景下能找到相较于SDES收敛性、多样性更优的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿.
表1和表2展现出的SDES-P在大规模MOSG任务求解精度上的优势主要来自于本文提出的优先级策略. 在SDES-P中,优先级策略通过优先地释放$ t\in \bar{U} $上的资源,最小化异质攻击者$ {A}_{i} $意图改变的数量. 上述过程中,选择资源释放对象的搜索域为$ T $,而异质攻击者的数量为$ N $. 虽然SDES也引入了攻击集$ \{{\varGamma }_{1},{\varGamma }_{2},…,{\varGamma }_{N}\} $的概念,但是并没有明确提供一个显式的划分策略. 此外,SDES-P还在优化过程中实时更新$ U $. 具体来说,SDES-P每次做演化局部搜索前都会按照当前资源分配情况重新计算$ U $,保证每次分组的正确性. 随着问题规模$ T $和$ N $的扩大,采用静止的优先级策略的SDES的出错率将越来越大,导致不能很好地收敛到最优的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿上.
3.4节指出SDES-P框架求解MOSG任务的样本复杂度和SDES框架是相同量级的. 本节在大规模MOSG任务中验证. 大规模MOSG任务可分为2类:保护对象$ T $大规模和攻击者$ N $大规模,分别展示在图3(a)和图3(b)中. 其中$ N $只取到10是因为大部分对比算法都无法在最大等待时间30 min内收敛.
图3(a)(b)表明SDES-P框架在大规模保护对象和大规模攻击者场景下都明显优于基于$ \epsilon $-约束框架的对比算法,例如,ORIGAMI-M和ORIGAMI-A等. 同时,SDES-P的时耗变化率与SDES相似,说明它们的样本复杂度在同一个量级上. 结合图3(b)可以看出N=10时SDES-P耗时距离最大等待时间30 min较远,结合SDES-P关于N接近线性的变化率,可以预估SDES-P在更大规模的问题上的可行性. 因此,SDES-P的求解效率明显优于基于$ \epsilon $-约束框架的算法的同时,保持了SDES框架中良好的规模可扩展性.
在4.2.2节中,SDES-P在大规模MOSG问题上取得了明显的优势. SDES-P的主要贡献是重新设计的评估组件,包括完全冷漠初始化策略、基于优先级的可行解搜索策略和基于优先级的演化局部搜索策略. SDES-P的核心优势在于利用了MOSG优先级先验和使用了演化局部搜索策略. 其中,SDES-P的核心算法不涉及特别的超参数. 因此,本节专注于消融实验,讨论2点:1)优先级先验在SDES-P框架中的贡献;2)演化局部搜索策略在SDES-P框架中的贡献.
表3中设计了4个场景:1)SDES作为基线模型;2)SDES-P移除优先级先验;3)SDES-P移除局部搜索;4)完整的SDES-P框架. 具体而言,没有优先级先验的SDES-P意味着可行解搜索策略和演化局部搜索策略不再受优先级先验的指导,即目标$ {t}\in \bar{U} $不再被优先探索. 没有演化局部搜索策略的SDES-P意味着由基于优先级的可行解搜索策略找到的非支配解将直接用于构建$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿. 由于不同场景的复杂度不同,所以基于固定时间而非固定迭代次数来评估不同场景. 表3显示了4个场景下的$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{o} $前沿的$ HV $和$ {IGD}^{+} $指标.
消融实验选择$ N=5,T=200 $的MOSG问题规模,这是因为此时所有的精确解法都超时,该规模下的求解只能依赖基于SDES框架的算法. 表3展示了大规模问题下SDES基线和SDES-P的重要组件的表现. 具体地,算法1的SDES基线在$ HV $最大化指标以及$ IG{D}^{+} $最小化指标上都表现得最差,而算法4的SDES-P表现最好. 同时对比算法1和算法3,如果SDES-P不采用演化局部搜索策略,SDES-P会退化成SDES算法. 算法2和算法4的比较也说明了优先级先验的作用,算法2仅使用演化局部搜索但是没利用MOSG任务的优先级先验,虽然效果优于算法1和算法3,但是仍然和完整的SDES-P框架有一定差距,反映了MOSG优先级先验在进一步提升解的精度上的重要性. 同时这也是SDES-P框架能够去掉SDES框架中的解的精炼组件的重要原因.
本文提出了一种基于优先级先验的演化多目标安全博弈通用框架SDES-P,用于解决大规模多目标安全博弈任务. SDES-P是一个同时考虑了求解质量和规模可扩展性的MOSG简化求解框架,其通过优先级先验重新设计了评估组件并简化了SDES框架,可以在降低阶段耦合风险的同时解决各种规模的MOSG任务. 本文分析发现SDES-P可保持SDES样本复杂度低、规模可扩展性强的优势,并且各种规模下的MOSG对比实验表明, MOSG任务不满足收敛假设时,SDES-P可以找到相较于SDES收敛性、多样性更优的高质量Pareto前沿. 消融实验验证了SDES-P框架中各组件的必要性与贡献.
SDES-P框架的局限主要体现在样本复杂度和优先级预处理方面. 虽然在复杂度分析中SDES-P的评估组件和SDES的评估组件具有同级样本复杂度$ O\left(NT\right) $,但从大规模MOSG场景的性能实验中可以看出,SDES-P在目标维度上的规模可扩展性稍逊于SDES. 也即,SDES-P的复杂度常数项比SDES大. 虽然从实验上来看SDES-P相比于SDES的复杂度的常数项更大,但是相比于其他基于$ \epsilon $-约束框架的对比算法,基于演化算法的SDES-P算法是易于并行化加速的. 此外,SDES-P使用的优先级预处理的效果尚有进一步挖掘空间. 本文中的优先级预处理仅将目标分为2组:$ U $组和$ \bar{U} $组,并指定保护对象$ t\in \bar{U} $比$ t\in U $组的目标具有更高的释放资源的优先级. 不过,本文没有为属于同一组的2个被保护对象提供详细的分组方法. 然而,性能实验结果表明即使随机选择同一组的被保护对象,SDES-P也可以取得优越的结果,尤其是在大规模MOSG中,未来工作可以进一步完善MOSG优先级先验的分组策略.
作者贡献声明:吴宇鹏主要负责算法实现、实验实现、后期校对以及部分写作;钱鸿和周爱民负责论文的指导;王为业和张杨文辉主要参与部分的实验以及后期校对.

参考文献 引证文献
排序方式:
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
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
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
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)
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
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
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
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
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
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
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
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
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
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
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
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
2025年第62卷第2期
89
39
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202330463
  • 接收时间:2023-06-06
  • 首发时间:2026-11-10
  • 出版时间:2025-02-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2023-06-06
  • 修回日期:2024-01-03
  • 录用日期:2024-03-06
基金
作者信息
    1华东师范大学计算机科学与技术学院 上海 200062
    2华东师范大学上海智能教育研究院 上海 200062

通讯作者:

参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330463
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏