A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems
- PDF / 395,690 Bytes
- 11 Pages / 595 x 842 pts (A4) Page_size
- 102 Downloads / 200 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems M Hi® Universite de Paris, France 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 modi®cations 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 speci®cally 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. Keywords: combinatorial optimization; genetic algorithms; heuristics; independent set
Introduction Unless P NP, many interesting combinatorial optimization problems cannot be solved exactly within a reasonable amount of time. Consequently, heuristics must be used to solve large realworld problems. Heuristic algorithms may be divided into two main classes: ®rst, the general purpose algorithms independent of the optimization problem and, on the other hand, the tailored algorithms especially designed for a given problem. In this paper, we present a genetic algorithm-based heuristic for solving the weighted maximum independent set (IS) and a complementary problem, namely, the weighted minimum vertex cover problem (VC) as well as the weighted maximum clique (MC) problem. We discuss a possible way for solving the weighted set packing (SP) problem by using the same approach. The described model concerns the general case where weights are associated with each variable of the considered problem. It deals with the unweighted versions as particular cases. First, we treat weighted IS and VC. These two problems are known to be equivalent with respect to their complexity.1,2 There is a simple relation between the cardinalities of an IS and a VC in a graph. Given a graph G, a VC is the complement of an IS with respect to the
Corrrespondence: Dr M Hi®, CERMSEM, Universite de Paris 1, PantheÂon-Sorbonne, 90 rue de Tolbiac 75634, Paris Cedex 13, France. e-mail: hi®@univ-paris1.fr
vertex set of G. Moreover, a method solving these two problems can also solve the MC problem. Indeed, given a graph G, s set of vertices constituting an independent set on where G induces a subgraph that constitutes a clique on G G is the complement of G constructed as follows:
x1 ; x2 is if and only if x1 and x2 are not adjacent in G. an edge of G Moreover, SP and IS are i
Data Loading...
