Probability distribution of solution time in GRASP: An experimental investigation

被引:93
作者
Aiex, RM
Resende, MGC
Ribeiro, CC
机构
[1] Catholic Univ Rio de Janeiro, Dept Comp Sci, BR-22453900 Rio De Janeiro, Brazil
[2] AT&T Labs Res, Informat Sci Res Ctr, Florham Pk, NJ 07932 USA
关键词
combinatorial optimization; meta-heuristic; GRASP; experimental analysis of algorithms; probability distribution; parallel algorithm;
D O I
10.1023/A:1015061802659
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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 approximately achieve linear speed-up by implementing GRASP in parallel.
引用
收藏
页码:343 / 373
页数:31
相关论文
共 37 条
[1]  
[Anonymous], DIMACS SERIES DISCRE
[2]   PARALLEL BIASED SEARCH FOR COMBINATORIAL OPTIMIZATION - GENETIC ALGORITHMS AND TABU [J].
BATTITI, R ;
TECCHIOLLI, G .
MICROPROCESSORS AND MICROSYSTEMS, 1992, 16 (07) :351-367
[3]  
Bollobas B, 1985, RANDOM GRAPHS
[4]   QAPLIB-A QUADRATIC ASSIGNMENT PROBLEM LIBRARY [J].
BURKARD, RE ;
KARISCH, S ;
RENDL, F .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 55 (01) :115-119
[5]  
Chambers JM., 1983, WADSWORTH
[6]  
CIMIKOWSKI R, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P322
[7]   SLOW ANNEALING VERSUS MULTIPLE FAST ANNEALING RUNS - AN EMPIRICAL-INVESTIGATION [J].
DODD, N .
PARALLEL COMPUTING, 1990, 16 (2-3) :269-272
[8]  
EIKELDER HT, 1996, METAHEURISTICS THEOR, P605
[9]   A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR MAXIMUM INDEPENDENT SET [J].
FEO, TA ;
RESENDE, MGC ;
SMITH, SH .
OPERATIONS RESEARCH, 1994, 42 (05) :860-878
[10]   GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES [J].
FEO, TA ;
RESENDE, MGC .
JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) :109-133