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 条
  • [41] Adaptive Granularity Learning Distributed Particle Swarm Optimization for Large-Scale Optimization
    Wang, Zi-Jia
    Zhan, Zhi-Hui
    Kwong, Sam
    Jin, Hu
    Zhang, Jun
    [J]. IEEE TRANSACTIONS ON CYBERNETICS, 2021, 51 (03) : 1175 - 1188
  • [42] Automatic Niching Differential Evolution With Contour Prediction Approach for Multimodal Optimization Problems
    Wang, Zi-Jia
    Zhan, Zhi-Hui
    Lin, Ying
    Yu, Wei-Jie
    Wang, Hua
    Kwong, Sam
    Zhang, Jun
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2020, 24 (01) : 114 - 128
  • [43] Dynamic Group Learning Distributed Particle Swarm Optimization for Large-Scale Optimization and Its Application in Cloud Workflow Scheduling
    Wang, Zi-Jia
    Zhan, Zhi-Hui
    Yu, Wei-Jie
    Lin, Ying
    Zhang, Jie
    Gu, Tian-Long
    Zhang, Jun
    [J]. IEEE TRANSACTIONS ON CYBERNETICS, 2020, 50 (06) : 2715 - 2729
  • [44] Dual-Strategy Differential Evolution With Affinity Propagation Clustering for Multimodal Optimization Problems
    Wang, Zi-Jia
    Zhan, Zhi-Hui
    Lin, Ying
    Yu, Wei-Jie
    Yuan, Hua-Qiang
    Gu, Tian-Long
    Kwong, Sam
    Zhang, Jun
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2018, 22 (06) : 894 - 908
  • [45] Wegener I., 2003, EVOLUTIONARY OPTIMIZ, P349
  • [46] Two-stage heuristic algorithm with pseudo node-based model for electric vehicle routing problem
    Xia, Xiaoyun
    Zhuang, Helin
    Wang, Zijia
    Chen, Zefeng
    [J]. APPLIED SOFT COMPUTING, 2024, 165
  • [47] On the analysis of ant colony optimization for the maximum independent set problem
    Xia, Xiaoyun
    Peng, Xue
    Liao, Weizhi
    [J]. FRONTIERS OF COMPUTER SCIENCE, 2021, 15 (04)
  • [48] Performance Analysis of ACO on the Quadratic Assignment Problem
    Xia Xiaoyun
    Zhou Yuren
    [J]. CHINESE JOURNAL OF ELECTRONICS, 2018, 27 (01) : 26 - 34
  • [49] On the effectiveness of immune inspired mutation operators in some discrete optimization problems
    Xia, Xiaoyun
    Zhou, Yuren
    [J]. INFORMATION SCIENCES, 2018, 426 : 87 - 100
  • [50] Xue Peng, 2015, Cloud Computing and Security. First International Conference, ICCCS 2015. Revised Selected Papers: LNCS 9483, P448, DOI 10.1007/978-3-319-27051-7_38