×

Machine learning for global optimization. (English) Zbl 1243.90178

Summary: We introduce the LeGO (Learning for Global Optimization) approach for global optimization in which machine learning is used to predict the outcome of a computationally expensive global optimization run, based upon a suitable training performed by standard runs of the same global optimization method. We propose to use a Support Vector Machine (although different machine learning tools might be employed) to learn the relationship between the starting point of an algorithm and the final outcome (which is usually related to the function value at the point returned by the procedure). Numerical experiments performed both on classical test functions and on difficult space trajectory planning problems show that the proposed approach can be very effective in identifying good starting points for global optimization.

MSC:

90C26 Nonconvex programming, global optimization
68T05 Learning and adaptive systems in artificial intelligence
90C59 Approximation methods and heuristics in mathematical programming

Software:

LIBSVM; PSwarm
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Addis, B., Cassioli, A., Locatelli, M., Schoen, F.: A global optimization method for the design of space trajectories. COAP, published on line (2009). doi: 10.1007/s10589-009-9261-6 · Zbl 1223.90043
[2] Addis, B., Locatelli, M., Schoen, F.: Local optima smoothing for global optimization. Optim. Methods Softw. 20(45), 417–437 (2005) · Zbl 1134.90035 · doi:10.1080/10556780500140029
[3] Ampatzis, C., Izzo, D.: Machine learning techniques for approximation of objective functions in trajectory optimisation. In: Proceedings of the IJCAI-09 Workshop on Artificial Intelligence in Space, pp. 1–6 (2009)
[4] Burges, C.J.C.: A tutorial on support vector machines for pattern recognition. Data Min. Knowl. Discov. 2(2), 121–167 (1998) · Zbl 05470543 · doi:10.1023/A:1009715923555
[5] Byrd, R.H., Nocedal, J., Lu, P., Zhu, C.: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. Tech. Rep., Northwestern University, Department of Electrical Engineering and Computer Science (1995) · Zbl 0912.65057
[6] Chang, C.-C., Lin, C.-J.: LIBSVM: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/\(\sim\)cjlin/libsvm (2001)
[7] Dill, K.A., Phillips, A.T., Rosen, J.B.: CGU: an algorithm for molecular structure prediction. In: Bigler, L.T., Coleman, T.F., Conn, A.R., Santosa, F.N. (eds.) Large-Scale Optimization with Applications. Part 3: Molecular Structure and Optimization, vol. 94, pp. 1–21. Springer, Berlin (1997) · Zbl 0884.65050
[8] Dill, K.A., Phillips, A.T., Rosen, J.B.: Protein structure and energy landscape dependence on sequence using a continuous energy function. J. Comput. Biol. 4(3), 227–240 (1997) · doi:10.1089/cmb.1997.4.227
[9] Grosso, A., Locatelli, M., Schoen, F.: A population based approach for hard global optimization problems based on dissimilarity measures. Math. Programm. 110(2), 373–404 (2007) · Zbl 1116.90084 · doi:10.1007/s10107-006-0006-3
[10] Izzo, D., Becerra, V., Myatt, D., Nasuto, S., Bishop, J.: Search space pruning and global optimisation of multiple gravity assist spacecraft trajectories. J. Global Optim. 38, 283–296 (2007) · Zbl 1179.90342 · doi:10.1007/s10898-006-9106-0
[11] Jin, Y.: A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput. Fusion Found. Methodol. Appl. 9(1), 3–12 (2005)
[12] Jin, Y., Olhofer, M., Sendhoff, B.: A framework for evolutionary optimization with approximate fitness functions. IEEE Trans. Evol. Comput. 6(5), 481–494 (2002) · Zbl 05452037 · doi:10.1109/TEVC.2002.800884
[13] Leary, R.H.: Global optimization on funneling landscapes. J. Global Optim. 18, 367–383 (2000) · Zbl 0986.90038 · doi:10.1023/A:1026500301312
[14] Lourenço, H.R., Martin, O.C., Stülze, T.: Iterated local search. In: Glover, F.W., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, pp. 321–353. Kluwer Academic, Dordrecht (2003) · Zbl 1116.90412
[15] Mangasarian, O.L., Rosen, J.B., Thompson, M.E.: Global minimization via piecewise-linear underestimation. J. Global Optim. 32(1), 1–9 (2005) · Zbl 1098.90072 · doi:10.1007/s10898-004-5907-1
[16] Olympio, J.T., Marmorat, J.-P.: Global trajectory optimization: can we prune the solution space when considering deep space manoeuvres? Final Report, ESA (2008)
[17] Rinnooy Kan, A.H.G., Timmer, G.T.: Stochastic global optimization methods. Part I: Clustering methods. Math. Programm. 39, 27–56 (1987) · Zbl 0634.90066 · doi:10.1007/BF02592070
[18] Rinnooy Kan, A.H.G., Timmer, G.T.: Stochastic global optimization methods. Part II: Multi level methods. Math. Programm. 39, 57–78 (1987) · Zbl 0634.90067 · doi:10.1007/BF02592071
[19] Schölkopf, B., Smola, A.J.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, Cambridge (2002)
[20] Vapnik, V.N.: Statistical Learning Theory. Wiley, New York (1998) · Zbl 0935.62007
[21] Vasile, M.: Design of Earth-Mars transfer trajectories using evolutionary-branching technique. Acta Astronaut. 56, 705–720 (2005) · doi:10.1016/j.actaastro.2004.12.002
[22] Vaz, I.F., Vicente, L.N.: A particle swarm pattern search method for bound constrained global optimization. J. Glob. Optim. 39, 197–219 (2007) · Zbl 1180.90252 · doi:10.1007/s10898-007-9133-5
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.