Journal of Heuristics, vol. 8, pp. 343-373, 2002.
A GRASP (greedy randomized adaptive search procedure)
is a multi-start metaheuristic for combinatorial optimization. We
study the probability distributions of solution time to a sub-optimal
target value in five GRASPs that have appeared in the literature and for
which source code is available. The distributions are estimated by
running 12,000 independent runs of the heuristic. Standard methodology
for graphical analysis is used to compare the empirical and theoretical
distributions and estimate the parameters of the distributions. We
conclude that the solution time to a sub-optimal target value fits a
two-parameter exponential distribution. Hence, it is possible to
achieve linear speed-up by implementing GRASP in parallel.
PDF file of full paper
Mauricio G.C. Resende's Home PageLast modified: 15 December 2000