%PDF-1.4 % 4 0 obj << /Subtype /Image /Name /Im1 /Type /XObject /Filter /DCTDecode /Width 500 /Height 649 /Length 23864 /BitsPerComponent 8 /ColorSpace /DeviceRGB >> stream JFIFC   (1#%(:3=<9387@H\N@DWE78PmQW_bghg>Mqypdx\egcC//cB8Bcccccccccccccccccccccccccccccccccccccccccccccccccc" }!1AQa"q2#BR$3br %&'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz w!1AQaq"2B #3Rbr $4%&'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz ?qEwh'jLp )43Hc&i3E1 J3In>\,;4E>m8n}&b(41KEvhPh& '&"i x>ԔdQqX_ZJ)vt(z҃MPFia٠nx4sFióaf3L,;4!X}(Hh3|]#+VϋN|Aq㢱r %-%KaER((3E&h&.E44N٦њ.3M&hXvh64\,.h&4\,8(74Qp3M4\,;PJSI@4Q)) vf  ̬z(((JZ-t@Q; (RCL /z,EPEPKڒZ))h1E- NPE-'zJ)hP-+RS K(h(XQE)RJ&(QEZJ()E!4)XږHgQv܃o\WAX())i)QEQEQEꢔRP+-@ Gj@ih)}i 4褥f-.h44PEњLO4Qޓ#4Bޓ4ff@z\ ;Q@f@}hQGzZ)(4v(QG;њ))M%Ph@ q5,GoYB|O!ۏ+*PRQEHŠ(((U=먑OJյ/ؑ^k38ŽUYؚ #(Kʆ#YdEt9VOTNneܣ8'*Nϧ1 vRf ⹁f [f,E`>t٢B-6#~!ϖ}G]9Ⲗ'uVS@W%FwP\5BA,[oҬOVUqoLWiq%բJD܊\x[kK~3DaXG`qS'$}rʩ [ʺHcuC!mn U^[G#?ݓǸTBQ1>zzcZ|i^JQp?QWxlab49Q<1 U.^[i~΂Tg IqP_%PҜqm[)8Jo`-; ?H |Ux其T44,k;GZ8P{zyjR;1A&tY@Q GɸH/bN#pۑϦq|Y!fn uSAК[[[y&5FY=8n.n"XQ" ~BGM$RBu)ouA+NQRj7ch!"F2yS׷xY\ѲCSK3?ewik,j`۰QRڼʈ2\85%x[!P?F"gC̩c$Qv Y M+ ֫gCa#{*=_Z0F[E *"qy=yH1GJyK,So8XeX _t^fm!%BDgڧYI%/ u#Ek B]Bx4X#,dN1Qj4N#AOAYsi^ڛCJoRMcf\InfI)0ʉGtm &Ctl}3k?_fnDZjy$K+ԱVm U}+TQSn:TPxhdfwG}qS CKސZCCxCEEdַ?;q_VHgRQE ( ( (=VI@;%JܰbQa%WeGվF0i9'@h|FeBZ $+ZOe6ڤH_$4u4Xc>Idaߡ_nKIr\AשP TuUWUP2I" 9P "TMWTMC5ӺR\stAs퉶; ¨ZxDr#ts:Wd `A;◚R0;;c dEo"wnԎ3Z&1M5ɖ6C NLg=TTc2vqhԢuIIF}B*-A[SdBQԟZ<֗ךҧ)*'Qil#medlZxdP]jG#Gdˍ)\S[M=("{ KVQK Adp:EM<ڨ-O%ft(sN?Zi~Z%vj䖱-'YLr֖)GX (nenRʤ,GU 䎦4SP"RF"eym'>ղC/COH$,Mo(IKņkbݷF[{ޓ pjrk/tϱj+؛TUEak4 kHdw?!,` )E!;h}A+['+$W3l%QHaEPEPEPP);ں4f,y=\uKY{++={;?%nYր,F*9ǪG(2"ah1.ZIE,pq9fbȃ.3?:vlmXbbϥIkq[$00c4UT?9f 2:\պ\iF wq< t# ݺ ,E8M!IÏتzLhuҥ p?*?SeMb 3fH؞*)pij.!) q2 #=E=!{XB3w%3Ïx&jJzXX⒞D;>˝3[X#Y8TؠnKP'C,=2+ )o'Kp[6տ8E;.!hѽf9PLn/0#md+9QaAtX%`- Z5PsPXaր6Yȟy q85.+N\,9Gʺ29 r1s?5&x{$A}CQqϨ 媱 s#5y#_j`Dgp[~εQ8QUWX0X0=4K[(nnf@C2ڱ?eP];H Ƨ{{ #˥ctf#'w2x>5#IC*\C#lYg?+>l`㞇VL2FucX.2:k$DMT$]*K2Iy8?7\ 5dP.,:3R)?Ze ɢAKpѩ[]#P>Ag햹F7F,0j -6c9A- < dz( 93ȏX~q lVIFѭg꧊-w șy#ZWX3zl4$"צT@PzcW5gOF'"WSq%0Mqw UeyUw0xڔ yl\$EْhPHsZ"Ku *.>î[ܫS <Ḗ*D rqHi{PzP!)?–P4p^(Y5}A\sUQEHQ@Q@Q@Gj(]F&7ʩam0v?ZYDFeaPJHd--n&#ϗèdq@w7vv:whWx?WUnVy;ϠR^%f)DNJ)Ҁ!:M~Π`n8ѲrP?^dȡV(RAj-1E,,XO(-'< | Cke/b3B?xVcYY2[AV0*@ {ҰyR{kQu#)&̓F$Qj"-ⴁ܊Xӊt]}L˴p8Ƌ#(}\TOY nnTp^AGLW q3S3o?Vj\m_qۿr1W hC%mO?~!V쯀%-8oEqhmtE 0AiDutWF 2wI"sHQRzUXt-''>X("٧Gi#`jc̊;5'u?[UY.0AU zRtXfb|4MZҮ ?;.85i԰vC[M:+d`rUu@-s F\cKZ0 2BsU{= 2ɂG¥e<p\Ґ^dGwcp[ b2LWSP}A㵒4ط4\]\jM8dbAj~[8[&= ZZl\ĘirrX[Cwq#=Tڋ1uc[9Δtd`~_E6g!8 s'e<-ǥ&uk[LҴM. IU>pҕSU_FZp]O]7P uHU>k@ΤN[r$Mר45'FC`-ߜ `7L]qOM*maXw( h.mV&G# \~ U-ZBDaU8)6u E#8F`'NJy-fh,z+k}9^QQkf;8Vk«6vNBܙݱ_h1Jr" OZöĒDG] ђe0aS[x4g* ͜?˜o0㷚r1 R[alY7Ib(T-? A-)s /FQִ r“b? G2*ŧqsӭ/Sp;nN +4kޟ`Ju,nEXѢl\(ٲw 9XEgmY?QgEѣ ,JOHYs\d;3[+$Ne}ajTl$1.df(Ym/W}`jOH/j9YVXTV~?N,J͙.OZVo4 gmYtݿO]v,hQYܺ{?Qk˯o, Qk˿oٴ7Qt41EPůKz7S_Z@L@Z݆( 4RLRb4RP+ zRX|S!ɭ_\}A\sA((((h3RR3EQ@X3Gz(@j {0( G"Es/tG?V5-VcA$ ZǘH ; _Ajs#tfLL J3Tfe9v kD\P f\1*A#$9>\sޟ_U2n) tnZu#ޚW-Fyʄ׽gj"jO9nen- Oj Ԋ7IS4 >%Cpx7\V-vKq(h$b[f<0"J~^{Ԗɸ띨IIkXdU$+|XM]2%֖S~汯*~V>1ӃQ]|ekA5X1]]ܷ1'ՁqJ5-,rsqC2֚TXz?H( VLٶ<]~֬~^DchPOʦz36[hZxf-ǵ9~( TY@9ORu?8ҐpH aY'kBQ49G5˶'$l-.bqƚz֦Aފ^Z V<"SVXwaIE QEQER@H:Rъ (@$QE (4PQEQ҃@-%-I@\MtO,?W7 IE{Ơ"SYY!mzkeS&($ T䑧l,GH;H1Â* I&Pa@>£rNyFgd~5IR*d qs|*m\{j瞸*6Tmip;{׷oyr8'*({Pٔ}63@!®ĖVQǏ޾Y s64 vֆ[8w~-"sʢ0PB;kׂcǏsN«ҥ/"dn!p2Āӧ\9q 1ֶz#Z͒t=qIi,c8V0sBC)4%;WdA64`ǖ5a"\դA´{3 ʂ[)!Af=";ޣ{GO_l\=:\I]ճ .3 9eb2:=yɬ3[) 9 JB@no13Z#{zl,2wW2XqFѯ1*+HPm=v^w9_ D\>"q * m:űsm|Cdxt6ǀRsI%urBw+|\׈4fQ<1]lJd9lӣqH9$ A8k k:]2I#i9S߭sw0S0PpVtXl i[< K/#}=)$4ze)\# ;ާBIU' S| JCfm-֡TgW:|@ø'H!2N8ϥU< JfIS`?#3zIM9o_cio 'f{zc8#*0stHۜ_K9lRG|sU$Xr%yJG1 w=TX;kJm.8ԕ u_ֲ緑pBeksI5<-C:5!U'+92MG|q;zvyדi5FM[ g͕F`shM#3Tv!7eyd.,kgēw:;Tz+KHW͟1ǚMBUG][<{QrWP9,qFf w,{Uۈ]6;tDrGnRڗവUC\dg\4C;{VA-+ 9=zcAh7! ȦV=`tR$P]snV/d!vU{B gVtQⵃ|(UKYL6|_lu&j<>]?aZɳf70#wn¢褒8*x#,2S5pA{N 栱;q#oڪwozs[vb0#^!k( cߥXa&&lT?ɫ3-J^8bzVutBE1H⻉+~ut1C0+yR6CXv57qeY ՠ Dc*a֩[IA'Z #!zV?[>}k{ &FHi[Bk%!4q(ҥ# ͭ?zfV=K(((((QގfAisH(4 Jh/Z) &(EGz([QuqEc& tEs&sQżgtVR*%M#=M2R/>QY+iBY%OoJvO+"5mAJ#֮{֒o.aTyܗr$# UGE羔ح1Q#tNRyEdd9YTbNwcTm[RpQH=3lywρ=:fI߳=NzsS J0s$:$+ǚ"1]'2g.JY1ֹZC۱' N;;'aȫx'Xr.;dgJցS֓DE!qֳ|`?☼'*e]ʹ2 9+Id?Zjb M4Ҹ4Ͱ4IME#P|M!믪"W+*QKIREPEPIEzEF(R P())ԝ-'jZ() :Q@Kz1(:ksGe:umAXzn#Zvjm4N (9P@>QqX2@ ? ړqI2 jѵ=' }7W60xv!ƒ͑(c*8g"f?x!͐ni9*~Pp>ʲ6WXϗ#C^N#W*x@zѽF~Zi2+WCccF9Vݏ֡K#Mr(uYJ(yǵ-Ěl JQmf VUe%A;Tnj{֎!wvV,]ܝqץswz-Nyj+nX8V%¸:mGsU29䌏ΨP#ޛJxhV!))})($ZCE!hM!{+(V=s_VUs=DQ@Q@ EPAEu hP@%()i(4R04E[R?-/jA)H48S(KA|FNe b3 VL]K13YMqfn8'Fj]v($otɥttYO¹bA Î3{xKyB۲=#DL79ڈ:Z%b.Vsٺ"p),>p= T^_?hYE FP%{ҹ]äؤ J%I Aq#O1.OJt G+n.te 1'rxV!Pc^m}*_2#6/ιp]/nIz̈́lэʥxNxLZ/&2䝿S^OSHJ!@S4i JAAj#Os*$Ӟ?lRO{*Q5'z#1%gن &SPDBS=*)M`R=(!AJc$PÏ0މ=itW4Q-SkΜ4#XO46VF4V usTbޙoP}+$9[)IY۫kg֕4MlaM=i;d9@͑j\ԇU*HyHg!@4EYLϦ#3cIʟ&9n W#UN8xkcgZ]#_ggvȧxd#g݌XW'E]Iae!gm][ =QqԳɽ(nhc5$޴e :a ihLr3zl#ZS< y8yu;?Zm/sGAxC?V]jC?QʮwQEHQ@Q@ E%QEu-%(u(4vEP)i;Q@ EPE%mOAw]N OWS+/uZg?"TN'!i 9,¸bOz֮ 9?RKc+D(4r)q[B[pZhMsA70lSdmx$-$i(HRR 撐A!" .VfT<#cMq֛IEcÉլ5`nb ovgp@8.3GV"YmĈ7m<S\wzKk3<;@)\eO'9kVST6Mu&KDRMHNW?6}@ǤAI֨bE)i)hM!믪"SV]sB*@(((CGcGZ1]FBZJ(-%RR(@sF8GE-%( M! ڙ]qԚ{hhu/{5jΠb Eb4juw%ėbX{W8\v8WuqPjȓъ[1r:ӈ0INc6g-Ģ($JZJ(RQEM4JւvsB P(ikQ@-P*ޗq  jEQfk12SkfHg͏*j/{% ^Amjb@3Qw8IKր3LR|wMlF%-%-RP/XZF.8Z8\zԱҨOȚv_Kqw2y<@sޯK})m9YL.G )Ym1,IV1Ģ))(  ) - y R<-AE-(ZJZ(@=HehdFH viiO\j:PSM,~]v0 ycBxAw/r!RG#RhG'Gz^IZKIA!AIKڀGC_Q̭?z?Y4(QEQEQERWQQ@ Z((4QE ^QAHAK@zZJV /*os\A5+m D^jxy}Sr$':+,*Ý"3mPsTmۯ*`y zSFNsw)wx7nF:3kKY@\2 889h!(QEPMCvAE% 8&lqzvitTH̥qJ߂ c+( ԍt)TH@ϡ5}h LQ&.T8_z̺,@24ѫ3 A85zxs zє֚f.6H*xw`a:(LGcZHGJƚSҗ#/AZ%"j%QREPEPEP斛Ndw-AEPPJZ(%@E(@EJ ))hRSA /N??k2x {QU(`2O;6l6GB,W/ `[Tsq th;\#\^p!L?]2䍣qEszI8·U̧.bR(9QEQEPRvŠ(`*w:㱪blU@q䜞-͵9Fp-F7I(,zd#]Xn\E3(BX0~#^t-O6(%33lX/oNjxrmG ӌt rYlazҀel y^RAnMaסnʲ/"wg<"FTl*#"H[cr*0='E/Ɗ)  !@?u_V]jCGԃʮwQEHŠ(((VQEu(K@REhAEP w`)i=haފWP @?s\A5X9RN~V"*0r+6uGaÂ:E)VUS *M*_ Yz12{S5@]}y9ljJSEQ ( ( (QEQE (uuXqUj&R6mnSv?,AZ}KwҹH(x-#⑪wEf$n2 8,:zա)/#8 i6m8☉X-0/?x*} [1Uq篰U9 ;q)2.l *rT|?ߟi(9G8RQE2CcG\Yuo\YBJ(aEPEPEPZJZ2 Q֐Ҋt%W (B(z)hTWQuϠ\U`C] ۯ iZ H6vF C.Vo1GTI6TtAٗ:R @`85%G='A+W"h%QR0(((E:-uz(hQA@) /zC@P!hQ@ĥ-(WR-/ߵK )e{tMuMtWl"ӱ.z&$ֽ݈Y`l  XuSڼRӮ4˶Bt pÎE 4b!.F*=45sXȸ5veqk>'pޕiybXMT:zVvs4UnYGh/r~եAwRW(z3"mco hU͐A뚣 JZ(( ;RR[ӦT4kBp*`0>(PN9&T$`RZ"H~޴)U52lC ;VW=C/S[J@w RWFњF?l?Jꭘ"jC?VUs(QEQEQEvu/z)(hQEQE-%QEQE0zϴjz(=`KG*z)X>m>߱G*z(͝C~d{C~XKoO[ϴ?U)Ym)~o>߱SQEۃ߱IX?*Y>~e}b~~f}OEAr/AQH:ˀO].?1`}GǭsY64Mlg4|FWqp@{XsҨ\D20-!Yv#j9tIpD#~`p4}3HA }*W0amiJ)ǘgaRc0 A NE[pH >ՙIi) >iu{W.vDdd;s@Ҕk*|9#($r:HQ$b&[w__cEqRwB5: a5B+:c REtQ6ܻt\\ZtbbQEbI@t(1E-RRց 4 Z(b)h 4Rb<ĿxV_j'?{VrĢ*@(((zZJ;Q%[[@C& v8[Z{YƤŵy}+P4 OO#`h%֘(D&#v㧥i(/9( {g{UM.aw"TK\0*HZ QjQpOIXN?GƖkXn"u.< ֎)آS<6'3F|ʀrsH4R \URc-z%bd}qMإHFF Ҵ)h̭*E'eq+as$c idFѨ%UXvh W?V;PUkI~6\VяaEΜmmdTX6ڼhl$`h8qѢ lYL0Z6PqQ]66VWHY]H RL Yjs,m%RLn3ՙ.#pB'Kߞiy#J#R඙qFUURI=*)f@$C# 7P7Qf7QdFi7Q`&i3LFArL Fu;ǓII CIBhi !%[է? _+3d(J(aEPEPEP endstream endobj 5 0 obj << /Filter /FlateDecode /Length 42 >> stream H*25030PA3K39K3P%+ V endstream endobj 6 0 obj << /Type /Encoding /Differences [24 /breve /caron /circumflex /dotaccent /hungarumlaut /ogonek /ring /tilde 39 /quotesingle 96 /grave 128 /bullet /dagger /daggerdbl /ellipsis /emdash /endash /florin /fraction /guilsinglleft /guilsinglright /minus /perthousand /quotedblbase /quotedblleft /quotedblright /quoteleft /quoteright /quotesinglbase /trademark /fi /fl /Lslash /OE /Scaron /Ydieresis /Zcaron /dotlessi /lslash /oe /scaron /zcaron 160 /Euro 164 /currency 166 /brokenbar 168 /dieresis /copyright /ordfeminine 172 /logicalnot /.notdef /registered /macron /degree /plusminus /twosuperior /threesuperior /acute /mu 183 /periodcentered /cedilla /onesuperior /ordmasculine 188 /onequarter /onehalf /threequarters 192 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis] >> endobj 7 0 obj << /Encoding 6 0 R /Subtype /Type1 /Name /Helv /Type /Font /BaseFont /Helvetica >> endobj 8 0 obj << /Subtype /Type1 /Name /ZaDb /Type /Font /BaseFont /ZapfDingbats >> endobj 3 0 obj << /Resources << /ProcSet [/PDF /ImageC] /XObject << /Im1 4 0 R >> >> /Type /Page /Parent 1 0 R /Contents 5 0 R /MediaBox [0 0 500 649] /CropBox [0 0 500 649] >> endobj 12 0 obj << /Type /Encoding /Differences [32 /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quotesingle /parenleft /parenright /asterisk /plus /comma /minus /period /slash /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore /grave /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde 128 /Euro 130 /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE 145 /quoteleft /quoteright /quotedblleft /quotedblright /bullet /endash /emdash /tilde /trademark /scaron /guilsinglright /oe 159 /Ydieresis /space /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen /registered /macron /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis] >> endobj 11 0 obj << /Encoding 12 0 R /Subtype /Type1 /Type /Font /BaseFont /Times-Bold >> endobj 13 0 obj << /Encoding 12 0 R /Subtype /Type1 /Type /Font /BaseFont /Times-Roman >> endobj 14 0 obj << /Encoding 12 0 R /Subtype /Type1 /Type /Font /BaseFont /Helvetica-Bold >> endobj 15 0 obj << /Encoding 12 0 R /Subtype /Type1 /Type /Font /BaseFont /Helvetica >> endobj 16 0 obj << /Filter /FlateDecode /Length 752 >> stream HtT]o0}ϯKS) Im*U6M}ql]wmax~{=|z;jQՖ%MXaA!ǢQqzI :g,+£K p]# jvHWK<߱ԕ$ҧ%($XhKv,dJ" ZYUlA_>EXyԬ(>^hqZ0%.kUKa?Q9h]–7U*7'!='޾pp0ؗY9KXQvutrwj,M>˜%iG\JV~[n$&5 9ݾ- 8;erp̥ҌɌ9u:F^ߎǮk/> CUw{( r2P=0ƴXVO7i: tN[:BvVyH2di^V%66Q!C*Iu2OXxU.(,FqȆaq!n?G_ _Ҭ1 endstream endobj 10 0 obj << /Resources << /Font << /F5 11 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 16 0 R /MediaBox [0 0 595 792] /CropBox [0 0 595 792] >> endobj 19 0 obj << /Length 10202 >> stream q 1 0 0 1 72 36 cm BT /F9 19 Tf 163.239 697.19 Td 0.000 Tc(Table of Contents)Tj /F5 11 Tf -163.239 -22.81 Td(An)Tj 14.058 0 Td( Introduction)Tj 62.645 0 Td( to)Tj 11.913 0 Td( Genetic)Tj 38.797 0 Td( Algorithms)Tj 54.337 0 Td(............................................................................................................1)Tj /F4 11 Tf -145.75 -13.2 Td(Mitchell)Tj 37.279 0 Td( Melanie)Tj 36.971 0 Td(......................................................................................................................................1)Tj /F5 11 Tf -110.25 -26.4 Td(Chapter)Tj 39.105 0 Td( 1:)Tj 11.913 0 Td( Genetic)Tj 38.797 0 Td( Algorithms:)Tj 59.576 0 Td( An)Tj 16.808 0 Td( Overview)Tj 45.801 0 Td(.................................................................................................2)Tj /F4 11 Tf -176 -13.2 Td(Overview)Tj 41.25 0 Td(..................................................................................................................................................2)Tj -41.25 -13.2 Td(1.1)Tj 13.75 0 Td( A)Tj 10.692 0 Td( BRIEF)Tj 33.924 0 Td( HISTORY)Tj 50.413 0 Td( OF)Tj 16.808 0 Td( EVOLUTIONARY)Tj 89.507 0 Td( COMPUTATION)Tj 81.906 0 Td(.....................................................2)Tj -297 -13.2 Td(1.2)Tj 13.75 0 Td( THE)Tj 24.134 0 Td( APPEAL)Tj 44.308 0 Td( OF)Tj 16.808 0 Td( EVOLUTION)Tj 66 0 Td(.....................................................................................................4)Tj -165 -13.2 Td(1.3)Tj 13.75 0 Td( BIOLOGICAL)Tj 69.96 0 Td( TERMINOLOGY)Tj 81.29 0 Td(.....................................................................................................5)Tj -165 -13.2 Td(1.4)Tj 13.75 0 Td( SEARCH)Tj 46.145 0 Td( SPACES)Tj 43.098 0 Td( AND)Tj 26.576 0 Td( FITNESS)Tj 46.145 0 Td( LANDSCAPES)Tj 71.786 0 Td(.......................................................................6)Tj -247.5 -13.2 Td(1.5)Tj 13.75 0 Td( ELEMENTS)Tj 60.192 0 Td( OF)Tj 16.808 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 73.953 0 Td(...................................................................................7)Tj -178.5 -13.2 Td(Examples)Tj 43.384 0 Td( of)Tj 11.913 0 Td( Fitness)Tj 33.924 0 Td( Functions)Tj 45.279 0 Td(...................................................................................................7)Tj -134.5 -13.2 Td(GA)Tj 15.884 0 Td( Operators)Tj 44.366 0 Td(..............................................................................................................................8)Tj -96.25 -13.2 Td(1.6)Tj 13.75 0 Td( A)Tj 10.692 0 Td( SIMPLE)Tj 41.866 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHM)Tj 68.145 0 Td(..............................................................................................8)Tj -184.25 -13.2 Td(1.7)Tj 13.75 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 74.855 0 Td( AND)Tj 26.576 0 Td( TRADITIONAL)Tj 77.286 0 Td( SEARCH)Tj 46.145 0 Td( METHODS)Tj 55.341 0 Td(..................................10)Tj -343.75 -13.2 Td(1.9)Tj 13.75 0 Td( TWO)Tj 27.797 0 Td( BRIEF)Tj 33.924 0 Td( EXAMPLES)Tj 59.279 0 Td(..............................................................................................................12)Tj -98.75 -13.2 Td(Using)Tj 26.279 0 Td( GAs)Tj 22.913 0 Td( to)Tj 11.308 0 Td( Evolve)Tj 33.913 0 Td( Strategies)Tj 46.134 0 Td( for)Tj 15.576 0 Td( the)Tj 16.192 0 Td( Prisoner's)Tj 45.672 0 Td( Dilemma)Tj 43.013 0 Td(...................................................13)Tj -261 -13.2 Td(Hosts)Tj 25.058 0 Td( and)Tj 18.634 0 Td( Parasites:)Tj 44.913 0 Td( Using)Tj 29.029 0 Td( GAs)Tj 22.913 0 Td( to)Tj 11.308 0 Td( Evolve)Tj 33.913 0 Td( Sorting)Tj 35.145 0 Td( Networks)Tj 42.837 0 Td(..................................................16)Tj -299.75 -13.2 Td(1.10)Tj 19.25 0 Td( HOW)Tj 29.018 0 Td( DO)Tj 18.634 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 74.855 0 Td( WORK?)Tj 39.446 0 Td(...........................................................................21)Tj -231 -13.2 Td(THOUGHT)Tj 53.152 0 Td( EXERCISES)Tj 59.598 0 Td(......................................................................................................................23)Tj -112.75 -13.2 Td(COMPUTER)Tj 59.895 0 Td( EXERCISES)Tj 61.105 0 Td(...................................................................................................................24)Tj /F5 11 Tf -157 -26.4 Td(Chapter)Tj 39.105 0 Td( 2:)Tj 11.913 0 Td( Genetic)Tj 38.797 0 Td( Algorithms)Tj 55.913 0 Td( in)Tj 11.924 0 Td( Problem)Tj 43.076 0 Td( Solving)Tj 36.022 0 Td(......................................................................................27)Tj /F4 11 Tf -200.75 -13.2 Td(Overview)Tj 41.25 0 Td(................................................................................................................................................27)Tj -41.25 -13.2 Td(2.1)Tj 13.75 0 Td( EVOLVING)Tj 59.565 0 Td( COMPUTER)Tj 62.645 0 Td( PROGRAMS)Tj 62.04 0 Td(.......................................................................................27)Tj -162 -13.2 Td(Evolving)Tj 40.337 0 Td( Lisp)Tj 22.308 0 Td( Programs)Tj 44.355 0 Td(...........................................................................................................27)Tj -107 -13.2 Td(Evolving)Tj 40.337 0 Td( Cellular)Tj 38.192 0 Td( Automata)Tj 44.971 0 Td(.....................................................................................................34)Tj -159.5 -13.2 Td(2.2)Tj 13.75 0 Td( DATA)Tj 33.297 0 Td( ANALYSIS)Tj 57.134 0 Td( AND)Tj 26.576 0 Td( PREDICTION)Tj 67.243 0 Td(.......................................................................................42)Tj -162 -13.2 Td(Predicting)Tj 45.221 0 Td( Dynamical)Tj 51.018 0 Td( Systems)Tj 38.261 0 Td(.................................................................................................42)Tj -134.5 -13.2 Td(Predicting)Tj 45.221 0 Td( Protein)Tj 34.529 0 Td( Structure)Tj 41 0 Td(......................................................................................................47)Tj -156.75 -13.2 Td(2.3)Tj 13.75 0 Td( EVOLVING)Tj 59.565 0 Td( NEURAL)Tj 47.355 0 Td( NETWORKS)Tj 63.58 0 Td(............................................................................................49)Tj -148.25 -13.2 Td(Evolving)Tj 40.337 0 Td( Weights)Tj 39.413 0 Td( in)Tj 11.308 0 Td( a)Tj 7.634 0 Td( Fixed)Tj 27.808 0 Td( Network)Tj 41 0 Td(.....................................................................................50)Tj -167.5 -13.2 Td(Evolving)Tj 40.337 0 Td( Network)Tj 41.239 0 Td( Architectures)Tj 61.174 0 Td(..............................................................................................53)Tj -142.75 -13.2 Td(Direct)Tj 27.489 0 Td( Encoding)Tj 43.761 0 Td(........................................................................................................................54)Tj -71.25 -13.2 Td(Grammatical)Tj 57.431 0 Td( Encoding)Tj 44.069 0 Td(.............................................................................................................55)Tj -101.5 -13.2 Td(Evolving)Tj 40.337 0 Td( a)Tj 7.634 0 Td( Learning)Tj 42.46 0 Td( Rule)Tj 22.069 0 Td(.........................................................................................................58)Tj -148.5 -13.2 Td(THOUGHT)Tj 53.152 0 Td( EXERCISES)Tj 59.598 0 Td(......................................................................................................................60)Tj -112.75 -13.2 Td(COMPUTER)Tj 59.895 0 Td( EXERCISES)Tj 61.105 0 Td(...................................................................................................................62)Tj /F5 11 Tf -157 -26.4 Td(Chapter)Tj 39.105 0 Td( 3:)Tj 11.913 0 Td( Genetic)Tj 38.797 0 Td( Algorithms)Tj 55.913 0 Td( in)Tj 11.924 0 Td( Scientific)Tj 46.134 0 Td( Models)Tj 35.714 0 Td(.....................................................................................65)Tj /F4 11 Tf -203.5 -13.2 Td(Overview)Tj 41.25 0 Td(................................................................................................................................................65)Tj -41.25 -13.2 Td(3.1)Tj 13.75 0 Td( MODELING)Tj 61.402 0 Td( INTERACTIONS)Tj 82.797 0 Td( BETWEEN)Tj 55.297 0 Td( LEARNING)Tj 58.96 0 Td( AND)Tj 26.576 0 Td( EVOLUTION)Tj 64.218 0 Td(...........................66)Tj -327 -13.2 Td(The)Tj 17.105 0 Td( Baldwin)Tj 40.029 0 Td( Effect)Tj 27.866 0 Td(...................................................................................................................66)Tj -85 -13.2 Td(A)Tj 7.942 0 Td( Simple)Tj 33.924 0 Td( Model)Tj 31.471 0 Td( of)Tj 11.913 0 Td( the)Tj 16.192 0 Td( Baldwin)Tj 40.029 0 Td( Effect)Tj 28.779 0 Td(....................................................................................68)Tj -170.25 -13.2 Td(Evolutionary)Tj 57.442 0 Td( Reinforcement)Tj 68.123 0 Td( Learning)Tj 41.935 0 Td(.....................................................................................72)Tj -203.5 -13.2 Td(3.2)Tj 13.75 0 Td( MODELING)Tj 61.402 0 Td( SEXUAL)Tj 46.134 0 Td( SELECTION)Tj 60.214 0 Td(.............................................................................................75)Tj -145.5 -13.2 Td(Simulation)Tj 48.29 0 Td( and)Tj 18.634 0 Td( Elaboration)Tj 54.076 0 Td( of)Tj 11.913 0 Td( a)Tj 7.634 0 Td( Mathematical)Tj 63.239 0 Td( Model)Tj 31.471 0 Td( for)Tj 15.576 0 Td( Sexual)Tj 32.692 0 Td( Selection)Tj 43.475 0 Td(...........................76)Tj -363 -13.2 Td(3.3)Tj 13.75 0 Td( MODELING)Tj 61.402 0 Td( ECOSYSTEMS)Tj 73.348 0 Td(.........................................................................................................78)Tj -148.5 -13.2 Td(3.4)Tj 13.75 0 Td( MEASURING)Tj 68.134 0 Td( EVOLUTIONARY)Tj 89.507 0 Td( ACTIVITY)Tj 54.109 0 Td(.............................................................................81)Tj -225.5 -13.2 Td(Thought)Tj 37.279 0 Td( Exercises)Tj 42.471 0 Td(..................................................................................................................................84)Tj -79.75 -13.2 Td(Computer)Tj 44 0 Td( Exercises)Tj 44 0 Td(...............................................................................................................................85)Tj ET Q endstream endobj 18 0 obj << /Resources << /Font << /F5 11 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 19 0 R /MediaBox [0 0 595 792] >> endobj 22 0 obj << /Length 10198 >> stream q 1 0 0 1 72 36 cm BT /F9 19 Tf 163.239 697.19 Td 0.000 Tc(Table of Contents)Tj /F5 11 Tf -163.239 -22.81 Td(Chapter)Tj 39.105 0 Td( 4:)Tj 11.913 0 Td( Theoretical)Tj 56.518 0 Td( Foundations)Tj 61.435 0 Td( of)Tj 11.913 0 Td( Genetic)Tj 38.797 0 Td( Algorithms)Tj 55.569 0 Td(........................................................................87)Tj /F4 11 Tf -239.25 -13.2 Td(Overview)Tj 41.25 0 Td(................................................................................................................................................87)Tj -41.25 -13.2 Td(4.1)Tj 13.75 0 Td( SCHEMAS)Tj 54.703 0 Td( AND)Tj 26.576 0 Td( THE)Tj 24.134 0 Td( TWO-ARMED)Tj 73.722 0 Td( BANDIT)Tj 44.297 0 Td( PROBLEM)Tj 54.318 0 Td(.....................................................87)Tj -255.5 -13.2 Td(The)Tj 17.105 0 Td( Two-Armed)Tj 59.664 0 Td( Bandit)Tj 32.087 0 Td( Problem)Tj 39.394 0 Td(............................................................................................88)Tj -148.25 -13.2 Td(Sketch)Tj 29.942 0 Td( of)Tj 11.913 0 Td( a)Tj 7.634 0 Td( Solution)Tj 38.261 0 Td(..................................................................................................................89)Tj -87.75 -13.2 Td(Interpretation)Tj 59.873 0 Td( of)Tj 11.913 0 Td( the)Tj 16.192 0 Td( Solution)Tj 38.272 0 Td(....................................................................................................91)Tj -126.25 -13.2 Td(Implications)Tj 55 0 Td( for)Tj 15.576 0 Td( GA)Tj 18.634 0 Td( Performance)Tj 56.29 0 Td(.............................................................................................92)Tj -145.5 -13.2 Td(Deceiving)Tj 45.21 0 Td( a)Tj 7.634 0 Td( Genetic)Tj 36.96 0 Td( Algorithm)Tj 47.446 0 Td(................................................................................................93)Tj -137.25 -13.2 Td(Limitations)Tj 50.732 0 Td( of)Tj 11.913 0 Td( "Static")Tj 36.784 0 Td( Schema)Tj 37.576 0 Td( Analysis)Tj 38.745 0 Td(..................................................................................93)Tj -211.75 -13.2 Td(4.2)Tj 13.75 0 Td( ROYAL)Tj 40.634 0 Td( ROADS)Tj 39.116 0 Td(.............................................................................................................................94)Tj -57.5 -13.2 Td(Royal)Tj 26.279 0 Td( Road)Tj 25.971 0 Td( Functions)Tj 43.75 0 Td(...............................................................................................................94)Tj -96 -13.2 Td(Experimental)Tj 59.268 0 Td( Results)Tj 33.982 0 Td(................................................................................................................95)Tj -93.25 -13.2 Td(Steepest-ascent)Tj 70.356 0 Td( hill)Tj 17.424 0 Td( climbing)Tj 41.866 0 Td( \(SAHC\))Tj 37.854 0 Td(.....................................................................................96)Tj -167.5 -13.2 Td(Next-ascent)Tj 55.077 0 Td( hill)Tj 17.424 0 Td( climbing)Tj 41.866 0 Td( \(NAHC\))Tj 39.383 0 Td(..........................................................................................96)Tj -153.75 -13.2 Td(Random-mutation)Tj 82.599 0 Td( hill)Tj 17.424 0 Td( climbing)Tj 41.866 0 Td( \(RMHC\))Tj 42.111 0 Td(...............................................................................96)Tj -184 -13.2 Td(Analysis)Tj 38.5 0 Td( of)Tj 11.913 0 Td( Random-Mutation)Tj 86.57 0 Td( Hill)Tj 19.866 0 Td( Climbing)Tj 43.651 0 Td(.........................................................................97)Tj -200.5 -13.2 Td(Hitchhiking)Tj 52.558 0 Td( in)Tj 11.308 0 Td( the)Tj 16.192 0 Td( Genetic)Tj 36.96 0 Td( Algorithm)Tj 47.732 0 Td(......................................................................................98)Tj -164.75 -13.2 Td(An)Tj 13.442 0 Td( Idealized)Tj 43.065 0 Td( Genetic)Tj 36.96 0 Td( Algorithm)Tj 46.533 0 Td(...............................................................................................99)Tj -176 -13.2 Td(4.3)Tj 13.75 0 Td( EXACT)Tj 39.413 0 Td( MATHEMATICAL)Tj 91.96 0 Td( MODELS)Tj 47.971 0 Td( OF)Tj 16.808 0 Td( SIMPLE)Tj 41.866 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 72.435 0 Td(.....................103)Tj -338 -13.2 Td(Formalization)Tj 61.721 0 Td( of)Tj 11.913 0 Td( GAs)Tj 22.366 0 Td(.............................................................................................................103)Tj -96 -13.2 Td(Results)Tj 32.395 0 Td( of)Tj 11.913 0 Td( the)Tj 16.192 0 Td( Formalization)Tj 63 0 Td(...................................................................................................108)Tj -123.5 -13.2 Td(A)Tj 7.942 0 Td( Finite-Population)Tj 82.302 0 Td( Model)Tj 30.506 0 Td(....................................................................................................108)Tj -156.75 -13.2 Td(4.4)Tj 13.75 0 Td( STATISTICAL-MECHANICS)Tj 143.396 0 Td( APPROACHES)Tj 73.854 0 Td(.........................................................................112)Tj -231 -13.2 Td(THOUGHT)Tj 53.152 0 Td( EXERCISES)Tj 59.598 0 Td(....................................................................................................................114)Tj -112.75 -13.2 Td(COMPUTER)Tj 59.895 0 Td( EXERCISES)Tj 61.105 0 Td(.................................................................................................................116)Tj -121 -13.2 Td(5.1)Tj 13.75 0 Td( WHEN)Tj 35.739 0 Td( SHOULD)Tj 47.355 0 Td( A)Tj 10.692 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHM)Tj 68.739 0 Td( BE)Tj 16.808 0 Td( USED?)Tj 34.87 0 Td(........................................................116)Tj -277.75 -13.2 Td(5.2)Tj 13.75 0 Td( ENCODING)Tj 60.181 0 Td( A)Tj 10.692 0 Td( PROBLEM)Tj 54.703 0 Td( FOR)Tj 24.145 0 Td( A)Tj 10.692 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHM)Tj 67.54 0 Td(...................................................117)Tj -255.5 -13.2 Td(Binary)Tj 29.942 0 Td( Encodings)Tj 46.808 0 Td(....................................................................................................................117)Tj -76.75 -13.2 Td(Many-Character)Tj 74.624 0 Td( and)Tj 18.634 0 Td( Real-Valued)Tj 60.885 0 Td( Encodings)Tj 49.107 0 Td(......................................................................118)Tj -203.25 -13.2 Td(Tree)Tj 20.152 0 Td( Encodings)Tj 48.348 0 Td(.......................................................................................................................118)Tj -104.5 -13.2 Td(5.3)Tj 13.75 0 Td( ADAPTING)Tj 58.96 0 Td( THE)Tj 24.134 0 Td( ENCODING)Tj 59.906 0 Td(....................................................................................................118)Tj -120.75 -13.2 Td(Inversion)Tj 41 0 Td(.................................................................................................................................119)Tj -41 -13.2 Td(Evolving)Tj 40.337 0 Td( Crossover)Tj 47.355 0 Td( "Hot)Tj 23.738 0 Td( Spots")Tj 31.32 0 Td(............................................................................................120)Tj -142.75 -13.2 Td(Messy)Tj 28.721 0 Td( Gas)Tj 17.779 0 Td(...............................................................................................................................121)Tj -82.5 -13.2 Td(5.4)Tj 13.75 0 Td( SELECTION)Tj 62.634 0 Td( METHODS)Tj 55.616 0 Td(.............................................................................................................124)Tj -96 -13.2 Td(Fitness-Proportionate)Tj 97.262 0 Td( Selection)Tj 43.692 0 Td( with)Tj 22.308 0 Td( "Roulette)Tj 44.517 0 Td( Wheel")Tj 35.948 0 Td( and)Tj 18.634 0 Td( "Stochastic)Tj 52.459 0 Td( Universal")Tj -314.82 -13.2 Td( Sampling)Tj 43.75 0 Td(................................................................................................................................124)Tj -43.75 -13.2 Td(Sigma)Tj 28.116 0 Td( Scaling)Tj 34.884 0 Td(.........................................................................................................................125)Tj -63 -13.2 Td(Elitism)Tj 30 0 Td(.....................................................................................................................................126)Tj -30 -13.2 Td(Boltzmann)Tj 48.279 0 Td( Selection)Tj 42.221 0 Td(...............................................................................................................126)Tj -90.5 -13.2 Td(Rank)Tj 23.221 0 Td( Selection)Tj 42.529 0 Td(........................................................................................................................127)Tj -65.75 -13.2 Td(Tournament)Tj 53.768 0 Td( Selection)Tj 42.232 0 Td(.............................................................................................................127)Tj -96 -13.2 Td(Steady-State)Tj 58.146 0 Td( Selection)Tj 43.354 0 Td(...........................................................................................................128)Tj -137.5 -13.2 Td(5.5)Tj 13.75 0 Td( GENETIC)Tj 49.797 0 Td( OPERATORS)Tj 65.703 0 Td(..............................................................................................................128)Tj -93.25 -13.2 Td(Crossover)Tj 43.75 0 Td(................................................................................................................................128)Tj -43.75 -13.2 Td(Mutation)Tj 38.25 0 Td(..................................................................................................................................129)Tj -38.25 -13.2 Td(Other)Tj 25.047 0 Td( Operators)Tj 46.123 0 Td( and)Tj 18.634 0 Td( Mating)Tj 34.529 0 Td( Strategies)Tj 45.917 0 Td(..................................................................................130)Tj -206.25 -13.2 Td(5.6)Tj 13.75 0 Td( PARAMETERS)Tj 75.482 0 Td( FOR)Tj 24.145 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 73.326 0 Td(.......................................................................130)Tj -236.5 -13.2 Td(THOUGHT)Tj 53.152 0 Td( EXERCISES)Tj 59.598 0 Td(....................................................................................................................132)Tj -112.75 -13.2 Td(COMPUTER)Tj 59.895 0 Td( EXERCISES)Tj 61.105 0 Td(.................................................................................................................133)Tj ET Q endstream endobj 21 0 obj << /Resources << /Font << /F5 11 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 22 0 R /MediaBox [0 0 595 792] >> endobj 25 0 obj << /Length 4896 >> stream q 1 0 0 1 72 36 cm BT /F9 19 Tf 163.239 697.19 Td 0.000 Tc(Table of Contents)Tj /F5 11 Tf -163.239 -22.81 Td(Chapter)Tj 39.105 0 Td( 6:)Tj 11.913 0 Td( Conclusions)Tj 59.598 0 Td( and)Tj 20.482 0 Td( Future)Tj 35.134 0 Td( Directions)Tj 48.518 0 Td(............................................................................................135)Tj /F4 11 Tf -178.75 -13.2 Td(Overview)Tj 41.25 0 Td(..............................................................................................................................................135)Tj -41.25 -13.2 Td(Incorporating)Tj 59.873 0 Td( Ecological)Tj 49.797 0 Td( Interactions)Tj 52.58 0 Td(..................................................................................................136)Tj -162.25 -13.2 Td(Incorporating)Tj 59.873 0 Td( New)Tj 23.518 0 Td( Ideas)Tj 25.96 0 Td( from)Tj 24.134 0 Td( Genetics)Tj 39.765 0 Td(..............................................................................................136)Tj -173.25 -13.2 Td(Incorporating)Tj 59.873 0 Td( Development)Tj 62.018 0 Td( and)Tj 18.634 0 Td( Learning)Tj 40.975 0 Td(...........................................................................................137)Tj -181.5 -13.2 Td(Adapting)Tj 40.942 0 Td( Encodings)Tj 49.192 0 Td( and)Tj 18.634 0 Td( Using)Tj 29.029 0 Td( Encodings)Tj 49.192 0 Td( That)Tj 22.913 0 Td( Permit)Tj 32.087 0 Td( Hierarchy)Tj 46.728 0 Td( and)Tj 18.634 0 Td( Open-Endedness)Tj 77.649 0 Td(.................137)Tj -385 -13.2 Td(Adapting)Tj 40.942 0 Td( Parameters)Tj 49.808 0 Td(............................................................................................................................137)Tj -90.75 -13.2 Td(Connections)Tj 55 0 Td( with)Tj 22.308 0 Td( the)Tj 16.192 0 Td( Mathematical)Tj 63.239 0 Td( Genetics)Tj 41.239 0 Td( Literature)Tj 44.022 0 Td(.....................................................................138)Tj -242 -13.2 Td(Extension)Tj 44 0 Td( of)Tj 11.913 0 Td( Statistical)Tj 46.145 0 Td( Mechanics)Tj 50.402 0 Td( Approaches)Tj 53.79 0 Td(..................................................................................138)Tj -206.25 -13.2 Td(Identifying)Tj 48.884 0 Td( and)Tj 18.634 0 Td( Overcoming)Tj 57.739 0 Td( Impediments)Tj 60.192 0 Td( to)Tj 11.308 0 Td( the)Tj 16.192 0 Td( Success)Tj 37.576 0 Td( of)Tj 11.913 0 Td( GAs)Tj 20.812 0 Td(......................................................138)Tj -283.25 -13.2 Td(Understanding)Tj 64.768 0 Td( the)Tj 16.192 0 Td( Role)Tj 23.529 0 Td( of)Tj 11.913 0 Td( Schemas)Tj 41.855 0 Td( in)Tj 11.308 0 Td( GAs)Tj 20.185 0 Td(........................................................................................138)Tj -189.75 -13.2 Td(Understanding)Tj 64.768 0 Td( the)Tj 16.192 0 Td( Role)Tj 23.529 0 Td( of)Tj 11.913 0 Td( Crossover)Tj 45.848 0 Td(..................................................................................................139)Tj -162.25 -13.2 Td(Theory)Tj 31.768 0 Td( of)Tj 11.913 0 Td( GAs)Tj 22.913 0 Td( With)Tj 24.75 0 Td( Endogenous)Tj 57.134 0 Td( Fitness)Tj 33.022 0 Td(...........................................................................................139)Tj /F5 11 Tf -217.5 -26.4 Td(Appendix)Tj 45.848 0 Td( A:)Tj 14.355 0 Td( Selected)Tj 41.239 0 Td( General)Tj 40.634 0 Td( References)Tj 53.424 0 Td(...................................................................................................140)Tj -195.5 -26.4 Td(Appendix)Tj 45.848 0 Td( B:)Tj 13.75 0 Td( Other)Tj 30.855 0 Td( Resources)Tj 50.047 0 Td(.......................................................................................................................141)Tj /F4 11 Tf -104.5 -13.2 Td(SELECTED)Tj 55 0 Td( JOURNALS)Tj 58.971 0 Td( PUBLISHING)Tj 68.134 0 Td( WORK)Tj 36.355 0 Td( ON)Tj 18.634 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 73.359 0 Td(..........................141)Tj -360.25 -13.2 Td(SELECTED)Tj 55 0 Td( ANNUAL)Tj 49.181 0 Td( OR)Tj 18.029 0 Td( BIANNUAL)Tj 60.181 0 Td( CONFERENCES)Tj 80.982 0 Td( INCLUDING)Tj 63.844 0 Td( WORK)Tj 36.355 0 Td( ON)Tj -363.572 -13.2 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 73.953 0 Td(................................................................................................................141)Tj -123.75 -13.2 Td(INTERNET)Tj 53.768 0 Td( MAILING)Tj 50.402 0 Td( LISTS,)Tj 34.837 0 Td( WORLD)Tj 43.076 0 Td( WIDE)Tj 31.46 0 Td( WEB)Tj 27.192 0 Td( SITES,)Tj 34.837 0 Td( AND)Tj 26.576 0 Td( NEWS)Tj 33.913 0 Td( GROUPS)Tj 46.145 0 Td( WITH)Tj -382.206 -13.2 Td( INFORMATION)Tj 79.739 0 Td( AND)Tj 26.576 0 Td( DISCUSSIONS)Tj 73.645 0 Td( ON)Tj 18.634 0 Td( GENETIC)Tj 49.797 0 Td( ALGORITHMS)Tj 73.359 0 Td(........................................142)Tj -321.75 -13.2 Td(Bibliography)Tj 57.75 0 Td(........................................................................................................................................143)Tj ET Q endstream endobj 24 0 obj << /Resources << /Font << /F5 11 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 25 0 R /MediaBox [0 0 595 792] >> endobj 28 0 obj << /Encoding 12 0 R /Subtype /Type1 /Type /Font /BaseFont /Times-Italic >> endobj 29 0 obj << /Length 4385 >> stream q 1 0 0 1 72 36 cm BT /F9 19 Tf 0 678.992 Td 0.000 Tc(Chapter 1: Genetic Algorithms: An Overview)Tj /F9 15.8 Tf 0 -32.842 Td(Overview)Tj /F4 11 Tf 0 -27.368 Td(Science arises from the very human desire to understand and control the world. Over the course of history, we)Tj 0 -13.2 Td(humans have gradually built up a grand edifice of knowledge that enables us to predict, to varying extents, the)Tj 0 -13.2 Td(weather, the motions of the planets, solar and lunar eclipses, the courses of diseases, the rise and fall of)Tj 0 -13.2 Td(economic growth, the stages of language development in children, and a vast panorama of other natural,)Tj 0 -13.2 Td(social, and cultural phenomena. More recently we have even come to understand some fundamental limits to)Tj 0 -13.2 Td(our abilities to predict. Over the eons we have developed increasingly complex means to control many aspects)Tj 0 -13.2 Td(of our lives and our interactions with nature, and we have learned, often the hard way, the extent to which)Tj 0 -13.2 Td(other aspects are uncontrollable.)Tj 0 -26.4 Td(The advent of electronic computers has arguably been the most revolutionary development in the history of)Tj 0 -13.2 Td(science and technology. This ongoing revolution is profoundly increasing our ability to predict and control)Tj 0 -13.2 Td(nature in ways that were barely conceived of even half a century ago. For many, the crowning achievements)Tj 0 -13.2 Td(of this revolution will be the creation\227in the form of computer programs\227of new species of intelligent)Tj 0 -13.2 Td(beings, and even of new forms of life.)Tj 0 -26.4 Td(The goals of creating artificial intelligence and artificial life can be traced back to the very beginnings of the)Tj 0 -13.2 Td(computer age. The earliest computer scientists\227Alan Turing, John von Neumann, Norbert Wiener, and)Tj 0 -13.2 Td(others\227were motivated in large part by visions of imbuing computer programs with intelligence, with the)Tj 0 -13.2 Td(life-like ability to self-replicate, and with the adaptive capability to learn and to control their environments.)Tj 0 -13.2 Td(These early pioneers of computer science were as much interested in biology and psychology as in)Tj 0 -13.2 Td(electronics, and they looked to natural systems as guiding metaphors for how to achieve their visions. It)Tj 0 -13.2 Td(should be no surprise, then, that from the earliest days computers were applied not only to calculating missile)Tj 0 -13.2 Td(trajectories and deciphering military codes but also to modeling the brain, mimicking human learning, and)Tj 0 -13.2 Td(simulating biological evolution. These biologically motivated computing activities have waxed and waned)Tj 0 -13.2 Td(over the years, but since the early 1980s they have all undergone a resurgence in the computation research)Tj 0 -13.2 Td(community. The)Tj ( first has grown into the field of neural networks, the second into machine learning, and the)Tj 0 -13.2 Td(third into what is now called "evolutionary computation," of which genetic algorithms are the most prominent)Tj 0 -13.2 Td(example.)Tj /F9 15.8 Tf 0 -57.64 Td(1.1 A BRIEF HISTORY OF EVOLUTIONARY COMPUTATION)Tj /F4 11 Tf 0 -40.568 Td(In the 1950s and the 1960s several computer scientists independently studied evolutionary systems with the)Tj 0 -13.2 Td(idea that evolution could be used as an optimization tool for engineering problems. The idea in all these)Tj 0 -13.2 Td(systems was to evolve a population of candidate solutions to a given problem, using operators inspired by)Tj 0 -13.2 Td(natural genetic variation and natural selection.)Tj 0 -26.4 Td(In the 1960s, Rechenberg \(1965, 1973\) introduced "evolution strategies" \()Tj /F6 11 Tf (Evolutionsstrategie)Tj /F4 11 Tf ( in the original)Tj 0 -13.2 Td(German\), a method he used to optimize real-valued parameters for devices such as airfoils. This idea was)Tj 0 -13.2 Td(further developed by Schwefel \(1975, 1977\). The field of evolution strategies has remained an active area of)Tj 0 -13.2 Td(research, mostly developing independently from the field of genetic algorithms \(although recently the two)Tj 0 -13.2 Td(communities have begun to interact\). \(For a short review of evolution strategies, see Back, Hoffmeister, and)Tj 0 -13.2 Td(Schwefel 1991.\) Fogel, Owens, and Walsh \(1966\) developed "evolutionary programming," a technique in)Tj /F8 11 Tf 240.442 -32.174 Td(2)Tj ET Q endstream endobj 27 0 obj << /Resources << /Font << /F6 28 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 29 0 R /MediaBox [0 0 595 792] >> endobj 32 0 obj << /Length 5165 >> stream q 1 0 0 1 72 36 cm BT /F4 11 Tf 0 687 Td 0.000 Tc(which candidate solutions to given tasks were represented as finite-state machines, which were evolved by)Tj 0 -13.2 Td(randomly mutating their state-transition diagrams and selecting the fittest. A somewhat broader formulation)Tj 0 -13.2 Td(of evolutionary programming also remains an area of active research \(see, for example, Fogel and Atmar)Tj 0 -13.2 Td(1993\). Together, evolution strategies, evolutionary programming, and genetic algorithms form the backbone)Tj 0 -13.2 Td(of the field of evolutionary computation.)Tj 0 -26.4 Td(Several other people working in the 1950s and the 1960s developed evolution-inspired algorithms for)Tj 0 -13.2 Td(optimization and machine learning. Box \(1957\), Friedman \(1959\), Bledsoe \(1961\), Bremermann \(1962\), and)Tj 0 -13.2 Td(Reed, Toombs, and Baricelli \(1967\) all worked in this area, though their work has been given little or none of)Tj 0 -13.2 Td(the kind of attention or followup that evolution strategies, evolutionary programming, and genetic algorithms)Tj 0 -13.2 Td(have seen. In addition, a number of evolutionary biologists used computers to simulate evolution for the)Tj 0 -13.2 Td(purpose of controlled experiments \(see, e.g., Baricelli 1957, 1962; Fraser 1957 a,b; Martin and Cockerham)Tj 0 -13.2 Td(1960\). Evolutionary computation was definitely in the air in the formative days of the electronic computer.)Tj 0 -26.4 Td(Genetic algorithms \(GAs\) were invented by John Holland in the 1960s and were developed by Holland and)Tj 0 -13.2 Td(his students and colleagues at the University of Michigan in the 1960s and the 1970s. In contrast with)Tj 0 -13.2 Td(evolution strategies and evolutionary programming, Holland's original goal was not to design algorithms to)Tj 0 -13.2 Td(solve specific problems, but rather to formally study the phenomenon of adaptation as it occurs in nature and)Tj 0 -13.2 Td(to)Tj ( develop ways in which the mechanisms of natural adaptation might be imported into computer systems.)Tj 0 -13.2 Td(Holland's 1975 book)Tj /F6 11 Tf ( Adaptation in Natural and Artificial Systems)Tj /F4 11 Tf ( presented the genetic algorithm as an)Tj 0 -13.2 Td(abstraction of biological evolution and gave a theoretical framework for adaptation under the GA. Holland's)Tj 0 -13.2 Td(GA is a method for moving from one population of "chromosomes" \(e.g., strings of ones and zeros, or "bits"\))Tj 0 -13.2 Td(to a new population by using a kind of "natural selection" together with the genetics-inspired operators of)Tj 0 -13.2 Td(crossover, mutation, and inversion. Each chromosome consists of "genes" \(e.g., bits\), each gene being an)Tj 0 -13.2 Td(instance of a particular "allele" \(e.g., 0 or 1\). The selection operator chooses those chromosomes in the)Tj 0 -13.2 Td(population that will be allowed to reproduce, and on average the fitter chromosomes produce more offspring)Tj 0 -13.2 Td(than the less fit ones. Crossover exchanges subparts of two chromosomes, roughly mimicking biological)Tj 0 -13.2 Td(recombination between two single-chromosome \("haploid"\) organisms; mutation randomly changes the allele)Tj 0 -13.2 Td(values of some locations in the chromosome; and inversion reverses the order of a contiguous section of the)Tj 0 -13.2 Td(chromosome, thus rearranging the order in which genes are arrayed. \(Here, as in most of the GA literature,)Tj 0 -13.2 Td("crossover" and "recombination" will mean the same thing.\))Tj 0 -26.4 Td(Holland's introduction of a population-based algorithm with crossover, inversion, and mutation was a major)Tj 0 -13.2 Td(innovation. \(Rechenberg's evolution strategies started with a "population" of two individuals, one parent and)Tj 0 -13.2 Td(one offspring, the offspring being a mutated version of the parent; many-individual populations and crossover)Tj 0 -13.2 Td(were not incorporated until later. Fogel, Owens, and Walsh's evolutionary programming likewise used only)Tj 0 -13.2 Td(mutation to provide variation.\) Moreover, Holland was the first to attempt to put computational evolution on a)Tj 0 -13.2 Td(firm theoretical footing \(see Holland 1975\). Until recently this theoretical foundation, based on the notion of)Tj 0 -13.2 Td("schemas," was the basis of almost all subsequent theoretical work on genetic algorithms)Tj 0 -26.4 Td(In the last several years there has been widespread interaction among researchers studying various)Tj 0 -13.2 Td(evolutionary computation methods, and the boundaries between GAs, evolution strategies, evolutionary)Tj 0 -13.2 Td(programming, and other evolutionary approaches have broken down to some extent. Today, researchers often)Tj 0 -13.2 Td(use the term "genetic algorithm" to describe something very far from Holland's original conception. In this)Tj 0 -13.2 Td(book I adopt this flexibility. Most of the projects I will describe here were referred to by their originators as)Tj 0 -13.2 Td(GAs; some were not, but they all have enough of a "family resemblance" that I include them under the rubric)Tj 0 -13.2 Td(of genetic algorithms.)Tj /F8 11 Tf 135.601 640.2 Td(Chapter 1: Genetic Algorithms: An Overview)Tj 104.841 -720 Td(3)Tj ET Q endstream endobj 31 0 obj << /Resources << /Font << /F6 28 0 R /F4 13 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 32 0 R /MediaBox [0 0 595 792] >> endobj 35 0 obj << /Length 5765 >> stream q 1 0 0 1 72 36 cm BT /F9 15.8 Tf 0 682.16 Td 0.000 Tc(1.2 THE APPEAL OF EVOLUTION)Tj /F4 11 Tf 0 -27.368 Td(Why use evolution as an inspiration for solving computational problems? To evolutionary-computation)Tj 0 -13.2 Td(researchers, the mechanisms of evolution)Tj ( seem well suited for some of the most pressing computational)Tj 0 -13.2 Td(problems in many fields. Many computational problems require searching through a huge number of)Tj 0 -13.2 Td(possibilities for solutions. One example is the problem of computational protein engineering, in which an)Tj 0 -13.2 Td(algorithm is sought that will search among the vast number of possible amino acid sequences for a protein)Tj 0 -13.2 Td(with specified properties. Another example is searching for a set of rules or equations that will predict the ups)Tj 0 -13.2 Td(and downs of a financial market, such as that for foreign currency. Such search problems can often benefit)Tj 0 -13.2 Td(from an effective use of parallelism, in which many different possibilities are explored simultaneously in an)Tj 0 -13.2 Td(efficient way. For example, in searching for proteins with specified properties, rather than evaluate one amino)Tj 0 -13.2 Td(acid sequence at a time it would be much faster to evaluate many simultaneously. What is needed is both)Tj 0 -13.2 Td(computational parallelism \(i.e., many processors evaluating sequences at the same time\) and an intelligent)Tj 0 -13.2 Td(strategy for choosing the next set of sequences to evaluate.)Tj 0 -26.4 Td(Many computational problems require a computer program to be)Tj /F6 11 Tf ( adaptive)Tj /F4 11 Tf (\227to continue to perform well in a)Tj 0 -13.2 Td(changing environment. This is typified by problems in robot control in which a robot has to perform a task in)Tj 0 -13.2 Td(a variable environment, and by computer interfaces that must adapt to the idiosyncrasies of different users.)Tj 0 -13.2 Td(Other problems require computer programs to be innovative\227to construct something truly new and original,)Tj 0 -13.2 Td(such as a new algorithm for accomplishing a computational task or even a new scientific discovery. Finally,)Tj 0 -13.2 Td(many computational problems require complex solutions that are difficult to program by hand. A striking)Tj 0 -13.2 Td(example is the problem of creating artificial intelligence. Early on, AI practitioners believed that it would be)Tj 0 -13.2 Td(straightforward to encode the rules that would confer intelligence on a program; expert systems were one)Tj 0 -13.2 Td(result of this early optimism. Nowadays, many AI researchers believe that the "rules" underlying intelligence)Tj 0 -13.2 Td(are too complex for scientists to encode by hand in a "top-down" fashion. Instead they believe that the best)Tj 0 -13.2 Td(route to artificial intelligence is through a "bottom-up" paradigm in which humans write only very simple)Tj 0 -13.2 Td(rules, and complex behaviors such as intelligence emerge from the massively parallel application and)Tj 0 -13.2 Td(interaction of these simple rules. Connectionism \(i.e., the study of computer programs inspired by neural)Tj 0 -13.2 Td(systems\) is one example of this philosophy \(see Smolensky 1988\); evolutionary computation is another. In)Tj 0 -13.2 Td(connectionism the rules are typically simple "neural" thresholding, activation spreading, and strengthening or)Tj 0 -13.2 Td(weakening of connections; the hoped-for emergent behavior is sophisticated pattern recognition and learning.)Tj 0 -13.2 Td(In evolutionary computation the rules are typically "natural selection" with variation due to crossover and/or)Tj 0 -13.2 Td(mutation; the hoped-for emergent behavior is the design of high-quality solutions to difficult problems and)Tj 0 -13.2 Td(the ability to adapt these solutions in the face of a changing environment.)Tj 0 -26.4 Td(Biological evolution is an appealing source of inspiration for addressing these problems. Evolution is, in)Tj 0 -13.2 Td(effect, a method of searching among)Tj ( an enormous number of possibilities for "solutions." In biology the)Tj 0 -13.2 Td(enormous set of possibilities is the set of possible genetic sequences, and the desired "solutions" are highly fit)Tj 0 -13.2 Td(organisms\227organisms well able to survive and reproduce in their environments. Evolution can also be seen)Tj 0 -13.2 Td(as a method for)Tj /F6 11 Tf ( designing)Tj /F4 11 Tf ( innovative solutions to complex problems. For example, the mammalian immune)Tj 0 -13.2 Td(system is a marvelous evolved solution to the problem of germs invading the body. Seen in this light, the)Tj 0 -13.2 Td(mechanisms of evolution can inspire computational search methods. Of course the fitness of a biological)Tj 0 -13.2 Td(organism depends on many factors\227for example, how well it can weather the physical characteristics of its)Tj 0 -13.2 Td(environment and how well it can compete with or cooperate with the other organisms around it. The fitness)Tj 0 -13.2 Td(criteria continually change as creatures evolve, so evolution is searching a constantly changing set of)Tj 0 -13.2 Td(possibilities. Searching for solutions in the face of changing conditions is precisely what is required for)Tj 0 -13.2 Td(adaptive computer programs. Furthermore, evolution is a massively parallel search method: rather than work)Tj 0 -13.2 Td(on one species at a time, evolution tests and changes millions of species in parallel. Finally, viewed from a)Tj 0 -13.2 Td(high level the "rules" of evolution are remarkably simple: species evolve by means of random variation \(via)Tj 0 -13.2 Td(mutation, recombination, and other operators\), followed by natural selection in which the fittest tend to)Tj /F8 11 Tf 135.601 685.608 Td(Chapter 1: Genetic Algorithms: An Overview)Tj 104.841 -720 Td(4)Tj ET Q endstream endobj 34 0 obj << /Resources << /Font << /F6 28 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 35 0 R /MediaBox [0 0 595 792] >> endobj 38 0 obj << /Length 5200 >> stream q 1 0 0 1 72 36 cm BT /F4 11 Tf 0 687 Td 0.000 Tc(survive and reproduce, thus propagating their genetic material to future generations. Yet these simple rules are)Tj 0 -13.2 Td(thought to be responsible, in large part, for the extraordinary variety and complexity we see in the biosphere.)Tj /F9 15.8 Tf 0 -57.64 Td(1.3 BIOLOGICAL TERMINOLOGY)Tj /F4 11 Tf 0 -27.368 Td(At this point it is useful to formally introduce some of the biological terminology that will be used throughout)Tj 0 -13.2 Td(the book. In the context of genetic algorithms, these biological terms are used in the spirit of analogy with real)Tj 0 -13.2 Td(biology, though the entities they refer to are much simpler than the real biological ones.)Tj 0 -26.4 Td(All living organisms consist of cells, and each cell contains the same set of one or more)Tj /F6 11 Tf 0 -13.2 Td(chromosomes)Tj /F4 11 Tf (\227strings of DNA\227that serve as a "blueprint" for the organism. A chromosome can be)Tj 0 -13.2 Td(conceptually divided into)Tj /F6 11 Tf ( genes)Tj /F4 11 Tf (\227 each of which encodes a particular protein. Very roughly, one can think of)Tj 0 -13.2 Td(a gene as encoding a)Tj /F6 11 Tf ( trait)Tj /F4 11 Tf (, such as eye color. The different possible "settings" for a trait \(e.g., blue, brown,)Tj 0 -13.2 Td(hazel\) are called)Tj /F6 11 Tf ( alleles)Tj /F4 11 Tf (. Each gene is located at a particular)Tj /F6 11 Tf ( locus)Tj /F4 11 Tf ( \(position\) on the chromosome.)Tj 0 -26.4 Td(Many organisms have multiple chromosomes in each cell. The complete collection of genetic material \(all)Tj 0 -13.2 Td(chromosomes taken together\) is called the organism's)Tj /F6 11 Tf ( genome)Tj /F4 11 Tf (. The term)Tj /F6 11 Tf ( genotype)Tj /F4 11 Tf ( refers to the particular set)Tj 0 -13.2 Td(of genes contained in a genome. Two individuals that have identical)Tj ( genomes are said to have the same)Tj 0 -13.2 Td(genotype. The genotype gives rise, under fetal and later development, to the organism's)Tj /F6 11 Tf ( phenotype)Tj /F4 11 Tf (\227its)Tj 0 -13.2 Td(physical and mental characteristics, such as eye color, height, brain size, and intelligence.)Tj 0 -26.4 Td(Organisms whose chromosomes are arrayed in pairs are called)Tj /F6 11 Tf ( diploid)Tj /F4 11 Tf (; organisms whose chromosomes are)Tj 0 -13.2 Td(unpaired are called)Tj /F6 11 Tf ( haploid)Tj /F4 11 Tf (. In nature, most sexually reproducing species are diploid, including human beings,)Tj 0 -13.2 Td(who each have 23 pairs of chromosomes in each somatic \(non-germ\) cell in the body. During sexual)Tj 0 -13.2 Td(reproduction,)Tj /F6 11 Tf ( recombination)Tj /F4 11 Tf ( \(or)Tj /F6 11 Tf ( crossover)Tj /F4 11 Tf (\) occurs: in each parent, genes are exchanged between each pair of)Tj 0 -13.2 Td(chromosomes to form a)Tj /F6 11 Tf ( gamete)Tj /F4 11 Tf ( \(a single chromosome\), and then gametes from the two parents pair up to)Tj 0 -13.2 Td(create a full set of diploid chromosomes. In haploid sexual reproduction, genes are exchanged between the)Tj 0 -13.2 Td(two parents' single-strand chromosomes. Offspring are subject to)Tj /F6 11 Tf ( mutation)Tj /F4 11 Tf (, in which single nucleotides)Tj 0 -13.2 Td(\(elementary bits of DNA\) are changed from parent to offspring, the changes often resulting from copying)Tj 0 -13.2 Td(errors. The)Tj /F6 11 Tf ( fitness)Tj /F4 11 Tf ( of an organism is typically defined as the probability that the organism will live to)Tj 0 -13.2 Td(reproduce \()Tj /F6 11 Tf (viability)Tj /F4 11 Tf (\) or as a function of the number of offspring the organism has \()Tj /F6 11 Tf (fertility)Tj /F4 11 Tf (\).)Tj 0 -26.4 Td(In genetic algorithms, the term)Tj /F6 11 Tf ( chromosome)Tj /F4 11 Tf ( typically refers to a candidate solution to a problem, often)Tj 0 -13.2 Td(encoded as a bit string. The "genes" are either single bits or short blocks of adjacent bits that encode a)Tj 0 -13.2 Td(particular element of the candidate solution \(e.g., in the context of multiparameter function optimization the)Tj 0 -13.2 Td(bits encoding a particular parameter might be considered to be a gene\). An allele in a bit string is either 0 or 1;)Tj 0 -13.2 Td(for larger alphabets more alleles are possible at each locus. Crossover typically consists of exchanging genetic)Tj 0 -13.2 Td(material between two singlechromosome haploid parents. Mutation consists of flipping the bit at a randomly)Tj 0 -13.2 Td(chosen locus \(or, for larger alphabets, replacing a the symbol at a randomly chosen locus with a randomly)Tj 0 -13.2 Td(chosen new symbol\).)Tj 0 -26.4 Td(Most applications of genetic algorithms employ haploid individuals, particularly, single-chromosome)Tj 0 -13.2 Td(individuals. The genotype of an individual in a GA using bit strings is simply the configuration of bits in that)Tj 0 -13.2 Td(individual's chromosome. Often there is no notion of "phenotype" in the context of GAs, although more)Tj 0 -13.2 Td(recently many workers have experimented with GAs in which there is both a genotypic level and a phenotypic)Tj 0 -13.2 Td(level \(e.g., the bit-string encoding of a neural network and the neural network itself\).)Tj /F8 11 Tf 135.601 659.208 Td(Chapter 1: Genetic Algorithms: An Overview)Tj 104.841 -720 Td(5)Tj ET Q endstream endobj 37 0 obj << /Resources << /Font << /F6 28 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text] /XObject << >> >> /Type /Page /Parent 1 0 R /Contents 38 0 R /MediaBox [0 0 595 792] >> endobj 41 0 obj << /Subtype /Image /Type /XObject /Width 215 /Height 157 /Length 33755 /BitsPerComponent 8 /Interpolate true /ColorSpace [/Indexed /DeviceRGB 241 <0000000505050a0a0a0b0b0b0c0c0c0d0d0d1010101111111313131515151818181919191a1a1a1b1b1b1c1c1c1d1d1d1e1e1e1f1f1f2020202121212222222323232424242525252626262727272828282929292a2a2a2b2b2b2c2c2c2d2d2d2e2e2e2f2f2f3030303131313232323333333434343535353636363737373838383939393a3a3a3b3b3b3c3c3c3d3d3d3e3e3e3f3f3f4040404141414242424343434444444545454646464747474848484949494a4a4a4b4b4b4c4c4c4d4d4d4e4e4e4f4f4f5050505151515252525353535454545555555656565757575858585959595a5a5a5b5b5b5c5c5c5d5d5d5e5e5e5f5f5f6060606161616262626363636464646565656666666767676868686969696a6a6a6b6b6b6c6c6c6d6d6d6e6e6e6f6f6f7070707171717272727373737474747575757676767777777878787979797a7a7a7b7b7b7c7c7c7d7d7d7e7e7e7f7f7f8080808181818282828383838484848585858686868787878888888989898a8a8a8b8b8b8c8c8c8d8d8d8e8e8e8f8f8f9090909191919292929393939494949595959696969797979898989999999a9a9a9b9b9b9c9c9c9d9d9d9e9e9e9f9f9fa0a0a0a1a1a1a2a2a2a3a3a3a4a4a4a5a5a5a6a6a6a7a7a7a8a8a8a9a9a9aaaaaaabababacacacadadadaeaeaeafafafb0b0b0b1b1b1b2b2b2b3b3b3b4b4b4b5b5b5b6b6b6b7b7b7b8b8b8b9b9b9babababbbbbbbcbcbcbdbdbdbebebebfbfbfc0c0c0c1c1c1c2c2c2c3c3c3c4c4c4c5c5c5c6c6c6c7c7c7c8c8c8c9c9c9cacacacbcbcbcccccccdcdcdcecececfcfcfd0d0d0d1d1d1d2d2d2d3d3d3d4d4d4d5d5d5d6d6d6d7d7d7d8d8d8d9d9d9dadadadbdbdbdcdcdcdddddddedededfdfdfe0e0e0e1e1e1e2e2e2e3e3e3e4e4e4e5e5e5e6e6e6e7e7e7e8e8e8e9e9e9eaeaeaebebebecececedededeeeeeeefefeff0f0f0f1f1f1f2f2f2f3f3f3f4f4f4f5f5f5f6f6f6f7f7f7f8f8f8f9f9f9fafafafbfbfbfcfcfcfdfdfdfefefeffffff>] >> stream >+1+0.111111113210HFu0Oid8?0pfTl۾|eH81ҵ_?*#$@f^I2γhJ132;Qp^J0̬pG3&*7P|.ھϺoB+'%1Hy1m,E`UּmN;32;Ol|+,^k\7uԳcI6%)9Wz.oLg}(صQA&-QtHR0ȕнн{W;./;Ho!/bA-(6Hf1/Ǭa@%(BZuo12˯fG.)-9Z|,Ho@sҷhH5+,1QvJS)fYy0iճmQ8'%0P{ ,7[^gT~EJ*м$g)*z8T,m&N>+!W:*IiHTa&#h~a)'cpa\"w&w*\Ϛt&+)q+XJ-]-@K.Ɛ껖8rK4.j[yF{)])+ccfw"z+@npKJS ++.t+5!i)*a'APNK7R%ajZI@-mYbfC.wR/.񺈼|m+c&,~,CX**ēҪ"(bH}~vD[9E)F1* ~b'&_4t!-#vL>~-   % " !#&)###"""!!$%&%$%),1.+*,...83&"tt; !@9/:885//2-1-,-//.,)'+)'&''''%%&'(())'''&&&%%''''&&%$&&&&&'''""##$$%%$#$#"" # #!" !!" A|)eS/6"2-'--+-/-,.(,3/**-//.-,.13.//-,+,-/000.,**-,,.//-+,./../.,//../.-,,++,21!+),&%+'*+,/-((,,+(*()+(("+,(,2/*.++-.31%93^d003$).,,-,-.),1.*+,-,,,++,....-+++,..//-,*).+)()+---.-+*+,*-,,,,,*),-*(,#+,*'&')'((,-)')),(($$'$&.''*)')++%#1./v8G')2)21!(0%0.++,--+-/-+,,*)+-,**,...,+++,-----,**,,++,---,--+*++*0///0/.-++*+#(*.'((%+'('*-)&)+,'&"!$#&&)('++((.+)$+[U/C"1-/3,. !&)&1.++,.--.-++,,)(*./-,...--,,,,--,,-,+*,----,,,(+--./.+-,,,-,+*)'-3(**+'()(,*-)*-*(,0,''##&&*+&$))#'51+!E9;Hb&Q*0011///$#+0,+--.-/.,++,-+*+./--...------/-,,--,,/-+('(*,'*,-./.,**)***)(*%2-0(-)*(),*-.)*.+)-1+()%%('*))++*-.*!,yvYzW r#/275.-0//+,"$/*&(//+,.--./.++++-++++,,+)-,,,-...0.,,---,/.,+*****++**,,+..-.//.-,)1()(1),()-'+*'*.+)+,+(*'%&$'*,&'1+%.`bHB2 $1++-,*/1+++/1.+,2,.,+--,-./-,,**-*,,++,*&+**+,...0-+*,-,+.-./0/,*,-,*)++*-,,-..-,+0%-&+0+))))()('*,**+)*)+(&'$')(,1$NOWsD|L 72/-,,01+)/)2+*,+0-+,++.-+-./-,-*).),-+,/-')((),-.-0-*)+,+*.,**,--,,./---,*+++,,-,+)4,++,-+$)*&+(*)++(*,+*),)()'*)(-!*~_X!mf0-'+,'+-).+,+-..-,,-.---,,,++-.,,-*(,,+)*,-,*-/+,-.0,**+,,+**+,-,***+./0.,*))*'*-))*(.#.&+*/)'('')(*().($+(+'',,)+)0 "^-T߈. ..*/0/(+-(-*+*-..-,,-/-,++*++,*+*,-+),*)()+,+*+-))**-*)+,,,,+)+,,+***+)**)(()*+**-.+**')+(+)0*)*))+*)-**,+-))(%%,+%(G@>?140'*+'.(+-'+(**,-.-,+-/-,**)*+,&'()+*())''(*+*)),))((,*),-,,-,),,++**+,)))(()+-*-,+--+-#-'*,)-(&((()()0,,1-,/-)(#'($-yW)[*.))+,.1,'(+-'+(+,*,--+*,.,++**++,())+,*((*)))++*)+-++*(,,)-.**.-),++***,-,+*)()*,(,.*(-.(',')-)-(%'('&&(**--&'0+&()&!Te%}&+0/')*+)&+/&(+-',*-.(*++*)+,+,,--,,+*+-.--,+,,,,,,+*+-+,+)-,*--))--*++***+,-+*))((((**-*&.+((++).)0+((*)''+(,.**--4('?s ݕ'$0'&*+*+).1-+('+-(,*.0()*****+*+--.-,+&(+,*,-+,,---,+*)+),,),++-,)),-++*)*+,--++*++,+*-()++-" &4*+.)-)0+''*)&&-)-*'12*&"3{C(--0.(+*#.,*+**(&+.(+),.)))*+,+**+,,-,,+%'++'),*)*+,,,++()',-*+**++**++**))*,--,-,,,-.--,*(,/%-2,,,)+(.*$%))&')%)''+,0%`a20/+&)-*'),(())+#&+.'+(+,*))+--,+***+++,,*,0.)*-,&()+++++()(./,-+))*++*))*))*,--,-+**+++*(,(,/'-(,+')*(/+%&,,)+,(-21'*Cx%.6*..-++-,)-.,)(*+),**+*)+.-,+***+++,,++,+(.-+**+,,+*)(()*+-+,//-+*-*#-$,').**--**.+,.,)./*,,)-",,-,--)'+2-'',*'(-&-3 ./]= (7*)3./-++,+),,+(()*).-,,+)*,++***+,-*,,+,-,*++++++++,+*))***,+,./,++.,&/&.)*+)(++)*-+,-+),.)-+1(),,.---+),1&(.)')'+/$)b2KN$21+./&..-+*,+),-,))*+).---,))+++***+,-)+,,,--+))++++*),,+++***,+,.-,+-.+'/'-))))))*++,+-.+),-)-+1 #-/+.-+,+**-0-&'-.*""MF>j-1**2-'0---**,,*./.,+--+,++-,*)+-,+***++),-,,--+')*++****++,++++++,-,+,..,*/)-*)*,,**,-,+./-,-,)(2).+-),,*)**)/(+1.)%3T-ۆ%00/00,((+-+,,**,-,-..,+--++**,+)()-,+***+++-.,+,,+()**))*+')+++*++++,-,+,..--0+.,*+--*),,*),.-,+)((4)2+)*,-+)+,+-+$(*2hk%;*4*-.+-+'+.&*,,**,-,+,,**++),*)++(&'++***+,-+..+**,,)*+*))*,')++**+,,++,,++-*)*+(*+'*,+(())(&*,+*('(1# 1+*,,-.-+-.-+31%(TzK3/-6/&./+))))+--*)*++)++))**),*)*+)'(++***+,-+--*(*,-*,,+*)+,)+-,*)*,-++,-++,'')('(*'*+*)()))'++))('+/.3(*0-+,-++..8'As./)-.+-/0/--,*),..+)****,,**++*+)(*++**-,+***++*,,)'*-.+,.-+)+,,-.-*)*+-+*,-+****-+*,/+++****+++-,**)*/ $.-0.++'),)(,-&3xڏ-%00/-,-.,+,--+**++,+)*,.-+++*))*++.-)(+-,,---,,,+,+,--,-0+,..+()--+),0.+------,,,+,++,..,/-..++,*-+'+)'.*(//,0,,+.-*++#`yB"7,-..,,.//,---+***,--**+,++,,+**+,***)))+.,,+***++**,.-++-*+-.,)+.,,+,/.+,****++++,-,+,/.,-,-.,,-+.0(//,1*-+-/1-./-30$L#pX52&,-//-,---,,--,+++,..+**+*,,,,++,--*)++)+/-,+*)*+,*+-//,+,,,-.-++-+.-+--+,++,,,,---..,-//-,+-.,-.,..*.0.(.1..01-/3.$:3Tx22,1..,./-++,+*,--,,,,+..,****+,,,++,.1.---+,/..-,,,--+,.0/.--0../.+*+*/.+,,++....----.//-.0/-,+-.,-.+.)-,/+/+-34014/'*c@A)+'/*%**-(+-,,--,,---,++++--+*+++*+++*+,-00/,,./.------,,*,----..0../.+***//+,+*+----,,,,///-.0/--+-.,,-+.*../!')-+*580.-N67A'7,,11/10/*,---.-+.//.,***+,,*+,-+++++**+,,.,)*/0.,,,,,+++)++**+--.,,..,,-+..,,+)+++,-.//0./.-.0/-.,-.+,-++.*/(/(32.3("9.a^x_$00245/---//.///01.*-./.,+**-,+)+--*,,,,++,-,,**,/00-,,++++++--+*+,,-,,..,,-+-,,-+),++,-/012---,-//-.+,-+,.-+.+.+-)/5-!.p8eRE84*!#$%(2@KP''(%&1+-1/21-./0342-+,---,--.-*)+--*-.--,+,-1-+-/./1/.-,,,-..00.,--,---.-+*,,,+,.+),))*+,--.,-,,-//--++,*-0/0-4.7+/)*)Pgɰ8"$%&&,---,.320-,/22.,-/1/++-,--.//01'+...00/,,,,,,,,++..))--+++,--+*+/+)..-31,-/-+./*/00.,03,/7240/#:\,-/00-+**)**'#"()&(*.11025.//0////.121/.,*...---,,.,-.-/1/,,--..-,.0-,21-/0.//-031-(,.(*0,/1"%30&-|b21-/11/-,,+.11/.-.-/11.+))((&#!"$&'(.01//0001222333332220010-,,-.//.*,*+21++010,+/0-)*23++00.)!9)3[ڃ0080),.00.,,,/01/+*+,-..//...10.-.//010.,-/-*####! "%'*+*.11..2643212221.10030,-010..11/+12-0/.72"%*J/(71(.-.011/.././//..1431024531.,+,.0114420/0-*.//.--../.../.-,+(%"#')**.000/0431135312142.65*/&;58997556899999876/036765441122340011001/,+--++,,*,*)*,..-,++..+('))*****+,-,,0/*)-+)'&$"! !!  "q¿z{Y1V^UAb:Dش}G2IAqf endstream endobj 42 0 obj << /Length 4338 >> stream q 1 0 0 1 72 36 cm 0.00 0.00 0.00 RG 220.1 231.4 m 249.1 231.4 l S 249.1 231.4 m 265.6 231.4 l S q 154.0 0 0 112.4 0.0 38.6 cm /I11 Do Q BT /F9 15.8 Tf 0 682.16 Td 0.000 Tc(1.4 SEARCH SPACES AND FITNESS LANDSCAPES)Tj /F4 11 Tf 0 -27.368 Td(The idea of searching among a collection of candidate solutions for a desired solution is so common in)Tj 0 -13.2 Td(computer science that it has been given its own name: searching in a "search space." Here the term "search)Tj 0 -13.2 Td(space" refers to some collection of candidate solutions to a problem and some)Tj ( notion of "distance" between)Tj 0 -13.2 Td(candidate solutions. For an example, let us take one of the most important problems in computational)Tj 0 -13.2 Td(bioengineering: the aforementioned problem of computational protein design. Suppose you want use a)Tj 0 -13.2 Td(computer to search for a protein\227a sequence of amino acids\227that folds up to a particular three-dimensional)Tj 0 -13.2 Td(shape so it can be used, say, to fight a specific virus. The search space is the collection of all possible protein)Tj 0 -13.2 Td(sequences\227an infinite set of possibilities. To constrain it, let us restrict the search to all possible sequences of)Tj 0 -13.2 Td(length 100 or less\227still a huge search space, since there are 20 possible amino acids at each position in the)Tj 0 -13.2 Td(sequence. \(How many possible sequences are there?\) If we represent the 20 amino acids by letters of the)Tj 0 -13.2 Td(alphabet, candidate solutions will look like this:)Tj 0 -26.4 Td(A G G M C G B L\205.)Tj 0 -26.4 Td(We will define the distance between two sequences as the number of positions in which the letters at)Tj 0 -13.2 Td(corresponding positions differ. For example, the distance between A G G M C G B L and MG G M C G B L)Tj 0 -13.2 Td(is 1, and the distance between A G G M C G B L and L B M P A F G A is 8. An algorithm for searching this)Tj 0 -13.2 Td(space is a method for choosing which candidate solutions to test at each stage of the search. In most cases the)Tj 0 -13.2 Td(next candidate solution\(s\) to be tested will depend on the results of testing previous sequences; most useful)Tj 0 -13.2 Td(algorithms assume that there will be some correlation between the quality of "neighboring" candidate)Tj 0 -13.2 Td(solutions\227those close in the space. Genetic algorithms assume that high-quality "parent" candidate solutions)Tj 0 -13.2 Td(from different regions in the space can be combined via crossover to, on occasion, produce high-quality)Tj 0 -13.2 Td("offspring" candidate solutions.)Tj 0 -26.4 Td(Another important concept is that of "fitness landscape." Originally defined by the biologist Sewell Wright)Tj 0 -13.2 Td(\(1931\) in the context of population genetics, a fitness landscape is a representation of the space of all possible)Tj 0 -13.2 Td(genotypes along with their fitnesses.)Tj 0 -26.4 Td(Suppose, for the sake of simplicity, that each genotype is a bit string of length)Tj /F6 11 Tf ( l)Tj /F4 11 Tf (, and that the distance between)Tj 0 -13.2 Td(two genotypes is their "Hamming distance"\227the number of locations at which corresponding bits differ. Also)Tj 0 -13.2 Td(suppose that each genotype can be assigned a real-valued fitness. A fitness landscape can be pictured as an \()Tj /F6 11 Tf (l)Tj /F4 11 Tf 0 -13.2 Td(+ 1\)-dimensional plot in which each genotype is a point in)Tj /F6 11 Tf ( l)Tj /F4 11 Tf ( dimensions and its fitness is plotted along the \()Tj /F6 11 Tf (l)Tj /F4 11 Tf ( +)Tj 0 -13.2 Td(1\)st axis. A simple landscape for)Tj /F6 11 Tf ( l)Tj /F4 11 Tf ( = 2 is shown in figure 1.1. Such plots are called landscapes because the plot)Tj 0 -13.2 Td(of fitness values can form "hills," "peaks," "valleys," and other features analogous to those of physical)Tj 0 -13.2 Td(landscapes. Under Wright's formulation, evolution causes populations to move along landscapes in particular)Tj 0 -13.2 Td(ways, and "adaptation" can be seen as the movement toward local peaks. \(A "local peak," or "local optimum,")Tj 0 -13.2 Td(is not necessarily the highest point in the landscape, but any small)Tj 0 -152.04 Td(Figure 1.1: A simple fitness landscape for l = 2. Here f\(00\) = 0.7, f\(01\) = 1.0, f\(10\) = 0.1, and f\(11\) = 0.0.)Tj /F8 11 Tf 135.601 692.448 Td(Chapter 1: Genetic Algorithms: An Overview)Tj 104.841 -720 Td(6)Tj ET Q endstream endobj 40 0 obj << /Resources << /Font << /F6 28 0 R /F4 13 0 R /F9 14 0 R /F8 15 0 R >> /ProcSet [/PDF /Text /ImageB /ImageC /ImageI] /XObject << /I11 41 0 R >> >> /Type /Page /Parent 1 0 R /Contents 42 0 R /MediaBox [0 0 595 792] >> endobj 1 0 obj << /Kids [3 0 R 10 0 R 18 0 R 21 0 R 24 0 R 27 0 R 31 0 R 34 0 R 37 0 R 40 0 R] /Type /Pages /Count 10 >> endobj 43 0 obj << /Type /Catalog /Pages 1 0 R >> endobj 44 0 obj << /ModDate (D:20170703184312+02'00') /CreationDate (D:20170703184312+02'00') /Creator (pdftk 2.01 - www.pdftk.com) /Producer (itext-paulo-155 \(itextpdf.sf.net-lowagie.com\)) >> endobj xref 0 45 0000000000 65535 f 0000116832 00000 n 0000000000 65535 f 0000025691 00000 n 0000000015 00000 n 0000024062 00000 n 0000024178 00000 n 0000025504 00000 n 0000025604 00000 n 0000000000 65535 f 0000028859 00000 n 0000027663 00000 n 0000025872 00000 n 0000027754 00000 n 0000027846 00000 n 0000027941 00000 n 0000028031 00000 n 0000000000 65535 f 0000039345 00000 n 0000029086 00000 n 0000000000 65535 f 0000049804 00000 n 0000039549 00000 n 0000000000 65535 f 0000054960 00000 n 0000050008 00000 n 0000000000 65535 f 0000059698 00000 n 0000055164 00000 n 0000055257 00000 n 0000000000 65535 f 0000065123 00000 n 0000059902 00000 n 0000000000 65535 f 0000071137 00000 n 0000065316 00000 n 0000000000 65535 f 0000076597 00000 n 0000071341 00000 n 0000000000 65535 f 0000116592 00000 n 0000076801 00000 n 0000112198 00000 n 0000116955 00000 n 0000117007 00000 n trailer << /Info 44 0 R /ID [<68073173fceb3c294d302187639f4557>] /Root 43 0 R /Size 45 >> startxref 117203 %%EOF