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.
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.
