Evolúciós algoritmusok alkalmazása az adatelemzésben Simon Károly
BabesBolyai Tudományegyetem
[email protected]
1
Evolúciós számítástechnikai modellek Evolúciós számítástechnika: biológiai inspirációjú keresési és optimalizálási paradigma Alapötlet: a biológiai reprodukció, természetes kiválasztódás és evolúció modellezése → lehetséges megoldás populációk evolúciója Evolúciós számítástechnika → evolúciós számítástechnikai modellek → Evolúciós Algoritmusok Evolúciós Algoritmusok: Genetikus Algoritmusok, Evolúciós Programozás, Evolúciós Stratégiák, Genetikus programozás Evolúciós optimalizálás: komplex optimalizálási problémák megoldása evolúciós algoritmusok segítségével
2
Evolúciós Algoritmusok lehetséges megoldás populációk evolúciója biológiai inspirációjú keresési operátorok: kiválasztás, keresztezés, mutáció a lehetséges megoldások egy populáció egyedei, mindenik egyed a keresési tér egyegy pontját kódolja az egyedeket egy probléma specifikus rátermettségi (fitness) függvény segítségével hasonlítjuk össze a populáció fejlődése egy adott leállítási feltétel eléréséig tart a megoldás: az utolsó populáció, annak egy része, vagy a legnagyobb rátermettségi értékkel rendelkező egyed
3
Genetikus Algoritmusok az egyedeket kromoszómákkal kódoljuk Kódolási típusok: bináris: a kromoszómák bit sorozatok valós: problémaspecifikus kódolás Keresési operátorok: keresztezés (recombination): új egyedek létrehozása a szülők genetikai információjának kombinálásával mutáció: új egyed létrehozása egy egyed génállományának véletlenszerű megváltoztatásával kiválasztás a keresztezésre: a populációból mely egyedek lesznek kiválasztva mint szülők kiválasztás a cserére: mely egyedek kerülnek a következő generációba
4
Genetikus Algoritmusok A keresési folyamat: minden iterációnál egy új populáció jön létre → generációk néhány egyedet rátermettségük alapján kiválasztunk keresztezésre. a párokból származtatott egyedek egy közbeeső populációt alkotnak. a mutáció operátor módosítja ezeket az utódokat és egy új közbeeső populáció jön létre. az új generáció: a közbeeső populáció, és az eredeti populációból kiválasztott egyedek
5
Evolúciós optimalizálás
egy célfüggvény optimalizálása komplex optimalizálási problémák (NPteljes problémák, kombinatoriális optimalizálási problémák, nem konvex vagy nem deriválható célfüggvények, stb.) dinamikus, multikriteriális és multimodális optimalizálás
6
Evolúciós multimodális optimalizálás Multimodális optimalizálás: a standard genetikus algoritmusok a globális optimum fele konvergálnak sok valós probléma esetében több optimális vagy optimálist közelítő megoldás létezik néhány esetben célunk lehet minden optimum pont meghatározása (lokális optimumok) speciális evolúciós modelleket alkalmazhatunk
7
Evolúciós multimodális optimalizálás Klasszikus modellek: alpopulációk alkalmazása megosztott rátermettségi függvény példák klasszikus modellekre: niching, crowding, migration, speciation stb. Hátrányok: túl korai konvergencia különböző alpopulációkhoz tartozó egyedek keresztezése → érvénytelen megoldások optimum pontok közötti egyedek keresztezése → fölösleges műveletek, magas komplexitás Új evolúciós multimodális optimalizálási eljárások: Roaming, Genetic Chromodynamics, stb.
8
Genetic Chromodynamics egy új keresési és optimalizálási metaheurisztika több optimum pont meghatározására alapötlet: stabil alpopulációk kialakulásának elősegítése, és ezek fenntartása az alpopulációk különböző optimum pontok fele konvergálnak jellemzők: változó méretű populációk használata, „stepping stone” keresési mechanizmus, rövidtávú kölcsönhatások, „merging” (egyesítési) operátor mikropopulációs modelleket alkalmazhatunk bármilyen problémaspecifikus kodifikálás használata lehetséges
9
Alkalmazás az adatelemzésben: klaszterezés Központi probléma az adatelemzés keretein belül: az objektumok természetes csoportosulásának meghatározása → Klaszterezés (Clustering): egy adathalmaz elemeit csoportokba soroljuk egymáshoz való hasonlóságuk alapján egy csoportot egy prototípus vektor határoz meg, a klaszterközéppont. a klaszterezés folyamán két problémát kell megoldanunk: meg kell határoznunk a csoportok számát meg kell találnunk a középpontokat Statikus klaszterezési eljárások: a klaszterek száma előre meghatározott Dinamikus klaszterezési eljárások: az eljárás meghatározza a klaszterek számát is
10
GCalapú dinamikus klaszterezés
minden osztályt egy prototípus határoz meg, minden prototípust egy kromoszóma kódol a cél a természetes klaszterközéppontok fele konvergáló kromoszómák azonosítása a kezdeti populációt véletlenszerűen generáljuk a keresési folyamat során alkalmazott keresési operátorok: kiválasztás, keresztezés, mutáció és egybeolvasztás (merging)
11
Rátermettségi függvény Gauss típusú rátermettségi függvény: m
f (L j ) = ∑ e
−
xi − L j
2
σ j2
i =1
Rátermettség tájkép (fitness landscape)
12
GCDC Kölcsönhatási tartomány: minden egyed esetében meghatározunk egy kölcsönhatási tartományt a kölcsönhatási tartomány sugara egyedenként változhat Kiválasztás: mikropopulációs modellt alkalmazunk Keresztezés: a gének konvex rekombinációja Mutáció: a gének additív perturbációja Túlélés: a leszármazottat összehasonlítjuk a domináns szülővel, és a rátermettebb kerül be a következő generációba (direct survival competition)
13
GCDC Egybeolvasztás (merging): az alpopulációkon belül a kromoszómák egy idő után közel kerülnek egymáshoz amikor két kromoszóma közötti távolság egy adott küszöbérték alá csökken, az illető egyedeket egybeolvasztjuk Leállási feltétel: ha egy meghatározott számú lépés után nincsen változás a populációban, a keresési folyamat leáll az utolsó populációt képező egyedek lesznek a klaszterek középpontjai meghatározzuk a pontok hovatartozását
14
GCDC
Paraméterek: a kölcsönhatási tartomány sugara (interaction radius) az egybeolvasztási küszöbérték (merging distance) a mutáció léptéke (mutation step size) a rátermettségi függvény σj paramétere Adaptációs mechanizmusok: a kölcsönhatási tartomány adaptációja összefüggés bevezetése a kölcsönhatási tartomány mérete és a σj paraméter között → dinamikus rátermettségi függvény → dinamikus optimalizálás a mutáció léptéke és a kölcsönhatási tartomány mérete közötti összefüggés, az egybeolvasztási küszöbérték automatikus meghatározása csatolt cellás (linkcell) eljárás → a rövidtávú kölcsönhatások kezelése, kisebb komplexitás, új adaptációs technikák
15
Példa
Példa a GCDC eljárás működésére: a GCDC által meghatározott prototípusok 1, 10, 50 és 150 iteráció után.
16
Alkalmazás: Gene Expression Analysis Génkifejeződés (génexpresszió): soklépcsős folyamat, melynek során a génben rejlő információ (DNS) megjelenik valamilyen fehérjében, és ennek eredményeként a sejt szerkezete, funkciója jól mérhetően megváltozik Génexpressziós szintek mérése → microarray technológia → génexpressziós adatok (általában valós mátrixok: a sorok különböző géneknek, az oszlopok különböző feltételeknek vagy időpillanatoknak felelnek meg) Génexpresszió Analízis (Gene Expression Analysis): Cél: a génexpressziós adatok statisztikai elemzése → a gének klaszterezése az expressziós szintek függvényében Motiváció: a sejtek működésének megértése, a génkifejeződési szintek változásának megfigyelése betegségek, kezelések ideje alatt
17
A GCDC alkalmazás RCNS adathalmaz: 112 gén kifejeződési szintjei a patkány központi idegrendszerének kialakulása alatt, 9 időpillanatban a biológiailag értelmezhető felosztás 6 osztályt tartalmaz
18
Eredmények Elért eredmények:
az osztályok száma: 917 közeli klaszterek egybeolvasztása → 6 klaszter: a 3. és 5. klaszter: OK az 1. klaszter felosztása 3 kisebb klaszterbe a 2., 4. és 6. klaszter egybeolvasztása
Összehasonlítások: GCDC ↔ kmeans, linkage a klaszterezés pontosságának mérése: tévesztésmátrix (recall, precision → Fmeasure) method Fmeasure
kmeans
5.9009
GCDC
6.1781
Linkage
8.1396 19
