Tài liệu Xây dựng mô hình mạng nơ ron dự báo dữ liệu và ứng dụng mô hình đó trong bài toán dự báo đỉnh lũ sông Trà Khúc tại trạm khí tượng Sơn Giang

1 Më ®Çu Dù b¸o d÷ liÖu lµ bµi to¸n quan träng mang l¹i nhiÒu lîi Ých thiÕt thùc phôc vô con ngêi, nã gióp con ngêi n¾m b¾t ®îc c¸c quy luËt vËn ®éng trong tù nhiªn vµ trong ®êi sèng kinh tÕ x· héi. Trong nh÷ng n¨m gÇn ®©y, c¸c m¹ng n¬ ron truyÒn th¼ng nhiÒu líp ®îc thùc tiÔn chøng minh lµ kh¸ m¹nh vµ hiÖu qu¶ trong c¸c bµi to¸n dù b¸o vµ ph©n tÝch sè liÖu, ®Æc biÖt trong c¸c bµi to¸n dù b¸o sö dông n¨ng lîng, dù b¸o kinh tÕ, dù b¸o trong tù nhiªn… C¸c m¹ng n¬ ron truyÒn th»ng ph¶i ®îc huÊn luyÖn tríc khi sö dông ®Ó thùc thi mét bµi to¸n dù b¸o trong thùc tÕ. Víi mét cÊu tróc m¹ng ®îc chän, qu¸ tr×nh huÊn luyÖn m¹ng lµ qu¸ tr×nh hiÖu chØnh c¸c träng sè cña m¹ng vµ thêng ®îc ph¸t biÓu díi d¹ng mét bµi to¸n tèi thiÓu ho¸ hµm sai sè huÊn luyÖn. Thñ tôc huÊn luyÖn cÇn mét gi¶i thuËt t×m kiÕm cã kh¶ n¨ng t×m lêi gi¶i toµn côc, kh«ng phô thuéc vµo qu¸ tr×nh khëi ®éng c¸c trong sè ban ®Çu. Ngoµi ra, c¸c gi¶i thuËt nµy ph¶i cã kh¶ n¨ng t×m kiÕm hiÖu qu¶ trong kh«ng gian nhiÒu chiÒu do sè lîng träng sè trong c¸c m¹ng n¬ ron lµ kh¸ lín. Gi¶i thuËt GA lµ gi¶i thuËt t×m kiÕm dùa trªn qu¸ tr×nh chän läc tù nhiªn, di truyÒn vµ tiÕn hãa. C¸c nguyªn lý c¬ b¶n cña gi¶i thuËt ®îc t¸c gi¶ J.H.Holland ®Ò xuÊt lÇn ®Çu vµo n¨m 1962, nÒn t¶ng to¸n häc cña gi¶i thuËt GA ®îc t¸c gi¶ c«ng bè trong cuèn s¸ch “Sù thÝch nghi trong c¸c hÖ thèng tù nhiªn vµ nh©n t¹o” xuÊt b¶n n¨m 1975. Gi¶i thuËt GA ®îc xem nh mét ph¬ng ph¸p t×m kiÕm cã bíc chuyÓn ngÉu nhiªn mang tÝnh tæng qu¸t ®Ó gi¶i c¸c bµi to¸n tèi u ho¸. Víi nh÷ng ®Æc thï riªng cña m×nh, gi¶i thuËt GA ®îc sö dông kh¸ hiÖu qu¶ trong thñ tôc huÊn luyÖn m¹ng n¬ ron. Tuy nhiªn, gi¶i thuËt GA gÆp khã kh¨n vÒ sù héi tô. Gi¶i thuËt GA ®¬n gi¶n do Holland ®Ò xuÊt ®· ®îc chøng minh lµ kh«ng b¶o ®¶m sù héi tô hoÆc kh«ng héi tô tíi lêi gi¶i toµn côc. Ngoµi ra, c¸c gi¶i ph¸p c¶i tiÕn chiÕn lîc thay thÕ hoÆc to¸n tö ®ét biÕn tuy gióp cho gi¶i thuËt GA héi tô, nhng sù héi tô nµy dÔ dÉn ®Õn hiÖn tîng héi tô sím, nghÜa lµ gi¶i thuËt kÕt thóc t¹i mét cùc trÞ ®Þa ph¬ng mµ kh«ng cã kh¶ n¨ng t×m thÊy cùc trÞ toµn côc. Gi¶i thuËt huÊn luyÖn kinh ®iÓn lan truyÒn ngîc cña sai sè (gi¶i thuËt BP) ®îc sö dông réng r·i nhÊt trong viÖc huÊn luyÖn m¹ng n¬ ron truyÒn th¼ng. Gi¶i thuËt nµy ®¶m b¶o sù héi tô nhng dÔ héi tô t¹i mét cùc trÞ ®Þa ph¬ng mµ kh«ng cã kh¶ n¨ng t×m kiÕm cùc trÞ toµn côc. MÆt kh¸c, kÕt qu¶ huÊn luyÖn cña gi¶i thuËt nµy phô thuéc vµo nhiÒu yÕu tè, ®Æc biÖt lµ qu¸ tr×nh khëi ®éng c¸c träng sè ban ®Çu. Do nhu cÇu cÊp thiÕt ph¶i x©y dùng mét gi¶i thuËt võa cã kh¶ n¨ng t×m kiÕm lêi gi¶i toµn côc, võa ph¶i ®¶m b¶o sù héi tô ®Ó huÊn luyÖn cho m¹ng n¬ ron truyÒn th¼ng thùc thi mét bµi to¸n dù b¸o trong thùc tÕ, luËn v¨n tËp trung nghiªn cøu gi¶i 2 ph¸p tÝch hîp gi¶i thuËt GA víi gi¶i thuËt BP trong viÖc huÊn luyÖn m¹ng n¬ ron truyÒn th¼ng. Trªn c¬ së ®ã, luËn v¨n tr×nh bµy c¸c bíc chÝnh ®Ó x©y dùng m« h×nh m¹ng n¬ ron dù b¸o d÷ liÖu vµ øng dông m« h×nh ®ã trong bµi to¸n dù b¸o ®Ønh lò s«ng Trµ Khóc t¹i tr¹m khÝ tîng S¬n Giang. Nh÷ng ®ãng gãp chÝnh cña luËn v¨n  LuËn v¨n tr×nh bµy c¸c vÊn ®Ò lý thuyÕt vÒ m¹ng n¬ ron, m¹ng n¬ ron truyÒn th¼ng nhiÓu líp vµ thuËt to¸n BP d¹ng tæng qu¸t ®Ó huÊn luyÖn m¹ng, mét sè vÊn ®Ò vÒ sö dông gi¶i thuËt BP ®Ó huÊn luyÖn m¹ng thùc thi mét bµi to¸n trong thùc tÕ.  LuËn v¨n tr×nh bµy c¸c vÊn ®Ò lý thuyÕt vÒ gi¶i thuËt SGA vµ nh÷ng c¶i tiÕn cña gi¶i thuËt SGA.  LuËn v¨n x©y dùng gi¶i ph¸p tÝch hîp gi¶i thuËt GA víi gi¶i thuËt BP thµnh mét gi¶i thuËt lai GA - BP dÓ huÊn luyÖn m¹ng n¬ ron truyÒn th¼ng nhiÓu líp.  LuËn v¨n tr×nh bµy øng dông gi¶i thuËt lai GA - BP trong m« h×nh m¹ng n¬ ron dù b¸o. Gi¶i thuËt lai GA - BP ®· ®îc cµi ®Æt vµ thö nghiÖm ®Ó huÊn luyÖn m¹ng n¬ ron truyÒn th¼ng trong bµi to¸n dù b¸o khÝ tîng thuû v¨n. CÊu tróc cña luËn v¨n PhÇn më ®Çu cña luËn v¨n giíi thiÖu néi dung nghiªn cøu, tÝnh cÊp thiÕt cña ®Ò tµi vµ nh÷ng ®ãng gãp chÝnh cña luËn v¨n. Ch¬ng 1 giíi thiÖu c¸c kh¸i niÖm c¬ b¶n vµ ph¹m vi øng dông cña m¹ng n¬ ron. Ch¬ng 2 giíi thiÖu vÒ gi¶i thuËt SGA vµ c¸c c¶i tiÕn cña gi¶i thuËt SGA. Ch¬ng 3 giíi thiÖu vÒ m¹ng n¬ ron truyÒn th¼ng nhiÒu líp, gi¶i thuËt BP, c¸c vÊn ®Ò vÒ sö dông gi¶i thuËt BP vµ x©y dùng gi¶i ph¸p tÝch hîp gi¶i thuËt GA víi gi¶i thuËt BP trong viÖc huÊn luyÖn m¹ng n¬ ron truyÒn th¼ng nhiÒu líp. Ch¬ng 4 tr×nh bµy m« h×nh thuËt to¸n vµ cµi ®Æt gi¶i thuËt lai GA BP. Ch¬ng 5 tr×nh bµy c¸c bíc x©y dùng m« h×nh m¹ng n¬ ron dù b¸o vµ thö nghiÖm gi¶i thuËt GA - BP trong viÖc huÊn luyÖn m¹ng n¬ ron ®Ó thùc thi bµi to¸n dù b¸o ®Ønh lò s«ng Trµ Khóc t¹i tr¹m S¬n Giang. PhÇn kÕt luËn nªu ra c¸c kÕt luËn tõ luËn v¨n vµ c¸c híng nghiªn cøu tiÕp theo. PhÇn phô lôc ®a ra mét sè chøc n¨ng cña ch¬ng tr×nh ®îc viÕt b»ng Visual Basic. 3 4 Ch¬ng 1 C¸c kh¸i niÖm c¬ b¶n vÒ m¹ng n¬ ron Ch¬ng nµy ®Ò cËp ®Õn c¸c vÊn ®Ò sau: 1.1. 1.2. 1.3. 1.4. 1.5. N¬ ron sinh häc vµ m¹ng n¬ ron sinh häc N¬ ron nh©n t¹o M¹ng n¬ ron nh©n t¹o Thñ tôc häc cña m¹ng n¬ ron Ph¹m vi øng dông cña m¹ng n¬ ron 1.1. N¬ ron sinh häc vµ m¹ng n¬ ron sinh häc HÖ thÇn kinh ë ngêi cã kho¶ng 1010 tÕ bµo thÇn kinh ®îc gäi lµ c¸c n¬ ron [24]. Mçi n¬ ron gåm cã ba phÇn: th©n n¬ ron víi nh©n ë bªn trong, mét ®Çu thÇn kinh ra vµ mét hÖ thèng h×nh c©y c¸c ®Çu thÇn kinh vµo. §é lín cña c¸c tÝn hiÖu vµo cã thÓ bÞ thay ®æi khi ®îc truyÒn qua c¸c khíp thÇn kinh cã trªn c¸c nh¸nh thÇn kinh vµo. Tû lÖ biÕn ®æi tÝn hiÖu ë khíp thÇn kinh ®îc gäi lµ ®é khuyÕch ®¹i khíp vµ ®îc gäi lµ c¸c träng sè trong c¸c n¬ ron nh©n t¹o. Theo c¸c nghiªn cøu vÒ sinh häc, chøc n¨ng cña hÖ thÇn kinh kh«ng phô thuéc nhiÒu vµo vai trß cña tõng n¬ ron ®¬n lÎ mµ phô thuéc vµo c¸ch mµ toµn bé c¸c n¬ ron ®îc nèi víi nhau, gäi lµ m¹ng n¬ ron sinh häc [24]. 1.2. N¬ ron nh©n t¹o N¬ ron nh©n t¹o lµ m« h×nh to¸n häc m« pháng n¬ ron sinh häc. Mçi n¬ ron nh©n t¹o ®îc gäi lµ mét ®¬n vÞ xö lý víi chøc n¨ng: nhËn tÝn hiÖu vµo tõ c¸c ®¬n vÞ phÝa tríc (hay mét nguån bªn ngoµi), tÝnh tÝn hiÖu ra tõ c¸c tÝn hiÖu vµo vµ lan truyÒn tÝn hiÖu ra sang c¸c ®¬n vÞ kh¸c. x0 x1 ... xn θj w j0 w j1 Σ w jn n j aj a j   w ji x i   j g ( a j) zj zj  g (a j) i 1 H×nh 1.1 : §¬n vÞ xö lý thø j Mçi tÝn hiÖu ®Çu vµo n¬ ron thø j ®îc ký hiÖu lµ xi víi träng sè t¬ng øng lµ wji. §¹i lîng ®o tÝn hiÖu tæng céng ®i vµo n¬ ron thø j, ký hiÖu lµ aj, ®îc x¸c ®Þnh mét c¸ch ®¬n gi¶n nh sau :  aj lµ hµm cña c¸c tÝn hiÖu xi vµ c¸c träng sè wji, gäi lµ Hµm kÕt hîp 5  Hµm kÕt hîp lµ tæng c¸c tÝch cña tÝn hiÖu xi vµ träng sè t¬ng øng wj : n aj  wjixi  j i 1 Trong ®ã  lµ mét tham sè ®îc gäi lµ ngìng cña n¬ ron. NÕu wji>0, n¬ ron ®îc coi lµ ë trong tr¹ng th¸i kÝch thÝch. NÕu wji < 0, n¬ ron ë tr¹ng th¸i kiÒm chÕ. Qu¸ tr×nh biÕn ®æi gi¸ trÞ aj thµnh tÝn hiÖu ®Çu ra zj ®îc thùc hiÖn bëi hµm kÝch ho¹t (hµm chuyÓn) phi tuyÕn zj= g(aj). Hµm kÝch ho¹t ph¶i tho¶ m·n c¸c ®iÒu kiÖn sau:  TÝn hiÖu ®Çu ra zj lµ kh«ng ©m víi bÊt kÓ gi¸ trÞ nµo cña aj  g lµ hµm liªn tôc vµ bÞ chÆn trong kho¶ng [0,1] Nh÷ng hµm tháa m·n ®iÒu kiÖn trªn cßn ®îc gäi lµ c¸c hµm nÐn theo nghÜa chóng nÐn tÝn hiÖu ®Çu ra vµo mét kho¶ng nhá. Cã kh¸ nhiÒu hµm tho¶ m·n c¸c ®iÒu kiÖn trªn, song trong thùc tÕ chØ cã mét sè hµm thêng ®îc sö dông trong c¸c m¹ng n¬ ron nh sau 1) Hµm tuyÕn tÝnh (Linear) : g ( x)  x 2) Hµm ranh giíi cøng (Hard-Limiter) : Hµm nµy chØ cã hai gi¸ trÞ lµ 0 vµ 1, ngoµi ra hµm cßn cã mét gi¸ trÞ ngìng . TÝn hiÖu ®Çu ra phô thuéc tæng tÝn hiÖu ®Çu vµo vµ gi¸ trÞ ngìng. 1 g ( x)  0 if( x  ) if( x   ) V× hµm nµy rÊt thuËn tiÖn khi ®a c©u tr¶ lêi cã hay kh«ng nªn nã thêng xuyªn ®îc sö dông cho c¸c tÝn hiÖu ra cuèi cïng cña m¹ng. 3) Hµm ngìng logic: 1 g ( x)  0 if( x  ) if( x   ) 4) Hµm sigmoid (Sigmoid function (logsig)) 1 g ( x)  1  e x Hµm nµy ®Æc biÖt thuËn lîi khi sö dông cho c¸c m¹ng ®îc huÊn luyÖn b»ng gi¶i thuËt BP, bëi v× nã dÔ lÊy ®¹o hµm, do ®ã cã thÓ gi¶m ®¸ng kÓ tÝnh to¸n trong qu¸ tr×nh huÊn luyÖn. MÆt kh¸c, hµm nµy ®îc øng dông cho c¸c bµi to¸n mµ ®Çu ra mong muèn r¬i vµo kho¶ng [0,1]. 1.3. M¹ng n¬ ron nh©n t¹o 6 Kh¸i niÖm M¹ng n¬ ron nh©n t¹o lµ hÖ thèng bao gåm nhiÒu n¬ ron nh©n t¹o kÕt hîp víi nhau. HÖ thèng nµy cã kh¶ n¨ng häc sè liÖu vµ tæng qu¸t hãa tõ c¸c sè liÖu ®îc häc. CÊu tróc M¹ng n¬ ron nh©n t¹o ®îc biÓu diÔn b»ng mét ®å thÞ gåm mét tËp c¸c nót vµ c¸c cung cã híng, mçi nót t¬ng øng víi mét n¬ ron, c¸c cung biÓu diÔn c¸c liªn kÕt gi÷a c¸c n¬ ron. CÊu tróc m¹ng n¬ ron gåm c¬ cÊu tæ chøc vµ s¬ ®å kÕt nèi. C¬ cÊu tæ chøc thêng ®îc x¸c ®Þnh bëi sè líp m¹ng vµ sè n¬ ron trong mçi líp:  Líp vµo : C¸c n¬ ron trong líp vµo gäi lµ c¸c n¬ ron vµo, chóng kh«ng xö lý th«ng tin mµ chØ m· hãa mÉu ®a vµo m¹ng ®Ó xö lý. Th«ng thêng, sè thuéc tÝnh cña mÉu ®a vµo m¹ng b»ng sè n¬ ron vµo, chÝnh lµ sè ®Çu vµo cña m¹ng.  Líp Èn : C¸c n¬ ron trong líp nµy gäi lµ c¸c n¬ ron Èn v× chóng kh«ng thÓ quan s¸t trùc tiÕp ®îc. M¹ng cã thÓ cã mét hay nhiÒu líp Èn. Chóng cung cÊp c¸c m« h×nh to¸n häc phi tuyÕn cho m¹ng.  Líp ra : C¸c n¬ ron ë líp nµy gäi lµ c¸c n¬ ron ra, c¸c n¬ ron nµy m· ho¸ gi¸ trÞ hay kh¸i niÖm cña c¸c mÉu ®a vµo m¹ng. VÝ dô, trong bµi to¸n ph©n líp, mçi ®Çu ra lµ ®¹i diÖn cho mét líp c¸c ®èi tîng. S¬ ®å kÕt nèi x¸c ®Þnh bëi ph¬ng thøc kÕt nèi gi÷a c¸c n¬ ron trong m¹ng [21]:  M¹ng truyÒn th¼ng : Luång d÷ liÖu ®i tõ c¸c n¬ ron vµo ®Õn c¸c n¬ ron ra chØ ®îc truyÒn th¼ng. Kh«ng cã c¸c liªn kÕt tõ c¸c n¬ ron ra tíi c¸c n¬ ron vµo trong cïng mét líp hay cña c¸c líp tríc ®ã. x0 bias h0 x1 bias y1 h1 x2 y2 h2 … … xl Líp vµo w (1 ) ji hm Líp Èn … yn w (2) kj Líp ra H×nh 1.2: M¹ng n¬ron truyÒn th¼ng nhiÒu líp (Feed-Forward Neural Network) 7  M¹ng håi quy: Cã chøa c¸c liªn kÕt ngîc, nghÜa lµ c¸c liªn kÕt tõ n¬ ron líp ra tíi n¬ ron líp vµo trong cïng mét líp hoÆc c¸c líp tríc ®ã. h0 x0 y0 h1 x1 … xl Líp vµo … y1 … yn hm Líp Èn Líp ra H×nh 1.3: M¹ng håi quy (Recurrent Neural Network) C¸c th«ng sè cÊu tróc cña m¹ng Díi ®©y lµ c¸c th«ng sè cÊu tróc cña m¹ng n¬ ron nh©n t¹o:  S¬ ®å kÕt nèi (m¹ng truyÒn th¼ng hay håi quy)  Sè t×n hiÖu vµo vµ sè tÝn hiÖu ra  Sè líp m¹ng  Sè n¬ ron trªn mçi líp  Sè lîng c¸c träng sè cña mçi líp 1.4. Thñ tôc häc cña m¹ng n¬ ron Thµnh phÇn quan träng nhÊt vµ kh«ng thÓ thiÕu cña c¸c m¹ng n¬ ron lµ c¸c thñ tôc häc (gi¶i thuËt huÊn luyÖn m¹ng). Cã thÓ chia c¸c thñ tôc nµy thµnh hai nhãm chÝnh lµ häc tham sè vµ häc cÊu tróc. C¶ hai thñ tôc häc nµy cã thÓ ®îc thùc hiÖn ®ång thêi hoÆc t¸ch biÖt. C¸c thñ tôc häc tham sè l¹i cã thÓ ®îc chia thµnh ba líp nhá h¬n lµ häc cã thÇy [24], häc t¨ng cêng [6] vµ häc kh«ng cã thÇy [16]. Häc tham sè Víi mét cÊu tróc m¹ng cho tríc, c¸c träng sè cña m¹ng (gäi lµ c¸c tham sè cña m¹ng) ph¶i ®îc x¸c ®Þnh tríc khi sö dông m¹ng ®Ó thùc thi mét nhiÖm vô cô thÓ. Ngo¹i trõ trêng hîp c¸c m¹ng n¬ ron mét líp Hopfield (c¸c träng sè ®îc tÝnh to¸n mét c¸ch gi¶i tÝch), th«ng thêng, c¸c träng sè cña m¹ng ®îc khëi t¹o ngÉu nhiªn trong mét kho¶ng nhÊt ®Þnh. Häc tham sè lµ qu¸ tr×nh ®iÒu chØnh c¸c träng sè ®Ó m¹ng nhËn biÕt ®îc mèi quan hÖ gi÷a ®Çu vµo vµ ®Çu ra mong muèn. RÊt nhiÒu 8 c¸c thuËt to¸n häc ®îc ®Ò xuÊt ®Ó t×m tËp träng sè tèi u ®èi víi mçi bµi to¸n, c¸c thuËt to¸n ®ã cã thÓ chia thµnh hai nhãm chÝnh : Häc cã thÇy (Supervised learning) vµ Häc kh«ng cã thÇy (Unsupervised Learning).  Häc cã thÇy M¹ng ®îc häc b»ng c¸ch cung cÊp cho nã c¸c cÆp mÉu ®Çu vµo vµ ®Çu ra mong muèn. Sai sè gi÷a c¸c ®Çu ra thùc tÕ so víi c¸c ®Çu ra mong muèn ®îc thuËt to¸n sö dông ®Ó hiÖu chØnh c¸c träng sè trong m¹ng. TËp mÉu lµ tËp c¸c cÆp vÐc t¬ vµo - ra mong muèn M = {x i,yi)} ®îc sö dông ®Ó luyÖn m¹ng n¬ ron. §èi víi mçi vÐc t¬ tÝn hiÖu vµo xi, m¹ng n¬ ron tÝnh to¸n tÝn hiÖu ra out vµ so s¸nh tÝn hiÖu nµy víi tÝn hiÖu ra mong muèn yi ®Ó t¹o ra tÝn hiÖu sai sè. TÝn hiÖu sai sè nµy x¸c ®Þnh bÒ mÆt sai sè lµ hµm cña c¸c träng sè, cã thÓ dïng nh hµm môc tiªu ®Ó hiÖu chØnh c¸c träng sè. C¸c gi¶i thuËt t×m kiÕm ®îc ¸p dông trong thñ tôc häc ®Ó hiÖu chØnh c¸c träng sè sao cho m¹ng n¬ ron cã thÓ s¶n sinh ra c¸c tÝn hiÖu ra out víi mét sai sè chÊp nhËn ®îc so víi tÝn hiÖu ra mong muèn [13]. D÷ liÖu huÊn luyÖn §Çu vµo §Çu ra mong muèn §Ých M¹ng Vµo Ra Thay ®æi Träng sè Sai sè + - Hàm Môc tiªu Gi¶i thuËt luyÖn (Ph ¬ng ph¸p tèi u) H×nh 1.4. S¬ ®å häc cã thÇy  Häc kh«ng cã thÇy Víi ph¬ng ph¸p häc kh«ng cã thÇy, kh«ng cã th«ng tin ph¶n håi tõ m«i trêng bªn ngoµi ®Ó chØ ra r»ng ®Çu ra out cña m¹ng lµ ®óng hay sai. M¹ng n¬ ron ph¶i tù kh¸m ph¸ c¸c ®Æc trng, c¸c mèi t¬ng quan, tÝnh c©n xøng cña c¸c mÉu häc mét c¸ch tù ®éng. §èi víi phÇn lín c¸c biÕn thÓ cña häc kh«ng cã thÇy, c¸c ®Ých trïng víi ®Çu vµo. Nãi mét c¸ch kh¸c, häc kh«ng cã thÇy lu«n thùc hiÖn mét c«ng viÖc t¬ng tù nh mét m¹ng tù liªn hîp, c« ®äng th«ng tin tõ d÷ liÖu vµo. Häc cÊu tróc Trong phÇn häc tham sè, gi¶ ®Þnh lµ ®· cã mét cÊu tróc m¹ng. Thñ tôc häc tham sè tinh chØnh c¸c gi¸ trÞ träng sè sao cho m¹ng ho¹t ®éng nh mong muèn. Thñ 9 tôc häc cÊu tróc t×m kiÕm c¸c tham sè cÊu tróc cña m¹ng ®Ó t¹o ra mét m¹ng ho¹t ®éng tèt nhÊt. Thùc chÊt, häc cÊu tróc lµ viÖc t×m ra sè líp Èn vµ sè n¬ ron trªn mçi líp Èn v× sè ®Çu vµo vµ sè ®Çu ra cña m¹ng lµ x¸c ®Þnh ®èi víi mét bµi to¸n cô thÓ. KÕt qu¶ häc cÊu tróc phô thuéc nhiÒu vµo kÕt qu¶ häc tham sè. Do ®ã, viÖc x©y dùng mét gi¶i thuËt t×m kiÕm cho thñ tôc häc tham sè lµ cÇn thiÕt. Gi¶i thuËt t×m kiÕm nµy ph¶i cã kh¶ n¨ng t×m kiÕm lêi gi¶i toµn côc, t×m kiÕm hiÖu qu¶ trong kh«ng gian nhiÒu chiÒu vµ cã thÓ sö dông cho nhiÒu cÊu tróc m¹ng kh¸c nhau. Trong nh÷ng n¨m gÇn ®©y, mét sè gi¶i thuËt tèi u toµn côc mang tÝnh tÊt ®Þnh vµ mét sè gi¶i thuËt mang tÝnh x¸c suÊt ®· ®îc ®Ò xuÊt. C¸c gi¶i thuËt mang tÝnh x¸c suÊt bao gåm c¸c gi¶i thuËt tiÕn hãa{3] mµ gi¶i thuËt GA lµ mét vÝ dô ®iÓn h×nh. Gi¶i thuËt GA sÏ ®îc tr×nh bµy trong ch¬ng 2 cña luËn v¨n. 1.5. Ph¹m vi øng dông cña m¹ng n¬ ron M¹ng n¬ ron thêng ®îc øng dông trong c¸c lÜnh vùc nh ph©n lo¹i (classification), m« h×nh hãa (modeling), biÕn ®æi (transformation and mapping) vµ dù b¸o c¸c sù kiÖn phô thuéc thêi gian. Ph©n lo¹i Ph©n lo¹i lµ c¸ch s¾p xÕp c¸c ®èi tîng vµo c¸c tËp hoÆc vµo c¸c líp con cña c¸c líp lín h¬n. ViÖc ph©n lo¹i thêng ®îc tiÕn hµnh nhiÒu møc gièng nh phÐp to¸n ra quyÕt ®Þnh, ph©n líp ®èi tîng vµo nhãm, nhãm con; vµo chñng lo¹i, chñng lo¹i con hoÆc vµo líp, líp con. Mét ®èi tîng cã thÓ ®ång thêi thuéc vµo nhiÒu líp kh¸c nhau, do ®ã kÕt qu¶ cña viÖc ph©n lo¹i lµ tÝch cña hai hay nhiÒu quyÕt ®Þnh. M« h×nh hãa HÖ thèng ph©n lo¹i thêng ®a ra c©u tr¶ lêi rêi r¹c nh cã, kh«ng hoÆc mét sè nguyªn ®Þnh danh ®èi tîng ®Çu vµo thuéc líp nµo. Tuy nhiªn, viÖc m« h×nh hãa yªu cÇu hÖ thèng ph¶i s¶n sinh ra c¸c c©u tr¶ lêi mang tÝnh liªn tôc. Mét sè lîng nhá c¸c sè liÖu thùc nghiÖm ®îc sö dông ®Ó x©y dùng m« h×nh, m« h×nh nµy cã thÓ ®a ra c¸c dù b¸o cho tÊt c¶ c¸c ®èi tîng ®Çu vµo cã thÓ. ViÖc t×m ra ®êng cong phï hîp víi c¸c sè liÖu thùc nghiÖm lµ mét vÝ dô øng dông thuéc d¹ng nµy. C¸c øng dông thuéc d¹ng nµy phÇn lín lµ thñ tôc cña mét biÕn vµo vµ mét biÕn ra nh sau: y = f (x, a, b,…, p) Hµm f chøa mét tËp c¸c tham sè a, b,…, p. C¸c tham sè nµy ph¶i ® îc x¸c ®Þnh b»ng viÖc tèi thiÓu hãa ®é chªnh lÖch gi÷a sè liÖu thùc nghiÖm vµ gi¸ trÞ tÝnh to¸n tõ m« h×nh. M« h×nh hãa còng cã thÓ më réng cho bµi to¸n nhiÒu biÕn vµo mét biÕn ra hoÆc nhiÒu biÕn vµo - nhiÒu biÕn ra. 10 ViÖc m« h×nh hãa thêng ®îc sö dông cho c¸c ®èi tîng cã Ýt biÕn, kho¶ng tõ 1 ®Õn 10. §iÒu nµy cã nghÜa lµ thêng sö dông c¸c m¹ng nhá, thêi gian tÝnh còng nh tµi nguyªn m¸y tÝnh Ýt h¬n so víi c¸c m¹ng dïng cho viÖc ph©n lo¹i. BiÕn ®æi ViÖc biÕn ®æi nh»m môc ®Ých nÐn c¸c ®èi tîng tõ kh«ng gian m chiÒu vµo kh«ng gian cã sè chiÒu nhá, kho¶ng hai hoÆc ba. Qua viÖc nÐn c¸c ®èi tîng nµy, chóng sÏ béc lé nh÷ng ®Æc ®iÓm mµ chóng ta kh«ng nhËn thÊy khi chóng ë trong kh«ng gian nhiÒu chiÒu. ViÖc biÕn ®æi t¬ng tù nh viÖc nhãm c¸c ®èi tîng hay ph©n lo¹i. Sù kh¸c biÖt kh«ng lín l»m n»m ë ph¬ng ph¸p biÓu diÔn c¸c kÕt qu¶. Nh÷ng c©u hái mµ viÖc biÕn ®æi cã thÓ tr¶ lêi lµ bµn ®å cña toµn bé ®èi tîng nh thÕ nµo, cã bao nhiªu vïng trªn b¶n ®å cã thÓ ph©n biÖt ®îc, h×nh d¸ng c¸c vïng ®ã nh thÕ nµo… Mét trong nh÷ng øng dông cña biÕn ®æi lµ tiÒn xö lý sè liÖu. Th«ng qua tiÒn xö lý, c¸c ®èi tîng ®iÓn h×nh ®îc chän tõ tËp v« sè c¸c ®èi tîng ngÉu nhiªn nhËn ®îc, lo¹i trõ ®îc c¸c ®èi tîng d thõa hay trïng lÆp. §iÒu nµy rÊt quan träng khi chän c¸c ®èi tîng lµm mÉu häc cho m¹ng truyÒn th¼ng huÊn luyÖn b»ng gi¶i thuËt BP ®Ò cËp ë ch¬ng 3. Dù b¸o c¸c sù kiÖn phô thuéc thêi gian LÜnh vùc nghiªn cøu c¸c qu¸ tr×nh phô thuéc thêi gian lµ mét trong nh÷ng lÜnh vùc chÝnh trong nghiªn cøu ®iÒu khiÓn qu¸ tr×nh. ë ®©y, m« h×nh dù b¸o ®îc x©y dùng dùa trªn mét chuçi sè liÖu ®îc ghi nhËn theo thêi gian. Trong m« h×nh nµy, c¸c biÕn cña tÝn hiÖu vµo vµ tÝn hiÖu ra vÒ c¬ b¶n lµ gièng nhau. ChØ mét ®iÒu kh¸c biÖt lµ, tÝn hiÖu vµo lµ c¸c gi¸ trÞ hiÖn t¹i vµ qu¸ khø cña c¸c biÕn qu¸ tr×nh, tÝn hiÖu ra lµ gi¸ trÞ dù b¸o trong t¬ng lai cña c¸c biÕn qu¸ tr×nh ®ã. 11 Ch¬ng 2 Gi¶i thuËt di truyÒn Ch¬ng nµy tr×nh bµy c¸c vÊn ®Ò sau: 2.1. Tæng quan vÒ gi¶i thuËt di truyÒn 2.2. Gi¶i thuËt di truyÒn ®¬n gi¶n 2.3. NÒn t¶ng to¸n häc cña gi¶i thuËt di truyÒn 2.4. Nh÷ng c¶i tiÕn tiÕp theo cña gi¶i thuËt di truyÒn 2.1. Tæng quan vÒ gi¶i thuËt di truyÒn Gi¶i thuËt GA thuéc líp c¸c gi¶i thuËt t×m kiÕm tiÕn hãa. Kh¸c víi phÇn lín c¸c gi¶i thuËt t×m kiÕm theo ®iÓm, gi¶i thuËt GA thùc hiÖn t×m kiÕm song song trªn mét tËp gäi lµ quÇn thÓ c¸c lêi gi¶i cã thÓ. Th«ng qua viÖc ¸p dông c¸c to¸n tö di truyÒn, gi¶i thuËt GA trao ®æi th«ng tin gi÷a c¸c cùc trÞ vµ do ®ã lµm gi¶m thiÓu kh¶ n¨ng kÕt thóc gi¶i thuËt t¹i mét cùc trÞ ®Þa ph¬ng. Trong thùc tÕ, gi¶i thuËt GA ®· ®îc ¸p dông thµnh c«ng trong nhiÒu lÜnh vùc bao gåm c¶ thñ tôc huÊn luyÖn m¹ng n¬ ron [7, 11]. Néi dung gi¶i thuËt di truyÒn Gi¶i thuËt GA lÇn ®Çu tiªn ®îc t¸c gi¶ J. H. Holland giíi thiÖu vµo n¨n 1962 [12, 14]. Gi¶i thuËt GA m« pháng qu¸ tr×nh tån t¹i cña c¸c c¸ thÓ cã ®é phï hîp tèt th«ng qua qu¸ tr×nh tiÕn hãa trong tù nhiªn, sao cho khi thùc thi gi¶i thuËt, quÇn thÓ c¸c lêi gi¶i ban ®Çu tiÕn ho¸ dÇn tíi lêi gi¶i mong muèn. Gi¶i thuËt GA duy tr× mét quÇn thÓ c¸c lêi gi¶i cã thÓ cña bµi to¸n tèi u hãa. Mçi lêi gi¶i gäi lµ mét c¸ thÓ hay mét nhiÔm s¾c thÓ, thêng ®îc m· hãa díi d¹ng mét chuçi c¸c gen, gi¸ trÞ cña c¸c gen cã trong chuçi ®îc lÊy tõ mét b¶ng c¸c ký tù ®îc ®Þnh nghÜa tríc. Mçi chuçi gen ®îc liªn kÕt víi mét gi¸ trÞ gäi lµ gi¸ trÞ thÝch nghi, cßn gäi lµ ®é phï hîp cña chuçi. §é phï hîp cña mçi chuçi gen ®¸nh gi¸ ®é thÝch nghi cña nã víi m«i trêng (®é tèt xÊu cña lêi gi¶i) vµ ®îc dïng trong qu¸ tr×nh chän läc. QuÇn thÓ míi ®îc t¹o ra b»ng c¸ch sö dông c¸c qu¸ tr×nh chän läc, lai ghÐp vµ ®ét biÕn. Qu¸ tr×nh chän läc sao chÐp c¸c c¸ thÓ cã ®é phï hîp tèt vµo mét quÇn thÓ t¹m thêi ®îc gäi lµ quÇn thÓ bè mÑ. C¸c c¸ thÓ trong quÇn thÓ bè mÑ ®îc ghÐp ®«i mét c¸ch ngÉu nhiªn vµ tiÕn hµnh lai ghÐp t¹o ra c¸c c¸ thÓ con. Sau khi tiÕn hµnh qu¸ tr×nh lai ghÐp, gi¶i thuËt GA m« pháng mét qu¸ tr×nh kh¸c trong tù nhiªn 12 lµ qu¸ tr×nh ®ét biÕn, trong ®ã c¸c gen cña c¸c c¸ thÓ con tù thay ®æi gi¸ trÞ víi mét x¸c xuÊt nhá. Nh vËy, gi¶i thuËt GA xuÊt ph¸t víi tËp lêi gi¶i ban ®Çu, th«ng qua nhiÒu bíc trong qu¸ tr×nh tiÕn ho¸ h×nh thµnh c¸c tËp lêi gi¶i míi tèt h¬n, vµ cuèi cïng t×m ra lêi gi¶i ®ñ tèt chÊp nhËn ®îc (lêi gi¶i gÇn víi lêi gi¶i tèi u). Díi ®©y lµ s¬ ®å khèi cña gi¶i thuËt di truyÒn 2.1. S¬ ®å khèi cña gi¶i thuËt di truyÒn C¸c bíc chÝnh trong viÖc ¸p dông gi¶i thuËt di truyÒn §Ó ¸p dông gi¶i thuËt GA gi¶i mét bµi to¸n trong thùc tÕ, c¸c bíc sau ®©y cÇn ®îc thùc hiÖn: Bíc 1 : Chän tËp lêi gi¶i ban ®Çu cho bµi to¸n. Bíc 2 : M· ho¸ c¸c lêi gi¶i díi d¹ng c¸c chuçi, th«ng thêng c¸c lêi gi¶i ®îc m· hãa thµnh c¸c chuçi nhÞ ph©n. Bíc 3 : T×m hµm sè thÝch nghi (hµm phï hîp) cho bµi to¸n vµ tÝnh gi¸ trÞ thÝch nghi cho mçi lêi gi¶i , cßn gäi lµ gi¸ trÞ ®é phï hîp. 13 Bíc 4 : Dùa trªn gi¸ trÞ thÝch nghi cña mçi lêi gi¶i ®Ó thùc hiÖn chän läc (selecttion) vµ tiÕn hãa c¸c lêi gi¶i. C¸c ph¬ng ph¸p tiÕn hãa gåm lai ghÐp (crossover) vµ ®ét biÕn (mutation). Bíc 5 : TÝnh c¸c gi¸ trÞ thÝch nghi cho c¸c lêi gi¶i míi vµ lo¹i bá c¸c lêi gi¶i kÐm nhÊt, chØ gi÷ l¹i mét sè nhÊt ®Þnh c¸c lêi gi¶i Bíc 6 : NÕu cha t×m ®îc lêi gi¶i tèi u hay cha hÕt h¹n chu kú x¸c ®Þnh th× trë l¹i Bíc 4 ®Ó t×m lêi gi¶i míi. Bíc 7 : T×m ®îc lêi gi¶i tèi u chÊp nhËn ®îc hoÆc nÕu chu kú cho phÐp ®· chÊm døt th× b¸o c¸o kÕt qu¶ tÝnh ®îc. Cã nhiÒu lùa chän kh¸c nhau cho tõng vÊn ®Ò trªn. PhÇn tiÕp theo sÏ ®a ra c¸ch lùa chän theo J.H.Holland khi thiÕt kÕ phiªn b¶n gi¶i thuËt GA ®Çu tiªn. Gi¶i thuËt nµy ®îc gäi lµ gi¶i thuËt di truyÒn ®¬n gi¶n (SGA) [12,14] 2.2. Gi¶i thuËt di truyÒn ®¬n gi¶n J. H. Holland sö dông m· hãa nhÞ ph©n ®Ó biÓu diÔn c¸c c¸ thÓ, lý do lµ phÇn lín c¸c bµi to¸n tèi u hãa, lêi gi¶i ®Òu cã thÓ ®îc m· hãa thµnh chuçi nhÞ ph©n kh¸ ®¬n gi¶n [14]. Mçi lêi gi¶i ®îc m· hãa thµnh mét chuçi bÝt, mçi chuçi bÝt sau ®ã ®îc gi¶i m· ®Ó lÊy l¹i gi¸ trÞ thùc vµ gi¸ trÞ hµm môc tiªu ®îc tÝnh theo gi¸ trÞ thùc nµy. Tuú tõng bµi to¸n cùc tiÓu hay cùc ®¹i, gi¸ trÞ hµm môc tiªu ®îc biÕn ®æi thµnh gi¸ trÞ thÝch nghi cho tõng chuçi. QuÇn thÓ chuçi ban ®Çu ®îc khëi ®éng ngÉu nhiªn vµ sau ®ã ®îc tiÕn hãa tõ thÕ hÖ nµy sang thÕ hÖ kh¸c b»ng c¸ch sö dông ba to¸n tö : Chän läc (selecttion) Lai t¹o (crossover) §ét biÕn (mutation) Chän läc Chän läc lµ viÖc lùa chän c¸c c¸ thÓ ®Ó tham gia vµo c¸c pha tiÕp theo cña qu¸ tr×nh tiÕn hãa, viÖc lùa chän nµy phô thuéc vµo gi¸ trÞ thÝch nghi cña c¸ thÓ ®ã, nghÜa lµ nh÷ng c¸ thÓ nµo cã gi¸ trÞ thÝch nghi cao h¬n sÏ cã kh¶ n¨ng cã nhiÒu con ch¸u h¬n trong c¸c thÕ hÖ tiÕp theo. Gi¸ trÞ thÝch nghi quyÕt ®Þnh sù tån t¹i hay diÖt vong cña mét c¸ thÓ. Gi¸ trÞ thÝch nghi ®îc tÝnh tõ hµm thÝch nghi, viÖc ¸nh x¹ tõ hµm môc tiªu sang hµm thÝch nghi ®îc tr×nh bµy ë phÇn sau. M« h×nh chän läc thêng ®îc dïng lµ b¸nh xe xæ sè (roulette wheel selection). Gi¶i thuËt GA sö dông mét vßng trßn trong ®ã mçi c¸ thÓ chiÕm mét phÇn t¬ng víi ®é réng lµ x¸c suÊt chän läc cña mçi c¸ thÓ. X¸c suÊt chän läc pi cña c¸ thÓ vi ®îc tÝnh theo c«ng thøc pi = eval(vi)/F, trong ®ã eval(vi) lµ gi¸ trÞ thÝch nghi cña c¸ thÓ vi, F lµ tæng gi¸ trÞ thÝch nghi cña toµn quÇn thÓ F=(eval(vi). 14 Mçi khi thùc hiÖn mét lÇn quay vßn trßn, mét øng cö viªn ®îc chän cho viÖc lai ghÐp. ViÖc quay vßng trßn ®îc thùc hiÖn qua nh÷ng bíc sau: Bíc 1 : §¸nh sè c¸c c¸ thÓ trong quÇn thÓ. TÝnh tæng gi¸ trÞ thÝch nghi cña toµn quÇn thÓ vµ gäi nã lµ tæng thÝch nghi (Total fitness). Bíc 2 : Sinh mét sè ngÉu nhiªn n trong kho¶ng tõ 0 ®Õn tæng thÝch nghi. Bíc 3 : Tr¶ l¹i c¸ thÓ ®Çu tiªn trong quÇn thÓ cã gi¸ trÞ thÝch nghi cña nã céng víi gi¸ trÞ thÝch nghi cña c¸c c¸ thÓ tríc ®Êy lín h¬n hoÆc b»ng n. Lai ghÐp To¸n tö chän läc nh»m t×m ra nh÷ng c¸ thÓ tèt nhÊt nhng kh«ng t¹o ra c¸ thÓ míi. Tuy vËy, trong tù nhiªn, c¸c con sÏ thõa hëng di truyÒn nh÷ng ®Æc tÝnh tèt tõ c¶ cha vµ mÑ. To¸n tö t¸c ®éng trªn c¸c c¸ thÓ cha vµ mÑ ®Ó t¹o ra c¸c con lai tèt ® îc gäi lµ lai ghÐp. Chóng chØ ®îc ¸p dông lªn cÆp cha mÑ ®îc chän víi x¸c suÊt lai ghÐp ký hiÖu lµ Pcross [14]. X¸c xuÊt nµy cho chóng ta sè lîng Pcross*pop_size c¸ thÓ ®îc dïng cho ho¹t ®éng lai ghÐp víi pop_size lµ kÝch thíc quÇn thÓ. Ngoµi c¸c c¸ thÓ ®ã ra, c¸c c¸ thÓ con lµ b¶n sao trùc tiÕp tõ cha mÑ. To¸n tö lai ghÐp trong gi¶i thuËt SGA lµ to¸n tö lai ghÐp mét ®iÓm c¾t. Gi¶ sö chuçi c¸ thÓ cã ®é dµi L (chuçi cã L bÝt), to¸n tõ lai ghÐp ®îc tiÕn hµnh qua hai giai ®o¹n lµ :  Ph¸t sinh mét sè ngÉu nhiªn r trong miÒn [0;1]  NÕu r < Pcross chän c¸ thÓ ®ã ®Ó lai ghÐp. Sau ®ã, kÕt hîp c¸c c¸ thÓ ®îc chän mét c¸ch ngÉu nhiªn. Víi mçi cÆp c¸ thÓ, ph¸t sinh mét sè ngÉu nhiªn pos tõ miÒn [1, L]. Sè pos b¸o hiÖu vÞ trÝ cña ®iÓm lai ghÐp. Hai c¸ thÓ : (b1b2…bposbpos+1…bL) vµ (ccc2…cposcpos+1…cL) ®îc thay thÕ bëi cÆp con ch¸u : (b1b2…bposcpos+1…cL) vµ (ccc2…cposbpos+1…bL) §ét biÕn C¸c to¸n tö ®ét biÕn nh»m t¹o ra c¸c th«ng tin míi trong quÇn thÓ thu ®îc sau khi lai ghÐp t¹i c¸c vÞ trÝ bÝt nµo ®ã (quÇn thÓ cã pop_size c¸ thÓ, mçi c¸ thÓ cã ®é dµi L bÝt). §ét biÕn ®îc ¸p dông víi x¸c suÊt rÊt nhá p m, v× nÕu x¸c suÊt pm lín, gi¶i thuËt GA trë thµnh gi¶i thuËt t×m kiÕm ngÉu nhiªn. Sè lîng bÝt ®ét biÕn lµ pm*L*pop_size bÝt. Mçi bÝt cã c¬ héi ®ét biÕn nh nhau vµ ®îc thay ®æi tõ 0 thµnh 1 vµ ngîc l¹i. Cã thÓ xö lý theo c¸ch sau: Víi mçi c¸ thÓ trong quÇn thÓ vµ mçi bÝt trong c¸ thÓ: 15  Ph¸t sinh mét sè ngÉu nhiªn r trong miÒn [0,1].  NÕu r < pm, tiÕn hµnh ®ét biÕn t¹i bÝt ®ã. C¸c thao t¸c nµy ®îc ¸p dông lÆp l¹i cho tíi khi c¸c c¸ thÓ con ch¸u t¨ng trëng tíi kÝch cì mong muèn cña quÇn thÓ. Tãm l¹i, ba to¸n tö nªu trªn ®îc tiÕn hµnh trong mét vßng lÆp cho ®Õn khi c¸c chuçi con chiÕm toµn bé quÇn thÓ míi. QuÇn thÓ míi gåm c¸c c¸ thÓ cña ba lo¹i: bÞ ®ét biÕn sau khi lai ghÐp; lai ghÐp nhng kh«ng bÞ ®ét biÕn; kh«ng lai ghÐp vµ còng kh«ng bÞ ®ét biÕn mµ chØ ®¬n gi¶n lµ sao chÐp l¹i. Hµm thÝch nghi (fitness) V× hµm thÝch nghi ph¶i nhËn gi¸ trÞ kh«ng ©m nªn cÇn ph¶i x©y dùng ¸nh x¹ tõ hµm môc tiªu ®ang xÐt cña bµi to¸n sang hµm thÝch nghi th«ng qua mét hoÆc nhiÒu lÇn ¸nh x¹. NÕu bµi to¸n tèi u lµ cùc tiÓu mét hµm gi¸ g(x), viÖc chuyÓn tõ hµm gi¸ sang hµm thÝch nghi ®Ó sö dông trong GA nh sau: f(x) = Cmax - g(x) khi g(x) < Cmax f(x) = 0 trong c¸c trêng hîp cßn l¹i ë ®©y, Cmax lµ tham sè ®Çu vµo. VÝ dô, cã thÓ lÊy C max lµ gi¸ trÞ lín nhÊt trong quÇn thÓ hiÖn t¹i, hoÆc lín nhÊt sau k vßng lÆp. Khi hµm môc tiªu t¨ng hoÆc ®ang xÐt bµi to¸n cùc ®¹i hãa mét hµm h÷u dông u(x), cã thÓ chuyÓn sang hµm thÝch nghi nh sau: f(x) = u(x) + Cmin khi u(x) + Cmin > 0 f(x) = 0 trong c¸c trêng hîp cßn l¹i ë ®©y, Cmin lµ tham sè ®Çu vµo, cã thÓ lµ gi¸ trÞ tuyÖt ®èi bÐ nhÊt trong quÇn thÓ hiÖn t¹i hoÆc trong k vßng lÆp cuèi cïng … Tû lÖ hãa gi¸ trÞ thÝch nghi ViÖc ®iÒu chØnh sè lîng con cña mçi c¸ thÓ trong nh÷ng quÇn thÓ nhá lµ ®iÒu rÊt quan träng trong viÖc sö dông gi¶i thuËt SGA ®Ó gi¶i c¸c bµi to¸n tèi u. Vµo lóc khëi ®éng vµ mét sè thÕ hÖ ban ®Çu, c¸c quÇn thÓ thêng cã mét sè c¸ thÓ siªu kháe so víi ®¹i ®a sè c¸ thÓ cßn l¹i. NÕu ®Ó nguyªn mµ ¸p dông quy t¾c chän läc th× c¸c c¸ thÓ siªu kháe sÏ chiÕm gÇn toµn bé quÇn thÓ tiÕp theo v× chóng cã rÊt nhiÒu con. §iÒu nµy dÉn ®Õn viÖc héi tô sím kh«ng mong muèn. Vµo giai ®o¹n cuèi, khi sè thÕ hÖ kh¸ lín, gi¸ trÞ thÝch nghi trung b×nh cña toµn quÇn thÓ cã thÓ gÇn víi gi¸ trÞ thÝch nghi cña c¸ thÓ tèt nhÊt, nÕu ®Ó tù nhiªn th× c¸c c¸ thÓ trung b×nh còng cã sè con t¬ng ®¬ng víi c¸c c¸ thÓ tèt nhÊt trong thÕ hÖ tiÕp theo. NÕu ®iÒu nµy x¶y ra th× gi¶i thuËt SGA trë thµnh gi¶i thuËt t×m kiÕm ngÉu nhiªn gi÷a c¸c c¸ thÓ trung b×nh. C¶ 16 hai khã kh¨n lóc b¾t ®Çu vµ giai ®o¹n kÕt thóc nªu trªn cã thÓ vît qua b»ng viÖc tû lÖ hãa gi¸ trÞ thÝch nghi toµn quÇn thÓ. Mét trong nh÷ng thñ tôc tû lÖ hãa ®¬n gi¶n vµ hiÖu qu¶ lµ tû lÖ hãa tuyÕn tÝnh. NÕu gäi gi¸ trÞ thÝch nghi ban ®Çu (cha tû lÖ hãa) lµ f vµ gi¸ trÞ thÝch nghi sau khi tû lÖ hãa lµ f’ th× ph¬ng tr×nh tû lÖ hãa tuyÕn tÝnh lµ : f’ = a.f + b C¸c hÖ sè a, b cã thÓ ®îc chän theo mét sè c¸ch.Tuy nhiªn, trong mäi trêng hîp, mong muèn r»ng gi¸ trÞ thÝch nghi trung b×nh sau khi tû lÖ hãa cña toµn quÇn thÓ f’ave b»ng gi¸ trÞ thÝch nghi trung b×nh cña toµn quÇn thÓ tríc khi tû lÖ hãa. §iÓu nµy ®¶m b¶o r»ng, c¸c c¸ thÓ trung b×nh sÏ ®ãng gãp mét con cho thÕ hÖ tiÕp theo. §Ó kiÓm so¸t sè con cho thµnh viªn siªu kháe, mét ph¬ng tr×nh kh¸c ®îc chän lµ f’max = Cmult*fave , ë ®©y Cmult lµ sè con cña c¸ thÓ cã gi¸ trÞ thÝch nghi tèt nhÊt trong quÇn thÓ. §èi víi c¸c quÇn thÓ nhá (50 obj(Xbest)) Xbest = X; } while (k - Xem thêm -