Luận án Phát triển một số mô hình phân tích dữ liệu ảnh và ứng dụng

Chl1Ohg 1 TIEP CAN MAY ROC. . TRaNG PRAN TICR DU' LIEU. P hall tlchdir li~ugiupchocacnhanghienCUllphantlchvaly giaicac k~tquanghienCUllthvc nghi~m;trenca s&do giupdinhhuangnghien CUllvadv tlnh- dVbaacacva:nd~khoahQcmQtcachdungdilnvahqply nha:t. ChuangnaytdnhbaymQts5cachti~pc~ncuamayhQctrongphantlch dir li~unhum<;1ngo-ran,logicmavathu~tgiaidi truy~n.Quanghien CUllcacmahlnhdo, chungtai d~xua:tmQtmahlnhphant{chdir li~u NNGA. Ma hlnhd~xua:tla mQtsv k~thqpgiirathu~tgiaidi truy~nva m<;1ngo-ran.Thvc nghi~mchungto r~ngmahlnhd~xua:tcoth~duqc dungra:thi~uquakhixaydvngcacmahlnhdv baatir t~pthvc nghi~m. NQidungch{nhcuachU'angtdnhbay: (1.1)Xay dvngmahlnhchodirli~u:MQtbaitoanngU'qc. (1.2)M<;1ngIan truy~ngiai bai toanngU'qc. (1.3)Xa:pxi ma. (1.4)Thu~tgiaidi truy~ngiaibaitoanxacdinhthallis5. (1.5)NNGA - mQtm<;1ngIantruy~nvai thu~tgiaihQcdi truy~n. 6 1.1 Xay dl,tngma hlnh cho dit li~u: MQt bai toaD ngl1Q'c Phantichdif 1i~unh~mmvcdichxacdinhm<)tmahlnhtoanhQcphil hQ'pvai t~pdif 1i~uth\l'cnghi~m- t~pm~u.Vi~cxacdinhdU'Q'cmahlnh nhU'th~1am<)tbaitoanquailtrQngvac~nthi~trongnhieu1anhV\l'Ckhoa hQcclingnhU'cangngh~.N~um<)tmahlnhdU'Q'cxayd\l'ngphilhQ'pt6t vai t~pm~u;thl khangnhifngno giupcacnhanghienCUllco m<)tdinh hU'angt6t chonghienCUll;macongiupxacdinhcacd\l'tlnh- d\l'baave cacv~ndekhoahQcm<)tcachdungdiinvahQ'p1ynh~t. Th\l'Cch~t,vi~cxacdinhdU'Q'cm<)tmahlnhtoanhQcphilhQ'pvai t~p m~uchotrU'ac1am<)tbaitoanngU'Q'c.Theodo,phantlchdif 1i~ucoth~ dU'Q'cdinhnghianhU'sail: Phan t{chdii lifu la m(jtph'liO'ngphaptoan h9C)tren cO'sa tiJp cac dii lifU quansat a'liQ'c)xay dvng mo hinh bilu diln moi quanhf nhan quagiiia cacbitn ph?!thu(jcveLD cacbitn a(jcliJp. M<)tcachhlnhthuc,baitoancoth~dU'Q'cmata nhU'sail: Bai toaD cd ban. Cho t~pm~u: n ={(Xi,1i) saDchoXi E IRn;1i E IRm;i =1,N} Vai mQiE dU'O'ngcho trU'ac,tlm ma hlnh G : IRn ---7 IRmsaGcho Vi=1,N , taco IIG(Xi)- 1i11< E 7 Co nhi~uphU'O'ngphap co th~dU'Q'cS11dvng d~giai bai toan cO'ban tren. M(>ttrong nhli'ngphU'O'ngphap truy~nthongdU'Q'cac nha nghien cuu S11dvng la phU'O'ngphap hbi qui tuy~ntlnh. Rbi qui tuy~nt{nhra:t phu hQ'pcho cac t~pm~uma trong do, cac bi~nphv thu(>cva cac bi~n ... dtquailh~nhanquatuy~ntlnh. Trongtnl'C!nghQ'pmaquail h~do khBngtuy~nt{nh,t~pm~uphaidU'Q'ctuy~nt{nhboab~ngm(>ts6 phepbi~nd6i;vamBhlnhxaydvngdU'Q'cla mBhlnhxacdinhtrencac bi~n'd<:tid ~n'chocacbi~ntrongt~pm~u[42].Di~ukhokhanch{nhla chU'acom(>tnghiencuud~yduhU'angd~ncachthucchQncacphepbi~n d6id~tuy~ntlnhboam(>tt~pm~ukhBngtuy~ntlnh. Cacnhaphantkh phaith11(thucBng)m<)ts6phepbi~nd6ichod~nkhi d<:ttdU'Q'cmBhlnh phuhQ'pvai t~pm~u.Ra:tcoth~,cacnhaphantlchkhBngth~kiennh~n chod~nkhi dU'Q'cmBhlnhthkh hQ'p! M<)thU'angti~pc~nkhaccuatri tu~nhant<:t°d~giaibaitoancO'ban trenla hU'angti~pc~ndungcBngngh~mayhQctrongphantkh dli'li~u. CacphU'O'ngphapnaychophepxaydvngmBhlnhtoanhQctir t~pm~u dccuacacbi~nphvthu<)cvaobi~nd<)cl~pla tuy~n HnhhaykhBngtuy~ntlnh.Theocaccachti~pc~nnay,lC!igiai(mBhlnh) dU'Q'chlnhthanhtrongti~ntdnh hQc. Hi~nba phU'O'ngphapsail la cacphU'O'ngphapling dvngthanhcBng cachti~pc~nmayhQctrongphantlchdli'li~u: . MtphU'O'ngphapdU'Q'cphat tri~ntir nhli'ngnam 80va ap dvng ra:tthanhcBngtrong nhi~ubai toan. . Xa:pxi mC!.M(>tcachti~pc~ncuacBngngh~mC!vamayhQctrongxa:p Xl hamlien tvc. . Thu~tgiaidi truy~n.M<)tcachti~pc~nmBphongdi truy~ntv nhien ra:tthanhcBngtrongcacbaitoantlmki~m. 8 1.2M<;tngIan truy~nva bai toan ngU'9'c 1.2.1M6 hlnh ffi<;tngIan truy~n tong quat a- ~ a 1('£i=1aiWij - 8j) an - Hlnh 1.1:Nd-ron j cualap thu k :2'2vai ngl1Cing(}j. Gia trj cuanut j dl1qcxacdjnh tu cacgia trj ai, i = r;n cua cacnd-ronthuQClap thu k - 1va cac tr.;>ngWij cua caccling tl1dngung. f la hamtruy~n. M<;1ngIantruy~nt6ngquat,ky hi~uNN, la dbthtcotrQnggbmK 16p tachbi~t.M8i nutj, dU'Q'cgQila mQtnO'-ron,thuQc16pthuk,2 <k<K, comQtngU'&ng8j E JR va dU'Q'clien k~ttn,rcti~pv6i mQinut i thuQc16p thu (k - 1);vam8icling(ij) naydU'Q'cg~nmQtgiatrt trQngs6WijE JR. Hlnh1.1minhho2. Khi thi hanh,dii'li~u,la mQtvec-tO'n chi~uX = (Xl?...,Xi, ...,Xn)E JRn, dU'Q'cnh~ptn,rcti~pvao16pthu nh:1t(l6pnh~p),khi :1y,giatrt cuanO'-ron i thuQc16pnh~psenh~ngia trt Xi, vaxU:1tra (j 16pK (l6pxu:1t).Gia trt cuanO'-ronthu j thuQc16pk >2dU'Q'cxacdtnhtheocongthuc sail: Yj =1j(8j) (1.1) nk-l 5j =~aiwij +8j z (1.2) trongdo, - ai la giatrt cuanO'-roni thuQc16p(k - 1). - Wijla giatIt trQngs6cuacling(ij). - 8j la giatrt ngU'&ngcuanO'-ronj. - nk-l la s6nO'-rontrong16p(k - 1). - Va 1j la hamtruy~ncuanut j. Hamtruy~nla hamcodtnhnghianhU'sail: 9 Dinh nghia1.1:Hamtruy~nJ laanhx~J : IR --7 IR thoa: (1) J lahamlientVc. (2) J la hambi ch~n: Vx E 1R,3M E IR : If(x)1<M. (1.3) (3) J la hamdO'ndi~utang: Vx,yE lR,x <Y=} J(x) < J(y). (1.4) MQihamthoadinhnghia1.1d~ucoth~dU'Q'cchQnlamhamtruy~ncho m~ngIantruy~n.Tuy nhien,trongth\l'ct~caid~t,cacham8authU'Cing dU'Q'C811dvng ph6 bi~n[1]: (1)Hamlogistic: 1 J(x) =g(x)=-1+e-X chogiatri thuQc]0,1]la hamthU'CingdU'Q'cdungdotlnhdO'ngiancuad~o hambacnhat: (1.5) g'(x)=g(x)(1- g(x)). (1.6) (2)Hamtanh: eX- e-X J(x) - tanh(x) =( 2ex +e-x) clingthU'CingdU'Q'c811dvngkhi c~ngia tri thuQc]- 1,1[. Va d~ohamb~c nhatcod~ng: (1.7) 4 (tanh(x))'=(sech(x))2=(ex+e-x)2' (1.8) (3)Hamsgn: { 1, x >0 sgn(x)= 0, x<O (1.9) dU'Q'C811dvngkhi c~ngiatri chocacnO'-rontronglapxuat (lapK) cua m~ngIantruy~ngiatri nhiphan. 10 Nhu v~y,m;;tngIan truy~nco th~dugcxemnhu m(>tanhX;;tNN : IRn -7 IRm.Va m;;tngN N coth~dugcdungxaydvngcacmohlnhcho- dif li~utIeDcosadinhly sau: Dinh If 1.1 (Dinh If Hornik-White [16]): M(>tm;;tngIan truy~nNN : IRn -7 IRmv6iso16p~nthlchhgp,coth~ xa:pXl d~um(>thamlient\lCba:tky f : D c IRn -7 IRmtIeDm(>tmi~n com-p~cD. M(>tva:nd~d~tra la lamthenaoxacdinhgiatri cactrQngsoWi,jcho caccling(ij) vacacngu&ngBj cuaDO-Ionj. D~tWOj=Bjvaao=1,congthuc(1.2)dugcvietl;;ti: nk-l S. =L aiWijJ . 02= (1.10) thl baitOaDcuata tra thanhbaitoaDxacdinhcacgiatri Wij tuongung. Ta gQichungla xacdinhcacgiatri trQngsochom(>tca:utrucm9>ngcho tru6c. 1.2.2Qui tcdelta Hi~nconhi~uphuongphapchophepxacdinhtrQngsochom(>tm;;tng Iantruy~n.Parker(1985)[28],thu(>ctruCJngd;;tihQcCambridge,d~xua:t thu~tgiaihQccotenlearning-logic.Le CUD(1985)[39],m(>ttacgianguCJi Phap,clingd~xua:tm(>tsodbhQctuongtV. NhomnghienCUllxUl1phan b6/songsongcuatruCJngd;;tihQcCaliforniadu6isvlanhd;;tocuaDavidE. RumelhartvaJamesL. McClelland(1986)[31],[32]d~xua:thu~tgiaihQc tantruytn nguQ'cltJi. Nhln chungcacphuongphapnayd~uxaydvng tIeDcosaphuongphapgradientgiam,m(>tphuongphapd;;tngleaa6iv6i thongtin trg giupla d;;tohamb~cnha:t.VI the,cacqui t~cdo dugcgQi chungla quitdc delta.Quit~cdeltacoth~dugctrlnhbaynhusail: Chot~pm~un ={(Xi,}i);Xi E IRn;}iE IRm;i= 1,N} D~t m Ep =2;(Ypj - NN(Xp)j)2 j=l 1a16icuam~ngNN sov<1im~u(Xp,Yp)E D. Va, (1.11) N E = L Ep p=l (1.12) 1at6ng16icuam~ngN N. Mv.cd{Chcuata 1axac dinh cactrQngs6w saochodi~uki~n: E <EO, (1.13) duQ'cthoa;V<1iEO1amQth~ngdU'O'ngba:tky chotrU'<1c. Va qui t~cdeltadU'Q'ctom t~tnhU'sau. Qui tdehgedeltala quitdelq.pr1ieuehinhcaetr9ngs6/w ehor1tnkhi dieuki~n(1.13)duQ'ethod.Tr;tim6i budelq.p,th1/ehi~n: (1) Vdi m6i mau(Xp,Yp),xaer1inhZp=N N(Xp) theocaee6ngthue (1.1)-(1.2)va l6i Ep theo(1.11). (2) T{nhtdngl6i E theoe6ngthue(1.12). (3) Sau m6i bude lq.p,tung tr9ngs6/w r1uQ'eg,pnhg,tnhu sau: w(t)t- w(t- 1)+C(t); (1.14) trongdo, C(t)=-ED(t); E E (0,1]; N ( 8E ) D(t)=L p=l 8w(t) p (1.15) (1.16) E trong c6ngthuc (1.15)dU'Q'cgQi1ah~s6 hQc. T6c dQ hQi tv. cua thu~1tgiai phv.thuQcnhi~uvao gia tri E dU'Q'chQn. N~uE dU'Q'chQn 12 kh6ngthichhQ'pseanhhl10'ngd~ntocdQhQitv cuathu~tgiai. Ta hlnh dungm~tl8inhl1lamQthamE+w),thl hlnh1.2minhhoq.quatdnhgiam l8i khi cacE quabe ho~cqual6n. D~chQnmQtgia tri thichhQ'pnha:t choE,cacphantlchvienthl1CJngsuphl1O'ngphapthu-va-saib~ngcachcho mq.nghQcnhieul~nv6icach~sohQckhacnhauvachQnh~sohQctotnha:t. c. c. a w w Hlnh 1.2: Gia tri cuac:anh ht1dngMn t6c dhitlf CURthu{lttoan, (a) c:quanho, bi~nthien tr<;mgs6nho, m-nglau d-tMn c,!c ti~u ham 16i, (b) c:qua Ian, bi~nthien tritlf ciao dnglen xu6ng quanh C,!C ti~u ham 16;, Nam1988,RobertJacobsvacQngs1,1'cua6ngdexua:tqui uk caiti~n tirquit~cdeltavagQila quit~cdelta-baT-delta,congQila quit~chQcv6i h~sohQcthichnghi[18].Theoquit~cnay,m8itrQngsodl1Q'Cg~nv6imQt h~sohQcE(w) rieng.Trongquatdnh c~pnh~ttrQng,n~uh116ngiam l8iclingbellv6ih116nggiaml8i0'(cac)b116ctr116c,thl E tangthemmQt ll1Q'ngK > 0; ngl1Q'clq.i,n~uhaih116ngnaykhacben,E sedl1Q'Cnhanv6i ffiQth~so cpE (0,1]. Trong qui t~cdelta-bar-delta, h116ngdl1Q'Cxac dinh theo da:ucua D(t) theo c6ng thuc sau: g(t+1)=Bg(t)+(1- B)D(t); (1.17) 13 BE (0,1]. Va h~so hQedU',exa dinh nhU'sail: c(t)= { c(t - 1)+~ n~u D (t)g(t) >0 c(t- 1)x cp n~u D(t)g(t) <O. LU'u'1ding, chi coqui t~ehQedelta121,cochungminh eh~tehetoan v~tlnhhQitv d~nqre ti~uevebQ[35].Khi e~pnh~tbQtrQng,m6i tI sodU',ee~pnh~ttheosaisodU',etlnh trentoanbQt~pmj,u. Qui t~e delta-bar-deltakh6ngthirahU'&ngchungminhnay. Tuy nhien,trongt t~eai dM, qui t~eh~so thich nghi hQitv rat nhanh hO'nso v6i qui deltava clingrat dangtin. M~tkhae,qui t~eh~so thiehnghigiupn! dungm<;1ngIan truy~nkh6ngphai boi roi khi phaj quy~tdinh ehQnh hQenaG. M~edu qui t~eh~so thiehnghi co phv thuQeVaGba tham (),cp,~nhU'ngno kh6ngnh<;1yearnnhi~uv6i caegia tri nay. ThU'c)'ngeh dU',eehQnnhU'sail [35]: (1 ~=0.1; cp=0.5; B=0.7. Va hi~nnay,thu~tngi1qui t~edeltacling dU',ehi~u121,qui t~ehi thiehnghi. MQt van d~rat quail trQngma h~uh~tcaenha nghienCUll1'1thl ffi<;1ngIan truy~ntranh d~e~ptf1!eti~p121,vand~v~s6'lop an va s6' trongm6i lop an. M~edu dinh 1'1Hornik-WhiteclingnhU'h~uh~tea thuy~txap xi ffi<;1ngO'-ronchungto r~ngmQtm<;1ngN N : IRn --7 v6isonut~nthichh,pcoth~xapxi d~ubatky hamlientve f : 1 IRn--7 IRmtren mQtmi~ncom-pacD, nhU'ngkh6ngco dinh1'1naGeb dU',ephaidungbaanhieunut ~nevth~.Sonut ~nthU'CingdU',eehQn thuQekinh nghi~mngU'CiiS11dvngm<;1ng.N~usonut ~nit, ffi<;1nghQitv eh~mva qre ti~uevebQd,ethU'Cingrat xa qrc ti~umongmuon; s6nut ~nnhi~u,eveti~uevebQthU'Cing~nv6i eveti~utoan evenh ffi<;1ngl<;1ikh6ngco kha nangt6ng quat boa eao;nghia la, m<;1ngthU' anhX,ehQc. 14 T6cdQhQitv cuaquit~cdelta(ham1ca.qui t~chQch~s6thichnghi) hi~nclingconrat ch~mclingla mQtvand~dangquailtam. Trangphan cu6icuachU'O'ng,chungtai setdnhbaymQtquit~chQck~thQ'pcuanhi~u phU'O'ngphaphQckhacnhaud~giiiiquy~tkhokhannay. 1.3Xap xi mb 1.3,1H~mb ..............................................................-.......__..........................-....................................., ' n~uAl thl BI x n~uAj thl Bj '~B~giai mO'~Y =F(X) n~uAk thl Bk ; , , ', ', ', ' """,-"",--,,-,"""""""""""""-"""'-"""""""""""""""""""""'" ,-.-........_.-..-.-.....-.-.. H' h 1 3 K '..!' t ' -t h- ' t .:l ' tIn ,: Ien rue mQ ~ mef ong qua , Bi~nnh~pX sekichho(ltsongsong cacphfm 'n~u'cua k qui tAc va xac dinh mtlc do?Bj thuQcphf.n 'th\' ttlc1ngtlng. K~t xuAt B =2:jBjwjse du,?,cgiai mb d~chogia tri Y =F(X). H~mO'la mQtmahlnhtOaDhQcdU'Q'cxay d1,fngtren cO's&11thuy~tmO' vamayhQc.Nam1991,Bart Koskod~xuatmahlnhxapxi hammO'va dq.tenh~mO'.Theodo,mQth~mO'F la mQth~th6ngg6fi k lu~tfiO'co I dq.ng'ntuX =Aj thi Y =Bj; vafiQt fiq.ngnO'-rondq.ngbQnh6k~thQ'p [23].M8i bi~nnh~pX VaGh~th6ngsekichhoq.tsongsongphan'n~u'cua k lu~tfiO'vachocacfiUC dQBj tU'O'ngungtrongphan'thl' cuaqui t~c theonguyent~ct~pfiO'[38].Va k~txuatF(X) cuah~th6ngdU'Q'cxac dinhtheonguyent~ct5ngtuy~ntlnhcuacacBj nay. NhU'th~,fiQt h~fiO'F : IRn --7 IRmhoq.tdQngnhU'fiQt bQnh6k~t 15 hQ'pmO'[19]. Hlnh 1.3 ma tit m9t ca:utruc h~mO't6ng quat. 1.3.2H~mb ellip x~pxi ham H~mO'coth~dl1Q'cdungd~xayd1,1'ngmahlnhchocacdi1li~u.Bart Kosko(1997)dachungminhdinhly sail: Dinh Iy 1.2 (Dinh Iy Kosko [19]): M9t h~mO'F : IRn + IRm vai so lu~tmO'thichhQ'p,co th~xa:pxi d~um9thamlien t1,1Cba:tky f :D c IRn +IRmtIeDm9tmi~ncom-p~cD. D~xa:pxi m9thamdich,KoskoSlrd1,1ngm9tt~pk caclu~tmO'ellip choh~mO'vaS1,1'xa:pxi hamdlchchotrl1accoth~dl1Q'cxemnhl1S1,1'phil d~uk ellipnayleDd6thi cuahamdlch. Hlnh 1.4minhhoi?-m9th~mO' ellipd~xa:pxi m9thamdlch. a x x Hlnh 1.4:Trang hlnh (a) b6n lu(\t ma Ian phu m(\tph);.nham dich f : Dl C JR ---t ID2 C JR. Hlnh (b) sir l'1oi,chi phi tlnh taanciing caahdn. d\lngsir d\lngnhi~ulu(\t metellipklch thl1acnho d~xip xi ham f. K~tquaxip xi (b) t6t hdnrit nhi~u(a) bu CohaimahlnhhQcd~xayd1,1'ngm9th~mO'. Ma hlnh thu nha:t,hQcgiamsat, chig6mm9tgiaidoi?-nhQc(nhl1mi?-ng llO'-ron)d~xac dinh caetrQngso wi' Nhl1th~,cacehuyengia phiti cling 16 ca:pchoh~th6ngcaclu~tellip thkh hQ'pv<1ibai toaDdU'Q'chao Ma hlnh hQcthu hai,hQckhanggiamsat,phuc t;;tphO'nvag6mhaigiai cIo;;tnchinh. Giai cIo;;tnthu nha:t,tu t~pcacqui t~ctho (chong~unhienk ellip ba:tky) h~sehQCva hi~uchinhkichthU'<1cclingnhU'hU'<1ngthichhQ'p chotung lu~tellipsaochophil kin nha:tt~pm~udl1Q'chaoGiai do;;tnthu hai clingnhU'trongmahlnh thu nha:tla xac dinh cactrQngs6choh~mCi. Tom l;;ti,h~mCicoth~dU'Q'cS11dvngd~xay d1!ngmahlnh chom9tt~p m~u.Di~mchinhkhi xay d1!ngma hlnh la cling ca:pt~plu~tchoh~mCi; t~plu~tnay co th~dU'Q'cxac dinh t1!d9ngnhU'ngphai chotrU'<1cs6 lu~t c~nxay d1!ng.N~us6lu~tit, k~tquamahlnh sekhangt6t; nhU'ngn~us6 lu~tnhi~u,ta sedl1Q'cm9t ma hlnh sai s6 tha:pnhl1ngphai chi phi nhi~u thCiigian may tlnh cho qua tdnh tlrih tOaD. NhU'th~,h~mCicling nhU' ffi;;tngIan truy~n,conl~thu9Cnhi~uvaokinh nghi~mcua ngU'CiiS11dvng. 1.4 Thu~t giiii di truy~n giiii bai toan xac djnh thalli s6 , Trangnhi~uungdvng,baitOaDxayd1!ngmahlnhchodi11i~ucoth~ dl1Q'cdl1av~bai tOaDxac dinhthams6,m9td;;tngbai tOaDngU'Q'c[5],nhU' sail: Bai toan xac djnh thalli s6 Cho n ={(Xi,~)IXiE IRn;~E IRm;i =1,N} \ va GA : IRn +IRm trongdo, A = (aI,a2,...,ap)E IRp lat~pcacthams6chU'abi~t. Vciicdl1O'ngchotrl1cic,xacdinht~pcacthams6A saochoV(Xi,~) E n IIGA(XJ - ~II <c. (1.19) 17 PhU'O'ngphapthu{jtgidi di truyenla mQtphU'O'ngphaptim ki~mthlch h<;ipd~xacdinhvec-to'thalliA nay. 1.4.1Cae khai ni~mcd ban eua thu~t giai di truy~n Nam1975,John HollandtrongmQtcongtdnh nghienCUllv~cach~ th6ngtri tu~nhant~o[13]dadU'arakhaini~mthu~tgiaidi truy~n.Qng ly lu~nr~ngt{nhhi~uquacungtlnh d~thlchungcuaS1fs6ngcodU'<;icla doti~nboatrongchQnlQct1fnhien;va do do, ta coth~ap d1,1ngch{nh nguyenly do trongcach~th6ngnhant~o.Va Hollandda d~xua:tmQt phU'O'ngphaptim ki~mm6igQila thu~tgiaidi truy~n. Thu~tgiaidi truy~nla mQtthu~tgiaimaytlnh tImki~mlai giaid1fa trendQngl1fcti~nboa trong hQcthuy~tti~nboa cua Darwin. Y tU'Cing ch{nhcuathu~tgiaidi truy~nnhU'sail: - Xemd6itU'9'ngc~ntim cuabaitoannhU'mQtcdthe'. - M6ta l6pcacd6itU'<;ingc~ntImtheomQtc{{utruetitn hod,tU'O'ng t1JnhU'trongt1fnhien,cacsinhv~tcomadi truy~nlacacgene(chu5ichua b6nlo~iNucleic). - KhCiit~omQtqulinthl bandatigamcaccath~. - Xac dinh cacpheptac dQngVEtOqUailth~gamcacphep:phep ch9n) pheplai va phepaQtbitn mophongtU'O'ngt1fdQngcO'ti~nboatrong ti~n hoat1Jnhien. - Dinh nghiame>tde>do th{chnghi chocacca th~. - Dungcacphepmophongti~nboatacde>ngVEtOqUailth~valU'utruy~n qu~nth~quanhi~uth~h~.Qua quatrlnh di truy~ndo, qUailth~se ti~n hoatheomQtdinh hU'c1ngdU'<;icqui dinh trU'c1cquadQdo th{chnghi. NhU' th~,cangngay,qUailth~cangco nhi~uca.th~ti~nt6i m1,1ctieu tim ki~m. - Trongm5i th~h~ti~nboa,ca th~thlch nghi nha:ttrong quail th~co th~dU'<;icchQnnhU'lai giai (ho~cxa:pXl lai giai) cuabai toan. Th1fccha:t,thu~tgiai di truy~nla mQtphU'O'ngphaptIm ki~mlai giai trongmQtkhonggian caclai giai. Tuy nhien,khacv6i cacphU'O'ngphap 18 tlmki~mtruy€mth6ng,thu~tgiaidi truy€mconhilngd9-ctnrngsail: (1)Thu~tgiaidi truy~n1aphuongphaptlm ki~mtIeDmQtt~pcacdi@m (quanth@);khongphaitrentungdi@mdonIe,rC1ir~c. (2)Thu~tgiai di truy~nchi S11dvngcacthongtin nQit~itrongqUailth@; khongdungba:tky mQttri thuc phVnaokhac. (3) Thu~tgiai di truy~nS11dvng cac1u~tchuy@nd6i dva tIeDxac sua:t; khongphai tIeDcac1u~tquy~tdinh. 1.4.2Cae pheptoancd ban euaThu~itgiai di truy~n Chot~pk kyhi~uk~thuc(t~pcacmadi truy~n): T = {tl,t2,...,tk}; vaS 1achu6icochi~udaic6dinhl. M6i cath~se1amQtS, trongdo S[i]E T; i =W. GQi - M 1as6cath~trongqUailth~. - G 1as6t6i da cacbu6c1i[Lp. - Pr,Pc,Pm1acacthalli s6 (xacsua:t)di~ukhi~ncacquatrlnh tai sinh, 1ait~p,va dQtbi~n. - f 1ahamdo dQthichnghi. Thu~tgiai di truy~ngomcacbu6c ch{nhsail: Thu~tgiai di truy~n- GA (GAl) - Tr;LongtfunhienmQtqulinthebanriliuP(O) chuaM cdthi!. - D(jt t = O. 19 (GA2) VS E P(t)) tinhf(S). (GA3) Nlu aieuki~ndung(1.19)thoahayt >G thi GotoGA6. (GA4)Tr;LOmQtqu6nthe"mdi nhusau: (GA4.1) Th1Jchi~npheptai sinhvdi xacswltPn cheFveLDQ(t). (GA4.2) Th1Jchi~npheplai vdi xacsuraPC)tr;LOthl h~conchau P(t +1). (GA4.3) Th1Jchi~naQtbitn vdi xacsuo;/tPm)tr;LOra caccathe"lr;t chottj,pR(t). (GA4.4)P(t +1)f- P(t) UP(t +1)UQ(t) U R(t) va chi giiJ lr;tiM ca the"t6'tnht{t. (GA4.S)t f- t+1. (GAS) GotoGA3. (GA6)Gidimaktt qua. Trongdo,cacphepdi truy~ng6m: Phep chn: - PhepchQnla m9tthut\lCmaytlnhmoph6ngquatrlnhchQnlQcm9t cath~tirqu~mth~dl!atrenkhanangthkh nghicuano. - Y nghiacuaphepchQnla giupchocacca th~th{chnghicaoseco nhi~uca maydU'Q'cchQnlai ghepsinhra caccath~choth~h~m&iv6i khclnangthkh nghicaohall. Ch{nhdi~unaygiupcaiti~nqu~nth~theo hU'&ngti~nhoathkh nghihanv&imoitrU'Cfng. - ThongthU'Cfng,phepchQndU'Q'cthl!chi~nnhU'sau: (1)Phanhoq.chdoq.n[0,1]thanhM doq.ncon[ai,biJnhU'sau: f( i) al =O,bM=1,bi=ai+ -,aj+l =bjF (1.20) 20 Vi =1,M,j =2,M - 1. trongdo,f( i) la dQthichnghicuacath~th1ii va M F='Lf(i). i=I (1.21) (2)Ca th~th1ii seduQ'chQnn~ut<;tox +-Randomvax E [ai,bJ trongdo,Randomlahamt<;tomQtgiatri ng~unhientrongdo<;tn[0,1]. SailkhimQtcath~daduQ'chQn,mQtbimsaocuanoseduQ'chepvao illQtnhomrieng,nhomnaysephvcvv chocacphepk~ti~p. Phep lai: - Lai la quatrlnh traod6ithongtin giiXacaccath~duQ'chQntrong qu~nth~. - Mvcdichcuapheplai la t<;toranhiXngcath~m6ithirak~nhiXngd~c t{nhdi truy€mcuachavam~. - Co nhi~ucachthvc hi~nlai khacnhau(tuy thuQcbai toan). Tuy nhien,mQtpheplai t6ngquatg6mhaibu6cch{nhsail: (1)ChQncacdi~mlai trencaccath~chavam~. (2)Tachtir cacdi~mlai naycaccath~cham~thanhcackhilcconva hoanvi t6 hQ'pcackhilcconnayd~t<;tora caccath~m6i. Phep d{>tbien: - DQtbi~nla sv thayd6ing~unhiengia tri cuamQt(s6)vi tr{tren chubicath~. - DQtbi~nnh~mlamphongphilthemchoqu~nth~di truy~n. 1.4.3Hi~u qua cua thu~tgiai di truy~n Dinh nghia 1.2: ChoT ={tI,...,td la t~pkyhi~uk~tthilc,vaT+= T U{*}. ('*' lakyhi~ucoth~d~idi~nchomQtkyhi~uti E T ba:tky) Sd db duQ'cdinhnghiala mQtchubiS,I vi tr{maSri]E T+,i = 1,I. 21 Tif dinhnghia1.2,ta d~dangsuyfa: - SosadE>cochieudai l la (k+ 1)l. - M(>tchu6ixacdinhlu6nco2lsadE>chuano, - M(>tqu~nth~M cath~secotif 2ld~nM2l sadE>tliy theoSlJdad<;Lng cuaqu~nth~. Dinh nghia 1.3: . B~ccuasadE>H, ky hi~uo(H) la sovi tri khac,*, trongsadE>. . ChieudaixacdinhcuasadE>H, ky hi~u5(H), la khoangcachgiuavi tri khac,*, d~utienvacuoiclingcuaH. Va:ndecuata la 110'C111Q'ngxemcokhoangbaanhieutrongs62l d~n M2l sadE>d11Q'cthu~tgiaidi truyenS11dvngtrongquatrlnhtlm ki~m? Kh6ngma:tlnht6ngquat,ta chixett~pT ={O,I}, Va ta com(>tvai qui 110'Csau: - M(>tchu6i A d11Q'cvi~t l<;Li:A =al...ak;ai E T,i =1,k. - A(t) la qu~nth~CJth~h~thu t; vaAj la m(>tcath~cuaqu~nth~nay. M~nhd~1.1[11] D110'ianh h11CJngcua phepchQn,s6m~uthu(>csa dE>H cJth~h~thu t la: m(H,t) =m(H,0)(1+c)t (1.22) v6ic la m(>th~ngs6. ChUng minh m~nh d~ 1.1 Gia S11cJb110'ct ta co m m~uthu(>csa dE>H, Ta vi~tm =m(H,t), Xac sua:td~m(>tchu6iAi d11Q'cchQnla: J( i) Pi=p' (1.23) 86bansaDcuaAj sauquatrlnhchQn(n l~n)la: Xi =M.Pi =M. J(i) p' (1.24) 22 M.m(H,t).f(H) m(H,t +1)= (").L.jf J V6if(H) 1agiatri tIlingblnhcuacacchu6itrongqu~nth~thuQcsC1db H t;;tith~th~t. D~t Suy ra s6ffi~Ucua H cith~h~(t + 1) sail khi chn1a: m m(H,t+1)=LXi. i=l Ta co m(H,t+1)=ML.~lf(i) =M.m.!;;L.if(i) L.jf(j) L.jf(j) hay f =L.jf(j) M. Ta co, f(H) m(H,t+1)=m(H,t) - . f D~tf(H) =c.f + f, v6ic 1affi(>th~ngs6,ta co: c.f +f m(H,t+1)=m(H,t) - =(l+c)m(H,t). f Suyfa: m(H,t) =m(H,0)(1+c)t. (1.26) (1.27) (1.28) (1.29) (1.30) M~nhd~1.2 [11]:Du6ianhhuCingcuaphep1ai,n~uPs1axacsua:tbn tq.icuasC1dbH thl: o(H) P >l- p - s- cl-l ChUngminh m~nhd~1.2 Ta co,xacsua:td~ffiQtSC1dbH bi phaVcl1a: o(H). Pd=l - 1' \ I ~ ~ . vaxac suatton t;;tl: Ps =1- Pd=1- o(H) l- 1. 23 (1.31) (1.32) (1.33) Nghia la, ill9t sCid6 v~nt6n tq.ikhi di~illlai n~illngoaidoq.nchi~udai xacdinh. N~upheplai duQ'cthvc hi~nng~unhienv6i xac sua:tPc, thl xac sua:t t6n tq.icuaill9t SCid6 H la: 6(H) Ps =1-pc-' l - 1 Gongthuc (1.34)khongxetd~ntruCinghQ'pcahaichu6iduQ'chQnlai clingthu9CSCid6H. TrongtruCinghQ'pnay,xacsua:t6ntq.icuaH la 1. Nhuv~y,ta coch~ndu6icuaPschoScid6H ba:tky. Hay 6(H) Ps> 1- Pcl - 1. Do pheplai sayra sailphepchQn,(1.22)va(1.31)chota: f(H) [ 6(H) ]m(H,t+1)>m(H,t) 1 1- Pcl - 1 . (1.34) (1.35) D6iv6i phepQ9tbi~n,nh~nxet r~ngill9t Scid6t6ntq.isailkhi d9tbi~n n~uta:tcacacvi tri xacdinhv~ngili'nguyen(chicacvi tri da:u,*, bi d9t bi~n). GQixacsua:thayd6iill9t vi tr{trenchu6ilaPm'suyra xacsua:t6n tC;1icllaill9tvi trila (1- Pm)' Nhuv~y,xacsua:t6ntq.icuaill9tscid6saild9tbi~nlaPe=(l-Pm)o(H). N~uPm << 1,xacsua:t6ntq.icuaH saild9tbi~nla: Pe ~ 1- o(H).Pm (1.36) Ap dvngcack~tquatren,ta k~tlu~nr~ngs6bansaocuascid6 H nh~nduQ'cCith~h~k~ti~pdu6ianhhuCingcuacabaphepdi truy~nla: f(H) [ 6(H) ]m(H,t+1»m(H,t) 1 1-Pcl-1 Pe' (1.37) guy ra f(H) [ 6(H) 6(H) ] m(H,t+1)>m(H,t) 1- Pc- - o(H).Pm+pc-o(H).Pm . f l-l l-l . (1.38) 24 1.4.4M<)ts6 van de khi sit dvng thuifttgiiii di truyen giiii bai toan xac dinh thalli s6 Khi ap dvngthu~tgiitidi truy~ngiitibai toaDxacdinhthalli socho t~pduli~un vdi d(;tnghamG bi~ttrudc,cactac giitthuc)'ngdungCali trucchue;ichi~udaik codinhd~bi~udi~ncath~la m9tvec-tO'thalli so A E IRk [11]. N~ukhCiit(;toqu~nth~P(O), M cath~thl t~pky hi~uk~tthucT chua toi da k.M ky hi~u.Me;iky hi~ud(;tidi~nchom9t so thlfc duQ'ckhCiit(;to ng~unhien. Nhu the m9t kh6nggian lCiigiiti ~={Ai E IRkIAi[j]E T}. duQ'Ct(;tofa. Kh6ng gian~cotoida2k.Mph~ntu. Vdi hi~usuattlm kiemO(M3) [13],trongph~nldn cacthlfcnghi~m cuachungt6i, lieUM < 500vagiitsukh6ngdungphepd9tbi~nthl sail khoitng50theh~,ta thuCingduQ'cath~tot nhatcuat~p~. Mq.cdu hi~usuatcuathu~tgiitidi truy~nla rat cao,tuynhien,khiap dvngd~giitibaitoaDxacdinhthalliso,m9tsovand~t6nt(;tinhusail: (1)Kh6nggianlCiigiiti~ durat ldnnhunghuuh(;tn.Va nhuthe,coth~ ~kh6ngchualCiigiiti.Nghiala,vec-tO'totnhatcua~v~nkh6nglam chodi~uki~nIIGA(Xi) - ~II ~ 0;V(Xi,~) E n. (2)Vand~thuhaidangluuyhO'n;dolavand~xacdinhtrudcd(;tngcua hamG. Vi~cxacdinhd(;tnghamphuhQ'pthuCingdokinhnghi~mcua nguCiiphantlch. Di~unaygaykh6ngit khokhanchonhungphan tichVieDkh6ngnhi~ukinhnghi~m. VI nhungly dotIeD,chungt6ikh6ngdungtrlfctier thu~tgiitidi truy~n nhuneutIeDd~giitibaitoanxaydlfngm6hlnhphuhQ'pt~pduli~ucho trudc;machidungthu~tgiitidi truy~nd~he;trQ'quatdnhhQCcuam(;tng Iantruy~n. 25 1.5 M6 hlnh NNGA (Neural Network and Genetic Algorithm) NNGA lam6hInhk~thQ'pgili'am;;tngIantruy~nvathu~tgiilidi truy~n. Nhi~utacgiadasirdvngphU'O'ngphapk~thQ'pnaynhU'ngtheonhi~uhU'ang khacnhau: (1) Dung thu~tgiai di truy~nthay cho cacthu~tgiai hQccuam;;tngIan truy~n. Theo hU'angnay, thu~tgiai di truy~ndU'Q'csir dvng d~tIm bQtrQngcho m;;tngIan truy~n. NhU'chungt6i da phan tlch Ciph~n trU'ac,co th~m;;tngchi hQitv v~C\1'Cti~ucvc bQ;VI kh6nggiankhCii t;;tOband~ukh6ngchuaC\1'Cti~utOaDcvc. (2)Dungthu~tgiaidi truy~nd~xacdinhc~utrucm;;tng.PhU'O'ngphap nay co thalli vQnggiai quy~tdongthai hai v~nd~cuam;;tngIan truy~n:xacdinhc~utruc(s6lap j,nvas6nut j,nchom6ilap)dong thaiclingxacdinhlu6nvec-tO'trongtU'O'ngungvaic~utrucdo.Theo chungt6i, phU'O'ngphapnaycodQphuct;;tpr~tIan va doih6imQt kh6nggiannhaIand~coth~cungluc chuanhi~um;;tngkhacnhau [14].(1) Chungt6i ti~pc~ntheohU'angkhac.Nghiala, ta kh6ngthayhoantoaD cacphU'O'ngphaphQCcuam;;tngIantruy~nb~ngthu~tgiaidi truy~nma chidungthu~tgiaidi truy~nd~khCiit;;tobQttQngchom;;tngIantruy~n; vasaildo,dungti~pm<)tthu~tgiaihQcd~ti~ptvc quatr'tnhdi~uchinh b<)trQng. Ngoaithu~tgiaihQcdeltachuj,nvathu~tgiaicaiti~ndelta-baT-delta, coffiQts6thu~tgiaihQccaiti~nkhac[35].Chungt6i nghienCUllvasir d\lngthu~tgiaiQuickProp. 1M. Othmanva caec(mgsll dung thu{Ltgiai di truyl:nxAyd\fngm(\tm",ng(ciu true va tr<;mg56)nh{Lnd",ngchi sau nguy~nAm ti~ng Mii-lai tach rCti. K~t qua, phai mit sau ngay thi hanh tr~n may pentium 100Mhz, RAM 64 MB [14]. 26 1.5.1 QuickProp, illccai ti~n QuiekProp, viet tiit euaQuick Propagation,la phuO'ngphap dU'Q'ed~ xua:tb6'iScottFahlman[8];lamQttrong nhungdj tien nh~mnangeao toedQhQitv euathu~tgiiiihQedelta.Chungt6i ehQnQuiekPropthayVI ehQndelta-baT-deltaVIQuiekPropkh6ngl~thuQeVaGcaeh~sohQe. y tU'6'ngehinheuaQuiekPropla xa:pxi haml8i b~ngmQtehu8icae parabolcophanm6'hU'<1nglentren(hInh1.5(a)). T(;1im8ibU'<1e,trQngse dU'Q'ee~pnh~tsaGehogiatri l8i E trong(1.12)d(;1tdenvi tri qreti~ueua parabolke. Cv th~,e6ngthuee~pnh~ttrQngdU'Q'exaydl,fngnhU'sau: - GQi . D(t - 1)la gia tri d(;1ohamhaml8i 6'bU'<1el:;tptrU'<1e. . D(t) la gia tri d(;1ohamt(;1ibU'<1ehi~nhanh. . C (t) la bienthientrQngsoeuabU'<1el:;tptrU'<1e. - Ta bietr~ng,t(;1ivi tri el,feti~u,d(~whamhaml8i seb~ng0,nhU'the D(t+1)=O. (1.41) Mvedieheuata laxaedinhbienthientrQngsoC(t) ehobU'<1ee~pnh~t hi~nhanh. Ta co: C(t) D(t + 1)- D(t) C(t - 1) D(t) - D(t - 1)' The (1.41)VaG(1.42)ta dU'Q'C: D(t) C(t) = ( ) ( )C(t- 1).Dt-1 -Dt (1.42) (1.43) V~y,trQngsodU'Q'ee~pnh~ttheocaee6ngthuesau: w(t)~ w(t- 1)+C(t) trongdo,C(t) dU'Q'exaedinhtheo(1.43)vaD(t), D(t - 1)dU'Q'exaedinh theo(1.16). 27 Hlnh 1.5minh hQacachtlnh nay. a w D-o-l+~ w Hlnh 1.5:(a) Ham 16iduqexflpxi bo-im(Jtehu6icaeparabol.Qua tr\nh e(ipnh(it trngla quatr\nh di ehuy~n tit eVeti~ueuaparabolnay d~neVeti~ueuaparabolk~. (b) Hlnh anh euaparabolhi~nhlmhduqe xaedjnh tit caegia trj D(t -l),D(t). Nh~nxetr~ngc6ngthllCbi~nthientrQng(1.43)sekh6ngxacdinhkhi D(t)= D(t -1). Trangtnl'dnghQ'pnay,C(t) sedU'Q'ctlnhtheoc6ngthllc (1.15): C(t) =ED(t). QuickPropdU'Q'cMurraySmithx~pVaGnhomnhli'ngphU'O'ngphaphQc b~chai vathl1'anh~ndingt6cd9h9i t1,lcuaQuickPropnhanhhO'nr.it nhi~uIansov<Jithu~toanhQcdelta[35]. 1.5.2M<;tngNNGA venthu~t giai hQc tren cd s(j thu~t giai di truy~n Bai toanxacdinhtrQngchom9tc.iutrucm<;1ngchotrU'<Jcchinhla bai toanxacdinhthams6nhU'trlnhbaytrong1.4.aday,hamchotrU'<Jcla anh X<;1N N : IRn ---7 IRm.Vat~pcacthams6A canxacdinhchinhla vec-tO'trQngW. NhU'v~y,thu~tgiaidi truy~nco th~dU'Q'csir d1,lng.Tren C(js&do, chungt6i d~lightm9tthu~tgiai hQccho m<;1ngIan truy~ntren c(js&thu~tgiai di truy~nNNGA nhU'sau: 28 Thu~itgiiii NN GA (NNGA1) Khdi tr;wvec-teJtr9ng W cho mr;rngIan truytn bangthug,t gidi di truytn vdi t6/iaa G budc I(fp. (Nhu trinh baytrudc)chungt6i ch9nG =50) (NNGA2) Ntu aitu ki~n(1.12)chuathda)thi cg,pnhg,ttr9ngtheo QuickProp. 1.6K~t lu~n Tomlq.i,chungtai datdnh baym9tcacht6ngquailcacphU'O'ngphap mciinha:ti~pc~nmayhQctrongphantlch dif li~u.M8i phU'O'ngphap, nhudatdnh bay,d~uconhifngdi~mmq.nhvadi~my~unha:tdinh. N~u khangcoin~ngvi~cxacdinhca:utructhlchhqpthl mq.ngIantruy~n,theo chungtai la cachti~pc~nphuhqphO'ncachovi~cxayd1,1'ngm9tmahlnh tU'Cingminhtrongphantlchdif li~u.PhU'O'ngphapti~pc~nly thuy~tmCi, th1,1'ccha:tla m9tmar9ngcuarnq.ngnO'-ronh~mt~ndl,mgt6i datri thuc cuachuyengia(phantlchviencokinhnghi~m).D~hq.nch~81,1'ph1,1thu9C nay,chungtaid~lightmq.ngNNGA vciim9tlcip~n.Th1,1'cnghi~mchung tor~ngphuO'ngphapd~lightthU'Cingchok~tquat6t (xemchU'O'ng4: Ma hlnhNNGA apd1,1ngtrongphantlchcacdif li~uhoahQCvay khoa). Thu~tgiaidi truy~nla m9tphuO'ngphapap d1,1ngra:thi~uquacho nhiingbaitoanNP-Complete,la nhifngbai toanmakhanggianlCiigiai lahiiuhq.nnhungdo81,1'bungn6cuat6 hqpvadotlnhhifuhq.ncuamay tlnhlienkhangth~apd1,1ngnhifngphU'O'ngphaptlm ki~mtruy~nth6ng ciU'qc.D6ivciicacbaitoancokhanggianlai giaivahq.n,nhU'baitoanxac ciinhtham86chinghq.n,thl thu~tgiaidi truy~nkhangluandambaa8e tlmduqclai giait6tnha:t.HO'nnifa,dq.nghamlq.iclingl~thu9CVaGkinh 29 nghi~mngU'Ciiphantlch,di~umata dangc6tranh,lamchothu~tgiaidi truy~nkh6ngphatbuyh~ttacdvng.ChU'O'ngsauchungt6i setdnh bay ID9tcachti~pc~nmar9ngthu~tgiaidi truy~nnh~mkh<icphvccach~n ch~nay. 30