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 条
  • [1] On local search for weighted k-set packing
    Arkin, EM
    Hassin, R
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (03) : 640 - 648
  • [2] Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
    Bafna, V
    Narayanan, B
    Ravi, R
    [J]. DISCRETE APPLIED MATHEMATICS, 1996, 71 (1-3) : 41 - 53
  • [3] Berman P, 2000, LECT NOTES COMPUT SC, V1851, P214
  • [4] Greedy local improvement and weighted set packing approximation
    Chandra, B
    Halldórsson, MM
    [J]. JOURNAL OF ALGORITHMS, 2001, 39 (02) : 223 - 240
  • [5] A hybrid evolutionary approach for set packing problem
    Chaurasia S.N.
    Sundar S.
    Singh A.
    [J]. OPSEARCH, 2015, 52 (2) : 271 - 284
  • [6] An evolutionary algorithm based hyper-heuristic framework for the set packing problem
    Chaurasia, Sachchida Nand
    Kim, Joong Hoon
    [J]. INFORMATION SCIENCES, 2019, 505 : 1 - 31
  • [7] Improved approximation for 3-dimensional matching via bounded pathwidth local search
    Cygan, Marek
    [J]. 2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 509 - 518
  • [8] Combinatorial auctions: A survey
    de Vries, S
    Vohra, RV
    [J]. INFORMS JOURNAL ON COMPUTING, 2003, 15 (03) : 284 - 309
  • [9] GRASP for set packing problems
    Delorme, X
    Gandibleux, X
    Rodriguez, J
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 153 (03) : 564 - 580
  • [10] Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem
    Delorme, Xavier
    Gandibleux, Xavier
    Degoutin, Fabien
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 204 (02) : 206 - 217