A GENETIC ALGORITHM-BASED HEURISTIC FOR SOLVING THE WEIGHTED MAXIMUM INDEPENDENT SET AND SOME EQUIVALENT PROBLEMS

In this paper we present a genetic algorithm-based heuristic especiall y for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization proble ms. 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 th e heuristic-feasibility operator tailored specifically for the weighte d independent set. The performance of our algorithm was evaluated on s everal randomly generated problem instances for the weighted independe nt set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results sh ow that the proposed approach is able to produce high-quality solution s within reasonable computational times. This algorithm is easily para llelizable and this is one of its important features.