Matematika | Felsőoktatás » Genetikus algoritmusok Markov-lánc modellje

ELT E Term e szettudom a nyi Kar Opera cio kutata s Tansze k Genetikus algoritmusok Markov-lanc modellje Szakdolgozat Kesztette: Boncz Andra s Temavezet}o: Kova cs M argit Docens 1996. T a r ta lo m je g y z e k Bevezetes . I. Markov-lancok I.1 Markov-lancok dencioi I.2 Markov-lancok allapotainak jellemzese I.3 Markov-lancok hatareloszlasa II. A ltalanos modell II.1 Alapvet}o denciok II.2 Genetikus ter . II.3 Szelekcio II.4 Mutacio II.5 Keresztezes . II.6 Fitness III. Genetikus algoritmusok III.1 Denciok III.2 Eredmenyek Koszonetnyilvantas . Irodalomjegyzek . {i{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 3 3 6 9 9 10 12 13 15 16

18 18 18 20 21 B e v e z e t e s Az utobbi id}oben egyre hangsulyosabb szerepet kapnak a kulonboz}o keres}o algoritmusok. Alapvet}oen ket kulonboz}o tpusu keresesi feladat van: a) sz}ukebb ertelemben vett kereses: adott tulajdonsagu elem keresese, illetve b) optimalizalas: egy adott relacio szerinti legjobb elem keresese. A ket feladat ekvivalens egymassal, mivel az is egy tulajdonsag, hogy valamely elem egy adott relacio szerint a legjobb es ugy is denialhatunk egy relaciot, hogy minden elemhez, melynek megvan a keresett tulajdonsaga, 1-t rendelunk, a tobbihez pedig 0-t. Ennek ellenere a ket kulonboz}o megfogalmazas gyokeresen elter}o megoldasi modszereket igenyelhet. Jelen dolgozatban csak az optimalizalas egy lehetseges modszerer}ol lesz szo. A legkezenfekv}obb modszer -amely mindket megfogalmazas eseten hasznalhato- a leszamlalas. Ez abbol all, hogy az ember az osszes szobajohet}o elemet megvizsgalja, ekkor

el lehet donteni, hogy melyik a legjobb. Ennek termeszetesen megvan az a hatranya, hogy sok ideig tart, ha nagy a keresesi ter. A folytonos keres}o modszerekien (pl. Newton- ill gradiens-modszer) alapulo moho algoritmus akkor hasznalhato, ha a keresesi ternek van valamilyen szomszedsagi strukturaja. Ekkor kiindulva egy tetsz}oleges elemb}ol, a szomszedai kozul a legjobbat valasztjuk ki Addig folytatjuk ezt a m}uveletet, amg a szomszedai kozt van nala jobb Ekkor termeszetesen egy lokalisan legjobb elemhez jutunk. Vagy el}ozetesen tudjuk, hogy csak egyetlen lokalis optimum van, vagy tobb kulonboz}o elemb}ol kiindulva a kapott lokalis optimumok kozul kivalasztjuk a legjobbat. Ez a modszer akkor hasznalhato, ha a relacio kell}oen "sima", azaz nincs tulsagosan sok lokalis optimum. A genetikus algoritmusok otlete biologiai pelda hatasara merult fel. Itt mar mi generaljuk a strukturat, szamunkra kenyelmes modon kodoljuk a

ter elemeit. Nem egyetlen elemet vizsgalunk, hanem egy egesz populaciot es ugynevezett genetikus operatorok segtsegevel hozunk letre ujabb populaciokat. Ezt addig folytatjuk, amg az uj populacio elterese az el}oz}ot}ol egy kuszob alatt marad Ezt a modszert {1{ vizsgalom a dolgozatban. Az ugynevezett "simulated annealing" algoritmus -amelyet talan lassu h}utesnek lehetne fordtani- pedig zikai analogian alapul 1]. Eszerint ha hirtelen leh}utunk egy rendszert, az valamely magasabb energiaju allapotban "befagy". Viszont ha lassan h}utjuk le, akkor folyamatosan egyre kisebb energiaju allapotokon keresztul eleri a minimalis energiaju allapotot. A genetikus algoritmusok vizsgalataval tobben foglalkoztak mar 2,5]. Mindezen m}uvek azonban azonos szemszogb}ol jarjak korul a problemat Ebben a dolgozatban felhasznalom a Markov-lancok elmeletet, amely hatekony vizsgalati eszkoz lehet. Az els}o fejezet a

