Dolování dat
Genetické algoritmy
Jan Górecki
Název
prezentace
Název projektu
Rozvoj vzdělávání na Slezské univerzitě v Opavě
Registrační číslo projektu
CZ.02.2.69/0.0./0.0/16_015/0002400
Logolink_OP_VVV_hor_barva_cz

Obsah přednášky
•Co jsou Genetické algoritmy (GA)
•Příklad
•Selekce
•Křížení
•Mutace
•GA pro získávání pravidel z dat

Vysvětlení genetických algoritmů:
https://www.youtube.com/watch?v=7J-DfS52bnI
Další:
https://obitko.com/tutorials/genetic-algorithms/index.php

Genetické algoritmy
•Zdrojem inspirace se tentokrát stal mechanismus evoluce:
„Nějaký živočišný druh se během svého vývoje zdokonaluje tak, že z generace na generaci se přenáší
genetická informace jen těch nejsilnějších jedinců.“
-
-
-
-
-Používají se především pro optimalizaci (nelineární regrese,
neuronové sítě)
-Hledání globálního minima chybové funkce – podobně jako
např. simulované žíhání, genetická optimalizace umí
překonat uvíznutí v lokálním minimu (maximu)
Genetický algoritmus (GA) je heuristický postup, vycházející z evolučního přístupu, který lze
nasadit na řešení složitých problémů, pro které neexistuje použitelný exaktní algoritmus.

csvukrs

Příklad
Hledání globálního maxima Rastriginovy funkce
fit(x1, x2) = − 20 − x12 − x22 + 10(cos2πx1 + cos2πx2)
Globální maximum v (0,0)
Lokální maximum
Lokální minimum

https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html#f13721

Příklad

https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html#f13721
Elite – zachovám nejsilnější jedince
Crossover – kombinuju nejsilnější jednice
Mutace – zvětšuju diverzitu populace (překování uvíznutí v lokálním minimu)
Sem8.txt – ukázka v tohoto příkladu MATLABu

Genetický algoritmus
Podmínka pro zastavení:
•počet generací
•kvalita nejlepšího jedince v populaci
•změna kvality nejlepšího jedince mezi generacemi

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8b
f3

Selekce

https://en.wikipedia.org/wiki/Tournament_selection

Křížení
jednobodové
dvoubodové
K*N/2 dvojic

csvukrs

Mutace
M*N jedinců

csvukrs

GA pro získávání pravidel z dat
paralelní náhodné prohledávání

GABIL (deJong, 1993)

Jedinci jsou pravidla:
If konto(nízké) Ù příjem(nízký)  then úvěr(ne)
If konto(vysoké)  then úvěr(ano)

100 10 01
001 11 10

csvukrs

Zpřesnění základního algoritmu

csvukrs

Aplikace
Řešení ekonomických úloh
•Optimalizace výrobního plánu podniku (více výrobků a společné suroviny na jejich výrobu).
•Problém obchodního cestujícího (častá úloha v podobě rozvážky zboží na jednotlivá distribuovaná
místa, obdobou je i hledání spojnice optimální trasy mezi dvěma vzdálenými městy).
•Úloha o baťohu (cílem je umístit výrobky o daných rozměrech do vymezeného prostoru, často
využíváno u distribučních a zásilkových služeb při volbě vhodného obalového materiálu, potažmo
krabice).
•Umístění distribučního skladu (modifikace úlohy obchodního cestujícího, cílem je umístit
distribuční sklad tak, aby bylo zvolené místo optimální vzhledem na propustnost distribučních cest
a velikost zavážek).

https://is.mendelu.cz/eknihovna/opory/zobraz_cast.pl?cast=21840

Děkuji za pozornost
Některé snímky převzaty od:
prof. Ing. Petr Berka, CSc. berka@vse.cz