1. MMC
  2. All Volumes and Issues
  3. Volume 8, Number 4, 2021
  4. A modified choice function hyper-heuristic with Boltzmann function

A modified choice function hyper-heuristic with Boltzmann function

MMC.
2021;
Volume 8, Number 4
: pp. 736–746
https://doi.org/10.23939/mmc2021.04.736
Received: May 23, 2021
Accepted: June 07, 2021

Mathematical Modeling and Computing, Vol. 8, No. 4, pp. 736–746 (2021)

Authors:
  1. O. Mellouli
  2. I. Hafidi
  3. A. Metrane
1
LIPIM, ENSA Khouribga, University Sultan Moulay Slimane
2
LIPIM, ENSA Khouribga, University Sultan Moulay Slimane
3
LIPIM, ENSA Khouribga, Sultan Moulay Slimane University, Khouribga, Morocco

Hyper-heuristics are a subclass of high-level research methods that function in a low-level heuristic research space.  Their aim objective is to improve the level of generality for solving combinatorial optimization problems using two main components: a methodology for the heuristic selection and a move acceptance criterion, to ensure intensification and diversification [1].  Thus, rather than working directly on the problem's solutions and selecting one of them to proceed to the next step at each stage, hyper-heuristics operates on a low-level heuristic research space.  The choice function is one of the hyper-heuristics that have proven their efficiency in solving combinatorial optimization problems [2–4].  At each iteration, the selection of heuristics is dependent on a score calculated by combining three different measures to guarantee both intensification and diversification for the heuristics choice process.  The heuristic with the highest score is therefore chosen to be applied to the problem.  Therefore, the key to the success of the choice function is to choose the correct weight parameters of its three measures.  In this study, we make a state of the art in hyper-heuristic research and  propose a new method that automatically controls these weight parameters based on the Boltzmann function.  The results obtained from its application on five problem domains are compared with those of the standard, modified choice function proposed by Drake et al. [2,3].

hyper-heuristics
combinatorial optimization
choice function
modified choice function
heuristic selection
heuristic generation
Boltzmann function
  1. Burke E. K., Hyde M., Kendall G., Ochoa G., Özcan E., Woodward J. R.  A classification of hyper-heuristic approaches in Handbook of Metaheuristics. Springer US. 449–468 (2010).
  2. Drake J. H., Özcan E., Burke E. K.  An Improved Choice Function Heuristic Selection for Cross Domain Heuristic Search.  PPSN 2012: Parallel Problem Solving from Nature – PPSN XII. 307–316 (2012).
  3. Drake J. H., Özcan E., Burke E. K.  A Modified Choice Function hyper-heuristic controlling unary and binary operators.  2015 IEEE Congress on Evolutionary Computation (CEC). 3389–3396 (2015).
  4. Tay J. C., Ho N. B.  Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems.  Computers & Industrial Engineering. 54 (3), 453–473 (2008).
  5. Lyaqini S., Nachaoui M., Quafafou M.  Non-smooth classification model based on new smoothing technique.  Journal of Physics: Conference Series. 1743 (1), 012025 (2021).
  6. Cowling P. I., Kendall G., Soubeiga E.  A Hyperheuristic Approach to Scheduling a Sales Summit.  PATAT 2000: Practice and Theory of Automated Timetabling III. 2079, 176–190 (2001).
  7. Crowston W. B., Glover F., Thompson G. L., Trawick J. D.  Probabilistic and parametric learning combinations of local job shop scheduling rules.  ONR research memorandum, Carnegie-Mellon University, Pittsburgh (1963).
  8. Fisher H., Thompson G. L.  Probabilistic learning combinations of local job-shop scheduling rules.  In: Muth J. F., Thompson G. L. (eds).  Industrial Scheduling. 225–251 (1963).
  9. Fisher H., Thompson G. L.  Probabilistic learning combinations of local job-shop scheduling rules.  In: Factory Scheduling Conference, Carnegie Institue of Technology. May 10–12 (1961).
  10. Nachaoui M., Chakib A., Nachaoui A.  An efficient evolutionary algorithm for a shape optimization problem.  Applied and Computational Mathematics. 19 (2), 220–244 (2020).
  11. Oteiza P. P., Rodriguez D. A., Brignole N. B.  Parallel cooperative optimization through hyper-heuristics.  Computer Aided Chemical Engineering. 44, 805–810 (2018).
  12. Burke E. K., Hyde M., Kendall G., Ochoa G., Ozcan E., Woodward J.  Exploring  hyper-heuristic methodologies with genetic programming.  Computational Intelligence. 177–201 (2009).
  13. 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.  GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation. 1559–1565 (2007).
  14. Burke E. K., Hyde M. R., Kendall G., Woodward J. R.  The scalability of evolved on line bin packing heuristics.  2007 IEEE Congress on Evolutionary Computation. 2530–2537 (2007).
  15. Burke E. K., Hyde M. R., Kendall G.  Evolving bin packing heuristics with genetic programming.  Parallel Problem Solving from Nature – PPSN IX. 860–869 (2006).
  16. Dimopoulos C., Zalzala A. M. S.  Investigating the use of genetic programming for a classic one-machine scheduling problem.  Advances in Engineering Software. 32 (6), 489–498 (2001).
  17. Fukunaga A.  Automated discovery of composite SAT variable selection heuristics.  Proceedings of the National Conference on Artificial Intelligence (AAAI). 641–648 (2002).
  18. Fukunaga A. S.  Automated discovery of local search heuristics for satisfiability testing.  Evol. Comput. 16 (1), 31–61 (2008).
  19. Fukunaga A. S.  Evolving local search heuristics for SAT using genetic programming.  Genetic and Evolutionary Computation – GECCO-2004. 483–494 (2004).
  20. Geiger C. D., Uzsoy R., Aytug H.  Rapid modeling and dis- covery of priority dispatching rules: an autonomous learning approach.  Journal of Scheduling. 9, 7–34 (2006).
  21. Keller R. E., Poli R.  Cost-benefit investigation of a genetic-programming hyperheuristic.  EA 2007: Artificial Evolution. 13–24 (2007).
  22. Keller R. E., Poli R.  Linear genetic programming of parsimonious metaheuristics.  2007 IEEE Congress on Evolutionary Computation. 4508–4515 (2007).
  23. Acevedo N., Barra C. R., Bolton C. C., Parada V.  Automatic design of specialized algorithms for the binary knapsack problem.  Expert Systems with Applications. 141, 112908 (2020).
  24. Eglese R. W.  Simulated annealing: A tool for operational research.  European Journal of Operational Research. 46 (3), 271–281 (1990).
  25. Fleischer M. A.  Simulated annealing: Past, present, and future.  Proceedings of the 1995 Winter Simulation Conference. 155–161 (1995).
  26. Koulamas C., Antony S. R., Jaen R.  A survey of simulated annealing applications to operations research problems.  Omega. 22 (1), 41–56 (1994).
  27. Kirkpatrick S., Gelatt Jr, C. D., Vecchi M. P.  Optimization by Simulated Annealing.  Science. 220 (4598), 671–680 (1983).
  28. Romeo F., Sangiovanni-Vincentelli A.  A theoretical frame-work for simulated annealing.  Algorithmica. \textbf{6}, Article number: 302 (1991).
  29. Suman B., Kumar P.  A survey of simulated annealing as a tool for single and multiobjective optimization.  Journal of the Operational Research Society. 57 (10), 1143–1160 (2006).
  30. Alahyane M., Hakim A., Laghrib A., Raghay S.  A lattice Boltzmann method applied to the fluid image registration.  Applied Mathematics and Computation. 349, 421–438 (2019).