search_cover_ants {gor}

Ant colony optimization algorithm for Vertex-Cover

Description

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.

Usage

search_cover_ants(g, K, N, alpha = 2, beta = 2, dt = 1, rho = 0.1, verb = TRUE)

Arguments

g

Graph.

K

Number of ants per iteration.

N

Number of iterations.

alpha

Exponent of the pheronome index, see details.

beta

Exponent of the vertex degree, see details.

dt

Pheromone increment.

rho

Pheromone evaporation rate.

verb

Boolean; if TRUE (default) it echoes to the console the routine progress .

Details

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 adges 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 guarateed 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.

Value

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).

Author(s)

Cesar Asensio

See Also

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.

Examples

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