A Genetic Algorithm for the Minimum Vertex Cover Problem with Interval-Valued Fitness

Abstract

This paper presents a new genetic algorithm for the minimum vertex cover problem. It uses interval-valued fitness and greedy error correction to obtain phenotypes (candidate solutions). By the interval-valued fitness the fitness of the candidate solution is measured not only for the whole graph, but for some of its disjoint subgraphs. A new candidate solution is obtained from those subgraphs that have the best performance among the subgraphs of the candidates with the same set of vertices. The interval-valued fitness accelerates the search effectively for graphs with a great deal of nodes and relatively small numbers of edges. In the presented algorithm we prefer to distinguish genotypes and phenotypes and do not use Lamarckian inheritance. Phenotypes are easily generated by greedy error correction from the genotypes and, in this way, a larger variety of genomes can be used during the process.