Bakalářská práce je zaměřená na používání evolučních optimalizačních technik k řešení NP úplných problémů. V teoretické části jsou vysvětleny a popsány: NP úplnost, vybrané NPC problémy a evoluční algoritmy.
V praktické části jsou implementovány a optimalizovány jednotlivé metody evolučních technik. Tyto metody jsou dále aplikovány na ukázkových NP problémech a závěrem jsou porovnány jejich účinnosti.
Anotace v angličtině
This Bachelor work is focused on using evolution of optimization techniques for solution NP-complete problems. In the theoretical part are explained and described: NP completeness, selected NPC problems and evolution algorithms.
In the practice part are implemented and optimized the individual methods of evolutionary techniques. These methods are applied to the demonstration NP issues and conclusions are compared their effectiveness.
Klíčová slova
Genetické algoritmy, evoluční strategie, diferenciální evoluce, horolezecký algoritmus, NP úplnost, problém batoh, hledání globálního minima
Klíčová slova v angličtině
Genetic algorithm, Evaluation strategy, Differential evolution, Hill climbing, NP-complete, Problem bagging, Search global minima
Rozsah průvodní práce
-
Jazyk
CZ
Anotace
Bakalářská práce je zaměřená na používání evolučních optimalizačních technik k řešení NP úplných problémů. V teoretické části jsou vysvětleny a popsány: NP úplnost, vybrané NPC problémy a evoluční algoritmy.
V praktické části jsou implementovány a optimalizovány jednotlivé metody evolučních technik. Tyto metody jsou dále aplikovány na ukázkových NP problémech a závěrem jsou porovnány jejich účinnosti.
Anotace v angličtině
This Bachelor work is focused on using evolution of optimization techniques for solution NP-complete problems. In the theoretical part are explained and described: NP completeness, selected NPC problems and evolution algorithms.
In the practice part are implemented and optimized the individual methods of evolutionary techniques. These methods are applied to the demonstration NP issues and conclusions are compared their effectiveness.
Klíčová slova
Genetické algoritmy, evoluční strategie, diferenciální evoluce, horolezecký algoritmus, NP úplnost, problém batoh, hledání globálního minima
Klíčová slova v angličtině
Genetic algorithm, Evaluation strategy, Differential evolution, Hill climbing, NP-complete, Problem bagging, Search global minima
Zásady pro vypracování
Anotace:
Cíl práce: Cílem je nalézt a vhodně modifikovat různé evoluční algoritmy tak, aby pokud možno efektivně řešily ukázkové NP úplné problémy (dva loupežníci, problém batohu, obchodní cestující, ...).
Teoretická část: Je třeba popsat NP úplnost po teoretické stránce, popsat evoluční algoritmy, které budou použity a dále popsat historii a zadání jednotlivých NP úplných problémů.
Implementační část: Student v JAVĚ (případně v jiném jazyce, podle domluvy) naprogramuje funkce pro použití jednotlivých evolučních algoritmů. Tyto funkce pak aplikuje na ukázkové NP úplné problémy a porovná jejich účinnost.
Zásady pro vypracování
Anotace:
Cíl práce: Cílem je nalézt a vhodně modifikovat různé evoluční algoritmy tak, aby pokud možno efektivně řešily ukázkové NP úplné problémy (dva loupežníci, problém batohu, obchodní cestující, ...).
Teoretická část: Je třeba popsat NP úplnost po teoretické stránce, popsat evoluční algoritmy, které budou použity a dále popsat historii a zadání jednotlivých NP úplných problémů.
Implementační část: Student v JAVĚ (případně v jiném jazyce, podle domluvy) naprogramuje funkce pro použití jednotlivých evolučních algoritmů. Tyto funkce pak aplikuje na ukázkové NP úplné problémy a porovná jejich účinnost.
Seznam doporučené literatury
*ZELINKA, I. Umělá inteligence v problémech globální optimalizace. Praha : BEN - technická literatura, 2002. 193 s. ISBN 80-7300-069-5
*HYNEK, J. Genetické algoritmy a genetické programování. Praha: GRADA, 2008. 200 s. ISBN 978-80-247-2695-3
Seznam doporučené literatury
*ZELINKA, I. Umělá inteligence v problémech globální optimalizace. Praha : BEN - technická literatura, 2002. 193 s. ISBN 80-7300-069-5
*HYNEK, J. Genetické algoritmy a genetické programování. Praha: GRADA, 2008. 200 s. ISBN 978-80-247-2695-3
Přílohy volně vložené
CD ROM
Přílohy vázané v práci
-
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Cílem práce bylo dle vedoucího práce nalézt a vhodně modifikovat různé evoluční algoritmy (genetický algoritmus, diferenciální evoluce, SOMA) tak, aby pokud možno efektivně řešily ukázkové NP úplné problémy (dva loupežníci, problém batohu, obchodní cestující, ...).
Výstupem práce je aplikace, která může sloužit k demonstraci principů několika typů a evolučních algoritmů.
Student výborně reagoval na dotazy a připomínky členů komise.