Ir al contenido

Documat


A statistical learning based approach for parameter fine-tuning of metaheuristics

  • Laura Calvet [3] Árbol académico ; Angel A. Juan [3] Árbol académico ; Carles Serrat [2] Árbol académico ; Jana Ries [1]
    1. [1] University of Portsmouth

      University of Portsmouth

      Southsea, Reino Unido

    2. [2] Universitat Politècnica de Catalunya

      Universitat Politècnica de Catalunya

      Barcelona, España

    3. [3] UOC
  • Localización: Sort: Statistics and Operations Research Transactions, ISSN 1696-2281, Vol. 40, Nº. 1, 2016, págs. 201-224
  • Idioma: inglés
  • Enlaces
  • Resumen
    • Metaheuristics are approximation methods used to solve com binatorial optimization problems.

      Their performance usually depends on a set of parameters tha t need to be adjusted. The selection of appropriate parameter values causes a loss of efficiency, as it requires time, and advanced analytical and problem-specific skills. This paper provide s an overview of the principal approaches to tackle the Parameter Setting Problem, focusing on the sta tistical procedures employed so far by the scientific community. In addition, a novel methodolog y is proposed, which is tested using an already existing algorithm for solving the Multi-Depot V ehicle Routing Problem

  • Referencias bibliográficas
    • Adenso-Diaz, B. and Laguna, M.](2006). Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research,...
    • Ansótegui, C., Malitsky, Y., Samulowitz, H., Sellmann, M. and Tierney, K. (2015). Model-based genetic algorithms for algorithm configuration....
    • Bartz-Beielstein, T., Parsopoulos, K. E. and Vrahatis, M. N. (2004). Design and analysis of optimization algorithms using computational statistics....
    • Battiti, R. and Brunato, M. (2005). Reactive search: machine learning for memory-based heuristics. Technical Report Teofilo F. Gonzalez (Ed.),...
    • Battiti, R. and Brunato, M. (2010). Reactive search optimization: learning while optimizing. In Handbook of Metaheuristics (pp. 543–571)....
    • Battiti, R. and Tecchiolli, G. (1994). The reactive tabu search. ORSA journal on computing, 6, 126–140.
    • Beasley, D., Bull, D.R., Martin, R.R. et al. (1993). An overview of genetic algorithms: Part 2, research topics. University computing, 15,...
    • Birattari, M. and Kacprzyk, J. (2009). Tuning metaheuristics: a machine learning perspective, volume 197. Springer.
    • Birattari, M., Yuan, Z., Balaprakash, P. and Stützle, T. (2010). F-race and iterated f-race: An overview. In Experimental methods for the...
    • Boussaı̈d, I., Lepagnot, J. and Siarry, P. (2013). A survey on optimization metaheuristics. Information Sciences, 237 , 82–117.
    • Bovet, D.P. and Crescenzi, P. (1994). Introduction to the Theory of Complexity. Hertfordshire, UK, UK: Prentice Hall International (UK) Ltd.
    • Carvalho, A.R., Ramos, F.M. and Chaves, A.A. (2011). Metaheuristics for the feedforward artificial neural network architecture optimization...
    • Clarke, G. and Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12, 568–581.
    • Conover, W.J. (1999). Practical Nonparametric Statistics. (3rd ed.). John Wiley & Sons.
    • Coy, S. P., Golden, B.L., Runger, G.C. and Wasil, E.A. (2001). Using experimental design to find effective parameter settings for heuristics....
    • Czarn, A., MacNish, C., Vijayan, K., Turlach, B. and Gupta, R. (2004). Statistical exploratory analysis of genetic algorithms. Evolutionary...
    • De Jong, K. (2007). Parameter setting in eas: a 30 year perspective. In Parameter setting in evolutionary algorithms (pp. 1–18). Springer.
    • Dobslaw, F. (2010). A parameter tuning framework for metaheuristics based on design of experiments and artificial neural networks. In International...
    • Eiben, A.E., Hinterding, R. and Michalewicz, Z. (1999). Parameter control in evolutionary algorithms. Evolutionary Computation, IEEE Transactions...
    • Gendreau, M., Potvin, J.-Y., Bräumlaysy, O., Hasle, G. and Løkketangen, A. (2008). Metaheuristics for the vehicle routing problem and its...
    • Gunawan, A., Lau, H.C. and Wong, E. (2013). Real-world parameter tuning using factorial design with parameter decomposition. In Advances in...
    • Hastie, T., Tibshirani, R. and Friedman, J. (2009). The elements of statistical learning. (2nd ed.). Springer.
    • Hooker, J.N. (1995). Testing heuristics: We have it all wrong. Journal of Heuristics, 1 , 33–42.
    • Hutter, F., Hoos, H.H. and Leyton-Brown, K. (2011). Sequential model-based optimization for general algorithm configuration. In Learning and...
    • Hutter, F., Hoos, H.H., Leyton-Brown, K. and Stützle, T. (2009). Paramils: an automatic algorithm configuration framework. Journal of Artificial...
    • Johnson, D.S. (2002). A theoreticians guide to the experimental analysis of algorithms. Data structures, near neighbor searches, and methodology:...
    • Juan, A.A., Faulin, J., Jorba, J., Riera, D., Masip, D. and Barrios, B. (2011). On the use of monte carlo simulation, cache and splitting...
    • Juan, A.A., Pascual, I., Guimarans, D. and Barrios, B. (2015). Combining biased randomization with iterated local search for solving the multidepot...
    • Lessmann, S., Caserta, M. and Arango, I.M. (2011). Tuning metaheuristics: A data mining based approach for particle swarm optimization. Expert...
    • Maron, O. and Moore, A.W. (1993). Hoeffding races: Accelerating model selection search for classification and function approximation. Robotics...
    • Martins, S.L. and Ribeiro, C.C. (2006). Metaheuristics and applications to optimization problems in telecommunications. In Handbook of optimization...
    • Montero, E., Riff, M.-C. and Neveu, B. (2014). A beginner’s guide to tuning methods. Applied Soft Computing, 17, 39–51.
    • Montgomery, D.C. (2008). Design and analysis of experiments. (8th ed.). John Wiley & Sons.
    • Park, M.-W. and Kim, Y.-D. (1998). A systematic procedure for setting parameters in simulated annealing algorithms. Computers & Operations...
    • Pavón, R., Dı́az, F., Laza, R. and Luzón, V. (2009). Automatic parameter tuning with a bayesian case-based reasoning system. a case...
    • Pongcharoen, P., Chainate, W. and Thapatsuwan, P. (2007). Exploration of genetic parameters and operators through travelling salesman problem....
    • Ramos, I.C., Goldbarg, M.C., Goldbarg, E.G. and Neto, A.D.D. (2005). Logistic regression for parameter tuning on an evolutionary algorithm....
    • Ridge, E. and Kudenko, D. (2007). Analyzing heuristic performance with response surface models: prediction, optimization and robustness. In...
    • Ries, J. (2009). Instance-based flexible parameter tuning for meta-heuristics using fuzzy-logic. Ph.D. thesis University of Portsmouth.
    • Ries, J., Beullens, P. and Salt, D. (2012). Instance-specific multi-objective parameter tuning based on fuzzy logic. European Journal of Operational...
    • Rousseeuw, P.J. (1987). Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and...
    • Smith, J.E. (2008). Self-adaptation in evolutionary algorithms for combinatorial optimisation. In Adaptive and Multilevel Metaheuristics (pp....
    • Talbi, E.-G. (2009). Metaheuristics: from design to implementation, volume 74. John Wiley & Sons.
    • Theodoridis, S. and Koutroumbas, K. (2009). Pattern Recognition, volume 74. John Wiley & Sons.
    • Viana, A., Sousa, J.P. and Matos, M.A. (2005). Constraint oriented neighbourhoodsa new search strategy in metaheuristics. InMetaheuristics:...
    • Xu, J., Chiu, S.Y. and Glover, F. (1998). Fine-tuning a tabu search algorithm with statistical tests. International Transactions in Operational...
    • Zennaki, M. and Ech-Cherif, A. (2010). A new machine learning based approach for tuning metaheuristics for the solution of hard combinatorial...

Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno