A CLONALG-based Approach for the Set Covering Problem

In this paper, we propose a CLONALG-based simple heuristic, which is one of the most popular artificial immune system (AIS) models, for the non-unicost set covering problem (SCP). In addition, we have modified our heuristic to solve the unicost SCP. It is well known that SCP is an NP-hard problem that can model several real world situations such as crew scheduling in airlines, facility location problem, production planning in industry etc. In real cases, the problem instances can reach huge sizes, making the use of exact algorithms impractical. So, for finding practically efficient approaches for solving SCP, different kind of heuristic approaches have been applied in the literature. To the best of our knowledge, our work here is the first attempt to solve SCP using Artificial Immune System. We have evaluated the performance of our algorithm on a number of benchmark non-unicost instances. Computational results have shown that it is capable of producing high-quality solutions for non-unicost SCP. We have also performed some experiments on unicost instances that suggest that our heuristic also performs well on unicost SCP.