tttplots-compare: A perl program to compare time-to-target plots or general runtime distributions of randomized algorithms


Celso C. Ribeiro1 and Isabel Rosseti1


1Department of Computer Science, Universidade Federal Fluminense, Niterói, Rio de Janeiro, Brazil.

Click here to download the paper [PDF: 536 Kb].

Abstract:

Run time distributions or time-to-target plots display on the ordinate axis the probability that an algorithm will find a solution at least as good as a given target value within a given running time, shown on the abscissa axis. Given a pair of different stochastic local search algorithms $X_1$ and $X_2$, we describe a numerical method that gives the probability that $X_1$ finds a solution at least as good as a given target value in a smaller computation time than $X_2$, for the case where the runtimes of each of the two algorithms follow any runtime distribution. An illustrative example of a numerical application is also reported. We describe the perl program tttplots-compare, developed to compare time-to-target plots or general runtime distribution for measured CPU times of any two heuristics based on stochastic local search. The perl program can be downloaded in Section 4 or from http://www.ic.uff.br/$\sim$celso/tttplots/tttplots-compare.gz.

1) Motivation

Runtime distributions or time-to-target plots display on the ordinate axis the probability that an algorithm will find a solution at least as good as a given target value within a given running time, shown on the abscissa axis. Time-to-target plots were first used by Feo et al. [7]. Runtime distributions have been advocated also by Hoos and Stützle [8,9] as a way to characterize the running times of stochastic algorithms for combinatorial optimization.

Aiex et al. [2] described a perl program to create time-to-target plots for measured times that are assumed to fit a shifted exponential distribution, following closely [1]. Such plots are very useful in the comparison of different algorithms or strategies for solving a given problem and have been widely used as a tool for algorithm design and comparison.

In this work, we explore runtime distributions to evaluate stochastic local search algorithms and we describe a new tool to compare any pair of different stochastic local search algorithms $A_1$ and $A_2$. In Section 2, we describe a numerical method originally presented by Ribeiro et al. [14,15] that gives the probability that algorithm $A_1$ finds a solution at least as good as a given target value in a smaller computation time than $A_2$, for the case where the runtimes of the two algorithms follow any general runtime distribution. A detailed numerical application is reported in Section 3, illustrating the comparison of two different sequential algorithms. This is followed in Section 4 by the description of the perl program tttplots-compare, whose source code may be downloaded from http://www.ic.uff.br/$\sim$celso/tttplots/tttplots-compare.gz. Concluding remarks are made in the last section.

2) General run time distributions

We assume the existence of two stochastic local search algorithms $A_1$ and $A_2$ for the approximate solution of some combinatorial optimization problem. We denote by $X_1$ (resp. $X_2$) the continuous random variable representing the time needed by algorithm $A_1$ (resp. $A_2$) to find a solution as good as a given target value. Let $F_{X_1}(\tau)$ and $f_{X_1}(\tau)$ (resp. $F_{X_2}(\tau)$ and $f_{X_2}(\tau)$) be the cumulative probability distribution and the probability density function of $X_1$ (resp. $X_2$), respectively. Then,

\begin{displaymath}%\begin{equation}\label{eq5} Pr(X_1 \leq X_2) = \int_{-\infty... ...u)d\tau= \int_{0}^{\infty}Pr(X_1 \leq \tau)f_{X_2}(\tau)d\tau, \end{displaymath}

since $f_{X_1}(\tau)= f_{X_2}(\tau)= 0$ for any for any $\tau < 0$. For an arbitrary small real number $\varepsilon$, the above expression can be rewritten as
\begin{displaymath} Pr(X_1 \leq X_2) = \sum_{i = 0}^{\infty}\int_{i\varepsilon}^{(i+1)\varepsilon} Pr(X_1 \leq \tau)f_{X_2}(\tau)d\tau. \end{displaymath} (1)

Since $Pr(X_1 \leq i\varepsilon) \leq Pr(X_1 \leq \tau) \leq Pr(X_1 \leq (i+1)\varepsilon)$ for $i\varepsilon \leq \tau \leq (i+1)\varepsilon$, replacing $Pr(X_1 \leq \tau)$ by $Pr(X_1 \leq i \varepsilon)$ and by $Pr(X_1 \leq (i+1) \varepsilon)$ in (1) leads to

