Ant colony optimization (ACO) heuristic algorithm to search for a vertex cover of small size in a graph. ACO is a random algorithm; as such, it yields better results when longer searches are run. To guess the adequate parameter values resulting in better performance in particular instances requires some experimentation, since no universal values of the parameters seem to be appropriate to all examples.
search_cover_ants(g, K, N, alpha = 2, beta = 2, dt = 1, rho = 0.1, verb = TRUE)A list with three components: $set contains the subset of V(g) representing the cover and $size contains the number of vertices of the cover; $found is the number of vertex covers found in subsequent iterations (often they are repeated, that is, different explorations may find the same vertex cover).
Graph.
Number of ants per iteration.
Number of iterations.
Exponent of the pheronome index, see details.
Exponent of the vertex degree, see details.
Pheromone increment.
Pheromone evaporation rate.
Boolean; if TRUE (default) it echoes to the console the routine progress .
Cesar Asensio
ACO is an optimization paradigm that tries to replicate the behavior of a colony of ants when looking for food. Ants leave after them a soft pheromone trail to help others follow the path just in case some food has been found. Pheromones evaporate, but following again the trail reinforces it, making it easier to find and follow. Thus, a team of ants search a vertex cover in a graph, leaving a pheromone trail on the chosen vertices. At each step, each ant decides the next vertex to add based on the pheromone level and on the degree of the remaining vertices, according to the formula \(P(v) ~ \phi(v)^\alpha*\exp(\beta*d(v))\), where \(\phi(v)\) is the pheromone level, \(d(v)\) is the degree of the vertex \(v\), and \(\alpha\), \(\beta\) are two exponents to broad or sharpen the probability distribution. After each vertex has been added to the subset, its incident edges are removed, following a randomized version of the greedy heuristic. In a single iteration, each ant builds a vertex cover, and the best of them is recorded. Then the pheromone level of the vertices of the best cover are enhanced, and the remaining pheromones begin to evaporate.
Default parameter values have been chosen in order to find the optimum in the examples considered below. However, it cannot be guaranteed that this is the best choice for all cases. Keep in mind that no polynomial time exact algorithm can exist for the VCP, and thus harder instances will require to fine-tune the parameters. In any case, no guarantee of optimality of covers found by this method can be given, so they might be improved further by other methods.
is_cover checks if a vertex subset is a vertex cover, build_cover_greedy builds a cover using a greedy heuristic, build_cover_approx builds a cover using a 2-approximation algorithm, improve_cover_flip improves a cover using local search, search_cover_random looks for a random cover of fixed size, find_cover_BB finds covers using a branch-and-bound technique, plot_cover plots covers.
library(igraph)
set.seed(1)
g <- sample_gnp(25, p=0.25) # Random graph
X6 <- search_cover_ants(g, K = 20, N = 10)
plot_cover(X6, g)
X6$found
Run the code above in your browser using DataLab