Optimization of the Vertex Separation Problem with Genetic Algorithms
Héctor Joaquín Fraire Huacuja, Norberto Castillo–García · Advances in logistics, operations, and management science book series · 2016
The Vertex Separation Problem (VSP) is an NP-hard combinatorial optimization problem in the context of graph theory. The importance of studying VSP lies in its close relation with other problems. Thus, VSP has important practical applications in the contexts of very large scale integration design, computer language compiler design, natural language processing, order processing of manufactured products and bioinformatics. Up to our knowledge, there are only two trajectory-based metaheuristic algorithms for VSP documented in the literature. The main contribution of this chapter is that we extend the available heuristics to solve VSP by proposing a genetic algorithm (GA). It is of particular interest to study the impact of four different crossover operators in the algorithm performance. The experimental results showed that the order-based crossover is the best. Moreover, the best GA variant was compared with the best algorithm for VSP: GVNS. The results of this comparison showed that GVNS outperforms our best GA variant by approximately 1.54 times in solution quality.