\begin{displaymath} \sum_{i = 0}^{\infty}F_{X_1}(i \varepsilon) \int_{i \varepsi... ...on) \int_{i \varepsilon}^{(i+1)\varepsilon}f_{X_2}(\tau)d\tau. \end{displaymath}

Let $L(\varepsilon)$ and $R(\varepsilon)$ be the value of the left and right hand sides of the above expression, respectively, with $\Delta(\varepsilon)=R(\varepsilon)-L(\varepsilon)$ being the difference between the upper and lower bounds of $Pr(X_1 \leq X_2)$. Then,
\begin{displaymath} \Delta(\varepsilon)=\sum_{i = 0}^{\infty} \left[F_{X_1}((i+1... ...ght] \int_{i\varepsilon}^{(i+1)\varepsilon}f_{X_2}(\tau)d\tau. \end{displaymath} (2)

Let $\delta= \max_{\tau \geq 0}\{f_{X_1}(\tau)\}$. Since $\vert F_{X_1}((i+1)\varepsilon) - F_{X_1}(i \varepsilon)\vert \leq \delta\varepsilon$ for $i \geq 0$, expression (2) turns out to be

\begin{displaymath} \Delta(\varepsilon) \leq \sum_{i = 0}^{\infty} \delta \varep... ...ilon \int_{0}^{\infty}f_{X_2}(\tau)d\tau = \delta \varepsilon. \end{displaymath}

Consequently,
\begin{displaymath} \Delta(\varepsilon) \leq \delta \varepsilon, \end{displaymath} (3)

i.e., the difference $\Delta(\varepsilon)$ between the upper and lower bounds of $Pr(X_1 \leq X_2)$ (or the absolute error in the integration) is smaller than or equal to $\delta \varepsilon$. Therefore, this difference can be made as small as desired by choosing a sufficiently small value for $\varepsilon$.

In order to numerically evaluate a good approximation to $Pr(X_1 \leq X_2)$, we select the appropriate value of $\varepsilon$ such that the resulting approximation error $\Delta(\varepsilon)$ is sufficiently small. Next, we compute $L(\varepsilon)$ and $R(\varepsilon)$ to obtain the approximation

\begin{displaymath} Pr(X_1 \leq X_2) \approx \frac{L(\varepsilon)+R(\varepsilon)}{2}. \end{displaymath} (4)

In practice, the probability distributions are unknown. Instead of them, all information available is a sufficiently large number $N_1$ (resp. $N_2$) of observations of the random variable $X_1$ (resp. $X_2$). Since the value of $\delta= \max_{\tau \geq 0}\{f_{X_1}(\tau)\}$ is also unknown beforehand, the appropriate value of $\varepsilon$ cannot be estimated. Then, we proceed iteratively as follows.

Let $t_1(j)$ (resp. $t_2(j)$) be the value of the $j$-th smallest observation of the random variable $X_1$ (resp. $X_2$), for $j=1,\ldots,N_1$ (resp. $N_2$). We set the bounds $a=\min\{t_1(1),t_2(1)\}$ and $b=\max\{t_1(N_1),t_2(N_2)\}$ and choose an arbitrary number $h$ of integration intervals to compute an initial value $\varepsilon= (b-a)/h$ for each integration interval. For sufficiently small values of the integration interval $\varepsilon$, the probability density function $f_{X_1}(\tau)$ in the interval $[i\varepsilon,(i+1)\varepsilon]$ can be approximated by $\hat{f}_{X_1}(\tau) = (\hat{F}_{X_1}((i+1)\varepsilon)-\hat{F}_{X_1}(i\varepsilon))/\varepsilon$, where

\begin{displaymath} \hat{F}_{X_1}(i\varepsilon) = \vert\{t_1(j), j=1,\ldots,N_1: t_1(j) \leq i\varepsilon\}\vert. \end{displaymath} (5)

The same approximations hold for random variable $X_2$.

Finally, the value of $Pr(X_1 \leq X_2)$ can be computed as in expression (4), using the estimates $\hat{f}_{X_1}(\tau)$ and $\hat{f}_{X_2}(\tau)$ in the computation of $L(\varepsilon)$ and $R(\varepsilon)$. If the approximation error $\Delta(\varepsilon)=R(\varepsilon)-L(\varepsilon)$ is sufficiently small, then the procedure stops. Otherwise, the value of $\varepsilon$ is halved and the above steps are repeated until convergence.

3) Illustrative example

We illustrate the application of the tool described in the previous section with the comparison of two stochastic local search algorithms (running on the same instance) for the routing and wavelength assignment problem. The first is a multistart procedure, while the second is a tabu search heuristic.

A point-to-point connection between two endnodes of an optical network is called a lightpath. Two lightpaths may use the same wavelength, provided they do not share any common link. The routing and wavelength assignment problem is that of routing a set of lightpaths and assigning a wavelength to each of them, minimizing the number of wavelengths needed. Noronha and Ribeiro [13] proposed a decomposition heuristic for solving this problem. First, a set of possible routes is precomputed for each lightpath. Next, one of the precomputed routes and a wavelength are assigned to each lightpath by a tabu search heuristic solving an instance of the partition coloring problem.

We compare this decomposition strategy based on the tabu search heuristic with the multistart greedy heuristic of Manohar et al. [12]. Two networks are used for benchmarking. The first has 27 nodes representing the capital cities in Brazil, with 70 links connecting them. There are 702 lightpaths to be routed. Instance [10] Finland is formed by 31 nodes and 51 links, with 930 lightpaths to be routed.

Each algorithm was run 200 times with different seeds. The target was set at 24 (the best known solution value is 24) for instance Brazil and at 50 (the best known solution value is 47) for instance Finland. Algorithm $A_1$ is the multistart heuristic, while $A_2$ is the tabu search decomposition scheme.

The empirical run time distributions of the decomposition and multistart strategies are superimposed in Figure 1. The direct comparison of the two approaches shows that decomposition clearly outperformed the multistart strategy for instance Brazil, since $Pr(X_1 \leq X_2) = 0.13$ in this case (with $L(\varepsilon) = 0.129650$, $R(\varepsilon) = 0.130350$, $\Delta(\varepsilon) = 0.000700$, and $\varepsilon = 0.008163$). However, the situation changes for instance Finland. Although both algorithms have similar performances, multistart is slightly better with respect to the measure proposed in this work, since $Pr(X_1 \leq X_2) = 0.536787$ (with $L(\varepsilon) = 0.536525$, $R(\varepsilon) = 0.537050$, $\Delta(\varepsilon) = 0.000525$, and $\varepsilon = 0.008804$).

Figure 1: Superimposed run time distributions of multistart and tabu search: (a) $Pr(X_1 \leq X_2) = 0.13$, and (b) $Pr(X_1 \leq X_2) = 0.536787$.
\includegraphics[width=11cm, angle=0]{gpr-gedpXts-brasil.eps}
(a) Brazil instance with target 24
 
\includegraphics[width=11cm, angle=0]{gpr-gedpXts-fin.eps}
(b) Finland instance with target 50

We have investigated the convergence of the proposed measure with the sample size (i.e., with the number of independent runs of each algorithm). Convergence with the sample size is illustrated next for the Finland instance of the routing and wavelength assignment problem, with the target set at 49. Once again, algorithm $A_1$ is the multistart heuristic and algorithm $A_2$ is the tabu search decomposition scheme. The estimation of $Pr(X_1 \leq X_2)$ is computed for N = 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, and 5000 independent runs of each algorithm. Figure 2 displays the results obtained. We notice that the estimation of $Pr(X_1 \leq X_2)$ stabilizes as the sample size $N$ increases.

Figure 2: Convergence of the estimation of $Pr(X_1 \leq X_2)$ with the sample size for the Finland instance of the routing and wavelength assignment problem.
\includegraphics[width=10cm, angle=0]{fin-100-5000.eps}

4) The perl program: tttplots-compare