3] alapjan epul fel, ebben a kes}obb felhasznalando teteleket rtam le. A masodik fejezetben az algoritmusban szerepl}o fogalmakat denialtam ujra, hogy illeszkedjenek a Markov-lancok elmeletehez. Ebben nagy segtsegemre volt 4], innen vettem a metahalmaz otletet. A harmadik fejezet tartalmazza az alkalmazast {2{ I. M a r k o v - la n c o k I.1 M arkov-la ncok dencio i 1. Dencio: Egy fXt t 2 Tg sztochasztikus folyamatot Mar- kov-lancnak nevezunk, ha a) allapotainak halmaza megszamlalhato b) P(Xt = bjXt1 = a1  Xt2 = a2  : : : Xt = an )= P(Xt = bjXt = an ) (8 t1 < t2 < : : : < tn < t) 2. Dencio: Az Xt Markov-lancot diszkret parameter}unek nevezzuk, ha T  IN. 3. Dencio: Az Xt diszkret parameter}u Markov-lancot homogen atmenetvaloszn}useg}unek nevezzuk, ha P(Xi+j = bjXj = a) fuggetlen j -t}ol (n) = P(X = ijX = j ), de n =1 eseten csak P -t runk. Jelolesek: Pij t+n t ij n n I.2 M arkov-la ncok a

llap otainak jellem ze se I.21 Dencio: Legyen I egy diszkret parameter}u, homogen atmenetvaloszn}useg}u Markov-lanc allapotainak halmaza i 2 I allapotot elerhetetlennek nevezzuk, ha 8j 2 I Pji =0. I.22 Dencio: Legyen i j 2 I egy diszkret parameter}u, homogen atmenetvaloszn}useg}u Markov-lanc ket allapota Azt mondjuk, (n) > 0. Jelolese: i!j (Terhogy i-b}ol elerhet}o j , ha 9n 2 IN, hogy Pij (0) =  ertelmezes miatt i!i.) Azt mondjuk, hogy i es j meszetesen Pij ij kolcsonosen elerhet}oek,ha i!j es j !i. Jelolese: i$j I.21 A lltas: A $ relacio ekvivalenciarelacio Bizonytas: i$i a dencio alapjan teljesul. A szimmetria is fennall, ugyanis $ denciojaban i es j szerepe szimmetrikus. Vegul pedig a tranzitivitas igazolasahoz eleg belatni, hogy ! tranzitv. Ha (n2 ) > 0. Ekkor i!j es j !k, akkor 9n1  n2 2 IN, hogy Pij(n1 ) > 0 es Pjk (n1 +n2 )  P (n1 ) P (n2 ) > 0. Azaz i!k Pik ij jk {3{

I.23 Dencio: Legyen I egy diszkret parameter}u, homogen atmenetvaloszn}useg}u Markov-lanc allapotainak halmaza. i 2 I allapotot lenyegesnek nevezzuk, ha 8j 2 I, amelyre i!j , teljesul j !i is Egy nem lenyeges, elerhet}o allapotot atmenetinek nevezunk. I.22 A lltas: A lenyegesseg es az atmenetiseg osztalytulajdonsag, azaz minden ekvivalenciaosztaly elemeire egyszerre teljesulnek vagy nem teljesulnek. Bizonytas: Legyen i lenyeges es legyen i$j . Ekkor 8k 2 I, amelyre j !k, teljesul i!k is. Mivel i lenyeges, k!i, ebb}ol pedig k!j is kovetkezik. Azaz j is lenyeges Legyen most i atmeneti es legyen i$j . Ez azt jelenti, hogy 9k 2 I, amelyre i!k, de k 6 !i Ekkor j !k is teljesul es ha k!j lenne, akkor kovetkezne k!i is, ami ellentmondas. Emiatt j is atmeneti. I.24 Dencio: Az i allapot periodusanak nevezz uk azon n ( n ) szamok legnagyobb kozos osztojat, melyekre teljesul Pii > 0. Jelolese: di . I.23 A lltas: Legyen

(ina) llapot periodusa di es legyen i$j Ekkor dj = di , ezenkvul 9r 2 IN Pij > 0 ) n r(mod di ). Bizonytas: i$j miatt 9n m : Pij(n)  Pji(m) > 0. Ekkor 8s, amely(m+n+s) > 0 is teljesul d jm + n es d jm + n + s miatt re Pii(s) > 0, Pjj j j dj js. Mivel di az ilyen s szamok legnagyobb kozos osztoja, dj jdi is teljesul Mivel i es j szerepe szimmetrikus, dj jdi Eszerint tehat di = dj A masik alltas ennek egyszer}u kovetkezmenye. I.25 Denci(on:) Jelolje Cr (i) C (i) i osztalyanak azon j elemeit, amelyekre Pij > 0 ) n r(mod di ). I.26 Dencio: Legyen fij(n) = P(Xt+n = j jXt = i 80 < k < j Xt+k =6 j ). P (n) . i 2 I allapotot visszater}onek nevezzuk, ha Legyen fij = fij n2IN fii =1. I.27 Dencio: Legyen i 2 I egy visszater}o allapot Az n 7! ( n ) fii valoszn}usegeloszlasu valtozot els}o visszateresi id}onek nevezzuk. Legyen mii =: mi az els}o visszateresi id}o varhato erteke. Ha mi < 1, akkor

