1 Egy kis biológia A DNS Az evolúció A kanonikus genetikus algoritmus 11

´k Tartalomjegyze 1 Egy 1.1. 1.2. 1.3.

kis biol´ ogia A DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kromosz´oma, g´en, ¨or¨okl˝od´es . . . . . . . . . . . . . . . . . . . . . . Az evol´ uci´o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 A kanonikus genetikus algoritmus

5 5 6 8 11

3 A genetikus algoritmusok konvergenci´ aja 3.1. S´emaelm´elet . . . . . . . . . . . . . . . . . . . A szelekci´o hat´asa a s´em´ara . . . . . . A crossover hat´asa a s´em´ara . . . . . . A mut´aci´o hat´asa a s´em´ara . . . . . . 3.2. A genetikus algoritmusok mint Markov-l´ancok

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

17 17 18 19 20 21

4 A genetikus algoritmusok konvergencia-ideje

29

5 Szelekci´ o, keresztez´ es, mut´ aci´ o

31

6 Oszt´ alyoz´ as genetikus algoritmusokkal

33

7 P´ arhuzamos genetikus algoritmusok

35

8 M´ as evolut´ıv algoritmusok 8.1. Evol´ uci´os strat´egi´ak . . . . . . . . . . . 8.1.1. Az (1,1)-ES konvergenci´aja . . . 8.2. Evol´ uci´os programoz´as . . . . . . . . . 8.3. Genetikus programoz´as . . . . . . . . . 8.3.1. Line´aris genetikus programoz´as

37 37 37 38 38 38

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

9 Alkalmaz´ asok 39 9.1. F¨ uggv´enyoptimiz´al´as kanonikus genetikus algoritmussal . . . . . . . 39 9.1.1. A Gray-k´od . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1

´k Tartalomjegyze

2 9.2. 9.3. 9.4. 9.5. 9.6. 9.7. 9.8.

F¨ uggv´enyoptimiz´al´as val´os ´abr´azol´assal . . . . . . . . Nemline´aris programoz´as . . . . . . . . . . . . . . . . T´erk´ep- vagy gr´afsz´ınez´esi probl´ema . . . . . . . . . . Az utaz´o u ¨gyn¨ok probl´em´aja . . . . . . . . . . . . . . SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . A 8 kir´alyn˝o probl´em´aja . . . . . . . . . . . . . . . . Strat´egi´ak keres´ese genetikus algoritmusokkal . . . . 9.8.1. A fogoly-dilemma . . . . . . . . . . . . . . . . 9.8.2. Tic-tac-toe . . . . . . . . . . . . . . . . . . . . 9.8.3. A ragadoz´o ´es zs´akm´any probl´em´aja . . . . . 9.9. Klaszterez´es genetikus algoritmusokkal . . . . . . . . 9.9.1. K-k¨ozpont´ u klaszterez´es . . . . . . . . . . . . 9.9.2. Gr´af-klaszterez´es . . . . . . . . . . . . . . . . Normaliz´alt v´ag´ason alapul´o gr´af-klaszterez´es

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

46 46 46 47 50 54 57 57 57 57 57 58 59 61

˝ Bevezeto A szerz˝o – s ez´altal e jegyzet – semmilyen szempontb´ol nem t¨orekszik teljess´egre.

3

4

´k Tartalomjegyze

1 ´ gia Egy kis biolo

1.1.

A DNS

Egy organizmus l´etrehoz´as´ahoz sz¨ uks´eges teljes utas´ıt´ashalmazt genomnak nevezz¨ uk. A genom f˝o modellj´et k´epezi minden sejtszerkezetnek ´es sejttev´ekenys´egnek a sejt vagy a teljes szervezet eg´esz ´elettartam´ara. A genom dezoxiribonukleinsav-sz´alakb´ol (r¨oviden DNS) ´es a hozz´a tartoz´o protein molekul´akb´ol ´all. A DNS a sejtmagban tal´alhat´o, tov´abb´a az organizmus minden sejtje ugyanazon DNS molekul´akat tartalmazza, viszont minden sejtt´ıpus m´as ´es m´as proteint gener´al. A proteinek az el˝ol´enyek els˝odleges alkot´oielemei, olyan enzimek, melyek lehet˝ov´e teszik az ´elethez sz¨ uks´eges k´emiai reakci´okat. Ezek a proteinek aminosavakb´ol ´ep¨ ulnek fel. Egy egyed genetikai k´odj´at a DNS molekul´ak tartalmazz´ak. A DNS alakja egy ,,sodort l´etra”, azaz k´et, egym´assal ,,p´arhuzamos” k¨ot´esekkel ¨osszekapcsolt sz´al. Alkot´oelemei a nukleotid´ak, melyek h´arom r´eszb˝ol ´allnak. Ezek f˝o komponense a b´azismolekula, mely k´etf´ele lehet: purin [adenin (A) vagy guanin (G)] vagy piramidin molekula [citozin (C) vagy thimin (T)]. A k´et sz´al k¨oz¨otti k¨ot´es hidrog´en-k¨ot´es, azaz gyenge, ami k´et b´azist k¨ot ¨ossze: egy purin ´es egy piramidin molekul´at. A lehets´eges k¨ot´esek teh´at G–C ´es T–A, illetve ezek ford´ıtottjai. Ebb˝ol l´atszik, hogy az egyik DNS sz´al a m´asik komplementere, ez´ert ha ismert az egyik, akkor a m´asik egy´ertelm˝ uen fel´ep´ıthet˝o. Sejtoszt´od´askor a spir´al kett´ev´alik – egyik sz´al megy a l´etrej¨ov˝o egyik sejtbe, a m´asik sz´al a m´asikba – majd ott, a b´azisoknak megfelel˝oen, l´etrehozz´ak a maguk kieg´esz´ıt˝o sz´alj´at. Az egym´ast nem ´atfed˝o nukleotid-h´armasokat kodonoknak nevezz¨ uk. Minden kodon megfelel egy aminosavnak, azaz minden kodon egy aminosavat k´odol (ez ford´ıtva nem igaz, t¨obb k¨ ul¨onb¨oz˝o kodon is k´odolhatja egyazon aminosavat). K´etf´ele kodon l´etezik. Az u ´n. stop-kodon nem k´odol semmit, ez az aminosavszekvencia, azaz a protein v´eg´et jel¨oli. Az ¨osszes t¨obbi egy-egy aminosavat k´odol. A dolgok azonban tov´abb bonyol´odnak. A DNS-ben vannak olyan r´eszek, melyek 5

6

´ gia 1. fejezet. Egy kis biolo

1.1. ´abra. A DNS leegyszer˝ us´ıtett szerkezete nem k´odolnak semmit; ezeket intronoknak nevezz¨ uk (a DNS aminosavba val´o lek´epez´esekor ezek a r´eszek kiesnek). A jelent´essel b´ır´o szekvenci´akat exonoknak nevezz¨ uk (vigy´azat, nem ¨osszet´evesztend˝o az axonnal ). Az aminosav-szekvenci´aba val´o lek´epez´es k´et l´ep´esben t¨ort´enik: az els˝o l´ep´esben a DNS ´at´ır´odik egy u ´n. mRNS (m = messenger) molekul´aba, amibe m´ar csak az exonok ker¨ ulnek; a m´asodik l´ep´es az mRNS aminosav-szekvenci´aba val´o lek´epez´ese.

1.2.

Kromosz´ oma, g´ en, ¨ or¨ okl˝ od´ es

A kromosz´ oma egy DNS molekul´at jelent. Azokat az el˝ol´enyeket, melyek a genomot k´et p´eld´anyban tartalmazz´ak, azaz minden kromosz´oma k´etszer szerepel, diploid egyedeknek, m´ıg a genomot egy p´eld´anyban tartalmaz´o egyedeket haploid egyedeknek nevezz¨ uk. Az ember sejtmagja p´eld´aul 23 p´ar kromosz´om´at tartalmaz: 22 p´ar autosz´om´at ´es egy X vagy Y kromosz´omap´art. Egy norm´alis n˝o sejtmagja 22 p´ar autosz´om´at ´es egy p´ar X kromosz´om´at, m´ıg egy norm´alis f´erfi´e ugyancsak 22 p´ar autosz´om´at ´es egy XY kromosz´omap´art tartalmaz. A g´enek a kromosz´om´akon, azaz a DNS molekul´akon helyezkednek el, ´es a kromosz´oma egy bizonyos r´esz´et jelentik. A g´enek hat´arozz´ak meg az egyed tulajdons´agait (pl. sz˝oke, barna; k´ekszem˝ u, z¨oldszem˝ u, stb.). A g´en tulajdonk´eppen csak egy kezdeti ´es egy v´egs˝o poz´ıci´ot jelent, azaz csak a tulajdons´ag hely´et hat´arozza meg. Egy g´en megjelen´esi form´ait all´eloknak nevezz¨ uk, vagy u ´gy is mondhatjuk, hogy az all´el a g´en fenot´ıpusa. ¨ okl˝od´es alatt bizonyos tulajdons´agok ´atvitel´et ´ertj¨ Or¨ uk a sz¨ ul˝okr˝ol az

´ cio ´ 1.3. Az evolu

7

ut´odokra. Az ¨or¨okl˝od´es egys´eg´enek a g´ent tekintj¨ uk. K´etf´ele ¨or¨okl˝od´esr˝ol besz´elhet¨ unk, att´ol f¨ ugg˝oen, hogy a g´enek milyen t´ıpus´ u kromosz´om´an helyezkednek el. ´ Az autoszom´alis ¨or¨okl˝od´es felfedez˝oje Gregor Mendel, egy Agoston-redi szerzetes volt. Mendel Morvaorsz´agban sz¨ uletett a XIX. sz´azadban, amely akkor az Osztr´ak-Magyar Monarchia r´esz´et k´epezte. Az iskola elv´egz´ese ut´an a br¨ unni Szent ´ Tam´as Agoston-rendi kolostorba l´epett be. A kolostor vezet˝oi B´ecsbe k¨ uldt´ek megszerezni a tan´ıt´oi bizony´ıtv´anyt, de Mendel megbukott a vizsg´akon, ´es visszat´ert Br¨ unnbe. Ekkor kezdte el ny¨ov´enykeresztez´esi k´ıs´erleteit, ami´ert ma ˝ot nevezz¨ uk a genetika, mint tudom´any megalapoz´oj´anak. Statisztikai adatokb´ol kiindulva t¨orv´enyszer˝ us´egeket fedezett fel a tulajdons´agok ´at¨or¨ok´ıt´es´eben a sz¨ ul˝ot˝ol a lesz´armazottra. A manaps´ag is haszn´alt domin´ans ´es recessz´ıv kifejez´eseket Mendel haszn´alta el˝osz¨or. A nemi ¨or¨okl˝od´est Thomas Hunt Morgan kutatta, kinek eredm´enyeit 1934ben Nobel-d´ıjjal jutalmaztak. A crossover (´atkeresztez´es) felfedez´ese is Morgan nev´ehez f˝ uz˝odik. (A tov´abbiakban mindenhol az angol kifejez´est fogom haszn´alni, mivel magyarul t´ uls´agosan hasonl´ıt a keresztez´es sz´ohoz, amely m´ast jelent, r´aad´asul 13 bet˝ ub˝ol ´all.) Morgan szerint mei´oziskor (= cs´ırasejtek oszt´od´asa) a homol´og kromosz´om´ak p´arba rendez˝odnek, valahol megt¨ornek, ´es r´eszeket cser´elnek ki egym´as k¨oz¨ott u ´gy, hogy genetikai anyag nem veszl˝odik el. A crossover mellett a m´asik fontos genetikai m˝ uvelet a mut´aci´o, amely az evol´ uci´os v´altoz´as alapvet˝o forr´as´at k´epezi. A mut´aci´o a kromosz´oma egy r´esz´enek megv´altoz´as´at jelenti. A DNS molekul´ak nem teljesen stabilak, vagyis minden b´azisp´ar rendelkezik egy bizonyos mut´aci´os val´osz´ın˝ us´eggel. A mut´aci´o k´etf´ele lehet: spont´an vagy el˝oid´ezett. Az el˝obbi bek¨ovetkez´es´enek sokkal kisebb a val´osz´ın˝ us´ege, de evol´ uci´os szempontb´ol sokkal fontosabb a m´asodikn´al. A v´altoz´as milyens´eg´et tekintve, sokf´ele mut´aci´o l´etezik. Csak a pont-mut´aci´okat figyelembe v´eve, azaz melyek egyetlen b´azisban v´altoztatj´ak meg a DNS-szekvenci´at, m´aris h´arom t´ıpusr´ol besz´elhet¨ unk: b´azis-helyettes´ıt´eses, b´azis-hozz´aad´asos, illetve b´azis-t¨orl´eses, ´es m´eg ezek sem az oszt´alyoz´asi fa levelei! Azonban ne gondoljuk, hogy olyan egyszer˝ u dolog mut´aci´onak bek¨ovetkeznie a g´enekben. A sejtek ugyanis bonyolult repair-mechanizmusokkal rendelkeznek, melyek megjav´ıtj´ak a s´er¨ ult DNS-t, megakad´alyozva ezzel a v´altoz´ast. M´ıg crossover minden esetben t¨ort´enik, azaz val´osz´ın˝ us´ege 1, mut´aci´o bek¨ovetkez´es´enek val´osz´ın˝ us´ege enn´el nagys´agrendekkel kisebb.

1.3.

Az evol´ uci´ o

A darwini evol´ uci´o, vagyis a term´eszetes kiv´alaszt´od´as vagy szelekci´o elm´elete szerint egy popul´aci´o azon egyedei maradnak fenn nagyobb val´osz´ın˝ us´eggel, melyek

8

´ gia 1. fejezet. Egy kis biolo

bizonyos k¨ornyezeti felt´eteleket tekintve r´atermettebbek a t¨obbiekn´el. Darwin nem tudott az ¨or¨okl˝od´esi elvekr˝ol, viszont egy olyan ¨or¨okl˝od´est felt´etelezett, ahol az ¨or¨okl¨ott tulajdons´agok a folyad´ekok elegy´ıt´es´ehez hasonl´oan keverednek az ut´odokban. A term´eszetes szelekci´ot Michalewicz a k¨ovetkez˝o p´eld´aval magyar´azza el ([Mic96, p.14]): ,, [. . . ] Vegy¨ uk p´eld´aul a nyulakat: minden id˝opillanatban l´etezik egy ny´ ulpopul´aci´o. A nyulak k¨oz¨ ul n´eh´any gyorsabb ´es okosabb mint a t¨obbi. Ezeket a gyors ´es okos nyulakat sokkal kisebb val´osz´ın˝ us´eggel kapj´ak el ´es eszik meg a r´ok´ak, ez´ert sokuk fennmarad, hogy azt csin´alhassa, amit a nyulak a legjobban tudnak: m´eg t¨obb nyulat. Term´eszetesen n´eh´any lass´ ubb ´es but´abb ny´ ul is fenn fog maradni, kiz´ar´olag az´ert, mert szerencs´esek. A r´ok´akat t´ ul´el˝o ny´ ulpopul´aci´o elkezd szaporodni. Ez a nyulak genetikai anyag´anak kever´ek´ehez vezet: n´eh´any lass´ u ny´ ul gyors ny´ ullal p´arosodik, n´eh´any gyors ny´ ul gyors ´ ny´ ullal, n´eh´any okos ny´ ul buta ny´ ullal, ´es ´ıgy tov´abb. Es mindennek a tetej´ebe a term´eszet n´eha bedob egy ’vadnyulat’ a genetikus anyag mut´aci´oja r´ev´en. A sz´armaz´o kisnyulak (´atlagban) gyorsabbak ´es okosabbak lesznek, mint az el˝oz˝o popul´aci´oban l´ev˝ok, mivel a gyorsabb ´es okosabb sz¨ ul˝ok ´elt´ek t´ ul a r´ok´akat. (Szerencs´ere a r´ok´ak is hasonl´o folyamaton mennek kereszt¨ ul – m´ask¨ ul¨onben a nyulak t´ ul gyorsakk´a ´es okosokk´a v´aln´anak ahhoz, hogy a r´ok´ak elkapj´ak ˝oket.)” Az evol´ uci´o kezdetekor a F¨old¨on csak egysejt˝ u ´el˝ol´enyek voltak. Az evol´ uci´o k¨ovetkezt´eben minden ´el˝ol´eny alapegys´ege a sejt. A v´ırusok persze nem sejtekb˝ol ´allnak, azonban fennmarad´asuk f¨ ugg a sejtekt˝ol, mert csak azokat ,,megfert˝ozve” k´epesek a reprodukci´ora. M´ara a l´etez˝o fajok sz´ama 5 ´es 50 milli´o k¨oz´e tehet˝o. ´ Erdekes megjegyezn¨ unk, hogy a legn´epszer˝ ubb gerincesek (halak, h¨ ull˝ok, k´et´elt˝ uek, madarak, eml˝os˝ok) ezeknek k¨or¨ ulbel¨ ul 3%-´at teszik ki. A nemi rekombin´aci´o, azaz a p´arosod´as feltehet˝oleg sz¨ uks´eges el˝ofelt´etele volt a t¨obbsejt˝ u ´el˝ol´enyek megjelen´es´enek. Vagyis a p´arosod´as ,,feltal´al´asa” a genetikai k´odok kombin´aci´oj´anak nagyobb sikere miatt t¨ort´ent.