The perl program tttplots-compare takes two input files with $N$ lines each, where $N$ denotes the number of runs of each algorithm $A_1$ and $A_2$. Each line contains a running time entry. The program calculates the probability that the first algorithm $A_1$ finds a solution at least as good as an originally given target value in a smaller computation time than $A_2$.

The perl source code of program tttplots.compare is available for download by clicking here. To run this program, simply type: perl ttttplots-compare -f input-filename1 input-filename2, where input-filename1.dat and input-filename2.dat are the input data files with $N$ running time data points in each of them.

5) Concluding remarks

Run time distributions are very useful tools to characterize the running times of stochastic algorithms for combinatorial optimization. In this work, we extended a previous tool developed for plotting and evaluating run time distributions [1], providing a perl program that establishes pairwise comparisons of stochastic local heuristics for combinatorial optimization problems by computing the probability that one heuristic is faster than the other.

This new tool and the resulting probability index revealed themselves as very useful and promising, providing a new, additional measure for comparing the performance of stochastic local search algorithms or different versions of the same algorithm. They can also be used for setting the best parameters of a given algorithm, by providing an strategy for comparing the resulting implementations.

In addition to the first applications reported in [14,15], the perl program described and made available in this paper has already been used in the comparison of evolutionary and genetic algorithms to the $k$-interconnected multi-depot multi-traveling salesmen problem, to the winner determination problem in combinatorial auctions, to the general-cost set covering problem, to the Steiner triple covering problem, to the general-cost set $k$-covering by pairs problem, see e.g. Andrade et al. [3,4,11]. It was also used in comparisons of stochastic local search algorithms for the 2-path network design problem [5] and for the antibandwidth problem [6].

