Optimization Online


Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms

Celso Ribeiro(celso***at***ic.uff.br)
Isabel Rosseti(rosseti***at***ic.uff.br)
Reinaldo Vallejos(reinaldo.vallejos***at***usm.cl)

Abstract: Run time distributions or time-to-target plots are very useful tools to characterize the running times of stochastic algorithms for combinatorial optimization. We further explore run time distributions and describe a new tool to compare two algorithms based on stochastic local search. For the case where the running times of both algorithms fit exponential distributions, we derive a closed form index that gives the probability that one of them finds a solution at least as good as a given target value in a smaller computation time than the other. This result is extended to the case of general run time distributions and a numerical iterative procedure is described for the computation of the above probability value. Numerical examples illustrate the application of this tool in the comparison of different sequential and parallel algorithms for a number of distinct problems.

Keywords: Run time distributions; tttplots; stochastic local search; metaheuristics; heuristics; GRASP

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Global Optimization (Stochastic Approaches )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )


Download: [PDF]

Entry Submitted: 03/10/2010
Entry Accepted: 03/11/2010
Entry Last Modified: 03/10/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society