2 A kanonikus genetikus algoritmus

A ,,genetikus algoritmusok” elnevez´es els˝ore furcs´anak t˝ unhet az olvas´onak. Az elnevez´es abb´ol ad´odik, hogy ezek az algoritmusok megpr´ob´alj´ak szimul´alni azt a folyamatot, ami a term´eszetben j´atsz´odik le: tulajdons´agok ´atvitele a sz¨ ul˝or˝ol az ut´odra, ezen tulajdons´agok keresztez˝od´ese, v´altoz´asa ´es term´eszetes kiv´alaszt´od´as. El˝osz¨or az alapalgoritmus ker¨ ul bemutat´asra, majd k´es˝obb l´atni fogjuk, hogy ezek val´os matematikai alapokra ´ep¨ ulnek ´es val´oban hat´ekonyak (a hat´ekonys´agr´ol b˝ovebben ugyancsak k´es˝obb lesz sz´o). N´eh´any tov´abbi egyszer˝ u fogalom ´ertelmez´ese, melyekkel a tov´abbiakban sokszor fogunk tal´alkozni: Egy popul´aci´ot egyedek alkotnak, az egyedeket pedig a kromosz´om´ajuk hat´arozza meg. A kromosz´om´ak line´aris szekvenci´aba rendezett g´enekb˝ol ´ep¨ ulnek fel. A keresztez´es egys´ege a rekon, a v´altoz´ekonys´ag, mut´aci´o egys´ege a muton. A genetikus algoritmusokkal val´o foglalkoz´as kezdetei az 1950-es ´evek elej´ere tehet˝o, mikor n´eh´any biol´ogus a sz´am´ıt´og´ep seg´ıts´eg´evel biol´ogiai rendszereket pr´ob´alt szimul´alni. A tulajdonk´eppeni genetikus algoritmus John Holland nev´ehez f˝ uzodik, aki munk´ass´ag´aval az eg´esz vil´ag sz´am´ara ismertt´e tette azt. Ezek az algoritmusok a megold´as bin´aris stringk´ent val´o reprezent´aci´oj´ara ´es a Holland ´altal fel´all´ıtott s´emaelm´elet (Schema Teorem) alapjaira ´ep¨ ulnek. A genetikus algoritmusok a probabilisztikus algoritmusok oszt´aly´aba tartoznak, a determinisztikus ´es sztochasztikus keres´es elemeit egyes´ıtik, ez´ert sokkal hat´ekonyabbak, mint a determinisztikus keres´esi met´odusok. Olyan sztochasztikus algoritmusok, melyek keres´esi met´odusai egy biol´ogiai jelens´eget modelleznek. Glob´alis optimiz´al´o algoritmusok, melyek egy kezdeti popul´aci´ob´ol kiindulva – mely potenci´alis megold´asokat tartalmaz – eljutnak egy v´egs˝o popul´aci´ohoz, melyben az egyedek ´ert´eke, melyet a r´atermetts´egi f¨ uggv´eny fog megadni, az optimumhoz fog konverg´alni. A megold´ast k´odolni kell annak ´erd´ek´eben, hogy majd a genetikus oper´atorok alkalmaz´as´aval (keresztez´es, mut´aci´o) u ´jabb egyedek ”sz¨ ulethessenek”. Minden megold´ashoz hozz´arendel¨ unk egy sorozatot, mely az illet˝o megold´ast fogja k´odolni. Ez a sorozat lesz a megold´as genot´ıpusa, m´ıg maga 9

10

2. fejezet. A kanonikus genetikus algoritmus

a megold´as a fenot´ıpus. A sorozat lesz az egyed kromosz´om´aja ´es a benne lev˝o bet˝ uk, sz´amok a gen´eket reprezent´alj´ak. (A genetikus algoritmusok csak haploid egyedekkel foglalkoznak, vagyis minden egyed egy kromosz´om´aval rendelkezik, ´es az egyedeket egyed¨ ul a kromosz´om´ajuk hat´arozza meg, vagyis az egyed ekvivalens a kromosz´om´aval. Ez´ert sok esetben az egyed helyett kromosz´om´at mondunk vagy ford´ıtva.) Az eml´ıtett kezdeti popul´aci´ob´ol kiv´alogatunk bizonyos egyedeket valamilyen felt´etel szerint, majd ezekb˝ol egy u ´j popul´aci´ot hozunk l´etre. Ebben az u ´j popul´aci´oban egyes egyedp´arokat keresztez¨ unk, egyes egyedeket pedig mut´aci´onak vet¨ unk al´a. A keresztez´es a k¨ovetkez˝o m´odon t¨ort´enik: legyen (a1 , a2 , a3 , a4 , a5 ) ´es (b1 , b2 , b3 , b4 , b5 ) k´et egyed, melyet kiv´alasztottunk keresztez´esre, a keresztez´es egys´ege (rekon) pedig legyen 2. Ekkor a keletkezett k´et lesz´armazott (b1 , b2 , a3 , a4 , a5 ) ´es (a1 , a2 , b3 , b4 , b5 ) lesz. A mut´aci´o a kromosz´om´an bel¨ ul egy vagy t¨obb g´ent megv´altoztat, vagyis mut´al. Legyen (a1 , a2 , a3 , a4 , a5 ) egy egyed a popul´aci´ob´ol, melyet kiv´alasztottunk mut´aci´ora, a mut´aci´o egys´ege (muton) legyen 1, a mut´aci´o pozici´oja 3. Ekkor az (a1 , a2 , a∗3 , a4 , a5 ) lesz´armazottat kapjuk. A keresztez´es ´es mut´aci´o befejezt´evel megkaptuk az u ´j popul´aci´ot. Most az u ´j popul´aci´o lesz a kezdeti popul´aci´o, ´es u ´jb´ol elv´egezz¨ uk a fent le´ırt algoritmust. Ezt addig ism´etelj¨ uk, am´ıg a meg´allasi felt´etel nem teljes¨ ul, vagy el˝ore meghat´arozott k sz´amszor hajtjuk v´egre. (Az ut´obbi esetben k-t a gener´aci´ok sz´am´anak nevezz¨ uk.) A keresztez´es alkalmaz´as´anak c´elja az, hogy egyes egyedek tulajdons´agait ¨otv¨ozve u ´jabb, esetleg r´atermettebb egyedeket hozzunk l´etre, m´ıg a mut´aci´o c´elja az egyedek, a popul´aci´o friss´ıt´ese, vagyis v´altozatoss´ag bevitele a popul´aci´oba. A keresztez´es ´es a mut´aci´o v´egrehajt´as´ahoz sz¨ uks´eg¨ unk van k´et val´osz´ın˝ us´egi ´ert´ekre: a keresztez´es ´es a mut´aci´o val´osz´ın˝ us´eg´ere, az´ert, hogy az egyedeknek csak bizonyos sz´azal´ek´at vess¨ uk al´a ezen genetikai ”m˝ uveleteknek”. A legismertebb algoritmus a rulettker´ek m´odszer. Nev´et a szerencsej´at´ekr´ol kapta, ´es a m´odszert u ´gy kell elk´epzeln¨ unk mint egy rulettkereket, ahol a szeletek m´erete ar´anyos az egyedek r´atermetts´eg´evel. Ez´ert az ebben az algoritmusban haszn´alt szelekci´os met´odust r´atermetts´eg-ar´anyos szelekci´onak nevezz¨ uk. Az algoritmus le´ır´as´ahoz sz¨ uks´eg¨ unk van egy r´atermetts´egi f¨ uggv´enyre ´es a m´ar eml´ıtett k´et val´osz´ın˝ us´egi ´ert´ekre. Legyen P = {v1 , v2 , . . . , vn } popul´aci´o, ahol n a popul´aci´o m´erete, valamint vi , i = 1, 2, . . . , n az egyedek. Legyen tov´abb´a f(vi ) a vi egyed r´atermetts´egi ´ert´eke, ahol f() a r´atermetts´egi f¨ uggv´eny.

11

0.194

0.16 0.086

0.12 0.086

0.194

0.16

2.1. ´abra. Egy k´ epzeletbeli rulettker´ ek. A szeletek m´erete (k¨or´ıvek hossza, k¨orcikkek ter¨ ulete) v´altoz´o, vagyis annak val´osz´ın˝ us´ege, hogy a goly´o egy adott szeletben ´alljon meg, ar´anyos a szelet ter¨ ulet´evel. A szeletekben a val´osz´ın˝ us´egek l´athat´ok.

A kanonikus genetikus algoritmus (CGA): 1. Hat´arozzuk meg a P popul´aci´o r´atermetts´eg´et: F=

n X

f(vi )

i=1

2. Minden egyedre sz´amoljuk ki a kiv´alaszt´asi val´osz´ın˝ us´eget: pi = f(vi )/F,

i = 1, 2, . . . , n

3. Minden egyedre kisz´amoljuk a kumulat´ıv kiv´alaszt´asi val´osz´ın˝ us´eget: qi =

i X

pj ,

i = 1, 2, . . . , n

j=1

4. Minden egyedre a P popul´aci´ob´ol: (a) Gener´alunk egy val´os v´eletlen sz´amot: r ∈ [0, 1] (b) Ha r < q1 , akkor kiv´alasztjuk v1 -et az u ´j P 0 popul´aci´oba; K¨ ul¨onben, ha qi−1 < r ≤ qi , akkor kiv´alasztjuk vi -t az u ´j P 0 popul´aci´oba 5. Minden egyedre az u ´j P 0 popul´aci´ob´ol: (a) Gener´alunk egy val´os v´eletlen sz´amot: r ∈ [0, 1]

12

2. fejezet. A kanonikus genetikus algoritmus

(b) Ha r < pc , akkor kiv´alasztjuk az aktu´alis egyedet keresztez´esre (pc a keresztez´esi val´osz´ın˝ us´eg) 6. Legyen c a keresztez´esre kiv´alasztott egyedek sz´ama. Ha c p´aratlan, akkor a kiv´alasztottak k¨oz¨ ul v´eletlenszer˝ uen kiejt¨ unk egy egyedet. 7. Minden keresztez´esre kiv´alasztott egyedp´arra: (a) Gener´alunk egy pozit´ıv eg´esz v´eletlen sz´amot: r ∈ {1, 2, . . . , m − 1}, ahol m a kromosz´oma hossza, azaz a g´enek sz´ama. (b) Az r sz´am lesz a rekon, ´es elv´egezz¨ uk a keresztez´est. (c) A k´et kiv´alasztott sz¨ ul˝o hely´ere a k´et lesz´armazott ker¨ ul az u ´j P 0 popul´aci´oban. 8. Minden egyed (kromosz´oma) minden g´enj´ere az u ´j P 0 popul´aci´oban: (a) Gener´alunk egy val´os v´eletlen sz´amot: r ∈ [0, 1] (b) Ha r < pm , a g´ent mut´aljuk (pm a mut´aci´o val´osz´ın˝ us´ege; muton=1) 9. Ha a meg´all´asi felt´etel teljes¨ ul, akkor STOP; 0 K¨ ul¨onben P := P ´es visszaugrunk az 1. pontra. Algoritmusunk r¨oviden a k¨ovetkez˝ok´eppen v´azolhat´o: L´etrehozzuk a kezdeti P popul´aci´ot Ism´eteld: Szelekci´o: P → P 0 Keresztez´es, mut´aci´o P 0 popul´aci´oban P := P 0 Am´ıg a meg´all´asi felt´etel teljes¨ ul. A meg´all´as ut´an a v´egs˝o popul´aci´o legr´atermettebb egyede j´o megk¨ozel´ıt´es´et fogja adni az ´altalunk keresett optimumnak. Ezzel a m´odszerrel az algoritmus v´eges sz´am´ u iter´aci´o ut´an a glob´alis optimumhoz fog konverg´alni f¨ uggetlen¨ ul a kezdeti popul´aci´ot´ol. A k´ıs´erletek azt igazolt´ak, hogy hogy a kezdeti popul´aci´o k¨ ul¨onb¨oz˝o megv´alaszt´asa csak a konvergencia sebess´eg´et befoly´asolja. A tulajdonk´eppeni genetikus algoritmus fogalm´ahoz szervesen kapcsol´odott a bin´aris string reprezent´aci´o, az´ert, hogy a kromosz´om´ak ´es g´enek modellez´ese szeml´eletes, val´os´agh˝ u legyen. De ezen reprezent´aci´onak h´atul¨ ut˝oi is vannak: nagy keres´esi ter¨ ulet ´es nagy pontoss´ag eset´en ´ori´asira n˝ohet egy kromosz´oma hossza, ami pr´ob´ara teszi a sz´am´ıt´og´ep mem´oriak´eszlet´et. Az oda-vissza

13 k´odol´as k¨ovetkezt´eben az algoritmus vesz´ıt gyorsas´ag´ab´ol. Ez´ert bevezett´ek a lebeg˝opontos ´abr´azol´asi m´odot. A k´ıs´erletek sor´an a lebeg˝opontos ´abr´azol´assal jobb eredm´enyeket ´ertek el, ´es nagy keres´esi ter¨ ulet illetve pontoss´ag eset´en is jelent˝os gyorsas´agbeli k¨ ul¨onbs´eg volt tapasztalhat´o a k´et reprezent´aci´o k¨oz¨ott. A genetikus algoritmusok teh´at probl´emaf¨ uggetlen glob´alis optimiz´al´o algoritmusok, melyek biol´ogiai, evol´ uci´os folyamatokat modelleznek ugyan, viszont nem jellemz˝o r´ajuk a ”term´eszetes” sz´o.

14

2. fejezet. A kanonikus genetikus algoritmus

3 A genetikus algoritmusok ´ ja konvergencia

3.1.

S´ emaelm´ elet

