V této doktorské disertační práci je předveden vytvořený algoritmus, jehož základem jsou některé algoritmy založené na lokálním prohledávání. Do algoritmu lokálního prohledávání byl přidán penalizační faktor spolu s aspiračním kritériem, které by mělo urychlit vyhledávání optimálního (nebo alespoň suboptimálního) řešení ve vybraných problémech. Následně je předvedena funkcionalita algoritmu na vybraných úlohách z oblasti problematiky obchodního cestujícího a také funkcionalita na vybraných testovacích funkcích. Jednotlivé výsledky měření jsou porovnány a na jejich základě je zkoumáno, zda je tento algoritmus úspěšný či nikoliv.
Anotace v angličtině
In this thesis we show how local search algorithm can be applied to a set of problems, and we show that this algorithm improves its performance. We added an aspiration criterion from Tabu Search algorithm to improve local search algorithm in order to advance the performance of some problem types and parameter settings. We demonstrate then the functionality of the algorithm on some types of problems of Travelling Salesman Problem and on some test?s functions; we make some search monitors for this extension to analyse in case this extension fails or succeeds.
Klíčová slova
Optimalizace, stochastické optimalizační algoritmy, penalizační lokální prohledávání, zakázané prohledávání, aspirační kritérium, problém obchodního cestujícího
Klíčová slova v angličtině
Optimization, stochastic optimization algorithms, penalty local search, tabu search, aspiration criterion, travelling salesman problem
Rozsah průvodní práce
-
Jazyk
CZ
Anotace
V této doktorské disertační práci je předveden vytvořený algoritmus, jehož základem jsou některé algoritmy založené na lokálním prohledávání. Do algoritmu lokálního prohledávání byl přidán penalizační faktor spolu s aspiračním kritériem, které by mělo urychlit vyhledávání optimálního (nebo alespoň suboptimálního) řešení ve vybraných problémech. Následně je předvedena funkcionalita algoritmu na vybraných úlohách z oblasti problematiky obchodního cestujícího a také funkcionalita na vybraných testovacích funkcích. Jednotlivé výsledky měření jsou porovnány a na jejich základě je zkoumáno, zda je tento algoritmus úspěšný či nikoliv.
Anotace v angličtině
In this thesis we show how local search algorithm can be applied to a set of problems, and we show that this algorithm improves its performance. We added an aspiration criterion from Tabu Search algorithm to improve local search algorithm in order to advance the performance of some problem types and parameter settings. We demonstrate then the functionality of the algorithm on some types of problems of Travelling Salesman Problem and on some test?s functions; we make some search monitors for this extension to analyse in case this extension fails or succeeds.
Klíčová slova
Optimalizace, stochastické optimalizační algoritmy, penalizační lokální prohledávání, zakázané prohledávání, aspirační kritérium, problém obchodního cestujícího
Klíčová slova v angličtině
Optimization, stochastic optimization algorithms, penalty local search, tabu search, aspiration criterion, travelling salesman problem
Zásady pro vypracování
Současný stav řešené problematiky
Metody řešení daného problému
Penalizační prohledávání
Problém obchodního cestujícího
Zásady pro vypracování
Současný stav řešené problematiky
Metody řešení daného problému
Penalizační prohledávání
Problém obchodního cestujícího
Seznam doporučené literatury
Dorigo, M., Maniezzo, V. and Colorni, A. The Ant System: Optimization by a colony of cooperating agents. In IEEE Transactions on Systems and Cybernetics - Part B, Vol. 26, No. 1, 1996. pp 1-13.
Gass, S.I., Harris, C.M. Encyclopedia of Operations Research and Management Science centennial edition, druhé vydání, Dodrecht, Kluwer AP, 2004. ISBN 0-7923-7827-X.
Goldberg, D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison - Wesley, 1989. 432 s.ISBN 0-2011-5767-5.
Seznam doporučené literatury
Dorigo, M., Maniezzo, V. and Colorni, A. The Ant System: Optimization by a colony of cooperating agents. In IEEE Transactions on Systems and Cybernetics - Part B, Vol. 26, No. 1, 1996. pp 1-13.
Gass, S.I., Harris, C.M. Encyclopedia of Operations Research and Management Science centennial edition, druhé vydání, Dodrecht, Kluwer AP, 2004. ISBN 0-7923-7827-X.
Goldberg, D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison - Wesley, 1989. 432 s.ISBN 0-2011-5767-5.