An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics
Hyper-heuristics are intended to be reusable domain independent approaches for solving complex computational problems. There are tailored approaches successfully applied to a specific problem, however they require parameter tuning and cannot be applied to another problem. Memetic Algorithms are a co...
| Main Author: | |
|---|---|
| Format: | Dissertation (University of Nottingham only) |
| Published: |
2015
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/30801/ |
| _version_ | 1848794063487107072 |
|---|---|
| author | Ozcagdavul, Mazlum |
| author_facet | Ozcagdavul, Mazlum |
| author_sort | Ozcagdavul, Mazlum |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Hyper-heuristics are intended to be reusable domain independent approaches for solving complex computational problems. There are tailored approaches successfully applied to a specific problem, however they require parameter tuning and cannot be applied to another problem. Memetic Algorithms are a combination of genetic algorithms and local search methods. The evolutionary interaction of memes helps to create intelligent complexes which are able to solve computational problems.
Hyper-heuristics are a high level search technique which conducts on the field of a set of low-level heuristics which directly works on the solution. Hyper-heuristics have two core parts. The first one is heuristic selection, and the second one move acceptance mechanism. While heuristic selection method decides which low-level heuristic to be used, move acceptance mechanism decides to accept or reject the obtained solution.
In this study, we investigate a multi-meme memetic algorithm as a hyper-heuristic which mixes and controls multiple hyper-heuristic (Modified Choice Function All Moves, Reinforcement Learning with Great Deluge and Simple Random Only Improvement), and parameters of heuristics (operators) such as mutation rates and depth of search. We have performed an empirical study in which three different variations of proposed hyper-heuristic is tested. In the first algorithm, Only Improvement acceptance technique is used for both Reinforcement Learning and Simple Random and All Moves is used for Modified Choice Function. In the second version, instead of Only Improvement, Great Deluge method is used for Reinforcement Learning. While in the first and second algorithms there was no information sharing between hyper-heuristics, a component which share improvement and non-improvement information of low-level heuristics is added to the third algorithm.
The results of the third algorithm outperformed most of competitors of CHeSC2011 and become third best hyper-heuristic. |
| first_indexed | 2025-11-14T19:10:14Z |
| format | Dissertation (University of Nottingham only) |
| id | nottingham-30801 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:10:14Z |
| publishDate | 2015 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-308012015-12-09T15:33:53Z https://eprints.nottingham.ac.uk/30801/ An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics Ozcagdavul, Mazlum Hyper-heuristics are intended to be reusable domain independent approaches for solving complex computational problems. There are tailored approaches successfully applied to a specific problem, however they require parameter tuning and cannot be applied to another problem. Memetic Algorithms are a combination of genetic algorithms and local search methods. The evolutionary interaction of memes helps to create intelligent complexes which are able to solve computational problems. Hyper-heuristics are a high level search technique which conducts on the field of a set of low-level heuristics which directly works on the solution. Hyper-heuristics have two core parts. The first one is heuristic selection, and the second one move acceptance mechanism. While heuristic selection method decides which low-level heuristic to be used, move acceptance mechanism decides to accept or reject the obtained solution. In this study, we investigate a multi-meme memetic algorithm as a hyper-heuristic which mixes and controls multiple hyper-heuristic (Modified Choice Function All Moves, Reinforcement Learning with Great Deluge and Simple Random Only Improvement), and parameters of heuristics (operators) such as mutation rates and depth of search. We have performed an empirical study in which three different variations of proposed hyper-heuristic is tested. In the first algorithm, Only Improvement acceptance technique is used for both Reinforcement Learning and Simple Random and All Moves is used for Modified Choice Function. In the second version, instead of Only Improvement, Great Deluge method is used for Reinforcement Learning. While in the first and second algorithms there was no information sharing between hyper-heuristics, a component which share improvement and non-improvement information of low-level heuristics is added to the third algorithm. The results of the third algorithm outperformed most of competitors of CHeSC2011 and become third best hyper-heuristic. 2015-12-10 Dissertation (University of Nottingham only) NonPeerReviewed Ozcagdavul, Mazlum (2015) An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics. [Dissertation (University of Nottingham only)] Hyper-Heuristic Cross-domain Heuristic Search Challenge (CHeSC 2011) Multi-meme memetic algorithm parameter tuning. |
| spellingShingle | Hyper-Heuristic Cross-domain Heuristic Search Challenge (CHeSC 2011) Multi-meme memetic algorithm parameter tuning. Ozcagdavul, Mazlum An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics |
| title | An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics |
| title_full | An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics |
| title_fullStr | An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics |
| title_full_unstemmed | An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics |
| title_short | An adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics |
| title_sort | adaptive multi meme memetic algorithm embedding choice function, reinforcement learning and simple random hyper-heuristics |
| topic | Hyper-Heuristic Cross-domain Heuristic Search Challenge (CHeSC 2011) Multi-meme memetic algorithm parameter tuning. |
| url | https://eprints.nottingham.ac.uk/30801/ |