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

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 ∂ ∂−−=∂ −∂ =∂ −−∂=∂ ∂= ∑ = ∧ 21 2 Bëi v×: ( ) ( )MiMM i M i M M i M i M i i nf n nf n a n a •=∂ ∂=∂ ∂=∂ ∂ nªn ta cã thÓ viÕt: ( ) ( )MiMiiMi nfats •−−= 2 ë d¹ng ma trËn sÏ lµ: ( )( )atnFs −−= • MMM 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 D−¬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 −−= • MMM 2 ( )( ) .11 ++•= mTmmmm sWnFs vi 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 α α −=+ −=+ − 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 D−¬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 D−¬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]: • ],[ nlm∈ - n»m gi÷a kho¶ng kÝch th−íc líp vµo, líp ra • 3 )(2 nlm += - 2/3 tæng kÝch th−íc líp vµo vµ líp ra • lm 2< - nhá h¬n 2 lÇn kÝch th−íc líp vµo • 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 D−¬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 xe−+1 ( )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 D−¬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 (1≤ p ≤ ∝) 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 ≤ p ≤ ∝ (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 D−¬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 α. 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Þ α 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 α 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Þ α 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 D−¬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 α…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 ρ nµo ®ã (víi 0 < ρ < 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 D−¬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 D−¬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 D−¬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 D−¬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: • 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. • 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 D−¬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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 78 Ch−¬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 D−¬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 ®ã: • N¨m: lµ n¨m lÊy mÉu sè liÖu, kh«ng tham gia vµo d÷ liÖu dù b¸o • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 80 • 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 • 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 • 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: • L−îng m−a trung b×nh: nhËn gi¸ trÞ thùc cña nã. • Mùc n−íc ch©n lò: nhËn gi¸ trÞ thùc cña nã. • 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 D−¬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 D−¬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: • 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. • 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. • 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 D−¬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 • 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] • Vµo: - TËp mÉu huÊn luyÖn • 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. • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 84 Ph©n hÖ 1 • 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. • Vµo: - CÊu tróc m¹ng m, n, a. - TËp mÉu luyÖn. • 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. • 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 • 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|. • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 85 - Sè l−îng chuçi nhÞ ph©n Popsize. • Ra: - QuÇn thÓ gåm Popsize chuçi nhÞ ph©n ®−îc l−u tr÷ trong b¶ng OldPop. • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 86 Ph©n hÖ 1.1 • 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. • Vµo: - QuÇn thÓ OldPop. - TËp luyÖn. • Ra: - Gi¸ trÞ søc khoÎ toµn quÇn thÓ ®−îc chøa trong b¶ng Fitness( ). • 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 D−¬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 • 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 • Vµo: - Chuçi nhÞ ph©n ®é dµi Lchrom - Tæng sè träng sè M • Ra: - B¶ng W( ) cña c¸c träng sè (sè thùc). • 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 • 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. • 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). • Ra: - Sai sè e sinh ra sau khi lan truyÒn toµn bé c¸c mÉu qua m¹ng. • 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 D−¬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 ( )ljlj NetOut −+= 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 • 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( ). • Vµo: - B¶ng gi¸ trÞ hµm gi¸ objective( ). - Sè c¸ thÓ trong quÇn thÓ PopSize. • Ra: - B¶ng gi¸ trÞ hµm søc kháe Fitness( ) • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 89 Ph©n hÖ 1.2 • 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. • Vµo: - QuÇn thÓ cò OldPop. - B¶ng gi¸ trÞ søc kháe cña quÇn thÓ cò. • Ra: - QuÇn thÓ OldPop ®· ®−îc thÕ bëi thÕ hÖ míi. • 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 • 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Ó ®ã. • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 90 • Ra: - QuÇn thÓ míi NewPop c¸c c¸ thÓ bè mÑ ®−îc chän • 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 • Chøc n¨ng: - T¹p lai hai chuçi bè mÑ ®Ó t¹o thµnh hai con míi • Vµo: - ChØ sè cña hai chuçi bè mÑ trong quÇn thÓ cò - X¸c suÊt t¹p lai Pcross. • Ra: - Hai chuçi con míi. • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 91 Thñ tôc 1.2.3 • Chøc n¨ng: - Lµm ®ét biÕn gen cña hai chuçi con míi ®−îc sinh ra. • Vµo: - Hai chuçi con sinh ra sau t¹p lai. - X¸c suÊt ®ét biÕn Pmutation. • Ra: - Hai chuçi con sau ®ét biÕn. • 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 • 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. • Vµo: 0.05*PopSize bé träng sè cïng mét cÊu tróc m¹ng m, n, a. • Ra: Mét bé träng sè W. • 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 D−¬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 • Chøc n¨ng:Häc tham sè b»ng gi¶i thuËt BP víi hÖ sè häc biÕn ®æi • 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 α, 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 ε. • Ra: Bé träng sè W sau khi häc. • 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 ε. - 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 ( )ljlj NetOut −+= exp1 1 + TÝnh sai sè ë líp ra ( )∑ = −= n j last jj last Outy 1 2ε + 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 ijδ L−îng hiÖu chØnh 1. −=∆ liijlji Outw δη 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 D−¬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µ α = α + a + NÕu ∆e >= 0 th× α = α * (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: • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 94 H×nh 4.6: D÷ liÖu tÖp huÊnluyÖn • 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. • 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 D−¬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 • 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 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 96 • 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 D−¬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. • 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 D−¬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 D−¬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 D−¬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 D−¬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.