Algoritmy

Než začnu vyjmenovávat názvy všech možných algoritmů, tak raději uklidním mladší studenty, aby se nevyděsili pojmů, které možná v životě neslyšeli. Boloňský proces nás bohužel dostal do situace, kdy si studenti po třech semestrech studia musí vybrat téma, i když zatím mají za sebou jen základní kurzy programování a měli by používat algoritmy vyučované v předmětech, které jsou doporučené až v dalších semestrech. Vyučující jsou si tohoto stavu vědomi a očekávané nároky tomu odpovídají. Nicméně něco se k závěrečné práci budete muset naučit.

Jak postupovat?

Přečtěte si tento text hned na začátku semestru (ideálně ještě před začátkem), protože jedna z možných cest je zapsat si navíc předmět, ve kterém se potřebné věci naučíte. V dnešní době se nejedná o jedinou variantu, protože zdrojů na Internetu je mnoho. Můžete si pustit přednášky ze záznamu a předmět splnit později. Navíc se nemusíte omezovat jen na přednášky na MFF UK.

Další cestou je samostatná četba. Pro prvotní seznámení s potřebnými algoritmy bych doporučoval přečíst si jejich stručný popis na Wikipedii nebo poznámky vyučujících k příslušným předmětů. Tyto texty vám dají počáteční intuici, co jednotlivé algoritmy obnáší, a zároveň mohou být ze začátku srozumitelnější než odborná literatura. Za pomoci těchto zdrojů si můžete vybrat téma práce. Poté si s pomocí vedoucího najdete odbornou literaturu, která vám poskytne potřebné znalosti k vypracování závěrečné práce.

Níže uvádím příklady algoritmů, které můžete v mnou zadávaných tématech prací používat. Mnohem podrobnější najdete například na Wikipedii. Pokud jste se s matematickou optimalizací ještě nesetkali, tak začněte na Wikipedii.

Pokud jste se po s vedoucím práce domluvili, že budete používat nějaký algoritmus, se kterým jste zatím nikdy nepracovali, tak bych vám doporučoval si jej nejprve vyzkoušet na jednoduchém příkladu než jej začnete používat v závěrečné práci. Proto níže najdete i odkazy na zadání úloh procvičujících jednotlivé algoritmy.

Příklady algoritmů

Genetický algoritmus: Algoritmus motivovaný na evolučními principy výběru, křížení a motaci DNA v přírodě použitelný na širokou škálu optimalizačních problémů. Úvod na Wikipedii a stránkách Martina Piláta. Jednoduchý příklad použití je problém batohu.
Mravenčí kolonie (Ant colony optimization): Algoritmus inspirovaný způsobem, jakým mravenci hledají cesty k potravě, a proto se často používá na hledání cest v grafu s různými omezeními. Úvod na Wikipedii a stránkách Martina Piláta. Jednoduchý příklad použití je varianta problému obchodního cestujícího.
Optimalizace hejnem částic (Particle Swarm Optimization): Algoritmus založený na pohybu částic, kde každá má svoji polohy a rychlost a je přitahována směrem k nejlepšímu známému řešení. Na rozdíl od předchozích algoritmů je vhodný pro spojitou optimalizaci. Úvod na Wikipedii a stránkách Martina Piláta.
Gradientní metody: Algoritmus využívající derivaci k určení směru, ve kterém dostane lepší řešení. Lze použít na optimalizaci libovolné funkce, kterou umíme derivovat. Popis na Wikipedii.
Lokální prohledávání: Algoritmus zkouší, zda lze v aktuálním řešení udělat malou změnu vedoucí ke zlepšení. Popis na Wikipedii.
Memetické algoritmy: Memetické algoritmy kombinují evoluční algoritmy (generický algoritmy, mravenčí kolonie, atd.) a lokální prohledávání. Úvod na Wikipedii a stránkách Martina Piláta.
Genetické programování: Pokud máme dány hodnoty nějaké funkce f v několika bodech (například výstup nějakého experimentu) a chceme najít předpis této funkce nebo alespoň její aproximaci, můžeme použít genetické programování. Úvod na Wikipedii a stránkách Martina Piláta.
Lineární programování: Pokud umíme všechna omezení v daném problému popsat pomocí lineárních rovnic a nerovnic a cílová funkce (fitness) je též lineární, tak optimální řešení nám dá řešič (Gurobi, CPLEX a další). Popis na Wikipedii. Na lineárním programování je založeno mnoho zajímavých algoritmů, například Column generation a Lagrangian relaxation.
Splňování podmínek: Podobně jako pro lineární programování existují obecné programy umějící hledat řešení splňující libovolné matematicky formulovatelné podmínky. Popis na Wikipedii.
Strojové učení: O neuronových sítích a dalších nástrojích strojového učení jste již určitě slyšeli. Můžete je používat nejen k samotnému hledání řešení, ale i jako pomocný nástroj k zrychlení předchozích algoritmů.
Kombinace předchozích algoritmů: Ačkoliv to může znít šíleně, tak je možné v jednom algoritmu kombinovat například lineární programování, evoluční algoritmy a strojové učení. Příklad použití najdete v tomto přehledovém článku. Nicméně doporučuji jen pokud máte předchozí zkušenosti se všemi jednotlivým nástroji.

Doporučené předměty

Ke studiu výše uvedených algoritmů se vám můžou hodit následující předměty.

Lineární programování a kombinatorická optimalizace: Úvod do lineárního programování, na kterým je postavena řada matematických algoritmů. Podrobnosti na stránkách Jiřího Sgalla.
Large Scale Optimization: Exact Methods: Algoritmy vycházející z lineárního programování, zejména řezné nadroviny, Column generation a Lagrangian relaxation.
Large Scale Optimization: Metaheuristics: Heuristické algoritmy k získání co nejlepšího řešení i pro velké úlohy.
Přírodou inspirované algoritmy: Úvod do evolučních algoritmů, neuronových sítí