Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Ant colony optimization on a limited budget of evaluations

  • Published:
Swarm Intelligence Aims and scope Submit manuscript

Abstract

Ant colony optimization (ACO) is a successful method for solving difficult combinatorial optimization problems. Following Ant System, the first ACO algorithm, a large number of algorithmic variants have been developed that showed significantly better performance on a wide range of optimization problems. Typically, performance was measured according to the solution quality achieved for a given computation time limit, which usually allowed the evaluation of a very large number of candidate solutions, often in the range of millions. However, there are practical applications where the number of evaluations that can be done is very restricted due to tight real-time constraints or to the high computational cost of evaluating a solution. Since these situations are quite different from those for which ACO algorithms were initially designed, current knowledge on good parameter settings or the most promising search strategies may not be directly applicable. In this paper, we examine the performance of different ACO algorithms under a strongly limited budget of 1000 evaluations. We do so using default parameter settings from the literature and parameter settings tuned for the limited-budget scenario. In addition, we compare the performance of the ACO algorithms to algorithms that make use of surrogate modeling of the search landscapes. We show that tuning algorithms for the limited-budget case is of uttermost importance, that direct search through the ACO algorithms keeps an edge over techniques using surrogate modeling, and that the ACO variants proposed as improvements over Ant System remain preferable.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. All experiments were performed on a single core of cluster nodes each equipped with two AMD Opteron 6272 16 cores CPUs running at 2.1 GHz and with 64 GB RAM. Note that the heavy computation needs for the model update, and other computations in EGO make this approach an option in case the actual real evaluation of a candidate solution involves very high computation times but not for the case of very tight real-time constraints.

  2. In what follows, we use the problem name to identify results specific to a problem, e.g., EGOTSP-AS refers to the TSP results obtained by using AS to search the landscape of the expected improvement.