pozitv visszater}o allapotnak nevezzuk, kulonben pedig nullvisszater}onek. {4{ I.24 A lltas: Pij(n) = Xn f (k)  P (n k) k=1 ij jj ; Bizonytas: Az ugynevezett els}o eleres modszerevel bizonytunk. Legyen  =inf fn  1 : Xn = j jX0 = ig: (k) . Igy az Szetvalasztjuk az esemenyeket  erteke szerint.P ( = k) = fij alltas eppen a teljes valoszn}useg tetele. I.28 Dencio: gij =: P(Xn = j vegtelen sok n;rejX0 = i) Mertekelmeleti megfontolasok alapjan gij = mlim P(9n > m : Xn = j jX0 = i)= mlim !1 !1 X P (m)  f k2I ik kj : I.25 A lltas: gij = fij  gjj Bizonytas: Az els}o eleres modszerevel bizonythato. I.26 A lltas: gij = fij , ha j visszater}o, kulonben pedig gij =0 Bizonytas: gij (m) =: P(9nm > : : : > n1 > 0 : Xn = j jX0 = i). k Az els}o eleres modszerevel belathato gij (m + 1) = fij  gjj (m), gy gij (m + 1)= fij  (fjj )m . gij = mlim gij (m)-b}ol az

alltas kovetkezik. !1 {5{ I.3 M arkov-la ncok hata reloszla sa I.31 Tetel: P Pii(n) divergens, ha i visszater}o allapot n IN P Pii(n) =(1 ; fii) 1, ha i nem visszater}o. b) a) 2 ; n2IN Bizonytas: Felhasznaljuk a kovetkez}o lemmat bizonytas nelkul. Legyenek (an )n2IN (bn)n2IN valos szamsorozatok a kovetkez}o tulajdonsagokkal: a) an =0 an  0 nlim n P !1 ai i=0 b) 9b 2 IR nlim bn = b !1 Ekkor Pn ai  bn;i i =0 lim =b n n!1 ai i=0 P Az I.24 alltas alapjan XN P (n) = XN nX1 f (n k)  P (k) = NX1 P (k)  XN f (n k) = NX1 P (k)  NXk f (n): ; n=1 ij ; ; ; ; ij jj jj ij jj n=1 k=0 k=0 n=k+1 k=0 (n) es b = n f (i) esetre felhasznalva a lemmat an = Pjj n ij i=1 N (n) Pij n =1 lim =f n!1 N (n) ij P n=0 jj P P P egyenl}oseget kapjuk, amib}ol j = i esetben PN Pii(n) lim n=1P N (n) = fii n 1 + Pii !1 Ebb}ol az alltas kovetkezik. n=1 {6{ ; n=1 ij I.32 Tetel: Legyen i visszater}o allapot di

periodussal Ekkor (nd ) = di  emellett P (nd +r) =0 ha r 6 0 (mod d ): lim P i ii ii n!1 mi i i Bizonytas: Az alltas masodik fele nyilvanvalo kovetkezmenye a periodus denciojanak. Az els}onek a belatasahoz felhasznaljuk a kovetkez}o lemmat bizonytas nelkul: di azon n szamok legnagyobb kozos osztoja is, amelyekre fii(n) > 0 teljesul. P1 fii(n), ekkor P1 rk = P1 k  fii(k) = mi. Az I24 alltasba Legyen rk = k=1 k=0 n=k+1 k ; rk;1 )-t helyettestve: ii n Pii(n) = ; (rk ; rk;1 )  Pii(n;k)  azaz k=1 n n;1 rk  Pii(n;k) = rk  Pii(n;1;k) = : : : = r0  Pii(0) =1 k=0 k=0 ( Legyen  =lim sup Piindi ) . Ekkor 9nk reszsorozat, melyre n!1 (nk di ) :  = klim P ii !1 Legyen s tetsz}oleges olyan szam, melyre fii(s) > 0. Ekkor a lemma alapjan di js. Ekkor  =lim inf P (nk di ) = k!1 ii nk ( s ) ( n (r)  P (nk di ;r) )  k di ;s) =lim inf ( f  P + f ii ii ii ii k!1 r=1 r6=s nk (s)  lim inf P (nk di ;s) + lim sup

fii(r)  Pii(nk di ;r) =  fii k!1 ii k!1 r=1 r6=s = fii(s)  lim inf P (nk di ;s) +   (1 ; fii(s)): k!1 ii Az egyenl}otlensegb}ol   lim inf P (nk di ;s) kovetkezik, amely  denk!1 ii (nk di ;s) alltasra vezet. Egy ismert szamelciojaval egyutt  = klim P ii !1 meleti eredmeny alapjan ebb}ol nlim P (ndi) =  is kovetkezik. Emiatt !1 ii n 1 1  ( n ;k) 1= nlim rk  Pii =   rkdi = d  rk =   md i : !1 i k=0 i k=0 k=0 f (k) = ;(r X X X X X X X {7{ X Ez azt jelenti, hogy  = mdi : i I.33 Tetel: Legyen j visszater}o allapot dj periodussal Ekkor ha a) i ugyanabba az osztalyba tartozik es j 2 Cr (i), akkor P (ndj +r) = mdj  emellett nlim Pij(ndj +k) =0 ha k 6 nlim !1 ij !1 j r (mod di ) (n) =0 b) i masik, lenyeges osztalyba tartozik, akkor 8n 2 IN : Pij c) i atmeneti, akkor (nd +r) = f (r)  dj  ahol f (r)= lim P ij ij ij n!1 mj j X kr(mod dj ) (r) fij Bizonytas: Ha i es j kulonboz}o le(nyeges

osztalyok, akkor i 6 !j n) es j 6 !i. Azaz valoban 8n 2 IN : Pij = 0 Ha j 2 Cr (i), akkor k 6 r (mod di ) eseten az I.23 alltas alapjan Pij(nd +k) = 0 Az a) es a c) esetre vonatkozo alltas az I.32 tetel bizonytasanak modszerevel belathato. I.341Tetel: Ha j nem visszater}o allapot, akkor P Pij(n) < 1, emiatt lim Pij(n) =0. 8i 2 I : n!1 j n=0 Bizonytas: Az I.24 alltas alapjan XN P (n) = NX1 P (k)  NXk f (n)  NX1 P (k) emiatt ; n=1 ij k=0 ; jj ij n=1 k=0 X P (n)  X P (n) < 1 1 . ; n=0 1 ij n=0 jj {8{ jj I I . A lta la n o s m o d e ll II.1 Alapvet}o dencio k II.11 Dencio: Legyen X egy megszamlalhato halmaz Je- lolje  az X 7;! X fuggvenyek halmazat. Jelolje P (X ) az  7;!  fuggvenyek, az ugynevezett sztochasztikus operatorok halmazat. A sztochasztikus operatorokat ugy is fel lehet fogni, hogy 8x 2 X elemhez egy valoszn}usegi valtozot rendelnek, f (x) : ! 7! f (!)(x). II.12

