Wednesday , June 20 2018

Improving Simulated Annealing Performance by means of
Automatic Parameter Tuning

Pablo CABRERA-GUERRERO1,*, Guillermo GUERRERO1,
Jorge VEGA2, Franklin JOHNSON3

1 Pontificia Universidad Católica de Valparaíso, Chile
pablo.cabrera.g@mail.pucv.cl
2 Universidad de Antofagasta, Escuela de Ingeniería Electrica, Chile
jvega@antofa.cl
3 Universidad de Playa Ancha, Chile
fjohnson@upla.cl

* Corresponding author

Abstract: A common problem when using (meta)-heuristic techniques to solve complex combinatorial optimization problems is related to parameters tuning. Finding “the right” parameter values can lead to significant improvements in terms of best solution objective value found by the heuristic, heuristic reliability and heuristic convergence, among others. Unfortunately, this is usually a tedious and complicated task if done manually. In this paper, we propose a framework that is based on Genetic Programming to fine-tune a key parameter of the well-known Simulated Annealing (SA) algorithm. Experiments on a set of small instances of the Facility Location Problem with capacity constraints are performed. Results show that automatically adjusting a key parameter in SA by means of Genetic Programming leads to an average value of the obtained solution that is closer to the optimal solution than the average value obtained by the simple SA algorithm with a priori selected values. More important, standard deviation of the algorithm is greatly improved by our approach which makes it much more reliable if time limitations are imposed.

Keywords: Genetic Programming, Simulated Annealing, Combinatorial Optimization, Automatic Parameter Tuning.

>>Full text<<
CITE THIS PAPER AS:
Pablo CABRERA-GUERRERO, Guillermo GUERRERO, Jorge VEGA, Franklin JOHNSON, Improving Simulated Annealing Performance by means of Automatic Parameter Tuning, Studies in Informatics and Control, ISSN 1220-1766, vol. 24 (4), pp. 419-426, 2015.

  1. Introduction

Optimization algorithms have been widely studied in literature. While exact methods are very efficient in solving small and medium size problems, they fail on finding (nearly) optimal solutions for large scale optimization problems [1]. When exact algorithms cannot be used directly on such large scale complex optimization problems, heuristic methods are very helpful. During the past five decades an increasing number of (meta-)heuristics have been developed to provide “good” solutions within an acceptable computational time. Although (meta-)heuristic techniques cannot ensure optimality (as exact method does), they have demonstrated to be very effective on solving complex large-scale combinatorial optimization problems.

One key element in the success of a (meta-)heuristic method is its parameters configuration. It has been shown that fine parameter tuning can lead to great improvements on the final solution quality as well as on the technique behaviour [2,3,4,5]. Unfortunately, fine tuning task is quite time consuming and problem-specific. Automatic parameter tuning has been widely studied in the literature (see [4,5,6]). In this paper we propose a genetic programming [7] algorithm to adjust a key parameter of a well-known local search heuristic namely Simulated Annealing (SA) [12]. We test our approach on a set of instances of the Capacitated Facility Location problem (CFLP), obtained from the OR Library [8].

The idea is to let Genetic Programming finds a good value of a key parameter in SA which leads to an improvement in both final objective function value found by the heuristic method and heuristic behaviour (reliability, convergence, etc).

