Polytechnická univerzita v Bukurešti ročník - ppt stiahnuť
Polytechnická univerzita v Bukurešti Akademický rok 2008-2009 Automatické vzdelávanie Polytechnická univerzita v Bukurešti Akademický rok 2008-2009 Adina Magda Florea http://turing.cs.pub.ro/inva_09 a curs.cs.pub.ro
Kurz č. 9 Genetické algoritmy Úvod Základná schéma Modelovanie problémov Príklad Výber Rekombinácia TSP mutácia s genetickými algoritmami Paralelná implementácia AG 2
1. Úvod GA - USA, J. H. Holland (1975) Evolučné algoritmy - Nemecko, I. Rechenberg, H.-P. Schwefel (1975-1980) Genetické programovanie (1960-1980, 2000) J. Koza Optimalizácia Ekonomické modely Ekologické modely Modely sociálnych systémov Učenie 3
Úvod - účet Funguje na populácii jednotlivcov = potenciálne riešenia - uplatňuje princíp prežitia založený na adaptácii (zdatnosti) Každá generácia - nový prístup k riešeniu Evolúcia populácie jednotlivcov lepšie prispôsobená prostrediu Modely prírodných procesov: výber, rekombinácia, mutácia, migrácia, poloha Obyvateľstvo jednotlivcov - paralelné vyhľadávanie 4
2. Základná schéma Generuje populáciu počiatočných jedincov (gény) Reprezentácia problému Funkcia Fitness Generuje populáciu počiatočných jedincov (gény) Vyhodnocuje objektívnu funkciu Kritérium zastavenia splnené? áno nie najlepší jedinci výber počiatočných výsledkov kríženie/rekombinácia získanie novej populácie potomkov mutácie generácie 5
3. Modelovanie problémov Počiatočná populácia Vytvoriť zastúpenie - gén - jednotlivec Určiť počet jedincov v populácii Stanoviť hodnotiacu funkciu (cieľ) Počiatočná populácia (gény) náhodne vytvorená Selection Selection - extrakcia podmnožiny génov z existujúcej populácie ako definícia kvality - hodnotiaca funkcia Určuje jednotlivcov vybraných na rekombináciu a koľko potomkov vyprodukuje každý jedinec 6
Modelovanie problémov Zastavovacie kritérium Multipopulačné GA riešenie, ktoré spĺňa kritérium počet generácií plató rozpočet pre najlepšiu kondíciu Multipopulačné GA Lepšie výsledky - subpopulácie Každá populácia sa vyvíja osobitne Jednotlivci sa menia po niekoľkých generáciách 7
Výber (1) Prvý krok: priradenie fitnes - proporcionálne priradenie - priradenie podľa poradia (2) Efektívny výber: rodičia sú vybraní vo fitness na základe jedného z algoritmov: výber rulety stochastické univerzálne vzorkovanie stohastica) miestny výber (miestny výber) výber turnaja (výber turnaja) výber skrátenia (skrátený výber) 8
Opätovné vloženie potomstva - ak sa vyskytne menej jedincov alebo menej detí, musia sa do novej populácie znova vložiť ďalší jedinci. Algoritmus výberu určuje schému opätovného vloženia (všeobecne) globálnu reintegráciu - do celej populácie pre. výber rulety, stochastický univerzálny odber vzoriek, výber skrátenia lokálne vloženie pre miestny výber 9
Crossover/Recombination Rekombinácia vytvára nových jedincov kombináciou informácií od rodičov (rodičia - páriaca sa populácia). Rôzne schémy rekombinácie Jedna možnosť - náhodné párenie Rovnaké ako pri genetickom krížení Vyberie sa a náhodne spáruje percento PM novo osídlených jedincov. Pre každý pár sa vyberie krížový bod (rovnaká alebo iná pravdepodobnosť). Medzi týmito dvoma osobami sa vymieňajú informácie. jednotlivci na základe bodu prechodu 10
Mutácia s malými náhodnými poruchami Potomstvo - mutácia Mutácia s malými náhodnými poruchami Rôzne formy mutácií, v závislosti od znázornenia Mutácia - skúmanie vs vykorisťovanie Jednoduchá schéma Každý bit má pravdepodobnosť mutácie 12
Účinok mutácie a selekcie 14
4 Príklad Vypočítajte maximum funkcie f (x1, x2,. Xn) Nájdite x1, x2,. xn, pre ktoré je maximum f Použite GA 15
Reprezentácia Mierka premenných vynásobením 10n, kde n je požadovaná presnosť Premenná = celé číslo (Var × 10 n) Premenné sú reprezentované v binárnom formáte Premenné sú zreťazené - individuálne Ak chceme znamienko: Pridajte hodnotu a otočte ju na kladnú alebo O jeden bit na znamienko Binárna reprezentácia alebo Sivý kód 16
Výpočet Počiatočná populácia náhodná Crossover Selection Mutation Transformuje každého jednotlivca na premenné: x1, x2,. xn Vyskúšajte kvalitu každého jednotlivca: f (x1, x2,. xn) Vyskúšajte, či je kvalita najlepšieho jednotlivca dosť dobrá, ak prestanete, inak choďte na 2 17
5. Výber Prvým krokom je priradenie zdatnosti (F) Priame priradenie na základe objektívnej funkcie ALEBO Priradenie založené na mechanizme Každý jednotlivec v populácii dostane hodnotu zdatnosti Na základe hodnoty zdatnosti sa výber (S) uskutoční podľa výberovej schémy 18
Výber Pravdepodobnosť reprodukcie možno spájať s jednotlivcom - závisí to od hodnoty fitnesovej funkcie jednotlivca a od hodnoty fitnesovej funkcie ostatných jedincov v populácii. Túto pravdepodobnosť je možné použiť pri výbere 19.
Pojmy selekčný tlak: pravdepodobnosť výberu najlepšieho jedinca v porovnaní s priemernou pravdepodobnosťou selekcie všetkých jednotlivcov: rozsah hodnôt počtu potomkov jednotlivca strata rozmanitosti: podiel jednotlivcov v populácii, ktorý nie je vybraný, intenzita výberu: priemerná hodnota fitnes populácie po uplatnení výberovej kovariancie výberovej metódy: kovariancia distribúcie fitnes populácie po aplikácii výberovej metódy 20
A1. Proporcionálna alokácia zdatnosti Každý gén má priradenú zdatnosť Vypočítajte priemernú zdatnosť populácie Každý jednotlivec sa skopíruje do novej populácie vo funkcii fitness v porovnaní s priemernou zdatnosťou fitnes 5,76, zdatnosť jednotlivca 20,21 - skopíruje sa trikrát Jednotlivci s zdatnosťou rovnou alebo nižšou priemer sa ignoruje Nová populácia - môže byť menšia Nová populácia je naplnená náhodne vybranými jedincami zo starej populácie 21
A2. Priradenie fitnes podľa poradia Fitnes priradený každému jednotlivcovi závisí iba od jeho postavenia medzi jednotlivcami v populácii. Postavenie jednotlivca v populácii závisí od objektívnej funkcie Pos = 1 - najmenej dobrý Pos = Nind - najlepší Obyvateľstvo je zoradené podľa fitnes 22
Priradenie fitnes na základe poradia Nind - počet jednotlivcov v populácii Pos - poloha jednotlivca v populácii (najhorší Pos = 1, najlepší Pos = Nind) SP - selekčný tlak (pravdepodobnosť výberu najlepšieho jedinca v pomere k pravdepodobnosti priemerný výber všetkých jednotlivcov) Lineárne poradie Fitness (Pos) = 2 - SP + 2 * (SP - 1) * (Pos - 1)/(ind - 1) Lineárne poradie umožňuje hodnoty SP v (1,0, 2,0). výberu jedinca na rekombináciu je zdatnosť (normalizovaná) v porovnaní s celkovou zdatnosťou populácie 23
Priradenie fitnes na základe hodnotenia Nelineárne hodnotenie: Fitness (Pos) = Nind * X (Pos - 1)/ i = 1, Nind (X (i - 1)) X sa počíta ako koreň polynómu: 0 = (SP - Nind ) * X (Nind - 1) + SP * X (Nind - 2) +. + SP * X + SP Nelineárny rozsah umožňuje hodnoty SP v [1,0, Nind - 2,0] SP vyššie Pravdepodobnosť výberu jednotlivca na rekombináciu je zdatnosť (normalizovaná) vzhľadom na celkovú zdatnosť populácie 24
Priradenie fitnes na základe lineárneho poradia SP = 2 0.2 SP = 1,5 0,5.1,5 Priradenie fitnes lineárne poradie a nelineárne poradie 25
Priradenie fitnes na základe poradia V porovnaní s proporcionálnym priradením: Vyvarujte sa problému stagnácie, ak je výberový tlak príliš nízky alebo predčasná konvergencia vytvára príliš úzku oblasť vyhľadávania Poskytuje ľahký spôsob kontroly výberového tlaku Všeobecne robustnejšie 26
Priradenie fitnes na základe poradia Vlastnosti Intenzita výberu: SelIntRank (SP) = (SP-1) * (1/sqrt ()). Strata rozmanitosti: LossDivRank (SP) = (SP-1)/4. Kovariancia výberu: SelVarRank (SP) = 1 - ((SP-1) 2/) = 1-SelIntRank (SP) 2. 27
S1. Výber na základe „výberu rulety“ alebo „stochastického vzorkovania s náhradou“ 11 jednotlivcov, lineárne poradie a SP = 2 6 náhodných čísel (rovnomerne rozdelených medzi 0,0 a 1,0): 0,81, 0,32, 0,96, 0,01, 0,65, 0,42. Individuálne číslo 1 2 3 4 5 6 7 8 9 10 11 Fitness hodnota 2,0 1,8 1,6 1,4 1,2 1,0 0,8 0,6 0,4 0,2 0,0 Pravdepodobne. výber 0,18 0,16 0,15 0,13 0,11 0,09 0,07 0,06 0,03 0,02 6, 2, 9, 1, 5, 3 28
S2. Stochastické univerzálne vzorkovanie Ukazovatele sú umiestnené v rovnakých vzdialenostiach v intervale [0.1] - vyberie sa toľko ukazovateľov ako jednotlivcov NPointer - počet vybraných jedincov Vzdialenosť medzi ukazovateľmi 1/Npointer Pozícia prvého ukazovateľa je daná náhodným číslom v rozmedzí [0.1/NPinter]. Pre výber 6 osôb je vzdialenosť medzi ukazovateľmi 1/6 = 0,167. 1 náhodné číslo v rozsahu [0, 0,167]: 0,1. 1, 2, 3, 4, 6, 8 29
S3. Miestny výber Každý jednotlivec je v susedstve Štruktúra populácie Okolie - skupina jednotlivcov, ktorí môžu rekombinovať (potenciál) Lineárne susedstvo: úplný a polovičný okruh 30
Potom je definované susedstvo pre každého vybraného jednotlivca. Lokálny výber Prvá polovica populácie je vybraná náhodne (alebo pomocou výberového algoritmu - stochastický odber vzoriek alebo turnaj). Potom je definované susedstvo pre každého vybraného jednotlivca. Vyberte iného jedinca na rekombináciu v susedstve (najlepší, vhodný proporčne alebo náhodne). 32
Miestny výber Izolačná vzdialenosť medzi jednotlivcami Čím menšie je okolie, tým väčšia je izolácia Prekrývajúce sa štvrte - dochádza k prenosu vlastností Veľkosť okolia určuje rýchlosť šírenia Rýchle šírenie vs. udržiavanie vysokej rozmanitosti Vysoká rozmanitosť - zabraňuje predčasnej konvergencii 33
S4. Výber turnaja Počet turnajov jednotlivcov v populácii je vybraný náhodne a najlepší rodič je vybraný ako rodič. Proces sa opakuje pre koľko jednotlivcov chceme vybrať. Parameterom veľkosti turnaja je Tour. Prehliadka - hodnoty medzi 2 . Nind Vzťah medzi prehliadkou a intenzitou výberu Veľkosť turnaja 1 2 3 5 10 30 Intenzita výberu 0,56 0,85 1,15 1,53 2,04 Priemerná hodnota kondície populácie po použití výberovej metódy 34
Výber turnaja Intenzita výberu: SelIntTour (Tour) = sqrt (2 * (log (Tour) -log (sqrt (4,14 * log (Tour)))))) Strata rozmanitosti: LossDivTour (Tour) = Tour - (1/(Tour) -1)) - Tour - (Tour/(Tour-1)) (Približne 50% populácie je stratených pri Tour = 5). Variabilita výberu: SelVarTour (Tour) = 1 - 0,096 * log (1 + 7,11 * (Tour-1)), SelVarTour (2) = 1-1/ 35
6. Crossover/recombination Produkuje nových jedincov rekombináciou rodičovských informácií Binárne reprezentácie binárne viacbodové uniformné Celé/reálne reprezentácie diskrétne skutočné lineárne medziľahlé 36
6.1 Binárna rekombinácia Náhodne zvolená poloha kríženia occur vyskytujú sa 2 potomkovia 37.
Binárna rekombinácia Príklad jednotlivca 1: 0 1 1 1 0 0 1 1 0 1 0 pozícia crossoveru = 5 Vytvoria sa 2 nové osoby: potomstvo 1: 0 1 1 1 0 | 1 0 0 1 0 1 potomstvo 2: 1 0 1 0 1 | 0 1 1 0 1 0 38
6.2 Rekombinácia viacbodových m krížových pozícií ki jednotlivca 1: 0 1 1 1 0 0 1 1 0 1 0 jednotlivcov 2: 1 0 1 0 1 1 0 0 1 0 1 poz. kríž (m = 3) 2 6 10 potomkov 1: 0 1 | 1 0 1 1 | 0 1 1 1 | 1 potomok 2: 1 0 | 1 1 0 0 | 0 0 1 0 | 0 39
6.3 Jednotná rekombinácia Zovšeobecňuje jednoduchú binárnu a viacbodovú masku Crossover - rovnakú veľkosť ako jednotlivec; náhodne vytvorená a parita bitov v maske označuje, ktorý rodič dá potomkovi, ktorý ktorý bit individuálne, 1: 0 1 1 1 0 0 1 1 0 1 0 jednotlivca 2: 1 0 1 0 1 1 0 0 1 0 1 maska 1: 0 1 1 0 0 0 1 1 0 1 0 maska 2: 1 0 0 1 1 1 0 0 1 0 1 (vzad na masku 1) potomstvo 1: 1 1 1 0 1 1 1 1 1 1 1 1 potomok 2: 0 0 1 1 0 0 0 0 0 0 0 Spears a De Jong (1991) - parametrizácia pomocou priradenia pravdepodobnosti 40
6.4 Skutočná diskrétna rekombinácia Diskrétna rekombinácia Výmena skutočných hodnôt medzi jednotlivcami. jednotlivec 1: 12 25 5 jednotlivec 2: 123 4 34 Pre každú hodnotu je náhodne vybraný prispievajúci rodič vzorka 1: 2 2 1 vzorka 2: 1 2 1 Po rekombinácii: potomok 1: 123 4 5 potomok 2: 12 4 5 41
Diskrétna skutočná rekombinácia Diskrétna rekombinácia Možné polohy potomkov Možno použiť s ľubovoľnými hodnotami (binárne, skutočné alebo symboly). 42
Medzikontinentálna rekombinácia Iba pre skutočné hodnoty Hodnoty potomkov zvolených okolo hodnôt od rodičov Pravidlo: potomok = rodič 1 + alfa (rodič 2 - rodič 1), kde Alpha je náhodne zvolený faktor škálovania v rozsahu [-d, 1 + d] . d = 0 alebo d> 0. Dobrá hodnota d = 0,25. Každá hodnota v potomstve je výsledkom kombinácie rodičov s novou alfa pre každú premennú 43
Stredná skutočná rekombinácia jednotlivec 1: 12 25 5 jednotlivcov 2: 123 4 34 Hodnoty alfa sú: vzorka 1: 0,5 1,1 -0,1 vzorka 2: 0,1 0,8 0,5 Noví jedinci (potomstvo = rodič 1 + Alfa (rodič 2 - rodič 1) potomok 1: 67,5 1,9 2,1 potomka 2: 23,1 8,2 19,5 44
Skutočná medziproduktová rekombinácia Rozsah hodnôt potomkov v porovnaní s rodičmi Distribúcia potomkov po prechodnej rekombinácii 45
Skutočná lineárna rekombinácia Lineárna rekombinácia Podobná ako medziprodukt, ale používa sa iba jedna alfa. jednotlivci 1: 12 25 5 jednotlivci 2: 123 4 34 Alfa hodnoty sú: vzorka 1: 0,5 vzorka 2: 0,1 Noví jedinci: potomkovia 1: 67,5 14,5 19,5 potomkovia 2: 23,1 22,9 7,9 46
Lineárna skutočná rekombinácia Lineárna rekombinácia 47
7. Mutácia Po rekombinácii - mutácia potomkov Hodnoty od potomkov sa posúvajú inverziou (binárne) alebo pridaním malých náhodných hodnôt (krok mutácie), s nízkou pravdepodobnosťou. Pravdepodobnosť mutácie je nepriamo úmerná veľkosti jedincov. Čím dlhšie máme jedincov pravdepodobnosť mutácie je nižšia 48
7.1 Binárna mutácia Výmena binárnych hodnôt Pre každého jednotlivca je bit, ktorý sa má presunúť, náhodne vybraných 11 hodnôt, bit 4 pred mutáciou 1 po mutácii 49
7.2 Mutácia so skutočnými hodnotami Mutačný efekt Veľkosť kroku - ťažká; sa môže v priebehu vývoja líšiť Malý - dobrý, pomalý; veľký - rýchlejší Operátor mutácie: mutovaná premenná = premenná ± rozsah · delta (+ alebo - s rovnakými pravdepodobnosťami) rozsah = 0,5 * delta variabilnej domény = súčet (a (i) 2-i), a (i) = 1 s pravdepodobnosťou 1/m, inak a (i) = 0,50
8. Použitie GA na: - Batoh s problémom 0/1 - TSP 51
8.1 Problém s batohom 0/1. Daných je veľa predmetov, každý s hmotnosťou/hmotnosťou w (i) a hodnotou/ziskom p (i). Určte počet objektov každého typu, ktoré sa majú zahrnúť do zbierky a.i. hmotnosť by mala byť menšia ako zadaná hodnota W a celková hodnota by mala byť maximálna. Batoh s problémom 0/1 - 0 alebo 1 objekt každého typu. Multiobjektívny optimalizačný problém: maximalizovať zisk a minimalizovať váhu Neexistuje (jediné) optimálne riešenie, ale súbor riešení s optimálnym „kompromisom“ = súbor riešení, pre ktoré nie je možné zlepšiť jedno kritérium bez zhoršenia iného 52
0/1 Problém s batohom Maximalizovať súčet (x (i) * p (i)) Obmedziť súčet (x (i) * w (i)) (2, 0) - vyberte 0: 4 1 2 0 xx (0, 1) Spätná väzba: Spätná väzba k zásadám ochrany osobných údajov
O projekte: Podmienky služby SlidePlayer