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

Description Usage Arguments Details Value References

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

1	solver_abc_kui(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.

In addition, in step 1 and 2, for every pair of selected individuals x_i and x_j, we calculate a "random similarity" value (S <- 1 - runif(1) * sum(x_i != x_j) / length(x_i)). If S is lower than a random value between 0 and 1, we discard that particular mutation. This should in theory weight the algorithm towards performing mutations on individuals that are more similar to each other.

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.

Kui Chen, Hitoshi Kanoh, "A Discrete Artificial Bee Colony Algorithm Based on Similarity for Graph Coloring Problems", Proceedings of the 5th TPNC, 2017

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