Luận văn Kỹ thuật mạng nơron và giải thuật di truyền trong khai phá dữ liệu và thử nghiệm ứng dụng

Þ HiÒn Thanh – CNTT 2006 65 §Õn ®©y ta cã thÓ thÊy ®é nhËy c¶m ®†îc lan truyÒn ng†îc qua m¹ng tõ líp cuèi cïng trë vÒ líp ®Çu tiªn: sMosM - 1o......(s1. CÇn nhÊn m¹nh r»ng ë ®©y thuËt to¸n lan truyÒn ng†îc lçi sö dông cïng mét kü thuËt gi¶m theo h†íng nh† thuËt to¸n LMS. Sù phøc t¹p duy nhÊt ë chç ®Ó tÝnh gradient cÇn ph¶i lan truyÒn ng†îc ®é nhËy c¶m tõ c¸c líp sau vÒ c¸c líp tr†íc nh† ®· nªu trªn. B©y giê cÇn ph¶i biÕt ®iÓm b¾t ®Çu lan truyÒn ng†îc, xÐt ®é nhËy c¶m sM t¹i líp cuèi cïng:          M i i iiM i S l ll M i T M i M i n aat n at n atat n Fs M w w  w w w w w w ¦ š 21 2 Bëi v×:    Mi M M i M i M M i M i M i i nf n nf n a n a x w w w w w w nªn ta cã thÓ viÕt:    Mi M ii M i nfats x  2 ë d¹ng ma trËn sÏ lμ:   atnFs  x M M M 2 . Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 66 Tãm l¹i, thuËt to¸n lan truyÒn ng†îc cã thÓ ph¸t biÓu nh† sau: b. Sö dông gi¶i thuËt Trªn ®©y lμ gi¶i thuËt BP d¹ng tæng qu¸t. PhÇn tiÕp theo sÏ tr×nh bμy c¸c vÊn ®Ò vÒ khÝa c¹nh øng dông cña gi¶i thuËt BP trong viÖc huÊn luyÖn m¹ng n¬ ron truyÒn th¼ng nhiÒu líp, nh† chän lùa cÊu tróc m¹ng, c¸c hμm kÝch ho¹t, c¸c hμm gi¸, khëi ®éng c¸c träng sè ban ®Çu, tËp mÉu häc, sù héi tô… Chän lùa cÊu tróc m¹ng VÊn ®Ò ®Çu tiªn cÇn quan t©m lμ lùa chän cÊu tróc m¹ng. Nh† ®· tr×nh bμy ë phÇn 3.1.1, m¹ng n¬ ron truyÒn th¼ng nhiÒu líp lu«n cã mét líp vμo vμ mét líp ra, sè líp Èn cã thÓ tõ 0 ®Õn vμi líp. §èi víi mét bμi to¸n cô thÓ, sè n¬ ron trªn líp vμo cè ®Þnh b»ng sè biÕn cña vÐc t¬ vμo, sè n¬ ron trªn líp ra cè ®Þnh b»ng sè biÕn cña vÐc t¬ ®Ých. V× vËy, vÊn ®Ò thiÕt kÕ cÊu tróc m¹ng lμ vÊn ®Ò chän sè líp Èn vμ sè n¬ ron trªn mçi líp Èn Sè líp Èn B»ng thùc nghiÖm ®· chøng minh r»ng ®èi víi phÇn lín c¸c bμi to¸n trong thùc tÕ, chØ cÇn sö dông mét líp Èn cho m¹ng [12]. Bëi v×: Bɉ͛c 1: Lan truyɾn xuôi ÿɤu vào qua mɞng: a0 = p am+1 = fm+1 (Wm+1 am + bm+1) v͛i m = 0, 1, ..., M – 1. a = aM Bɉ͛c 2: Lan truyɾn ÿ͙ nhɪy cɠm (l͗i) ngɉͣc lɞi qua mɞng:   atnFs  x M M M 2    .11 x mTmm m m sWnFs v
i m = M – 1, ..., 2, 1. Bɉ͛c 3: Cu͑i cùng, các tr͍ng s͑ và ÿ͙ lʄch ÿɉͣc cɪp nhɪt b͟i công thͩc sau:     mmm Tmmmm kk kk sbb asWW D D      1 1 1 . Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 67 1) PhÇn lín c¸c thuËt to¸n huÊn luyÖn cho c¸c m¹ng n¬ron truyÒn th¼ng nhiÒu líp dùa trªn ph†¬ng ph¸p gi¶m gradient. C¸c líp thªm vμo sÏ thªm viÖc lan truyÒn c¸c lçi lμm cho vÐc t¬ gradient rÊt kh«ng æn ®Þnh, mμ sù thμnh c«ng cña bÊt kú mét thuËt to¸n tèi †u theo gradient phô thuéc vμo ®é kh«ng thay ®æi cña h†íng khi mμ c¸c tham sè thay ®æi. 2) Sè c¸c cùc trÞ ®Þa ph†¬ng t¨ng lªn rÊt lín khi cã nhiÒu líp Èn. PhÇn lín c¸c thuËt to¸n tèi †u dùa trªn gradient chØ cã thÓ t×m ra c¸c cùc trÞ ®Þa ph†¬ng, do vËy chóng kh«ng thÓ t×m ra cùc trÞ toμn côc. MÆc dï thuËt to¸n luyÖn m¹ng cã thÓ t×m ra cùc trÞ toμn côc, nh†ng x¸c suÊt bÞ t¾c trong mét cùc trÞ ®Þa ph†¬ng lμ kh¸ cao, vμ khi ®ã, ta ph¶i b¾t ®Çu luyÖn m¹ng l¹i. 3) Cã thÓ ®èi víi mét bμi to¸n cô thÓ, sö dông nhiÒu h¬n mét líp Èn víi chØ mét vμi n¬ ron th× tèt h¬n lμ sö dông Ýt líp Èn víi sè n¬ ron lμ lín, ®Æc biÖt ®èi víi c¸c m¹ng cÇn ph¶i häc c¸c hμm kh«ng liªn tôc. VÒ tæng thÓ, ng†êi ta khuyªn r»ng nªn xem xÐt kh¶ n¨ng sö dông m¹ng cã mét líp Èn ®Çu tiªn trong khi thiÕt kÕ c¸c m¹ng truyÒn th¼ng trong thùc tÕ. NÕu dïng mét líp Èn víi mét sè l†îng lín c¸c n¬ ron mμ kh«ng cã hiÖu qu¶ th× nªn sö dông thªm mét líp Èn víi mét sè Ýt c¸c n¬ ron. Tãm l¹i, m¹ng n¬ ron truyÒn th¼ng th†êng sö dông mét líp Èn ®Ó gi¶i quyÕt c¸c bμi to¸n trong thùc tÕ. VÊn ®Ò thiÕt cÊu tróc m¹ng quy vÒ viÖc t×m ra sè n¬ ron trong líp Èn. Sè n¬ ron trong líp Èn M¹ng n¬ ron truyÒn th¼ng cã kh¶ n¨ng tæng qu¸t hãa tõ nh÷ng d÷ liÖu mμ nã ®· häc, nãi c¸ch kh¸c, m¹ng n¬ ron truyÒn th¼ng cã kh¶ n¨ng dù b¸o tèt. Kh¶ n¨ng dù b¸o phô thuéc nhiÒu vμo sè n¬ ron trong líp Èn, hay phô thuéc nhiÒu vμo sè l†îng c¸c träng sè cña m¹ng. Mét m¹ng cã sè l†îng c¸c träng sè lín víi mét sè l†îng nhá c¸c mÉu häc cã thÓ häc rÊt tèt, song viÖc dù b¸o cã thÓ kh«ng tèt, hiÖn t†îng nμy th†êng gäi lμ häc qu¸ (overfiting). Nãi c¸ch kh¸c, khi sè l†îng träng sè lín h¬n sè mÉu häc, kÕt qu¶ luyÖn tham sè kh«ng ph¶n ¸nh ®óng ho¹t ®éng cña m¹ng. §Ó tr¸nh tr†êng hîp häc Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 68 qu¸, sè träng sè trong c¸c m¹ng n¬ ron ph¶i nhá h¬n hoÆc t†¬ng ®†¬ng víi sè mÉu cã trong tËp mÉu [12]. NÕu sè l†îng c¸c träng sè qu¸ nhá, m¹ng n¬ ron cã thÓ kh«ng nhËn d¹ng ®†îc ®Çy ®ñ c¸c tÝn hiÖu trong mét tËp d÷ liÖu phøc t¹p, cßn gäi lμ hiÖn t†îng thiÕu ¨n khíp (underfitting) Sè l†îng tèt nhÊt cña c¸c n¬ ron Èn phô thuéc vμo rÊt nhiÒu yÕu tè, ®ã lμ sè ®Çu vμo, sè ®Çu ra cña m¹ng, sè c¸c mÉu kh¸c nhau trong tËp mÉu, ®é nhiÔu cña d÷ liÖu ®Ých, ®é phøc t¹p cña hμm lçi, kiÕn tróc m¹ng, vμ thuËt to¸n huÊn luyÖn m¹ng… Cã rÊt nhiÒu “luËt” ®Ó lùa chän sè n¬ ron trong c¸c líp Èn [6, 12]: x ],[ nlm - n»m gi÷a kho¶ng kÝch th†íc líp vμo, líp ra x 3 )(2 nlm  - 2/3 tæng kÝch th†íc líp vμo vμ líp ra x lm 2 - nhá h¬n 2 lÇn kÝch th†íc líp vμo x nlm ˜ - c¨n bËc hai cña tÝch kich th†íc líp vμo, líp ra. C¸c luËt nμy chØ mang tÝnh lý thuyÕt mμ kh«ng ph¶n ¸nh ®†îc thùc tÕ bëi v×, chóng chØ xem xÐt ®Õn nh©n tè kÝch th†íc ®Çu vμo, ®Çu ra mμ bá qua c¸c nh©n tè quan träng kh¸c nh† sè l†îng mÉu ®†a vμo huÊn luyÖn, ®é nhiÔu ë c¸c ®Çu ra, ®é phøc t¹p cña hμm lçi … C¸c hμm kÝch ho¹t C¸c hμm kÝch ho¹t cña líp Èn dïng trong m¹ng n¬ ron truyÒn th¼ng nhiÒu líp th«ng dông nhÊt lμ hμm sigmoid . Ngoμi ra, mét sè hμm kÝch ho¹t ë b¶ng d†íi ®©y cã tÝnh chÊt t†¬ng tù nh† hμm sigmoid cã thÓ ®†îc sö dông: Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 69 f(x) f’(x) f’(f(x)) xe 1 1 x x e e     1 1 x x 1 xe1  21 x x e e      21 2 x x e e     21 1 x xe  f(x)(1-f(x)) 1 - (f(x))2 (1 - f(x))2 1 - f(x) B¶ng 3.1. C¸c hμm kÝch ho¹t §èi víi líp ra, c¸c hμm kÝch ho¹t ph¶i ®†îc chän sao cho phï hîp víi sù ph©n phèi cña c¸c gi¸ trÞ ®Ých mong muèn. Ta thÊy r»ng, ®èi víi c¸c gi¸ trÞ ®Ých trong kho¶ng [0,1], hμm sigmoid lμ cã Ých, ®èi víi c¸c gi¸ trÞ ®Ých mong muèn liªn tôc trong kho¶ng ®ã th× hμm nμy vÉn cã nghÜa. Nh†ng nÕu gi¸ trÞ ®Ých kh«ng biÕt tr†íc kho¶ng x¸c ®Þnh th× hμm hay ®†îc sö dông nhÊt lμ hμm tuyÕn tÝnh (xem phÇn 1.2 ch†¬ng 1). NÕu gi¸ trÞ ®Ých mong muèn lμ d†¬ng nh†ng kh«ng biÕt cËn trªn th× mét hμm kÝch ho¹t d¹ng mò cã thÓ ®†îc sö dông. C¸c hμm gi¸ Hμm gi¸ b×nh ph†¬ng ®†îc ®Þnh nghÜa theo ph†¬ng tr×nh 3.1 kh«ng ph¶i lμ sù lùa chän duy nhÊt cã thÓ. Sè h¹ng b×nh ph†¬ng sai sè  2lastjkjk Outy  cã thÓ ®†îc thay thÕ b»ng bÊt cø hμm cã kh¶ n¨ng ®¹o hμm nμo kh¸c F(yik, outjk), víi ®iÒu kiÖn lμ c¸c hμm nμy sÏ ®¹t cùc tiÓu khi hai ®èi sè yik vμ outjk b»ng nhau. Dùa vμo d¹ng cña hμm gi¸ míi cã thÓ thu nhËn ®†îc c¸c ph†¬ng tr×nh kh¸c nhau cho viÖc hiÖu chØnh c¸c träng sè. Mét ®iÒu dÔ nhËn thÊy lμ chØ cã ph†¬ng tr×nh hiÖu chØnh träng sè ë líp ra lμ thay ®æi theo c¸c d¹ng hμm gi¸ kh¸c nhau, trong khi ®ã c¸c ph†¬ng tr×nh kh¸c cña gi¶i thuËt BP vÉn gi÷ nguyªn. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 70 C¸c hμm gi¸ th†êng ®†îc sö dông lμ nh÷ng hμm dùa trªn chuÈn Lp (1d p d v) bëi sù lîi thÕ cña d¹ng ph†¬ng tr×nh to¸n häc ®¬n gi¶n. C¸c hμm nh† vËy cã d¹ng lμ: ¦  n k plast jkjk Outyp E 1 1 víi 1 d p d v (3.3) Tr†êng hîp hμm gi¸ ®Þnh nghÜa theo ph†¬ng tr×nh (3.1) lμ tr†êng hîp riªng víi p = 2 cña ph†¬ng tr×nh (3.2). Khëi ®éng c¸c träng sè ban ®Çu Gi¸ trÞ c¸c träng sè khëi t¹o ban ®Çu cña m¹ng khi ¸p dông gi¶i thuËt BP ¶nh h†ëng rÊt m¹nh tíi lêi gi¶i cuèi cïng. ViÖc khëi t¹o tÊt c¶ c¸c träng sè b»ng nhau sÏ lμm cho viÖc häc cña m¹ng trë nªn kh«ng tèt. C¸c träng sè khëi t¹o ban ®Çu cïng kh«ng ®†îc qu¸ lín v× ®iÒu nμy lμm cho hμm sigmoid hoÆc c¸c hμm d¹ng nμy sÏ bÞ b·o hßa (hoÆc b»ng 0, hoÆc b»ng 1) ngay tõ lóc b¾t ®Çu, lμm cho hÖ thèng bÞ t¾c t¹i mét cùc trÞ ®Þa ph†¬ng gÇn ®iÓm xuÊt ph¸t. Do vËy, c¸c träng sè ban ®Çu th†êng ®†îc khëi t¹o b»ng nh÷ng sè ngÉu nhiªn nhá. Gi¸ trÞ khëi ®éng ban ®Çu cña c¸c träng sè trªn líp thø nhÊt th†êng ®†îc chän ngÉu nhiªn trong kho¶ng [-1/n,1/n], trong ®ã n lμ tæng träng sè trªn líp thø nhÊt [12]. TËp mÉu häc TËp mÉu häc ph¶i ®ñ vμ ®óng. Tuy nhiªn, kh«ng cã mét thñ tôc hay mét nguyªn t¾c chän tËp mÉu häc phï hîp cho mäi tr†êng hîp. Mét nguyªn t¾c theo kinh nghiÖm lμ tËp mÉu häc ph¶i ®†îc chän sao cho chóng bao phñ toμn bé kh«ng gian cña tÝn hiÖu vμo. Trong qu¸ tr×nh häc, c¸c cÆp vÐc t¬ vμo - lêi gi¶i nªn ®†îc chän ngÉu nhiªn tõ tËp häc. C¸c tËp mÉu häc sö dông ®Ó huÊn luyÖn m¹ng ph¶i ®†îc tû lÖ hãa ®óng ®¾n, chi tiÕt vÒ viÖc tû lÖ hãa sÏ ®†îc ®Ò cËp trong ch†¬ng 4, phÇn tæ chøc sè liÖu. Sù héi tô Trong thuËt to¸n LMS, ®iÓm cùc trÞ toμn côc lμ lu«n tån t¹i bëi lÏ hμm trung b×nh b×nh ph†¬ng lçi cña LMS lμ mét hμm bËc hai, h¬n n÷a, do lμ hμm bËc hai nªn ®¹o hμm bËc hai cña hμm lçi sÏ lμ h»ng sè do vËy mμ ®é cong cña hμm theo mét Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 71 h†íng cho tr†íc lμ kh«ng thay ®æi. Trong khi ®ã, gi¶i thuËt BP ¸p dông cho c¸c m¹ng nhiÒu líp sö dông c¸c hμm chuyÓn phi tuyÕn sÏ cã nhiÒu ®iÓm cùc trÞ ®Þa ph†¬ng vμ ®é cong cña hμm lçi cã thÓ kh«ng cè ®Þnh theo mét h†íng cho tr†íc, viÖc thùc hiÖn thuËt to¸n cã thÓ ®†a m¹ng héi tô vÒ ®iÓm cùc trÞ ®Þa ph†¬ng, lμm cho m¹ng kh«ng tr¶ l¹i kÕt qu¶ chÝnh x¸c. Mét nh©n tè kh¸c ¶nh h†ëng tíi hiÖu lùc vμ ®é héi tô cña gi¶i thuËt lμ hÖ sè häc D. Kh«ng cã mét gi¸ trÞ duy nhÊt ®ñ tèt phï hîp víi tÊt c¶ c¸c bμi to¸n kh¸c nhau, hÖ sè häc nμy th†êng ®†îc chän b»ng thùc nghiÖm cho mçi bμi to¸n cô thÓ b»ng ph†¬ng ph¸p thö sai. Gi¸ trÞ D lín lμm t¨ng tèc ®é héi tô nh†ng kh«ng cã lîi v× thñ tôc häc sÏ kÕt thóc rÊt nhanh t¹i mét cùc trÞ ®Þa ph†¬ng gÇn nhÊt. NÕu gi¸ trÞ cña D qu¸ nhá, tèc ®é héi tô cña gi¶i thuËt l¹i trë nªn chËm. Do ®ã, cÇn chän mét gi¸ trÞ tho¶ hiÖp gi÷a tèc ®é häc vμ viÖc ng¨n chÆn héi tô vÒ c¸c cùc trÞ ®¹i ph†¬ng. C¸c gi¸ trÞ D n»m trong kho¶ng 10-3 vμ 10 ®· ®†îc sö dông thμnh c«ng cho rÊt nhiÒu bμi to¸n cô thÓ. Nãi chung, gi¸ trÞ h»ng sè häc n»m trong kho¶ng [0.3, 0.6] ®†îc chøng minh b»ng thùc nghiÖm lμ kh¸ tèt cho viÖc chän hÖ sè häc ban ®Çu. VÊn ®Ò n¶y sinh lμ gi¸ trÞ tèt cña hÖ sè häc t¹i thêi ®iÓm b¾t ®Çu cã thÓ lμ kh«ng tèt cho giai ®o¹n sau cña qu¸ tr×nh häc. Do ®ã, mét ph†¬ng ph¸p c¶i tiÕn lμ sö dông hÖ sè häc biÕn ®æi sÏ ®†îc tr×nh bμy ë phÇn tiÕp theo. 3.2.2. Mét sè c¶i tiÕn cña gi¶i thuËt BP B¶n chÊt cña gi¶i thuËt BP lμ gi¶i thuËt t×m kiÕm sö dông kü thuËt t×m kiÕm ng†îc h†íng gradient. MÆc dï dÔ thùc thi nh†ng gi¶i thuËt nμy béc lé mét sè nh†îc ®iÓm nh† sau: 1) T¹i c¸c vïng hoÆc mét sè h†íng mμ bÒ mÆt sai sè b»ng ph¼ng, c¸c gi¸ trÞ gradient nhá dÉn ®Õn tèc ®é héi tô cña gi¶i thuËt chËm [12]. 2) BÒ mÆt sai sè trong ®a sè c¸c bμi to¸n th†êng kh«ng “låi” mμ cã nhiÒu vïng “lâm” kh¸c nhau, nã phô thuéc vμo qu¸ tr×nh khëi t¹o c¸c träng sè ban ®Çu cña m¹ng, ®iÒu ®ã dÉn ®Õn gi¶i thuËt cã thÓ bÞ t¾c t¹i c¸c cùc trÞ ®Þa ph†¬ng (t¾c t¹i c¸c vïng “lâm”). Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 72 3) C¸c hμm kÝch ho¹t cña n¬ ron vμ hμm gi¸ tÝnh tÝn hiÖu sai sè ph¶i kh¶ vi [22]. §iÓu nμy lμ ®iÓm bÊt lîi trong c¸c øng dông sö dông c¸c hμm ng†ìng lμm hμm kÝch ho¹t do tÝnh kh«ng kh¶ vi cña chóng. 4) HiÖu n¨ng t×m kiÕm cña gi¶i thuËt phô thuéc vμo c¸c tham sè luyÖn nh† sè n¬ ron trªn líp Èn (tham sè cÊu tróc), gi¸ trÞ c¸c träng sè khëi t¹o ban ®Çu, h»ng sè häc D…ViÖc x¸c ®Þnh c¸c gi¸ trÞ cña chóng dÔ ®†a tíi t×nh thÕ tiÕn tho¸i l†ìng lan gi÷a tèc ®é héi tô vμ sù dao ®éng trong qu¸ tr×nh t×m kiÕm. Cã rÊt nhiÒu c¸c nghiªn cøu ®· ®Ò xuÊt c¸c c¶i tiÕn nh»m kh¾c phôc c¸c nh†îc ®iÓm trªn nh† sö dông tham sè b†íc ®μ, sö dông hÖ sè häc biÕn ®æi, sö dông gradient kÕt hîp, sö dông thuËt to¸n gi¶ luyÖn kim, sö dông gi¶i thuËt di truyÒn, ... LuËn v¨n nghiªn cøu gi¶i ph¸p tÝch hîp gi¶i thuËt GA víi gi¶i thuËt BP nh† mét gi¶i thuËt lai sö dông ®Ó huÊn luyÖn m¹ng n¬ ron. Do sö dông gi¶i ph¸p nμy mμ gi¶i thuËt BP sö dông trong gi¶i thuËt lai chØ sö dông ph†¬ng ph¸p c¶i tiÕn hÖ sè häc biÕn ®æi. Ph¬ng ph¸p sö dông hÖ sè häc biÕn ®æi Trong thùc tÕ, c¸c hμm hiÖu n¨ng cã d¹ng biÓu diÔn h×nh häc lμ kh«ng ®ång ®Òu, cã lóc cã d¹ng ph¼ng (hμm kh«ng thay ®æi gi¸ trÞ hoÆc thay ®æi rÊt Ýt) hoÆc cã d¹ng phÔu (gi¸ trÞ cña hμm thay ®æi rÊt nhanh khi thay ®æi tham sè ®Çu vμo). NÕu ta chØ sö dông hÖ sè häc cè ®Þnh th× cã thÓ sÏ tèn thêi gian t¹i c¸c vïng ph¼ng. V× vËy, ý t†ëng cña gi¶i thuËt BP sö dông hÖ sè häc biÕn ®æi lμ khi gÆp vïng ph¼ng th× t¨ng hÖ sè häc lªn vμ ng†îc l¹i khi gÆp vïng d¹ng phÔu th× gi¶m hÖ sè häc ®i. Ng†êi ta ®· ®†a ra rÊt nhiÒu ph†¬ng ph¸p ®Ó thùc hiÖn gi¶i ph¸p trªn, ë ®©y chØ xin nªu ra mét c¸ch biÕn ®æi hÖ sè häc dùa trªn hiÖu n¨ng cña m¹ng [8]: B†íc 1: NÕu b×nh ph†¬ng lçi trªn toμn bé tËp huÊn luyÖn t¨ng mét sè phÇn tr¨m cho tr†íc [ (th«ng th†êng lμ tõ 1% cho ®Õn 5%) sau mét lÇn cËp nhËt träng sè th× bá qua viÖc cËp nhËt nμy, hÖ sè häc ®†îc nh©n víi mét sè h¹ng U nμo ®ã (víi 0 < U < 1). B†íc 2: NÕu b×nh ph†¬ng lçi gi¶m sau mét lÇn cËp nhËt träng sè, th× cËp nhËt ®ã lμ chÊp nhËn ®†îc vμ hÖ sè häc ®†îc nhh©n víi mét sè h¹ng nμo ®ã > 1. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 73 B†íc 3: NÕu b×nh ph†¬ng lçi t¨ng mét l†îng < [ th× cËp nhËt träng sè lμ chÊp nhËn ®†îc nh†ng hÖ sè häc kh«ng thay ®æi. 3.3. KÕt hîp gi¶i thuËt di truyÒn víi gi¶i thuËt BP 3.3.1. Gi¶i thuËt di truyÒn trong viÖc huÊn luyÖn m¹ng n¬ron truyÒn th¼ng nhiÒu líp §Ó cã thÓ sö dông gi¶i thuËt GA trong thñ tôc huÊn luyÖn m¹ng (hiÖu chØnh c¸c träng sè cña m¹ng), cÇn ph¶i gi¶i quyÕt c¸c vÊn ®Ò vÒ x©y dùng hμm gi¸, m· ho¸ vμ gi¶i m· c¸c träng sè, khëi ®éng quÇn thÓ ®Çu tiªn, x¸c ®Þnh c¸c tham sè cña gi¶i thuËt GA. X©y dùng hμm gi¸ Gi¶i thuËt BP x©y dùng mét hμm gi¸ duy nhÊt (hμm gi¸ 3.2). §èi víi gi¶i thuËt GA, víi mét tËp häc cho tr†íc (Xs,ys) cÇn lan truyÒn lÇn l†ît c¸c vÐc t¬ vμo vμ tÝch luü c¸c sai sè l¹i thμnh mét sai sè tæng thÓ cho tËp häc ®ã:  ¦¦  p s n i last sisi OutywE 1 1 2 2 1)( (3.4) Trong ®ã: ysi lμ thμnh phÇn thø i cña ®Çu ra mong muèn outsilast lμ thμnh phÇn thø i cña ®Çu ra thùc tÕ Gi¶i thuËt GA sÏ t×m kiÕm tËp träng sè W trong kh«ng gian RM ®Ó tèi thiÓu hμm gi¸ 3.4. Mâ hãa vμ gi¶i mâ c¸c träng sè Nh† ®· ®Ò cËp ë ch†¬ng 2, c¸c to¸n tö cña gi¶i thuËt GA ho¹t ®éng ë møc cuèi ®èi víi c¸c bÝt. Do ®ã, mét tËp c¸c träng sè cña mét cÊu tróc m¹ng ph¶i ®†îc m· hãa thμnh mét chuçi. §èi víi mét cÊu tróc m¹ng cho tr†íc, c¸c träng sè ®†îc s¾p xÕp thμnh mét danh s¸ch. H×nh 3.3 lμ mét vÝ dô vÒ viÖc s¾p xÕp nh† vËy. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 74 H×nh 3.3: S¬ ®å m· hãa c¸c träng sè cña m¹ng n¬ ron (0.1, 2.7, -0.2, 0.1, -3, 0.5, -1.5, 0.9, -0.7) Gi¶ sö cã mét m¹ng n¬ ron truyÒn th¼ng víi L líp, m vμ n lÇn l†ît lμ sè n¬ ron trªn líp vμo vμ líp ra. Träng sè wlji thø i cña n¬ ron thø j trªn líp l sÏ chiÕm vÞ trÝ thø k trong danh s¸ch theo c«ng thøc sau:   > @ ilNjsNsNk l s »¼ º «¬ ª  ¦  1)1()1(1)1()( 1 1 (3.5) Danh s¸ch nμy sau ®ã ®†îc m· hãa tiÕp thμnh mét chuçi (mét c¸ thÓ). Do ®ã mét chuçi m« t¶ mét tËp c¸c träng sè. Chó ý r»ng, tÊt c¶ c¸c chuçi trong quÇn thÓ ®Òu m« t¶ c¸c tËp träng sè cña cïng mét cÊu tróc m¹ng. Danh s¸ch ®†îc m· hãa thμnh chuçi nhÞ ph©n nh† sau: mçi träng sè ®†îc m· hãa thμnh mét chuçi con cã ®é dμi 20 bÝt víi gi¸ trÞ n»m trong kho¶ng [-10,10] ®Ó tr¸nh tr†êng hîp c¸c gi¸ trÞ ho¹t hãa cña c¸c n¬ ron bÞ b·o hßa [3]. C¸c chuçi con 20 bÝt cña c¸c träng sè ®†îc nèi víi nhau t¹o thμnh mét chuçi dμi. Chuçi dμi nμy ®¹i diÖn cho mét tËp träng sè cña mét cÊu tróc m¹ng. ViÖc gi¶i m· c¸c träng sè tõ mét chuçi dμi lμ viÖc c¾t chuçi dμi thμnh c¸c chuçi con 20 bÝt. Gi¶ sö gi¸ trÞ cña chuçi nhÞ ph©n con ®†îc c¾t ra lμ x, lóc nμy gi¸ trÞ cña träng sè t†¬ng øng víi chuçi con ®ã lμ 20*x/(220-1)-10. §Ó ®¸nh gi¸ søc khoÎ cña mét chuçi trong quÇn thÓ, gi¶i m· chuçi thμnh tËp träng sè cña m¹ng n¬ ron cã cÊu tróc ®· ®Þnh tr†íc . Sau ®ã, lan truyÒn toμn bé c¸c 0.1 0.1 2.7 -3-0.2 0.5 -1.5 0.9 -0.7 Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 75 mÉu cã trong tËp huÊn luyÖn, tÝnh gi¸ trÞ cña hμm gi¸ theo c«ng thøc 3.3. Nãi c¸ch kh¸c, m¹ng n¬ ron ®ãng vai trß nh† mét hμm ®Þnh gi¸ trong gi¶i thuËt GA. Khëi ®éng quÇn thÓ ®Çu tiªn C¸c träng sè cña c¸c c¸ thÓ trong quÇn thÓ ban ®Çu ®†îc chän ngÉu nhiªn trong kho¶ng [-10, 10]. C¸c träng sè nμy ®†îc khëi ®éng ngÉu nhiªn víi x¸c suÊt cho bëi ph©n bè e-x . X¸c suÊt nμy ®†îc rót ra tõ c¸c quan s¸t trong thùc nghiÖm lμ lêi gi¶i tèi †u cã phÇn lín c¸c träng sè víi gi¸ trÞ tuyÖt ®èi nhá vμ ®ång thêi chóng còng cã sè Ýt c¸c träng sè cã gi¸ trÞ tuyÖt ®èi lín. Do ®ã, viÖc khëi ®éng c¸c träng sè sö dông ph©n bè x¸c suÊt nμy cho phÐp gi¶i thuËt GA th¨m dß c¸c kho¶ng chøa tÊt c¶ c¸c lêi gi¶i cã thÓ, ®ång thêi nã h†íng gi¶i thuËt vμo nh÷ng vïng hay chøa lêi gi¶i nhÊt. C¸c tham sè cña gi¶i thuËt di truyÒn C¸c tham sè cña gi¶i thuËt GA nh† x¸c suÊt t¹p lai, x¸c suÊt ®ét biÕn, sè c¸ thÓ trong quÇn thÓ vμ sè thÕ hÖ ®†îc chän theo ph†¬ng ph¸p thö vμ sai. C¸c gi¸ trÞ pcross=0.7, pmutation=0.001 ®†îc coi lμ c¸c gi¸ trÞ xuÊt ph¸t kh¸ tèt. NÕu gi¸ trÞ pmutation lín, gi¶i thuËt GA trë thμnh gi¶i thuËt t×m kiÕm ngÉu nhiªn. Sè c¸ thÓ trong quÇn thÓ th†êng ®†îc chän cì trung b×nh tõ 100 ®Õn 200 c¸ thÓ cho mét quÇn thÓ. Sè thÕ hÖ cÇn thiÕt theo thùc nghiÖm cì 5 ®Õn 10 lÇn tæng sè träng sè cã trong m¹ng. 3.3.2. GhÐp nèi víi gi¶i thuËt lan truyÒn ngîc sai sè Gi¶i thuËt GA cã thÓ t×m ra vïng chøa cùc trÞ toμn côc, song nã kh«ng cã kh¶ n¨ng leo lªn ®Ønh cña cùc trÞ ®ã. Nãi c¸ch kh¸c, gi¶i thuËt GA kh«ng b¶o ®¶m sù héi tô. Tr¸i l¹i, gi¶i thuËt BP ®¶m b¶o cho sù héi tô nh†ng kh«ng cã kh¶ n¨ng t×m kiÕm cùc trÞ toμn côc. Do ®ã, viÖc kÕt hîp hai gi¶i thuËt trªn trong mét gi¶i thuËt lai lμ lÏ tù nhiªn. §èi víi mét cÊu tróc m¹ng cho tr†íc, xuÊt ph¸t b»ng gi¶i thuËt GA víi viÖc khëi ®éng mét quÇn thÓ ban ®Çu gåm N chuçi nhÞ ph©n (N c¸ thÓ). Mçi chuçi lμ mét b¶n m· nhÞ ph©n cña mét tËp träng sè cña mét cÊu tróc m¹ng ®· cho. Gi¶i thuËt GA tiÕn hμnh tiÕn hãa quÇn thÓ ban ®Çu b»ng c¸ch sö dông c¸c to¸n tö chän läc, lai ghÐp vμ ®ét biÕn. Sau G thÕ hÖ, 5% c¸ thÓ tèt nhÊt trong G ®†îc l†u tr÷ l¹i. Nh† vËy, ®Çu vμo cña gi¶i thuËt GA lμ mét cÊu tróc m¹ng vμ tËp huÊn luyÖn, ®Çu ra lμ 0.05*N tËp Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 76 träng sè. C¸c tËp träng sè nμy lÇn l†ît ®†îc gi¶i thuËt BP luyÖn ®Õn b·o hßa. KÕt qu¶ cña qu¸ tr×nh luyÖn b»ng gi¶i thuËt BP lμ 0.05*N tËp träng sè míi. TËp träng sè cho kÕt qu¶ tèt nhÊt (gi¸ trÞ hμm gi¸ nhá nhÊt) trong 0.05*N tËp träng sè nμy ®†îc gi÷ l¹i lμ kÕt qu¶ cña gi¶i thuËt lai GA - BP. Gi¶i thuËt BP trong gi¶i thuËt lai nμy lμ gi¶i thuËt BP ®· tr×nh bμy ë phÇn 3.1 víi: x C¸c gi¸ trÞ träng sè ban ®Çu kh«ng cÇn ph¶i khëi ®éng mμ tiÕp nhËn tËp träng sè lμ kÕt qu¶ tõ gi¶i thuËt GA nh† tËp träng sè ban ®Çu. x Gi¶i thuËt BP sö dông h»ng sè häc biÕn ®æi ®Ó ®¶m b¶o gi¸ trÞ cña c¸c hμm gi¸ 3.3 lu«n gi¶m. Nãi mét c¸ch kh¸c, lμm t¨ng tèc ®é héi tô cña gi¶i thuËt. H×nh 3.4 lμ s¬ ®å khèi tæng thÓ cña gi¶i thuËt lai GA - BP. Gi¶i thuËt lai nμy ®†îc dïng trong thñ tôc huÊn luyÖn m¹ng n¬ ron truyÒn th¼ng nhiÒu líp. H×nh 3.4: S¬ ®å cña gi¶i thuËt lai ™ KÕt luËn ch¬ng 3 Ch†¬ng 3 m« t¶ gi¶i thuËt BP vμ c¸c vÊn ®Ò khi sö dông gi¶i thuËt BP trong huÊn luyÖn m¹ng n¬ron truyÒn th¼ng nhiÒu líp nh† lùa chon cÊu tróc m¹ng, hμm kÝch ho¹t, x©y dùng hμm gi¸, khëi t¹o tËp träng sè ban ®Çu, ... Ch†¬ng 3 còng tr×nh bÇy gi¶i ph¸p tÝch hîp gi¶i thuËt GA vμ BP thμnh mét gi¶i thuËt lai ®Ó häc tham sè cho m¹ng n¬ron. Mét cÊu tróc m¹ng Gi¶i thuËt GA 5% quÇn thÓ tèt nhÊt ®†îc l†u tr÷ Gi¶i thuËt BP Mét tËp träng sè Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 77 Cïng víi thùc tÕ m¹ng n¬ron ®†îc øng dông réng r·i trong lÜnh vùc dù b¸o d÷ liÖu, ®Æc biÖt lμ c¸c bμi to¸n dù b¸o tiªu thô n¨ng l†îng, dù b¸o kinh tÕ, dù b¸o c¸c hiÖn t†îng tù nhiªn.... Ch†¬ng 4 cña luËn v¨n sÏ thùc hiÖn cμi ®Æt thö nghiÖm ch†¬ng tr×nh dù b¸o lò trªn s«ng Trμ Khóc sö dông m¹ng n¬ ron truyÒn th¼ng huÊn luyÖn b»ng gi¶i thuËt lai GA – BP. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 78 Chn¬ng 4: øng dông trong bμi to¸n dù b¸o d÷ liÖu 4.1. giíi thiÖu bμi to¸n Dù b¸o ®Ønh lò trªn s«ng lμ mét trong nh÷ng bμi to¸n quan träng trong lÜnh vùc dù b¸o thuû v¨n, nã cã ý nghÜa to lín trong ®êi sèng x· héi v× nã gióp con ng†êi dù b¸o ®†îc c¸c trËn lò lín tr†íc mét thêi gian dμi, tr¸nh ®†îc thiÖt h¹i vÒ ng†êi vμ vËt chÊt do chóng g©y ra. Dßng ch¶y s«ng suèi ®†îc h×nh thμnh d†íi ¶nh h†ëng cña nhiÒu nh©n tè. Song trong sè ®ã næi lªn hai nh©n tè quan träng lμ l†îng m†a vμ l†îng tr÷ n†íc trªn l†u vùc s«ng. M†a lμ nh©n tè quyÕt ®Þnh ®é lín cña ®Ønh lò, tuy nhiªn, cïng mét l†îng m†a trªn cïng mét l†u vùc, vÉn cã thÓ sinh ra c¸c ®Ønh lò kh¸c nhau. VÝ dô, trªn s«ng Hång l†îng m†a sinh ra trËn lò lín nhÊt n¨m 1969 vμ 1996 t†¬ng øng lμ 250 vμ 300 mm, lín h¬n l†îng m†a g©y trËn lò th¸ng 8/1971 lμ 218 mm, song do l†îng tr÷ n†íc t¹i thêi ®iÓm tr†íc lò n¨m 1971 lín h¬n ®· lμm cho ®Ønh lò th¸ng 8/1971 lín h¬n nhiÒu so víi hai trËn lò kia. Nh† vËy, l†îng tr÷ n†íc tr†íc lò, hay gäi lμ ch©n lò, cã thÓ xem lμ nh©n tè quan träng thø hai, quyÕt ®Þnh ®é lín cña ®Ønh lò. Ngoμi ra cßn cã c¸c yÕu tè kh¸c t¸c ®éng ®Õn lò lôt nh† ®iÒu kiÖn thêi tiÕt… chóng chØ lμ c¸c nh©n tè gi¸n tiÕp. S«ng Trμ Khóc b¾t nguån tõ vïng rõng nói Gi¸ Vùc, phÝa t©y nam tØnh Qu¶ng Ng·i, ë vμo kho¶ng 14o34’30’’B vμ 108o25’20’’§. §é cao nguån s«ng kho¶ng 900 m, chiÒu dμi s«ng 135 km, chiÒu dμi l†u vùc 123 km, diÖn tÝch l†u vùc 3240 km2, ®é dèc l†u vùc 18,5%, chiÒu réng l†u vùc 26,3 km. Cã hai d¹ng lò trªn s«ng, lò ®¬n vμ lò kÐp. LuËn v¨n x©y dùng ch†¬ng tr×nh dù b¸o d÷ liÖu sö dông m¹ng n¬ ron truyÒn th¼ng huÊn luyÖn b»ng gi¶i thuËt lai GA - BP ®†îc thö nghiÖm víi bμi to¸n dù b¸o ®Ønh lò s«ng Trμ Khóc tr¹m S¬n Giang. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 79 Sè liÖu huÊn luyÖn m¹ng vμ kiÓm tra kh¶ n¨ng dù b¸o cña m¹ng ®†îc lÊy tõ Trung t©m Th«ng tin t† liÖu - Tæng côc KhÝ t†îng Thuû v¨n, lμ sè liÖu ®o ®†îc t¹i tr¹m S¬n Giang tõ n¨m 2001 ®Õn nay vμ ®†îc l†u tr÷ d†íi d¹ng sau: Thêi gian Mùc n†íc lò trung b×nh N¨m B¾t ®Çu KÕt thóc L†îng m†a trung b×nh Ch©n lò §Ønh lò 2001 2002 1h/6/10 1h/7/10 19h/9/10 7h/11/10 1h/9/11 7h/22/10 1h/12/9 7h/2/11 19h/17/10 1h/25/10 9h/28/10 11h/29/10 7h/16/11 1h/19/11 21h/19/11 7h/30/11 21h/30/11 7h/19/12 …………. 13h/6/10 13h/7/10 13h/10/10 13h/11/10 19h/10/11 7h/23/10 13h/12/9 1h/3/11 7h/18/10 13h/25/10 19h/28/10 11h/29/10 19h/16/11 7h/19/11 7h/20/11 19h/30/11 3h/1/12 3h/20/12 191.5 184.5 118.5 74.5 289 199 67 298 82 121.5 62 84.5 173.5 95.5 121 150.5 60 165.5 2831 3088 3041 3185 3025 2931 2820 3077 2955 3143 3159 3312 3112 3362 3433 3097 3519 3004 3352 3594 3414 3340 3717 3449 3084 4020 3203 3578 3382 3548 3643 3585 3615 3572 3710 3451 B¶ng 4.1: Sè liÖu thö nghiÖm cña bμi to¸n dù b¸o Trong ®ã: x N¨m: lμ n¨m lÊy mÉu sè liÖu, kh«ng tham gia vμo d÷ liÖu dù b¸o x Thêi gian: lμ kho¶ng thêi gian ®o sè liÖu, kh«ng tham gia vμo sè liÖu dù b¸o Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 80 x L†îng m†a trung b×nh: lμ l†îng m†a trung b×nh ®o ®†îc trong kho¶ng thêi gian trªn tÝnh b»ng mm, lμ mét ®Çu vμo cña d÷ liÖu dù b¸o x Mùc n†íc ch©n lò: lμ gi¸ trÞ mùc n†íc ch©n lò tÝnh b»ng cm, lμ ®Çu vμo thø hai cña d÷ liÖu dù b¸o x Mùc n†íc ®Ønh lò: lμ gi¸ trÞ mùc n†íc ®Ønh lò tÝnh b»ng cm, lμ gi¸ trÞ dù b¸o. 4.2. m« h×nh ho¸ bμi to¸n, thiÕt kÕ d÷ liÖu vμ gi¶i thuËt 4.2.1. M« h×nh ho¸ bμi to¸n TiÒn xö lý: Víi d÷ liÖu ®· cho, cã thÓ thiÕt lËp m« h×nh gåm cã ba hiÖu øng sau: x L†îng m†a trung b×nh: nhËn gi¸ trÞ thùc cña nã. x Mùc n†íc ch©n lò: nhËn gi¸ trÞ thùc cña nã. x Mùc n†íc ®Ønh lò: nhËn gi¸ trÞ thùc cña nã. TÊt c¶ c¸c d÷ liÖu ®†a vμo m¹ng sÏ ®†îc chuÈn hãa vÒ kho¶ng (0,1) theo c«ng thøc: SV = OV*(0.9-0.1) / (MAX – MIN) (4.1) trong ®ã: OV: Gi¸ trÞ tr†íc khi biÕn ®æi SV: Gi¸ trÞ sau khi biÕn ®æi (gi¸ trÞ ®†a vμo m¹ng) MAX, MIN: Gi¸ trÞ lín nhÊt vμ nhá nhÊt cña tËp gi¸ trÞ 0.9, 0.1: Gi¸ trÞ lín nhÊt vμ nhá nhÊt cña hμm sigmoid M« h×nh dù b¸o: Ta dïng c¸c ký hiÖu sau: X: L†îng m†a trung b×nh Hc: Mùc n†íc ch©n lò H®: Mùc n†íc ®Ønh lò Nh† vËy, m« h×nh dù b¸o mùc n†íc ®Ønh lò theo mùc n†íc ch©n lò vμ l†îng m†a trung b×nh ®†îc biÓu diÔn b»ng hμm sè: H® = f (Hc,X) (4.2) Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 81 Lùa chän kiÕn tróc m¹ng: M¹ng bao gåm mét líp ra vμ mét líp Èn. §Çu vμo cña m¹ng lμ l†îng m†a trung b×nh X vμ mùc n†íc ch©n lò Hc, ®Çu ra cña m¹ng lμ gi¸ trÞ dù b¸o mùc n†íc ®Ønh lò H® . M¹ng sÏ yªu cÇu sè n¬ ron trong líp Èn võa ®ñ ®Ó häc ®†îc c¸c ®Æc tr†ng tæng qu¸t vÒ mèi quan hÖ gi÷a ®Çu vμo vμ ®Çu ra. Môc tiªu lμ sö dông sè n¬ ron trong líp Èn cμng Ýt cμng tèt. Sè n¬ ron trong líp Èn ®†îc x¸c ®Þnh b»ng c¸ch huÊn luyÖn víi mét sè tËp kiÓm tra. Hμm kÝch ho¹t cña c¸c n¬ ron trong líp Èn lμ hμm sigmoid. Hμm kÝch ho¹t cña c¸c n¬ ron ë líp ra chän lμ hμm ®ång nhÊt. 4.2.2. ThiÕt kÕ d÷ liÖu Gi¶i thuËt di truyÒn C¸c to¸n tö cña gi¶i thuËt GA ho¹t ®éng ë møc chuçi nªn cÊu tróc d÷ liÖu c¬ b¶n lμ quÇn thÓ c¸c chuçi. Mét trong nh÷ng cÊu tróc d÷ liÖu sö dông lμ b¶ng hai chiÒu víi mçi hμng lμ mét c¸ thÓ vμ sè cét lμ ®é dμi cña mçi c¸ thÓ. Do ®é dμi cña mçi c¸ thÓ vμ sè c¸ thÓ th†êng xuyªn biÕn ®éng nªn b¶ng hai chiÒu ®†îc cÊp ph¸t ®éng. Hai quÇn thÓ cò vμ míi ®†îc ®Þnh nghÜa lμ hai con trá chØ ®Õn hai b¶ng hai chiÒu cã kÝch th†íc ®éng Oldpop( ) vμ NewPop( ). §ång thêi víi quÇn thÓ c¸c c¸ thÓ lμ hai vÐc t¬ ®†îc cÊp ph¸t ®éng cña c¸c sè thùc nh»m ghi nhËn gi¸ trÞ cña hμm môc tiªu t†¬ng øng víi c¸c c¸ thÓ vμ gi¸ trÞ søc kháe t†¬ng øng : Objective( ) vμ Fitness( ). C¸c biÕn Popsize ghi sè c¸ thÓ trong quÇn thÓ, Pcross ghi x¸c suÊt t¹p lai, Pmutation ghi x¸c suÊt ®ét biÕn, Gen ghi sè thÕ hÖ cÇn tiÕn hãa vμ ®é dμi chuçi lμ Lchrom. M¹ng n¬ ron M¹ng n¬ ron truyÒn th¼ng ®†îc cμi ®Æt lμ mét líp cã tªn gäi lμ Network, c¸c tham sè cña m¹ng lμ c¸c biÕn thμnh viªn; NumInputs, NumOutputs, NumNeurals t†¬ng øng lμ sè ®Çu vμo, sè ®Çu ra, sè n¬ ron trªn líp Èn, Inputs( ) vμ Expected_Outputs( ) lμ hai vÐc t¬ chøa ®Çu vμo vμ ®Çu ra mong muèn cña m¹ng, Layers( ) lμ vÐc t¬ cã kiÓu phÇn tö thuéc líp Layer chøa c¸c líp m¹ng. Líp Layer cã Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 82 biÕn thμnh viªn lμ hai vÐc t¬ Inputs( ), Outputs( ) vμ Output_Errors( ) chøa ®Çu vμo, ®Çu ra vμ sai sè ®Çu ra cña líp. §Ó tÝch hîp gi¶i thuËt GA víi gi¶i thuËt BP cÇn sö dông mét b¶ng hai chiÒu cÊp ph¸t ®éng GA_Weights( ) ®Ó l†u tr÷ c¸c träng sè cña m¹ng t¹i mçi thÕ hÖ tiÕn hãa, sè cét lμ sè träng sè cña m¹ng, sè hμng lμ sè c¸ thÓ trong quÇn thÓ. Mçi hμng cña b¶ng t†¬ng øng víi mét bé träng sè cña m¹ng, viÖc ®†a vμo m¹ng bé träng sè nμy ®†îc thùc hiÖn nhê thñ tôc GA_loadWeight( ) cña líp network. Ngoμi ra cßn sö dông b¶ng hai chiÒu cÊp ph¸t ®éng BP_weights( ) ®Ó l†u tr÷ 0.05*N bé träng sè kÕt qu¶ cña gi¶i thuËt GA sau Gen thÕ hÖ tiÕn hãa lμm ®Çu vμo cho gi¶i thuËt BP. Sè liÖu mÉu vμ tæ chøc sè liÖu: Sè liÖu thùc nghiÖm ®†îc tæ chøc trong mét tÖp sè liÖu. C¸c cÆp vÐc t¬ tÝn hiÖu vμo vμ tÝn hiÖu ra ®†îc viÕt trªn mét dßng. Do hμm biÕn ®æi dïng trong m¹ng lμ hμm sigmoid nªn c¸c sè liÖu nμy sÏ ®†îc ch†¬ng tr×nh tù ®éng tû lÖ hãa tuyÕn tÝnh trong kho¶ng [0.1, 0.9] theo c«ng thøc (4.1). TËp d÷ liÖu sau khi ®· ®†îc tû lÖ hãa nh† trªn ®†îc l†u tr÷ trong hai vÐc t¬ cÊp ph¸t ®éng Inputs( ) vμ Expected_outputs( ). 4.2.3. ThiÕt kÕ gi¶i thuËt S¬ ®å chÝnh cña ch†¬ng tr×nh nh† sau: x Vμo: - Tªn file chøa sè liÖu mÉu. - CÊu tróc m¹ng n¬ ron (m, n, a). - Sè thÕ hÖ cÇn tiÕn hãa Gen. x Ra: - TËp träng sè øng víi cÊu tróc m¹ng trªn. - Sai sè cña m¹ng trªn. x Gi¶i thuËt: - TiÒn xö lý sè liÖu b»ng viÖc tû lÖ hãa tËp huÊn luyÖn (Thñ tôc 1). - Häc tham sè b»ng gi¶i thuËt di truyÒn (Ph©n hÖ 1) Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 83 - L†u tr÷ 5% c¸ thÓ tèt nhÊt tõ quÇn thÓ cuèi cïng. - Häc tham sè b»ng gi¶i thuËt BP víi h»ng sè häc thÝch nghi cho tõng c¸ thÓ trong 5% c¸ thÓ tõ gi¶i thuËt di truyÒn chuyÓn sang (ph©n hÖ 2) - TËp träng sè cña c¸ thÓ tèt nhÊt sau giai ®o¹n häc b»ng gi¶i thuËt BP ®†îc gi÷ l¹i nh† kÕt qu¶ cña ch†¬ng tr×nh. Thñ tôc 1 x Chøc n¨ng: - Tû lÖ hãa tuyÕn tÝnh tËp huÊn luyÖn vμo kho¶ng [0.1, 0.9] x Vμo: - TËp mÉu huÊn luyÖn x Ra: - Gi¸ trÞ hai tËp con ®· ®†îc tû lÖ hãa Xtrain( ), Ytrain( ) víi Xtrain( ) lμ vÐc t¬ ®Çu vμo vμ Ytrain( ) lμ vÐc t¬ ®Çu ra mong muèn . - Sè l†îng mÉu cã trong tËp P. x Gi¶i thuËt: - X¸c ®Þnh sè l†îng mÉu cã trong tÖp P. - X¸c ®Þnh sè biÕn cña tÝn hiÖu vμo m vμ tÝn hiÖu ra n. - LÆp i = 1 ®Õn P LÆp j = 1 ®Õn m + n + Scale[j] = (0.9-0.1) / (max[j] - min[j]). + Xtrain[i,j] = (input[i,j] - min[j] )*Scale[j] + 0.1. + Ytrain[i,j] = (Target[i,j] - min[j] )*Scale[j] + 0.1 Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 84 Ph©n hÖ 1 x Chøc n¨ng: - Sö dông gi¶i thuËt di truyÒn ®Ó huÊn luyÖn (häc tham sè) m¹ng n¬ ron truyÒn th¼ng nhiÒu líp. x Vμo: - CÊu tróc m¹ng m, n, a. - TËp mÉu luyÖn. x Ra: - QuÇn thÓ c¸c c¸ thÓ cña thÕ hÖ cuèi cïng, mçi c¸ thÓ lμ mét bé träng sè cña m¹ng. x Gi¶i thuËt: - Khëi ®éng quÇn thÓ ®Çu tiªn (Thñ tôc 1.1) - LÆp i = 1 ®Õn Gen + §¸nh gi¸ søc kháe toμn quÇn thÓ (Ph©n hÖ 1.1) + TiÕn hãa tõ thÕ hÖ cò sang thÕ hÖ míi (ph©n hÖ 1.2) Thñ tôc 1.1 x Chøc n¨ng: - S¶n sinh mét b¶ng OldPop víi Popsize dßng lμ Popsize chuçi nhÞ ph©n, mçi chuçi lμ b¶ng m· cña mét tËp c¸c träng sè cña m¹ng. - C¸c träng sè ®†îc khëi t¹o ngÉu nhiªn trong kho¶ng [-10,10] tu©n theo x¸c suÊt e-|x|. x Vμo: - CÊu tróc m¹ng m, n, a. m, n, A, Tұp luyӋn Khӣi ÿӝng quҫn thӇ ÿҫu tiên (Thӫ tөc 1.1) i = 1 Ĉánh giá sӭc khӓe toàn quҫn thӇ (Phân hӋ 1.1) TiӃn hóa (phânhӋ 1.2) i < Gen i = i + Hình 4.1: S˯ d͛ kh͙i gi̫i thu̵t Phân h͏ 1 Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 85 - Sè l†îng chuçi nhÞ ph©n Popsize. x Ra: - QuÇn thÓ gåm Popsize chuçi nhÞ ph©n ®†îc l†u tr÷ trong b¶ng OldPop. x Gi¶i thuËt: - TÝnh tæng sè träng sè M trong m¹ng, sè träng sè trong m¹ng b»ng: M = (m + n) * a + n + a - LÆp i = 1 ®Õn Popsize LÆp j = 1 ®Õn M + Sinh sè ngÉu nhiªn p0 trong kho¶ng [0,1]. + TÝnh gi¸ trÞ x = ln (1- p0) + Sinh sè ngÉu nhiªn p1 + NÕu p1 < 0.5 th× x = -x + M· hãa gi¸ trÞ x thμnh chuçi nhÞ ph©n con 20 bÝt trong kho¶ng [-10,10]. + Nèi kÕt M chuçi nhÞ ph©n con thμnh mét chuçi lín, chÝnh lμ chuçi c¸ thÓ. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 86 Ph©n hÖ 1.1 x Chøc n¨ng: - §èi víi mçi chuçi c¸ thÓ trong quÇn thÓ OldPop gi¶i m· thμnh tËp träng sè, sau ®ã lan truyÒn toμn bé tËp luyÖn qua m¹ng, tÝch luü sai sè theo hμm gi¸ 3.3 ë ch†¬ng 3. - ChuyÓn ®æi gi¸ trÞ hμm gi¸ thμnh gi¸ trÞ søc kháe. x Vμo: - QuÇn thÓ OldPop. - TËp luyÖn. x Ra: - Gi¸ trÞ søc khoÎ toμn quÇn thÓ ®†îc chøa trong b¶ng Fitness( ). x Gi¶i thuËt - LÆp i = 1 ®Õn PopSize + Gi¶i m· chuçi thø i trong quÇn thÓ oldPop thμnh tËp träng sè W (Thñ tôc 1.1.1). + TÝnh gi¸ trÞ hμm gi¸ cho m¹ng n¬ ron cã tËp träng sè võa ®†îc gi¶i m· vμ l†u gi¸ trÞ ®ã vμo b¶ng obiective( ) (Thñ tôc 1.1.2). Hình 4.2: S˯ d͛ kh͙i gi̫i thu̵t Phân h͏ 1.1 i = 1 Giҧi mã chuӛi thӭ i thành tұp trӑng sӕ W (Thͯ tͭc 1.1.1) Tính giá trӏ hàm giá và lѭu vào bҧng Objective (Thͯ tͭc 1.1.2) i < Gen Ra i = i + 1 Tұp luyӋn Tính bҧng Fitness tӯ bҧng Objective (Thͯ tͭc 1.1.3) Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 87 - TÝnh b¶ng søc kháe Fitness( ) tõ b¶ng gi¸ trÞ hμm gi¸ objective( ) (Thñ tôc 1.1.3). Thñ tôc 1.1.1 x Chøc n¨ng: - Gi¶i m· chuçi nhÞ ph©n thμnh b¶ng tuyÕn tÝnh c¸c träng sè W x Vμo: - Chuçi nhÞ ph©n ®é dμi Lchrom - Tæng sè träng sè M x Ra: - B¶ng W( ) cña c¸c träng sè (sè thùc). x Gi¶i thuËt: - LÆp i =1 ®Õn M + C¾t liªn tiÕp mét chuçi con ®é dμi 20 bÝt tõ chuçi c¸ thÓ. + TÝnh gi¸ trÞ x cña chuçi nhÞ ph©n (x lμ sè nguyªn dμi) + Gi¸ trÞ W(i) = (20.x / (220 - 1)) – 10. Thñ tôc 1.1.2 x Chøc n¨ng: - TÝnh sai sè cho mét cÊu tróc m¹ng m, n, a vμ bé träng sè W víi mét tËp luyÖn cho tr†íc. x Vμo: - CÊu tróc m¹ng m, n, a vμ bé träng sè. - TËp sè liÖu huÊn luyÖn gåm P mÉu (hai vÐc t¬ vμo vμ ra X, y). x Ra: - Sai sè e sinh ra sau khi lan truyÒn toμn bé c¸c mÉu qua m¹ng. x Gi¶i thuËt - G¸n e = 0 - LÆp i = 1 ®Õn P + G¸n c¸c tÝn hiÖu ra cña c¸c bias = 1. + G¸n tÝn hiÖu ra ë líp vμo out0 b»ng tÝn hiÖu vμo X. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 88 + LÆp ®èi víi mäi n¬ ron thø j ë trªn líp Èn vμ líp ra TÝnh tæng tÝn hiÖu vμo theo c«ng thøc ¦ m i l i l ji l j xwNet 1 . TÝnh tÝn hiÖu ra  lj l j Net Out  exp1 1 + TÝch luü sai sè vμo e:  ¦  n j last j i j OutyEE 1 2 2 1 Thñ tôc 1.1.3 x Chøc n¨ng: - TÝnh b¶ng gi¸ trÞ søc kháe Fitness( ) cña quÇn thÓ oldPop tõ b¶ng gi¸ trÞ hμm gi¸ objective( ). x Vμo: - B¶ng gi¸ trÞ hμm gi¸ objective( ). - Sè c¸ thÓ trong quÇn thÓ PopSize. x Ra: - B¶ng gi¸ trÞ hμm søc kháe Fitness( ) x Gi¶i thuËt: - TÝnh gi¸ trÞ Max cña b¶ng gi¸ trÞ hμm gi¸ objective( ). - LÆp j = 1 ®Õn Popsize: Fitness[i] = Max – objective(i) - TÝnh gi¸ trÞ Max, gi¸ trÞ trung b×nh ave cña b¶ng Fitness. - NÕu Max > 2*ave th× a = ave / (Max - ave), b = (Max – 2*ave)*a Kh«ng th× a = 1, b = 0. - LÆp j = 1 ®Õn PopSize Fitness[j] = Fitness[j]*a + b. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 89 Ph©n hÖ 1.2 x Chøc n¨ng: - S¶n sinh quÇn thÓ míi NewPop tõ quÇn thÓ cò OldPop - ThÕ quÇn thÓ cò b»ng quÇn thÓ míi. x Vμo: - QuÇn thÓ cò OldPop. - B¶ng gi¸ trÞ søc kháe cña quÇn thÓ cò. x Ra: - QuÇn thÓ OldPop ®· ®†îc thÕ bëi thÕ hÖ míi. x Gi¶i thuËt: - To¸n tö chän läc (Thñ tôc 1.2.1) - LÆp i = 1 ®Õn khi i lín h¬n hoÆc b»ng PopSize, b†íc nh¶y 2 + To¸n tö t¹p lai (Thñ tôc 1.2.2) + To¸n tö ®ét biÕn (Thñ tôc 1.2.3) - ThÕ quÇn thÓ cò OlpPop b»ng quÇn thÓ míi NewPop. Thñ tôc 1.2.1 x Chøc n¨ng: - Chän läc quÇn thÓ bè mÑ tõ quÇn thÓ con, mçi c¸ thÓ ®†îc chän víi s¸c xuÊt tû lÖ víi søc kháe cña c¸ thÓ ®ã. x Vμo: - QuÇn thÓ cò OldPop vμ b¶ng gi¸ trÞ søc kháe cña tõng c¸ thÓ trong quÇn thÓ. OldPop, Fitness( ) Chӑn lӑc (Thͯ tͭc 1.2.1) i = 1 Tҥp lai (Thͯ tͭc 1.2.2) Ĉӝt biӃn (Thͯ tͭc 1.2.3) i < Gen i = i + OldPop:= NewPop Hình 4.3: S˯ d͛ gi̫i thu̵t Phân h͏ 1.2 Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 90 x Ra: - QuÇn thÓ míi NewPop c¸c c¸ thÓ bè mÑ ®†îc chän x Gi¶i thuËt: - TÝnh tæng søc kháe toμn quÇn thÓ Sumfitness. - LÆp i = 1 ®Õn khi i lín h¬n hoÆc b»ng PopSize + Sinh mét sè ngÉu nhiªn p0. + TÝnh gi¸ trÞ Su = p0*Sumfitness. + ChØ sè j ®Ó tæng ch¹y søc kháe cña c¸ thÓ lín h¬n Su lμ chØ sè cña c¸ thÓ ®†îc chän. + §†a c¸ thÓ ®†îc chän vμo quÇn thÓ míi NewPop. Thñ tôc 1.2.2 x Chøc n¨ng: - T¹p lai hai chuçi bè mÑ ®Ó t¹o thμnh hai con míi x Vμo: - ChØ sè cña hai chuçi bè mÑ trong quÇn thÓ cò - X¸c suÊt t¹p lai Pcross. x Ra: - Hai chuçi con míi. x Gi¶i thuËt - Sinh mét sè ngÉu nhiªn p0 - NÕu p0 < Pcross th× + Sinh mét sè ngÉu nhiªn míi p1 + TÝnh vÞ trÝ t¹p lai l = p1*(Lchrom -1) Kh«ng th× VÞ trÝ t¹p lai lμ Lchrom. - Sao chÐp gen tõ 1 ®Õn l cña bè mÑ 1 sang con 1 vμ bè mÑ 2 sang con 2 - Sao chÐp gen tõ l+1 ®Õn Lchrom cña bè mÑ 1 sang con 2 vμ tõ bè mÑ 2 sang con 1. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 91 Thñ tôc 1.2.3 x Chøc n¨ng: - Lμm ®ét biÕn gen cña hai chuçi con míi ®†îc sinh ra. x Vμo: - Hai chuçi con sinh ra sau t¹p lai. - X¸c suÊt ®ét biÕn Pmutation. x Ra: - Hai chuçi con sau ®ét biÕn. x Gi¶i thuËt: - DuyÖt tõ gen cña hai chuçi con míi ®†îc sinh ra sau t¹p lai. - Sinh sè ngÉu nhiªn p0. - NÕu p0 < Pmutation th× Gen ®ã ®†îc biÕn ®æi tõ 0 sang 1 hoÆc ng†îc l¹i. Kh«ng th× Gen ®ã ®†îc gi÷ nguyªn. Ph©n hÖ 2 x Chøc n¨ng: - LuyÖn tham sè b»ng gi¶i thuËt BP víi hÖ sè häc biÕn ®æi ®èi víi bé träng sè chuyÓn tõ kÕt qu¶ luyÖn cña gi¶i thuËt GA chuyÓn sang. - L†u tr÷ bé träng sè tèt nhÊt. x Vμo: 0.05*PopSize bé träng sè cïng mét cÊu tróc m¹ng m, n, a. x Ra: Mét bé träng sè W. x Gi¶i thuËt: LÆp i = 1 ®Õn 0.05*PopSize Hình 4.4: S˯ ÿ͛ kh͙i gi̫i thu̵t ph©n h͏ 2 - Cҩu trúc mҥng m,n,A - M = 0.05*PopSize bӝ trӑng sӕ i = 1 Hӑc tham sӕ bҵng giҧi thuұt BP vӟi hӋ sӕ hӑc biӃn ÿәi (Thӫ tөc 2.1) i < M i = i + 1 Lѭu trӳ bӝ trӑng sӕ tӕt nhҩt Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 92 + Häc tham sè víi gi¶i thuËt BP víi hÖ sè häc biÕn ®æi (Thñ tôc 2.1). + L†u tr÷ bé träng sè cho gi¸ trÞ sai sè tÝch luü e lμ nhá nhÊt. Thñ tôc 2.1 x Chøc n¨ng:Häc tham sè b»ng gi¶i thuËt BP víi hÖ sè häc biÕn ®æi x Vμo: CÊu tróc m¹ng m, n, a, W vμ tËp mÉu luyÖn, sè b†íc thùc hiÖn biÕn ®æi Step, hÖ sè häc D, b†íc t¨ng gi¶m cña hÖ sè häc a vμ sai sè tèi thiÓu lμm tiªu chuÈn dõng H. x Ra: Bé träng sè W sau khi häc. x Gi¶i thuËt: LÆp c¸c b†íc sau ®©y choi ®Õn khi sai sè MSe nhá h¬n tiªu chuÈn dõng H. - Khëi t¹o tæng sai sè trªn tËp huÊn luyÖn e = 0, b†íc thùc hiÖn biÕn ®æi k =0 - LÆp i = 1 ®Õn sè mÉu cã trong tËp luyÖn + G¸n tÝn hiÖu ra ë líp vμo out0 = Xi + LÆp ®èi víi c¸c n¬ ron thø j ë trªn líp Èn ( l = 1) vμ líp ra ( l = 2) TÝn tæng tÝn hiÖu vμo theo c«ng thøc ¦ m i l i l ji l j xwNet 1 . TÝn gi¸ trÞ tÝn hiÖu ra  lj l j Net Out  exp1 1 + TÝnh sai sè ë líp ra  ¦  n j last jj last Outy 1 2H + B¾t ®Çu tõ líp ra ( l = 2 ) cho tíi líp Èn ( l = 1 ) tÝnh: HÖ sè hiÖu chØnh ijG L†îng hiÖu chØnh 1.  ' liijlji Outw GK HiÖu chØnh c¸c träng sè lji l ji l ji www ' - TÝnh gi¸ trÞ hμm gi¸ e theo Thñ tôc 1.1.2 - Thùc hiÖn qu¸ tr×nh biÕn ®æi hÖ sè häc: Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 93 + NÕu 'e < 0, kiÕm tra nÕu k < Step th× k = k + 1, kh«ng th× g¸n k = 0 vμ D = D + a + NÕu 'e >= 0 th× D = D * (1 - a) vμ g¸n k = 0. 4.3. ch‡¬ng tr×nh dù b¸o d÷ liÖu Mμn h×nh chÝnh cña ch†¬ng tr×nh nh† sau : H×nh 4.5. Mμn h×nh chÝnh cña ch†¬ng tr×nh dù b¸o Ch†¬ng tr×nh x©y dùng gåm c¸c môc thùc ®¬n : Khëi t¹o tham sè, LuyÖn m¹ng n¬ ron, Dù b¸o d÷ liÖu. Sau ®©y lμ m« t¶ chi tiÕt c¸c chøc chÝnh cña ch†¬ng tr×nh: x Më tÖp huÊn luyÖn TÖp d÷ liÖu huÊn luyÖn lμ tÖp cã cÊu tróc ®†îc l†u tr÷ trong mét tÖp TXT, chøa 43 mÉu sè liÖu tõ n¨m 2001 ®Õn n¨m 2005 vÒ mùc n†íc ®Ønh lò, mùc n†íc ch©n lò vμ l†îng m†a trung b×nh ®o ®†îc t¹i tr¹m S¬n Giang. Sè liÖu ®†a vμo m¹ng ®†îc m· hãa trong ®o¹n [0.1,0.9] theo nguyªn t¾c nªu phÇn 4.2.1. - C¸c tr†êng d÷ liÖu ®†îc ph©n c¸ch nhau b»ng dÊu “;” - Tr†êng d÷ liÖu dù b¸o lμ tr†êng cuèi cïng, lμ ®Çu ra cña m¹ng. VÝ dô : tÖp d÷ liÖu sau khi ®†îc m· hãa nh† sau : Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 94 H×nh 4.6: D÷ liÖu tÖp huÊnluyÖn x Mμn h×nh nhËp c¸c tham sè cÊu tróc m¹ng Cho phÐp ng†êi sö dông nhËp c¸c tham sè ®Çu vμo cho m¹ng n¬ron. Sè líp m¹ng ngÇm ®Þnh lμ 2, sè ®Çu vμo lμ 2 vμ sè ®Çu ra lμ 1 lÊy theo tÖp huÊn luyÖn. H×nh 4.7: Mμn h×nh nhËp tham sè cho m¹ng n¬ron Víi bμi to¸n nμy, sè n¬ ron trªn líp Èn chän lμ 4, gi¸ trÞ c¸c tham sè kh¸c ngÇm ®Þnh trªn mμn h×nh nhËp ®†îc coi lμ c¸c gi¸ trÞ khëi ®Çu kh¸ tèt. Sau khi nhËp xong, nhÊn OK ®Ó g¸n gi¸ trÞ c¸c tham sè cho m¹ng n¬ ron. x Mμn h×nh nhËp c¸c tham sè cña gi¶i thuËt di truyÒn Cho phÐp ng†êi sö dông nhËp c¸c tham sè cña gi¶i thuËt di truyÒn nh† kÝch th†íc quÇn thÓ, x¸c suÊt t¹p lai, x¸c suÊt ®ét biÕn, sè thÕ hÖ tiÕn hãa...C¸c gi¸ trÞ ngÇm ®Þnh ë mμn h×nh d†íi ®†îc xem lμ c¸c gi¸ trÞ xuÊt ph¸t kh¸ tèt t×m ®†îc theo ph†¬ng ph¸p thö vμ sai, kÝch th†íc quÇn thÓ chän lμ 100, sè thÕ hÖ tiÕn hãa lμ 100. Tû lÖ chuyÓn giao sè c¸ thÓ sang luyÖn tiÕp b»ng gi¶i thuËt BP ngÇm ®Þnh lμ 0.05. Sè träng sè cña m¹ng t†¬ng øng víi bμi to¸n thö nghiÖm khi chän 4 n¬ ron Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 95 trong líp Èn lμ 4*2 + 4 + 4*1 + 1 = 17 träng sè, do vËy ®é dμi cña chuçi c¸ thÓ lμ 17*20 = 340. H×nh 4.8:Mμn h×nh nhËp tham sè cho gi¶i thuËt GA B†íc tiÕp theo lμ thùc thi gi¶i thuËt lai GA - BP x T×m kiÕm b»ng gi¶i thuËt di truyÒn Mμn h×nh t×m kiÕm c¸c c¸ thÓ tèt b»ng gi¶i thuËt di truyÒn cã d¹ng sau H×nh 4.9: T×m kiÕm b»ng gi¶i thuË GA T¹i mçi thÕ hÖ tiÕn hãa, mμn h×nh th«ng b¸o sè c¸ thÓ tèt cã søc kháe lín h¬n søc kháe trung b×nh toμn quÇn thÓ vμ sè c¸ thÓ trung b×nh cã søc kháe nhá h¬n søc kháe trung b×nh. NhËn thÊy r»ng ë gai ®o¹n cuèi cña sè thÕ hÖ tiÕn hãa, sè c¸ thÓ tèt chiÕm ®¹i ®a sè, gi¸ trÞ søc kháe cña chóng gÇn víi gi¸ trÞ søc khoÎ trung b×nh. Sau 100 thÕ hÖ tiÕn hãa, 5 c¸ thÓ cã søc kháe tèt nhÊt trong sè 100 c¸ thÓ ë quÇn thÓ cuèi cïng ®†îc l†u tr÷ l¹i lμm ®Çu vμo cho gi¶i thuËt BP. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 96 x HuÊn luyÖn b»ng gi¶i thuËt BP 5 c¸ thÓ lÇn l†ît ®†îc gi¶i thuËt BP sö dông h»ng sè häc biÕn ®æi luyÖn ®Õn b·o hßa víi c¸c tham sè ban ®Çu ®· ®†îc khëi t¹o. C¸c ®å thÞ d†íi ®©y m« t¶ mét chu kú luyÖn ®èi víi mét c¸ thÓ. Trªn ®å thÞ, ®†êng mμu xanh nh¹t lμ c¸c ®Çu ra mong muèn ®èi víi tËp d÷ liÖu, ®†êng mμu xanh ®Ëm lμ tr¶ lêi cña m¹ng ®èi víi d÷ liÖu ®Çu vμo. §èi víi mçi c¸ thÓ, t¹i ®iÓm xuÊt ph¸t luyÖn b»ng gi¶i thuËt BP, hai ®†êng nμy ®· kh¸ gÇn nhau, do vËy gi¶i thuËt di truyÒn t×m kiÕm c¸c c¸ thÓ ®· kh¸ gÇn lêi gi¶i. H×nh 4.10.a:HuÊn luyÖn b»ng gi¶i thuËi BP TËp d÷ liÖu huÊn luyÖn ®ång thêi còng dïng lμm tËp kiÓm tra ®Ó kiÓm tra kh¶ n¨ng tæng qu¸t hãa cña m¹ng. ViÖc kiÓm tra nμy ®†îc thùc hiÖn víi viÖc cËp nhËt ®å thÞ ®Òu ®Æn sau 50 chu kú huÊn luyÖn. Sau mét sè lín chu kú huÊn luyÖn, kh¶ n¨ng tæng qu¸t hãa cña m¹ng ®· kh¸ tèt so víi ban ®Çu. Trªn h×nh vÏ, hai ®†êng gÇn nh† trïng nhau. §ång thêi, lçi MSE tiÕp tôc gi¶m cho ®Õn khi nhá h¬n hÖ sè chÝnh x¸c, tËp träng sè ®†îc ghi l¹i vμ thuËt to¸n l¹i tiÕp tôc víi c¸ thÓ tiÕp theo Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 97 H×nh 4.10.b:HuÊn luyÖn b»ng gi¶i thuËt BP KÕt thóc chu kú huÊn luyÖn 5 c¸ thÓ, c¸ thÓ cã tËp träng sè tèt nhÊt (cã sai sè MSe nhá nhÊt) ®†îc chän lμm kÕt qu¶ cña gi¶i thuËt. TËp träng sè nμy ®†îc ghi l¹i d†íi d¹ng mét tÖp TXT. x Dù b¸o d÷ liÖu M¹ng sau khi ®†îc huÊn luyÖn sö dông ®Ó dù b¸o d÷ liÖu. TÖp d÷ liÖu dù b¸o lμ tÖp TXT chøa sè liÖu vÒ mèi quan hÖ gi÷a mùc n†íc ®Ønh lò víi mùc n†íc ch©n lò vμ l†îng m†a ®o ®†îc t¹i tr¹m S¬n Giang. TÖp nμy cã cÊu tróc vμ ®†îc tû lÖ hãa gièng nh† tÖp huÊn luyÖn Mμn h×nh dù b¸o nh† sau: Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 98 H×nh 4.11:Mμn h×nh dù b¸o Trªn mμn h×nh, ®†êng biÓu diÔn ®Çu ra mong muèn vμ tr¶ lêi cña m¹ng s¸t nhau, chøng tá kh¶ n¨ng tæng qu¸t hãa cña m¹ng sau khi ®†îc häc lμ kh¸ tèt. ™ KÕt luËn ch¬ng 4 Ch†¬ng 4 giíi thiÖu bμi tãan dù b¸o lò trªn s«ng Trμ Khóc vμ thùc hiÖn c¸c b†íc x©y dùng ch†¬ng tr×nh dù b¸o dùa trªn c¬ së gi¶i thuËt lai GA-BP ®· tr×nh bÇy trong ch†¬ng 3. KÕt qu¶ cña ch†¬ng tr×nh ®· cho thÊy, sau khi ®†îc huÊn luyÖn b»ng gi¶i thuËt lai GA-BP, m¹ng cho kÕt qu¶ dù b¸o kh¸ tèt. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 99 KÕt luËn LuËn v¨n tËp trung nghiªn cøu kü thuËt sö dông m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu. KÕt hîp tÝnh chÊt t×m kiÕm toμn côc cña gi¶i thuËt GA víi tÝnh héi tô cña gi¶i thuËt BP, luËn v¨n nghiªn cøu gi¶i ph¸p x©y dùng gi¶i thuËt lai GA-BP trong huÊn luyÖn m¹ng n¬ron truyÒn th¼ng nhiÒu líp vμ ¸p dông thö nghiÖm m« h×nh ®ã cho bμi to¸n dù b¸o trong lÜnh vùc khÝ t†îng thuû v¨n. Mét sè kÕt qu¶ ®¹t ®†îc cña luËn v¨n: - Tæng kÕt nh÷ng vÊn ®Ò nghiªn cøu vÒ khai ph¸ d÷ liÖu vμ ph¸t hiÖn tri thøc trong CSDL. - T×m hiÓu vÒ kü thuËt sö dông m¹ng n¬ron, gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ c¸c vÊn ®Ò liªn quan. Nghiªn cøu gi¶i ph¸p tÝch hîp gi¶i thuËt GA vμ gi¶i thuËt BP thμnh mét gi¶i thuËt lai dïng ®Ó huÊn luyÖn m¹ng n¬ron truyÒn th¼ng nhiÒu líp. - ¸p dông nh÷ng vÊn ®Ò ®· nghiªn cøu vμo x©y dùng m« h×nh vμ cμi ®Æt m¹ng n¬ron dù b¸o cho bμi to¸n dù b¸o lò trªn s«ng. Mét sè híng ph¸t triÓn: - TÝch hîp gi¶i thuËt GA vμ PB trong viÖc häc cÊu tróc cña m¹ng n¬ron nh»m t×m ra sè n¬ron trong líp Èn tèt nhÊt cho mét bμi to¸n. - C¶i tiÕn c¸c to¸n tö cña gi¶i thuËt GA ®Ó n©ng cao hiÖu qu¶ t×m kiÕm c¸c c¸ thÓ tèt nhÊt. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 100 Tμi liÖu tham kh¶o Tμi liÖu tiÕng ViÖt [1]. NguyÔn §×nh Thóc (2001), LËp tr×nh tiÕn hãa, Nhμ xuÊt b¶n gi¸o dôc. Tμi liÖu tiÕng Anh [2]. Back T. and Schwefel H.-P. (1993), “An overview of evolutionary algorithms for parameter optimization”, evolutionary Computation, vol. 1, no. 1, pp. 1- 23. [3]. Bose N. and Liang P. (1996), Neural Network Foundamentals with Graphs, algorithms, and applications, McGraw-Hill. [4]. Fayyad, Gregory Piatetsky, Shapiro, Padhraic Smith, (1996), From Data mining to Knowledge Discovery: An overview. [5]. Gero J. S., Kazakov V. a., and Schinier T., (1997), “Genetic engineering and design problems”, In Evolutionary Algorithms in Engineering Applications, pages 47-68. Springer-Verlag. [6]. Goldberg D. E., (1989), Genetic algorithm in search, optimization and machine learning, Addison-Wesley, Reading, Massachusets. [7]. Ho Tu Bao, Introduction to Knowledge Discovery and Data Mining, Institute of Information Technology, [8]. Lawrence S., C. L. Giles, a. C. Tsoj, “What size Neural Network Gives optimal Generalization? Convergence Properties of Backpropagation”, Techni cal Report, Institute for Advanced Computer Studies - University of Maryland College Park, June 1996. [9]. Oh S. H., Lee yj., a modified error function to improve the error Back- Propagation algorithm for Multi-layer perceptrons, eTRi Journal Vol 17, No 1, april 1995. [10]. Patterson D. (1996), Artifical Neural Networks, Theory and Application, Prentice Hall. Kü thuËt m¹ng n¬ron vμ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vμ thö nghiÖm øng dông Dy¬ng ThÞ HiÒn Thanh – CNTT 2006 101 [11]. Randall S. Sexton and Naheel A. Sikander, “Data Mining using a Genetic algorithm trained Neural network”, Computer introduction system, Southwest Missouri State University, USA. [12]. Schalkoff R. (1997), Artifical neural networks, McGraw-Hill. [13]. Udoseiffert, Michaelis B., On the gradient desert in back-propagation and its substitution by a genetic algorithm, Proceedings of the IASTED international Conference Applied Informatics 14-17/02/2000, InnsBruck, Austria.