Dencio: X -beli metahalmaznak nevezunk egy m : P : X 7;! IN fuggvenyt, ha c(m) = m(x) < 1. A c(m) szamot a x2X metahalmaz szamossaganak nevezzuk. A H(m) = fx 2 X jm(x) > 0g halmaz m tartohalmaza. Legyen M(n) (X )= fm X ;beli metahalmazj c(m)= ng valamint M(X )=  M(n)(X ): n2IN II.13 Dencio: Legyen f 2 P (X ) tetsz}oleges sztochasztikus operator. Ekkor kepezhet}o a kovetkez}o, M(f ) 2 P (M(X )) sztochasztikus operator: m 2 M(X ) eseten legyen X ((M(f ))(m))(y) =: X m(x) x2X i=1 ffxi (x) = y g valoszn}usegi valtozo, ahol fxi operatorok fuggetlenek es eloszlasuk megegyezik f eloszlasaval. {9{ II.2 Genetikus te r II.21 Dencio: Legyen ; egy megszamlalhato halmaz, ame- lyet a genotpusok halmazanak nevezunk. M(;) halmazt az osszes populacio halmazanak, mg M(;) halmazt a lehetseges populaciok halmazanak nevezzuk. II.22 Dencio: Tegyuk fel, hogy ; el}oall ;1  : : :  ;k alakban, ahol k > 1 Ekkor ;-t

dekomponalhatonak nevezzuk ;i elemei az i: gen alleljai. II.23 Dencio: Egy ! 2 P ( ) sztochasztikus operatort genetikus operatornak nevezunk A (  !1 : : : !n ) strukturat genetikus ternek nevezzuk, ha a) a lehetseges populaciok halmaza b) !i i =1 : : : n -n ertelmezett fuggetlen genetikus operatorok. II.21 A lltas: Legyen (  !1 : : : !n ) genetikus ter Legyen 0 tetsz}oleges -n ertelmezett valoszn}usegi valtozo. A k+1 =: !1 (: : : (!n ( k ) : : :) rekurzioval denialt sztochasztikus folyamat homogen atmenetvaloszn}useg}u Markov-lanc. Bizonytas: Mivel k+1 -t k fuggvenyekent denialtuk, Markovlancot kapunk. 8k 2 IN eseten ugyanazt a fuggvenyt hasznaljuk, gy homogen atmenetvaloszn}useg}u is lesz. II.24 Dencio: S genetikus operatort szelekcionak nevezzuk, ha 8m 2 : P(H(S (m)) H(m))=1: II.25 Dencio: P 2 P (;) sztochasztikus operatort mutacionak nevezzuk, ha a) 8 1 2 eseten P1 2 =: P(P ( 1)= 2 ) > 0

