A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

0.00 Avg rating0 Votes
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:
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.