Set Packing Optimization by Evolutionary Algorithms with Theoretical Guarantees

被引:0
作者
Jin, Youzhen [1 ]
Xia, Xiaoyun [1 ]
Wang, Zijia [2 ]
Peng, Xue [3 ]
Zhang, Jun [4 ,5 ]
Liao, Weizhi [1 ]
机构
[1] Jiaxing Univ, Sch Informat Sci & Engn, Jiaxing 314001, Peoples R China
[2] Guangzhou Univ, Sch Comp Sci & Cyber Engn, Guangzhou 510006, Peoples R China
[3] Guangdong Polytech Normal Univ, Sch Math & Syst Sci, Guangzhou 510665, Peoples R China
[4] Nankai Univ, Coll Artificial Intelligence, Tianjin 300350, Peoples R China
[5] Hanyang Univ, Dept Elect & Elect Engn, Ansan 15588, South Korea
基金
中国国家自然科学基金;
关键词
set packing; evolutionary algorithms; local search; approximation algorithm; performance guarantee; approximation ratio; runtime analysis; PARTICLE SWARM OPTIMIZATION;
D O I
10.3390/biomimetics9100586
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
The set packing problem is a core NP-complete combinatorial optimization problem which aims to find the maximum collection of disjoint sets from a given collection of sets, S, over a ground set, U. Evolutionary algorithms (EAs) have been widely used as general-purpose global optimization methods and have shown promising performance for the set packing problem. While most previous studies are mainly based on experimentation, there is little theoretical investigation available in this area. In this study, we analyze the approximation performance of simplified versions of EAs, specifically the (1+1) EA, for the set packing problem from a theoretical perspective. Our analysis demonstrates that the (1+1) EA can provide an approximation guarantee in solving the k-set packing problem. Additionally, we construct a problem instance and prove that the (1+1) EA beats the local search algorithm on this specific instance. This proof reveals that evolutionary algorithms can have theoretical guarantees for solving NP-hard optimization problems.
引用
收藏
页数:13
相关论文
共 54 条
  • [11] Doerr B., 2021, ACM T EVOLUTIONARY L, V1, p16:1, DOI [10.1145/3472304, DOI 10.1145/3472304]
  • [12] Duppala S, 2023, PROCEEDINGS OF THE THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023, P391
  • [13] ONLINE SET PACKING
    Emek, Yuval
    Halldorsson, Magnus M.
    Mansour, Yishay
    Patt-Shamir, Boaz
    Radhakrishnan, Jaikumar
    Rawitz, Dror
    [J]. SIAM JOURNAL ON COMPUTING, 2012, 41 (04) : 728 - 746
  • [14] Furer Martin, 2014, Combinatorial Optimization. Third International Symposium, ISCO 2014. Revised Selected Papers. LNCS: 8596, P408, DOI 10.1007/978-3-319-09174-7_35
  • [15] On the Parameterized Complexity of Compact Set Packing
    Gadekar, Ameet
    [J]. ALGORITHMICA, 2024, 86 (11) : 3579 - 3597
  • [16] He J., 2024, Evol. Comput, DOI [10.1162/evcoa00349, DOI 10.1162/EVCOA00349]
  • [17] Average Drift Analysis and Population Scalability
    He, Jun
    Yao, Xin
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2017, 21 (03) : 426 - 439
  • [18] Average Convergence Rate of Evolutionary Algorithms
    He, Jun
    Lin, Guangming
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2016, 20 (02) : 316 - 321
  • [19] On the Easiest and Hardest Fitness Functions
    He, Jun
    Chen, Tianshi
    Yao, Xin
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2015, 19 (02) : 295 - 305
  • [20] Wireless sensor networks-based adaptive differential evolution for multimodal optimization problems ☆
    Huang, Yi-Biao
    Wang, Zi-Jia
    Zhang, Yu -Hui
    Wang, Yuan -Gen
    Kwong, Sam
    Zhang, Jun
    [J]. APPLIED SOFT COMPUTING, 2024, 158