Ant Colony Hyper-heuristics for Travelling Salesman Problem
| Autor: | Zalilah Abd Aziz |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Mathematical optimization
Heuristic (computer science) Computer science Heuristic Ant colony optimization algorithms Travelling Salesman Problem Pheromone Lin–Kernighan heuristic Hyper-heuristics Ant colony ComputingMethodologies_ARTIFICIALINTELLIGENCE Travelling salesman problem Ant Colony Algorithms Ant hyper-heuristics Problem domain General Earth and Planetary Sciences Heuristics Metaheuristic General Environmental Science |
| Zdroj: | Procedia Computer Science. 76:534-538 |
| ISSN: | 1877-0509 |
| DOI: | 10.1016/j.procs.2015.12.333 |
| Popis: | Metaheuristics are capable of producing good quality solutions. However, they often need to perform some adjustment of relevant parameters in order to be applied to new problems or different problem instances. Furthermore, they often are time-consuming and knowledge intensive procedures that requires deep understanding of the problem domain. This motivates the investigation of developing an algorithm that can produce good quality solutions across different instances and problems and which do not require extensive parameter tuning. Hyper-heuristics is specifically designed to raise the generality of optimisation systems in such a way that the technique can be reused and applied to other different problems. In this work, we develop a generalised heuristic method (hyper-heuristics) based on ant colony algorithms. In our approach, in order to produce a generalized approach, pheromone and visibility values consider a non-domain specific knowledge. Ant colony hyper-heuristics applies the same methodology as ant colony algorithms where it involves two pheromone updating procedures; the local and global update. The global update will use the best solution found at the current iteration to update the pheromone trail and the local update is performed after each ant performs a tour. We apply our work on one routing problem; the Travelling Salesman Problem (TSP). The TSP is a problem of finding the shortest possible tour to visit each city exactly once and it is known to be in the class of NP-hard problems. Results presented in this paper are able to outperform some other popular methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|