A genetic algorithm applied to graph problems involving subsets of vertices

Many graph problems seek subsets of their vertices that maximize or minimize objective functions on the vertices. Among these are the capacitated p-median problem, the geometric connected dominating set problem, the capacitated k-center problem, and the traveling tourist problem. Prior genetic algorithms research in this area applied a simple mutation of an allele by random replacement. Recently an enhanced operator called hypermutation was developed, proving to be very effective for solving the capacitated p-median problem. We propose a GA with a new heuristic called the nearest four neighbors heuristic (N4N) for solving graph problems requiring a subset of vertices. It is an extension of the hypermutation operator. Genetic algorithms that use each of these three mutation operators (simple, hypermutation, N4N) are applied to instances of the four graph-subset problems listed above. Results show that our N4N heuristic obtained superior results compared to the hypermutation and the simple mutation operators in every test case.