×

zbMATH — the first resource for mathematics

Generating meta-heuristic optimization code using ADATE. (English) Zbl 1198.90408
Summary: Local Search based meta-heuristic methods for finding good solutions to hard combinatorial optimization problems have attained a lot of success, and a plethora of methods exist, each with its own successes, and also with its own parameter settings and other method-specific details. At the same time, experience is needed to implement highly competitive code, and some of the experience applied is not easy to quantify.
ADATE is a system to automatically generate code based on a set of input-output specifications, and can work in vastly different domains. It generates code in a subset of the programming language ML and works by searching for transformations of purely functional ML programs.
Code automatically generated by the ADATE system compares with state-of-the-art handcrafted meta-heuristic optimization code. In particular, the programs generated by ADATE target the move selection part of BOOP-Boolean Optimization Problems. The baseline is a highly successful Tabu Search implementation. Comparisons are made for versions running for a limited number of iterations, being suitable for applications needing a short response time. The computational results show that the ADATE system is able to generate highly competitive code that produces more optimal solutions to hard BOOP instances within given iteration limits than the previously published Tabu Search implementation. The automatically generated code also gives new insights into the general design of meta-heuristic mechanisms, and contains novel search mechanisms.
MSC:
90C59 Approximation methods and heuristics in mathematical programming
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bader-El-Din, M.B., Poli, R.: Generating sat local-search heuristics using a gp hyper-heuristic framework. In: Proceedings of the 8th International Conference on Artificial Evolution. LNCS, vol. 4926, pp. 37–49. Springer, Berlin (2007)
[2] Burke, E.K., Kendall, G., Hart, J., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology. In: Glover, F., Kochenbergerm, G. (eds.) Handbook of Meta-Heuristics, Chap. 16, pp. 457–474 (2003) · Zbl 1102.90377
[3] Burke, E.K., Hyde, M.R., Kendall, G., Woodward, J.: Automatic heuristic generation with genetic programming: evolving a jack-of-all-trades or a master of one. In: Proceedings of the 9th ACM Genetic and Evolutionary Computation Conference (GECCO’07), London, UK, pp. 1559–1565 (2007)
[4] Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.: A classification of hyper-heuristics approaches. Computer Science Technical Report No. NOTTCS-TR-SUB-0907061259-5808, School of Computer Science and Information Technology, University of Nottingham (2009a) · Zbl 1184.68207
[5] Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Qu, R.: A survey of hyper-heuristics. Computer Science Technical Report No. NOTTCS-TR-SUB-0906241418-2747, School of Computer Science and Information Technology, University of Nottingham (2009b)
[6] Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third ACM Symposium on Theory of Computing, pp. 151–158 (1971) · Zbl 0253.68020
[7] Davoine, T., Hammer, P.L., Vizvári, B.: A heuristic for Boolean optimization problems. J. Heuristics 9, 229–247 (2001) · Zbl 1035.90069 · doi:10.1023/A:1023717307746
[8] Du, D., Gu, J., Pardalos, P.: Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 35 (1997) · Zbl 0881.00041
[9] Fukunaga, A.S.: Automated discovery of local search heuristics for satisfiability testing. Evol. Comput. 16(1), 31–61 (2008) · Zbl 05514036 · doi:10.1162/evco.2008.16.1.31
[10] Geiger, C.D., Uzsoy, R., Aytug, H.: Rapid modeling and discovery of priority dispatching rules: an autonomous learning approach. J. Sched. 9(1), 7–34 (2006) · Zbl 1154.90451 · doi:10.1007/s10951-006-5591-8
[11] Hvattum, L.M., Løkketangen, A., Glover, F.: Adaptative memory search for Boolean optimization problems. Discrete Appl. Math. 142, 99–109 (2004). Special issue on Boolean and pseudo-Boolean functions · Zbl 1122.90052 · doi:10.1016/j.dam.2003.06.006
[12] Hvattum, L.M., Løkketangen, A., Glover, F.: New heuristics and adaptive memory procedures for Boolean optimization problems. In: Karlof, J. (ed.) Integer Programming: Theory and Practice, pp. 1–18. CRC Press, Boca Raton (2006) · Zbl 1117.90051
[13] Geard, N., Wiles, J., Hallinan, J., Tonkes, B., Skellett, B.: A comparison of neutral landscapes–nk, nkp and nkq. In: Proceedings of the 2002 Congress on Evolutionary Computation (2002)
[14] Glover, F., Laguna, M.: Tabu Search. Springer, Berlin (1997)
[15] Hoos, H.: On the run-time behaviour of stochastic local search methods for SAT. In: Proceedings of AAAI, pp. 661–666 (1969)
[16] Kimura, M.: The Neutral Theory of Molecular Evolution. Cambridge University Press, Cambridge (1983)
[17] Linnaeus, C.: Systema Naturae per Regna Tria Naturae, Secundum Classes, Ordines, Genera, Species Cum Caracteribus, Differentiis, Synonymis, Locis, 10th edn. Laurentii Salvii, Stockholm (1758)
[18] Miller, G.A.: The magical number 7, plus or minus 2. Psychol. Rev. 63, 81–97 (1956) · doi:10.1037/h0043158
[19] Milner, R., Tofte, M., Harper, R., MacQueen, D.: The Definition of Standard ML. MIT Press, Cambridge (1997). (Revised)
[20] Olsson, R.: Inductive functional programming using incremental program transformation. Artif. Intell. 1, 55–83 (1995) · doi:10.1016/0004-3702(94)00042-Y
[21] Riedmiller, M., Braun, H.: A direct adaptive method for faster backpropagation learning: the rprop algorithm. In: International Conference on Neural Networks, San Francisco (1993)
[22] Schwefel, H.-P.: Evolution and Optimum Seeking. Wiley, New York (1995)
[23] Selman, B., Kautz, H., Cohen, B.: Local Search Strategies for Satisfiability Testing. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26 (1996) · Zbl 0864.90093
[24] Tay, J.C., Ho, N.B.: Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput. Ind. Eng. 54(3), 453–473 (2008) · doi:10.1016/j.cie.2007.08.008
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.