References

  • April, J., Glover, F., Kelly, JP., & Laguna, M. (2003). Simulation-based optimization: Practical introduction to simulation optimization. In S. E. Chick, P. J. Sanchez, D. M. Ferrin, D. J. Morrice (Eds.), Proceedings of the 35th winter simulation conference: Driving innovation (Vol. 1, pp. 71–78). New Orleans, LA: ACM.

  • Balaprakash, P., Birattari, M., & Stützle, T. (2007). Improvement strategies for the F-race algorithm: Sampling design and iterative refinement. In T. Bartz-Beielstein, M. J. Blesa, C. Blum, B. Naujoks, A. Roli, G. Rudolph, & M. Sampels (Eds.), Hybrid metaheuristics, Lecture notes in computer science (Vol. 4771, pp. 108–122). Heidelberg, Germany: Springer.

  • Bersini, H., Dorigo, M., Langerman, S., Seront, G., & Gambardella, L. M. (1996). Results of the first international contest on evolutionary optimisation. In T. Bäck, T. Fukuda, & Z. Michalewicz (Eds.), Proceedings of the 1996 IEEE international conference on evolutionary computation (ICEC’96) (pp. 611–615). Piscataway, NJ: IEEE Press.

  • Bullnheimer, B., Hartl, R., & Strauss, C. (1999). A new rank-based version of the Ant System: A computational study. Central European Journal for Operations Research and Economics, 7(1), 25–38.

    MathSciNet  MATH  Google Scholar 

  • Dorigo, M. (1992). Optimization, learning and natural algorithms. PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy (in Italian).

  • Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.

    Article  Google Scholar 

  • Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. Cambridge, MA: MIT Press.

    Book  MATH  Google Scholar 

  • Dorigo, M., Maniezzo, V., & Colorni, A. (1991). The Ant System: An autocatalytic optimizing process. Tech. Rep. 91–016 Revised, Dipartimento di Elettronica, Politecnico di Milano, Italy.

  • Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics—Part B, 26(1), 29–41.

    Article  Google Scholar 

  • Fernandez, S., Alvarez, S., Díaz, D., Iglesias, M., & Ena, B. (2014). Scheduling a galvanizing line by ant colony optimization. In M. Dorigo, et al. (Eds.), Swarm intelligence, 8th international conference, ANTS 2014, Lecture notes in computer science (Vol. 8667, pp. 146–157). Heidelberg: Springer.

  • Gambardella, L. M., Montemanni, R., & Weyland, D. (2012). Coupling ant colony systems with strong local searches. European Journal of Operational Research, 220(3), 831–843.

    Article  MathSciNet  MATH  Google Scholar 

  • Jones, D. R., Schonlau, M., & Welch, W. J. (1998). Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4), 455–492.

    Article  MathSciNet  MATH  Google Scholar 

  • Knowles, J. D., Corne, D., & Reynolds, A. P. (2009). Noisy multiobjective optimization on a budget of 250 evaluations. In M. Ehrgott, C. M. Fonseca, X. Gandibleux, J. K. Hao, & M. Sevaux (Eds.), Evolutionary multi-criterion optimization (EMO 2009), Lecture notes in computer science (Vol. 5467, pp. 36–50). Heidelberg: Springer.

  • López-Ibáñez, M., Prasad, T. D., & Paechter, B. (2008). Ant colony optimisation for the optimal control of pumps in water distribution networks. Journal of Water Resources Planning and Management, ASCE, 134(4), 337–346.

    Article  Google Scholar 

  • López-Ibáñez, M., Dubois-Lacoste, J., Stützle, & T., Birattari, M. (2011). The irace package, iterated race for automatic algorithm configuration. Tech. Rep. TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium. http://iridia.ulb.ac.be/IridiaTrSeries/IridiaTr2011-004.

  • Moraglio, A., & Kattan, A. (2011). Geometric generalisation of surrogate model based optimization to combinatorial spaces. In P. Merz & J. K. Hao (Eds.), Proceedings of EvoCOP 2011—11th European conference on evolutionary computation in combinatorial optimization, Lecture notes in computer science (Vol. 6622, pp. 142–154). Heidelberg: Springer.

  • Moraglio, A., Kim, Y., & Yoon, Y. (2011). Geometric surrogate-based optimisation for permutation-based problems. In N. Krasnogor & P. L. Lanzi (Eds.), GECCO (Companion) (pp. 133–134). New York, NY: ACM Press.

    Google Scholar 

  • Pellegrini, P., Favaretto, D., & Moretti, E. (2006). On \({{\cal MAX}}\)–\({{\cal MIN}}\) Ant System’s parameters. In M. Dorigo, et al. (Eds.), Ant colony optimization and swarm intelligence, 5th international workshop, ANTS 2006, Lecture notes in computer science (Vol. 4150, pp. 203–214). Heidelberg: Springer.

  • Pellegrini, P., Mascia, F., Stützle, T., & Birattari, M. (2014). On the sensitivity of reactive tabu search to its meta-parameters. Soft Computing, 18(11), 2177–2190.

    Article  Google Scholar 

  • Pérez Cáceres, L., López-Ibáñez, M., & Stützle, T. (2014). Ant colony optimization on a budget of 1000. In M. Dorigo, et al. (Eds.), Swarm intelligence, 8th international conference, ANTS 2014, Lecture notes in computer science (Vol. 8667, pp. 50–61). Heidelberg: Springer.

  • Pérez Cáceres, L., López-Ibáñez, M., & Stützle, T. (2015). Ant colony optimization on limited budget of evaluations: Supplementary material. http://iridia.ulb.ac.be/supp/IridiaSupp2015-004.

  • Schiavinotto, T., & Stützle, T. (2007). A review of metrics on permutations for search space analysis. Computers & Operations Research, 34(10), 3143–3153.

    Article  MATH  Google Scholar 

  • Stützle, T. (2002). ACOTSP: A software package of various ant colony optimization algorithms applied to the symmetric traveling salesman problem. http://www.aco-metaheuristic.org/aco-code/.

  • Stützle, T., & Hoos, H. H. (1997). The \({{\cal MAX}}\)–\({{\cal MIN}}\) Ant System and local search for the traveling salesman problem. In T. Bäck, Z. Michalewicz, & X. Yao (Eds.), Proceedings of the 1997 IEEE international conference on evolutionary computation (ICEC’97) (pp. 309–314). Piscataway, NJ: IEEE Press.

  • Stützle, T., & Hoos, H. H. (2000). \({{\cal MAX}}\)–\({{\cal MIN}}\) Ant System. Future Generation Computer Systems, 16(8), 889–914.

    Article  Google Scholar 

  • Teixeira, C., Covas, J., Stützle, T., & Gaspar-Cunha, A. (2012). Multi-objective ant colony optimization for solving the twin-screw extrusion configuration problem. Engineering Optimization, 44(3), 351–371.

    Article  Google Scholar 

  • Zaefferer, M., Stork, J., & Bartz-Beielstein, T. (2014). Distance measures for permutations in combinatorial efficient global optimization. In T. Bartz-Beielstein, J. Branke, B. Filipič, & J. Smith (Eds.), PPSN 2014, Lecture notes in computer science (Vol. 8672, pp. 373–383). Heidelberg: Springer.

  • Zaefferer, M., Stork, J., Friese, M., Fischbach, A., Naujoks, B., & Bartz-Beielstein, T. (2014). Efficient global optimization for combinatorial problems. In C. Igel & D. V. Arnold (Eds.), Proceedings of the genetic and evolutionary computation conference (GECCO 2014) (pp. 871–878). New York, NY: ACM Press.

  • Zeng, Q., & Yang, Z. (2009). Integrating simulation and optimization to schedule loading operations in container terminals. Computers & Operations Research, 36(6), 1935–1944.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The research leading to the results presented in this paper received support from the COMEX project within the Interuniversity Attraction Poles Programme of the Belgian Science Policy Office and from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ERC Grant Agreement No. 246939. Manuel López-Ibáñez and Thomas Stützle acknowledge support from the Belgian F.R.S.-FNRS, of which they are a postdoctoral researcher and a senior research associate, respectively. Leslie Pérez Cáceres acknowledges support of CONICYT Becas Chile.

Author information

Authors and Affiliations

  1. IRIDIA, CoDE, Université libre de Bruxelles, Brussels, Belgium

    Leslie Pérez Cáceres, Manuel López-Ibáñez & Thomas Stützle

Authors
  1. Leslie Pérez Cáceres
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manuel López-Ibáñez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Thomas Stützle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Stützle.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pérez Cáceres, L., López-Ibáñez, M. & Stützle, T. Ant colony optimization on a limited budget of evaluations. Swarm Intell 9, 103–124 (2015). https://doi.org/10.1007/s11721-015-0106-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11721-015-0106-x

Keywords

Search

Navigation