A hybrid encoded memetic algorithm for set covering problem
Fang Xu, Jinlong Li · 2018
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 f or e ach 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.