A COMPREHENSIVE ANALYSIS OF MULTI-STRATEGY MEMETIC ALGORITHMS INCORPORATING LOW-LEVEL HEURISTICS AND ACCEPTANCE MECHANISMS

Abstract

Hyper-heuristics are designed to be reusable, domain-independent methods for addressing complex computational issues. While there are specialized approaches that work well for particular problems, they often require parameter tuning and cannot be transferred to other problems. Memetic Algorithms combine genetic algorithms and local search techniques. The evolutionary interaction of memes allows for the creation of intelligent complexes capable of solving computational problems. Hyper-heuristics are a high-level search technique that operates on a set of low-level heuristics that directly address the solution. They have two main components: heuristic selection and move acceptance mechanisms. The heuristic selection method determines which low-level heuristic to use, while the move acceptance mechanism decides whether to accept or reject the resulting solution. In this study, we explore a multi-meme memetic algorithm as a hyper-heuristic that integrates and manages multiple hyper-heuristics (Modified Choice Function All Moves, Reinforcement Learning with Great Deluge, and Simple Random Only Improvement) and parameters of heuristics (such as mutation rates and search depth). We conducted an empirical study testing two different variations of the proposed hyper-heuristic. The first algorithm uses the Only Improvement acceptance technique for both Reinforcement Learning and Simple Random, and All Moves for Modified Choice Function. In the second version, the Great Deluge method replaces Only Improvement for Reinforcement Learning. The second algorithm's results were the best of all competitors from the CHeSC2011 competition, achieving the fourth-best hyper-heuristic performance.

Keywords

• Hyper-Heuristic
• Cross-domain Heuristic Search Challenge (CHeSC 2011)
• Multi-meme memetic algorithm
• parameter tuning.

References

1. A. E. Eiben, R. Hinterding, and Z. Michalewicz, “Parameter control in evolutionary algorithm,” IEEE Trans. Evol. Comput., vol. 3, pp. 124–141, Jul. 1999.
2. Asmuni, H., Burke, E. K., Garibaldi, J. M., & McCollum, B. (2007). A novel fuzzy approach to evaluate the quality of examination timetabling. In Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT'06), LNCS, 3867, (pp. 327-346), Springer.
3. Burke EK, Hyde M, Kendall G, Ochoa G, Özcan E and Woodward J (2009), Exploring hyper-heuristic methodologies with genetic programming. In: Mumford C and Jain L (eds). Computational Intelligence: Collaboration, Fusion and Emergence, Intelligent Systems Reference Library. Springer: New York, pp 177–201.
4. Burke, E., Kendall, G., & Soubeiga, E. (2003b), A tabu-search hyper-heuristic for timetabling and rostering. Journal of Heuristics, 9, 451-470, Kluwer Academic Publishers
5. Cowling, P., Kendall, G., & Soubeiga, E. (2001a). A hyperheuristic approach to scheduling a sales summit. In Proceedings of the 3rd International Conference on Practice and Theory of Automated Timetabling (PATAT’00), (pp. 176-190), Springer-Verlag.
6. E. Burke and G. Kendall, Search methodologies: introductory tutorials in optimization and decision support techniques. Springer Science+ Business Media, 2005.
7. E. Burke and G. Kendall, Search methodologies: introductory tutorials in optimization and decision support techniques. Springer Science+ Business Media, 2005.
8. E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. ¨Ozcan, and R. Qu, “Hyper-heuristics: A survey of the state of the art,” Journal of the Operational Research Society, 2013.

