Extending time‐to‐target plots to multiple instances

• Date: 01 September 2018
• Published date: 01 September 2018
• Author: Celso C. Ribeiro,Alberto Reyes
• DOI: http://doi.org/10.1111/itor.12507

Intl. Trans. in Op. Res. 25 (2018) 1515–1536

DOI: 10.1111/itor.12507

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Extending time-to-target plots to multiple instances

Alberto Reyes and Celso C. Ribeiro

Institute of Computing, Universidade FederalFluminense, Niter ´

oi, RJ 24210-346, Brazil

E-mail: albertord84@gmail.com [Reyes]; celso@ic.uff.br [Ribeiro]

Received 31 July2016; received in revised form 27 March 2017; accepted 10 August 2017

Abstract

Time-to-target plots (ttt-plots) are a useful tool to characterize, evaluate, and compare the behavior of

randomized heuristics for a given problem instance of some combinatorial optimization problem. Multiple

time-to-target plots (mttt-plots) are their naturalextension to sets of multiple instances. Weshow how to build

an mttt-plot from the individual ttt-plots of each instance in the set and we illustrate several case studies to

illustrate the applicability and usefulness of the new tool.

Keywords:runtime distribution; time-to-target plot; multiple time-to-target plot; randomized metaheuristics

1. Introduction

Runtime distributions or time-to-target plots (or, simply, ttt-plots) display on the ordinate axis the

probability that an algorithm will find a solution at least as good as a given target value for a

given problem instance within a givenrunning time, shown on the abscissa axis. They provide a very

useful tool to characterize the running times of stochastic algorithms for combinatorialoptimization

problems and to compare different algorithms or strategies for solving a given problem. ttt-Plots

were first used by Feo et al. (1994) and have been widely used as a tool for algorithm design

and comparison. They have also been advocated by Hoos and St¨

utzle (1998a, 1998b) as a way to

characterize the execution times of stochastic algorithms for combinatorial optimization.

Let Pbe an optimization problem and Ha randomized heuristic for this problem. Furthermore,

let Ibe a specific instance of Pand let look4 be a target value for this instance.

Aiex et al. (2007) developed a perl programto create ttt-plots for measured times that are assumed

to fit a shifted exponential distribution, following closely the work of Aiex et al. (2002). To build

the ttt-plot, the heuristic His run Ntimes on the fixed instance Iand the algorithm is made to stop

as soon as a solution whose objective function is at least as good as the given target value look4 is

found. For each of the Nruns, the random number generator used in the implementation of the

heuristic is initialized with a distinct seed. Therefore, the runs are assumed to be independent. The

solution time of each run is recorded and saved.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1516 A. Reyes and C. C. Ribeiro/ Intl. Trans. in Op. Res. 25 (2018) 1515–1536

Fig. 1. Cumulative probability distribution plot of measured data. [Colour figure can be viewedat

wileyonlinelibrary.com]

After concluding the Nindependent runs, the solution times are sorted in increasing order.

We associate with the ith sorted solution time tia probability pi=(i−1/2)/N(see Resende and

Ribeiro, 2016, p. 114) and plot the points zi=(ti,pi),fori=1,...,N.

If X≥0 denotes the continuous random variable representing the time taken by heuristic Hto

find a solution as good as the target value look4 for instance I,then ˆ

FX(ti)=piis an estimator

of P(X≤x)=FX(x),foreveryx=ti,i=1,...,N. Figure 1 illustrates the plot of this estimated

cumulative probability distribution for some problem P, a heuristic H, an instance I, and a target

look4. We can see that the probability that the heuristic finds a solution at least as good as the target

value in at most 416 seconds is about 50%, in at most 1064 seconds is about 80%, and in at most

1569 seconds is about 90%.

Ribeiro et al. (2009) developed a closed-form result to compare two exponential algorithms and

an iterativeprocedure to compare two algorithms following generic runtime distributions. This work

was extended by Ribeiro et al. (2012) and was also applied in the comparison of parallel heuristics.

Ribeiro and Rosseti (2015) developed a code to compare runtime distributions of randomized

algorithms. However,a possible limitation of the use of ttt-plots to compare different algorithms for

the same problem is that they convey information that is valid strictly for a single pair of problem

instance and target value at a time. To consider the implications of this assumption, let us consider

one numerical example involving an instance of the routing and wavelength assignment problem

(Zang et al., 2000).

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies