uğurlu, onur ege university - faculty of scienc - department of mathematics, turkey

A NEW HYBRID GENETIC ALGORITHM FOR VERTEX COVER PROBLEM

34116

The minimum vertex cover problem belongs to the class of NP-complete graph theoretical problems. This paper presents a hybrid genetic algorithm to solve minimum vertex cover problem. In this paper, it has been shown that when local optimization technique is added to genetic algorithm to form hybrid genetic algorithm, it gives more quality solution than simple genetic algorithm. Also, a new mutation operator has been developed especially for minimum vertex cover problem, which converges faster to the global optimal solution. The new hybrid genetic algorithm has been compared with the previous works. The experimental results have shown that the proposed algorithm can yield quality solutions in reasonable times.

277

Vertex cover problem , Hybrid algorithms , Genetic algorithms , Local optimization techniques

Anadolu University Journal of Science and Technology. A : Applied Sciences and Engineering

282