A s´emaelm´elet a genetikus algoritmusok m˝ uk¨od´es´ere pr´ob´al magyar´azattal szolg´alni. Ebben a r´eszben ezzel az elm´eleti h´att´errel ismerked¨ unk meg. A s´emaelm´eletben az ´abr´azol´as bin´aris, a szelekci´o ar´anyos, a keresztez´es pedig egypontos. 3.1. defin´ıci´ o (S´ ema). Egy olyan speci´ alis kromosz´ am´ at, amely a 0 ´es 1 szimb´ olumokon (´ert´ekeken) k´ıv¨ ul m´eg a ”*” szimb´olumot is tartalmazhatja, s´em´ anak nevezz¨ uk, a ”*” szimb´olumot pedig nemt¨or˝od¨om (angolul don’t-care) szimb´ olumnak nevezz¨ uk. Teh´at egy nemt¨or˝od¨om szimb´olum hely´ere ak´ar 0, ak´ar 1 is ker¨ ulhet. Egy s´ema t¨obb kromosz´om´ara is illeszkedhet, m´egpedig egy k nemt¨or˝od¨om szimb´olumot tartalmaz´o kromosz´oma 2k kromosz´om´ara illeszkedik. A defin´ıci´ob´ol az is k¨ovetkezik, hogy minden kromosz´oma egyben s´ema is, mely nem tartalmaz ”*”-ot, ´es minden ilyen s´ema egyetlen kromosz´om´ara illeszkedik, m´egpedig saj´at mag´ara. P´eld´aul az S1 = (101∗∗101∗∗) s´ema t¨obbek k¨oz¨ott az (1011110111) kromosz´om´ara is illeszkedik. 3.2. defin´ıci´ o (S´ ema rendje). Egy s´ema r¨ogz´ıtett bitjeinek sz´am´ at a s´ema rendj´enek nevezz¨ uk ´es S s´ema eset´en o(S) szimb´olummal jel¨olj¨ uk. A fennebb l´athat´o p´elda eset´eben o(S1 ) = 6. 3.3. defin´ıci´ o (S´ ema defin´ıci´ os hossza). Egy s´ema els˝o ´es utols´o r¨ogz´ıtett bitje k¨ oz¨ otti t´avls´ agot a s´ema defin´ıci´ os hossz´anak nevezz¨ uk, ´es S s´ema eset´en δ(S) szimb´ olummal jel¨olj¨ uk. Ugyancsak a fenti p´elda eset´eben δ(S1 ) = 7. 15

16

´ ja 3. fejezet. A genetikus algoritmusok konvergencia

3.4. defin´ıci´ o (S´ ema r´ atermetts´ egi f¨ uggv´ eny´ ert´ eke). Egy s´ema r´ atermetts´egi f¨ uggv´eny´ert´eke azon kromosz´ om´ak r´atermetts´egi f¨ uggv´eny´ert´ekenek atlaga, amelyekre a s´ema illeszkedik: ´ f(S, t) =

p X

f(vi )/p,

i=1

hogyha S s´ema p darab kromosz´ om´ ara illeszkedik (t id˝opontban, illetve a t-edik gener´ aci´ oban). A szelekci´ o hat´ asa a s´ em´ ara Ebben a r´eszben a szelekci´o hat´as´at vizsg´aljuk meg a s´em´akra, vagyis, hogyan v´altozik a szelekci´o k¨ovekezt´eben azon kromosz´om´ak sz´ama, melyekre egy bizonyos s´ema illeszkedik. Legyen ξ(S, t) azon kromosz´om´ak sz´ama, melyekre az S s´ema t id˝opillanatban illeszkedik. Egy ´altal´anos kromosz´oma kiv´alaszt´asi val´osz´ın˝ us´ege, melyre az S s´ema illeszkedik (F(t) a popul´aci´o (¨ossz)r´atermetts´ege): f(S, t) F(t) Mivel n kiv´alaszt´as t¨ort´enik (n a popul´aci´o m´erete), fel´ırhatjuk a k¨ovetkez˝o k´epletet: ξ(S, t + 1) = ξ(S, t) · n · f(S, t)/F(t) Jel¨olj¨ uk F(t)-vel a popul´aci´o ´atlagr´atermetts´eg´et, azaz F(t) = F(t)/n Fenti k´eplet¨ unk ´ıgy a k¨ovetkez˝ok´eppen m´odosul, ξ(S, t + 1) = ξ(S, t) · f(S, t)/F(t) Ezt az ¨osszef¨ ugg´est reprodukt´ıv s´ema-n¨oveked´esi egyenletnek nevezz¨ uk. Azt a s´em´at, melynek r´atermetts´egi f¨ uggv´eny´ert´eke nagyobb mint a popul´aci´o ´atlagr´atermetts´ege, ´atlagon fel¨ uli s´em´anak nevezz¨ uk. Ugyan´ıgy, ha egy s´ema r´atermetts´egi f¨ uggv´enye kisebb (vagy egyenl˝o) mint a popul´aci´o ´atlagr´atermetts´ege, akkor a s´em´at ´atlagon aluli s´em´anak nevezz¨ uk. Egy s´ema r´atermetts´egi f¨ uggv´eny´ert´eke fel´ırhat´o a k¨ovetkez˝ok´eppen: f(S, t) = F(t) + ε · F(t),

´maelme ´let 3.1. Se

17

´ ahol ε ≥ −1 val´os sz´am. Atlagon fel¨ uli s´ema eset´en ε > 0, ´atlagon aluli s´ema eset´en pedig ε ∈ [−1, 0]. Az el˝obbi k´epletet a s´ema-n¨oveked´esi egyenletbe helyettes´ıtve kapjuk, hogy ξ(S, t + 1) = ξ(S, t) · (1 + ε), ahonnan ξ(S, t) = ξ(S, 0) · (1 + ε)t Ez a k´eplet azt jelenti, hogy ha az S s´ema ´atlagon fel¨ uli, akkor azon kromosz´om´ak sz´ama, melyekre S illeszkedik, exponenci´alisan n¨ovekszik az egym´ast k¨ovet˝o gener´aci´okban. A crossover hat´ asa a s´ em´ ara Ha egy kromosz´oma hossza m, akkor m − 1 egypontos keresztez´esi poz´ıci´o lehets´eges. ´Igy fel´ırhatjuk, hogy az S s´ema elhal´aloz´asi val´osz´ın˝ us´ege (angolul probability of destruction) δ(S) , pd (S) = m−1 vagyis a t´ ul´el´es val´osz´ın˝ us´ege (probability of survival ) ps (S) = 1 −

δ(S) m−1

K´eplet¨ unk ´ıgy m´eg nem igaz´an helyes, mivel nem vett¨ uk figyelembe a pc keresztez´esi val´osz´ın˝ us´eget. Ezt figyelembe v´eve v´egs˝o k´eplet¨ unk a k¨ovetkez˝o lesz, ps (S) ≥ 1 − pc ·

δ(S) m−1

Az´ert szerepel ”≥” jel az egyenl˝os´eg helyett, mert ha r¨ogz´ıtett poz´ıci´ok k¨oz¨ott is t¨ort´enik a keresztez´es, van es´ely a t´ ul´el´esre. Tekints¨ uk p´eld´aul a k¨ovetkez˝o esetet: Legyen S = (∗ ∗ 1 ∗ 0∗), amely a v1 = (011100) kromosz´om´ara illeszkedik, a keresztez´es v1 ´es v2 = (101011) kromosz´oma k¨oz¨ott megy v´egbe, tov´abb´a legyen a keresztez´esi poz´ıci´o 4. Ekkor v10 = (101000), v20 = (011110). L´athatjuk, hogy S ugyancsak illeszkedik v10 -re, mivel S els˝o fele illeszkedett v2 els˝o fel´ere. Figyelembe v´eve a s´ema t´ ul´el´esi val´osz´ın˝ us´eg´et, s´ema-n¨oveked´esi egyenlet¨ unk a k¨ovetkez˝ok´eppen m´odosul, · ¸ ¤ δ(S) ξ(S, t + 1) ≥ ξ(S, t) · f(S, t)/F(t) · 1 − pc · m−1 £

18

´ ja 3. fejezet. A genetikus algoritmusok konvergencia

A mut´ aci´ o hat´ asa a s´ em´ ara Egy s´ema akkor fogja t´ ul´elni a mut´aci´ot, azaz akkor fog illeszkedni a kromosz´om´akra a mut´aci´o ut´an, ha a r¨ogz´ıtett poz´ıci´okon l´ev˝o elemek v´altozatlanok maradnak. Egy g´en t´ ul´el´esi val´osz´ın˝ us´ege 1 − pm . Minden egyes g´enre el kell d¨onts¨ uk, hogy megv´altoztatjuk vagy v´altozatlanul hagyjuk. Ezek teh´at f¨ uggetlen val´osz´ın˝ us´egek, ´ıgy ezek szorzat´ara van sz¨ uks´eg¨ unk, azaz egy s´ema t´ ul´el´esi val´osz´ın˝ us´ege ps (S) = (1 − pm )o(S) lesz. Newton binomi´alis k´eplet´et alkalmazva fel´ırhatjuk, hogy (1 − pm )o(S) = 1 + C1o(S) · 1 · (−pm ) + C2o(S) · 1 · (−pm )2 + . . . Mivel pm ∈ (0, 1) ´es pm ¿ 1, ha egy megk¨ozel´ıt˝o ¨osszef¨ ugg´est szeretn´enk kapni pm -re, el´eg figyelembe venn¨ unk az ¨osszeg els˝o k´et tagj´at, u ´gy ´ervelve, hogy egy nagyon kicsi sz´am n´egyzete m´ar t´enyleg nagyon kicsi sz´am lesz, stb. ´Igy pm ≈ 1 − o(S) · pm Mostm´ar fel´ırhatjuk v´egs˝o s´ema-n¨oveked´esi egyenlet¨ unket, · ¸ ¤ £ δ(S) · [1 − o(S) · pm ] ξ(S, t + 1) ≈ ξ(S, t) · f(S, t)/F(t) · 1 − pc · m−1 3.1. t´ etel (S´ ema t´ etel). A r¨ovid, kisrend˝ u, ´atlagon fel¨ uli s´em´ ak exponenci´ alisan n¨ ovekv˝o r´eszt kapnak a genetikus algoritmusok egym´ ast k¨ovet˝ o gener´aci´ oiban. R¨ovid s´em´anak azt a s´em´at nevezz¨ uk, melynek defin´ıci´os hossza r¨ovid, m´ıg kisrend˝ unek azt, melyben a r¨ogz´ıtett bitek sz´ama kicsi. · ¸ δ(S) t ξ(S, t) ≈ ξ(S, 0) · (1 + ε) · 1 − pc · · [1 − o(S) · pm ] m−1 ´ ıt˝ 1. Hipot´ ezis (Ep´ okocka (Building Block ) hipot´ ezis). A genetikus algoritmusok r¨ovid kisrend˝ u, ´atlagon fel¨ uli (=´ep´ıt˝ o) s´em´ akon kereszt¨ ul kv´azi-optim´ alis (megk¨ ozel´ıt˝ oen optim´alis) eredm´enyt szolg´altatnak.

3.2.

A genetikus algoritmusok mint Markovl´ ancok

A kanonikus genetikus algoritmus (bin´aris ´abr´azol´as, ar´anyos szelekci´o, egypontos crossover) (Canonical Genetic Algorithm – CGA) algoritmusa a k¨ovetkez˝ok´eppen is fel´ırhat´o:

´ ncok 3.2. A genetikus algoritmusok mint Markov-la

19

kezdeti popul´aci´o kiv´alaszt´asa szelekci´o ism´eteld crossover mut´aci´o szelekci´o am´ıg a le´all´asi felt´etel nem teljes¨ ul Jel¨olj¨ uk n-nel a popul´aci´o m´eret´et, valamint legyen l egy kromosz´oma hossza. Tekints¨ unk egy popul´aci´ot egy ´allapotnak. Mivel egy popul´aci´oban n darab l hossz´ us´ag´ u bin´aris sztring szerepel, egy popul´aci´o hossza n · l. Teh´at az ´allapott´er, S = {0, 1}n·l m´erete 2n·l , mivel 2n·l n · l hossz´ us´ag´ u k¨ ul¨onb¨oz˝o bin´aris sztring l´etezik. A m˝ uveleteket (crossover, mut´aci´o, szelekci´o) pedig tekinthetj¨ uk egy sztochasztikus ´atmenetnek egy m´asik ´allapotba, ez´ert a CGA ´ertelmezhet˝o Markov-l´anck´ent, mely ´atmenetm´atrix´anak m´erete 2n·l × 2n·l . Legyen πk (i) egy olyan f¨ uggv´eny, amely visszaadja az i-edik ´allapot k-adik egyed´et. A tov´abbiakban a m˝ uveletek ´atmenetm´atrixait vizsg´aljuk.

Crossover Vizsg´aljuk meg azt az esetet, amikor a crossover nem v´altoztatja meg a popul´aci´ot, azaz a crossover el˝otti ´es ut´ani popul´aci´o egyedei azonosak. Ez h´arom esetben k¨ovetkezhet be. Legyen c a rekombin´aci´ora kiv´alasztott egyedek sz´ama. (a) c = 0 (b) c = 1 (c) Bizonyos egyedek rekombin´al´odnak, v´altozatlan marad. P´eld´aul: P ° 01|01 10|11 ° 01|11 10|01

→ →

de a popul´aci´o ennek ellen´ere

0 ¯ P 1001 ¯ 0111 1011 0101

´ ja 3. fejezet. A genetikus algoritmusok konvergencia

20

Fel´ırhatjuk a k¨ovetkez˝o val´osz´ın˝ us´egeket: P{c = 0}

= p0c · (1 − pc )n = (1 − pc )n

P{c = 1}

= pc · (1 − pc )n−1

P{c = 0 vagy c = 1} = (1 − pc )n + pc · (1 − pc )n−1 = = (1 − pc )n−1 · (1 − pc + pc ) = (1 − pc )n−1 Figyelembe v´eve, hogy a (c) eset is bek¨ovetkezhet, fel´ırhatjuk, hogy P{popi → popi } ≥ (1 − pc )n−1 > 0

