Abstract
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.
TopIntroduction
The vertex separation problem (VSP) is an NP-hard combinatorial optimization problem (Lengauer, 1981) that asks for a linear ordering of the vertices of an input graph that minimizes the maximum number of vertex separators at each position of the ordering (Díaz, Petit, & Serna, 2002). VSP has important practical applications since it is strongly related to other important problems in a variety of contexts such as VLSI design (Leiserson, 1980; Linhares & Yanasse, 2002), computer language compiler design (Bodlaender, Gustedt, & Telle, 1998), natural language processing (Kornai & Tuza, 1992), order processing of manufactured products (Lopes & de Carvalho, 2010) and bioinformatics (Luque & Alba, 2005). Perhaps, one of the most important applications of VSP is the optimization of the layout area required to assemble a set of logical gates on an electronic circuit. Specifically, this application requires to assign a set of circuit nodes (gates) in an optimal sequence such that the number of tracks needed to cover the interconnection of the gates is minimized (De Oliveira & Lorena, 2002). In order to illustrate this application, consider the example depicted in Figure 1.
Figure 1. a) One possible ordering of the gates that requires seven tracks to allocate all the nets. b) Another possible ordering of the gates, this ordering only requires five tracks (optimal ordering). The gate numbers are at the top of the figures. This example was taken from (De Oliveira & Lorena, 2002)
In this example there are nine gates and seven nets. The nets represent the interconnection of the gates. The gate numbers are presented at the top of each figure. In Figure 1a is presented a configuration (ordering) of the gates such that the number of tracks required is seven. In other words, each net occupies one track in the circuit. Conversely, Figure 1b presents another configuration in which only five tracks are needed to connect the circuit completely. In this configuration two nets can share the same track. More precisely, the nets 
and 
(highlighted in red) occupy the second track and the nets 
and 
(highlighted in blue) share the fifth track. Notice that this example exhibits the importance of looking for a linear ordering of the gates such that the maximum number of tracks is minimized, and hence, the layout area is optimized.
Key Terms in this Chapter
Crossover Operator: The crossover operator is perhaps the main method of the genetic algorithms. The crossover operator combines the characteristics of two solutions (parents) in order to generate a new solution (offspring). This operator is inspired in the way in which the genetic code of one individual is inherited to its descendants in nature.
Linear Ordering: A linear ordering consists in arranging the vertices of the graph in a horizontal line. Mathematically, a linear ordering is the one-to-one mapping function , where is the set of vertices and is the number of vertices in the graph. In the linear ordering , the vertex is placed at the first position, the vertex at the second position and so on.
Graph: A graph is a mathematical abstraction of a collection of objects called vertices where some pairs of objects are connected by links called edges. In other words, a graph represents binary relations among the objects.
Genetic Algorithm: A genetic algorithm is a population-based metaheuristic algorithm that uses genetics-inspired operators to sample the solution space. This means that this algorithm applies some kind of genetic operators to a population of individuals (solutions) in order to evolve (improve) them throughout the generations (iterations).
Metaheuristic Algorithm: A metaheuristic algorithm is general framework to tackle NP-hard combinatorial optimization problems. Basically, a metaheuristic algorithm samples the solution space by visiting those regions with larger probabilities of having the best solution.
Solution Space: The solution space is the set of all possible solutions for the combinatorial optimization problem. The solution space of the Vertex Separation Problem contains all the linear orderings of the vertices. Thus, the cardinality of the solution space of VSP is . Notice that the number of feasible solutions for the problem grows exponentially with respect to the size of the instance (number of vertices).
Combinatorial Optimization Problem: An optimization problem consists in finding the best solution from a set of feasible solutions. An optimization problem whose variables are discrete (not continuous) is known as a combinatorial optimization problem. The goal of a combinatorial optimization problem is to find a mathematical object, e.g., a permutation, from a finite (or countable infinite) set.