×

A simulated annealing hyper-heuristic methodology for flexible decision support. (English) Zbl 1241.90077

Summary: Most of the current search techniques represent approaches that are largely adapted for specific search problems. There are many real-world scenarios where the development of such bespoke systems is entirely appropriate. However, there are other situations where it would be beneficial to have methodologies which are generally applicable to more problems. One of our motivating goals for investigating hyper-heuristic methodologies is to provide a more general search framework that can be easily and automatically employed on a broader range of problems than is currently possible. In this paper, we investigate a simulated annealing hyper-heuristic methodology which operates on a search space of heuristics and which employs a stochastic heuristic selection strategy and a short-term memory. The generality and performance of the proposed algorithm is demonstrated over a large number of benchmark datasets drawn from two very different and difficult problems, namely; course timetabling and bin packing. The contribution of this paper is to present a method which can be readily (and automatically) applied to different problems whilst still being able to produce results on benchmark problems which are competitive with bespoke human designed tailor made algorithms for those problems.

MSC:

90B90 Case-oriented studies in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdullah S, Burke EK, McCollum B (2007) Using a randomised iterative improvement algorithm with composite neighbourhood structures for the university course timetabling problem. In: Doerner KF, Gendreau M, Greistorfer P, Gutjahr G, Hartl RF, Reimann M (eds) Metaheuristics–progress in complex systems optimization. Springer, New York, pp 153–169 · Zbl 1172.90393
[2] Alvim ACF, Ribeiro CC, Glover F, Aloise DJ (2004) A hybrid improvement heuristic for the one-dimensional bin packing problem. J Heuristics 10: 205–229 · doi:10.1023/B:HEUR.0000026267.44673.ed
[3] Asmuni H, Burke EK, Garibaldi JM (2005) Fuzzy multiple heuristic ordering for course timetabling. In: Proceedings of the 5th United Kingdom workshop on computational intelligence (UKCI05), London, UK, pp 302–309
[4] Bai R, Kendall G (2005) An investigation of automated planograms using a simulated annealing based hyper-heuristic. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solver–(Operations research/computer science interface series, vol 32). Springer, New York, pp 87–108
[5] Belov G, Scheithauer G (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. Eur J Oper Res 171(1): 85–106 · Zbl 1091.90080 · doi:10.1016/j.ejor.2004.08.036
[6] Burke EK, Kendall G (2005) Search methodologies: introductory tutorials in optimization and decision support techniques. Kluwer, Dordrecht · Zbl 1140.90015
[7] Burke EK, Bykov Y, Newall J P, Petrovic S (2003a) A time-predefined approach to course timetabling. Yugosl J Oper Res 13(2): 139–151 · Zbl 1055.90039 · doi:10.2298/YJOR0302139B
[8] Burke EK, Kendall G, Soubeiga E (2003b) A tabu-search hyperheuristic for timetabling and rostering. J Heuristics 9: 451–470 · doi:10.1023/B:HEUR.0000012446.94732.b6
[9] Burke EK, Petrovic S, Qu R (2006) Case based heuristic selection for timetabling problems. J Sched 9(2): 115–132 · Zbl 1154.90423 · doi:10.1007/s10951-006-6775-y
[10] Burke EK, McCollum B, Meisels A, Petrovic S, Qu R (2007) A graph-based hyper-heuristic for timetabling problems. Eur J Oper Res 176(1): 177–192 · Zbl 1137.90602 · doi:10.1016/j.ejor.2005.08.012
[11] Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Woodward JR (2009) A classification of hyper- heuristic approaches. In: Gendreau M, Potvin J-Y (eds) Handbook of metaheursistics. Springer, New York, pp 449–468
[12] Burke EK, Hyde M, Kendall G, Woodward JR (2010) A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics. IEEE Trans Evol Comput 14(6): 942–958 · Zbl 05921220 · doi:10.1109/TEVC.2010.2041061
[13] Chiarandini M, Birattari M, Socha K, Rossi-Doria O (2006) An effective hybrid algorithm for university course timetabling. J Sched 9(5): 403–432 · Zbl 1154.90428 · doi:10.1007/s10951-006-8495-8
[14] Chiarandini M, Stutzle T (2003) A landscape analysis for a hybrid approximate algorithm on a timetabling problem. TU Darmstadt Technical Report, AIDA-03-05
[15] Conover WJ (1999) Practical nonparametric statistics, 3rd edn. Wiley, New York
[16] Cowling P, Kendall G, Soubeiga E (2001) A hyperheuristic approach to scheduling a sales summit. In: Burke EK, Erben W (eds) Selected papers of the 3rd international conference on the practice and theory of automated timetabling, Lecture Notes in computer science series, vol 2079. Springer, pp 176–190 · Zbl 0982.68516
[17] Crowston WB, Glover F, Thompson GL, Trawick JD (1963) Probabilistic and parametric learning combinations of local job shop scheduling rules. ONR Research Memorandum, GSIA, Carnegie Mellon University, Pittsburgh, p 117
[18] Dowsland KA, Soubeiga E, Burke EK (2006) A simulated annealing hyper-heuristic for determining shipper sizes. Eur J Oper Res 179(3): 759–774 · Zbl 1127.90007 · doi:10.1016/j.ejor.2005.03.058
[19] Falkenauer E (1996) A hybrid grouping genetic algorithm for bin packing. J Heuristics 2: 5–30 · Zbl 0865.90107 · doi:10.1007/BF00226291
[20] Falkenauer E (1998) Genetic algorithms and grouping problems. Wiley, New York · Zbl 0803.68037
[21] Fisher H, Thompson GL (1963) Probabilistic learning combinations of local job-shop scheduling rules. In: Muth JF, Thompson GL (eds) Industrial scheduling. Prentice-Hall, Englewood Cliffs, NJ, pp 225–251
[22] Fleszar K, Hindi KS (2002) New heuristics for one-dimensional bin-packing. Comput Oper Res 29(7): 821–839 · Zbl 0994.90134 · doi:10.1016/S0305-0548(00)00082-4
[23] Glover F, Kochenberger G (2003) Handbook of metaheuristics. Kluwer, Dordrecht · Zbl 1058.90002
[24] Han L, Kendall G (2003) Guided operators for a hyper-heuristic genetic algorithm. In: AI 2003: advances in artificial intelligence: the proceedings of 16th Australian conference on AI. Lecture notes in computer science, vol 2903. Springer, pp 807–820
[25] Hansen P, Mladenovic N, Moreno Perez JA (2008) Variable neighbourhood search: methods and applications. 4OR-A Q J Oper Res 6: 319–360 · Zbl 1179.90332 · doi:10.1007/s10288-008-0089-1
[26] Hart E, Ross P, Nelson JA (1998) Solving a real-world problem using an evolving heuristically driven schedule builder. Evol Comput 6(1): 61–80 · Zbl 05412815 · doi:10.1162/evco.1998.6.1.61
[27] Kitano H (1990) Designing neural networks using genetic algorithms with graph generation system. Complex Syst 4: 461–476 · Zbl 0709.92539
[28] Kostuch P (2004) The university course timetabling problem with a 3-phase approach. In: Burke EK, Trick M (eds) The practice and theory of automated timetabling V, Lecture notes in computer science, vol 3616. Springer, Berlin, pp 109–125
[29] Lourenco HR, Martin OC, Stutzle T (2003) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer, Dordrecht, pp 321–354
[30] Lundy M, Mees A (1986) Convergence of an annealing algorithm. Math Program 34: 111–124 · Zbl 0581.90061 · doi:10.1007/BF01582166
[31] Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York · Zbl 0708.68002
[32] Martello S, Toth P (1990) Lower pounds and reduction procedures for the bin packing problem. Discret Appl Math 28: 59–70 · Zbl 0704.90074 · doi:10.1016/0166-218X(90)90094-S
[33] McMullan P (2007) An extended implementation of the Great Deluge Algorithm for course timetabling. Lecture notes in computer science, vol 4487. Springer, Berlin, pp 538–545
[34] Metaheuristic Network (2003) International timetabling competition: Competition results http://www.idsia.ch/Files/ttcomp2002/results.htm . Accessed 11 October 2010
[35] Mockus J (1989) Bayesian approach to global optimization. Kluwer, Dordrecht · Zbl 0693.49001
[36] Mockus J (1994) Application of bayesian approach to numerical methods of global and stochastic optimization. J Glob Optim 4(4): 347–366 · Zbl 0801.90099 · doi:10.1007/BF01099263
[37] Mockus J (1997) Bayesian heuristic approach to discrete and global optimization. Kluwer, Dordrecht · Zbl 0864.65036
[38] Mockus J (2000) A set of examples of global and discrete optimization: application of bayesian heuristic approach. Kluwer, Dordrecht · Zbl 0963.90076
[39] Nareyek A (2003) Choosing search heuristics by non-stationary reinforcement learning. In: Resende MGC, de Sousa JP (eds) Metaheuristics: computer decision-making. Kluwer, Dordrecht, pp 523–544
[40] Qu R, Burke EK (2009) Hybridisations within a graph based hyper-heuristic framework for university timetabling problems. J Oper Res Soc 60: 1273–1285 · Zbl 1196.90071 · doi:10.1057/jors.2008.102
[41] Rattadilok P, Gaw A, Kwan RSK (2005) Distributed choice function hyper-heuristics for timetabling and scheduling. In: Burke EK, Trick M (eds) Selected papers from the 5th international conference on the practice and theory of automated timetabling. Lecture notes in computer science series, vol 3616. Springer, Berlin, pp 51–70
[42] Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40(4): 455–472 · doi:10.1287/trsc.1050.0135
[43] Ross P (2005) Hyper-heuristics. In: Burke EK, Kendall G (eds) Search methodologies: introductory tutorials in optimization and decision support techniques. Springer, Berlin, pp 529–556
[44] Ross P, Marin-Blazquez JG, Schulenburg S, Hart E (2003) Learning a procedure that can solve hard bin-packing problems: a new GA-based approach to hyper-heuristics. In: Proceeding of the genetic and evolutionary computation conference, GECCO 2003. Springer, Berlin, pp 1295–1306 · Zbl 1038.68841
[45] Rossi-Doria O, Blum C, Knowles J, Samples M, Socha K, Paechter B (2002) A local search for automated timetabling. In: Proceedings of the 4th international conference on the practice and theory of automated timetabling [PATAT 2002] (pp 124–127)
[46] Runarsson TP, Yao X (2000) Stochastic ranking for constrained evolutionary optimization. IEEE Trans Evol Comput 4(3): 344–354
[47] Scholl A, Klein R, Jurgens C (1997) BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput Oper Res 24(7): 627–645 · Zbl 0882.90113 · doi:10.1016/S0305-0548(96)00082-2
[48] Schwerin P, Wascher G (1997) The bin-packing problem: a problem generator and some numerical experiments with FFD packing and MTP. Int Trans Oper Res 4(5/6): 377–389 · Zbl 0906.90151 · doi:10.1111/j.1475-3995.1997.tb00093.x
[49] Socha K, Knowles J, Samples M (2002) A max-min ant system for the university course timetabling problem. In: Proceedings of the 3rd international workshop on ant algorithm, ANTS 2002. Lecture notes in computer science, vol 2463, pp 1–13
[50] Soubeiga E (2003) Development and application of hyperheuristics to personnel scheduling. PhD Thesis, The University of Nottingham, UK
[51] Sutton RS, Barto AG (1998) Reinforcement learning: an introduction. MIT Press, Cambridge, MA
[52] Terashima-Marin H, Ross P, Valenzuela-Rendon M (1999) Evolution of constraint satisfaction strategies in examination timetabling. In: Proceedings of the genetic and evolutionary computation conference, GECCO 1999. Morgan Kaufmann, Los Altos, CA, pp 635–642
[53] Venkatraman S, Yen GG (2005) A generic framework for constrained optimization using genetic algorithms. IEEE Trans Evol Comput 9(4): 424–435 · Zbl 05452178 · doi:10.1109/TEVC.2005.846817
[54] Waescher G, Gau T (1996) Heuristics for the integer one-dimensional cutting stock problem: a computational study. OR Spektrum 18: 131–144 · Zbl 0853.90099 · doi:10.1007/BF01539705
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.