Acknowledgments.

This paper provides the perl program whose fundamentals and numerical computations have been originally proposed in the paper titled ``On the use of run time distributions to evaluate and compare sequential and parallel stochastic local search algorithms'' [14], which received the ``Best Paper Presentation Award'' among all papers presented at the conference ``Engineering Stochastic Local Search Algorithms'' held in Brussels from September 3 to 4, 2009.

Bibliography

[1] R.M. Aiex, M.G.C. Resende, and C.C. Ribeiro. Probability distribution of solution time in GRASP: An experimental investigation. Journal of Heuristics, 8:343-373, 2002.

[2] R.M. Aiex, M.G.C. Resende, and C.C. Ribeiro. TTTPLOTS: A perl program to create time-to-target plots. Optimization Letters, 1:355-366, 2007.

[3] C.E. Andrade, F.K. Miyazawa, and M.G.C. Resende. Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem. In Proceedings of the Genetic and Evolutionary Computation Conference, Amsterdam, 2013. To appear.

[4] C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, and R.F. Toso. Biased random-key genetic algorithms for the winner determination problem in combinatorial auctions. Evolutionary Computation. To appear.

[5] H. Barbalho, I. Rosseti, S. L. Martins, and A. Plastino. A hybrid data mining grasp with path-relinking. Computers & Operations Research, To appear.

[6] A. Duarte, R. Martí, M.G.C. Resende, and R.M.A. Silva. GRASP with path relinking heuristics for the antibandwidth problem. Networks, 58:171-189, 2011.

[7] T.A. Feo, M.G.C. Resende, and S.H. Smith. A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42:860-878, 1994.

[8] H.H. Hoos and T. Stützle. Evaluation of Las Vegas algorithms - Pitfalls and remedies. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, pages 238-245, 1998.

[9] H.H. Hoos and T. Stützle. On the empirical evaluation of Las Vegas algorithms - Position paper. Technical report, Computer Science Department, University of British Columbia, 1998.

[10] E. Hyytiã and J. Virtamo. Wavelength assignment and routing in WDM networks. In Nordic Teletraffic Seminar 14, pages 31-40, 1998.

[11] M.G.C. Resende J.F. Gonçalves and R.F. Toso. Biased and unbiased random-key genetic algorithms: An experimental analysis. In The X Metaheuristics International Conference, Singapore, 2013. To appear.

[12] P. Manohar, D. Manjunath, and R.K. Shevgaonkar. Routing and wavelength assignment in optical networks from edge disjoint path algorithms. IEEE Communications Letters, 5:211-213, 2002.

[13] T.F. Noronha and C.C. Ribeiro. Routing and wavelength assignment by partition coloring. European Journal of Operational Research, 171:797-810, 2006.

[14] C.C. Ribeiro, I. Rosseti, and R. Vallejos. On the use of run time distributions to evaluate and compare stochastic local search algorithms. In T. Stützle, M. Biratari, and H.H. Hoos, editors, Engineering Stochastic Local Search Algorithms, volume 5752 of Lecture Notes in Computer Science, pages 16-30. Springer, 2009.

[15] C.C. Ribeiro, I. Rosseti, and R. Vallejos. Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms. Journal of Global Optimization, 54:405-429, 2012.