[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

TTT plots: a perl program to create time-to-target plots

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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

    Article  MathSciNet  Google Scholar 

  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

    MathSciNet  Google Scholar 

  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

    Google Scholar 

  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

    Article  MATH  Google Scholar 

  5. Battiti R., Tecchiolli G. (1992) Parallel biased search for combinatorial optimization: genetic algorithms and TABU. Microprocess. Microsyst. 16, 351–367

    Article  Google Scholar 

  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

    Article  MATH  MathSciNet  Google Scholar 

  7. Chambers J.M., Cleveland W.S., Kleiner B., Tukey P.A. (1983) Graphical Methods for Data Analysis. Chapman Hall, London

    MATH  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  11. Dodd N. (1990) Slow annealing versus multiple fast annealing runs: an empirical investigation. Parallel Comput. 16, 269–272

    Article  MATH  Google Scholar 

  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

    Google Scholar 

  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

    Article  MATH  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Article  MathSciNet  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Article  MATH  Google Scholar 

  24. Hoos H.H., Stützle T. (2000) Local search algorithms for SAT: an empirical evaluation. J. Autom. Reason. 24, 421–481

    Article  MATH  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    MATH  Google Scholar 

  32. Resende M.G.C., Gonzalez Velarde J.L. (2003) GRASP: Procedimientos de búsqueda miope aleatorizado y adaptativo. Intel. Artif. 19, 61–76

    Google Scholar 

  33. Resende M.G.C., Ribeiro C.C. (2003) A GRASP with path-relinking for private virtual circuit routing. Networks 41, 104–114

    Article  MATH  MathSciNet  Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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)

  43. Taillard E.D. (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput. 17, 443–455

    Article  MathSciNet  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  47. Verhoeven M.G.A., Aarts E.H.L. (1995) Parallel local search. J. Heuristics 1, 43–66

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, RJ, 22451, Brazil

    Renata M. Aiex

  2. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932-0971, USA

    Mauricio G. C. Resende

  3. Department of Computer Science, Universidade Federal Fluminense, Rua Passo da Pátria, 156, Niterói, RJ, 24210-240, Brazil

    Celso C. Ribeiro

Authors
  1. Renata M. Aiex
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mauricio G. C. Resende
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Celso C. Ribeiro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mauricio G. C. Resende.

Additional information

Renata M. Aiex passed away on February 17, 2006.

AT&T Labs Research Technical Report: TD-6HT7EL.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aiex, R.M., Resende, M.G.C. & Ribeiro, C.C. TTT plots: a perl program to create time-to-target plots. Optimization Letters 1, 355–366 (2007). https://doi.org/10.1007/s11590-006-0031-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-006-0031-4

Keywords

Search

Navigation