A new hybrid approach based on genetic algorithm for minimum vertex cover

摘要

Minimum vertex cover (MVC) problem is a NP-Hard optimization problem which we often encounter in real life applications like wireless sensor networks, graph theory, bioinformatics, social network analysis etc. To deal with this optimization problem in an efficient way, we introduce a new Hybrid Genetic algorithm (NHGA) to solve MVC problem. In this study, the proposed algorithm has also been tested on DIMACS benchmarks, BHOSLIB benchmarks and random graphs. Performance of NHGA is then compared with the simple Genetic algorithm (GA) and Clever Greedy algorithm. Consequently, experimental results show that NHGA finds better solutions than other algorithms for MVC, since it offers near to optimal solutions.