This paper presents a new genetic algorithm for the minimum vertex cover problem. It uses interval valued fitness, greedy error correction to obtain phenotypes (candidate solutions). The interval valued fitness accelerates the search effectively at graphs with a lot of nodes and relatively small amount of edges. It is explained why we prefer to distinguish genotypes and phenotypes and do not use Lamarckian inheritance.