b) sup P < 1 es inf P > 0. 2;  2; Legyen (P ) =: 1 ; sup P es (P ) =: 1 ; inf P . 2;  2; (P )-t mutacios ratanak nevezzuk. { 10 { II.26 Dencio: Legyen ; dekomponalhato A CO : ;  ; 7;! ; operatort keresztezesnek nevezzuk, ha : eseten = CO( 1 2) olyan valoszin}usegi valtozo, melyre 8! 2  : j (!)= j1 vagy j (!)= j2. 1 = ( 1 : : : 1) 2 = ( 2 : : : 2) 1 1 k k A mutacio es a keresztezes nem genetikus operatorok. Viszont bel}oluk kiindulva kepezhetunk genetikus operatorokat: a) M = M(P )j mar genetikus operator, nevezzuk ezt is mutacionak b) C = M(Cr)j -t pedig nevezhetjuk keresztezesnek, ahol Cr 2 P (;) a kovetkez}o sztochasztikus operator: Legyen m 2 rogztett, 2 valoszn}usegi valtozo, P ( 2 = )= mc((m)) . Ekkor Cr : 1 7! CO( 1 2). A jeloles nem pontos, mert Cr kiterjesztesenel minden egyes m 2 eseten ezzel az m-mel tekintjuk Cr-t, nem pedig egy rogztettel. Ahhoz, hogy a kiterjesztett mutaciora

teljesuljenek a megkvant tulajdonsagok, nem lehet akarmilyen. El}oszor is: 8n 2 IN ( M(n)(;)= ) (M(n)(;) ): Legyen ugyanis m 2 M(n) (;) tetsz}oleges. Ekkor 8m 2 M(n) (;) P((M(P ))(m)= m ) > 0: Azaz m 2 eseten M(n) (;) -nek is teljesulnie kell. Emellett a II.25b tulajdonsag teljesulesehez szukseges, hogy 9K 2 IN : m 2 ) c(m)  K . Mivel a genetikus algoritmusoknal tovabbiakban ezt kikotjuk. { 11 { = M(K ) (;) eset teljesul, a II.3 Szelekcio II.31 A lltas: Ha m1 $S m2 , akkor H(m1 )= H(m2 ) Bizonytas: A II.24 tulajdonsag miatt m1 !S m2 -b}ol H(m2 ) H(m1 ) kovetkezik. II.31 Dencio: Legyenek az S -lenyeges allapotosztalyok "= f1  2 : : : n  : : :g. Jelolje az  fS(n)(m) 2 ijS(n)(m) 2  j g n2IN j 2 esemenyt i (m). A P(i (m)) erteket jeloljuk si (m)-mel II.32 Dencio: Az Sfm: 2 : si (m) > 0g halmazt i vonzask orzetenek nevezzuk es S (i ) = Si -vel jeloljuk. S Az fm 2 : si (m) > 1 ; g

halmaz neve pedig i -vonzaskorzete, jele Si (). II.33 Dencio: m 2 Si eseten legyen i (m)=inf fn 2 IN : S (n) (m) 2 i ji (m)g valoszn}usegi valtozo. Ezenkvul legyen  (m)=inf fn 2 IN : S (n) (m) 2 II.31 Tetel: E (m)= P i:m2Si  ig: i 2 Ei (m)  si (m). Bizonytas: A i (m) esemenyen  (m)= i (m), erre alkalmazhat- juk a teljes-varhatoertek tetelt. II.32 Tetel: Ei (m)=1 + X m 2Si m jx = m)  ha m 2=  : Ei (m )  P(SP((xS)= i (m) 2 S ) i Bizonytas: Szinten a teljes-varhatoertek tetelb}ol kovetkezik. { 12 { II.33 Tetel: si (m)= X m 2Si m jx = m)  ha m 2=  : si (m )  P(SP((xS)= i (m) 2 S ) i Bizonytas: Ez pedig a teljes valoszn}useg tetelb}ol kovetkezik. Ezek az egyenletek az Ei (m) = 0 es si (m) = 1, ha m 2 i feltetelekkel egyutt egy egyertelm}uen megoldhato linearis egyenletrendszert alkotnak. II.4 M uta cio M relacio szerint egyetII.41 A lltas: Legyen ; veges Ekkor a $ len osztaly

