Detail práce

Aplikace mravenčích algoritmů v rozsáhlých úlohách TSP

Bakalářská práce Student: Ramosová Patrícia Akademický rok: 2019/2020 Vedoucí: Bidlo Michal, doc. Ing., Ph.D.
Jazyk práce
slovenský
Abstrakt

V súčasnej dobe je v rade aplikácií kladený dôraz na nájdenie optimálneho riešenia určitého problému.  Pre niektoré úlohy je však typické, že sa ich náročnosť stupňuje exponenciálne v závislosti na veľkosti inštancie. Typickým príkladom takéhoto problému je obchodný cestujúci (angl. Traveling Salesman Problem - TSP). Jednou triedou metód, ktoré sa ukázali byť v riešení TSP veľmi nápomocné, sú mravčie algoritmy. Narazili však na svoj limit - vysoký počet miest v inštancii, kedy sa už stali kvôli časovej a pamäťovej náročnosti takmer nepoužiteľné. Cieľom tejto práce je modifikovať mravčí algoritmus a vytvoriť tak systém schopný rýchlo a efektívne riešiť rozsiahle úlohy TSP bez výraznej straty na kvalite nájdeného riešenia. Optimalizácie budú zamerané na redukciu priestorovej zložitosti a celkovému zníženiu výpočtového času.

Klíčová slova

optimalizácia mravčou kolóniou, problém obchodného cestujúceho, rozsiahle inštancie TSP, MAX-MIN Ant System

Ústav
Ústav počítačových systémů FIT VUT v Brně
Studijní program
Informační technologie
Soubory
Stav
obhájeno, hodnocení B
Obhajoba
8. července 2020
Oponent
Jaroš Jiří, doc. Ing., Ph.D.
Průběh obhajoby

Studentka nejprve prezentovala výsledky, kterých dosáhla v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Studentka následně odpověděla na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studentky na položené otázky rozhodla práci hodnotit stupněm B.

Otázky u obhajoby
  1. Můžete nějak kvantifikovat přínos jednotlivých technik (principiální úpravy algoritmu, paralelizace, vektorizace) na rychlost optimalizace?
  2. Na jakém systému byly řešeny jednotlivé úlohu? Úloha 5 byla měřena na Barboře, ty ostatní?
  3. Předpokládejme, že časová složitost MMAS roste lineárně s počtem mravenců. Proč tomu tak dle tabulky 5.6 není?  Devatenáctinásobný nárůst počtu mravenců vede pouze na čtyřnásobné prodloužení výpočetního času.
  4. Bylo by možné převést celý výpočet do datového typu float namísto double?
  5. Prováděla jste nějaké důkladnější profilování aplikace, či měření výkonnosti dílčích částí?
  6. V makefile jsem objevil parametr -mmic, který implikuje kompilaci pro akcelerátor Intel XeonPhi. Použila jste tuto kartu ve své práci?
  7. Jaké je porovnání konvenčního řešení s implementovaným algoritmem?
  8. Jaký byl hlavní cíl využití vektorových instrukcí?
  9. Jakým způsobem byly měřeny délky iterací?
  10. Jakým způsobem defininujete přesnost dosahovaného řešení?
Komise
Kořenek Jan, doc. Ing., Ph.D. (UPSY FIT VUT), předseda
Drahanský Martin, prof. Ing., Dipl.-Ing., Ph.D. (UITS FIT VUT), člen
Grézl František, Ing., Ph.D. (UPGM FIT VUT), člen
Hrubý Martin, Ing., Ph.D. (UITS FIT VUT), člen
Polčák Libor, Ing., Ph.D. (UIFS FIT VUT), člen
Citace
RAMOSOVÁ, Patrícia. Aplikace mravenčích algoritmů v rozsáhlých úlohách TSP. Brno, 2020. Bakalářská práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2020-07-08. Vedoucí práce Bidlo Michal. Dostupné z: https://www.fit.vut.cz/study/thesis/22589/
BibTeX 
@bachelorsthesis{FITBT22589,
    author = "Patr\'{i}cia Ramosov\'{a}",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    title = "Aplikace mraven\v{c}\'{i}ch algoritm\r{u} v rozs\'{a}hl\'{y}ch \'{u}loh\'{a}ch TSP",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2020,
    location = "Brno, CZ",
    language = "slovak",
    url = "https://www.fit.vut.cz/study/thesis/22589/"
}

Závěrečné práce

Nahoru