Mut´ aci´ o Annak val´osz´ın˝ us´ege, hogy a mut´aci´o egy egyedet egy meghat´arozott m´odon megv´altoztat a k¨ovetkez˝ok´eppen ´ırhat´o fel: k (i),πk (j)) P{πk (i) → πk (j)} = pH(π · (1 − pm )l−H(πk (i),πk (j)) , m

ahol a H(·, ·) f¨ uggv´eny k´et bin´aris sztring k¨oz¨otti Hamming-t´avols´agot adja meg. P´eld´aul P{1011 → 0001} = pm · (1 − pm ) · pm · (1 − pm ) = p2m · (1 − pm )2 Ezt ugyanilyen m´odon fel´ırhatjuk k´et popul´aci´o k¨oz¨ott: H(popi ,popj )

P{popi → popj } = pm

· (1 − pm )n·l−H(popi ,popj ) > 0

Ez azt jelenti, hogy a mut´aci´o ´atmenetm´atrixa szigor´ uan pozit´ıv.

Szelekci´ o R´atermetts´egi f¨ uggv´eny¨ unk f : {0, 1}l → R+ Annak val´osz´ın˝ us´ege, hogy egy egyed ´atker¨ ulj¨on a k¨ovetkez˝o gener´aci´oba (szelekci´os val´osz´ın˝ us´eg) f(πk (i)) P{πk (i) → πk (i)} = Pn k=1 f(πk (i))

´ ncok 3.2. A genetikus algoritmusok mint Markov-la

21

Annak val´osz´ın˝ us´ege, hogy minden egyed ´atker¨ ulj¨on a k¨ovetkez˝o gener´aci´oba, azaz kiv´alaszt´odjon ezen val´osz´ın˝ us´egek szorozata minden egyedre, vagyis Qn f(πk (i)) P{popi → popi } = Pnk=1 n > 0 [ k=1 f(πk (i))] Az egy¨ uttes ´atmenetm´atrix fel´ırhat´o u ´gy mint P = C · M · S, ahol C, M ´es S rendre a crossover, mut´aci´o, illetve szelekci´o ´atmenetm´atrixai. 3.2. t´ etel. A CGA P = C · M · S ´ atmenetm´ atrixa pozit´ıv sztochasztikus m´atrix, vagyis pij > 0, ∀i, j. P ´ s. Legyen A = C · M, ai,j = k cik · mkj > 0, mert cii > 0 ´es mij > 0. Bizony´ıta P Tov´abb´a P = A·S, pij = k aik ·skj > 0, mert sjj > 0 ´es aij > 0. 3.3. t´ etel. Legyen P egy ML ´atmenetm´ atrixa, u pedig a kezdeti eloszl´ast reprezent´ al´ o val´osz´ın˝ us´egi vektor. Ekkor u(n) = u · Pn

(a)

a l´anc val´osz´ın˝ us´eg´et adja az n-edik l´ep´esben, vagyis egy val´osz´ın˝ us´egi vektort, amely megmondja, hogy a ML az n-edik l´ep´esben melyik ´allapotban mekkora val´ osz´ın˝ us´eggel tal´alhat´ o. 3.5. defin´ıci´ o. Egy ML ergodikus, ha b´armelyik ´allapotb´ ol b´armelyik ´allapotba eljuthatunk v´eges sz´am´ u l´ep´esben. (Nem felt´etlen¨ ul egy l´ep´esben.) 3.6. defin´ıci´ o. Egy ML regul´aris ha ´atmenetm´ atrix´ anak valamely v´eges sz´am´ u hatv´ anya szigor´ uan pozit´ıv. 3.4. t´ etel. Legyen P egy regul´ aris ML ´atmenetm´ atrixa. Ha n → ∞, akkor Pn → W, ahol W minden sora ugyanazon w szigor´ uan pozit´ıv val´osz´ın˝ us´egi vektorral egyenl˝ o, azaz W = lim Pn (b) n→∞

Az (a) ´es (b) ¨osszef¨ ugg´esekb˝ol azonnali m´odon k¨ovetkezik, hogy u(∞) = lim u · Pn = u · lim Pn = u · W n→∞

n→∞

Mivel u 6= 0 – mert abban az esetben semmilyen ´allapotba sem juthatn´ank el –, (∞) ez´ert u(∞) = u · W > 0, azaz ui > 0, ∀i.

22

´ ja 3. fejezet. A genetikus algoritmusok konvergencia

­ 3.7. defin´ıci´ o. Legyen Zt = max

(t) f(πk (i))|k ∗

® = 1, . . . , n

az i-edik ´allapot

legjobb egyed´enek r´atermetts´ege, illetve jel¨olje f = max{f(b)|b ∈ {0, 1}l } a f¨ uggv´eny maximum´ at. Azt mondjuk, hogy egy genetikus algoritmus a glob´alis optimumhoz konverg´ al ha lim P{Zt = f∗ } = 1 n→∞

3.5. t´ etel. A CGA nem konverg´ al a glob´alis optimumhoz. ´ s. Tekints¨ Bizony´ıta unk egy ­ ® (t) Zt = max f(πk (i))|k = 1, . . . , n < f∗ (t)

tulajdons´ag´ u i ´allapotot. Tov´abb´a legyen pi annak a val´osz´ın˝ us´ege, hogy a genetikus algoritmus a t-edik id˝opillanatban ebben az ´allapotban van. ´Igy (t)

P{Zt < f∗ } = P{Zt 6= f∗ } = pi , vagyis

(t)

P{Zt = f∗ } = 1 − pi , ahonnan

(∞)

lim P{Zt = f∗ } = 1 − pi

t→∞

<1

Annak ellen´ere, hogy a CGA nem konverg´al a glob´alis optimumhoz egyszer˝ u v´altoztat´assal konvergenss´e tehetj¨ uk algoritmusunkat. Az elj´ar´ason annyit v´altoztatunk, hogy kib˝ov´ıtj¨ uk a popul´aci´ot egy u ´n. szuper egyeddel (super individual ), amely nem vesz r´eszt az evol´ uci´os folyamatban. Ez azt jelenti, hogy az ´allapott´er egy egyeddel kib˝ov¨ ul, vagyis sz´amoss´aga 2n·l -r˝ol 2(n+1)·l -re n˝o. Az i-edik ´allapot szuper egyed´et a π0 (i) f¨ uggv´eny seg´ıts´eg´evel ´erhetj¨ uk el. A crossover, mut´aci´o ´es szelekci´o ´atmenetm´atrix´at a k¨ovetkez˝ok´eppen szerkessz¨ uk meg: egym´as al´a helyezz¨ uk azon ´allapotok ´atmeneti val´osz´ın˝ us´egeit, melyek ugyanazt a szuper egyedet tartalmazz´ak, a szuper egyedek pedig balr´ol jobbra ´es fentr˝ol lefel´e r´atermetts´eg¨ uk szerint cs¨okken˝o sorrendben szerepelnek. ´Igy a crossover, mut´aci´o ´es szelekci´o kib˝ov´ıtett ´atmenetm´atrix´at a k¨ovetkez˝ok´eppen ´ırhatjuk fel:     M C     M C     + + C = ; ; M =  . . . .     . . M C

´ ncok 3.2. A genetikus algoritmusok mint Markov-la

   S = 



S S

+

23

  , 

... S

ahol C, M ´es S 2n·l × 2n·l m´eret˝ u n´egyzetes m´atrixok, melyek mindegyik´eb˝ol 2l darab tal´alhat´o a megfelel˝o fenti m´atrixokban. A m´asol´asi m˝ uveletet egy U feljav´ıt´o (upgrade) m´atrix seg´ıts´eg´evel val´os´ıtjuk meg, amely egy ´allapotot, melyben a legr´atermetteb egyed r´atermetts´ege nagyobb mint a szuper egyed´e, ´atv´altoztat olyan ´allapott´a, melyben a szuper egyed azonos a legr´atermettebb egyeddel. Form´alisan legyen b = argmax {f(πk (i))|k = 1, . . . , n} ∈ {0, 1}l az i ´allapot legr´atermettebb egyede figyelmen k´ıv¨ ul hagyva a szuper egyedet. Ekkor uij = 1 ha f(π0 (i)) < f(b), ahol j = (b, π1 (i), π2 (i), . . . , πn (i)) ∈ S, k¨ ul¨onben uii = 1. Ez´ert U fel´ırhat´o a k¨ovetkez˝ok´eppen,   U1,1  U2,1 U2,2    U =  .. , .. . ..  .  . U2l ,1 U2l ,2 · · · U2l ,2l ahol U·,· 2n·l × 2n·l m´eret˝ u minorm´atrixok. Az U m´atrix f˝o´atl´oja feletti elemek mind z´erusok, mivel U csak r´atermettebb szuper egyeddel rendelkez˝o ´allapotba m´odos´ıthat egy ´allapotot, ´es az aktu´alist´ol r´atermettebbek att´ol balra tal´alhat´ok. A k¨onnyebb meg´ert´es ´erdek´eben tekints¨ uk a k¨ovetkez˝o p´eld´at: f(x) = x, l = 1, n = 2 szuper egyed

1

0

1 popul´aci´ok 00 01 10 11 00 01 10 11

00 1

01

0 10

11

00

01

10

11

1 1 1 1 1 1 1

Nyilv´anval´o, hogy U1,1 = I, mivel ezek az ´allapotok a legr´atermettebb szuper egyedet, azaz a glob´alis optimumhoz tartoz´o ´ert´eket tartalmazz´ak. Tov´abb´a minden Ui,j , i > 1, j > 1 minorm´atrix olyan egys´egm´atrix, amely n´eh´any z´erust is tartalmaz a f˝oa´tl´on, term´eszetesen csak abban az esetben ha a f¨ uggv´eny egyetlen

´ ja 3. fejezet. A genetikus algoritmusok konvergencia

24

glob´alis optimummal rendelkezik. Ha t¨obbel, tegy¨ uk fel k glob´alis optimummal, akkor Uii = I, i = 1, . . . , k Uij = 0, i = 2, . . . , k, j = 1, . . . , k − 1, minden m´as U·,· m´atrix legal´abb egy darab 1-est tartalmaz a f˝o´atl´on u ´gy, hogy U minden sor´aban csak egy darab 1-es szerepel. Az egyszer˝ us´eg kedv´e´ert t´etelezz¨ uk fel, hogy f-nek csak egy glob´alis optimuma van. Az U m´atrixszal t¨ort´en˝o m´odos´ıt´ast a szelekci´o el˝ott kell, hogy elv´egezz¨ uk, ez´ert P+ = T+ · U · S+ , ahol T+ = C+ · M+ . ´Igy  +

P

  =  

T

   ·     =  

 

T ..

    ·  

. T

S S



U1,1 U2,1 .. .

 U2,2 .. .

U2l ,1 U2l ,2

. · · · U2l ,2l

  = 

... S

TU1,1 S TU2,1 S .. .

..

   

TU2,2 S .. .

 ..

. TU2l ,1 S TU2l ,2 S · · · TU2l ,2l S

   

(3.1)

ahol T · U1,1 · S > 0, mert T = C · M, U1,1 = I ⇒ T · U1,1 · S = C · M · S > 0. Legyen   TU2,1 S   .. R=  . TU2l ,1 S L´athatjuk, hogy R 6= 0, mivel T > 0 ´es U2,1 · S 6= 0, mert S f˝oa´tl´oj´an csak z´er´ot´ol k¨ ul¨onb¨oz˝o elemek vannak, U2,1 f˝o´atl´oj´an pedig legal´abb egy darab 1-es tal´alhat´o. Ugyan´ıgy, a fennmarad´o minorm´atrixokat V-vel jel¨olve nyilv´anval´o, hogy V 6= 0. 3.8. defin´ıci´ o. Egy Markov-l´ancot reducibilis Markov-l´ancnak nevez¨ unk ha P atmenetm´ ´ atrixa a k¨ovetkez˝ o alakra hozhat´o, µ ¶ C 0 P= , R T ahol C ´es T n´egyzetes m´atrixok.

´ ncok 3.2. A genetikus algoritmusok mint Markov-la

25

3.6. t´ etel. Ha P egy reducibilis sztochasztikus m´atrix, C egy m × m m´eret˝ u primit´ıv sztochasztikus m´atrix, illetve R, T 6= 0, akkor µ ¶ µ ∞ ¶ Ck 0 C 0 ∞ k P = lim P = Pk−1 i = k−i R∞ 0 k→∞ Tk i=0 T RC egy stabil sztochasztikus m´atrix. Ha u egy kezdeti eloszl´asvektor, akkor u(∞) = u · P∞ , (∞) ui > 0, 1 ≤ i ≤ m, (∞) ui = 0, i > m Vagyis a mi eset¨ unkben annak a val´osz´ın˝ us´ege, hogy az elitista kanonikus genetikus algoritmus t → ∞ l´ep´esben olyan ´allapotban legyen, ahol a szuper egyed nem a glob´alis optimum egyenl˝o z´er´oval. Mivel a bizony´ıt´ast el˝ore elv´egezt¨ uk nincs m´as h´atra mint kijelenten¨ unk t´etel¨ unket: 3.7. t´ etel. Az elitista CGA a glob´alis optimumhoz konverg´ al.

26

´ ja 3. fejezet. A genetikus algoritmusok konvergencia

4 A genetikus algoritmusok konvergencia-ideje

27

28

4. fejezet. A genetikus algoritmusok konvergencia-ideje

5 ´ , kereszteze ´s, muta ´ cio ´ Szelekcio

29

30

´ , kereszteze ´s, muta ´ cio ´ 5. fejezet. Szelekcio

6 ´ lyoza ´ s genetikus Oszta algoritmusokkal

31

32

´ lyoza ´ s genetikus algoritmusokkal 6. fejezet. Oszta

7 ´ rhuzamos genetikus Pa algoritmusok

Mag´at´ol ´ertet˝odik, hogy a kezdeti popul´aci´o megv´alaszt´asa nagyban befoly´asolja a konvergencia sebess´eg´et. Ez´ert ha p´arhuzamosan t¨obb popul´aci´ot tartunk fenn ´es bizonyos id˝ok¨oz¨onk´ent, hogy ne lassuljon l´enyegesen a folyamat, kicser´el¨ unk egyedeket a popul´aci´ok k¨oz¨ott, a konvergencia idej´enek cs¨okken´es´et v´arjuk el.

33

34

´ rhuzamos genetikus algoritmusok 7. fejezet. Pa

8 ´ s evolut´ıv algoritmusok Ma

8.1.

Evol´ uci´ os strat´ egi´ ak 3

2.5

2

1.5

1

0.5

0 −4

−3

−2

−1

8.1. ´abra. Gauss-g¨orbe, y =

8.1.1.

0

√1 σ 2π

1

2

exp(− 12

¡ x−µ ¢2 3

4

σ

), µ = 0, σ = 1

Az (1,1)-ES konvergenci´ aja

Az (1,1)-ES-kat a k¨ovetkez˝o felt´etelek mellett tehetj¨ uk konvergenss´e. Legyen f : N E → R f¨ uggv´eny, E ⊂ R . A feladat megtal´alni f minimum´at az E halmazon a k¨ovetkez˝o felt´etelek mellett: (i) az E keres´esi t´er Lebesgue-m´erhet˝o (ii) f m´erhet˝o f¨ uggv´eny (iii) f-nek l´etezik minimuma az E halmazon (iv) ha m(S) egy S halmaz Lebesgue-m´ert´eke, akkor b´armely a > 0 sz´am eset´en m({x|f(x) ≤ min f(y) + a}) > 0 y∈E

35

´ s evolut´ıv algoritmusok 8. fejezet. Ma

36

8.1. defin´ıci´ o. Egy e x pontot az optimiz´al´ asi (minimiz´al´ asi) feladat megold´ as´ anak nevez¨ unk, ha f(e x) ≤ min f(x) + ², x∈E

ahol ² a hiba m´ert´eke vagy hibak¨ usz¨ ob. 8.1. t´ etel (Konvergencia-t´ etel). Az (1,1)-ES – az (i)–(iv) felt´eteleknek megfelel˝ oen – a glob´alis optimumhoz konverg´ al. ´ s. (A bizony´ıt´as a [GZ01]-b˝ol sz´armazik.) Bizony´ıta T´etelezz¨ uk fel, hogy a hibak¨ usz¨ob ², vagyis e x a minimiz´al´asi probl´ema megold´asa ha f(e x) ≤ min f(x) + ² x∈E

8.2.

Evol´ uci´ os programoz´ as

8.3.

Genetikus programoz´ as

8.3.1.

Line´ aris genetikus programoz´ as

9 ´ sok Alkalmaza

9.1.

F¨ uggv´ enyoptimiz´ al´ as kanonikus genetikus algoritmussal

Legyen az optimiz´aland´o f¨ uggv´eny¨ unk f(x) = x · sin x + 3

(a)

melynek meg szeretn´enk hat´arozni a maximum´at p´eld´aul a [−10, 10] intervallumon. Az´ert sz¨ uks´eges egy v´eges intervallum megad´asa (a ,,v´eges” alatt itt mind¨ossze azt ´ertj¨ uk, hogy az intervallumnak van eleje ´es v´ege, egysz´oval az intervallum hat´arai v´eges sz´amok), mert a v´egtelen nem ´abr´azolhat´o a sz´am´ıt´og´ep v´eges mem´ori´aj´aban. Term´eszetesen a fenti intervallum is v´egtelen, viszont k¨onnyen v´egess´e alak´ıthat´o, ha csak egy bizonyos pontoss´aggal vizsg´aljuk (p´eld´aul 4-tizedes pontoss´aggal). A kanonikus genetikus algoritmus r´atermetts´eg-ar´anyos szelekci´ot haszn´al, a r´atermetts´eg pedig, ha egy f¨ uggv´eny maximum´at szeretn´enk meghat´arozni, akkor egyenl˝o a f¨ uggv´eny´ert´ekkel, f¨ uggv´enyminimum meghat´aroz´asakor pedig a f¨ uggv´eny´ert´ek ellentettj´evel vagy reciprok´aval. Mivel a szelekci´os val´osz´ın˝ us´egeket a r´atermetts´egb˝ol sz´am´ıtjuk ki, a r´atermetts´eg, azaz a f¨ uggv´eny´ert´ek pozit´ıv kell legyen ahhoz, hogy ´erv´enyes val´osz´ın˝ us´egeket kapjunk. Ha f¨ uggv´eny¨ unk nem pozit´ıv, akkor a pozitivit´as biztos´ıt´as´anak legegyszer˝ ubb m´odja egy el´egs´egesen nagy pozit´ıv konstans hozz´aad´asa a f¨ uggv´eny´ert´ekhez (felt´eve, hogy rendelkez¨ unk ilyen inform´aci´oval), azaz g(x) = f(x) + K, K > 0 u ´gy, hogy g(x) > 0 ∀x (Itt a g(x) > 0 felt´etelben elvileg ´allhatna ,,≥” is, viszont ez azt eredm´enyezn´e, hogy a z´erus r´atermetts´eg˝ u egyedek sohasem ker¨ ulnek kiv´alaszt´asra, ami viszont befoly´asolhatja az algoritmus konvergenci´aj´anak sebess´eg´et.) 37

´ sok 9. fejezet. Alkalmaza

38 12

10

8

6

4

2

0

-2

-4 -10

-8

-6

-4

-2

0

2

4

6

8

10

9.1. ´abra. Az x · sin x + 3 f¨ uggv´eny grafikus k´epe a [−10, 10] intervallumban Ezut´an pedig g(x)-et tekintj¨ uk az optimiz´aland´o f¨ uggv´enynek. Ha a keresett maximumot megtal´altuk – jel¨olje ezt xopt –, akkor az f(xopt ) = g(xopt )− K kisz´am´ıt´asa ´altal megkapjuk az eredeti f¨ uggv´eny maximum´at. Tekints¨ uk teh´at az (a) optimiz´aland´o f¨ uggv´enyt. Tudjuk, hogy x minimuma a [−10, 10] intervallumban −10, m´ıg sin x-´e −1. N´emi logik´aval kisz´am´ıthatjuk a f¨ uggv´eny minimum´anak egy als´o ´ert´ek´et u ´gy, hogy tekintj¨ uk (a) komponensenk´enti minimum´at, majd ezeket ¨osszevonjuk. N´ezz¨ uk a jelenlegi f¨ uggv´enyt. Tudjuk, hogy x minimuma a [−10, 10] intervallumon −10, m´ıg sin x-´e −1. Viszont e k´et komponens k¨oz¨ott szorz´as van, ez´ert az ¨osszevont minimumot akkor kapjuk, ha az el˝ojelek k¨ ul¨onb¨oznek, vagyis x · sin x minimuma −10. A 3 ,,f¨ uggv´eny” minimuma term´eszetesen 3, ez´ert, a k´et ´ert´eket ¨osszeadva kapjuk, hogy −K = −7, azaz K = 7. ´Igy a g(x) = x · sin x + 10 f¨ uggv´eny most felt´etelezhet˝oen pozit´ıv, viszont nem vagyunk biztosak a szigor´ u pozitivit´asban (term´eszetesen szigor´ uan pozit´ıv, de felt´etelezz¨ uk, hogy ezt nem tudjuk). Ez´ert ha g(x)-hez egyszer˝ uen hozz´aadunk egy tetsz˝oleges pozit´ıv ´ert´eket, akkor ily m´odon az ered˝o f¨ uggv´eny szigor´ uan pozit´ıv lesz az adott intervallumon. Enn´elfogva optimiz´aland´o f¨ uggv´eny¨ unk v´egs˝ o alakja: h(x) = x · sin x + 11 Mi´ert sz¨ uks´eges a szigor´ u pozitivit´as, mi´ert nem elegend˝o a pozitivit´as biztos´ıt´asa? Ha r´atermetts´eg-ar´anyos szelekci´oval dolgozunk, akkor a r´atermetts´egi f¨ uggv´eny¨ unk f(·)/F alak´ u, ahol f az optimiz´aland´o f¨ uggv´eny, vagy annak a fentiekhez hasonl´o transzform´aci´oja, m´ıg F egy normaliz´al´o t´enyez˝o, azaz a popul´aci´o

¨ ggve ´nyoptimiza ´ la ´ s kanonikus genetikus algoritmussal 9.1. Fu

39

r´atermetts´ege (l´asd az x. fejezetet). Ha f(·) ≥ 0, akkor lesz egy (vagy t¨obb) olyan pont, ahol a f¨ uggv´eny, illetve a r´atermetts´eg´enek ´ert´eke egyenl˝o lesz z´erussal. Ha ezt enged´elyezz¨ uk, akkor ezek az egyedek sohasem fognak r´eszt venni a popul´aci´o fejl˝od´es´eben, ´es mi ezt nem akarjuk, mivel lehet, hogy egy z´erus ´es egy z´erusn´al nagyobb r´atermetts´eg˝ u egyed rekombin´aci´oj´ab´ol a sz¨ ul˝okn´el r´atermettebb egyedet vagy egyedeket kapunk. Teh´at ez befoly´asolhatja az algoritmus konvergenci´aj´at vagy konvergenci´aj´anak sebess´eg´et, ez´ert mindig biztos´ıtsuk a szigor´ u pozitivit´ast. A k¨ovetkez˝o l´ep´esben tegy¨ uk v´egess´e a [−10, 10] intervallumot, azaz v´alasszunk egy el´egs´eges pontoss´agot. Legyen ez most 4. Ez tulajdok´eppen azt jelenti, hogy az egys´egnyi [k, k+1] intervallumot, k ∈ Z, 4·10-r´eszre kell osszuk, vagyis a [−10, 10]intervallumot (10 − (−10)) · 40 = 800 r´eszre. Egy [−10, 10] intervallumbeli sz´amot 4-tizedes pontoss´aggal b biten tudunk ´abr´azolni, 2b−1 < 800 ≤ 2b − 1, ahonnan b = 10, mivel 29 = 512 < 800 ≤ 210 − 1 = 1023. Azaz algoritmusunkban a kromosz´om´ak hossza 10 lesz. Viszont ahhoz, hogy egy egyed r´atermetts´eg´et ki tudjuk sz´am´ıtani, sz¨ uks´eg¨ unk lesz egy olyan f¨ uggv´enyre, mely egy 10 hossz´ us´ag´ u bitsztringet a [−10, 10] intervallumba k´epez. Az ´atalak´ıt´o f¨ uggv´enyhez a k¨ovetkez˝o ´ l´ep´eseken kereszt¨ ul juthatunk. Altal´ anosan, ha adott egy b hossz´ us´ag´ u x bitsztring, melyet az [i1 , i2 ] intervallumba akarunk lek´epezni, akkor 0 ≤ dec(x) ≤ 2b − 1, ahol dec(x) az x bitsztring 10-es sz´amrendszerbeli ´ert´ek´et adja. Osszuk el az ¨osszef¨ ugg´est (2b − 1)-gyel, majd szorozzuk be (i2 − i1 )-gyel. ´Igy dec(x) · (i2 − i1 ) ≤ i2 − i1 2b − 1 Most adjuk az ¨osszef¨ ugg´eshez i1 -et, ahonnan 0≤

i1 ≤

dec(x) · (i2 − i1 ) + i1 ≤ i2 2b − 1

´Igy a k¨oz´eps˝o ¨osszef¨ ugg´es pontosan a keresett ´atalak´ıt´o f¨ uggv´eny lesz, vagyis alak´ıt(x) =

dec(x) · (i2 − i1 ) + i1 2b − 1

Legyen p´eld´aul e1 = 1 0 1 0 0 0 1 1 1 1, ahonnan dec(e1 ) = 655, alak´ıt(e1 ) = 655 · 20 − 10 = 2.8054 ∈ [−10, 10]. Ha m´eg most is akad aki k´etelkedik az 1023 alak´ıt f¨ uggv´eny helyess´eg´eben, vizsg´aljuk meg a legkisebb illetve a legnagyobb 10-es hossz´ us´ag´ u bin´aris sz´amot (sztringet): e2 = 0 0 . . . 0 e3 = 1 1 . . . 1

´ sok 9. fejezet. Alkalmaza

40 Elv´egezve a m˝ uveleteket kapjuk, hogy alak´ıt(e2 ) =

0 · 20 − 10 = −10 1023

alak´ıt(e3 ) =

1023 · 20 − 10 = 10 1023

Egy egyed r´atermetts´eg´et a k¨ovetkez˝ok´eppen sz´am´ıthatjuk ki: r´atermetts´eg(e) = h(alak´ıt(e)) A szelekci´o t´ıpus´anak megv´alaszt´as´at az olvas´ora b´ızzuk. A mut´aci´ot ´es a crossovert u ´gy kell defini´alnunk, hogy csakis ´erv´enyes egyedeket eredm´enyezzenek (ebben az esetben minden 10 hossz´ us´ag´ u bin´aris sztring ´erv´enyes egyed). Haszn´alhatjuk a kanonikus oper´atorokat, azaz az ´alland´o val´osz´ın˝ us´eg˝ u, f¨ uggetlen g´enmut´aci´ot ´es az egypontos crossovert, azonban ekkor a konvergencia biztos´ıt´as´ahoz elitista szelekci´ot kell haszn´alnunk.

9.1.1.

A Gray-k´ od

A Gray-k´odokat a Bell Labsn´el dolgoz´o Frank Gray-r˝ol nevezt´ek el, aki anal´og jelek bin´aris k´odba val´o ´atalak´ıt´as´at val´os´ıtotta meg ezek ´altal. Az ilyen t´ıpus´ u k´odokat nem ˝o fedezte fel, ˝o csak mag´at az elj´ar´ast tal´alta ki, majd v´edte le. A Gray-k´odok azzal az ´erdekes tulajdons´aggal rendelkeznek, hogy k´et egym´as melletti term´eszetes sz´am Gray-k´odjainak Hamming-t´avols´aga 1, vagyis az egym´as melletti sz´amok 1 bitben k¨ ul¨onb¨oznek. A genetikus algoritmusokban val´o haszn´alatuk az´ert v´alt elterjedtt´e, mert gyorsabb kovergenci´at biztos´ıtanak. A mut´aci´o azt jelenti, hogy egy (bin´aris) egyed egyik bitj´et megv´altoztatjuk, azaz az aktu´alis bitet ´ert´ek´enek komplementere lesz az u ´j bit. Teh´at a keres´esi t´erben az el˝oz˝o poz´ıci´ot´ol val´o elt´avolod´as ar´anyos a mut´aci´ok sz´am´aval. Ha a mut´aci´ot a bin´aris sztringeken v´egezz¨ uk, akkor ez csak ritk´an fog ar´anyos elmozdul´ast eredm´enyezni. A keresztez´es is el˝ony¨osebb Gray-k´odokkal, ezt az al´abbi p´elda szeml´elteti (ref. Haupt, section 5.4). Tekints¨ uk az al´abbi k´et egyedet: p1 = 1 0 0|0 0 0 0 0 (= 128) p2 = 0 1 1|1 1 1 1 1 (= 127) A f¨ ugg˝oleges vonal a keresztez´esi pontot jel¨oli. Az egyedek r´atermetts´ege legyen egyszer˝ uen bin´aris k´odjuk decim´alis ´ert´eke (z´ar´ojelben ezek l´athat´ok). Elv´egezve a keresztez´est az al´abbi lesz´armazottakat kapjuk: o1 = 1 0 0|1 1 1 1 1 (= 159)

¨ ggve ´nyoptimiza ´ la ´ s kanonikus genetikus algoritmussal 9.1. Fu

41

o2 = 0 1 1|0 0 0 0 0 (= 96) L´athatjuk, hogy a sz¨ ul˝ok r´atermetts´ege rendre 128 ´es 127, m´ıg a lesz´armazottak´e 159 ´es 96. A keresztez´es – defin´ıci´o szerint – a sz¨ ul˝ok tulajdons´agait egyes´ıti ´es a lesz´armazottak nagy val´osz´ın˝ us´eggel r´atermettebbek lesznek sz¨ uleikn´el. A lesz´armazottak r´atermetts´ege nagyon elt´er a sz¨ ul˝ok r´atermetts´eg´et˝ol ´es k´et ir´anyban is v´altozik, ´es nem is kis m´ert´ekben. Erre a probl´em´ara ugyancsak megold´ast szolg´altatnak a Gray-k´odok. A bin´aris sztringek Gray-k´odba val´o alak´ıt´asa, illetve ezek visszaalak´ıt´asa bin´aris sztringg´e a 9.2. ´es 9.3. ´abr´akon l´athat´o. b5

b4 b3 b2 b1 Ņ Ņ Ņ Ņ b5 b4 b3 b2 b XOR XOR XOR XOR1 Ņ Ņ Ņ Ņ Ņ Ņ Ņ Ņ XOR XOR XOR XOR b5’ b4’ b3’ b2’ b1’ Ņ Ņ Ņ Ņ b4’ sz´am Gray-k´ b3’ odba val´ b2’ o ´atalak´ bıt´ ’ sa 9.2. b ´abra. Bin´aris 5’ 1a b5

b5 b5’

b5’

b4 Ņ b4 XOR ŅŅ bXOR 4’ Ņ b4’

b3 Ņ b3 XOR ŅŅ bXOR 3’ Ņ b3’

b2 Ņ b2 XOR ŅŅ bXOR 2’ Ņ b2’

b1 Ņ b1 XOR ŅŅ bXOR 1’ Ņ b1’

9.3. ´abra. A Gray-k´od visszaalak´ıt´asa bin´aris sz´amra Tekints¨ uk p1 ´es p2 Gray-k´odj´at: G(p1 ) = 1 1 0|0 0 0 0 0 G(p2 ) = 0 1 0|0 0 0 0 0 L´athatjuk, hogy a k´et bin´aris sztring k¨oz¨otti Hamming-t´avols´ag val´oban 1. Ha most a keresztez´esnek megfelel˝oen felcser´elj¨ uk a sz¨ ul˝ok k¨oz¨ott a ,,—”-t´ol jobbra es˝o r´eszeket, akkor a sz¨ ul˝okkel ekvivalens lesz´armazottakat kapunk. A bin´arisb´ol Gray-k´odba alak´ıt´as m˝ uvelete a k¨ovetkez˝ok´eppen is le´ırhat´o: (bn , bn−1 , . . . , b2 , b1 )⊗(0, bn , . . . , b3 , b2 ) = (bn ⊗0, bn−1 ⊗bn , . . . , b2 ⊗b3 , b1 ⊗b2 ), ahol ⊗ az XOR (eXclusive OR, ’kiz´ar´o vagy’) m˝ uveletet jel¨oli. L´assuk most annak bizony´ıt´as´at, hogy k´et egym´asut´ani bin´aris sz´am Gray-k´odjainak Hammingt´avols´aga 1. Legyen (bn , bn−1 ⊗ bn , . . . , b2 ⊗ b3, b1 ⊗ b2 ) a b = (bn , . . . , b1 )

´ sok 9. fejezet. Alkalmaza

42

Gray-k´odja, s ugyan´ıgy (dn , dn−1 ⊗ dn , . . . , d2 ⊗ d3 , d1 × d2 ) a d = (dn , . . . , d1 ) ´ Gray-k´odja, a k¨oz¨ott¨ uk lev˝o ¨osszef¨ ugg´es pedig b + 1 = d. Eszrevehetj¨ uk, hogy a Hamming-t´avols´ag tulajdonk´eppen a bitenk´enti XOR m˝ uveletek ¨osszege, ugyanis ez akkor fog 1-et adni egy bitre, ha azok megfelel˝o ´ert´ekei k¨ ul¨onb¨oznek. Vagyis azt kell kimutatnunk, hogy bn ⊗ dn + bn−1 ⊗ bn ⊗ dn−1 ⊗ dn + . . . + b1 ⊗ b2 ⊗ d1 ⊗ d2 = 1. Ha b1 = 0 volt akkor d1 = 1, ´es b ´es d az ¨osszes t¨obbi bitpoz´ıci´oban megegyezik. Ekkor a fenti ¨osszegnek csakis az utols´o tagja fog 1-et szolg´altatni, mivel b1 ⊗ b2 ⊗ d1 ⊗ d2 = b1 ⊗ d1 ⊗ b2 ⊗ d2 = 1 ⊗ 0=1, vagyis a k´et sztring Hamming-t´avos´aga 1. Ha viszont b1 = 1 volt, akkor d1 = 0, ´es a k¨ovetkez˝o k´et eset ´all fenn: (i) b2 = 0, ahonnan k¨ovetkezik, hogy d2 = 1, ´ıgy b1 ⊗ b2 ⊗ d1 ⊗ d2 = 1 ⊗ 1 = 0, ´es ekkor csak a fenti ¨osszeg k¨ovetkez˝o tagj´anak ´ert´eke lesz 1, az ¨osszes t¨obbi tag 0-t eredm´enyez, mert b2 ⊗ d2 = 1 ´es b3 -t´ol (d3 -t´ol) felfel´e minden bit megegyezik b-ben ´es d-ben; (ii) b2 = 1, ahonnan k¨ovetkezik, hogy d2 = 0, ´ıgy u ´jfent z´erus lesz e tag ´ert´eke. Ebben az esetben addig mind z´erus´ert´ek˝ u tagokat kapunk m´ıg b-ben egy 0-hoz nem ´er¨ unk. Ezt az al´abbi p´elda szeml´elteti: b =110111+ 1 d =111000 A fels˝o sz´am a b, m´ıg az eredm´eny, azaz a lenti sz´am a d. L´athat´o, hogy mikor b-ben egy z´erushoz ´er¨ unk, akkor G(b)i 1 lesz, ´es hasonl´oan G(d)i is 1-et szolg´altat, ´ıgy 1 ⊗ 1 = 0. A k¨ovetkez˝o tag eset´eben viszont G(b)i+1 ´es G(d)i+1 k¨ ul¨onb¨ozik, ez´ert ezek ´ert´ekei XOR-ral ¨osszek¨otve 1-et fognak szolg´altatni. Innent˝ol felfel´e viszont megintcsak minden tag ´ert´eke 0 lesz, mivel a bitek p´aronk´ent megegyeznek. A dek´odol´as, vagyis a Gray-k´od visszaalak´ıt´asa bin´aris k´odba az XOR m˝ uvelet tulajdons´ag´at haszn´alja ki, azaz, hogy (a ⊗ b) ⊗ b = a.

9.2.

F¨ uggv´ enyoptimiz´ al´ as val´ os ´ abr´ azol´ assal

9.3.

Nemline´ aris programoz´ as

9.4.

T´ erk´ ep- vagy gr´ afsz´ınez´ esi probl´ ema

Tekints¨ uk a k¨ovetkez˝o probl´em´at. Adott egy t´erk´ep, melyet u ´gy szeretn´enk kisz´ınezni, hogy az egym´assal szomsz´edos ter¨ uletek (orsz´agok, megy´ek, stb.) k¨ ul¨onb¨oz˝o sz´ın¨ uek legyenek. Legyen k a rendelkez´es¨ unkre ´all´o sz´ınek, N pedig a kisz´ınezend˝o ter¨ uletek sz´ama. E probl´em´at gr´afsz´ınez´esi probl´em´anak is szokt´ak

´rke ´p- vagy gra ´ fsz´ıneze ´si proble ´ma 9.4. Te

43

nevezni, mivel egy t´erk´ep gr´afk´ent is ´abr´azolhat´o u ´gy, hogy a gr´af cs´ ucsai jel¨olik a ter¨ uleteket, az egym´assal szomsz´edos ter¨ uleteknek megfelel˝o csom´opontokat pedig ir´any´ıtatlan ´elek k¨otik ¨ossze.

⇒

?>=< 89:; pp 2 =N=NNNN p p == NN ppp == NNN p p p == ?>=< 89:; ?>=< 89:; 1 . HVHVVVVVV h==hhh 3 h .. HHH VVVVhVhVhhhh h === . HhHhhhhh VVVVVVV = VV ?>=< h.h..hh HHHH ?>=< 89:; 7 == . 4 HH k89:; k k HH kkk k == .. H k k ==. kkkHHH kkkk 89:; ?>=< 89:; ?>=< 5 6

Ebben az esetben a gr´af cs´ ucsainak egy olyan sz´ınez´es´et keress¨ uk, ahol a szomsz´edos cs´ ucsok k¨ ul¨onb¨oz˝o sz´ın˝ uek. A probl´ema legegyszer˝ ubb k´odol´asa egy olyan N hossz´ us´ag´ u (s1 , s2 , . . . , sN ) lista, ahol si ∈ {1, 2, . . . , k}, i = 1, 2, . . . , N. Term´eszetesen m´as k´odol´as is alkalmazhat´o, p´eld´aul sorrendi k´odol´ as (ref. l´asd Fut´o, pp. 554–556), ezekre viszont itt nem t´er¨ unk ki. P´eld´aul ha a rendelkez´esre ´all´o sz´ınek sz´ama 3, m´ıg az orsz´agok´e N = 7 akkor egy lehets´eges egyedet a k¨ovetkez˝ok´eppen k´odolunk: s = 1 1 2 3 3 2 1. Az orsz´agok, ter¨ uletek szomsz´edoss´ag´at egy W szomsz´edoss´agi m´atrixban t´arolhatjuk, ahol Wij = 1 ha az i-edik ´es j-edik ter¨ ulet egym´assal szomsz´edos, ´es Wij = 0 k¨ ul¨onben. Ekkor a feladat ´ertelmezhet˝o u ´gy, mint a k¨ovetkez˝o f¨ uggv´eny minimaliz´al´asa: X E(s) = Wij · d(si , sj ), i,j

ahol

¯ d(si , sj ) =

1, ha si = sj 0, k¨ ul¨onben

A fenti minimaliz´aland´o f¨ uggv´ey azon ter¨ uletp´arok sz´am´at adja meg, melyek sz´ıne megegyezik. A problem´at egyszer˝ uen ´atalak´ıthatjuk maximaliz´al´asi feladatra. N´eh´any p´elda r´atermetts´egi f¨ uggv´enyre: r´atermetts´eg(s) = N · (N − 1) − E(s) vagy r´atermetts´eg(s) = e−β·E(s) , ahol a β param´eter a sz´ınegyez´eseket s´ ulyozza. [PKS01] 154. oldal´an is.

A probl´ema megtal´alhat´o a

´ sok 9. fejezet. Alkalmaza

44

9.5.

Az utaz´ ou ¨ gyn¨ ok probl´ em´ aja

Az utaz´o u ¨gyn¨ok probl´em´aja (travelling salesman problem, TSP) az egyik legt¨obbet t´argyalt NP-teljes probl´ema. A feladat a k¨ovetkez˝ok´eppen hangzik. Adott egy u ¨gyn¨ok, akinek adott n v´aroson kereszt¨ ul kell utaznia u ´gy, hogy v´eg¨ ul vissza´erjen a kezdeti v´arosba, ahonnan elindult, ´es u ´gy, hogy az ¨osszess´eg´eben megtett u ´t minim´alis legyen. A kezdeti v´aros tetsz˝oleges (b´ar ez nem igaz´an fedi a val´os´agot), tov´abb´a minden k´et v´aros k¨oz¨ott van u ´t. A feladatot u ´gy is ´ertelmezhetn´enk, mint egy n-edrend˝ u teljes gr´af minim´alis Hamilton-k¨or´enek megtal´al´asa. (A Hamiltonu ´t ´ertelmez´es szerint a gr´af ¨osszes cs´ ucs´at egyszer ´erint˝o u ´t, m´ıg a Hamiltonk¨or z´art Hamilton-utat jelent, vagyis az els˝o ´es utols´o cs´ ucs megegyezik. K´erd´es: melyiket tekintj¨ uk ,,els˝o”-nek?) Legyen V = {1, 2, . . . , n} a v´arosok halmaza, ´es jel¨olje d(i, j), i, j ∈ V a v´arosok k¨oz¨otti t´avols´agot. Form´alisan a feladat a k¨ovetkez˝o: keress¨ uk meg azt a vi , i = 1, . . . , n + 1 sorozatot (vn+1 = v1 ), hogy n X

d(vi , vi+1 )

i=1

minim´alis legyen. A keres´esi ter¨ ulet m´erete n! f¨ uggv´eny, pontosabban (n − 1)!/2. Ez azt jelenti, hogy a megold´as megtal´al´as´ahoz ennyi lehets´eges konfigur´aci´ot kell megvizsg´alnunk, ami m´ar 20 v´aros eset´en 1011 nagys´agrenndel nagyobb, mint ah´any hajsz´al van fej¨ unk¨on, azaz pontosan 60 822 550 204 416 000. Term´eszetesen l´eteznek k¨ozel´ıt˝o megold´asok (tulajdonk´eppen a genetikus algoritmusos megold´as is csak k¨ozel´ıt´esnek nevezhet˝o, mert sajnos a v´egtelen nem rekonstru´alhat´o a sz´am´ıt´og´epen, legal´abbis eleddig), az egyik ilyen egyszer˝ uen Kruskal algoritmusa alapj´an m˝ uk¨odik (minim´alis fesz´ıt˝ofa megkeres´ese gr´afokban), vagyis list´azzuk az ´eleket n¨ovekv˝o sorrendben, majd sorra kiv´alasztjuk azokat, melyek nem okoznak konfliktust. Konfliktus akkor ad´odik, ha egy olyan ´elt akarunk bevinni, amely egy cs´ ucs foksz´am´at 2-r˝ol h´aromra n¨oveli, illetve ha n-n´el r¨ovidebb k¨or alakul ´ıgy ki (egy k¨or hossz´at az ˝ot alkot´o cs´ ucsok sz´am´aval defini´aljuk). Tekints¨ uk a k¨ovetkez˝o p´eld´at: 89:; ?>=< 89:; 2 1 == 10 ?>=< ¢ ¢ ¢ 20==¢ 10 ¢¢== 50 30 == ¢¢ 89:; ?>=< 89:; 3 20 ?>=< 4

Az ´elek n¨ovekv˝ o sorrendben: 12 ? 13 ? 14 34 ? 23 24 ?

´ Ut: 12 312 4312 43124

Bal oldalon a v´arosok ´es a k¨oz¨ott¨ uk lev˝o t´avols´agok l´athat´ok, m´ıg jobb oldalon az el˝obb eml´ıtett algoritmus m˝ uk¨od´ese k¨ovethet˝o nyomon. A csillagok azokat az

´ u ¨ gyno ¨ k proble ´ma ´ ja 9.5. Az utazo

45

´eleket jel¨olik, melyeket bevett¨ unk a v´egs˝o u ´tba, az u ´t alakul´asa pedig a csillagokt´ol jobbra l´athat´o. Ebben az esetben csak 3 lehet˝os´eg¨ unk van, m´egpedig 1 2 3 4 1, 1 3 2 4 1 vagy 2 1 3 4 2, melyek hossza rendre 80, 110 ´es 90. A fenti algoritmus ´altal kapott u ´t viszont innen a m´asodiknak felel meg, amely pedig a leghosszabb, ´ıgy l´athatjuk, hogy ez az algoritmus nem mindig m˝ uk¨odik u ´gy ahogy kellene. ... Egy m´asik lehets´eges reprezent´aci´ot alkothatunk, ha megfigyelj¨ uk, hogy az ¨osszes eddigi reprezent´aci´onk ´altal le´ırt keres´esi t´er n! ´es nem (n − 1)!/2 nagys´ag´ u. El˝osz¨or is n´ezz¨ uk meg, n v´aros eset´en hogyan lesz (n − 1)!/2 lehets´eges megold´asunk. Els˝o l´ep´esben r¨ogz´ıts¨ unk egy cs´ ucsot (v´arost), mert ellenkez˝o esetben a cirkul´aris permut´aci´ok ugyanazt az utat ´ırj´ak le, ´ıgy n-szer t¨obb elrendez´est kapunk, mint ah´any val´oj´aban van. ´Igy eljutunk az (n − 1)!-hoz. Ez ´ıgy m´eg mindig nincs rendj´en, mert ha ´ıgy felsorojuk az ¨osszes lehet˝os´eget, ´eszrevessz¨ uk, hogy minden u ´t k´etszer szerepel, mivel mindegy, hogy balra vagy jobbra indulunk el az ´ıgy kialakul k¨or egy pontj´ab´ol. Enn´elfogva a lehets´eges elrendez´esek sz´ama pontosan (n − 1)!/2. Az u ´j reprezent´aci´o l´enyege az lenne, hogy csak (n − 1)!/2 utat ´ırjon le, vagyis ne tegyen k¨ ul¨onbs´eget az 1 2 3 ´es 2 3 1, illetve a 2 1 3 ´es 3 1 2 utak k¨oz¨ott. Az fenti ,,r¨ogz´ıt´est” u ´gy oldhatjuk meg, ha egyszer˝ uen kihagyunk egy v´arost, amely ´ legyen a maxim´alis sz´ammal ell´atott v´aros. Igy csak n − 1 v´aros permut´aci´oit fogjuk vizsg´alni. Mostm´ar csak a m´asodik pontot kell valahogyan megoldanunk, azaz, hogy egy u ´t ´es annak t¨ uk¨ork´epe ugyanazzal a reprezent´aci´oval rendelkezzen. Egy lehets´eges megold´as a kor´abban m´ar bemutatott m´atrix-reprezent´aci´ohoz hasonl´ıt, azzal az elt´er´essel, hogy most a szomsz´edoss´agi m´atrixban mind i ´es j szomsz´edoss´aga eset´en mind az (i, j), mind a (j, i) poz´ıci´ora 1-et ´ırunk. Mivel a m´atrix szimmetrikus a f˝oa´tl´ora n´ezve, elegend˝o csak a f˝oa´tl´o alatti vagy a f˝oa´tl´o feletti r´esszel foglalkoznunk. V´alasszuk a f˝o´atl´o alatti r´eszt. Az elemek sz´ama ebben a h´aromsz¨ogm´atrixban (n − 1) · (n − 2)/2. Ez a m´atrix akkor fog egy lehets´eges konfigur´aci´ot ´abr´azolni, ha benne az 1-esek sz´ama n − 2, a t¨obbi elem pedig z´erus. ´Igy p´eld´aul – 5 v´aros eset´en – az 2 3 4

1 1 0 0 1 0 1

2

3

a 4 2 1 3 (5) bej´ar´ast ´abr´azolja, vagy u ´gy is mondhatjuk, hogy a 4 2 1 3 (5) egyed¨ uli reprezent´aci´oja a fenti h´aromsz¨ogm´atrix (a f´elk¨ov´er sz´amok a sorok, illetve oszlopok index´et jel¨olik). Viszont valamit elhallgattunk a fenti ´abr´azol´asm´oddal kapcsolatoban. Mivel a m´atrix elemeinek sz´ama n v´aros eset´en (n − 1)(n − 2)/2, amib˝ol n−2 elemnek 1-nek kell lennie,¡ez´ert a fenti¢ reprezent´aci´oval le´ırhat´o elrendez´esek sz´ama nem (n−1)!/2, hanem (n−1)(n−2)/2 (ami egy bizonyos n-t˝ol kezdve n−2

´ sok 9. fejezet. Alkalmaza

46

nagyobb, mint az els˝o ¨osszef¨ ugg´es). Vagyis bizonyos megk¨ot´eseket kell tenn¨ unk a z´erusokkal ´es egyesekkel kapcsolatban, m´egpedig a k¨ovetkez˝o kett˝ot: 1. az 1-esek sz´ama b´armely sorban ´es oszlopban maximum kett˝o lehet, 2. a le´ırt gr´afban nem lehet k¨or. Az els˝o felt´etel vil´agos ´es k¨onnyen ellen˝orizhet˝o. N´ezz¨ uk a m´asodikat. Egy szomsz´edoss´agi m´atrix ´altal le´ırt gr´af akkor tartalmaz k¨ort, ha egy i cs´ ucsb´ol eljuthatunk egy j cs´ ucsba, majd a j cs´ ucsb´ol visszajuthatunk az i-be egy m´asik u ´ton. Vagyis k i◦

l

j◦

◦

konfigur´aci´o eset´en, amikor i = l. Mert ekkor egy i j k i alak´ uu ´thoz jutunk, ami term´eszetesen egy k¨ort ´ır le. Teh´at mindig ellen˝orizn¨ unk kell, hogy a popul´aci´o inicializ´al´asakor, mut´aci´o, illetve keresztez´eskor ´erv´enyes egyedet kapjunk. A lehets´eges mut´aci´okat ´es keresztez´eseket az olvas´o k´epzelet´ere b´ızzuk.

9.6.

SAT

A r¨ovid´ıt´es SAT az angol Boolean Satisfiability Problem elnevez´esb˝ol ered, melyet magyarul Boole-kiel´eg´ıthet˝os´egi probl´em´anak nevez¨ unk, azonban a r¨ovids´eg miatt az angol SAT elnevez´est r´eszes´ıtj¨ uk el˝onyben, ´es a tov´abbiakban ´ıgy fogunk r´a hivatkozni. A SAT probl´ema – egyszer˝ uen megfogalmazva – abban ´all, hogy egy ´ıt´eletkalkulusbeli formul´anak keress¨ uk meg egy olyan interpret´aci´oj´at (azaz a hamis ´es igaz [vagy 0 ´es 1] olyan hozz´arendel´eseit), amely a formul´at igazk´ent ´ert´ekeli ki. Az ´ıt´eletkalkulusban (vagy nulladrend˝ u predik´atumkalkulusban) nincsenek kvantorok, vagyis csak ´ıt´eletszimb´olumok, z´ar´ojelek ´es logikai m˝ uveleti jelek (neg´aci´o, konjunkci´o, diszjunkci´o, implik´aci´o ´es ekvivalencia) l´eteznek. P´eld´aul az A∨A↔1 egy ´ıt´eletkalkulusbeli formula, egyben logikai t¨orv´eny (az ekvivalencia jelt˝ol balra es˝o r´eszt tautol´ogi´anak nevezz¨ uk, mert annak minden interpret´aci´oja igaz). A SAT ugyancsak NP-teljes probl´ema, ez´ert egy lehets´eges megold´as megkeres´es´ehez itt is gyakran genetikus algoritmusokat alkalmaznak. Ennek a feladatnak a genetikus algoritmusok szempontj´ab´ol n´ezve az az ´erdekess´ege, hogy m´ıg a reprezent´aci´o szinte mag´at´ol ad´odik, el´eg neh´ez j´o ´es hat´ekony r´atermetts´egi

47

9.6. SAT

f¨ uggv´enyt tal´alni a megold´ashoz. Ha adott egy n darab ´ıt´eletv´altoz´ot tartalmaz´o formula, akkor annak evidens reprezent´aci´oja azon n hossz´ us´ag´ u kromosz´oma, ahol minden g´en egy v´altoz´onak felel meg a formul´ab´ol. Egy g´en ´ert´eke (all´elja) csak 0 ´es 1 lehet, ´es az adott v´altoz´ohoz rendelt igazs´ag´ert´eket tartalmazza. P´eld´aul ha adott a k¨ovetkez˝o formula: (A ∨ B) ∧ A ∧ C, akkor a kromosz´om´ank (b1 , b2 , b3 ) alak´ u lesz, ahol b1 A, b2 B, b3 pedig C ´ert´ek´et reprezent´alja (ennek a formul´anak az egyetlen igaz ´ert´ek˝ u interpret´aci´oja (1, 1, 1)). R´atermetts´egi f¨ uggv´enyk´ent tekinthetn´enk egyszer˝ uen a formula igazs´ag´ert´ek´et, viszont ezzel az a probl´ema, hogy csak 0 ´es 1 ´ert´eket vehet fel, ´es az esetek nagy t¨obbs´eg´eben ez sajnos 0 lesz, vagyis a popul´aci´onkat fejl˝od´es´et nem tudjuk a helyes ir´anyba terelni, nem tudnunk k¨ ul¨onbs´eget tenni k´et hamis formula k¨oz¨ott. Egy m´asik – imm´ar haszn´alhat´o – lehet˝os´eg az lenne, hogy el˝osz¨or a formul´at konjunkt´ıv norm´al form´ara (= diszjunkci´ok konjunkci´oja) hozzuk, majd r´atermetts´egk´ent ¨osszeadjuk az elemi diszjunkci´ok igazs´ag´ert´ek´et, megsz´aml´alva ezzel a konjunkt´ıv norm´al forma 1 igazs´ag´ert´ek˝ u elemeit. Ehhez azonban a formul´at el˝osz¨or konjunkt´ıv norm´al form´ara kell hoznunk. Ezt a k¨ovetkez˝ok´eppen tehetj¨ uk meg (ref. in Fut´o Iv´an, 132 old): 1. K¨ usz¨ob¨olj¨ uk ki az implik´aci´o ´es ekvivalencia jeleket az al´abbi szab´alyok seg´ıts´eg´evel: A ↔ B ≡ (A → B) ∧ (B → A) A→B≡A∨B 2. Reduk´aljuk a logikai tagad´asok hat´ask¨or´et, azaz vigy¨ uk ˝oket k¨ozvetlen¨ ul a logikai v´altoz´ok f¨ol´e (vagy mell´e, ha a m´asik szok´asos jel¨ol´est haszn´aljuk). Ezt a k¨ovetkez˝o szab´alyokat felhaszn´alva tehetj¨ uk meg: A∧B≡A∨B A∨B≡A∧B A≡A 3. Alkalmazzuk a disztributivit´as t¨orv´enyeit: A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) A fenti m´odszerrel ezut´an k¨onnyen ki tudjuk sz´amolni egy egyed r´atermetts´eg´et, csup´an annyi a probl´ema, hogy az el˝obb ismertetett algoritmus nem line´aris. Ez´ert egy m´asik r´atermetts´egi f¨ uggv´eny ut´an n´ez¨ unk. Tekints¨ uk a k¨ovetkez˝o ki´ert´ekel´esi szab´alyokat:

´ sok 9. fejezet. Alkalmaza

48 1. val(e) = 1 − val(e)

2. val(e1 ∧ e2 ∧ . . . ∧ en ) = min(val(e1 ), val(e2 ), . . . , val(en )) 3. val(e1 ∨ e2 vee . . . ∨ en ) = max(val(e1 ), val(e2 ), . . . , val(en )), ahol e, e1 ´es e2 formul´akat jel¨olnek. Mivel minden formula ´ert´eke csak 0 vagy 1 lehet, ez´ert k¨onnyen bel´athat´o, hogy a fenti rekurz´ıv m´odon ´ertelmezett val f¨ uggv´eny ´ert´ekk´eszlete ugyancsak a {0, 1} halmaz lesz. Viszont egy kis v´altoztat´assal a r´atermetts´egi f¨ uggv´eny ´ert´ekk´eszlete intervallumm´a alak´ıthat´o ([DS89]): val(e1 ∧ e2 ∧ . . . ∧ en ) = avg(val(e1 ), val(e2 ), . . . , val(en )) ´Igy a fenti p´eld´ank neh´any interpret´aci´oj´ahoz a k¨ovetkez˝o r´atermetts´egi ´ert´ekeket rendelhetj¨ uk: A B C 1 0 0 0 0 1 0 1 1 1 1 1

