Bukaresti Politechnikai Egyetem év - ppt letöltés
Bukaresti Műszaki Egyetem 2008-2009. Tanév Automatikus tanulás Bukaresti Műszaki Egyetem 2008-2009. Tanév Adina Magda Florea http://turing.cs.pub.ro/inva_09 és curs.cs.pub.ro
Tanfolyam száma 9 Genetikai algoritmusok Bevezetés Alapvető séma Probléma modellezése Példa kiválasztás Rekombinációs TSP mutáció genetikai algoritmusokkal Párhuzamos megvalósítás AG 2
1. Bevezetés GA - USA, J. H. Holland (1975) Evolúciós algoritmusok - Németország, I. Rechenberg, H.-P. Schwefel (1975-1980) Genetikai programozás (1960-1980, 2000) J. Koza Optimalizálás Gazdasági modellek Ökológiai modellek A szociális rendszerek modelljei Tanulás 3
Bevezetés - beszámoló Az egyének populációján működik = lehetséges megoldások - alkalmazkodik az adaptáción (fitneszen) alapuló túlélés elvéhez. Minden generáció - a megközelítés új megközelítése A környezethez jobban alkalmazkodó egyedek populációjának evolúciója Természetes folyamatokat modellez: szelekció, rekombináció, mutáció, vándorlás, elhelyezkedés Az egyének népessége - párhuzamos keresés 4
2. Alapvető séma Generálja a kezdeti egyedek (gének) populációját A probléma ábrázolása A fitnesz funkció generálja a kezdeti egyedek (gének) populációját Értékeli a célfüggvényt A megállási kritérium teljesült? igen, nem a legjobb egyének Eredmény kiválasztása Crossover/Rekombináció Új populáció utódok szerzése Mutációs generációk 5
3. Probléma modellezés Kezdeti populáció Reprezentáció létrehozása - gén - egyén Meghatározza a populációban lévő egyedek számát Értékelési függvény létrehozása (cél) Kezdeti populáció (gének) véletlenszerűen létrehozott Selection Selection - a létező populációból származó gének egy részének kivonása definícióként minőség - az értékelési függvény Meghatározza a rekombinációra kiválasztott egyedeket és azt, hogy egy-egy egyed hány utódot hoz létre 6
Problémamodellezés Stop kritérium Többpopulációs GA megoldások, amelyek megfelelnek a nemzedékek számának kritériumának fennsík költségvetése a legjobb fitnesz számára Többpopulációs GA-k Jobb eredmények - alcsoportok Minden populáció külön fejlődik Az egyének több generáció után változnak 7
Kiválasztás (1) Első lépés: fitnesz-hozzárendelés - arányos hozzárendelés - rang-alapú feladat (2) Hatékony kiválasztás: a szülőket fitneszben választják ki az egyik algoritmus alapján: rulett-kerék kiválasztása sztochasztikus univerzális mintavétel stohastica) helyi szelekció (helyi szelekció) tornaválasztás (tornaválasztás) csonkaválasztás (csonka szelekció) 8
Utódok reintegrációja - ha kevesebb egyed vagy kevesebb gyermek fordul elő, akkor további egyéneket kell újból beilleszteni az új populációba. A szelekciós algoritmus meghatározza a reintegrációs sémát (általában) a globális reintegrációt - a teljes populációban. rulettkerék kiválasztása, sztochasztikus univerzális mintavétel, csonkaválasztási helyi visszahelyezés a helyi kiválasztáshoz 9
Crossover/Rekombináció A rekombináció új egyéneket hoz létre a szülők (szülők - párosodó populáció) információinak kombinálásával. Különböző rekombinációs sémák Egy lehetőség - véletlenszerű párosítás Megegyezik a genetikai keresztezéssel Az újonnan lakott egyedek PM-es százalékát választják ki és véletlenszerűen párosítják. Minden párhoz választanak egy keresztezési pontot (azonos vagy eltérő valószínűséggel). Információcsere zajlik a kettő között egyének a crossover 10. pont alapján
Mutáció kis véletlenszerű zavarokkal Utódok - mutáció Mutáció kis véletlenszerű zavarokkal A mutáció különféle formái, az ábrázolástól függően. Mutáció - feltárás vs kiaknázás Egyszerű séma Minden bitnek mutáció valószínűsége van 12
A mutáció és a szelekció hatása
4 Példa Számítsa ki az f (x1, x2,. Xn) függvény maximumát. Keresse meg x1, x2,. xn, amelynél az f maximális Használja a GA 15 értéket
Ábrázolás A változók méretezése 10n-nel megszorozva, ahol n a kívánt pontosság. Változó = egész szám (Var × 10 n) A változókat binárisan ábrázoljuk. A változókat összefűzzük - egyénileg. Ha előjelet akarunk: Adjunk hozzá egy értéket, és fordítsuk pozitívra vagy egy bitre a jel bináris ábrázolására Szürke kód 16
Számítás Kezdeti populáció véletlenszerű keresztválasztás Mutáció Minden egyént változóvá alakít: x1, x2,. xn Ellenőrizze az egyes emberek minőségét: f (x1, x2,. xn) Ellenőrizze, hogy a legjobb egyén minősége elég jó-e, ha abbahagyja, különben ugorjon a 2 17 oldalra
5. Kiválasztás Az első lépés a fitnesz (F) kiosztása a célfüggvényen alapuló közvetlen hozzárendelés VAGY mechanizmuson alapuló hozzárendelés A populációban minden egyén kap fitneszértéket A fitneszérték alapján a kiválasztás (S) egy kiválasztási séma szerint történik 18
Szelekció A reprodukció valószínűsége társítható az egyénhez - ez függ az egyén fitneszfüggvényének értékétől és a populáció többi egyedének fitneszfüggvényének értékétől. Ez a valószínűség felhasználható a szelekcióban 19
Kifejezések szelekciós nyomása: a legjobb egyén kiválasztásának valószínűsége az összes egyed átlagos szelekciós valószínűségéhez képest: az egyéni sokféleség elvesztésének utódai számának értéktartománya: az egyének aránya a populációban, amely nincs kiválasztva szelekciós intenzitás: a populáció átlagos fitnesze egy szelekciós módszer alkalmazása után szelekciós kovariancia: a populáció fitnesz-eloszlásának kovarianciája a szelekciós módszer alkalmazása után 20
A1. Arányos fitnesz-elosztás Minden génhez társított fitnesz Számolja ki a populáció átlagos alkalmasságát Minden egyes egyed az új populációban átmásolásra kerül az fitness fitneszben az átlagos fitnesz átlagos átlagos fitneszhez viszonyítva, 5.76, egyéni fitnesz 20.21 - 3-szor másolódik. az átlagot figyelmen kívül hagyják Új populáció - kisebb lehet Az új populációt véletlenszerűen kiválasztott egyének töltik meg a régi populációból 21
A2. Rangalapú fitnesz-hozzárendelés Az egyes egyénekhez rendelt alkalmasság csak a populációban lévő egyedek között elfoglalt pozíciójától függ.Az egyén pozíciója a populációban a Pos = 1 - a legkevésbé jó Pos = Nind - legjobb célfüggvénytől függ fitnesz 22
Fitness-hozzárendelés Nind rang alapján - egyedek száma a populációban Pos - az egyén helyzete a populációban (legrosszabb Pos = 1, legjobb Pos = Nind) SP - szelekciós nyomás (a legjobb egyén kiválasztásának valószínűsége a valószínűséghez képest az egyének átlagos kiválasztása) Lineáris rang Fitness (Pos) = 2 - SP + 2 * (SP - 1) * (Pos - 1)/(Nind - 1) A lineáris rang lehetővé teszi az SP értékeket (1.0, 2.0]. Az egyén rekombinációra történő kiválasztásának a megfelelősége (normalizált) a populáció teljes alkalmasságához képest 23
Rangalapú fitnesz-hozzárendelés Nemlineáris rang: Fitness (Poz) = Nind * X (Pos - 1)/ i = 1, Nind (X (i - 1)) X a polinom gyökereként kerül kiszámításra: 0 = (SP - Nind ) * X (Nind - 1) + SP * X (Nind - 2) +. + SP * X + SP A nemlineáris tartomány lehetővé teszi az SP értékeket [1.0, Nind - 2.0] értékben. SP magasabb. Az egyén rekombinációra való kiválasztásának valószínűsége fitnesz (normalizált) a populáció teljes fitneszéhez viszonyítva 24
Fitnesz-hozzárendelés lineáris rang alapján SP = 2 0.2 SP = 1,5 0,5.1,5 Fitness-hozzárendelés lineáris rang és nemlineáris rang 25
Rangalapú fitnesz-hozzárendelés az arányos hozzárendeléshez képest: Kerülje el a stagnálás problémáját, ha a választási nyomás túl alacsony vagy az idő előtti konvergencia túl szűk keresési területet eredményez. Könnyű módot nyújt a választási nyomás szabályozására Általában még erősebb 26
Fitnesz hozzárendelés rang alapján Tulajdonságok Kiválasztás intenzitása: SelIntRank (SP) = (SP-1) * (1/sqrt ()). A sokféleség elvesztése: LossDivRank (SP) = (SP-1)/4. Kiválasztási kovariáns: SelVarRank (SP) = 1 - ((SP-1) 2/) = 1-SelIntRank (SP) 2. 27.
S1. Kiválasztás "rulettkerék-választás" vagy "sztochasztikus mintavétel cserével" alapján 11 személy, lineáris rang és SP = 2 6 véletlenszám (egyenletesen elosztva 0,0 és 1,0 között): 0,81, 0,32, 0,96, 0,01, 0,65, 0,42. Egyéni szám 1 2 3 4 5 6 7 8 9 10 11 Fitneszérték 2,0 1,8 1,6 1,4 1,2 1,2 1,0 0,8 0,6 0,4 0,2 0,0 Valószínűleg. kiválasztás 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. Sztochasztikus univerzális mintavétel A mutatókat azonos távolságra helyezzük el egy intervallumon [0.1] - ahány mutatót választunk ki, NPointer - kiválasztandó egyedek száma A mutatók közötti távolság 1/Npointer Az első mutató helyzetét véletlenszerű szám adja meg a [0.1/NPointer] tartományban. 6 személy kiválasztásához a mutatók közötti távolság 1/6 = 0,167. 1 véletlenszerű szám a [0, 0,167] tartományban: 0,1. 1, 2, 3, 4, 6, 8 29
S3. Helyi kiválasztás Minden egyén a szomszédságban van. Népességet strukturáló szomszédság - egyének csoportja, amely képes újrakombinálni (potenciális) lineáris szomszédság: teljes és félgyűrű
Ezután minden kiválasztott egyénhez meghatároz egy szomszédságot. Helyi kiválasztás A populáció első felét véletlenszerűen választják ki (vagy egy szelekciós algoritmus segítségével - sztochasztikus vagy versenymintavétel). Ezután minden kiválasztott egyénhez meghatároz egy szomszédságot. Válasszon egy másik személyt a környéken történő rekombinációhoz (legjobb, arányos vagy véletlenszerű fitnesz). 32
Helyi kiválasztás Elszigetelési távolság az egyének között Minél kisebb a környék, annál nagyobb az elszigeteltség Átfedő szomszédságok - jellemző átvitel történik A szomszédság mérete meghatározza a terjedés sebességét Gyors terjedés és a nagy változatosság fenntartása Nagy változatosság - megakadályozza az idő előtti konvergenciát 33
S4. A bajnokság kiválasztása A populációban szereplő túrák számát véletlenszerűen választják ki, és a legjobb egyént választják ki szülőnek. A folyamat megismétlődik, hogy hány egyént akarunk kiválasztani. A verseny méretének paramétere a Tour. Túra - értékek 2 . Nind között A túra és a kiválasztás intenzitása közötti kapcsolat A verseny nagysága 1 2 3 5 10 30 Kiválasztási intenzitás 0,56 0,85 1,15 1,53 2,04 A populáció átlagos értéke a kiválasztási módszer alkalmazása után 34
A verseny kiválasztása A kiválasztás intenzitása: SelIntTour (Tour) = sqrt (2 * (log (Tour) -log (sqrt (4.14 * log (Tour)))))) A sokszínűség elvesztése: LossDivTour (Tour) = Tour - (1/(Tour) -1)) - Tour - (Tour/(Tour-1)) (A Tour = 5 miatt a lakosság körülbelül 50% -a elveszett). Kiválasztási kovariátum: SelVarTour (Tour) = 1- 0,096 * log (1 + 7,11 * (Tour-1)), SelVarTour (2) = 1-1/ 35
6. Crossover/rekombináció Új egyedeket hoz létre a szülői információk rekombinálásával. Bináris reprezentációk bináris többpontos egyenletes Egész/valós reprezentációk diszkrét valós lineáris köztes 36
6.1 Bináris rekombináció Véletlenszerűen kiválasztott keresztező pozíció 2 utód fordul elő 37
Bináris rekombináció Egyedi példa 1: 0 1 1 1 0 0 1 1 0 1 0 keresztezési helyzet = 5 2 új egyed jön létre: utódok 1: 0 1 1 1 0 | 1 0 0 1 0 1 utód 2: 1 0 1 0 1 | 0 1 1 0 1 0 38
6.2 Rekombinációs többpontos m crossover pozíciók ki egyéni 1: 0 1 1 1 0 0 1 1 0 1 0 egyén 2: 1 0 1 0 1 1 0 0 1 0 1 pos. kereszt (m = 3) 2 6 10 utód 1: 0 1 | 1 0 1 1. | 0 1 1 1. | 1 utód 2: 1 0 | 1 1 0 0 | 0 0 1 0 | 0 39
6.3 Egységes rekombináció Általánosítja az egyszerű bináris és többpontos Crossover maszkot - ugyanolyan méretű, mint az egyén; véletlenszerűen létrehozva, és a maszkban található bitek paritása jelzi, hogy melyik szülő adja az utódokat, egyenként 1: 0 1 1 1 0 0 1 1 0 1 0 egyenként 2: 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 maszk 2: 1 0 0 1 1 1 0 0 1 0 1 (fordítva az 1. maszkhoz) utód 1: 1 1 1 0 1 1 1 1 1 1 1 utód 2: 0 0 1 1 0 0 0 0 0 0 0 Spears és De Jong (1991) - paraméterezés 40 valószínűség társításával
6.4 Valódi diszkrét rekombináció Diszkrét rekombináció Valódi értékek cseréje az egyének között. egyén 1: 12 25 5 egyén 2: 123 4 34 Minden értéknél véletlenszerűen, azonos valószínűséggel választják ki a közreműködő szülőt 1: 2 2 1 minta 2: 1 2 1 rekombináció után: utódok 1: 123 4 5 utódok 2: 12 4 5 41
Diszkrét valós rekombináció Diszkrét rekombináció Lehetséges utódpozíciók bármilyen értékkel (bináris, valós vagy szimbólumok) használhatók. 42
Közvetlen valós rekombináció Csak valós értékek esetén A szülők értékei köré választott utódok értékei Szabály: utód = szülő 1 + Alpha (szülő 2 - szülő 1), ahol az Alpha egy véletlenszerűen kiválasztott méretezési tényező a [-d, 1 + d] tartományban . d = 0 vagy d> 0. Jó érték d = 0,25. Az utódok mindegyik értéke annak az eredménye, hogy a szülőket egyesítettük egy új alfával minden 43 változóhoz
Közbenső valós rekombinációs egyed 1: 12 25 5 egyed 2: 123 4 34 Alfa értékek: 1. minta: 0,5 1,1 -0,1 minta 2: 0,1 0,8 0,5 Új egyedek (utód = szülő 1 + alfa (szülő 2 - szülő 1) utód 1: 67,5 1,9 2,1 utód 2: 23,1 8,2 19,5 44
Valódi köztes rekombináció Az utódok értéktartománya a szülőkéhez viszonyítva Az utódok megoszlása a köztes rekombináció után 45
Valódi lineáris rekombináció Lineáris rekombináció A közbensőhöz hasonlóan, de csak egy alfát használunk. egyén 1: 12 25 5 egyén 2: 123 4 34 Az alfa értékek: 1. minta: 0,5 minta 2: 0,1 Új egyedek: utódok 1: 67,5 14,5 19,5 utódok 2: 23,1 22,9 7,9 46
Lineáris valós rekombináció Lineáris rekombináció 47
7. Mutáció rekombináció után - a leszármazottak mutációja A leszármazottak értékeit inverzióval (binárisan) vagy kis véletlenszerű értékek hozzáadásával (mutációs lépés) mozgatjuk, alacsony valószínűséggel. A mutáció valószínűsége fordítottan arányos az egyedek méretével. Minél hosszabb egyedünk van a mutáció valószínűsége alacsonyabb 48
7.1 Bináris mutáció Cserélje ki a bináris értékeket Minden egyes egyed számára véletlenszerűen kiválasztja az áthelyezendő bitet 11 érték, a 4. bitet a mutáció után az 1. mutáció előtt 49
7.2 Mutáció valós értékekkel Mutációs hatás Lépés mérete - nehéz; az evolúció során változhat Kicsi - jó, lassú; nagy - gyorsabb mutációs operátor: mutált változó = változó ± tartomány · delta (+ vagy - azonos valószínűséggel) tartomány = 0,5 * változó tartomány delta = összeg (a (i) 2-i), a (i) = 1 valószínűséggel 1/m, különben a (i) = 0,50
8. A GA használata: - 0/1-es probléma hátizsák - TSP 51
8.1 0/1 Hátizsákprobléma Sok olyan tárgyat adnak meg, amelyek mindegyikének van súlya/súlya w (i) és értéke/nyeresége p (i). Határozza meg az egyes típusú objektumok számát, amelyeket a gyűjteménybe be kell vonni a.i. a súlynak kisebbnek kell lennie, mint egy adott W érték, és a teljes értéknek maximálisnak kell lennie. 0/1 feladat hátizsák - 0 vagy 1 objektum minden típusból. Multiobjektív optimalizálási probléma: maximalizálja a profitot és minimalizálja a súlyt Nincs (egyetlen) optimális megoldás, de optimális "kompromisszummal" rendelkező megoldások = olyan megoldások halmaza, amelyeknél az egyik kritérium nem javítható anélkül, hogy a másik rosszabbodna 52
0/1 Hátizsák probléma Összeg maximalizálása (x (i) * p (i)) Összeg korlátozása (x (i) * w (i)) (2, 0) - válassza 0: 4 1 2 0 xx (0, 1) Visszajelzés: Adatvédelmi irányelvek visszajelzése
A projektről: SlidePlayer szolgáltatási feltételek