A Hybrid Genetic Algorithm for Minimum Vertex Cover Problem.
Ketan V. Kotecha, Nilesh Gambhava · 2003
Minimum vertex cover problem (MVCP) is an NP-hard problem and it has numerous real life applications. This paper presents hybrid genetic algorithm (HGA) to solve MVCP efficiently. In this paper we have demonstrated that when local optimization technique is added to genetic algorithm to form HGA, it gives near to optimal solution speedy. We have developed new heuristic vertex crossover operator (HVX) especially for MVCP, which converges faster to the global optimal solution. HVX gives far better results compared to classical crossover operators. We have also studied the effect of mutation on optimal solution in MVCP.