Master's Thesis

Evolutionary algorithms for Network Interdiction problems

Final Thesis 2.39 MB Appendix 1.55 MB

Author of thesis: Bc. Pavel Ternbach

Acad. year: 2025/2026

Supervisor: doc. Ing. Jakub Kůdela, Ph.D.

Reviewer: Ing. Jan Turčínek, Ph.D.

Abstract:

Network interdiction are a relatively old type of optimization problems, but they are still not very well known. Over the course of their existence, several different approaches to solving them have been explored. Most of these solutions were carried out using dual formulations. However, this thesis does not investigate that approach; instead, it employs three well-known solvers: genetic algorithms (GA), evolution strategies (ES), and simulated annealing (SA). This thesis compares these three algorithms between themselves and evaluates the quality of their solutions to Network interdiction problems. The problems studied are based on two optimization problems: shortest path problem and maximum flow. In addition to different problems, various graphs are also examined, differing in size and structure. Besides generating these problems and examining the results of the three aforementioned algorithms, the thesis also focuses on describing commonly used methods for solving Network interdiction problems.

Keywords:

Evolutionary algorithms, Network interdiction, Genetic algorithms, Simulated annealing, Evolutionary strategies, Shortest path problem, Maximum flow problem

Date of defence

10.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Student obeznámil komisi s výsledky své DP. Po přečtení posudků následovaly dotazy oponenta (viz posudek) a komise: Porovnání časů (v testování). Použití vlastního programování. Role obránce/útočníka (v grafu). Student na všechny dotazy oponenta i komise reagoval.

Language of thesis

Czech

Faculty

Fakulta strojního inženýrství

Department

Institute of Automation and Computer Science

Study programme

Applied Computer Science and Control (N-AIŘ-P)

Composition of Committee

doc. Ing. Oldřich Trenz, Ph.D. (předseda)
doc. Ing. Jakub Kůdela, Ph.D. (místopředseda)
prof. Ing. Zdeněk Hadaš, Ph.D. (člen)
doc. Ing. Pavel Škrabánek, Ph.D. (člen)
Ing. Jiří Kurfürst, Ph.D. (člen)
Ing. Zdeněk Švihálek (člen)
prof. Ing. Petr Doležel, Ph.D. (člen)
prof. Ing. Jiří Jaroš, Ph.D. (člen)

Supervisor’s report
doc. Ing. Jakub Kůdela, Ph.D.

Diplomová práce se zabývá problematikou úloh typu Network Interdiction a možnostmi jejich řešení pomocí vybraných evolučních a heuristických algoritmů. V teoretické části práce student přehledně představuje základní pojmy z oblasti optimalizace, teorie grafů a úloh typu Network Interdiction. Dále popisuje klasické síťové úlohy, zejména problém nejkratší cesty a maximálního toku v síti, včetně algoritmů používaných pro jejich řešení.

Praktická část práce je zaměřena na implementaci a experimentální porovnání tří optimalizačních přístupů (genetického algoritmu, evolučních strategií a simulovaného žíhání). Student navrhl vlastní sadu testovacích úloh založených na několika typech grafových struktur a provedl rozsáhlé experimentální vyhodnocení.

Po formální stránce je práce zpracována na dobré úrovni. Text je logicky členěn, obsahuje odpovídající množství obrázků, algoritmů a experimentálních výsledků. Přestože se v práci místy vyskytují drobné stylistické či jazykové nepřesnosti a chyby ve formátování, tyto nedostatky nesnižují celkovou odbornou hodnotu práce.

Student během řešení diplomové práce pracoval aktivně a samostatně, pravidelně konzultoval dosažené výsledky a průběžně reagoval na připomínky vedoucího.

Zadané cíle práce byly splněny. Diplomovou práci doporučuji k obhajobě a navrhuji hodnocení A/výborně.
Evaluation criteria Grade
Splnění požadavků a cílů zadání A
Postup a rozsah řešení, adekvátnost použitých metod A
Vlastní přínos a originalita B
Schopnost interpretovat dosažené výsledky a vyvozovat z nich závěry A
Využitelnost výsledků v praxi nebo teorii B
Logické uspořádání práce a formální náležitosti B
Grafická, stylistická úprava a pravopis B
Práce s literaturou včetně citací A
Samostatnost studenta při zpracování tématu A

Grade proposed by supervisor: A

Reviewer’s report
Ing. Jan Turčínek, Ph.D.

Předložená práce plní stanovené cíle v oblasti řešení úloh typu Network Interdiction pomocí evolučních algoritmů. Teoretická rešerše představuje dostačující základ pro rozsáhlou experimentální část, která tvoří jádro práce.
Výpočetní náročnost experimentů, dosahující v součtu desítek hodin čistého strojového času, svědčí o robustnosti testování a získané výsledky jsou navíc správně validovány pomocí Friedmanova a Wilcoxonova testu.

I přes vysokou kvalitu praktických výsledků má práce drobné metodické a formální nedostatky. V textu postrádám detailnější popis technického zajištění a automatizace takto rozsáhlého testování; není specifikováno, jakým způsobem byl celý proces spouštění experimentů a sběru dat realizován. Po formální stránce se v práci občas objevují drobné typografické chyby a překlepy, které však nesnižují její celkovou vysokou odbornou úroveň.

Otázka:
Z výsledků Friedmanova i Wilcoxonova testu jednoznačně vyplývá, že Simulované žíhání (SA) dosahovalo nejhorších výsledků, ačkoli celková doba výpočtu (téměř 60 hodin) byla srovnatelná s úspěšnějším Genetickým algoritmem. Čím si vysvětlujete takto nízkou efektivitu algoritmu SA na testovaných grafech?
Evaluation criteria Grade
Splnění požadavků a cílů zadání A
Postup a rozsah řešení, adekvátnost použitých metod B
Vlastní přínos a originalita A
Schopnost interpretovat dosaž. výsledky a vyvozovat z nich závěry A
Využitelnost výsledků v praxi nebo teorii A
Logické uspořádání práce a formální náležitosti A
Grafická, stylistická úprava a pravopis C
Práce s literaturou včetně citací A

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová