Zadání diplomové práce

Studium genetických algoritmů v kontextu tradičních stochastických optimalizačních metod


K nejmodernějším metodám globální optimalizace patří evoluční algoritmy, zejména jeden jejich typ - genetické algoritmy. Jejich charakteristickým rysem je, že způsob, kterým se metoda přibližuje k hledanému optimu, je inspirován přirozeným výběrem ve vývoji biologických druhů, v případě genetických algoritmů potom speciálně mutacemi a křížením chromozomů. Vzhledem k této biologické inspiraci je princip genetických algoritmů snadno srozumitelný i nematematikům, a právě díky tomu se v průběhu posledních pěti let velmi rychle rozšířilo jejich používání při řešení optimalizačních úloh v nejrůznějších oborech. Z matematického hlediska jsou však evoluční a genetické algoritmy pouze dalšími zástupci stochastických optimalizačních algoritmů, podobně jako např. různé algoritmy simulovaného žíhání, adaptivního prohledávání či adaptivního rozkladu. V případě úloh, pro jejichž řešení byl zvolen genetický nebo jiný evoluční algoritmus pouze kvůli snadné srozumitelnosti, tudíž přirozeně vyvstává otázka, zda by hledané optimum nebylo možné pomocí některého z tradičních optimalizačních algoritmů nalézt přesněji či rychleji. Z toho důvodu jsou velmi potřebná srovnání genetických a evolučních algoritmů s tradičními stochastickými optimalizačními algoritmy, a to jak z teoretického hlediska, tak na základě výsledků testování konkrétních implementací na konkrétních datech. Právě takové srovnání by mělo být cílem navrhované diplomové práce.

Diplomant by se nejdříve v rámci rešeršní práce měl důkladně seznámit s teoretickými principy stochastických optimalizačních algoritmů, se zaměřením na algoritmy genetické. Měl by se naučit vidět specifické vlastnosti genetických algoritmů jako speciální případy obecných vlastností stochastických optimalizačních algoritmů, a na tomto pozadí by měl identifikovat podstatné rozdíly mezi teoretickými vlastnostmi genetických algoritmů a hlavních zástupců tradičních stochastických algoritmů. Hlavní náplň této diplomové práce však spočívá v praktickém testování konkrétních implementací genetických i tradičních stochastických algoritmů na konkrétních datech. Data a jednu rutinně používanou implementaci genetického algoritmu student obdrží, zatímco několik implementací tradičních stochastických algoritmů, a případně ještě i další implementaci genetického či nějakého obecnějšího evolučního algoritmu by měl sám naprogramovat v systému Matlab.
 

Doporučená literatura

·  V. Norkin, G.C. Pflug, A. Ruszczynski. A branch and bound method for stochastic global optimization. Mathematical Programming, 83A: 425-450, 1998.

·  E.M. Oblow. SPT: A stochastic tunneling algorithm for global optimization. Journal of Global Optimization, 20: 195-212, 2001.

·  L. Özdamar, M. Demirhan. Experiments with new stochastic global optimization search techniques. Computers and Operations Research, 27: 841-865, 2000.

·  D.J. Reaume, H.E. Romeijn, R.L. Smith. Implementing pure adaptive search for global optimization using Markov chain sampling. Journal of Global Optimization, 20: 33-47, 2001.

·  A. Törn, M.M. Ali, S. Viitanen. Stochastic global optimization: Problem classes and solution techniques. Journal of Global Optimization, 14: 437-447, 1999.

·  M.L. Wong, K.S. Leung. Data Mining Using Grammar Based Genetic Programming and Applications. Kluwer Academic Publishers, Dordrecht, 2000.

·  Z.B. Zabinsky. Stochastic methods for practical global optimization. Journal of Global Optimization, 14: 433-444, 1998.