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.
Annotation in English
Diversity in evolutionary algorithms and its application to permutative based combinatorial
optimization problems is the core objective of this dissertation. Diversity of
a population is viewed in terms of solution ordering.
Stagnation and its implication through chaotic attributes such as the application of
attractor and the viability of the the edge is discussed. Using these attributes, new
attack strategies in solution control are developed in order to induce viability in terms
of uniqueness to canonical metaheuristics.
Three new permutative versions of Self Organising Migrating Algorithm (SOMA)
are developed, being the Permutative Set Handling, Static Permutative SOMA and
Dynamic Permutative SOMA.
Permutative Set Handling is a new approach using special stochastic repairment
techniques. Static Permutative SOMA is a novel approach which uses pre-defined
jump sequences in order to calculate the mapping between two individuals. Dynamic
Permutative SOMA utilizes the problem size in order to calculate the jump sequences.
Novel clustered population paradigms based loosely around the concept of chaotic
attractors and edges are developed and utilized through Differential Evolution (DE),
SOMA and Genetic Algorithms (GA). New selection and deletion criteria´s are developed
and vetted with the canonical metaheuristics.
Six unique and challenging permutative based combinatorial optimization problems
of Flow Shop Scheduling, Flow Shop with Limited Intermediate Storage, Flow
Shop with No-Wait, Quadratic Assignment problem, Vehicle Routing problem and Job
Shop Scheduling problem are solved using these heuristics.
All results obtained validate the application of clustered heuristics. In Flow Shop
scheduling and Quadratic Assignment problem, GA is compared alongside DE and
SOMA which are the best performing heuristics for these problem class. In the other
problems, DE and SOMA are evaluated in the canonical and clustered version, with
DE on average slightly better performing than SOMA.
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.
Annotation in English
Diversity in evolutionary algorithms and its application to permutative based combinatorial
optimization problems is the core objective of this dissertation. Diversity of
a population is viewed in terms of solution ordering.
Stagnation and its implication through chaotic attributes such as the application of
attractor and the viability of the the edge is discussed. Using these attributes, new
attack strategies in solution control are developed in order to induce viability in terms
of uniqueness to canonical metaheuristics.
Three new permutative versions of Self Organising Migrating Algorithm (SOMA)
are developed, being the Permutative Set Handling, Static Permutative SOMA and
Dynamic Permutative SOMA.
Permutative Set Handling is a new approach using special stochastic repairment
techniques. Static Permutative SOMA is a novel approach which uses pre-defined
jump sequences in order to calculate the mapping between two individuals. Dynamic
Permutative SOMA utilizes the problem size in order to calculate the jump sequences.
Novel clustered population paradigms based loosely around the concept of chaotic
attractors and edges are developed and utilized through Differential Evolution (DE),
SOMA and Genetic Algorithms (GA). New selection and deletion criteria´s are developed
and vetted with the canonical metaheuristics.
Six unique and challenging permutative based combinatorial optimization problems
of Flow Shop Scheduling, Flow Shop with Limited Intermediate Storage, Flow
Shop with No-Wait, Quadratic Assignment problem, Vehicle Routing problem and Job
Shop Scheduling problem are solved using these heuristics.
All results obtained validate the application of clustered heuristics. In Flow Shop
scheduling and Quadratic Assignment problem, GA is compared alongside DE and
SOMA which are the best performing heuristics for these problem class. In the other
problems, DE and SOMA are evaluated in the canonical and clustered version, with
DE on average slightly better performing than SOMA.
