Dùng genetic programming giải bài toán symbolic regression

1DUØNG GENETIC PROGRAMMING GIAÛI BAØI TOAÙN SYMBOLIC REGRESSION Traàn Ngoïc Anh Khoa Toaùn Tin Ñeà taøi nghieân cöùu khoa hoïc caáp tröôøng 2006 TOÙM TAÉT Trong ñeà taøi naøy, taùc giaû tìm hieåu vaø aùp duïng Genetics Programming (GP) giaûi baøi toaùn Symbolic Regression (SR). Caùc thöû nghieäm treân baûy haøm moät bieán thöïc ñaõ chæ ra raèng coù theå giaûi baøi toaùn naøy baèng GP. Tieáp theo ñoù, taùc giaû aùp duïng chieán löôïc ñoäng vaøo pheùp lai chuaån nhaèm khaéc phuïc nhöôïc ñieåm tìm kieám cuïc boä cuûa pheùp lai naøy. Keát quûa chaïy 6 thöû nghieäm khi xaáp xæ hai haøm moät bieán ñöôïc choïn töø baûy haøm treân ñaõ chæ ra: pheùp lai chuaån coù aùp duïng chieán löôïc ñoäng ñaït ñöôïc ñoä chính xaùc cao hôn vaø oån ñònh hôn trong khoaûng thôøi gian ít hôn. 1. Môû ñaàu Genetic Programming (GP) laø moät nhaùnh cuûa Genetics Algorithm ñöôïc nghieân cöùu ñaàu tieân bôûi John Koza töø naêm 1972, sau ñoù bôûi William Langdon, Ricardo Poli, ... GP laø moät phöông phaùp toái öu kyù hieäu döïa treân bieåu dieãn caây – caây laø caáu truùc linh hoaït coù theå bieåu dieãn caùc chöông trình maùy tính, caùc bieåu thöùc, phöông trình toaùn hoïc, … GP coù nhieàu öùng duïng quan troïng nhö laäp trình töï ñoäng, giaûi baøi toaùn hoài quy kyù hieäu (Symbolic Regression). Phaàn 2 giôùi thieäu baøi toaùn SR vaø moâ hình aùp duïng GP giaûi baøi toaùn SR. Phaàn 3 aùp duïng chieán löôïc ñoäng vaøo pheùp lai chuaån trong GP nhaèm taêng ñoä chính xaùc cuûa lôøi giaûi. Phaàn 4 laø giao dieän chöông trình thöû nghieäm vaø keát quûa thöû nghieäm. Phaàn 5 laø caùc vaán ñeà caàn nghieân cöùu theâm. 2. Moâ hình GP giaûi baøi toaùn SR 2.1 Baøi toaùn SR Cho tröôùc taäp caùc ñieåm RyRxNiyxD i M iii ÎÎ== ,},,...,1),{( , taäp caùc haøm cô sôû 2F = ...}tan,cos,sin,,exp,ln,,/,,*,,{ sqrtabspow-+ vaø taäp caùc toaùn haïng T = ,...},,...,,{ 2121 consconsxx . Baøi toaùn ñaët ra laø tìm moät haøm RRf M ®:* , f* ñöôïc taïo bôûi caùc haøm trong F vaø caùc toaùn haïng trong T sao cho 0 %100* )(* )*,( 1 @ - = å = N y yxf DfE N i i ii . (1) 2.2 Thuaät giaûi di truyeàn – GA Hoaït ñoäng cuûa GA ñöôïc cho trong hình 1. Taïo ngaãu nhieân PopSize (PS) caù theå ban ñaàu (Q), t = 0 while (t < T) Qbr Q Qmr Qcmr Qrep = Qcmr U Qmr. U Qbr U Qgr Q = Opt (Qrep) Tính ñoä thích nghi cho caùc caù theå trong Q, t = t+1 Ñoät bieán (V) Choïn (III) caùc caù theå töø Q vaø lai (IV) chuùng Qcr Ñoät bieán (V) (1) (2)(4) (3) (5) Sinh ngaãu nhieân (I) Qgr Hình 1: Caùc böôùc thöïc hieän cuûa GA 3Trong ñoù, soá löôïng caùc phaàn töû ñöôïc: (1) choïn (theo ñoä thích nghi) töø Q ñeå lai laø PSC = (pCPS % 2 = 0 ? pCPS : pCPS+1), (2) choïn (ngaãu nhieân) töø Qcr ñeå ñoät bieán laø PSCM = pcm*PS, (3) choïn (ngaãu nhieân) töø Q ñeå ñoät bieán laø PSM = pmPS, (4) choïn (xeùn theo ñoä thích nghi) töø Q ñeå taùi taïo laø PSb = pbPS; vaø (5) coù (1 – (pC + pm + pb))PS ñöôïc sinh ngaãu nhieân. Caùc pheùp choïn treân döïa vaøo thuû tuïc choïn phaàn töû töø taäp L phaàn töû theo baøn xoay roulette theâm vaøo taäp T ôû vò trí thöù r. Goïi seli laø xaùc suaát choïn Li (chuù yù: 1£å i isel ). Saép taêng L theo }{ isel vaø ñaët: p0 := 0, å = = )( 1 : LCard i iselS . Thuû tuïc nhö sau: RWS (L, p, kind, r) begin do - q = random(0; S) Î (0; S) - if (pi-1 < q £ pi), vͣi i = 1..Card(L) T[r] = Li while ( ï î ï í ì =<$Ù= Ú=Ù=Ù= Ù - )]}:()_[( )]()02%()_{[( ) 1 jr rr TTrjALLDIFFkind TTrTWODIFFkind FREEkind ) return T[r] end vôùi kind laø hình thöùc choïn: ï î ï í ì ¹¹ ¹"¹ = elseFREE TTTTTWODIFF nmTTALLDIFF kind nm : ,...,:_ ,:_ 3210 Töø ñoù, ñeå: - choïn ngaãu nhieân: o böôùc choïn (2): T[r] := RWS(QCR, 1/PS, DIFF_ALL, r), r=1, .., PSCM o böôùc choïn (3): T[r] := RWS(Q, 1/PS, DIFF_ALL, r), r=1, .., PSM - choïn theo ñoä thích nghi g: o böôùc choïn (1): laáy PSb caù theå coù ñoä thích nghi cao nhaát töø Q, T := PopTop (Q, g, PSb). 4o böôùc choïn (4): T[r] := RWS(Q, g, DIFF_TWO, r), r=1, …, PSC. 2.3 Aùp duïng GP giaûi baøi toaùn SR Thuaät giaûi di truyeàn tieán hoùa treân caáu truùc caù theå coù daïng caây ñöôïc goïi laø GP. Bieåu dieãn haøm baèng caây nhò phaân ta coù theå duøng GP ñeå giaûi baøi toaùn SR. ÔÛ theá heä ñaàu tieân, moät quaàn theå caùc haøm (hay caây hay caù theå) ñöôïc sinh ngaãu nhieân. Trong caùc theá heä sau, ôû moãi theá heä, caùc haøm toát coù E beù ñöôïc choïn löïa ñeå bieán hoùa (lai gheùp, ñoät bieán) nhaèm taïo ra theá heä sau toát hôn. Haøm toát nhaát ôû theá heä cuoái cuøng ñöôïc choïn laøm lôøi giaûi. 2.3.1 Bieåu dieãn haøm baèng caây nhò phaân Caùc nuùt trong chöùa caùc toaùn töû, caùc nuùt laù chöùa caùc toaùn haïng. Chaúng haïn, xem hình 2. 2.3.2 Khôûi taïo quaàn theå Khôûi taïo quaàn theå ban ñaàu chöùa PopSize caây coù ñoä cao toái ña laø d. Coù 3 phöông phaùp khôûi taïo: Full, Grow, Ramped. 2.3.2.1 Khôûi taïo Full Caùc haøm cô sôû ñöôïc choïn laøm caùc nuùt cuûa caây cho ñeán khi ñaït ñeán ñoä saâu d-2, caùc toaùn haïng ñöôïc choïn laøm caùc nuùt ôû ñoä saâu d-1. Ñaëc ñieåm cuûa phöông phaùp naøy laø: moïi caù theå ñeàu coù cuøng ñoä cao d, quaàn theå khoâng ña daïng veà caáu truùc. 2.3.2.2 Khôûi taïo Grow Ñaàu tieân, choïn haøm cô sôû laøm nuùt goác. Sau ñoù, choïn ngaãu nhieân haøm cô sôû hoaëc toaùn haïng cho caùc nuùt ôû ñoä saâu 1. Neáu moät nuùt ôû ñoä saâu 1 laø toaùn haïng thì chaám döùt khôûi taïo treân nhaùnh con töông öùng ñoù, tieáp tuïc khôûi taïo caùc nhaùnh coøn laïi. Hình 2: Bieåu dieãn moät soá haøm baèng caây nhò phaân 5Ngöôïc laïi, neáu moät nuùt ôû ñoä saâu 1 laø haøm cô sôû thì tieáp tuïc khôûi taïo caùc nuùt ôû ñoä saâu 2. Tieáp tuïc khôûi taïo cho caùc nhaùnh cho ñeán khi caùc nhaùnh ñeàu ñaõ coù toaùn haïng hoaëc nuùt cuoái cuûa nhaùnh coù ñoä saâu d-2. Khi nuùt cuoái cuûa nhaùnh coù ñoä saâu d-2, ta choïn ngaãu nhieân moät hoaëc hai toaùn haïng laøm caùc nuùt coù ñoä saâu d-1 vaø keát thuùc nhaùnh. Ñaëc ñieåm cuûa phöông phaùp Grow laø: caùc caù theå coù ñoä cao ngaãu nhieân thuoäc ñoaïn [2, d], quaàn theå seõ chöùa nhieàu caù theå coù ñoä cao nhoû (2, 3, …) vaø ít caù theå coù ñoä cao lôùn (d, d-1, …). 2.3.2.3 Khôûi taïo Ramped half-and-half Ñeå khôûi taïo quaàn theå chöùa PopSize caù theå coù ñoä cao nhoû hôn giôùi haïn ñoä cao d cho tröôùc, ta traûi qua m giai ñoaïn, giai ñoaïn k khôûi taïo N/m caù theå chöùa: a) N/m/2 caù theå coù cuøng ñoä cao k baèng phöông phaùp Full, b) N/m/2 caù theå coù ñoä cao trong ñoaïn [1, k] baèng phöông phaùp Grow. Phöông phaùp naøy keát hôïp ñaëc ñieåm cuûa hai phöông phaùp Full vaø Grow ñeå taïo ra quaàn theå ña daïng veà caáu truùc. 2.3.3 Ñoä thích nghi cuûa caù theå Ñoä thích nghi cuûa caù theå theå hieän khaû naêng tham gia cuûa caù theå (so vôùi quaàn theå) vaøo quùa trình taùi taïo – caùc quùa trình choïn (1), (4) trong hình 1 – ra theá heä sau. Noù phuï thuoäc chính vaøo loãi cuûa caù theå treân taäp D: caù theå f coù E(f) lôùn/nhoû seõ coù ñoä thích nghi cao/thaáp. Caùc coâng thöùc sau chæ ra caùc caùch tính ñoä thích nghi gi cho caù theå fi (G(fi)): ),(:)( ii fEfStdFit = (2) ),(: ,...,1 jKj fStdFitMaxMaxStdFit = = (3) )(1 :)( , )(1 1:)( ,)(:)( )0( i i i i ii fStdFit MaxStdFitfAdjFit or fStdFit fAdjFit orfStdFitMaxStdFitfAdjFit + = + = +-= >e (4) å = = Nj j i i fAdjFit fAdjFitfG ,...,1 )( )( :)( (5) 2.3.4 Lai gheùp Lai gheùp giöõa hai caù theå ñöôïc choïn (coù ñoä thích nghi cao) nhaèm taïo ra hai caù theå môi coù ñoä thích nghi cao. Pheùp lai gheùp chuaån giöõa hai caù theå cha, meï dieãn ra nhö 6Hình 3: Minh hoïa pheùp lai chuaån Ñoät bieán Hình 4: Minh hoïa pheùp ñoät bieán sau: a) choïn ngaãu nhieân moät nuùt (ñieåm lai) treân cha, b) choïn ngaãu nhieân moät ñieåm lai treân meï, c) traùo ñoåi hai caây con coù goác laø hai ñieåm lai ñaõ choïn ñeå taïo ra hai caây con. 2.3.5 Ñoät bieán Ñoät bieán giuùp taïo ra caùc gen môùi (caùc caây con) trong quaàn theå giuùp quaàn theå duy trì ñöôïc tính ña daïng bò giaûm ñi do pheùp lai trong quaù trình tìm kieám. Ñoät bieán treân caù theå thay ñoåi moät caây con baèng moät caây con khaùc ñöôïc sinh ngaãu nhieân. 3. Aùp duïng chieán löôïc ñoäng vaøo pheùp lai chuaån 73.1 Nhöôïc ñieåm cuûa pheùp lai chuaån Ñoái vôùi pheùp lai chuaån, moïi ñieåm lai treân caây cha (meï) ñeàu coù xaùc suaát choïn baèng nhau. Khi caùc ñieåm lai ñöôïc choïn laø caùc nuùt laù thì caùc caù theå con taïo ra raát gaàn vôùi cha, meï (chæ khaùc bieät ôû caùc toaùn haïng)ï. Caùc nuùt laù trong caây chieám “gaàn” moät nöûa soá löôïng caùc nuùt cuûa caây. Do ñoù, pheùp lai chuaån thöïc hieän tìm kieám cuïc boä: khoâng khaùm phaù ñöôïc nhieàu vuøng khaùc (chöùa caùc daïng haøm khaùc) cuûa khoâng gian tìm kieám. Ñeå khaéc phuïc, Koza ñaõ ñöa ra luaät 90-10: 90% ñieåm lai ñöôïc choïn öùng vôùi caùc nuùt trong, 10% ñoái vôùi caùc nuùt laù. [Langdon, 1990] vaø [Harries, Smith, 1997] ñaõ nghieân cöùu caùc phaân phoái choïn ñieåm lai khaùc. 3.2 Caùc pheùp lai khaùc Trong [2], [3]; R. Poli, W.B. Langdon ñeà nghò caùc pheùp lai moät ñieåm, lai ñoàng nhaát. 3.2.1 Pheùp lai moät ñieåm Pheùp lai moät ñieåm (xem ví duï trong hình 5) goàm caùc böôùc: § Tìm caây lai tieàm taøng cuûa cha vaø meï: (a) nuùt trong töông öùng vôùi hai nuùt ôû cha vaø meï coù chung soá ñoái (hoaëc truøng nhau trong tröôøng hôïp lai ngaët), (b) nuùt laù töông öùng vôùi hai nuùt con chung cuoái cuøng cuûa cha vaø meï. § Choïn (vôùi xaùc suaát ñeàu) moät nuùt treân caây chung laøm ñieåm lai cho caû cha vaø meï. § Traùo ñoåi hai caây con töông öùng cuûa cha vaø meï. Trong giai ñoaïn ban ñaàu (neáu quaàn theå ñuû ña daïng veà maët caáu truùc), lai gheùp dieãn ra ôû phaàn treân (xaùc suaát lai gheùp ôû phaàn döôùi thaáp, thaäm chí coù theå baèng 0), caùc caây con ñöôïc traùo ñoåi coù kích thöôùc lôùn, söï traùo ñoåi löôïng vaät chaát di truyeàn maïnh, tìm kieám mang tính toaøn cuïc. Ñeán moät luùc, quaàn theå seõ hoäi tuï veà caùc caù theå coù chung caáu truùc ôû phaàn treân. Luùc naøy, lai gheùp dieãn ra ôû caùc ñieåm lai beân döôùi nhöng vôùi toác ñoä chaäm hôn vì lai gheùp cuõng coù theå dieãn ra ôû treân, tuy nhieân, caùc thay ñoåi cuûa phaàn döôùi seõ taùc ñoäng lôùn ñeán ñoä thích nghi cuûa caùc caù theå (vì phaàn treân ñaõ hoäi tuï ñeán caáu truùc chung). Löôïng vaät chaát di truyeàn traùo ñoåi baây giôø ít hôn, tìm kieám mang tính cuïc boä hôn trong khoâng gian caùc caù theå coù chung caáu truùc phaàn treân. Tình traïng töông töï dieãn ra, tìm kieám seõ chuyeån “daàn” töø khoâng gian lôùn (toaøn cuïc) vaøo caùc khoâng gian nhoû (cuïc boä) hôn – coá ñònh caáu truùc. ÔÛ giai ñoaïn cuoái, khi quaàn theå haàu nhö gioáng nhau veà caáu truùc, lai gheùp moät ñieåm trôû thaønh lai chuaån. Tuy nhieân, khoâng gioáng lai chuaån – tìm kieám mang tính cuïc boä trong khoâng gian lôùn – lai moät ñieåm tìm kieám cuïc boä trong khoâng gian caùc caáu truùc coá ñònh – khoâng gian naøy laø keát quûa cuûa quùa trình hoäi tuï daàn veà maët caáu truùc töø treân xuoáng döôùi trong quùa trình chuyeån töø tìm kieám toaøn cuïc sang tìm kieám cuïc boä. 8Luùc naøy, quaàn theå goàm nhieàu caù theå coù vaät lieäu di truyeàn gioáng nhau, do ñoù tìm kieám mang tính chaát raát cuïc boä, noù coù khaû naêng tinh chænh vaø chæ ra lôøi giaûi toát nhaát. 3.2.2 Pheùp lai ñoàng nhaát Pheùp lai ñoàng nhaát (xem ví duï trong hình 6) goàm caùc böôùc: § Tìm caây lai tieàm taøng con chung cuûa cha vaø meï: (a) nuùt trong töông öùng vôùi hai nuùt ôû cha vaø meï coù chung soá ñoái (hoaëc truøng nhau trong tröôøng hôïp lai ngaët), (b) nuùt laù töông öùng vôùi hai nuùt con chung cuoái cuøng cuûa cha vaø meï. § con_1ß cha; con_2ß meï § Duyeät treân caây lai tieàm taøng: o if (Flip(pS)) then Hình 5: Pheùp lai moät ñieåm 9Hình 6: Pheùp lai ñoàng nhaát § traùo ñoåi hai nuùt töông öùng cuûa con_1 vaø con_2 neáu ñieåm lai laø nuùt trong (cuûa caây lai tieàm taøng), § traùo ñoåi hai caây con töông öùng cuûa con_1 vaø con_2 neáu ñieåm lai laø nuùt laù (cuûa caây lai tieàm taøng). Tính toaøn cuïc hoaëc cuïc boä cuûa tìm kieám ñöôïc ñieàu khieån baèng pS: o neáu pS quùa beù (gaàn 0): tìm kieám mang tính cuïc boä, löôïng vaät chaát di truyeàn traùo ñoåi ít, o neáu pS quùa lôùn (gaàn 1): taát caû ñeàu bò traùo ñoåi, nhöng do tính ñoái xöùng, thöïc chaát chaúng coù traùo ñoåi naøo: tìm kieám mang tính cuïc boä, o neáu pS = 0.5: löôïng vaät chaát traùo ñoåi nhieàu nhaát: tìm kieám mang tính toaøn cuïc. 10 Neáu quaàn theå ban ñaàu ñuû ña daïng, trong giai ñoaïn ñaàu cuûa tieán hoùa, lai ñoàng nhaát chæ traùo ñoåi caùc nuùt vaø caùc caây con (coù kích thöôùc lôùn) gaàn goác. Qua moät thôøi gian tieán hoùa, khi phaàn treân ñaõ baét ñaàu hoäi tuï, töông töï nhö lai moät ñieåm, lai ñoàng nhaát seõ baét traùo ñoåi caùc nuùt vaø caây con (nhoû hôn) ôû caùc möùc thaáp hôn. Ñeán cuoái tieán hoùa, moïi nuùt cuûa caây ñeàu coù theå ñöôïc choïn lai gheùp, nhöng lai gheùp chæ laø traùo ñoåi caùc nuùt ñôn cuûa caây (caùc caây con töông öùng ôû cha vaø meï ôû caùc nuùt laù cuûa caây lai tieàm taøng chæ chöùa moät nuùt ñôn – laø nuùt laù ñoù). Tìm kieám luùc naøy mang tính cuïc boä, nhöng quaàn theå goàm nhieàu caù theå coù vaät lieäu di truyeàn gioáng nhau, do ñoù tìm kieám mang tính chaát raát cuïc boä, noù coù khaû naêng tinh chænh vaø chæ ra lôøi giaûi toát nhaát. 3.3 Aùp duïng chieán löôïc ñoäng vaøo pheùp lai chuaån ÔÛ ñaây, ta aùp duïng chieán löôïc ñoäng [4] vaøo pheùp lai chuaån (pheùp lai chuaån ñoäng) nhö sau: giai ñoaïn ñaàu choïn caùc ñieåm lai ôû gaàn goác vôùi xaùc suaát lôùn (caùc ñieåm lai xa goác vôùi xaùc suaát beù), giai ñoaïn sau choïn caùc ñieåm lai ôû gaàn caùc nuùt laù vôùi xaùc suaát lôùn (caùc ñieåm lai ôû gaàn goác vôùi xaùc suaát beù). Ñeå choïn ñieåm lai treân caù theå c (cha hoaëc meï) ôû theá heä thöù t trong quùa trình tieán hoùa T theá heä, ta xaùc ñònh tam giaùc )(tcD chöùa caùc nuùt coù ñoä saâu 0, 1, .., lim_depth(t, c) vôùi )2)((*)1(),(lim_ --= chigh T tctdepth . (6) Xaùc suaát choïn ñieåm lai trong )(tcD laø endbegendbeg T tendttrongp ³--+= ),(*)1()(_ . (7) )(_ ttrongp c m )(tcD )(tmD Hình 7: Minh hoïa pheùp lai chuaån ñoäng giöõa cha c vaø meï m 11 4. Chöông trình vaø keát quûa thöû nghieäm 4.1 Chöông trình thöû nghieäm Chöông trình thöû nghieäm ñöôïc vieát treân .NET 2003 vôùi giao dieän nhö sau: 4.2 Thöû nghieäm Aùp duïng moâ hình GP treân vôùi pheùp lai chuaån ñeå xaáp xæ 7 haøm moät bieán thöïc (cho trong baûng 1; caùc haøm 3, 4, 5, 6 ñöôïc choïn töø [1], caùc haøm 1, 2, 7 laø caùc haøm ña thöùc phoå bieán trong caùc taøi lieäu veà SR; ñoà thò caùc haøm cho trong hình 8). Thöû nghieäm 1: chaïy 5 laàn vôùi sieâu haït gioáng 8000, kích thöôùc quaàn theå 100, soá theá heä 100. Thöû nghieäm 2: chaïy 10 laàn vôùi sieâu haït gioáng 2000, kích thöôùc quaàn theå 150, soá theá heä 100. Loãi (%) trung bình, min, max, phöông sai cho trong baûng 2. Hieäu quûa cuûa pheùp lai chuaån vaø pheùp lai chuaån ñoäng ñöôïc so saùnh treân 6 thöû nghieäm vôùi: cuøng moâ hình aùp duïng GP (pheùp lai chuaån ñoäng vôùi beg = 0.7, end = 0.0), xaáp xæ caùc haøm 4 vaø 7 (baûng 1), soá theá heä 100, kích thöôùc quaàn theå 50. Loãi (%) trung bình, phöông sai, thôøi gian cuûa caùc thöû nghieäm cho trong baûng 3 (vôùi caùc kyù hieäu: pheùp lai chuaån: LC, pheùp lai chuaån ñoäng: LC_D). 12 12 246 ++- xxx12 ++ xx 1)1)cos()()(sinsin()cos( 23 +-- - xxxxex x 1)2sin(3.0 +xx p 1)log( +x 1+x 12 35 ++- xxx Hình 8: Moät soá daïng haøm thöû nghieäm 13 Baûng 1: Tham soá cuûa caùc haøm thöû nghieäm STT Haøm Mieàn trò Soá ñieåm 1 12 ++ xx [-1, 1] 50 2 12 246 ++- xxx [-1, 1] 50 3 1)2sin(3.0 +xx p [-1, 1] 100 4 1)1)cos()()(sinsin()cos( 23 +-- - xxxxex x [-1, 1] 100 5 1)log( +x [1, 10] 50 6 1+x [1, 10] 50 7 12 35 ++- xxx [-1, 1] 50 Baûng 2: Keát quûa cuûa 2 thöû nghieäm aùp duïng GP xaáp xæ 7 haøm moät bieán thöïc Thöû nghieäm 1 Thöû nghieäm 2 STT Trung bình Min Max Phöông sai Trung bình Min Max Phöông sai 1 3.7 0.8 6.9 1.1 2.8 0.6 8.9 1.5 2 2.2 0.5 3.6 1.0 1.6 0.4 3.6 0.8 3 4.6 3.5 6.3 1.0 4.0 3.0 5.8 0.8 4 8.0 3.1 21.2 2.2 4.1 1.1 9.3 1.2 5 0.4 0.0 0.9 0.6 0.1 0.0 0.4 0.3 6 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 7 2.8 2.14 4.7 0.8 3.9 0.3 8.3 1.4 Toång hôïp 3.1 0 21.2 1.0 2.3 0.0 9.3 0.9 Baûng 3: Keát quûa 6 thöû nghieäm so saùnh pheùp lai chuaån vaø pheùp lai chuaån ñoäng ([0.7, 0.0]) Sieâu haït gioáng 250 1000 4000 5000 7000 8000 Soá laàn 150 100 60 100 70 70 Trung bình 550 laàn So saùnh (%) 14 LC 10.17 13.77 13.79 12.41 9.51 12.48 11.83 100Trung bình LC_D 9.62 12.40 13.17 10.54 9.01 11.98 10.9 92 LC 2.19 2.53 2.46 2.45 2.09 2.42 2.34 100Phöông sai LC_D 2.14 2.30 2.40 2.14 2.02 2.27 2.19 94 LC 7h53 5h46 3h21 5h38 3h28 3h50 5h31 100Thôøi gian LC_D 7h14 5h34 3h10 5h24 3h25 3h50 5h14 95 Töø baûng 2 vaø baûng 3, ta coù nhaän xeùt: 1) GP coù theå giaûi hieäu quûa baøi toaùn xaáp xæ haøm moät bieán thöïc vôùi loãi beù (2.3%). 2) Pheùp lai chuaån ñoäng toát hôn pheùp lai chuaån: ñoä chính xaùc cao hôn (loãi giaûm 8%) vaø oån ñònh hôn (phöông sai beù hôn 6%) trong khoaûng thôøi gian ít hôn (5%). 5. Caùc vaán ñeà caàn nghieân cöùu theâm a) Caùc pheùp lai: moät ñieåm, lai ñoàng nhaát; caùc pheùp ñoät bieán: ñieåm, traùo ñoåi hai caây con cuûa chính noù; ñoät bieán ñoäng. b) Toái öu caùc heä soá baèng kyõ thuaät giaûm gradient, hoài quy tuyeán tính. c) Caùc phöông phaùp haïn cheá söï phaùt trieån ñoä saâu: parsimony pressure (ñoä cao caù theå laø moät cô sôû ñeå ñaùnh giaù ñoä toát cuûa caù theå), double tournament (hai löôït choïn, moät löôït döïa vaøo ñoä cao vaø moät löôït döïa vaøo ñoä toát). TAØI LIEÄU THAM KHAÛO [1] M. Keijzer, “Improving Symbolic Regression with Interval Arithmetic and Linear Scaling”, Computer Science Department, Free University Amsterdam. [2] R. Poli, W.B. Langdon, “Genetic Programming with One-Point Crossover and Point Mutation”, School of Computer Science, The University of Birmingham (UK). [3] R. Poli, W.B. Langdon, “On the Search Properties of Different Crossover Operators in Genetic Programming”, School of Computer Science, The University of Birmingham (UK). [4] T.C. Tin, “ÖÙng duïng chieán löôïc ñoäng trong thuaät giaûi di truyeàn giaûi moät soá baøi toaùn toái öu toaøn cuïc”, Hoäi thaûo quoác gia CNTT, Ñaø Laït, 2006. [5] M. Walker, “Introduction to Genetic Programming”, October 7, 2001.