EUVIMEDEUVIMED entdecken
Crossref

A Hybrid Chemical Reaction Optimization Algorithm with Local Refinement for the Maximum Independent Set Problem

Lena Paul, Mia Katharina

Bulletin of Computer and Data Sciences · 2023

DOI: 10.71448/bcds2342-1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bulletin of Computer and Data Sciences, 2023. Verfasst von Lena Paul und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The maximum independent set (MIS) problem is a classical NP-hard problem that appears in diverse applications such as scheduling, wireless sensor networks, resource allocation, and bioinformatics. Metaheuristic approaches, including Chemical Reaction Optimization (CRO), have shown promising results on medium-sized instances; however, plain CRO typically relies on stochastic structural modifications and may require multiple runs to reach optimal or near-optimal independent sets. This paper proposes a hybrid (memetic) variant of CRO for the MIS problem in which each newly generated molecule is passed through a problem-specific local refinement procedure. The local step greedily expands partial independent sets and applies 1-swap/2-swap neighborhood moves to remove conflicts and increase the cardinality of the set. By combining the global exploration capability of CRO with the intensification of local search, the proposed method achieves higher-quality solutions, especially on dense graphs where conflicts are frequent. Experimental results on synthetic graphs of varying sizes and densities, as well as on standard benchmark instances, show that the hybrid CRO consistently outperforms the baseline CRO in terms of best solution, average solution, and number of runs needed to reach the best MIS. These findings indicate that embedding domain knowledge into CRO is an effective way to improve robustness without losing generality.

Zitieren

APA

Paul, L., & Katharina, M. (2023). A Hybrid Chemical Reaction Optimization Algorithm with Local Refinement for the Maximum Independent Set Problem. Bulletin of Computer and Data Sciences. https://doi.org/10.71448/bcds2342-1

Vancouver

Paul L, Katharina M. A Hybrid Chemical Reaction Optimization Algorithm with Local Refinement for the Maximum Independent Set Problem. Bulletin of Computer and Data Sciences. 2023. doi:10.71448/bcds2342-1

BibTeX
@article{Paul2023,
  author = {Paul, Lena and Katharina, Mia},
  title = {A Hybrid Chemical Reaction Optimization Algorithm with Local Refinement for the Maximum Independent Set Problem},
  journal = {Bulletin of Computer and Data Sciences},
  year = {2023},
  doi = {10.71448/bcds2342-1}
}
Kostenlos starten →