Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/A2EA3E49-6766-4040-9483-FAC140B6805A | - |
| Αναγνωριστικό | https://doi.org/10.1007/s10472-010-9217-7 | - |
| Γλώσσα | en | - |
| Μέγεθος | 32 | en |
| Τίτλος | Optimization of heuristic search using recursive algorithm selection and reinforcement learning | en |
| Δημιουργός | Vasilikos Vasileios | en |
| Δημιουργός | Lagoudakis Michael | en |
| Δημιουργός | Λαγουδακης Μιχαηλ | el |
| Εκδότης | Springer Verlag | en |
| Περιγραφή | Δημοσίευση σε επιστημονικό περιοδικό | el |
| Περίληψη | The traditional approach to computational problem solving is to use one of the available algorithms to obtain solutions for all given instances of a problem. However, typically not all instances are the same, nor a single algorithm performs best on all instances. Our work investigates a more sophisticated approach to problem solving, called Recursive Algorithm Selection, whereby several algorithms for a problem (including some recursive ones) are available to an agent that makes an informed decision on which algorithm to select for handling each sub-instance of a problem at each recursive call made while solving an instance. Reinforcement learning methods are used for learning decision policies that optimize any given performance criterion (time, memory, or a combination thereof) from actual execution and profiling experience. This paper focuses on the well-known problem of state-space heuristic search and combines the A* and RBFS algorithms to yield a hybrid search algorithm, whose decision policy is learned using the Least-Squares Policy Iteration (LSPI) algorithm. Our benchmark problem domain involves shortest path finding problems in a real-world dataset encoding the entire street network of the District of Columbia (DC), USA. The derived hybrid algorithm exhibits better performance results than the individual algorithms in the majority of cases according to a variety of performance criteria balancing time and memory. It is noted that the proposed methodology is generic, can be applied to a variety of other problems, and requires no prior knowledge about the individual algorithms used or the properties of the underlying problem instances being solved. | en |
| Τύπος | Peer-Reviewed Journal Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-10-27 | - |
| Ημερομηνία Δημοσίευσης | 2010 | - |
| Θεματική Κατηγορία | Heuristic search | en |
| Θεματική Κατηγορία | Algorithm selection | en |
| Θεματική Κατηγορία | Reinforcement learning | en |
| Θεματική Κατηγορία | Software optimization | en |
| Θεματική Κατηγορία | Hybrid algorithms | en |
| Βιβλιογραφική Αναφορά | V.Vasilikos, M. Lagoudakis , "Optimization of heuristic search using recursive algorithm selection and reinforcement learning ," Annals of Mathematics and Artificial Intelligence, vol. 60, no. 1, pp. 119-151, 2010. doi: 10.1007/s10472-010-9217-7 | en |
Copyright © DIAS 2013
