A Hybrid Encoded Memetic Algorithm for Set Covering Problem

Set covering problem (SCP) is a classical NP-hard problem with many practical applications. To solve SCP, a hybrid encoded memetic algorithm with three main techniques is proposed in this paper. Firstly, we introduce a hybrid encoding approach to define two genetic segments for each individual chromosome, in which the first segment encodes a solution, and the second segment encodes the learning information. Then, we provided a mutation operator guided by the scores associated with the gene bits. In particular, the gene bit with the higher score is more likely to be mutated. In addition, a local search with row weighting procedure is used to improve the solution quality. Finally, a fragment-crossover operator is proposed to share learning information between individuals. Experimental results on the benchmark instances from Beasley's OR Library show that the proposed hybrid encoded memetic algorithm produces competitive solutions in comparison with other meta-heuristics.