J.F. Gonçalves, M.G.C. Resende, and R.F. Toso
AT&T Labs Technical Report, 2013
ABSTRACT
Random key genetic
algorithms are heuristic methods for solving combinatorial optimization
problems. They represent solutions as vectors of randomly generated real
numbers, the so-called random keys. A deterministic algorithm, called a
decoder, takes as input a vector of random keys and associates with it a
feasible solution of the combinatorial optimization problem for which an
objective value or fitness can be computed. We compare three types of
random-key genetic algorithms: the unbiased algorithm of Bean (1994);
the biased algorithm of Gon¸calves and Resende (2010); and a greedy
version of Bean’s algorithm on 12 instances from four types of covering
problems: general-cost set covering, Steiner triple covering,
general-cost set k-covering, and unit-cost covering by pairs.
Experiments are run to construct runtime distributions for 36
heuristic/instance pairs. For all pairs of heuristics, we compute
probabilities that one heuristic is faster than the other on all 12
instances. The experiments show that, in 11 of the 12 instances, the
greedy version of Bean’s algorithm is faster than Bean’s original method
and that the biased variant is faster than both variants of Bean’s
algorithm.
PDF file of full paper
Last modified: 11 October 2013