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.
· 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.