An adaptive multi meme memetic algorithm embedding choice function hyper-heuristic
Heuristic methodologies appears for solving optimisation problems. Hyper-heuristics focus on search spaces to select or generate the suitable low-level heuristics to solve computationally difficult problems rather than focusing on finding solutions directly. The main goal is to develop more general...
| Main Author: | |
|---|---|
| Format: | Dissertation (University of Nottingham only) |
| Language: | English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/30793/ |
| Summary: | Heuristic methodologies appears for solving optimisation problems. Hyper-heuristics focus on search spaces to select or generate the suitable low-level heuristics to solve computationally difficult problems rather than focusing on finding solutions directly.
The main goal is to develop more generally applicable search methodologies. The selection hyper-heuristics will be the core of designing the proposed algorithm and consist of two stages: the selection stage of low-level heuristics, and the acceptance stage of the solutions. An Evolutionary Algorithm approach produces high quality hyper-heuristics which can find optimal solutions for optimisation problems effectively. The Memetic Algorithms are evolutionary intelligent algorithms combining Genetic Algorithm with local search components. A Multi-Meme Memetic Algorithm presented in this project as a population based search method with Choice Function as a selection mechanism for low-level heuristics. The selection mechanism is encoded by multi-meme self-adaptation strategy for automating tuning of the choice function parameters. For each individual in the population, a meme encodes which setting is the best for Choice Function parameters for each operator type and relevant parameters of a chosen operator. Multi-Meme strategy is considered as a self-adaptive mechanism using a reward points system to increase the score for the meme that shows local improvement and uses these scores in the selection process. The proposed hyper-heuristics is tested and compared with the performance of previous hyper-heuristics which competed in the CHeSC2011 challenge across 9 problem domains. The achieved result was remarkable in some problem domains and opens some scope for further improvement in the proposed hyper-heuristic to improve the result in the rest of the problem domains. |
|---|