Article ID: | iaor19982863 |
Country: | United Kingdom |
Volume: | 48 |
Issue: | 6 |
Start Page Number: | 612 |
End Page Number: | 622 |
Publication Date: | Jun 1997 |
Journal: | Journal of the Operational Research Society |
Authors: | Hifi Mhand |
Keywords: | heuristics |
In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.