(A ∨ B) ∧ A ∧ C 1 3 2 3 2 3

1

Viszont van n´eh´any probl´ema ezzel a r´atermetts´eg-kisz´am´ıt´assal, m´egpedig az, hogy az avg (average, ’´atlag’) f¨ uggv´eny nem invari´ans az ´ıt´eletkalkulusbeli ekvivalenci´akra n´ezve. P´eld´aul A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C, viszont

A+B A + B+C +C 2 6= 2 . 2 2 Ugyan´ıgy a De Morgan-t¨orv´enyek sem ´erv´enyesek, vagyis

A ∨ B ≡ (A ∧ B), viszont max(A, B) 6=

A+B . 2

´Igy p´eld´aul a (0, 0)-n k´ıv¨ ul a (A ∧ B) formula ¨osszes t¨obbi interpret´aci´oja igaz, viszont a (0, 1) ´es (1, 0) interpret´aci´okra 0.5-¨ot kapunk, pedig ezek is ´ ugyan´ ugy helyesek, mint az (1, 1). Altal´ anosan kimutathat´o, hogy az ´ıgy meg´ep´ıtett r´atermetts´egi f¨ uggv´eny nem rendel 1-et hamis interpret´aci´okhoz, de

´ lyno ˝ proble ´ma ´ ja 9.7. A 8 kira