9. E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. R. ¨ Woodward, “A classification of hyper-heuristic approaches,” in Handbook of Metaheuristics, ser. International Series in Operations Research & Management Science, M. Gendreau and J.-Y. Potvin, Eds. Springer US, 2010, vol. 146, pp. 449–468.
10. E. Özcan, M. Misir , G. Ochoa, E. K. Burke, A Reinforcement Learning - Great-Deluge Hyper-heuristic for Examination Timetabling, International Journal of Applied Metaheuristic Computing, 1(1), pp. 39-59, 2010.
11. E. Ozcan, S. Asta, and C. Altıntas, “Memetic algorithms for cross domain heuristic search,” in Proceedings of the 13th Annual Workshop on Computational Intelligence (UKCI 2013), Y. Jin and S. A. Thomas, Eds. Surrey, UK: IEEE Press, 2013, pp. 175–182.
12. F. Neri and C. Cotta, “Memetic algorithms and memeting computing optimization: A literature review,” Swarm and Evolutionary Computation, vol. 2, pp. 1–14, 2012.
13. Fisher H, Thompson GL (1963) Probabilistic learning combination of local job-shop scheduling rules. In: Muth JF, Thompson GL (eds) Industrial Scheduling, Prentice-Hall, Inc, New Jersey, pp 225-251.
14. J. E. Smith et al., “Co-evolution of memetic algorithms: Initial investigations,” in Parallel Problem Solving From Nature—PPSN VII, G. Guervos et al., Eds. Berlin, Germany: Springer, 2002, vol. 2439, Lecture Notes in Computer Science, pp. 537–548.
15. J. E. Smith, “Co-evolving memetic algorithms: A learning approach to robust scalable optimization,” in IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 2003, vol. 1, pp. 498–505.
16. John H. Drake, Ender Özcan and Edmund K. Burke An Improved Choice Function Heuristic Selection for Cross Domain Heuristic Search The 12th International Conference on Parallel Problem Solving From Nature (PPSN 2012), Lecture Notes in Computer Science, Volume 7492, pp. 307-316, 2012.
17. Kaelbling, L. P., Littman, M., & Moore, A. (1996), Reinforcement learning: a survey. Journal of Artificial Intelligence Research, 4, (pp. 237-285).
18. Kendall G and Mohamad M (2004a), Channel assignment in cellular communication using a great deluge hyper-heuristic. In: Proceedings of the 2004 IEEE International Conference on Network (ICON2004). IEEE: Singapore, pp 769–773.
19. M. Gendreau and J.-Y. Potvin, “Metaheuristics in combinatorial optimization,” Annals of Operations Research, vol. 140, no. 1, pp. 189–213, 2005.
20. M. Gendreau and J.-Y. Potvin, “Metaheuristics in combinatorial optimization,” Annals of Operations Research, vol. 140, no. 1, pp. 189–213, 2005.
21. N. Krasnogor, “Studies on the Theory and Design Space of Memetic Algorithms,” Ph.D., Faculty of Comput., Math., and Eng., Univ. of the West of England, Bristol, U.K., 2002.
22. N. Krasnogor, B. Blackburne, J. D. Hirst, and E. K. N. Burke, “Multimeme algorithms for the structure prediction and structure comparison of proteins,” in Parallel Problem Solving From Nature, 2002, Lecture Notes in Computer Science.
23. Ozcan, E., Bilgin, B., Korkmaz, E.: Hill Climbers and Mutational Heuristics in Hyperheuristics. In: PPSN IX. pp. 202–211, 2010.
24. P. Moscato, “On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms,” Caltech concurrent computation program, C3P Report, vol. 826, p. 1989, 1989.
25. Qu, R., Burke, E. K., & McCollum, B. (2008a). Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. European Journal of Operational Research, 198(2), 392-404.
26. R. Dawkins, The Selfish Gene. New York City: Oxford University Press, 1976.
27. R. Hinterding, Z. Michalewicz, and A. E. Eiben, “Adaptation in Evolutionary Computation: A Survey,” in IEEE International Conference on Evolutionary Computation. Piscataway, NJ: IEEE Press, Apr. 1997, pp. 65–69.
28. Ross P (2005). Hyper-heuristics. In: Burke EK and Kendall G, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. chap 17, Springer: Berlin, pp 529–556.
29. Ross, P., Hart, E., Marin-Blazquez, J., & Schulenberg, S. (2003). Learning a procedure that can solve hard bin-packing problems: a new GA-based approach to hyperheuristics. Proceedings of Genetic and Evolutionary Computation Conference (GECCO'2003), (pp. 1295-1306).
30. Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: an introduction. The MIT Press.
31. Terashima-Marin, H., Moran-Saavedra, A., & Ross, P. (2005). Forming hyper-heuristics with GAs when solving 2D-regular cutting stock problems. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation, 2, (pp. 1104-1110), IEEE Press.
32. 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'99), (pp 635-642).
33. The University of Nottingham CHeSC2011 website. Retrieved April ,21, 2021 from: http://www.asap.cs.nott.ac.uk/external/chesc2011/hyflex_description.html
34. Vazquez-Rodriguez, J.A., Petrovic, S. & Salhi, A. (2007). A combined meta-heuristic with hyper-heuristic approach to the scheduling of the hybrid flow shop with sequence dependent setup times and uniform machines. In P. Baptiste, G. Kendall, A. Munier-Kordon & F. Sourd (Ed.), the 3rd Multi-disciplinary International Scheduling Conference: Theory and Applications (MISTA’07), (pp. 506-513), Paris, France.
35. Yew-Soon Ong, Meng-Hiot Lim, Ning Zhu, and Kok-Wai Wong, “Classification of Adaptive Memetic Algorithms: A Comparative Study” IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, vol. 36, pp. 141-152 No. 1, February 2006
36. Yilmaz, A. A., Guzel, M. S., Bostanci, E., & Askerzade, I. (2020). A novel action recognition framework based on deep-learning and genetic algorithms. IEEE Access, 8, 100631-100644.