Bidirectional evolutionary heuristic for the minimum vertex-cover problem

Abstract

In this study, we have solved the minimum vertex-cover problem, NP-hard, by the means of genetic algorithms (GA). In prior studies, initial population on which GA iteratively run, was created randomly. However, we have improved this technique to create initial population and the population created has some useful properties such as decreasing the number of iterations of GA algorithm and gets rid of diversity problem, local solution problem. Initially, one chromosome is created and then the inversion of this chromosome is taken as another chromosome. If it is required to create an initial population with large set of chromosomes, then randomly created chromosomes can be divided into desired partitions and other chromosomes can be obtained by the complement of each partition at a time. Search is handled in bidirectional manner, and the initial population contains both ends of solution space. (C) 2002 Elsevier Science Ltd. All rights reserved.