| Autor: |
Youzhen Jin, Xiaoyun Xia, Zijia Wang, Xue Peng, Jun Zhang, Weizhi Liao |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Biomimetics, Vol 9, Iss 10, p 586 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2313-7673 |
| DOI: |
10.3390/biomimetics9100586 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|