van, amely lenyeges, s}ot pozitv visszater}o. Ezenfelul a allapotok periodusa 1. Bizonytas: 8 1  2 : P ( 1 2) > 0, emiatt M m . Mivel 8m1  m2 2 : M (m1  m2 ) > 0, azaz 8m1  m2 2 : m1 ! 2 ( K ) ; veges es = M (;), 9 = m min M (m1  m2) > 0. Tehat egyetlen 1 m2 2 osztaly van, ez nyilvanvaloan lenyeges. Legyen m egy rogztett allapot Eleg ha err}ol belatjuk, hogy pozitv visszater}o, mert ez osztalytulajdonPn (k) sag. Legyen tehat fn = P(M (k) (m) 6= m k =1 : : : n) 1 ; fn = fmm k=1 f = 0. Mivel legal abb miatt m pontosan akkor visszater}o, ha nlim n !1 valoszn}useggel m allapotba kerulunk, akarmi is volt az el}oz}o allapot, fn+1  fn  (1 ; ). Ebb}ol fn  (1 ; )n kovetkezik, azaz nlim fn = 0. !1 Tehat m visszater}o, gy P 1 k=n+1 (k) =1 ; fmm X XX mm = n  f (n) = 1 n=1 1 mm 1 n=1 k=n+1 f (k) mm Pn fmm (k) = f , ebb}ol n k=1 X = fn  1 < 1: 1 n=1 Ez azt jelenti, hogy m pozitv visszater}o is. Mar csak

azt kell belatni, hogy a periodusa 1, ez pedig Mmm > 0 miatt egyertelm}u. Kovetkezmeny: Legyen ! 2 P ( ) tetsz}oleges genetikus operator. Ekkor a M$ relacio szerint is egyetlen, pozitv visszter}o osztaly van. { 13 { II.41 Dencio: Legyen ; dekomponalhato, ;=;1      ;k Legyen Pi mutacio ;i -n. Ekkor a P : 7! mutaciot a P1  : : : Pk mutaciok kompozciojanak nevezzuk, ha i = Pi ( i). Jelolese: P = P1      Pk . II.42 A lltas: Ha P a P1  : : : Pk mutaciok kompozcioja, akkor k Y (P )=1 ; (1 ; i=1 k X (Pi ))  i=1 k X (Pi ) ha i=1 (Pi )  1: Bizonytas: A kozeltes e;x  1 ; x-b}ol adodik, ha x  1. Az egyenl}oseg pedig abbol adodik, hogy P1  : : : Pk fuggetlenek, gy P(P ( 1 : : : k )=( 1 : : : k Y k ))= P(Pi ( i )= i ): i=1 Megjegyzes: Az alltas ugy pontosabb, -bar kevesbe fejezi ki a lenyeget- hogy k X 9 : i=1 (Pi ) <  ) k X (P ) < 2  i=1 (Pi ): II.43 A lltas: (M )  K  (P

) ha K  (P )  1: Bizonytas: A konvencionk ertelmeben = M(K )(;). Az el}oz}o alltashoz hasonlo kozeltest alkalmazunk. Egy populaciot a mutacio nem valtoztat meg, ha egyetlen egyed sem valtozik. Ehhez kepest elenyesz}oen kicsi annak a valoszn}usege, hogy az egyedek pontosan ugy valtozzanak, hogy a populacio masik egyede legyen bel}oluk. Kovetkezmeny: Ha P = P1    Pk es K  P (Pi ) < , akkor k Pk (M ) < 4K  i=1 i=1 (Pi ). { 14 { II.42 Dencio: Legyen ; dekomponalhato Jelolje dH az ugynevezett Hamming-tavolsagot, amit a kovetkez}okepp ertelmezunk: dH ( 1 2)= cardfi 2 IN : 1i 6= 2i g: Legyen dH -beli tavolsag dH alapjan: dH K X (m1  m2)=minf dH ( 1k  cardfi 2 IN : k=1 1i = 2k ) : 8 2; g = m1 ( ) cardfi 2 IN : 2i = g = m2 ( )g: Ez az alabbi dencio azt az elkepzelest fejezi ki, hogy ket populacio tavolsaga ugy all el}o, hogy parostjuk az egyedeket a ket populaciobol es a

