- Tytuł:
- The corridor method: a dynamic programming inspired metaheuristic
- Autorzy:
-
Sniedovich, M.
Viß, S. - Powiązania:
- https://bibliotekanauki.pl/articles/970877.pdf
- Data publikacji:
- 2006
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
programowanie dynamiczne
metaheuristics
dynamic programming
curse of dimensionality
very large neighborhoods
corridor method
global optimization
move-based
method-based
traveling salesman problem - Opis:
- This paper presents a dynamic programming inspired metaheuristic called Corridor Method. It can be classified as a method-based iterated local search in that it deploys method-based neighborhoods. By this we mean that the search for a new candidate solution is carried out by a fully-fledged optimization method and generates a global optimal solution over the neighborhood. The neighborhoods are thus constructed to be suitable domains for the fully-fledged optimization method used. Typically, these neighborhoods are obtained by the imposition of exogenous constraints on the decision space of the target problem and therefore must be compatible with the optimization method used to search these neighborhoods. This is in sharp contrast to traditional metaheuristics where neighborhoods are move-based, that is, they are generated by subjecting the candidate solution to small changes called moves. While conceptually this method-based paradigm applies to any optimization method, in practice it is best suited to support optimization methods such as dynamic programming, where it is easy to control the size of a problem, hence the complexity of algorithms, by means of exogenous constraints. The essential features of the Corridor Method are illustrated by a number of examples, including the traveling salesman problem, where exponentially large neighborhoods are searched by a linear time/space dynamic programming algorithm.
- Źródło:
-
Control and Cybernetics; 2006, 35, 3; 551-578
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł