solver_abc: Artificial Bee Colony Solver (Togashi Version)
In caranha/EvoGCP: Evolutionary Computation Tools for the Graph Coloring Problem

Solves a instance of the 3-GCP problem using the Artificial Bee Colony (ABC) implementation described in Togashi et al., 2017.

1	solver_abc(G, nfe, args)

G

the graph to be solved, represented by a list where G$V is the number of nodes, and G$E is a |E|x2 matrix of edges.

nfe

the number of function evaluations. The solver will stop after this number has been exceeded.

args

a list with arguments for the method. The list must contain the following names:

pop: Integer > 0. The size of the solution set X
onlooker: Integer > 0. The number of solutions chosen in step 2 of the algorithm.
scout: Integer > 0. The number of solutions chosen in step 3 of the algorithm.
limit: Integer > 0. Minimum number of iterations without improvement before a solution will be considered for step 3.
c: Number of elements in a solution exchanged during a mutation step.

The ABC algorithm begins with a random set of solutions X, and at every iteration performs the following three steps:

1- For every solution x_i in X, find x_j (i != j), and calculates x_u using 'mutate.abc(x_i, x_j)'. Evaluate x_u and replace x_i if better.
2- Select n = onlooker solutions x_i from X (with repetition), with probability proportional to their fitness. Apply Step 1 on these solutions.
3- Select n = scout solutions x_i from X where AGE(x_i) > limit. replace x_i with a random solution.

Mutate.abc(x_i, x_j, c) generates a new individual as follows: 'c' elements are choosen randomly from x_j, and copied into x_i.

A list with three names:

violation: the number of graph coloring violations of the best solution found (0 for a correct solution)
best: a vector with the best solution found
evals: the number of evaluations used by the time the solver stopped.

Yuuya Togashi, Claus Aranha, Hitoshi Kanoh, "Artificial Bee Colony Algorithm for Solving Graph Coloring Problem", Proceedings of the IPSJ, 2017

caranha/EvoGCP documentation built on May 3, 2021, 3:40 p.m.