parok tavolsagainak osszeget tekintjuk. Termeszetesen ez a tavolsag fuggene a parostastol, ezert vesszuk az osszes lehetseges parostasra a minimumot. II.5 Kereszteze s II.51 Dencio: Legyen ; dekomponalhato, ;=;1  : : :  ;k A #=;1  : : :  ;k halmazt semanak nevezzuk, ha i =1 : : :  k : ;i ;i . II.52 Dencio: # semat egyszer}unek nevezzuk, ha ;i = ;i vagy ;i = f i g. Legyen I = fi : ;i = f i gg es r(#) = card(I ), ekkor a semat #I 1 ::: -vel jeloljuk. II.53 Dencio: Legyen H ; egy tetsz}oleges nemures halmaz A H altal generalt semanak nevezzuk a legsz}ukebb #(H ) semat, melyre H #(H ) teljesul. Az m populacio altal generalt seman a #(H(m)) semat ertjuk. II.54 Dencio: Legyen # tetsz}oleges sema Legyen i ir (#)= fm 2 : #(H(m)) #g: (#)-t a # semara illeszked}o populaciok halmazanak nevezzuk. { 15 { II.51 A lltas: A keresztezes az m populaciot egy #(H(m))-ra illeszked}o populacioba

viszi. Bizonytas: Crm operator 8 2 #(H(m)) genotpust #(H(m))beli genotpusba visz at. Ha tehat tekintjuk C -t, a kiterjesztes tulajdonsagai miatt az eredmeny egy #(H(m))-ra illeszked}o populacio II.55 Dencio: m populacio atmer}ojen az r(#(H(m)) szamot ertjuk. II.6 Fitness II.61 Dencio: Az f : ; 7;! IR fuggvenyt tnessnek nevez- zuk, ha 8 2 ; eseten f ( ) > 0. II.62 Dencio: Legyen f tness, m 2 cio. mX (x) X : f (m) = f (x): tetsz}oleges popula- x2; i=1 Az fm ( ) =: ff((m))  (m( ) > 0) erteket egyed relatv tnessenek nevezzuk. II.63 Dencio: Legyen f tness, m 2 tetsz}oleges populacio, # tetsz}oleges sema X X f (x): f (#) =: m(x) x2 i=1 ( )  ( 2 # m( )) erteket egyed # semara illeszked}o Az f ( ) =: ff() relatv tnessenek nevezzuk. II.64 Dencio: Legyen f tness, m 2 tetsz}oleges populacio Legyen f : 7;! M(1) (;) a kovetkez}o sztochasztikus operator: f (m)( )=1 m( )  fm( ) valoszn}useggel. Az

cX (m) Sf : m 7! fi (m) i=1 sztochasztikus operatort az f tness altal vezerelt szelekcionak nevezzuk. { 16 { II.61 A lltas: Sf szelekcio Bizonytas: f dencioja alapjan H(f (m)) H(m) teljesul. H(Sf (m))= miatt az alltas igaz.  H(f (m)) c(m) i=1 i II.62 A lltas: Az Sf -lenyeges allapotok pontosan azok, melyek- nek a tartohalmaza egyelem}u. Mindegyik ilyen allapot egyetlen osztalyt alkot, melynek a vonzaskorzeteben pontosan azok a populaciok vannak, amelyek tartohalmaza tartalmazza azt az egy genotpust. Bizonytas: H(m ) H(m) eseten P(Sf (m) = m ) > 0. Azaz m!m () H(m ) H(m). Ebb}ol kovetkezik az alltas { 17 { I I I . G e n e tik u s a lg o r itm u s o k III.1 Dencio k III.11 Dencio: Legyen ; = f0 1gk a genotpusok halmaza Legyen P mutacio f0 1g-n, P(P (x) = x) = 1 ; p x = 0 1. Legyen P = P      P mutacio ;-n. Legyen CO keresztezes ;-n, P(COi ( 1 2) = i1) = 12 . Legyen f : ; 7;! IR+ tness Legyen

= M(K ) (;), Sf az f tness altal generalt szelekcio, M a P altal generalt mutacio, C pedig a CO altal generalt keresztezes -n. A kovetkez}o eljarast nevezzuk genetikus algoritmusnak: Kivalasztunk egy m0 2 populaciot, vegrehajtjuk a szelekciot, aztan a keresztezest vegul a mutaciot, gy kapjuk m1 = M (C (Sf (m0 ))) populaciot. Ugyangy kaphato mn+1 populacio mn -b}ol Egy megalltasi kriterium alapjan eldontjuk, mely n-re hagyjuk abba a m}uveletet (ez lehet el}ore rogztett n, de lehet pl olyan kriterium is, hogy jf (mn+1 ; f (mn ))j < ). III.2 Eredm e nyek A II.41 alltas kovetkezmenye alapjan egyetlen, pozitv visszater}o osztaly van. Az I33 tetel alapjan tehat a Markov-lancnak 9! stacionarius eloszlasa es barmely kezdeti eloszlasbol kiindulva ehhez a stacionarius eloszlashoz konvergal Ebben az eloszlasban minden allapot valoszn}usege pozitv. Mivel a genetikus algoritmussal a Markov-lancnak egy

