solver_hdpso: Hamming Distance PSO Solver
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 Hamming Distance PSO (HDPSO) implementation described in Aoki et al., 2015.

1	solver_hdpso(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
w: Float in [0,1]. Weight for randomly choosing new colors.
c1: Float in [0,1]. Weight for choosing a color from Pbest.
c2: Float in [0,1]. Weight for choosing a color from Gbest.

The HDPSO algorithm begins with a random set of solutions P. It keeps a set of best solution found at each position of X (P_best), a set of solutions found at the previous iteration (P_prev), and the best solution found so far (g_best).

The algorithm define the similarity between two solutions, x and y, as: similarity(x,y) = 1 - (sum(x != y) / length(x))

At each iteration, it generates a new set of solution based on the current set of solutions. For each solution x_i in P, it performs the following steps:

1- Calculate Vrand = w * similarity(x_i, P_prev_i), Vpbest = c1 * r1 * similarity(x_i, P_best_i), Vgbest = c2 * r2 * similarity(x_i, g_best)
2- w, c1, and c2 are parameters, r1 and r2 are random numbers taken from [0,1] every iteration
3- For each k element of x_i, selects a new element using one of three options: a random color, the kth color from P_best_i, the kth color from g_best.
4- The choice at the previous step is random, but weighted by Vrand, Vpbest and Vgbest, respectively.

After the new set of solutions is generated, the current set replaces the previous set, and the new set replaces the current set. The new set is evaluated, and P_best and G_best are updated as necessary.

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.

Takuya Aoki, Claus Aranha, Hitoshi Kanoh, "PSO Algorithm with Transition Probability Based on Hamming Distance for Graph Coloring Problem", IEEE International Conference On Systems, Man and Cybernetics, 2015.

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