Chaotické atributy permutačních optimalizací

Abstract

Jádro této dizertační práce tvoří problematika diverzity populace v evolučních algoritmech se zaměřením na permutační problémy. V práci je diskutována stagnace z pohledu deterministického chaosu se zaměřením na existenci chaotických atraktorů a tzv. hrany chaosu. Na základě existence chaotického chování, pozorovaného v evolučních technikách, jsou v této práci navržené nové řídicí metody a strategie, umožňující řídit chování a tím i výkonnost známých heuristik. V práci jsou navrženy (a také odzkoušeny) tři nové verze algoritmu SOMA a to: permutační SOMA (Permutative Set Handling SOMA), statická permutační SOMA (Static Permutative SOMA) a dynamická permutační SOMA (Dynamic Permutative SOMA). Permutační SOMA je modifikace existujícího algoritmu, využívající speciální stochastické opravné techniky v syntetizovaných řešeních, statická permutační SOMA využívá předdefinované sekvence skoků jedince, dynamická permutační SOMA využívá k výpočtu vhodných skoků jedince velikost řešeného problému. Společně s těmito modifikacemi je v práci diskutována problematika detekce chaosu a hran chaosu v populacích u různých algoritmů jako je diferenciální evoluce, SOMA a genetický algoritmus. Na základě existence chaotického chování, pozorovatelného v dynamice evolučních technik, jsou rovněž navržena nová pravidla pro výběr či zamítnutí nových řešení - jedinců v populaci. Pro potvrzení nových postupů a metod uváděných v této práci bylo vybráno šest typů problémů a to rozvrhování proudové výroby (Flow Shop Scheduling), rozvrhování proudové výroby s omezeným skladem (Flow Shop with Limited Intermediate Storage), rozvrhování proudové výroby s nulovým zpožděním (Flow Shop with No- Wait), kvadratický přiřazovací problém (Quadratic Assignment problem), okružní a rozvozní problémy (Vechicle Routing problem) a rozvrhování zakázkové výroby (Job Shop Scheduling problem). Tyto problémy byly řešeny již zmíněnými evolučními technikami a všechny získané výsledky ověřily správnost navrhovaných metod v této práci. Všechny výsledky jsou vzájemně srovnány a vyhodnoceny v závěru práce.