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 条
  • [31] Supplier behavior modeling and winner determination using parallel MDP
    Ray, Arun K.
    Jenamani, Mamata
    Mohapatra, Pratap K. J.
    [J]. EXPERT SYSTEMS WITH APPLICATIONS, 2011, 38 (05) : 4689 - 4697
  • [32] Pareto optimization for subset selection with dynamic cost constraints
    Roostapour, Vahid
    Neumann, Aneta
    Neumann, Frank
    Friedrich, Tobias
    [J]. ARTIFICIAL INTELLIGENCE, 2022, 302
  • [33] Sviridenko M, 2013, LECT NOTES COMPUT SC, V7965, P792, DOI 10.1007/978-3-642-39206-1_67
  • [34] Thiery T, 2023, Disc Algorithms, P1138
  • [35] A practical tutorial on solving optimization problems via PlatEMO
    Tian, Ye
    Zhu, Weijian
    Zhang, Xingyi
    Jin, Yaochu
    [J]. NEUROCOMPUTING, 2023, 518 : 190 - 205
  • [36] Velasquez R., 2006, OPERATIONS RES P 200, V2005, P425
  • [37] Fitness and Distance Based Local Search With Adaptive Differential Evolution for Multimodal Optimization Problems
    Wang, Zi-Jia
    Zhan, Zhi-Hui
    Li, Yun
    Kwong, Sam
    Jeon, Sang-Woon
    Zhang, Jun
    [J]. IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, 2023, 7 (03): : 684 - 699
  • [38] Superiority combination learning distributed particle swarm optimization for large-scale optimization
    Wang, Zi-Jia
    Yang, Qiang
    Zhang, Yu -Hui
    Chen, Shu-Hong
    Wang, Yuan -Gen
    [J]. APPLIED SOFT COMPUTING, 2023, 136
  • [39] Gene Targeting Differential Evolution: A Simple and Efficient Method for Large-Scale Optimization
    Wang, Zi-Jia
    Jian, Jun-Rong
    Zhan, Zhi-Hui
    Li, Yun
    Kwong, Sam
    Zhang, Jun
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2023, 27 (04) : 964 - 979
  • [40] Adaptive Estimation Distribution Distributed Differential Evolution for Multimodal Optimization Problems
    Wang, Zi-Jia
    Zhou, Yu-Ren
    Zhang, Jun
    [J]. IEEE TRANSACTIONS ON CYBERNETICS, 2022, 52 (07) : 6059 - 6070