49

gyakran rendel 1-n´el kisebb ´ert´eket bizonyos megold´asokhoz, ´es ez kisebb is lehet, mint a hamis interpret´aci´okhoz rendelt ´ert´ek. De Jong ´es Spears ([DS89]) r´aj¨ottek arra, hogy ilyen jelleg˝ u probl´ema csak akkor ad´odik, ha a formul´aban (e1 ∧ e2 ∧ . . . ∧ en ) alak´ u r´eszformul´ak szerepelnek. Ezeket ´atalak´ıtva, azaz alkalmazva a De Morgan szab´alyt, a probl´ema kik¨ usz¨ob¨olhet˝o. Azt is ´eszrevett´ek, hogy az (e1 ∨ e2 ∨ . . . ∨ en ) alak´ u r´eszformul´ak, ahol e1 , . . . , en csak 0 ´es 1 ´ert´eket vesz fel, 0 vagy 1 r´atermetts´eget eredm´enyez. Ha viszont itt is alkalmazzuk a megfelel˝o De Morgan t¨orv´enyt, akkor a r´atermetts´eget az avg ir´any´ıtja, amely nagyobb ´ert´eket rendel a ,,jobb” interpret´aci´okhoz. Egy m´asik m´odos´ıt´ast is tehet¨ unk, m´egpedig hogy az avg helyett az avgp f¨ uggv´enyt haszn´aljuk, vagyis az avg p-edik hatv´any´at. Ha p v´egtelenbe tart, akkor az avgp a min f¨ uggv´enyhez hasonl´ıt. De Jong ´es Spears a legjobb eredm´enyeket p = 2 eset´en kapta.

9.7.

A 8 kir´ alyn˝ o probl´ em´ aja

Feladatunk a k¨ovetkez˝o: helyezz¨ unk el egy tetsz˝oleges N × N m´eret˝ u sakkt´abl´an N darab kir´alyn˝ot u ´gy, hogy azok ne ,,¨ uss´ek” egym´ast, azaz ne legyen konfliktus k¨oz¨ott¨ uk. Konfliktus akkor ad´odik, ha k´et kir´alyn˝o ugyanazon sorban, ugyanazon oszlopban, vagy ugyanazon ´atl´on helyezkedik el. Az eredeti feladat egy 8 × 8-as sakkt´abl´ara vonatkozott, viszont ez kiterjeszthet˝o tetsz˝oleges m´eretre. A probl´em´at el˝osz¨or Gauss vetette fel 1850-ben. A feladatot sokszor u ´gy fogalmazz´ak meg, hogy keress¨ uk meg az az N kir´alyn˝o ¨osszes lehets´eges ilyen elrendez´es´et. Hab´ar ennek (gyors) megold´as´ara sok hat´ekony heurisztikus algoritmus sz¨ uletett az ´evek sor´an, a 8 kir´alyn˝o probl´am´aj´at szinte mindenki a backtracking programoz´asi technik´aval asszoci´alja. L´athatjuk, hogy a keres´esi ter¨ ulet N nagyon nagy, m´erete N vagyis exponenci´alis, ´es ´ıgy a megold´asok sz´ama is exponenci´alisan n¨ovekszik N f¨ uggv´eny´eben. M´ıg 8 kir´alyn˝o eset´en 92 megold´as l´etezik (12 egyedi megold´as, vagyis figyelmen k´ıv¨ ul hagyva azokat, melyek egy m´ar feljegyzett megold´as forgat´assal vagy t¨ ukr¨oz´essel kapott m´asai), 16 kir´alyn˝o eset´en 14 772 512 (melyb˝ol 1 846 955 egyedi megold´as), 20 kir´alyn˝o eset´en 39 029 188 884 (melyb˝ol 4 878 666 808 egyedi) megold´asunk van1 . Genetikus algoritmussal egyetlen megold´ast keres¨ unk. Reprezent´aci´onk legyen a k¨ovetkez˝o alak´ u: (q1 , q2 , . . . , qN ), ahol qi azt jel¨oli, hogy a sakkt´abla i-edik sor´anak qi -edik oszlop´aban egy kir´alyn˝o tal´alhat´o. P´eld´aul a q = (1, 5, 8, 6, 3, 7, 2, 4) 1

Az adatok a http://www.durangobill.com/N Queens.html oldalr´ol sz´armaznak

´ sok 9. fejezet. Alkalmaza

50

egy lehets´eges megold´as 8 × 8-as sakkt´abla eset´en (a sorokat a balfels˝o sarokt´ol lefel´e, az oszlopokat pedig balr´ol jobbra indexelj¨ uk; l´asd a 9.4. ´abr´at). Ezt a reprezent´aci´ot haszn´alva m´ar eleve megoldottuk azt a probl´em´at, hogy egy sorba, illetve egy oszlopba csak egyetlen kir´alyn˝o ker¨ ulhet.

9.4. ´abra. Egy lehets´eges megold´as 8 kir´alyn˝o eset´en K¨onnyen ´eszrevehet˝o, hogy a f˝oa´tl´on vagy a f˝o´atl´oval p´arhuzamos ´atl´on akkor k¨ovetkezik be u ¨tk¨oz´es, ha a poz´ıci´ok koordin´at´ainak ¨osszege megegyezik, azaz ∃i, j u ´gy, hogy i + qi = j + qj , vagyis, ha qi − qj = j − i. A mell´ek´atl´on vagy a mell´ek´atl´oval p´arhuzamos ´atl´on pedig akkor, hogyha ∃i, j u ´gy, hogy i − qi = j − qj , vagyis ha qi − qj = i − j. Ezeket ¨osszevonva fel´ırhatjuk, hogy akkor ´es csakis akkor van u ¨tk¨oz´es, ha qi − qj = ±(i − j), vagyis ha |qi − qj | = |i − j|. Ez alapj´an k¨onnyen fel´ırhatjuk a r´atermetts´egi f¨ uggv´eny¨ unket, ami r´atermetts´eg(q) =

N−1 X

N X

δ(|qi − qj | − |i − j|),

i=1 j=i+1

ahol

¯

1, ha x = 0 0, k¨ ul¨onben Keresztez´esk´ent haszn´alhatjuk a bin´aris ´abr´azol´asi m´odn´al is haszn´alt egypontos kereszt´est, m´ıg mut´aci´okor egyszer˝ uen gener´alhatunk egy v´eletlen sz´amot az {1, 2, . . . , N} halmazb´ol minden mut´aci´ora kiv´alasztott g´en eset´en, s a g´en u ´j ´ert´eke ez a sz´am lesz. Egy m´asik p´eld´at is adunk a r´atermetts´egi f¨ uggv´enyre. Egy q = (q1 , q2 , . . . , qN ) sorozat akkor megold´as, hogyha a k¨ovetkez˝o felt´etelek teljes¨ ulnek: δ(x) =

N X i=1 i+qi =k

1 ≤ 1, k = 2, 3, . . . , 2N,

´gia ´ k kerese ´se genetikus algoritmusokkal 9.8. Strate N X

51

1 ≤ 1, k = −(N − 1), −(N − 2), . . . , N − 1.

i=1 i−qi =k

Az els˝o felt´etel azt fejezi ki, hogy a f˝oa´tl´on vagy a f˝oa´tl´oval pa´arhuzamos ´atl´okon egy vagy z´erus darab kir´alyn˝o ´allhat, a m´asodik felt´etel pedig ugyanezt ´ırja le a mell´ek´atl´ora ´es az azzal p´arhuzamos ´atl´okra. ´Igy fel´ırhatjuk a k¨ovetkez˝o k´et b¨ untet˝of¨ uggv´enyt:         2N N   X  X    g1 (q) = max 0,  1 − 1 ,     k=2 i=1   i+qi =k

    N N−1   X X  g2 (q) = max 0,    k=−(N−1) i=1 

