Abstract
Stochastic local search (SLS) methods like evolutionary algorithms, ant colony optimisation or iterated local search receive an ever increasing attention for the solution of highly application relevant optimisation problems. Despite their noteworthy successes, several issues still hinder their even wider spread. One central issue is the configuration and parameterisation of SLS methods, which is known to be a time- and personal-intensive process. Recently, several attempts have been made to automate the tuning of SLS algorithms. One of the most promising directions is the usage of the racing methodology, which is a statistical method for selecting promising candidate configurations. We present results of a study on the application of this methodology to the tuning of a complex SLS method for an industrial vehicle scheduling and routing problem, and compare the performance of two racing methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hoos, H.H., Stützle, T.: Stochastic Local Search—Foundations and Applications. Morgan Kaufmann, San Francisco (2004)
Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, Cambridge (1996)
Moscato, P., Cotta, C.: A gentle introduction to memetic algorithms. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 105–144. Kluwer Academic Publishers, Norwell (2002)
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Lourenço, H.R., Martin, O., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 321–353. Kluwer Academic Publishers, Norwell (2002)
Xu, J., Chiu, S.Y., Glover, F.: Fine-tuning a tabu search algorithm with statistical tests. International Transactions in Operational Research 5(4), 233–244 (1998)
Coy, S.P., Golden, B.L., Runger, G.C., Wasil, E.A.: Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics 7(1), 77–97 (2001)
Adenso-Díaz, B., Laguna, M.: Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research (in press)
Birattari, M., Stützle, T., Paquete, L., Varrentrapp, K.: A racing algorithm for configuring metaheuristics. In: Langdon, W.B., others (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), pp. 11–18. Morgan Kaufmann, San Francisco (2002)
Birattari, M.: The Problem of Tuning Metaheuristics. PhD thesis, IRIDIA, Université Libre de Bruxelles, Belgium (2004)
Siegel, S., Jr., N.J.C., Castellan, N.J.: Nonparametric Statistics for the Behavioral Sciences, 2nd edn. McGraw Hill, New York (2000)
Sheskin, D.J.: Handbook of Parametric and Nonparametric Statistical Procedures. Chapman & Hall / CRC (2000)
Chiarandini, M., Birattari, M., Socha, K., Rossi-Doria, O.: An effective hybrid approach for the university course timetabling problem. Journal of Scheduling (submitted)
Maron, O., Moore, A.W.: Hoeffding races: Accelerating model selection search for classification and function approximation. In: Cowan, J.D., Tesauro, G., Alspector, J. (eds.) Advances in Neural Information Processing Systems, vol. 6, pp. 59–66. Morgan Kaufmann Publishers, Inc, San Francisco (1994)
Moore, A.W., Lee, M.S.: Efficient algorithms for minimizing cross validation error. In: International Conference on Machine Learning, pp. 190–198. Morgan Kaufmann Publishers, Inc., San Francisco (1994)
Conover, W.J.: Practical Nonparametric Statistics, 3rd edn. John Wiley & Sons, New York (1999)
Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Becker, S., Gottlieb, J., Stützle, T. (2006). Applications of Racing Algorithms: An Industrial Perspective. In: Talbi, EG., Liardet, P., Collet, P., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2005. Lecture Notes in Computer Science, vol 3871. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11740698_24
Download citation
DOI: https://doi.org/10.1007/11740698_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33589-4
Online ISBN: 978-3-540-33590-0
eBook Packages: Computer ScienceComputer Science (R0)