×

zbMATH — the first resource for mathematics

TTT plots: a perl program to create time-to-target plots. (English) Zbl 1220.90102
Summary: This paper describes a perl language program to create time-to-target solution value plots for measured CPU times that are assumed to fit a shifted exponential distribution. This is often the case in local search based heuristics for combinatorial optimization, such as simulated annealing, genetic algorithms, iterated local search, tabu search, WalkSAT, and GRASP. 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. We first discuss how TTT plots are generated. This is followed by a description of the perl program tttplots.pl.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aiex R.M., Binato S., Resende M.G.C. (2003) Parallel GRASP with path-relinking for job shop scheduling. Parallel Comput. 29, 393–430
[2] Aiex R.M., Pardalos P.M., Resende M.G.C., Toraldo G. (2005) GRASP with path relinking for three-index assignment. INFORMS J. Comput. 17, 224–247 · Zbl 1239.90087
[3] Aiex R.M., Resende M.G.C. (2005) Parallel strategies for GRASP with path-relinking. In: Ibaraki T., Nonobe K., Yagiura M. (eds) Metaheuristics: Progress as Real Problem Solvers. Springer, Berlin Heidelberg New York, pp. 301–331
[4] Aiex R.M., Resende M.G.C., Ribeiro C.C. (2002) Probability distribution of solution time in GRASP: an experimental investigation. J. Heuristics 8, 343–373 · Zbl 1012.68795
[5] Battiti R., Tecchiolli G. (1992) Parallel biased search for combinatorial optimization: genetic algorithms and TABU. Microprocess. Microsyst. 16, 351–367
[6] Buriol L.S., Resende M.G.C., Ribeiro C.C., Thorup M. (2005) A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks 46, 36–56 · Zbl 1072.90528
[7] Chambers J.M., Cleveland W.S., Kleiner B., Tukey P.A. (1983) Graphical Methods for Data Analysis. Chapman Hall, London · Zbl 0532.65094
[8] Chiarandini, M., Stützle, T.: Experimental evaluation of course timetabeling algorithms. Technical Report AIDA-02-05, Fachgebiet Intellektik, Fachbereich Informatik Technische Universität Darmstadt (2002)
[9] Czarnowski I., Jȩdrzejowicz P. (2004) Probability distribution of solution time in ANN training using population learning algorithm. In: Rutkowski L., et al. (eds) ICAISC 2004. Lecture Notes in Artificial Intelligence, vol. 3070. Springer, Berlin Heidelberg New York, pp. 172–177 · Zbl 1058.68551
[10] de Andrade M.R.Q., de Andrade P.M.F., Martins S.L., Plastino A. (2005) GRASP with path-relinking for the maximum diversity problem. In: Nikoletseas S.E. (eds) WEA 2005. Lecture Notes in Computer Science, vol. 3503. Springer, Berlin Heidelberg New York, pp. 558–569 · Zbl 1121.68417
[11] Dodd N. (1990) Slow annealing versus multiple fast annealing runs: an empirical investigation. Parallel Comput. 16, 269–272 · Zbl 0718.65046
[12] Ten Eikelder H.M.M., Verhoeven M.G.A., Vossen T.W.M., Aarts E.H.L. (1996) A probabilistic analysis of local search. In: Osman I.H., Kelly J.P. (eds) Metaheuristics: Theory Applications. Kluwer, Dordrecht, pp. 605–618 · Zbl 0877.90077
[13] Feo T.A., Resende M.G.C., Smith S.H. (1994) A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42, 860–878 · Zbl 0815.90121
[14] Fernandes E.R., Ribeiro C.C. (2005) Using an adaptive memory strategy to improve a multistart heuristic for sequencing by hybridization. In: Nikoletseas S.E. (ed) WEA 2005. Lecture Notes in Computer Science, vol. 3503. Springer, Berlin Heidelberg New York, pp. 4–15 · Zbl 1121.68404
[15] Festa P., Pardalos P.M., Pitsoulis L.S., Resende M.G.C. (2005) GRASP with path-relinking for the weighted maximum satisfiability problem. In: Nikoletseas S.E. (ed) WEA 2005. Lecture Notes in Computer Science, vol. 3503. Springer, Berlin Heidelberg New York, pp. 367–379 · Zbl 1121.68405
[16] Festa P., Pardalos P.M., Resende M.G.C., Ribeiro C.C. (2002) Randomized heuristics for the MAX-CUT problem. Optim. Methods Softw. 7, 1033–1058 · Zbl 1032.90073
[17] Gent I.P., Hoos H.H., Rowley A.G.D., Smyth K. (2003) Using stochastic local search to solve quantified Boolean formulae. In: Rossi F. (ed) CP 2003. Lecture Notes in Computer Science, vol. 2833. Springer, Berlin Heidelberg New York, pp. 348–362 · Zbl 1273.68346
[18] Hoos, H., Stützle, T.: On the empirical evaluation of Las Vegas algorithms–position paper. Technical report, Computer Science Department, University of British Columbia (1998)
[19] Hoos, H.H.: On the run-time behaviour of stochastic local search algorithms for SAT. In: Proceedings of AAAI-99, pp. 661–666. MIT Press, Cambridge (1999)
[20] Hoos, H.H., Boutilier, C.: Solving combinatorial auctions using stochastic local search. In: Proceedings of the 17th conference on artificial intelligence (AAAI 2000), pp. 22–29, Austin. MIT Press, Cambridge (2000)
[21] Hoos, H.H., Stützle, T.: Evaluation Las Vegas algorithms–pitfalls and remedies. In: Proceedings of the 14th conference on uncertainty in artificial intelligence, pp. 238–245 (1998)
[22] Hoos H.H., Stützle T. (1998) Some surprising regularities in the behaviour of stochastic local search. In: Maher M., Puget J.-F. (eds) CP’98. Lecture Notes in Computer Science, vol. 1520. Springer, Berlin Heidelberg New York, pp. 470
[23] Hoos H.H., Stützle T. (1999) Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artif. Intell. 112, 213–232 · Zbl 0996.68069
[24] Hoos H.H., Stützle T. (2000) Local search algorithms for SAT: an empirical evaluation. J. Autom. Reason. 24, 421–481 · Zbl 0961.68039
[25] Hutter, F.: Stochastic local search for solving the most probable explanation problem in Bayesian networks. Master’s Thesis, Computer Science Department, Darmstadt University of Technology (2004)
[26] Hutter F., Tompkins D.A.D., Hoos H.H. (2002) Scaling and probabilistic smoothing: Efficient local search for SAT. In: Van Hentenryck P. (ed) CP 2002. Lecture Notes in Computer Science, vol. 2470. Springer, Berlin Heidelberg New York, pp. 233–248
[27] Marinho, E.H.: Heurísticas busca tabu para o problema de programaçao de tripulaç oes de ônibus urbanos (in Portuguese). Master’s Thesis, Universidade Federal Fluminense (2005)
[28] Martins S.L., Ribeiro C.C., Rosseti I. (2004) Applications and parallel implementations of metaheuristics in network design and routing. In: Manandhar S., et al. (eds) AACC 2004. Lecture Notes in Computer Science, vol. 3285. Springer, Berlin Heidelberg New York, pp. 205–213
[29] Nudelman E., Leyton-Brown K., Hoos H.H., Devkar A., Shoham Y. (2004) Understanding random SAT: beyond the clauses-to-variables ratio. In: Wallace M. (ed) CP 2004. Lecture Notes in Computer Science, vol. 3258. Springer, Berlin Heidelberg New York, pp. 438–452 · Zbl 1152.68569
[30] Oliveira C.A.S., Pardalos P.M., Resende M.G.C. (2004) GRASP with path-relinking for the quadratic assignment problem. In: R ibeiro C.C., Martins S.L. (eds) Efficient and Experimental Algorithms – WEA2004. Lecture Notes in Computer Science, vol. 3059. Springer, Berlin Heidelberg New York, pp. 356–368
[31] Osborne L.J., Gillett B.E. (1991) A comparison of two simulated annealing algorithms applied to the directed Steiner problem on networks. ORSA J. Comput. 3, 213–225 · Zbl 0753.90067
[32] Resende M.G.C., Gonzalez Velarde J.L. (2003) GRASP: Procedimientos de búsqueda miope aleatorizado y adaptativo. Intel. Artif. 19, 61–76
[33] Resende M.G.C., Ribeiro C.C. (2003) A GRASP with path-relinking for private virtual circuit routing. Networks 41, 104–114 · Zbl 1028.90502
[34] Resende M.G.C., Ribeiro C.C. (2003) Greedy randomized adaptive search procedures. In: Glover F., Kochenberger G. (eds) Handbook of Metaheuristics. Kluwer, Dordrecht, pp. 219–249 · Zbl 1102.90384
[35] Resende M.G.C., Ribeiro C.C. (2005) Parallel greedy randomized adaptive search procedures. In: Alba E. (ed) Parallel Metaheuristics: A New Class of Algorithms. Wiley, New York, pp. 315–346 · Zbl 1137.90742
[36] Santos, H.G., Ochi, L.S., Souza M, J.F.: A tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. In: Burke, E.K., Trick, M. (eds.) Proceedings of the 5th international conference on the practice and theory of automated timetabling (PATAT ’04), pp. 343–358 (2004) · Zbl 1189.90065
[37] Santos H.G., Ochi L.S., Souza M.J.F. (2004) An efficient tabu search heuristic for the school timetabling problem. In: Ribeiro C.C., Martins S.L. (eds) Efficient and Experimental Algorithms – WEA2004. Lecture Notes in Computer Science, vol. 3059. Springer, Berlin Heidelberg New York, pp. 468–481
[38] Selman, B., Kautz H.A., Cohen B. (1994) Noise strategies for improving local search. In: Proceedings of the AAAI-94, pp. 337–343. MIT Press, Cambridge
[39] Shmygelska A., Aguirre-Hernández R., Hoos H.H. (2002) An ant colony optimization algorithm for the 2D HP protein folding problem. In: Dorigo M., et al. (eds) ANTS 2002. Lecture Notes in Computer Science, vol. 2463. Springer, Berlin Heidelberg New York, pp. 40–52
[40] Shmygelska A., Hoos H.H. (2003) An improved ant colony optimisation algorithm for the 2D HP protein folding problem. In: Xiang Y., Chaib-draa B. (eds) AI 2003. Lecture Notes in Artificial Intelligence, vol. 2671. Springer, Berlin Heidelberg New York, pp. 400–417
[41] Silva G.C., Ochi L.S., Martins S.L. (2004) Experimental comparison of greedy randomized adaptive search procedures for the maximum diversity problem. In: Ribeiro C.C., Martins S.L. (eds) Efficient and Experimental Algorithms – WEA2004. Lecture Notes in Computer Science, vol. 3059. Springer, Berlin Heidelberg New York, pp. 498–512
[42] Stützle, T., Hoos, H.H.: Analyzing the run-time behaviour of iterated local search for the TSP. Technical Report IRIDIA/2000-01, IRIDIA, Université Libre de Bruxelles (2000) · Zbl 0961.68039
[43] Taillard E.D. (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput. 17, 443–455
[44] Tompkins D.A.D., Hoos H.H. (2003) Scaling and probabilistic smoothing: dynamic local search for unweighted MAX-SAT. In: Xiang Y., Chaib-draa B. (eds) AI 2003. Lecture Notes in Artificial Intelligence, vol. 2671. Springer, Berlin Heidelberg New York, pp. 145–159
[45] Tulpan D.C., Hoos H.H. (2003) Hybrid randomised neighbourhoods improve stochastic local search for DNA code design. In: Xiang Y., Chaib-draa B. (eds) AI 2003. Lecture Notes in Artificial Intelligence, vol. 2671. Springer, Berlin Heidelberg New York, pp. 418–433
[46] Tulpan D.C., Hoos H.H., Condon A.E. (2003) Stochastic local search algorithms for DNA word design. In: Hagiya M., Ohuchi A. (eds) DNA8. Lecture Notes in Computer Science, vol. 2568. Springer, Berlin Heidelberg New York, pp. 229–241 · Zbl 1026.68564
[47] Verhoeven M.G.A., Aarts E.H.L. (1995) Parallel local search. J. Heuristics 1, 43–66 · Zbl 0853.68156
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.