i−qi =k

      1 − 1 .    

Mivel e f¨ uggv´enyek maxim´alis ´ert´eke p´aronk´ent N − 1, ez´ert r´atermetts´egi f¨ uggv´enyk´ent v´alaszthatjuk p´eld´aul a k¨ovetkez˝o kifejez´est: r´atermetts´eg(q) = 2(N − 1) − (g1 (q) + g2 (q)) .

9.8.

Strat´ egi´ ak keres´ ese genetikus algoritmusokkal

9.8.1.

A fogoly-dilemma

9.8.2.

Tic-tac-toe

9.8.3.

A ragadoz´ o´ es zs´ akm´ any probl´ em´ aja

9.9.

Klaszterez´ es genetikus algoritmusokkal

A klaszterez´es (az angol clustering sz´ob´ol) nagy fontoss´ag´ u feladat a matematik´aban ´es az informatik´aban. A g´epi tanul´asban nem-fel¨ ugyelt tanul´asnak is nevezik, ami azt jelenti, hogy a rendszer el˝oz˝oleg nem l´at egyetlen tanul´asi p´eld´at sem, vagyis a rendszert nem tan´ıtjuk, nem-fel¨ ugyelt m´odon mag´at´ol tanul. A feladat u ´gy sz´etv´alasztani az adatpontokat, hogy a felismert k¨ ul¨onb¨oz˝o halmazokban (klaszterekben) a pontok min´el jobban hasonl´ıtsanak egym´ashoz, m´ıg a k¨ ul¨onb¨oz˝o halmazokban lev˝o pontok min´el jobban elt´erjenek egym´ast´ol. A klaszterez´esi

´ sok 9. fejezet. Alkalmaza

52

probl´em´at sok ir´anyb´ol meg lehet k¨ozel´ıteni, ez´ert hatalmas irodalommal rendelkezik. Mivel ez a k¨onyv nem klaszterez´essel ´es g´epi tanul´assal foglalkozik, nem v´azolom a k¨ ul¨onb¨oz˝o ir´anyokat ´es a klaszterez´esi met´odusokat. Ilyen szempontb´ol nagyon j´o ´attekint´est ny´ ujt Belkhin cikke (belkhin) vagy Jain ´es Dubes ,,Algorithms for Clustering Data” (jain...) k¨onyve. Ebben a r´eszben k´et ismert megk¨ozel´ıt´est fogunk megvizsg´alni genetikus szempontb´ol. Az egyik egy particion´al´o algoritmus, a k-k¨ozpont´ u klaszterez´es (angolul k-means), a m´asik pedig a normaliz´alt v´ag´ason alapul´o gr´af-klaszterez´es. A klaszterezni k´ıv´ant adatpontok xi ∈ Rn , i = 1, . . . , m, ´es felt´etelezz¨ uk, hogy a klaszterek sz´ama ismert, ´espedig K.

9.9.1.

K-k¨ ozpont´ u klaszterez´ es

K-k¨ozpont´ u klaszterez´eskor a k¨ovetkez˝o f¨ uggv´enyt akarjuk minimiz´alni, F=

K X

Fi =

i=1

m K X X

Uij · kxj − ci k2 ,

i=1 j=1

ahol K a klaszterek sz´am´at, xj az adatpontokat ´es ci a klaszterk¨oz´eppontokat jel¨oli, U pedig az u ´gynevezett hozz´arendel´esi m´atrix, azaz Uij = 1 ha xj az iedik klaszterhez tartozik, k¨ ul¨onben z´erus, i = 1, . . . , K, j = 1, . . . , m. Az U hozz´arendel´esi m´atrixra az al´abbi megszor´ıt´asokat tessz¨ uk, K X

Uij = 1 ∀j;

i=1

m X

Uij ≥ 1 ∀i,

(∗)

j=1

vagyis egy pont csak egy klaszterhez tartozhat ´es nem lehetnek u ¨res klaszterek, vagyis minden klaszterhez legal´abb egy pontnak tartoznia kell. Az F ¨osszef¨ ugg´est egy iterat´ıv m´odszerrel minimiz´alhatjuk, amit Lloyd-algoritmusnak nevez¨ unk. Ha F-et ci szerint deriv´aljuk, majd egyenl˝ov´e tessz¨ uk z´erussal, a k¨ovetkez˝o ¨osszef¨ ugg´eshez jutunk, ∂F =0 ∂ci m m X X 2 Uij ci − 2 Uij xj = 0 j=1

j=1

Pm j=1 Uij xj ci = Pm , j=1 Uij

vagyis akkor lesz minim´alis, ha a klaszterk¨oz´eppontoknak a pontok k¨ozep´et (´atlag´at) v´alasztjuk. Ekkor az F-et xj szerint u ´gy minimiz´aljuk, hogy minden

´s genetikus algoritmusokkal 9.9. Klasztereze

53

pontot hozz´arendel¨ unk a hozz´a legk¨ozelebb ´all´o klaszterk¨oz´epponthoz, klaszterhez, mivel kxj − ci k ekkor lesz minim´alis. Lloyd algoritmusa a k¨ovetkez˝ok´eppen v´azolhat´o: 1. Rendelj¨ uk a pontokat v´eletlenszer˝ uen a K klaszterhez u ´gy, hogy a hozz´arendel´esi m´atrix teljes´ıtse a (∗) felt´eteleket. 2. Sz´amoljuk ki a klaszterek k¨oz´eppontjait. 3. Minden pontot rendelj¨ unk a hozz´a legk¨ozelebb es˝o klaszterhez a k¨oz´eppont alapj´an. 4. Ism´etelj¨ uk az elj´ar´ast a 2. l´ep´est˝ol m´ıg U m´ar nem v´altozik. A K-k¨ozpont´ u klaszterez´es legnagyobb h´atr´anya – euklideszi t´avols´agot haszn´alva –, hogy csak line´arisan sz´etv´alaszthat´o klasztereket k´epes helyesen megtal´alni. Ezeket sem minden esetben helyesen hat´arozza meg, mivel a v´egs˝o hozz´arandel´es nagyban f¨ ugg a kezdeti hozz´arendel´est˝ol, ez´ert ´atal´aban t¨obbsz¨or futtatjuk egym´as ut´an az algoritmust k¨ ul¨onb¨oz˝o kezdeti hozz´arendel´esekre. A line´arisan nem sz´etv´alaszthat´o klaszterek eset´en a K-k¨ozpont´ u klaszterez´es kerneliz´ alt v´altozat´at haszn´alhatjuk ([DGK04], [VM02]). A K-k¨ozpont´ u klaszterez´es egy m´odos´ıtott v´altozata a fuzzy K-k¨ozpont´ u klaszterez´es ([Ped05]), amely annyiban t´er el az els˝o v´altozatt´ol, hogy egy pont ak´ar t¨obb klaszterhez is tartozhat. A (∗) felt´etelek itt is ´erv´enyesek, viszont az U m´atrix m´ar nem csak z´erusokat ´es egyeseket tartalmazhat, hanem Uij ∈ [0, 1].

9.9.2.

Gr´ af-klaszterez´ es

A gr´af-klaszterez´esek alapj´at az adatpontok hasonl´os´aga alapj´an fel´ep´ıtett gr´af k´epezi. Ezen a gr´afon dolgozva megpr´ob´aljuk min´el jobban sz´etv´alasztani a j´ol ¨osszef¨ ugg˝o komponenseket. A legegyszer˝ ubb gr´af-klaszterez´es Kruskal algoritmusa, amely egy tetsz˝oleges (¨osszef¨ ugg˝o) gr´af minim´alis fesz´ıt˝of´aj´at hat´arozza meg. Az algoritmus u ´gy m˝ uk¨odik, hogy n¨ovekv˝o sorrendbe rendezz¨ uk az ´eleket, majd az ´ıgy kapott n¨ovekv˝o sorrendbe rendezett lista elej´et˝ol a v´ege fel´e haladva kiv´alasztunk ´eleket, felt´eve, hogy azok nem k´epeznek k¨ort a m´ar kiv´alasztott ´elekkel; ha igen, akkor azt az ´elt nem v´alasztjuk ki. Ez u ´gy haszn´alhat´o fel klaszterez˝o algoritmusk´ent, hogy addig folytatjuk a fenti elj´ar´ast, m´ıg K ¨osszef¨ ugg˝o komponenst kapunk. A gr´af-klaszterez´esek egy nagy oszt´aly´at a minim´alis v´ag´assal t¨ort´en˝o klaszterez´esek k´epezik. Egy v´ag´as alatt egy olyan ´elhalmazt ´ert¨ unk, melynek elt´avol´ıt´asa ut´an a gr´af nem marad ¨osszef¨ ugg˝o, hanem k´et ¨osszef¨ ugg˝o komponensre bomlik. Minim´alis v´ag´as keres´esekor mindig meg kell hat´aroznunk a gr´af

´ sok 9. fejezet. Alkalmaza

54

2 2

1

3

3

4 3 1

5 2

4

1

9.5. ´abra. k´et pontj´at, melyek k¨oz¨ott a minim´alis v´ag´ast keress¨ uk, ´es a v´ag´ast u ´gy keress¨ uk, hogy az egyik pont az els˝o, a m´asik a m´asodik komponensben legyen. P´eld´aul a 9.5. ´abr´an l´athat´o gr´af eset´en az 1 ´es 2 cs´ ucsok k¨oz¨otti minim´alis v´ag´as ´ert´eke 2 + 1 + 1 = 4, amely az S = {1, 3}, T = {2, 3, 4} cs´ ucsokat tartalmaz´o komponenseket eredm´enyezi. A minim´alis v´ag´as azt az ´elhalmazt jelenti, melyek minim´alis k¨olts´eg˝ uek, ´es elt´avol´ıt´asuk k´et ¨osszef¨ ugg˝o komponensre bontja a gr´afot, vagyis j´ol haszn´alhat´o klaszterez´esre. Ha csak k´et klaszter¨ unk van, akkor egyszer˝ uen megkeress¨ uk a minim´alis v´ag´ast minden k´et pont eset´en, ´es ezek k¨oz¨ ul a minim´alis ´ert´ek˝ ut v´alasztjuk. T¨obb klaszter eset´en a Gomory-Hu algoritmust haszn´alhatjuk. Ezzel az algoritmussal magkapjuk egy gr´af minim´alis v´ag´asait. Az algoritmus a k¨ovetkez˝ok´eppen m˝ uk¨odik: 1. Kiv´alasztunk k´et cs´ ucsot ugyanabb´ol a komponensb˝ol. 2. Megkeress¨ uk a minim´alis v´ag´ast ezen cs´ ucsok k¨oz¨ott. 3. Annyi u ´j jel¨oletlen cs´ ucsot hozunk l´etre ah´any m´ar l´etez˝o komponenshez a cs´ ucsok k¨ot˝odtek. 4. A cs´ ucsokat ¨osszek¨otj¨ uk a jel¨oletlen cs´ ucsokkal u ´gy, hogy a hozz´arendelt s´ uly az adott cs´ ucsb´ol a m´asik komponensbe men˝o s´ ulyok ¨osszege lesz. 5. A jel¨oletlen cs´ ucsokat ¨osszek¨otjuk, ´es a minim´alis v´ag´as ´ert´ek´et rendelj¨ uk hozz´a s´ ulyk´ent. 6. Vissza a 1-es l´ep´esre. A 9.6. ´abra a Gomory-Hu algoritmus l´ep´eseiben kapott gr´afokat mutatja. Az utols´o l´ep´esben, 9.6/(f), megkapjuk a gr´afot (f´at), melyb˝ol kiolvashat´o b´armely k´et cs´ ucs k¨oz¨otti minim´alis v´ag´as ´ert´eke u ´gy, hogy a k´et cs´ ucs k¨oz¨otti u ´ton szerepl˝o ´ ´elek s´ ulyai k¨oz¨ ul kiv´alasztjuk a minimumot. Igy p´eld´aul az 1 ´es 2 cs´ ucsok k¨oz¨otti minim´alis v´ag´as ´ert´eke 4, ami megfelel a 9.5. ´abr´an kapott ´ert´eknek. A klasztereket

´s genetikus algoritmusokkal 9.9. Klasztereze

4

2 2 3

1

5

3

4

2

2

1

3

55

2

4

1

(a)

(b) 4 s1

2

1

s3

3

4

5

3

1

3

6

s2

4

1

3

1

6

s1

2

3

2

6

s2

6

2

3

5

3

4

s5

4 3

s4

1

4 s1

4 2

1

s6

2

1 s3

3

4

2

6

s2

2

3

6

5

4

s4

2

3

(c) 3

4

(d)

s5

4 3

1

s6

2

1 s3

4

4 5

s4

3

2 s8

7

5

2

s7

4

2 s1

6

s2

6

5

3

4

1

4

(e)

4

7

2

6

5

(f) 9.6. ´abra.

most u ´gy kaphatjuk meg, hogy egyszer˝ uen elt´avol´ıtjuk az ´eleket a f´ab´ol, n¨ovekv˝o sorrendben. P´eld´aul 2 klaszter eset´en {3}, {1, 4, 2, 5} vagy {3, 1}, {4, 2, 5}, 3 klaszter eset´en a {3}, {1}, {4, 2, 5} komponenseket kapjuk. Normaliz´ alt v´ ag´ ason alapul´ o gr´ af-klaszterez´ es P K K X X w(a, b) Pa∈Ci ,b∈Ci G= Gi = a∈Ci ,b∈V w(a, b) i=1 i=1

56

´ sok 9. fejezet. Alkalmaza

Irodalomjegyz´ ek [Aga01]

Alexandru Agapie. Theoretical analysis of mutation-adaptive evolutionary algorithms. Evolutionary Computation, 9(2):127–146, 2001.

[DGK04] Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In Won Kim, Ron Kohavi, Johannes Gehrke, and William DuMouchel, editors, KDD, pages 551– 556. ACM, 2004. [DS89]

Kenneth A. De Jong and William M. Spears. Using genetic algorithm to solve NP-complete problems. In James D. Schaffer, editor, Proc. of the Third Int. Conf. on Genetic Algorithms, pages 124–132, San Mateo, CA, 1989. Morgan Kaufmann.

[GM00]

David Greenhalgh and Stephen Marshall. Convergence criteria for genetic algorithms. SIAM J. Comput, 30(1):269–282, 2000.

[GZ01]

Garrison W. Greenwood and Qiji Zhu. Convergence in evolutionary programs with self-adaptation in evolution strategies. Evolutionary Computation, 9(2):147–157, 2001.

[HH98]

Randy I Haupt and Sue Ellen Haupt. Practical Genetic Algorithms. John Wiley and Sons, New York, 1998.

[Mic96]

Zbigniew Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, third edition, 1996.

[Mit96]

M. Mitchell. An Introduction to Genetic Algorithms. The MIT Press, 1996.

[Ped05]

Witold Pedrycz. Knowledge-Based Clustering: From Data to Information Granules. Wiley, 2005.

[PKS01] Georgios Paliouras, Vangelis Karkaletsis, and Constantine D. Spyropoulos, editors. Machine Learning and Its Applications, Advanced Lectures, volume 2049 of Lecture Notes in Computer Science. Springer, 2001. 57

58

´ IRODALOMJEGYZEK

[Rud94] G¨ unter Rudolph. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, 5(1):96–101, 1994. [Rud98] G¨ unter Rudolph. Finite Markov chain results in evolutionary computation: A tour d’horizon. Fundamenta Informaticae, 35:67–89, 1998. [VM02]

S.V.N. Vishwanathan and Narasimha M. Murty. Kernel enabled Kmeans algorithm. Technical report, January 01 2002.