trajektoriajat jarjuk vegig, minden id}opontban egy konkret allapotban vagyunk. Az allapotok stacionarius eloszlasbeli valoszn}usege azt adja meg, aszimptotikusan mennyi id}ot toltunk abban az allapotban. Az atmenetvaloszn}usegmatrix ismereteben a stacionarius eloszlas meghatarozhato, legalabbis elvileg. A matrix 1 sajatertekhez tartozo sajatvektorat kell meghatarozni. Genetikus algoritmusok eseten pontosan egy ilyen sajatertek van, de az allapotok hatalmas szama miatt az egyenletek felrasa is nehezseget okoz, nemhogy a megoldasuk. { 18 { Szerencsere nekunk eleg az a teny, hogy 1 valoszn}useggel lesz olyan allapot, amely tartalmaz maximalis tness-szel rendelkez}o genotpust. S}ot 1 valoszn}useggel vegtelen sok ilyen allapot van. A minket erdekl}o kerdesek inkabb azok, hogy a) mikor jutunk el egy ilyen allapotba? b) hogyan ismerjuk fel, hogy ilyen allapotba jutottunk? Az els}o kerdesre adott valaszunk azon

alapul, hogy csak a mutacio es a keresztezes hoz letre uj genotpusokat. Annak a valoszn}usege, hogy m populacio a mutacioval olyan populaciova alakul, amely mar Q mQ()(1 ; P(P ( )= )). Legyen tartalmaz genotpust: Pm =1 ;  2; i=1 1 fels}o becslese az ilyen allapotba valo eljutas var= mmin P , ekkor m  2 hato ertekenek. Ha gyelembe vesszuk a keresztezest is, eleg, ha olyan populacioba mutalodik, amelyre a generalt semanak eleme . Ez joval kisebb varhato id}otartamot ad, ezutan mar csak meg kell varnunk, hogy a keresztezes "kikeverje" a megfelel}o genotpust. Termeszetesen a szelekcio meggyorsthatja a folyamatot, azaz olyan populacio iranyaba mozoghat, ahonnan konnyebb elerni a kvant genotpust. A masodik kerdesre adott valasznal kell gyelembe vennunk jelent}osebb mertekben a szelekciot. Az S -lenyeges allapotok eppen az egyetlen genotpust tartalmazo populaciok Minel magasabb tness tartozik az

adott genotpushoz, annal nagyobb az allapotnak a -vonzaskorzete. Azaz a mutacio es a keresztezes kisebb valoszn}useggel vezetnek ki az adott vonzaskorzetb}ol. Ez azt jelenti, hogy nagyobb az ebben az allapotban tartozkodas varhato ideje. Tehat meghatarozhatunk egy olyan id}ointervallumot, hogy ha az algoritmus legalabb ilyen hosszu ideig tartozkodik egy adott allapot kornyezeteben, akkor megtalaltuk a maximalis tness}u genotpust. Termeszetesen ehhez alacsony mutacios rata kell, hogy a szelekcio eleg gyorsan visszaterjen a lenyeges allapotba, azaz atmeneti allapotban keves mutacio legyen. { 19 { K o s z o n e t n y ilv a nt a s Szeretne k ko szo netet mondani: Kova cs Margitnak, te mavezet}o m nek a tu relme e rt Fritz Jo zsefnek kritikai megjegyze seie rt To ro k Ja nosnak es Cziro k Andra snak a TEX-ben ny u jtott segtse gu ke rt Richard Dawkinsnak a ko nyveib}o l mertett ihlete rt { 20 { H iv

a t k o z a s o k 1] van Laarhoven, Petrus Joseph Maria: Theoretical and Computational Aspects of Simulated Annealing 2] Holland, John H.: Adaptation in Natural and Articial Systems Cambridge, Massachusetts - London 3] Chung, Kai Lai: Markov chains with stationary transition probabilities Berlin - Heidelberg - New York Springer, 1969. 4] Jones, Terry: Evolutionary Algorithms, Fitness Landscapes and Search the University of New Mexico, Albequerque, New Mexico 1995. May 5] Feistel, R.& Eberling, W: Evolution of Complex Systems Berlin 1989. { 21 {