REFERENCES

  1. CABRERA, G., E. CABRERA, R. SOTO, J. M. RUBIO, B. CRAWFORD, F. PAREDES, A Hybrid Approach using an Artificial Bee Algorithm with Mixed Integer Programming Applied to a Large-scale Capacitated Facility Location Problem, Mathematical Problems in Engineering, vol. 2012, 2012.
  1. GLOVER, F., M. LAGUNA, Tabu Search . Norwell, MA, USA: Kluwer Academic Publishers, 1997.
  2. HOOS, H. Automated Algorithm Configuration and Parameter Tuning, in Autonomous Search, Y. Hamadi, E. Monfroy, and F. Saubion, Eds. Springer Berlin Heidelberg, 2012, pp. 37-71.
  3. VERA-PÉREZ, O. L., A. MESEJO-CHIONG, A. JAUME-I-CAPÓ, M. GONZÁLEZ-HIDALGO, Automatic Parameter Configuration: A Case Study on a Rehabilitation Oriented Human Limb Tracking Algorithm, Studies in Informatics and Control , vol. 23, no. 3, 2014, pp. 313-323.
  4. MORI, M., R. KOBAYASHI, M. SAMEJIMA, N. KOMODA, Cost-benefit Analysis of Decentralized Ordering on Multitier Supply Chain by Risk Simulator, Studies in Informatics and Control , vol. 21, no. 1, 2012, pp. 75-83.
  5. CRAWFORD, B., C. VALENZUELA, R. SOTO, E. MONFROY, F., PAREDES, Parameter Tuning of Metaheuristics using Metaheuristics, Adv. Sc. Letters, vol. 19, no. 12, 2013, pp. 3556-3559.
  6. KOZA, J. Genetic Programming as a Means for Programming Computers by Natural Selection. Kluwer Academic Publishers, vol. 4, no. 2, 1994.
  7. BEASLEY, J. An Algorithm for Solving Large Capacitated Warehouse Location Problems, European Journal of Operational Research, vol. 33, no. 3, 1998, pp. 314-325.
  8. BÖLTE, A., U. W. THONEMANN, Optimizing Simulated Annealing Schedules with Genetic Programming, European Journal of Operational Research , vol. 92, no. 2, 1996, pp. 402-416.
  9. KIRKPATRICK, S., Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics, vol. 34, no. 5-6, 1984, pp. 975-986.
  10. KIRKPATRICK S., C. D. GELATT, M. P. VECCHI, Optimization by Simulated Annealing. Science, vol. 220, no. 4598, 1983, pp. 671-680.
  11. METROPOLIS, N., A. W. ROSENBLUTH, M. N. ROSENBLUTH, A. H. TELLER, E. TELLER, Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics vol. 21, no. 6, 1953, pp. 1087-1092.
  12. CABRERA, G., S. RONCAGLIOLO, J. P. RIQUELME, C. CUBILLOS, R. SOTO, A Hybrid Particle Swarm Optimization-Simulated Annealing Algorithm for the Probabilistic Travelling Salesman Problem. Studies in Informatics and Control vol. 21, 2012, pp. 49-58.
  13. LIU, S., W. H. WU, C. C. KANG, W. C. LIN, Z. CHENG, A Single-machine Two-agent Scheduling Problem by a Branch-and-Bound and Three Simulated Annealing Algorithms. Discrete Dynamics in Nature and Society, vol. 2015, 2015, Article ID 681854.
  14. QIN, J., H. XIANG, Y. YE, L. NI, A Simulated Annealing Methodology to Multiproduct Capacitated Facility Location with Stochastic Demand. The Scientific World Journal vol. 2015, 2015, Article ID 826363.
  15. WILHELM, M., T. WARD, Solving Quadratic Assignment Problems by Simulated Annealing. IIE Transactions, vol. 19, no. 1, 1987, pp. 107-119.
  16. FOGEL, L. J., A. J. OWENS, M. J. WALSH, Artificial Intelligence through Simulated Evolution. New York, USA: John Wiley, 1966.
  17. HOLLAND, J. H. Adaptation in Natural and Artificial Systems. Ann Arbor, MI, USA: University of Michigan Press, 1975.
  18. RECHENBERG, I., Evolutionsstrategie: Optimierung technischer systeme nach prinzipien der biologischen evolution, Ph.D. dissertation, TU Berlin, 1971.
  19. EGGERMONT, J., Data Mining using Genetic Programming: Classification and Symbolic Regression, PhD dissertation, Universiteit Leiden, September 2005.
  20. WALKER, M., Introduction to Genetic Programming, Computer Science Department, Montana State University, Tech. Rep., December 2001.
  21. BEASLEY, J., OR-Library: Distributing Test Problems by Electronic Mail, Journal of the Operational Research Society , vol. 41(11), 1990, pp. 1069-1072.

https://doi.org/10.24846/v24i4y201506