Efficient hybrid methods for global continuous optimization based on simulated annealing. (English) Zbl 1079.90107
Summary: We introduce several hybrid methods for global continuous optimization. They combine simulated annealing and a local proximal bundle method. Traditionally, the simplest hybrid of a global and a local solver is to call the local solver after the global one, but this does not necessarily produce good results. Besides, using efficient gradient-based local solvers implies that the hybrid can only be applied to differentiable problems. We show several ways how to integrate the local solver as a genuine part of simulated annealing to enable both efficient and reliable solution processes. When using the proximal bundle method as a local solver, it is possible to solve even nondifferentiable problems. The numerical tests show that the hybridization can improve both the efficiency and the reliability of simulated annealing.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Floudas CA, Pardalos PM, editors. Recent advances in global optimization. Princeton, NJ: Princeton University Press; 1992.; Floudas CA, Pardalos PM, editors. Recent advances in global optimization. Princeton, NJ: Princeton University Press; 1992. |
| [2] | Horst R, Pardalos PM, editors. Handbook of global optimization. Dordrecht: Kluwer Academic Publishers; 1995.; Horst R, Pardalos PM, editors. Handbook of global optimization. Dordrecht: Kluwer Academic Publishers; 1995. · Zbl 0805.00009 |
| [3] | Preux, Ph.; Talbi, E.-G., Towards hybrid evolutionary algorithms, International Transactions in Operational Research, 6, 6, 557-570 (1999) |
| [4] | Talbi, E.-G., Taxonomy of hybrid metaheuristics, Journal of Heuristics, 8, 5, 541-564 (2002) |
| [5] | Yen, J.; Liao, J. C.; Lee, B.; Randolph, D., A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method, IEEE Transactions on Systems, Man, and Cybernetics—Part BCybernetics, 28, 2, 173-191 (1998) |
| [6] | Goffe, W. L.; Ferrier, G. D.; Rogers, J., Global optimization and statistical functions with simulated annealing, Journal of Econometrics, 60, 1-2, 65-99 (1994) · Zbl 0789.62095 |
| [7] | Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equation of state calculation by fast computing machines, Journal of Chemical Physics, 21, 6, 1087-1092 (1953) · Zbl 1431.65006 |
| [8] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162 |
| [9] | Ingber, L., Adaptive simulated annealing (ASA)lessons learned, Control and Cybernetics, 25, 1, 33-54 (1996) · Zbl 0860.93035 |
| [10] | Ingber, L., Simulated annealingpractice versus theory, Mathematical and Computer Modelling, 18, 11, 29-57 (1993) · Zbl 0819.90080 |
| [11] | Locatelli, M., Simulated annealing algorithms for continuous global optimizationconvergence conditions, Journal of Optimization Theory and Applications, 104, 1, 121-133 (2000) · Zbl 0970.90102 |
| [12] | Yang, R. L., Convergence of the simulated annealing algorithm for continuous global optimization, Journal of Optimization Theory and Applications, 104, 3, 691-716 (2000) · Zbl 1060.90085 |
| [13] | Aluffi-Pentini, F.; Parisi, V.; Zirilli, F., Global optimization and stochastic differential equations, Journal of Optimization Theory and Applications, 47, 1-16 (1985) · Zbl 0549.65038 |
| [14] | Vanderbilt, D.; Louie, S. G., A Monte Carlo simulated annealing approach to optimization over continuous variables, Journal of Computational Physics, 56, 259-271 (1984) · Zbl 0551.65045 |
| [15] | Ali, M. M.; Törn, A.; Viitanen, S., A direct search variant of the simulated annealing algorithm for optimization involving continuous variables, Computers & Operations Research, 29, 1, 87-102 (2002) · Zbl 1026.90101 |
| [16] | Bilbro, G.; Snyder, W., Optimization of functions with many minima, IEEE Transactions on Systems, Man, and Cybernetics, 21, 4, 840-849 (1991) |
| [17] | Decker, A.; Aarts, E., Global optimization and simulated annealing, Mathematical Programming, 50, 3, 367-393 (1991) · Zbl 0753.90060 |
| [18] | Hedar, A.-L.; Fukushima, M., Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization, Optimization Methods and Software, 17, 5, 891-912 (2002) · Zbl 1065.90081 |
| [19] | Özdamar, L.; Demirhan, M., Experiments with new stochastic global optimization search techniques, Computers & Operations Research, 27, 9, 841-865 (2000) · Zbl 0967.90086 |
| [20] | Salhi, S.; Queen, N. M., A hybrid algorithm for identifying global and local minima when optimizing functions with many minima, European Journal of Operational Research, 155, 1, 51-67 (2004) · Zbl 1053.90058 |
| [21] | Schittkowski, K., More test examples for nonlinear programming codes (1987), Springer: Springer Berlin · Zbl 0658.90060 |
| [22] | Wang, P. P.; Chen, D.-S., Continuous optimization by a variant of simulated annealing, Computational Optimization and Applications, 6, 1, 59-71 (1996) · Zbl 0852.90120 |
| [23] | Kiwiel, K. C., Proximity control in bundle methods for convex non-differentiable optimization, Mathematical Programming, 46, 1, 105-122 (1990) · Zbl 0697.90060 |
| [24] | Mäkelä, M. M.; Neittaanmäki, P., Nonsmooth optimizationanalysis and algorithms with applications to optimal control (1992), World Scientific Publishing Co.: World Scientific Publishing Co. Singapore · Zbl 0757.49017 |
| [25] | Lemaréchal, C., Nondifferentiable optimization, (Nemhauser, G. L.; Rinnooy Kan, A. H.G.; Todd, M. J., Optimization (1989), North-Holland: North-Holland Amsterdam), 529-572 · Zbl 0688.90034 |
| [26] | Clarke, F. H., Optimization and nonsmooth analysis (1983), Wiley: Wiley New York · Zbl 0727.90045 |
| [27] | SIMANN—Fortran simulated annealing code used in [6]. Available at http://wueconb.wustl.edu/\( \sim;\); SIMANN—Fortran simulated annealing code used in [6]. Available at http://wueconb.wustl.edu/\( \sim;\) |
| [28] | Haarala M, Miettinen K, Mäkelä MM. New limited memory bundle method for large-scale nonsmooth optimization. Optimization Methods and Software 2004;19(6):673-92.; Haarala M, Miettinen K, Mäkelä MM. New limited memory bundle method for large-scale nonsmooth optimization. Optimization Methods and Software 2004;19(6):673-92. · Zbl 1068.90101 |
| [29] | Genetic and evolutionary algorithm toolbox for use with MatLab, http://www.geatbx.com/; Genetic and evolutionary algorithm toolbox for use with MatLab, http://www.geatbx.com/ |
| [30] | Test problems for global optimization, http://www.imm.dtu.dk/\( \sim;\); Test problems for global optimization, http://www.imm.dtu.dk/\( \sim;\) |
| [31] | Trafalis, B.; Kasap, S., A novel metaheuristics approach for continuous global optimization, Journal of Global Optimization, 23, 2, 171-190 (2002) · Zbl 1175.90320 |
| [32] | Kiwiel, K. C., A method for solving certain quadratic programming problems arising in nonsmooth optimization, IMA Journal of Numerical Analysis, 6, 137-152 (1986) · Zbl 0603.65041 |
| [33] | Battiti, R.; Tecchiolli, G., The continuous reactive tabu searchblending combinatorial optimization and stochastic search for global optimization, Annals of Operations Research, 63, 153-188 (1996) · Zbl 0851.90093 |
| [34] | Bessaou, M.; Siarry, P., A genetic algorithm with real-value coding to optimize multimodal continuous functions, Structural and Multidisciplinary Optimization, 23, 1, 63-74 (2001) |
| [35] | Chelouah, R.; Siarry, P., Tabu search applied to global optimization, European Journal of Operational Research, 123, 2, 256-270 (2000) · Zbl 0961.90037 |
| [36] | Chelouah R, Siarry P. A hybrid method combining continuous tabu search and Nelder-Mead simplex algorithms for the global optimization of multiminima functions. European Journal of Operational Research, in press.; Chelouah R, Siarry P. A hybrid method combining continuous tabu search and Nelder-Mead simplex algorithms for the global optimization of multiminima functions. European Journal of Operational Research, in press. · Zbl 1071.90035 |
| [37] | Ji M, Tang H. Global optimizations and tabu search based on memory. Applied Mathematics and Computation 2004;159(2):449-57.; Ji M, Tang H. Global optimizations and tabu search based on memory. Applied Mathematics and Computation 2004;159(2):449-57. · Zbl 1057.65036 |
| [38] | Siarry, P.; Berthiau, G., Fitting of tabu search to optimize functions of continuous variables, International Journal for Numerical Methods in Engineering, 40, 13, 2449-2457 (1997) · Zbl 0882.65049 |
| [39] | Siarry, P.; Berthiau, G.; Durdin, F.; Haussy, J., Enhanced simulated annealing for globally minimizing functions of many-continuous variables, ACM Transactions on Mathematical Software, 23, 2, 209-228 (1997) · Zbl 0887.65067 |
| [40] | Maaranen H, Miettinen K, Mäkelä MM. Quasi random initial population for genetic algorithms. Computers & Mathematics with Applications 2004;47(12):1885-95.; Maaranen H, Miettinen K, Mäkelä MM. Quasi random initial population for genetic algorithms. Computers & Mathematics with Applications 2004;47(12):1885-95. · Zbl 1074.90036 |
| [41] | Ali MM, Storey C. Aspiration based simulated annealing algorithm. Journal of Global Optimization 1997;11(2):181-91.; Ali MM, Storey C. Aspiration based simulated annealing algorithm. Journal of Global Optimization 1997;11(2):181-91. · Zbl 0889.90127 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
