Giáo trình Trí tuệ nhân tạo (Phần 2)

61 trang ngocly 110

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Trí tuệ nhân tạo (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_tri_tue_nhan_tao_phan_2.pdf

Nội dung text: Giáo trình Trí tuệ nhân tạo (Phần 2)

Ch−¬ng V C¸c chiÕn l−îc t×m kiÕm tèi −u VÊn ®Ò t×m kiÕm tèi −u, mét c¸ch tæng qu¸t, cã thÓ ph¸t biÓu nh− sau. Mçi ®èi t−îng x trong kh«ng gian t×m kiÕm ®−îc g¾n víi mét sè ®o gi¸ trÞ cña ®èi t−îng ®ã f(x), môc tiªu cña ta lμ t×m ®èi t−îng cã gi¸ trÞ f(x) lín nhÊt (hoÆc nhá nhÊt) trong kh«ng gian t×m kiÕm. Hμm f(x) ®−îc gäi lμ hμm môc tiªu. Trong ch−¬ng nμy chóng ta sÏ nghiªn cøu c¸c thuËt to¸n t×m kiÕm sau: C¸c kü thuËt t×m ®−êng ®i ng¾n nhÊt trong kh«ng gian tr¹ng th¸i: ThuËt to¸n A*, thuËt to¸n nh¸nh_vμ_cËn. C¸c kü thuËt t×m kiÕm ®èi t−îng tèt nhÊt: T×m kiÕm leo ®åi, t×m kiÕm gradient, t×m kiÕm m« pháng luyÖn kim. T×m kiÕm b¾t ch−íc sù tiÕn hãa: thuËt to¸n di truyÒn. I. T×m ®−êng ®i ng¾n nhÊt Trong c¸c ch−¬ng tr−íc chóng ta ®· nghiªn cøu vÊn ®Ò t×m kiÕm ®−êng ®i tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i kÕt thóc trong kh«ng gian tr¹ng th¸i. Trong môc nμy, ta gi¶ sö r»ng, gi¸ ph¶i tr¶ ®Ó ®−a tr¹ng th¸i a tíi tr¹ng th¸i b (bëi mét to¸n tö nμo ®ã) lμ mét sè k(a,b) ≥ 0, ta sÏ gäi sè nμy lμ ®é dμi cung (a,b) hoÆc gi¸ trÞ cña cung (a,b) trong ®å thÞ kh«ng gian tr¹ng th¸i. §é dμi cña c¸c cung ®−îc x¸c ®Þnh tïy thuéc vμo vÊn ®Ò. Ch¼ng h¹n, trong bμi to¸n t×m ®−êng ®i trong b¶n ®å giao th«ng, gi¸ cña cung (a,b) chÝnh lμ ®é dμi cña ®−êng nèi thμnh phè a víi thμnh phè b. §é dμi ®−êng ®i ®−îc x¸c ®Þnh lμ tæng ®é dμi cña c¸c cung trªn ®−êng ®i. VÊn ®Ò cña chóng ta trong môc nμy, t×m ®−êng ®i ng¾n nhÊt tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i ®Ých. Kh«ng gian t×m kiÕm ë ®©y bao gåm tÊt c¶ c¸c ®−êng ®i tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i kÕt thóc, hμm môc tiªu ®−îc x¸c ®Þnh ë ®©y lμ ®é dμi cña ®−êng ®i. Chóng ta cã thÓ gi¶i quyÕt vÊn ®Ò ®Æt ra b»ng c¸ch t×m tÊt c¶ c¸c ®−êng ®i cã thÓ cã tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i ®Ých (ch¼ng h¹n, sö sông c¸c kü thuËt t×m kiÕm mï), sau ®ã so s¸nh ®é dμi cña chóng, ta sÏ t×m ra ®−êng ®i ng¾n nhÊt. Thñ tôc t×m kiÕm nμy th−êng ®−îc gäi lμ thñ tôc b¶o tμng Anh Quèc (British Museum Procedure). Trong thùc tÕ, kü thuËt nμy kh«ng thÓ ¸p dông ®−îc, v× c©y t×m kiÕm th−êng rÊt lín, viÖc t×m ra tÊt c¶ c¸c ®−êng ®i cã thÓ ®ßi hái rÊt nhiÒu thêi gian. Do ®ã chØ cã mét c¸ch t¨ng hiÖu qu¶ t×m kiÕm lμ sö dông c¸c hμm ®¸nh gi¸ ®Ò h−íng dÉn t×m kiÕm. C¸c ph−¬ng ph¸p t×m kiÕm ®−êng ®i ng¾n nhÊt mμ chóng ta sÏ tr×nh bμy ®Òu lμ c¸c ph−¬ng ph¸p t×m kiÕm heuristic. Gi¶ sö u lμ mét tr¹ng th¸i ®¹t tíi (cã d−êng ®i tõ tr¹ng th¸i ban ®Çu u0 tíi u). Ta x¸c ®Þnh hai hμm ®¸nh gi¸ sau: g(u) lμ ®¸nh gi¸ ®é dμi ®−êng ®i ng¾n nhÊt tõ u0 tíi u (§−êng ®i tõ u0 tíi tr¹ng th¸i u kh«ng ph¶i lμ tr¹ng th¸i ®Ých ®−îc gäi lμ ®−êng ®i mét phÇn, ®Ó ph©n biÖt víi ®−êng ®i ®Çy ®ñ, lμ ®−êng ®i tõ u0 tíi tr¹ng th¸i ®Ých). 51
h(u) lμ ®¸nh gi¸ ®é dμi ®−êng ®i ng¾n nhÊt tõ u tíi tr¹ng th¸i ®Ých. Hμm h(u) ®−îc gäi lμ chÊp nhËn ®−îc (hoÆc ®¸nh gi¸ thÊp) nÕu víi mäi tr¹ng th¸i u, h(u) ≤ ®é dμi ®−êng ®i ng¾n nhÊt thùc tÕ tõ u tíi tr¹ng th¸i ®Ých. Ch¼ng h¹n trong bμi to¸n t×m ®−êng ®i ng¾n nhÊt trªn b¶n ®å giao th«ng, ta cã thÓ x¸c ®Þnh h(u) lμ ®é dμi ®−êng chim bay tõ u tíi ®Ých. Ta cã thÓ sö dông kü thuËt t×m kiÕm leo ®åi víi hμm ®¸nh gi¸ h(u). TÊt nhiªn ph−¬ng ph¸p nμy chØ cho phÐp ta t×m ®−îc ®−êng ®i t−¬ng ®èi tèt, ch−a ch¾c ®· lμ ®−êng ®i tèi −u. Ta còng cã thÓ sö dông kü thuËt t×m kiÕm tèt nhÊt ®Çu tiªn víi hμm ®¸nh gi¸ g(u). Ph−¬ng ph¸p nμy sÏ t×m ra ®−êng ®i ng¾n nhÊt, tuy nhiªn nã cã thÓ kÐm hiÖu qu¶. §Ó t¨ng hiÖu qu¶ t×m kiÕm, ta sö dông hμm ®¸nh gi¸ míi : f(u) = g(u) + h(u) Tøc lμ, f(u) lμ ®¸nh gi¸ ®é dμi ®−êng ®i ng¾n nhÊt qua u tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i kÕt thóc. I.1 ThuËt to¸n A* H×nh 5.1 §å thÞ kh«ng gian tr¹ng th¸i víi hμm ®¸nh gi¸ ThuËt to¸n A* lμ thuËt to¸n sö dông kü thuËt t×m kiÕm tèt nhÊt ®Çu tiªn víi hμm ®¸nh gi¸ f(u). §Ó thÊy ®−îc thuËt to¸n A* lμm viÖc nh− thÕ nμo, ta xÐt ®å thÞ kh«ng gian tr¹ng th¸i trong h×nh 5.1. Trong ®ã, tr¹ng th¸i ban ®Çu lμ tr¹ng th¸i A, tr¹ng th¸i ®Ých lμ B, c¸c sè ghi c¹nh c¸c cung lμ ®é dμi ®−êng ®i, c¸c sè c¹nh c¸c ®Ønh lμ gi¸ trÞ cña hμm h. §Çu tiªn, ph¸t triÓn ®Ønh A sinh ra c¸c ®Ønh con C, D, E vμ F. TÝnh gi¸ trÞ cña hμm f t¹i c¸c ®Ønh nμy ta cã: g(C) = 9, f(C) = 9 + 15 = 24, g(D) = 7, f(D) = 7 + 6 = 13, g(E) = 13, f(E) = 13 + 8 = 21, g(F) = 20, f(F) = 20 +7 = 27 Nh− vËy ®Ønh tèt nhÊt lμ D (v× f(D) = 13 lμ nhá nhÊt). Ph¸t triÓn D, ta nhËn ®−îc c¸c ®Ønh con H vμ E. Ta ®¸nh gi¸ H vμ E (míi): g(H) = g(D) + §é dμi cung(D, H) = 7 + 8 = 15, f(H) = 15 + 10 = 25. §−êng ®i tíi E qua D cã ®é dμi: g(E) = g(D) + §é dμi cung(D, E) = 7 + 4 = 11. 52
VËy ®Ønh E míi cã ®¸nh gi¸ lμ f(E) = g(E) + h(E) = 11 + 8 = 19. Trong sè c¸c ®Ønh cho ph¸t triÓn, th× ®Ønh E víi ®¸nh gi¸ f(E) = 19 lμ ®Ønh tèt nhÊt. Ph¸t triÓn ®Ønh nμy, ta nhËn ®−îc c¸c ®Ønh con cña nã lμ K vμ I. Chóng ta tiÕp tôc qu¸ tr×nh trªn cho tíi khi ®Ønh ®−îc chän ®Ó ph¸t triÓn lμ ®Ønh kÕt thóc B, ®é dμi ®−êng ®i ng¾n nhÊt tíi B lμ g(B) = 19. Qu¸ tr×nh t×m kiÕm trªn ®−îc m« t¶ bëi c©y t×m kiÕm trong h×nh 5.2, trong ®ã c¸c sè c¹nh c¸c ®Ønh lμ c¸c gi¸ trÞ cña hμm ®¸nh gi¸ f(u). H×nh 5.2 C©y t×m kiÕm theo thuËt to¸n A* procedure A*; begin 1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu; 2. loop do 2.1 if L rçng then {th«ng b¸o thÊt b¹i; stop}; 2.2 Lo¹i tr¹ng th¸i u ë ®Çu danh s¸ch L; 2.3 if u lμ tr¹ng th¸i ®Ých then {th«ng b¸o thμnh c«ng; stop} 2.4 for mçi tr¹ng th¸i v kÒ u do {g(v) ← g(u) + k(u,v); f(v) ← g(v) + h(v); §Æt v vμo danh s¸ch L;} 2.5 S¾p xÕp L theo thø tù t¨ng dÇn cña hμm f sao cho tr¹ng th¸i cã gi¸ trÞ cña hμm f nhá nhÊt ë ®Çu danh s¸ch; end; Chóng ta ®−a ra mét sè nhËn xÐt vÒ thuËt to¸n A*. • Ng−êi ta chøng minh ®−îc r»ng, nÕu hμm ®¸nh gi¸ h(u) lμ ®¸nh gi¸ thÊp nhÊt (tr−êng hîp ®Æc biÖt, h(u) = 0 víi mäi tr¹ng th¸i u) th× thuËt to¸n A* lμ thuËt to¸n tèi −u, tøc lμ 53
nghiÖm mμ nã t×m ra lμ nghiÖm tèi −u. Ngoμi ra, nÕu ®é dμi cña c¸c cung kh«ng nhá h¬n mét sè d−¬ng δ nμo ®ã th× thuËt to¸n A* lμ thuËt to¸n ®Çy ®ñ theo nghÜa r»ng, nã lu«n dõng vμ t×m ra nghiÖm. Chóng ta chøng minh tÝnh tèi −u cña thuËt to¸n A*. Gi¶ sö thuËt to¸n dõng l¹i ë ®Ønh kÕt thóc G víi ®é dμi ®−êng ®i tõ tr¹ng th¸i ban ®Çu u0 tíi G lμ g(G). V× G lμ ®Ønh kÕt thóc, ta cã h(G) = 0 vμ f(G) = g(G) + h(G) = g(G). Gi¶ sö nghiÖm tèi −u lμ ®−êng ®i tõ u0 tíi ®Ønh kÕt thóc G1 víi ®é dμi l. Gi¶ sö ®−êng ®i nμy “tho¸t ra” khái c©y t×m kiÕm t¹i ®Ønh l¸ n (Xem h×nh 5.3). Cã thÓ xÈy ra hai kh¶ n¨ng: n trïng víi G1 hoÆc kh«ng. NÕu n lμ G1 th× v× G ®−îc chän ®Ó ph¸t triÓn tr−íc G1, nªn f(G) ≤ f(G1), do ®ã g(G) ≤ g(G1)= l. NÕu n ≠ G1 th× do h(u) lμ hμm ®¸nh gi¸ thÊp, nªn f(n) = g(n) + h(n) ≤ l. MÆt kh¸c, còng do G ®−îc chän ®Ó ph¸t triÓn tr−íc n, nªn f(G) ≤ f(n), do ®ã, g(G) ≤ 1. H×nh 5.3 §Ønh l¸ n cña c©y t×m kiÕm n»m trªn ®−êng ®i tèi −u Nh− vËy, ta ®· chøng minh ®−îc r»ng ®é dμi cña ®−êng ®i mμ thuËt to¸n t×m ra g(G) kh«ng dμi h¬n ®é dμi l cña ®−êng ®i tèi −u. VËy nã lμ ®é dμi ®−êng ®i tèi −u. • Trong tr−êng hîp hμm ®¸nh gi¸ g(u) = 0 víi mäi u, thuËt to¸n A* chÝnh lμ thuËt to¸n t×m kiÕm tèt nhÊt ®Çu tiªn víi hμm ®¸nh gi¸ g(u) mμ ta ®· nãi ®Õn. • ThuËt to¸n A* ®· ®−îc chøng tá lμ thuËt to¸n hiÖu qu¶ nhÊt trong sè c¸c thuËt to¸n ®Çy ®ñ vμ tèi −u cho vÊn ®Ò t×m kiÕm ®−êng ®i ng¾n nhÊt. I.2 ThuËt to¸n t×m kiÕm nh¸nh-vμ-cËn ThuËt to¸n nh¸nh_vμ_cËn lμ thuËt to¸n sö dông t×m kiÕm leo ®åi víi hμm ®¸nh gi¸ f(u). Trong thuËt to¸n nμy, t¹i mçi b−íc khi ph¸t triÓn tr¹ng th¸i u, th× ta sÏ chän tr¹ng th¸i tèt nhÊt v (f(v) nhá nhÊt) trong sè c¸c tr¹ng th¸i kÒ u ®Ó ph¸t triÓn ë b−íc sau. §i xuèng cho tíi khi gÆp tr¹ng th¸i v lμ ®Ých, hoÆc gÆp tr¹ng th¸i v kh«ng cã ®Ønh kÒ, hoÆc gÆp tr¹ng th¸i v mμ g(v) lín h¬n ®é dμi ®−êng ®i tèi −u t¹m thêi, tøc lμ ®−êng ®i ®Çy ®ñ ng¾n nhÊt trong sè c¸c ®−êng ®i ®Çy ®ñ mμ ta ®· t×m ra, hoÆc v ®· ph¸t triÓn nh−ng g(v) hiÖn t¹i lín h¬n g(v) ®−îc l−u, tøc ®−êng ®i míi qua v kh«ng tèt h¬n ®−êng ®i cò qua v. Trong c¸c tr−êng hîp nμy, ta kh«ng ph¸t triÓn ®Ønh v n÷a, hay nãi c¸ch kh¸c, ta quay lªn cha cña v ®Ó tiÕp tôc ®i xuèng tr¹ng th¸i tèt nhÊt trong c¸c tr¹ng th¸i cßn l¹i chê ph¸t triÓn. 54
VÝ dô: Chóng ta l¹i xÐt kh«ng gian tr¹ng th¸i trong h×nh 3.1. Ph¸t triÓn ®Ønh A, ta nhËn ®−îc c¸c ®Ønh con C, D, E vμ F, f(C) = 24, f(D) = 13, f(E) = 21, f(F) = 27. Trong sè nμy D lμ tèt nhÊt, ph¸t triÓn D, sinh ra c¸c ®Ønh con H vμ E, f(H) = 25, f(E) = 19. §i xuèng ph¸t triÓn E, sinh ra c¸c ®Ønh con lμ K vμ I, f(K) = 17, f(I) = 18. §i xuèng ph¸t triÓn K sinh ra ®Ønh B víi f(B) = g(B) = 21. §i xuèng B, v× B lμ ®Ønh ®Ých, vËy ta t×m ®−îc ®−êng ®i tèi −u t¹m thêi víi ®é dμi 21. Tõ B quay lªn K, råi tõ K quay lªn cha nã lμ E. Tõ E ®i xuèng I, f(I) = 18 nhá h¬n ®é dμi ®−êng ®i t¹m thêi (lμ 21). Ph¸t triÓn I sinh ra c¸c con K vμ B, f(K) = 25, f(B) = g(B) = 19. §i xuèng ®Ønh B, v× ®Ønh B lμ ®Ých ta t×m ®−îc ®−êng ®i ®Çy ®ñ míi víi ®é dμi lμ 19 nhá h¬n ®é dμi ®−êng ®i tèi −u t¹m thêi cò (21). VËy ®é dμi ®−êng ®i tèi −u t¹m thêi b©y giê lμ 19. B©y giê tõ B ta l¹i quay lªn c¸c ®Ønh cßn l¹i ch−a ®−îc ph¸t triÓn. Song c¸c ®Ønh nμy ®Òu cã gi¸ trÞ g lín h¬n 19, do ®ã kh«ng cã ®Ønh nμo ®−îc ph¸t triÓn n÷a. Nh− vËy, ta t×m ®−îc ®−êng ®i tèi −u víi ®é dμi 19. C©y t×m kiÕm ®−îc biÓu diÔn trong h×nh 5.4. 14,0 A 27, 20 F 21,13 C 24,9 13,7 D E 25, 15 H H 25,15 E 19, 11 K 22, 20 17, 15 K I 18, 14 B B K 25, 23 21, 21 19, 19 H×nh 5.4 C©y t×m kiÕm nh¸nh_vμ_cËn ThuËt to¸n nh¸nh_vμ_cËn sÏ ®−îc biÓu diÔn bëi thñ tôc Branch_and_Bound. Trong thñ tôc nμy, biÕn cost ®−îc dïng ®Ó l−u ®é dμi ®−êng ®i ng¾n nhÊt. Gi¸ trÞ ban ®Çu cña cost lμ sè ®ñ lín, hoÆc ®é dμi cña mét ®−êng ®i ®Çy ®ñ mμ ta ®· biÕt. 55
procedure Branch_and_Bound; begin 1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu; //c¸c tr¹ng th¸i ch−a ph¸t triÓn vμ // chê duyÖt; 2. Khëi t¹o danh s¸ch M rçng; //c¸c tr¹ng th¸i ®· ph¸t triÓn; 3. G¸n gi¸ trÞ ban ®Çu cho cost; 4. loop do 4.1 if L rçng then stop; 4.2 Lo¹i tr¹ng th¸i u ë ®Çu danh s¸ch L; 4.3 if u lμ tr¹ng th¸i kÕt thóc then {if g(u) ≤ cost then cost ← g(u); Quay l¹i 4.1}; 4.4 if g(u) > cost then Quay l¹i 4.1; 4.5 if u trong M then //®· xÐt ®−êng qua u; if g(u) ≥ gi¸ trÞ g(u) ®−îc l−u trong M then Quay l¹i 4.1; else cËp nhËt gi¸ trÞ g(u) trong M 4.6 Khëi t¹o danh s¸ch L1 rçng; 4.7 for mçi tr¹ng th¸i v kÒ u do {g(v) ← g(u) + k(u,v); f(v) ← g(v) + h(v); §Æt v vμo danh s¸ch L1}; 4.8 if u kh«ng cã trong M then ®Æt u vμo M vμ l−u gi¸ trÞ g(u); 4.9 S¾p xÕp L1 theo thø tù t¨ng cña hμm f; 4.10 ChuyÓn L1 vμo ®Çu danh s¸ch L; end; Ng−êi ta chøng minh ®−îc r»ng, thuËt to¸n nh¸nh_vμ_cËn còng lμ thuËt to¸n ®Çy ®ñ vμ tèi −u nÕu hμm ®¸nh gi¸ h(u) lμ ®¸nh gi¸ thÊp vμ cã ®é dμi c¸c cung kh«ng nhá h¬n mét sè d−¬ng δ nμo ®ã. II. T×m ®èi t−îng tèt nhÊt Trong môc nμy chóng ta sÏ xÐt vÊn ®Ò t×m kiÕm sau. Trªn kh«ng gian t×m kiÕm U ®−îc x¸c ®Þnh hμm gi¸ (hμm môc tiªu) cost, øng víi mçi ®èi t−îng x ∈ U víi mét gi¸ trÞ sè cost(x), sè nμy ®−îc gäi lμ gi¸ trÞ cña x. Chóng ta cÇn t×m mét ®èi t−îng mμ t¹i ®ã hμm gi¸ trÞ lín nhÊt, ta gäi ®èi t−îng ®ã lμ ®èi t−îng tèt nhÊt. Gi¶ sö kh«ng gian t×m kiÕm cã cÊu tróc cho phÐp ta x¸c ®Þnh ®−îc kh¸i niÖm l©n cËn cña mçi ®èi t−îng. Ch¼ng h¹n, U lμ kh«ng gian tr¹ng th¸i th× l©n cËn cña tr¹ng th¸i u gåm tÊt c¶ c¸c tr¹ng th¸i v 56
kÒ u; nÕu U lμ kh«ng gian c¸c vect¬ thùc n-chiÒu th× l©n cËn cña vect¬ x = (x1, x2, xn) gåm tÊt c¶ c¸c vect¬ ë gÇn x theo kho¶ng c¸ch Euclit th«ng th−êng. Trong môc nμy, ta sÏ xÐt kü thuËt t×m kiÕm leo ®åi ®Ó t×m ®èi t−îng tèt nhÊt. Sau ®ã ta sÏ xÐt kü thuËt t×m kiÕm gradient (gradient search). §ã lμ kü thuËt leo ®åi ¸p dông cho kh«ng gian t×m kiÕm lμ kh«ng gian c¸c vect¬ thùc n-chiÒu vμ hμm gi¸ lμ lμ hμm kh¶ vi liªn tôc. Cuèi cïng ta sÏ nghiªn cøu kü thuËt t×m kiÕm m« pháng luyÖn kim( simulated annealing). II.1 T×m kiÕm leo ®åi Kü thuËt t×m kiÕm leo ®åi ®Ó t×m kiÕm ®èi t−îng tèt nhÊt hoμn toμn gièng nh− kü thuËt t×m kiÕm leo ®åi ®Ó t×m tr¹ng th¸i kÕt thóc ®· xÐt trong môc 4.3. NghÜa lμ tõ mét ®Ønh u ta chØ leo lªn ®Ønh tèt nhÊt v (®−îc x¸c ®Þnh bëi hμm gi¸ cost) trong l©n cËn u nÕu ®Ønh nμy "cao h¬n" ®Ønh u, tøc lμ cost(v) > cost(u). Cßn ë ®©y, tõ mét tr¹ng th¸i ta "leo lªn" tr¹ng th¸i kÒ tèt nhÊt (®−îc x¸c ®Þnh bëi hμm gi¸), tiÕp tôc cho tíi khi ®¹t tíi tr¹ng th¸i ®Ých; nÕu ch−a ®¹t tíi tr¹ng th¸i ®Ých mμ kh«ng leo lªn ®−îc n÷a, th× ta tiÕp tôc "tôt xuèng" tr¹ng th¸i tr−íc nã, råi l¹i leo lªn tr¹ng th¸i tèt nhÊt cßn l¹i. Qu¸ tr×nh t×m kiÕm sÏ dõng l¹i ngay khi ta kh«ng leo lªn ®Ønh cao h¬n ®−îc n÷a. Trong thñ tôc leo ®åi sau, biÕn u l−u ®Ønh hiÖn thêi, biÕn v l−u ®Ønh tèt nhÊt (cost(v) nhá nhÊt) trong c¸c ®Ønh ë l©n cËn u. Khi thuËt to¸n dõng, biÕn u sÏ l−u ®èi t−îng t×m ®−îc. procedure Hill_Climbing; begin 1. u ← mét ®èi t−îng ban ®Çu nμo ®ã; 2. loop do 2.1 v lμ tr¹ng th¸i kÒ cña u cã gi¸ trÞ cost lín nhÊt trong c¸c tr¹ng th¸i kÒ 2.2 if cost(v) > cost(u) then u ← v else return u; end; Tèi −u ®Þa ph−¬ng vμ tèi −u toμn côc Râ rμng lμ, khi thuËt to¸n leo ®åi dõng l¹i t¹i ®èi t−¬ng u*, th× gi¸ cña nã cost(u*) lín h¬n gi¸ cña tÊt c¶ c¸c ®èi t−îng n»m trong l©n cËn cña tÊt c¶ c¸c ®èi t−îng trªn ®−êng ®i tõ ®èi t−îng ban ®Çu tíi tr¹ng th¸i u*. Do ®ã nghiÖm u* mμ thuËt to¸n leo ®åi t×m ®−îc lμ tèi −u ®Þa ph−¬ng. CÇn nhÊn m¹nh r»ng kh«ng cã g× ®¶m b¶o nghiÖm ®ã lμ tèi −u toμn côc theo nghÜa lμ cost(u*) lμ lín nhÊt trªn toμn bé kh«ng gian t×m kiÕm. §Ó nhËn ®−îc nghiÖm tèt h¬n b»ng thuËt to¸n leo ®åi, ta cã thÓ ¸p dông lÆp l¹i nhiÒu lÇn thñ tôc leo ®åi xuÊt ph¸t tõ mét d·y c¸c ®èi t−îng ban ®Çu ®−îc chän ngÉu nhiªn vμ l−u l¹i nghiÖm tèt nhÊt qua mçi lÇn lÆp. NÕu sè lÇn lÆp ®ñ lín th× ta cã thÓ t×m ®−îc nghiÖm tèi −u. KÕt qu¶ cña thuËt to¸n leo ®åi phô thuéc rÊt nhiÒu vμo h×nh d¸ng cña “mÆt cong” cña hμm ®¸nh gi¸. NÕu mÆt cong chØ cã mét sè Ýt cùc ®¹i ®Þa ph−¬ng, th× kü thuËt leo ®åi sÏ t×m ra rÊt nhanh cùc ®¹i toμn côc. 57
Song cã nh÷ng vÊn ®Ò mμ mÆt cong cña hμm gi¸ tùa nh− l«ng nhÝm vËy, khi ®ã sö dông kü thuËt leo ®åi ®ßi hái rÊt nhiÒu thêi gian. II.2 T×m kiÕm gradient T×m kiÕm gradient lμ kü thuËt t×m kiÕm leo ®åi ®Ó t×m gi¸ trÞ lín nhÊt (hoÆc nhá nhÊt) cña hμm kh¶ vi liªn tôc f(x) trong kh«ng gian c¸c vect¬ thùc n-chiÒu. Nh− ta ®· biÕt, trong l©n cËn ®ñ nhá cña ®iÓm x = (x1, ,xn), th× hμm f t¨ng nhanh nhÊt theo h−íng cña vect¬ gradient: Do ®ã t− t−ëng cña t×m kiÕm gradient lμ tõ mét ®iÓm ta ®i tíi ®iÓm ë l©n cËn nã theo h−íng cña vect¬ gradient. procedure Gradient_Search; begin x ← ®iÓm xuÊt ph¸t nμo ®ã; repeat x ← x + α∇f(x); until |∇f| cost(u)) th× ta ®i tíi v, cßn nÕu kh«ng ta chØ ®i tíi v víi mét x¸c suÊt nμo ®ã. X¸c suÊt nμy gi¶m theo hμm mò cña “®é xÊu” cña tr¹ng th¸i v. X¸c suÊt nμy cßn phô thuéc vμo tham sè nhiÖt ®é T. NhiÖt ®é T cμng cao th× b−íc ®i tíi tr¹ng th¸i xÊu cμng cã kh¶ n¨ng ®−îc thùc hiÖn. Trong qu¸ tr×nh t×m kiÕm, tham sè nhiÖt ®é T gi¶m dÇn tíi kh«ng. Khi T gÇn kh«ng, thuËt to¸n ho¹t ®éng gÇn gièng nh− leo ®åi, hÇu nh− nã kh«ng thùc hiÖn b−íc tôt xuèng. Cô thÓ ta x¸c ®Þnh x¸c suÊt ®i tíi tr¹ng th¸i xÊu v tõ u lμ eΔ/T, ë ®©y Δ = cost(v) - cost(u). Sau ®©y lμ thñ tôc m« pháng luyÖn kim. 58
procedure Simulated_Anneaning; begin t ← 0; u ← tr¹ng th¸i ban ®Çu nμo ®ã; T ← nhiÖt ®é ban ®Çu; repeat v ← tr¹ng th¸i ®−îc chän nhÉu nhiªn trong l©n cËn u; if cost(v) > cost(u) then u ← v else u ← v víi x¸c suÊt eΔ/T; T ← g(T, t); t ← t + 1; until T ®ñ nhá end; Trong thñ tôc trªn, hμm g(T, t) tháa m·n ®iÒu kiÖn g(T, t) < T víi mäi t, nã x¸c ®Þnh tèc ®é gi¶m cña nhiÖt ®é T. Ng−êi ta chøng minh ®−îc r»ng, nÕu nhiÖt ®é T gi¶m ®ñ chËm, th× thuËt to¸n sÏ t×m ®−îc nghiÖm tèi −u toμn côc. ThuËt to¸n m« pháng luyÖn kim ®· ®−îc ¸p dông thμnh c«ng cho c¸c bμi to¸n tèi −u cì lín. III. T×m kiÕm m« pháng sù tiÕn hãa. ThuËt to¸n di truyÒn ThuËt to¸n di truyÒn (TTDT) lμ thuËt to¸n b¾t ch−íc sù chän läc tù nhiªn vμ di truyÒn. Trong tù nhiªn, c¸c c¸ thÓ kháe, cã kh¶ n¨ng thÝch nghi tèt víi m«i tr−êng sÏ ®−îc t¸i sinh vμ nh©n b¶n ë c¸c thÕ hÖ sau. Mçi c¸ thÓ cã cÊu tróc gien ®Æc tr−ng cho phÈm chÊt cña c¸ thÓ ®ã. Trong qu¸ tr×nh sinh s¶n, c¸c c¸ thÓ con cã thÓ thõa h−ëng c¸c phÈm chÊt cña c¶ cha vμ mÑ, cÊu tróc gien cña nã mang mét phÇn cÊu tróc gien cña cha vμ mÑ. Ngoμi ra, trong qu¸ tr×nh tiÕn hãa, cã thÓ x¶y ra hiÖn t−îng ®ét biÕn, cÊu tróc gien cña c¸ thÓ con cã thÓ chøa c¸c gien mμ c¶ cha vμ mÑ ®Òu kh«ng cã. Trong TTDT, mçi c¸ thÓ ®−îc m· hãa bëi mét cÊu tróc d÷ liÖu m« t¶ cÊu tróc gien cña c¸ thÓ ®ã, ta sÏ gäi nã lμ nhiÔm s¾c thÓ (chromosome). Mçi nhiÔm s¾c thÓ ®−îc t¹o thμnh tõ c¸c ®¬n vÞ ®−îc gäi lμ gien. Ch¼ng h¹n, trong c¸c TTDT cæ ®iÓn, c¸c nhiÔm s¾c thÓ lμ c¸c chuçi nhÞ ph©n, tøc lμ mçi c¸ thÓ ®−îc biÓu diÔn bëi mét chuçi nhÞ ph©n. TTDT sÏ lμm viÖc trªn c¸c quÇn thÓ gåm nhiÒu c¸ thÓ. Mét quÇn thÓ øng víi mét giai ®o¹n ph¸t triÓn sÏ ®−îc gäi lμ mét thÕ hÖ. Tõ thÕ hÖ ban ®Çu ®−îc t¹o ra, TTDT b¾t ch−íc chän läc tù nhiªn vμ di truyÒn ®Ó biÕn ®æi c¸c thÕ hÖ. TTDT sö dông c¸c to¸n tö c¬ b¶n sau ®©y ®Ó biÕn ®æi c¸c thÕ hÖ. To¸n tö t¸i sinh (reproduction) (cßn ®−îc gäi lμ to¸n tö chän läc (selection)). C¸c c¸ thÓ tèt ®−îc chän läc ®Ó ®−a vμo thÕ hÖ sau. Sù lùa chän nμy ®−îc thùc hiÖn dùa vμo ®é thÝch nghi víi m«i tr−êng cña mçi c¸ thÓ. Ta sÏ gäi hμm øng mçi c¸ thÓ víi ®é thÝch nghi cña nã lμ hμm thÝch nghi (fitness function). To¸n tö lai ghÐp (crossover). Hai c¸ thÓ cha vμ mÑ trao ®æi c¸c gien ®Ó t¹o ra hai c¸ thÓ con. 59
To¸n tö ®ét biÕn (mutation). Mét c¸ thÓ thay ®æi mét sè gien ®Ó t¹o thμnh c¸ thÓ míi. TÊt c¶ c¸c to¸n tö trªn khi thùc hiÖn ®Òu mang tÝnh ngÉu nhiªn. CÊu tróc c¬ b¶n cña TTDT lμ nh− sau: procedure Genetic_Algorithm; begin t ← 0; Khëi t¹o thÕ hÖ ban ®Çu P(t); §¸nh gi¸ P(t) (theo hμm thÝch nghi); repeat t ← t + 1; Sinh ra thÕ hÖ míi P(t) tõ P(t-1) bëi Chän läc Lai ghÐp §ét biÕn; §¸nh gi¸ P(t); until ®iÒu kiÖn kÕt thóc ®−îc tháa m·n; end; Trong thñ tôc trªn, ®iÒu kiÖn kÕt thóc vßng lÆp cã thÓ lμ mét sè thÕ hÖ ®ñ lín nμo ®ã, hoÆc ®é thÝch nghi cña c¸c c¸ thÓ tèt nhÊt trong c¸c thÕ hÖ kÕ tiÕp nhau kh¸c nhau kh«ng ®¸ng kÓ. Khi thuËt to¸n dõng, c¸ thÓ tèt nhÊt trong thÕ hÖ cuèi cïng ®−îc chän lμm nghiÖm cÇn t×m. B©y giê ta sÏ xÐt chi tiÕt h¬n to¸n tö chän läc vμ c¸c to¸n tö di truyÒn (lai ghÐp, ®ét biÕn) trong c¸c TTDT cæ ®iÓn. 1. Chän läc: ViÖc chän läc c¸c c¸ thÓ tõ mét quÇn thÓ dùa trªn ®é thÝch nghi cña mçi c¸ thÓ. C¸c c¸ thÓ cã ®é thÝch nghi cao cã nhiÒu kh¶ n¨ng ®−îc chän. CÇn nhÊn m¹nh r»ng, hμm thÝch nghi chØ cÇn lμ mét hμm thùc d−¬ng, nã cã thÓ kh«ng tuyÕn tÝnh, kh«ng liªn tôc, kh«ng kh¶ vi. Qu¸ tr×nh chän läc ®−îc thùc hiÖn theo kü thuËt quay b¸nh xe. Gi¶ sö thÕ hÖ hiÖn thêi P(t) gåm cã n c¸ thÓ {x1, ,xn}. Sè n ®−îc gäi lμ cì cña quÇn thÓ. Víi mçi c¸ thÓ xi, ta tÝnh ®é thÝch nghi cña nã f(xi). TÝnh tæng c¸c ®é thÝch nghi cña tÊt c¶ c¸c c¸ thÓ trong quÇn thÓ: Mçi lÇn chän läc, ta thùc hiÖn hai b−íc sau: • Sinh ra mét sè thùc ngÉu nhiªn q trong kho¶ng (0, F); • xk lμ c¸ thÓ ®−îc chän, nÕu k lμ sè nhá nhÊt sao cho 60
ViÖc chän läc theo hai b−íc trªn cã thÓ minh häa nh− sau: Ta cã mét b¸nh xe ®−îc chia thμnh n phÇn, mçi phÇn øng víi ®é thÝch nghi cña mét c¸ thÓ (h×nh 5.5). Mét mòi tªn chØ vμo b¸nh xe. Quay b¸nh xe, khi b¸nh xe dõng, mòi tªn chØ vμo phÇn nμo, c¸ thÓ øng víi phÇn ®ã ®−îc chän. H×nh 5.5 Kü thuËt quay b¸nh xe Râ rμng lμ víi c¸ch chän nμy, c¸c c¸ thÓ cã thÓ cã ®é thÝch nghi cμng cao cμng cã kh¶ n¨ng ®−îc chän. C¸c c¸ thÓ cã ®é thÝch nghi cao cã thÓ cã mét hay nhiÒu b¶n sao, c¸c c¸ thÓ cã ®é thÝch nghi thÊp cã thÓ kh«ng cã mÆt ë thÕ hÖ sau (nã bÞ chÕt ®i). 2. Lai ghÐp: Trªn c¸ thÓ ®−îc chän läc, ta tÝÕn hμnh to¸n tö lai ghÐp. §Çu tiªn ta cÇn ®−a ra x¸c suÊt lai ghÐp pc. x¸c suÊt nμy cho ta hy väng cã pc x n c¸ thÓ ®−îc lai ghÐp (n lμ cì cña quÇn thÓ). Víi mçi c¸ thÓ ta thùc hiÖn hai b−íc sau: • Sinh ra sè thùc ngÉu nhiªn r trong ®o¹n [0, 1]; • NÕu r < pc th× c¸ thÓ ®ã ®−îc chän ®Ó lai ghÐp Tõ c¸c c¸ thÓ ®−îc chän ®Ó lai ghÐp, ng−êi ta cÆp ®«i chóng mét c¸ch ngÉu nhiªn. Trong tr−êng hîp c¸c nhiÔm s¾c thÓ lμ c¸c chuçi nhÞ ph©n cã ®é dμi cè ®Þnh m, ta cã thÓ thùc hiÖn lai ghÐp nh− sau: Víi mçi cÆp, sinh ra mét sè nguyªn ngÉu nhiªn p trªn ®o¹n [1, m], p lμ vÞ trÝ ®iÓm ghÐp. CÆp gåm hai nhiÔm s¾c thÓ a = (a1 , , ap , ap+1 , , am) b = (b1 , , bp , bp+1 , , bm) ®−îc thay bëi hai con lμ: a' = (a1 , , ap , bp+1 , , bm) b' = (b1 , , bp , ap+1 , , am) 3. §ét biÕn: Ta thùc hiÖn to¸n tö ®ét biÕn trªn c¸c c¸ thÓ cã ®−îc sau qu¸ tr×nh lai ghÐp. §ét biÕn lμ thay ®æi tr¹ng th¸i mét sè gien nμo ®ã trong nhiÔm s¾c thÓ. Mçi gien chÞu ®ét biÕn víi x¸c suÊt pm. X¸c suÊt ®ét biÕn pm do ta x¸c ®Þnh vμ lμ x¸c suÊt thÊp. Sau ®©y lμ to¸n tö ®ét biÕn trªn c¸c nhiÔm s¾c thÓ chuçi nhÞ ph©n. 61
Víi mçi vÞ trÝ i trong nhiÔm s¾c thÓ: a = (a1 , , ai , , am) Ta sinh ra mét sè thùc nghiÖm ngÉu nhiªn pi trong [0,1]. Qua ®ét biÕn a ®−îc biÕn thμnh a’ nh− sau: a' = (a'1 , , a'i , , a'm) Trong ®ã : ai nÕu pi ≥ pm a’i = 1 - ai nÕu pi < pm Sau qu¸ tr×nh chän läc, lai ghÐp, ®ét biÕn, mét thÕ hÖ míi ®−îc sinh ra. C«ng viÖc cßn l¹i cña thuËt to¸n di truyÒn b©y giê chØ lμ lÆp l¹i c¸c b−íc trªn. VÝ dô: XÐt bμi to¸n t×m max cña hμm f(x) = x2 víi x lμ sè nguyªn trªn ®o¹n [0,31]. §Ó sö dông TTDT, ta m· ho¸ mçi sè nguyªn x trong ®o¹n [0,31] bëi mét sè nhÞ ph©n ®é dμi 5, ch¼ng h¹n, chuçi 11000 lμ m· cña sè nguyªn 24. Hμm thÝch nghi ®−îc x¸c ®Þnh lμ chÝnh hμm f(x) = x2. QuÇn thÓ ban ®Çu gåm 4 c¸ thÓ (cì cña quÇn thÓ lμ n = 4). Thùc hiÖn qu¸ tr×nh chän läc, ta nhËn ®−îc kÕt qu¶ trong b¶ng sau. Trong b¶ng nμy, ta thÊy c¸ thÓ 2 cã ®é thÝch nghi cao nhÊt (576) nªn nã ®−îc chän 2 lÇn, c¸ thÓ 3 cã ®é thÝch nghi thÊp nhÊt (64) kh«ng ®−îc chän lÇn nμo. Mçi c¸ thÓ 1 vμ 4 ®−îc chän 1 lÇn. B¶ng kÕt qu¶ chän läc Thùc hiÖn qu¸ tr×nh lai ghÐp víi x¸c suÊt lai ghÐp pc = 1, nªn c¸ thÓ 1, 2, vμ 4 sau chän läc ®Òu ®−îc lai ghÐp. KÕt qu¶ lai ghÐp ®−îc cho trong b¶ng sau. Trong b¶ng nμy, chuçi thø nhÊt ®−îc lai ghÐp víi chuçi thø hai víi ®iÓm ghÐp lμ 4, chuçi thø hai vμ 4 ®−îc lai ghÐp víi nhau víi ®iÓm ghÐp lμ 2. B¶ng kÕt qu¶ lai ghÐp QuÇn thÓ sau §iÓm ghÐp QuÇn thÓ sau lai x §é thÝch nghi chän läc ghÐp f(x) = x2 0 1 1 0 | 1 4 0 1 1 0 0 12 144 1 1 0 0 | 0 4 1 1 0 0 1 25 625 1 1 | 0 0 0 2 1 1 0 1 1 27 729 1 0 | 0 1 1 2 1 0 0 0 0 16 256 62
§Ó thùc hiÖn qu¸ tr×nh ®ét biÕn, ta chän x¸c suÊt ®ét biÕn pm= 0,001, tøc lμ ta hy väng cã 5x4x0,001 = 0,02 bit ®−îc ®ét biÕn. Thùc tÕ sÏ kh«ng cã bit nμo ®−îc ®ét biÕn. Nh− vËy thÕ hÖ míi lμ quÇn thÓ sau lai ghÐp. Trong thÕ hÖ ban ®Çu, ®é thÝch nghi cao nhÊt lμ 576, ®é thÝch nghi trung b×nh 292. Trong thÕ hÖ sau, ®é thÝch nghi cao nhÊt lμ 729, trung b×nh lμ 438. ChØ qua mét thÕ hÖ, c¸c c¸ thÓ ®· “tèt lªn” rÊt nhiÒu. ThuËt to¸n di truyÒn kh¸c víi c¸c thuËt to¸n tèi −u kh¸c ë c¸c ®iÓm sau: TTDT chØ sö dông hμm thÝch nghi ®Ó h−íng dÉn sù t×m kiÕm, hμm thÝch nghi chØ cÇn lμ hμm thùc d−¬ng. Ngoμi ra, nã kh«ng ®ßi hái kh«ng gian t×m kiÕm ph¶i cã cÊu tróc nμo c¶. TTDT lμm viÖc trªn c¸c nhiÔm s¾c thÓ lμ m· cña c¸c c¸ thÓ cÇn t×m. TTDT t×m kiÕm tõ mét quÇn thÓ gåm nhiÒu c¸ thÓ. C¸c to¸n tö trong TTDT ®Òu mang tÝnh ngÉu nhiªn. §Ó gi¶i quyÕt mét vÊn ®Ò b»ng TTDT, chóng ta cÇn thùc hiÖn c¸c b−íc sau ®©y: Tr−íc hÕt ta cÇn m· hãa c¸c ®èi t−îng cÇn t×m bëi mét cÊu tróc d÷ liÖu nμo ®ã. Ch¼ng h¹n, trong c¸c TTDT cæ ®iÓn, nh− trong vÝ dô trªn, ta sö dông m· nhÞ ph©n. ThiÕt kÕ hμm thÝch nghi. Trong c¸c bμi to¸n tèi −u, hμm thÝch nghi ®−îc x¸c ®Þnh dùa vμo hμm môc tiªu. Trªn c¬ së cÊu tróc cña nhiÔm s¾c thÓ, thiÕt kÕ c¸c to¸n tö di truyÒn (lai ghÐp, ®ét biÕn) cho phï hîp víi c¸c vÊn ®Ò cÇn gi¶i quyÕt. X¸c ®Þnh cì cña quÇn thÓ vμ khëi t¹o quÇn thÓ ban ®Çu. X¸c ®Þnh x¸c suÊt lai ghÐp pc vμ x¸c suÊt ®ét biÕn. X¸c suÊt ®ét biÕn cÇn lμ x¸c suÊt thÊp. Ng−êi ta (Goldberg, 1989) khuyªn r»ng nªn chän x¸c suÊt lai ghÐp lμ 0,6 vμ x¸c suÊt ®ét biÕn lμ 0,03. Tuy nhiªn cÇn qua thö nghiÖm ®Ó t×m ra c¸c x¸c suÊt thÝch hîp cho vÊn ®Ò cÇn gi¶i quyÕt. Nãi chung thuËt ng÷ TTDT lμ ®Ó chØ TTDT cæ ®iÓn, khi mμ cÊu tróc cña c¸c nhiÔm s¾c thÓ lμ c¸c chuçi nhÞ ph©n víi c¸c to¸n tö di truyÒn ®· ®−îc m« t¶ ë trªn. Song trong nhiÒu vÊn ®Ò thùc tÕ, thuËn tiÖn h¬n, ta cã thÓ biÓu diÔn nhiÔm s¾c thÓ bëi c¸c cÊu tróc kh¸c, ch¼ng h¹n vect¬ thùc, m¶ng hai chiÒu, c©y, T−¬ng øng víi cÊu tróc cña nhiÔm s¾c thÓ, cã thÓ cã nhiÒu c¸ch x¸c ®Þnh c¸c to¸n tö di truyÒn. Qu¸ tr×nh sinh ra thÕ hÖ míi P(t) tõ thÕ hÖ cò P(t - 1) còng cã nhiÒu c¸ch chän lùa. Ng−êi ta gäi chung c¸c thuËt to¸n nμy lμ thuËt to¸n tiÕn hãa (evolutionary algorithms) hoÆc ch−¬ng tr×nh tiÕn hãa (evolution program). IV. Bμi tËp 1. Chøng minh r»ng nÕu ®é dμi cña c¸c cung kh«ng nhá h¬n mét sè d−¬ng δ nμo ®ã th× thuËt to¸n A* lμ thuËt to¸n ®Çy ®ñ. 2. ViÕt ch−¬ng tr×nh minh häa t×m kiÕm theo thuËt to¸n A*, nh¸nh vμ cËn, ®èi t−îng tèt nhÊt, leo ®åi cña bμi to¸n 8 sè. 3. ViÕt ch−¬ng tr×nh gi¶i bμi to¸n 8 con hËu. 4. Ứng dụng giải thuật di truyền để tìm giá trị của các biến nguyên x, y, z sao cho hàm f(x,y,z) = ysin(zcos(x)) – xcos(zsin(y)) đạt giá trị lớn nhất. 63
Biết rằng 0 < x < 10, 0< y < 10, 0 <z < 10. 5. Cho ®å thÞ kh«ng gian tr¹ng th¸i: 30 A 1 15 13 4 20 17 24 B C D 1 12 3 1 4 8 16 12 15 E 6 F 4 G 11 18 22 0 K §Ó t×m ®−êng ®i tõ A tíi K, h·y vÏ c©y t×m kiÕm cña t×m kiÕm A*, nh¸nh vμ cËn vμ leo ®åi. 64
Ch−¬ng VI T×m kiÕm cã ®èi thñ Nghiªn cøu m¸y tÝnh ch¬i cê ®· xuÊt hiÖn rÊt sím. Kh«ng l©u sau khi m¸y tÝnh lËp tr×nh ®−îc ra ®êi vμo n¨m 1950, Claude Shannon ®· viÕt ch−¬ng tr×nh ch¬i cê ®Çu tiªn. c¸c nhμ nghiªn cøu TrÝ TuÖ Nh©n T¹o ®· nghiªn cøu viÖc ch¬i cê, v× r»ng m¸y tÝnh ch¬i cê lμ mét b»ng chøng râ rμng vÒ kh¶ n¨ng m¸y tÝnh cã thÓ lμm ®−îc c¸c c«ng viÖc ®ßi hái trÝ th«ng minh cña con ng−êi. Trong ch−¬ng nμy chóng ta sÏ xÐt c¸c vÊn ®Ò sau ®©y: Ch¬i cê cã thÓ xem nh− vÊn ®Ò t×m kiÕm trong kh«ng gian tr¹ng th¸i. ChiÕn l−îc t×m kiÕm n−íc ®i Minimax. Ph−¬ng ph¸p c¾t côt α-β, mét kü thuËt ®Ó t¨ng hiÖu qu¶ cña t×m kiÕm Minimax. I. C©y trß ch¬i vμ t×m kiÕm trªn c©y trß ch¬i Trong ch−¬ng nμy chóng ta chØ quan t©m nghiªn cøu c¸c trß ch¬i cã hai ng−êi tham gia, ch¼ng h¹n c¸c lo¹i cê (cê vua, cê t−íng, cê ca r« ). Mét ng−êi ch¬i ®−îc gäi lμ Tr¾ng, ®èi thñ cña anh ta ®−îc gäi lμ §en. Môc tiªu cña chóng ta lμ nghiªn cøu chiÕn l−îc chän n−íc ®i cho Tr¾ng (M¸y tÝnh cÇm qu©n Tr¾ng). Chóng ta sÏ xÐt c¸c trß ch¬i hai ng−êi víi c¸c ®Æc ®iÓm sau. Hai ng−êi ch¬i thay phiªn nhau ®−a ra c¸c n−íc ®i tu©n theo c¸c luËt ®i nμo ®ã, c¸c luËt nμy lμ nh− nhau cho c¶ hai ng−êi. §iÓn h×nh lμ cê vua, trong cê vua hai ng−êi ch¬i cã thÓ ¸p dông c¸c luËt ®i con tèt, con xe, ®Ó ®−a ra n−íc ®i. LuËt ®i con tèt Tr¾ng xe Tr¾ng, còng nh− luËt ®i con tèt §en, xe §en, Mét ®Æc ®iÓm n÷a lμ hai ng−êi ch¬i ®Òu ®−îc biÕt th«ng tin ®Çy ®ñ vÒ c¸c t×nh thÕ trong trß ch¬i (kh«ng nh− trong ch¬i bμi, ng−êi ch¬i kh«ng thÓ biÕt c¸c ng−êi ch¬i kh¸c cßn nh÷ng con bμi g×). VÊn ®Ò ch¬i cê cã thÓ xem nh− vÊn ®Ò t×m kiÕm n−íc ®i, t¹i mçi lÇn ®Õn l−ît m×nh, ng−êi ch¬i ph¶i t×m trong sè rÊt nhiÒu n−íc ®i hîp lÖ (tu©n theo ®óng luËt ®i), mét n−íc ®i tèt nhÊt sao cho qua mét d·y n−íc ®i ®· thùc hiÖn, anh ta giμnh phÇn th¾ng. Tuy nhiªn vÊn ®Ò t×m kiÕm ë ®©y sÏ phøc t¹p h¬n vÊn ®Ò t×m kiÕm mμ chóng ta ®· xÐt trong c¸c ch−¬ng tr−íc, bëi v× ë ®©y cã ®èi thñ, ng−êi ch¬i kh«ng biÕt ®−îc ®èi thñ cña m×nh sÏ ®i n−íc nμo trong t−¬ng lai. Sau ®©y chóng ta sÏ ph¸t biÓu chÝnh x¸c h¬n vÊn ®Ò t×m kiÕm nμy. VÊn ®Ò ch¬i cê cã thÓ xem nh− vÊn ®Ò t×m kiÕm trong kh«ng gian tr¹ng th¸i. Mçi tr¹ng th¸i lμ mét t×nh thÕ (sù bè trÝ c¸c qu©n cña hai bªn trªn bμn cê). Tr¹ng th¸i ban ®Çu lμ sù s¾p xÕp c¸c qu©n cê cña hai bªn lóc b¾t ®Çu cuéc ch¬i. C¸c to¸n tö lμ c¸c n−íc ®i hîp lÖ. C¸c tr¹ng th¸i kÕt thóc lμ c¸c t×nh thÕ mμ cuéc ch¬i dõng, th−êng ®−îc x¸c ®Þnh bëi mét sè ®iÒu kiÖn dõng nμo ®ã. Mét hμm kÕt cuéc (payoff function) øng mçi tr¹ng th¸i kÕt thóc víi mét gi¸ trÞ nμo ®ã. Ch¼ng h¹n nh− cê vua, mçi tr¹ng th¸i kÕt thóc chØ cã thÓ lμ th¾ng, hoÆc thua 65
(®èi víi Tr¾ng) hoÆc hßa. Do ®ã, ta cã thÓ x¸c ®Þnh hμm kÕt cuéc lμ hμm nhËn gi¸ trÞ 1 t¹i c¸c tr¹ng th¸i kÕt thóc lμ th¾ng (®èi víi Tr¾ng), -1 t¹i c¸c tr¹ng th¸i kÕt thóc lμ thua (®èi víi Tr¾ng) vμ 0 t¹i c¸c tr¹ng th¸i kÕt thóc hßa. Trong mét sè trß ch¬i kh¸c, ch¼ng h¹n trß ch¬i tÝnh ®iÓm, hμm kÕt cuéc cã thÓ nhËn gi¸ trÞ nguyªn trong kho¶ng [-k, k] víi k lμ mét sè nguyªn d−¬ng nμo ®ã. Nh− vËy vÊn ®Ò cña Tr¾ng lμ, t×m mét d·y n−íc ®i sao cho xen kÏ víi c¸c n−íc ®i cña §en t¹o thμnh mét ®−êng ®i tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i kÕt thóc lμ th¾ng cho Tr¾ng. §Ó thuËn lîi cho viÖc nghiªn cøu c¸c chiÕn l−îc chän n−íc ®i, ta biÓu diÔn kh«ng gian tr¹ng th¸i trªn d−íi d¹ng c©y trß ch¬i. C©y trß ch¬i C©y trß ch¬i ®−îc x©y dùng nh− sau. Gèc cña c©y øng víi tr¹ng th¸i ban ®Çu. Ta sÏ gäi ®Ønh øng víi tr¹ng th¸i mμ Tr¾ng (§en) ®−a ra n−íc ®i lμ ®Ønh Tr¾ng (§en). NÕu mét ®Ønh lμ Tr¾ng (§en) øng víi tr¹ng th¸i u, th× c¸c ®Ønh con cña nã lμ tÊt c¶ c¸c ®Ønh biÓu diÔn tr¹ng th¸i v, v nhËn ®−îc tõ u do Tr¾ng (§en) thùc hiÖn n−íc ®i hîp lÖ nμo ®ã. Do ®ã, trªn cïng mét møc cña c©y c¸c ®Ønh ®Òu lμ Tr¾ng hÆc ®Òu lμ §en, c¸c l¸ cña c©y øng víi c¸c tr¹ng th¸i kÕt thóc. VÝ dô: XÐt trß ch¬i Dodgen (®−îc t¹o ra bëi Colin Vout). Cã hai qu©n Tr¾ng vμ hai qu©n §en, ban ®Çu ®−îc xÕp vμo bμn cê 3*3 (h×nh 6.1). Qu©n §en cã thÓ ®i tíi « trèng ë bªn ph¶i, ë trªn hoÆc ë d−íi. Qu©n Tr¾ng cã thÓ ®i tíi trèng ë bªn tr¸i, bªn ph¶i, ë trªn. Qu©n §en nÕu ë cét ngoμi cïng bªn ph¶i cã thÓ ®i ra khái bμn cê, qu©n Tr¾ng nÕu ë hμng trªn cïng cã thÓ ®i ra khái bμn cê. Ai ®−a hai qu©n cña m×nh ra khái bμn cê tr−íc sÏ th¾ng, hoÆc t¹o ra t×nh thÕ b¾t ®èi ph−¬ng kh«ng ®i ®−îc còng sÏ th¾ng. H×nh 6.1 Trß ch¬i Dodgem 66
Gi¶ sö §en ®i tr−íc, ta cã c©y trß ch¬i ®−îc biÓu diÔn nh− trong h×nh 6.2. H×nh 6.2 C©y trß ch¬i Dodgem víi §en ®i tr−íc Qu¸ tr×nh ch¬i cê lμ qu¸ tr×nh Tr¾ng vμ §en thay phiªn nhau ®−a ra quyÕt ®Þnh, thùc hiÖn mét trong sè c¸c n−íc ®i hîp lÖ. Trªn c©y trß ch¬i, qu¸ tr×nh ®ã sÏ t¹o ra ®−êng ®i tõ gèc tíi l¸. Gi¶ sö tíi mét thêi ®iÓm nμo ®ã, ®−êng ®i ®· dÉn tíi ®Ønh u. NÕu u lμ ®Ønh Tr¾ng (§en) th× Tr¾ng (§en) cÇn chän ®i tíi mét trong c¸c ®Ønh §en (Tr¾ng) v lμ con cña u. T¹i ®Ønh §en (Tr¾ng) v mμ Tr¾ng (§en) võa chän, §en (Tr¾ng) sÏ ph¶i chän ®i tíi mét trong c¸c ®Ønh Tr¾ng (§en) w lμ con cña v. Qu¸ tr×nh trªn sÏ dõng l¹i khi ®¹t tíi mét ®Ønh lμ l¸ cña c©y. Gi¶ sö Tr¾ng cÇn t×m n−íc ®i t¹i ®Ønh u. N−íc ®i tèi −u cho Tr¾ng lμ n−íc ®i dÇn tíi ®Ønh con cña v lμ ®Ønh tèt nhÊt (cho Tr¾ng) trong sè c¸c ®Ønh con cña u. Ta cÇn gi¶ thiÕt r»ng, ®Õn l−ît ®èi thñ chän n−íc ®i tõ v, §en còng sÏ chän n−íc ®i tèt nhÊt cho anh ta. Nh− vËy, ®Ó chän n−íc ®i tèi −u cho Tr¾ng t¹i ®Ønh u, ta cÇn ph¶i x¸c ®Þnh gi¸ trÞ c¸c ®Ønh cña c©y trß ch¬i gèc u. Gi¸ trÞ cña c¸c ®Ønh l¸ (øng víi c¸c tr¹ng th¸i kÕt thóc) lμ gi¸ trÞ cña hμm kÕt cuéc. §Ønh cã gi¸ trÞ cμng lín cμng tèt cho Tr¾ng, ®Ønh cã gi¸ trÞ cμng nhá cμng tèt cho §en. §Ó x¸c ®Þnh gi¸ trÞ c¸c ®Ønh cña c©y trß ch¬i gèc u, ta ®i tõ møc thÊp nhÊt lªn gèc u. Gi¶ sö u lμ ®Ønh trong cña c©y vμ gi¸ trÞ c¸c ®Ønh con cña nã ®· ®−îc x¸c ®Þnh. Khi ®ã nÕu u lμ ®Ønh Tr¾ng th× gi¸ trÞ cña nã ®−îc x¸c ®Þnh lμ gi¸ trÞ lín nhÊt trong c¸c gi¸ trÞ cña c¸c ®Ønh con. Cßn nÕu u lμ ®Ønh §en th× gi¸ trÞ cña nã lμ gi¸ trÞ nhá nhÊt trong c¸c gi¸ trÞ cña c¸c ®Ønh con. 67
VÝ dô: XÐt c©y trß ch¬i trong h×nh 6.3, gèc a lμ ®Ønh Tr¾ng. Gi¸ trÞ cña c¸c ®Ønh lμ sè ghi c¹nh mçi ®Ønh. §Ønh i lμ Tr¾ng, nªn gi¸ trÞ cña nã lμ max(3,-2) = 3, ®Ønh d lμ ®Ønh §en, nªn gi¸ trÞ cña nã lμ min(2, 3, 4) = 2. H×nh 6.3 G¸n gi¸ trÞ cho c¸c ®Ønh cña c©y trß ch¬i ViÖc g¸n gi¸ trÞ cho c¸c ®Ønh ®−îc thùc hiÖn bëi c¸c hμm ®Ö qui MaxVal vμ MinVal. Hμm MaxVal x¸c ®Þnh gi¸ trÞ cho c¸c ®Ønh Tr¾ng, hμm MinVal x¸c ®Þnh gi¸ trÞ cho c¸c ®Ønh §en. function MaxVal(u); begin if u lμ ®Ønh kÕt thóc then return f(u) else return max{MinVal(v) | v lμ ®Ønh con cña u} end; function MinVal(u); begin if u lμ ®Ønh kÕt thóc then return f(u) else return min{MaxVal(v) | v lμ ®Ønh con cña u} end; Trong c¸c hμm ®Ö quy trªn, f(u) lμ gi¸ trÞ cña hμm kÕt cuéc t¹i ®Ønh kÕt thóc u. Sau ®©y lμ thñ tôc chän n−íc ®i cho Tr¾ng t¹i ®Ønh u. Trong thñ tôc Minimax(u,v), v lμ biÕn l−u l¹i tr¹ng th¸i mμ Tr¾ng ®· chän ®i tíi tõ u. procedure Minimax(u, v); begin val ← -∞; for mçi w lμ ®Ønh con cña u do if val <= MinVal(w) then { val ← MinVal(w); 68
v ← w } end; Thñ tôc chän n−íc ®i nh− trªn gäi lμ chiÕn l−îc Minimax, bëi v× Tr¾ng ®· chän ®−îc n−íc ®i dÉn tíi ®Ønh con cã gi¸ trÞ lμ max cña c¸c gi¸ trÞ c¸c ®Ønh con, vμ §en ®¸p l¹i b»ng n−íc ®i tíi ®Ønh cã gi¸ trÞ lμ min cña c¸c gi¸ trÞ c¸c ®Ønh con. ThuËt to¸n Minimax lμ thuËt to¸n t×m kiÕm theo ®é s©u, ë ®©y ta ®· cμi ®Æt thuËt to¸n Minimax bëi c¸c hμm ®Ö quy. B¹n ®äc h·y viÕt thñ tôc kh«ng ®Ö quy thùc hiÖn thuËt to¸n nμy. VÒ mÆt lÝ thuyÕt, chiÕn l−îc Minimax cho phÐp ta t×m ®−îc n−íc ®i tèi −u cho Tr¾ng. Song nã kh«ng thùc tÕ, chóng ta sÏ kh«ng cã ®ñ thêi gian ®Ó tÝnh ®−îc n−íc ®i tèi −u. Bëi v× thuËt to¸n Minimax ®ßi hái ta ph¶i xem xÐt toμn bé c¸c ®Ønh cña c©y trß ch¬i. Trong c¸c trß ch¬i hay, c©y trß ch¬i lμ cùc kú lín. Ch¼ng h¹n, ®èi víi cê vua, chØ tÝnh ®Õn ®é s©u 40, th× c©y trß ch¬i ®· cã kho¶ng 10120 ®Ønh! NÕu c©y cã ®é cao m, vμ t¹i mçi ®Ønh cã b n−íc ®i th× ®é phøc t¹p vÒ thêi gian cña thuËt to¸n Minimax lμ O(bm). §Ó cã thÓ t×m ra nhanh n−íc ®i tèt (kh«ng ph¶i lμ tèi −u) thay cho viÖc sö dông hμm kÕt cuéc vμ xem xÐt tÊt c¶ c¸c kh¶ n¨ng dÉn tíi c¸c tr¹ng th¸i kÕt thóc, chóng ta sÏ sö dông hμm ®¸nh gi¸ vμ chØ xem xÐt mét bé phËn cña c©y trß ch¬i. Hμm ®¸nh gi¸ Hμm ®¸nh gi¸ eval øng víi mçi tr¹ng th¸i u cña trß ch¬i víi mét gi¸ trÞ sè eval(u), gi¸ trÞ nμy lμ sù ®¸nh gi¸ “®é lîi thÕ” cña tr¹ng th¸i u. Tr¹ng th¸i u cμng thuËn lîi cho Tr¾ng th× eval(u) lμ sè d−¬ng cμng lín; u cμng thuËn lîi cho §en th× eval(u) lμ sè ©m cμng nhá; eval(u) ≈ 0 ®èi víi tr¹ng th¸i kh«ng lîi thÕ cho ai c¶. ChÊt l−îng cña ch−¬ng tr×nh ch¬i cê phô thuéc rÊt nhiÒu vμo hμm ®¸nh gi¸. NÕu hμm ®¸nh gi¸ cho ta sù ®¸nh gi¸ kh«ng chÝnh x¸c vÒ c¸c tr¹ng th¸i, nã cã thÓ h−íng dÉn ta ®i tíi tr¹ng th¸i ®−îc xem lμ tèt, nh−ng thùc tÕ l¹i rÊt bÊt lîi cho ta. ThiÕt kÕ mét hμm ®¸nh gi¸ tèt lμ mét viÖc khã, ®ßi hái ta ph¶i quan t©m ®Õn nhiÒu nh©n tè: c¸c qu©n cßn l¹i cña hai bªn, sù bè trÝ cña c¸c qu©n ®ã, ë ®©y cã sù m©u thuÉn gi÷a ®é chÝnh x¸c cña hμm ®¸nh gi¸ vμ thêi gian tÝnh cña nã. Hμm ®¸nh gi¸ chÝnh x¸c sÏ ®ßi hái rÊt nhiÒu thêi gian tÝnh to¸n, mμ ng−êi ch¬i l¹i bÞ giíi h¹n bëi thêi gian ph¶i ®−a ra n−íc ®i. VÝ dô 1: Sau ®©y ta ®−a ra mét c¸ch x©y dùng hμm ®¸nh gi¸ ®¬n gi¶n cho cê vua. Mçi lo¹i qu©n ®−îc g¸n mét gi¸ trÞ sè phï hîp víi “søc m¹nh” cña nã. Ch¼ng h¹n, mçi tèt Tr¾ng (§en) ®−îc cho 1 (-1), m· hoÆc t−îng Tr¾ng (§en) ®−îc cho 3 (-3), xe Tr¾ng (§en) ®−îc cho 5 (-5) vμ hoμng hËu Tr¾ng (§en) ®−îc cho 9 (-9). LÊy tæng gi¸ trÞ cña tÊt c¶ c¸c qu©n trong mét tr¹ng th¸i, ta sÏ ®−îc gi¸ trÞ ®¸nh gi¸ cña tr¹ng th¸i ®ã. Hμm ®¸nh gi¸ nh− thÕ ®−îc gäi lμ hμm tuyÕn tÝnh cã träng sè, v× nã cã thÓ biÓu diÔn d−íi d¹ng: s1w1 +s2w2+. . . +snwn Trong ®ã, wi lμ gi¸ trÞ mçi lo¹i qu©n, cßn si lμ sè qu©n lo¹i ®ã. Trong c¸ch ®¸nh gi¸ nμy, ta ®· kh«ng tÝnh ®Õn sù bè trÝ cña c¸c qu©n, c¸c mèi t−¬ng quan gi÷a chóng. 69
VÝ dô 2: B©y giê ta ®−a ra mét c¸ch ®¸nh gi¸ c¸c tr¹ng th¸i trong trß ch¬i Dodgem. Mçi qu©n Tr¾ng ë mét vÞ trÝ trªn bμn cê ®−îc cho mét gi¸ trÞ t−¬ng øng trong b¶ng bªn tr¸i h×nh 4.4. Cßn mçi qu©n §en ë mét vÞ trÝ sÏ ®−îc cho mét gi¸ trÞ t−¬ng øng trong b¶ng bªn ph¶i h×nh 4.4: Ngoμi ra, nÕu qu©n Tr¾ng c¶n trùc tiÕp mét qu©n §en, nã ®−îc thªm 40 ®iÓm, nÕu c¶n gi¸n tiÕp nã ®−îc thªm 30 ®iÓm (Xem h×nh 6.4). T−¬ng tù, nÕu qu©n §en c¶n trùc tiÕp qu©n Tr¾ng nã ®−îc thªm -40 ®iÓm, cßn c¶n gi¸n tiÕp nã ®−îc thªm -30 ®iÓm. H×nh 6.4 §¸nh gi¸ c¸c qu©n trong trß ch¬i Dodgem ¸p dông c¸c qui t¾c trªn, ta tÝnh ®−îc gi¸ trÞ cña tr¹ng th¸i ë bªn tr¸i h×nh 6.6 lμ 75, gi¸ trÞ cña tr¹ng th¸i bªn ph¶i h×nh vÏ lμ -5. H×nh 6.5 §¸nh gi¸ sù t−¬ng quan gi÷a qu©n tr¾ng vμ ®en H×nh 6.6 Gi¸ trÞ cña mét sè tr¹ng th¸i trong trß ch¬i Dodgem Trong c¸nh ®¸nh gi¸ trªn, ta ®· xÐt ®Õn vÞ trÝ cña c¸c qu©n vμ mèi t−¬ng quan gi÷a c¸c qu©n. Mét c¸ch ®¬n gi¶n ®Ó h¹n chÕ kh«ng gian t×m kiÕm lμ, khi cÇn x¸c ®Þnh n−íc ®i cho Tr¾ng t¹i u, ta chØ xem xÐt c©y trß ch¬i gèc u tíi ®é cao h nμo ®ã. ¸p dông thñ tôc Minimax cho c©y trß ch¬i gèc u, ®é cao h vμ sö dông gi¸ trÞ cña hμm ®¸nh gi¸ cho c¸c l¸ cña c©y ®ã, chóng ta sÏ t×m ®−îc n−íc ®i tèt cho Tr¾ng t¹i u. 70
II. Ph−¬ng ph¸p c¾t côt alpha - beta Trong chiÕn l−îc t×m kiÕm Minimax, ®Ó t×m kiÕm n−íc ®i tèt cho Tr¾ng t¹i tr¹ng th¸i u, cho dï ta h¹n chÕ kh«ng gian t×m kiÕm trong ph¹m vi c©y trß ch¬i gèc u víi ®é cao h, th× sè ®Ønh cña c©y trß ch¬i nμy còng cßn rÊt lín víi h ≥ 3. Ch¼ng h¹n, trong cê vua, nh©n tè nh¸nh trong c©y trß ch¬i trung b×nh kho¶ng 35, thêi gian ®ßi hái ph¶i ®−a ra n−íc ®i lμ 150 gi©y, víi thêi gian nμy trªn m¸y tÝnh th«ng th−êng ch−¬ng tr×nh cña b¹n chØ cã thÓ xem xÐt c¸c ®Ønh trong ®é s©u 3 hoÆc 4. Mét ng−êi ch¬i cê tr×nh ®é trung b×nh còng cã thÓ tÝnh tr−íc ®−îc 5, 6 n−íc hoÆc h¬n n÷a, vμ do ®ã ch−¬ng tr×nh cña b¹n míi ®¹t tr×nh ®é ng−êi míi tËp ch¬i! Khi ®¸nh gi¸ ®Ønh u tíi ®é s©u h, mét thuËt to¸n Minimax ®ßi hái ta ph¶i ®¸nh gi¸ tÊt c¶ c¸c ®Ønh cña c©y gèc u tíi ®é s©u h. Song ta cã thÓ gi¶m bít sè ®Ønh cÇn ph¶i ®¸nh gi¸ mμ vÉn kh«ng ¶nh h−ëng g× ®Õn sù ®¸nh gi¸ ®Ønh u. Ph−¬ng ph¸p c¾t côt alpha- beta cho phÐp ta c¾t bá c¸c nh¸nh kh«ng cÇn thiÕt cho sù ®¸nh gi¸ ®Ønh u. T− t−ëng cña kü thuËt c¾t côt alpha-beta lμ nh− sau: Nhí l¹i r»ng, chiÕn l−îc t×m kiÕm Minimax lμ chiÕn l−îc t×m kiÕm theo ®é s©u. Gi¶ sö trong qu¸ trÝnh t×m kiÕm ta ®i xuèng ®Ønh a lμ ®Ønh Tr¾ng, ®Ønh a cã ng−êi anh em v ®· ®−îc ®¸nh gi¸. Gi¶ sö cha cña ®Ønh a lμ b vμ b cã ng−êi anh em u d· ®−îc ®¸nh gi¸, vμ gi¶ sö cha cña b lμ c (Xem h×nh 6.7). Khi ®ã ta cã gi¸ trÞ ®Ønh c (®Ønh Tr¾ng) Ýt nhÊt lμ gi¸ trÞ cña u, gi¸ trÞ cña ®Ønh b (®Ønh §en) nhiÒu nhÊt lμ gi¸ trÞ v. Do ®ã, nÕu eval(u) ≥ eval(v), ta kh«ng cÇn ®i xuèng ®Ó ®¸nh gi¸ ®Ønh a n÷a mμ vÉn kh«ng ¶nh h−ëng g× dÕn ®¸nh gi¸ ®Ønh c. Hay nãi c¸ch kh¸c ta cã thÓ c¾t bá c©y con gèc a. LËp luËn t−¬ng tù cho tr−êng hîp a lμ ®Ønh §en, trong tr−êng hîp nμy nÕu eval(u) ≤ eval(v) ta còng cã thÓ c¾t bá c©y con gèc a. H×nh 6.7 C¾t bá c©y con gèc a, nÕu eval(u) ≥ eval(v) §Ó cμi ®Æt kü thuËt c¾t côt alpha-beta, ®èi víi c¸c ®Ønh n»m trªn ®−êng ®i tõ gèc tíi ®Ønh hiÖn thêi, ta sö dông tham sè α ®Ó ghi l¹i gi¸ trÞ lín nhÊt trong c¸c gi¸ trÞ cña c¸c ®Ønh con ®· ®¸nh gi¸ cña mét ®Ønh Tr¾ng, cßn tham sè β ghi l¹i gi¸ trÞ nhá nhÊt trong c¸c ®Ønh con ®· ®¸nh gi¸ cña mét ®Ønh §en. Gi¸ trÞ cña α vμ β sÏ ®−îc cËp nhËt trong qu¸ tr×nh t×m kiÕm. α vμ β ®−îc sö dông nh− c¸c biÕn ®Þa ph−¬ng trong c¸c hμm MaxVal(u, α, β) (hμm x¸c ®Þnh gi¸ trÞ cña ®Ønh Tr¾ng u) vμ Minval(u, α, β) (hμm x¸c ®Þnh gi¸ trÞ cña ®Ønh §en u). ThuËt to¸n t×m n−íc ®i cho Tr¾ng sö dông kü thuËt c¾t côt alpha-beta, ®−îc cμi ®Æt bëi thñ tôc Alpha_beta(u,v), trong ®ã v lμ tham biÕn ghi l¹i ®Ønh mμ Tr¾ng cÇn ®i tíi tõ u. 71
function MaxVal(u α, β); begin if u lμ l¸ cña c©y h¹n chÕ hoÆc u lμ ®Ønh kÕt thóc then return eval(u) else { for mçi ®Ønh v lμ con cña u do {α ← max[α, MinVal(v, α, β)]; // C¾t bá c¸c c©y con tõ c¸c ®Ønh v cßn l¹i if α ≥ β then return β; } return α; } end; function MinVal(u, α, β); begin if u lμ l¸ cña c©y h¹n chÕ hoÆc u lμ ®Ønh kÕt thóc then return eval(u) else { for mçi ®Ønh v lμ con cña u do {β ← min[β, MaxVal(v, α, β)]; // C¾t bá c¸c c©y con tõ c¸c ®Ønh v cßn l¹i if α ≥ β then return α; } return β; } end; procedure Alpha_beta(u, v); α ← -∞; β ← ∞; begin for mçi ®Ønh w lμ con cña u do if α ≤ MinVal(w, α, β) then { α ← MinVal(w, α, β); v ← w;} end; VÝ dô. XÐt c©y trß ch¬i gèc u (®Ønh Tr¾ng) giíi h¹n bëi ®é cao h = 3 (h×nh 4.8). Sè ghi c¹nh c¸c l¸ lμ gi¸ trÞ cña hμm ®¸nh gi¸. ¸p dông chiÕn l−îc Minimax vμ kü thuËt c¾t 72
côt, ta x¸c ®Þnh ®−îc n−íc ®i tèt nhÊt cho Tr¾ng t¹i u, ®ã lμ n−íc ®i dÉn tíi ®Ønh v cã gi¸ trÞ 10. C¹nh mçi ®Ønh ta còng cho gi¸ trÞ cña cÆp tham sè (α, β). Khi gäi c¸c hμm MaxVal vμ MinVal ®Ó x¸c ®Þnh gi¸ trÞ cña ®Ønh ®ã. C¸c nh¸nh bÞ c¾t bá ®−îc chØ ra trong h×nh 6.8. 10 MAX U (-∞,∞) (-3,∞) (10,∞) MIN V -3 10 8 (-∞,-3) (-3,10) (10,∞) MAX (-∞,∞) -3 10 5 10 12 8 (-∞,5) (-3,∞) MIN -7 5 10 -5 12 8 (-∞,∞) (-7,∞) (-∞,-3) (-3,10) (-3,10) (10,∞) H×nh 6.8 X¸c ®Þnh gi¸ trÞ c¸c ®Ønh b»ng kü thuËt c¾t côt III. Bμi tËp 1. ViÕt ch−¬ng tr×nh trß ch¬i Dodgem cã ¸p dông ph−¬ng ph¸p c¾t côt alpha-beta. 2. Dïng kü thuËt c¾t côt alpha-beta ®Ó ®Þnh trÞ cho nót gèc cña c©y trß ch¬i (c¸c nót l¸ ®· ®−îc g¸n trÞ): 3. XÐt mét trß ch¬i cã 6 viªn bi, hai ng−êi thay phiªn nhau nhÆt tõ 1 ®Õn 3 viªn. Ng−êi ph¶i nhÆt viªn bi cuèi cïng th× bÞ thua. a. VÏ toμn bé c©y trß ch¬i b. Sö dông kü thuËt c¾t tØa alpha-beta ®Þnh trÞ cho nót gèc c. Ai sÏ th¾ng trong trß ch¬i nμy nÕu hai ng−êi ®Òu ®i nh÷ng n−íc tèt nhÊt. H·y cho mét tr−êng hîp tæng qu¸t khi ban ®Çu cã n viªn bi vμ mçi lÇn cã thÓ nhÆt tõ 1 ®Õn m viªn. 73
4. XÐt mét trß ch¬i cã 7 c¸i ®Üa. Ng−êi ch¬i 1 chia thμnh 2 chång cã sè ®Üa kh«ng b»ng nhau. Ng−êi ch¬i 2 chän mét chång trong sè c¸c chång con ®Ó chia vμ tiÕp tôc chia thμnh 2 chång kh«ng b»ng nhau. Hai ng−êi lu©n phiªn nhau chia ®Üa nh− vËy cho ®Õn khi kh«ng thÓ chia ®−îc n÷a th× thua a. VÏ toμn bé c©y trß ch¬i b. Sö dông kü thuËt c¾t tØa alpha-beta ®Þnh trÞ cho nót gèc c. Ai sÏ th¾ng trong trß ch¬i nμy nÕu hai ng−êi ®Òu ®i nh÷ng n−íc tèt nhÊt. 74
PhÇn III HỌC MÁY (MACHINE LEARNING) Nội dung chính: Trong phần này, chúng ta sẽ tìm hiểu về một nhánh nghiên cứu hiện đại của Trí Tuệ Nhân Tạo, đó là học máy bao gồm giải thuật ID3, mạng neuron, và giải thuật di truyền. Mục tiêu cần đạt : Sau chương này, sinh viên có thể : Hiểu được mục tiêu của lĩnh vực ‘máy hoc’. Biết 3 tiếp cận học của lĩnh vực học máy. Vận dụng giải thuật ID3 vào các bài toán thực tế Hiểu khái niệm mạng neuron và các vấn đề có liên quan Hiểu giải thuật di truyền và ứng dụng của nó vào các bài toán thực tế. Kiến thức tiên quyết: Biểu diễn tri thức ở dạng luật, tìm kiếm trong không gian trạng thái, khái niệm Entropy trong Lý thuyết thông tin. GIỚI THIỆU Khi được hỏi về những kỹ năng thông minh nào là cơ bản nhất đồng thời khó tự động hóa nhất của con người ngoài các hoạt động sáng tạo nghệ thuật, hành động ra quyết định mang tính đạo đức, trách nhiệm xã hội thì người ta thường đề cập đến vấn đề ngôn ngữ và học. Trãi qua nhiều năm, hai lĩnh vực này vẫn là mục tiêu, thách thức của khoa học TTNT. Tầm quan trọng của việc học thì không cần phải tranh cãi, vì khả năng học chính là một trong những thành tố quan trọng của hành vi thông minh. Mặc dù tiếp cận hệ chuyên gia đã phát triển được nhiều năm, song số lượng các hệ chuyên vẫn còn hạn chế. Một trong những nguyên nhân chủ yếu là do quá trình tích lũy tri thức phức tạp, chi phí phát triển các hệ chuyên gia rất cao, nhưng chúng không có khả năng học, khả năng tự thích nghi khi môi trường thay đổi. Các chiến lược giải quyết vấn đề của chúng cứng nhắc và khi có nhu cầu thay đổi, thì việc sửa đổi một lượng lớn mã chương trình là rất khó khăn. Một giải pháp hiển nhiên là các chương trình tự học lấy cách giải quyết vấn đề từ kinh nghiệm, từ sự giống nhau, từ các ví dụ hay từ những ‘chỉ dẫn’, ‘lời khuyên’, Mặc dù học vẫn còn là một vấn đề khó, nhưng sự thành công của một số chương trình học máy thuyết phục rằng có thể tồn tại một tập hợp các nguyên tắc học tổng quát cho phép xây dựng nên các chương trình có khả năng học trong nhiều lĩnh vực thực tế. Chương này sẽ giới thiệu sơ lược về lĩnh vực nghiên cứu này, đồng thời đi vào chi tiết một số giải thuật học quan trọng. 75
Định nghĩa ‘học’ Theo Herbert Simon: ‘Học được định nghĩa như là bất cứ sự thay đổi nào trong một hệ thống cho phép nó tiến hành tốt hơn trong lần thứ hai khi lặp lại cùng một nhiệm vụ hoặc với một nhiệm vụ khác rút ra từ cùng một quần thể các nhiệm vụ đó’ Định nghĩa này mặc dù ngắn nhưng đưa ra nhiều vấn đề liên quan đến việc phát triển một chương trình có khả năng học. Học liên quan đến việc khái quát hóa từ kinh nghiệm: hiệu quả thực hiện của chương trình không chỉ cải thiện với ‘việc lặp lại cùng một nhiệm vụ’ mà còn với các nhiệm vụ tương tự. Vì những lĩnh vực đáng chú ý thường có khuynh hướng là to lớn, nên các chương trình học – CTH (learner) chỉ có thể khảo sát một phần nhỏ trong toàn bộ các ví dụ có thể; từ kinh nghiệm hạn chế này, CTH vẫn phải khái quát hóa được một cách đúng đắn những ví dụ chưa từng gặp trong lĩnh vực đó. Đây chính là bài toán quy nạp (induction), và nó chính là trung tâm của việc học. Trong hầu hết các bài toán học, dữ liệu luyện tập sẵn có thường không đủ để đảm bảo đưa ra được một khái quát hóa tối ưu, cho dù CTH sử dụng giải thuật nào. Vì vậy, các giải thuật học phải khái quát hóa theo phương pháp heuristic, nghĩa là chúng sẽ chọn một số khía cạnh nào đó mà theo kinh nghiệm là cho hiệu quả trong tương lai để khái quát. Các tiêu chuẩn lựa chọn này gọi là thiên lệch quy nạp (inductive bias). Có nhiều nhiệm vụ học (learning task) khác nhau. Ở đây chỉ trình bày nhiệm vụ học quy nạp (inductive learning), đây là một trong những nhiệm vụ học cơ bản. Nhiệm vụ của CTH là học một khái quát (generalization) từ một tập hợp các ví dụ. Học khái niệm (concept learning) là một bài toán học quy nạp tiêu biểu: cho trước một số ví dụ của khái niệm, chúng ta phải suy ra một định nghĩa cho phép người dùng nhận biết một cách đúng đắn những thể hiện của khái niệm đó trong tương lai. Các tiếp cận học Có ba tiếp cận học: tiếp cận ký hiệu (symbol-based learning), tiếp cận mạng neuron hay kết nối (neural or connectionist networks) và tiếp cận nổi trội (emergent) hay di truyền và tiến hóa (genetic and evolutionary learning). Các CTH thuộc tiếp cận dựa trên ký hiệu biểu diễn vấn đề dưới dạng các ký hiệu (symbol), các giải thuật học sẽ tìm cách suy ra các khái quát mới, hợp lệ, hữu dụng và được biểu diễn bằng các ký hiệu này. Có nhiều giải thuật được đưa ra theo tiếp cận học này, tuy nhiên chương VII chỉ trình bày một giải thuật được sử dụng rộng rãi trong số đó, đó là giải thuật quy nạp cây quyết định ID3. Ngược lại với tiếp cận ký hiệu, tiếp cận kết nối không học bằng cách tích lũy các câu trong một ngôn ngữ ký hiệu. Giống như bộ não động vật chứa một số lượng lớn các tế bào thần kinh liên hệ với nhau, mạng neuron là những hệ thống gồm các neuron nhân tạo liên hệ với nhau. Tri thức của chương trình là ngầm định trong tổ chức và tương tác của các neuron này. chương VIII sẽ đi vào chi tiết của tiếp cận này. Tiếp cận thứ ba là tiếp cận nổi trội mô phỏng cách thức các hệ sinh học tiến hóa trong tự nhiên, nên còn được gọi là tiếp cận di truyền và tiến hóa. chương IX sẽ đi vào chi tiết của tiếp cận này. 76
Chương VII TIẾP CẬN KÝ HIỆU: GIẢI THUẬT QUY NẠP CÂY QUYẾT ĐỊNH ID3 I. Giới thiệu Giải thuật quy nạp cây ID3 (gọi tắt là ID3) là một giải thuật học đơn giản nhưng tỏ ra thành công trong nhiều lĩnh vực. ID3 là một giải thuật hay vì cách biểu diễn tri thức học được của nó, tiếp cận của nó trong việc quản lý tính phức tạp, heuristic của nó dùng cho việc chọn lựa các khái niệm ứng viên, và tiềm năng của nó đối với việc xử lý dữ liệu nhiễu. ID3 biểu diễn các khái niệm (concept) ở dạng các cây quyết định (decision tree). Biểu diễn này cho phép chúng ta xác định phân loại của một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó. Như vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ rèn luyện (training example) hay còn gọi là dữ liệu rèn luyện (training data). Hay nói khác hơn, giải thuật có: Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó. Đầu ra: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chưa gặp trong tương lai. 77
Ví dụ, chúng ta hãy xét bài toán phân loại xem ta ‘có đi chơi tennis’ ứng với thời tiết nào đó không. Giải thuật ID3 sẽ học cây quyết định từ tập hợp các ví dụ sau: Bảng 7.1 - Tập dữ liệu rèn luyện cho khái niệm ‘Có đi chơi tennis không?’ Tập dữ liệu này bao gồm 14 ví dụ. Mỗi ví dụ biểu diễn cho tình trạng thời tiết gồm các thuộc tính quang cảnh, nhiệt độ, độ ẩm và gió; và đều có một thuộc tính phân loại ‘chơi Tennis’ (có, không). ‘Không’ nghĩa là không đi chơi tennis ứng với thời tiết đó, ‘Có’ nghĩa là ngược lại. Giá trị phân loại ở đây chỉ có hai loại (có, không), hay còn ta nói phân loại của tập ví dụ của khái niệm này thành hai lớp (classes). Thuộc tính ‘Chơi tennis’ còn được gọi là thuộc tính đích (target attribute). Mỗi thuộc tính đều có một tập các giá trị hữu hạn. Thuộc tính quang cảnh có ba giá trị (âm u, mưa, nắng), nhiệt độ có ba giá trị (nóng, mát, ấm áp), độ ẩm có hai giá trị (cao, TB) và gió có hai giá trị (mạnh, nhẹ). Các giá trị này chính là ký hiệu (symbol) dùng để biểu diễn bài toán. 78
Từ tập dữ liệu rèn luyện này, giải thuật ID3 sẽ học một cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập này, đồng thời hy vọng trong tương lai, nó cũng sẽ phân loại đúng các ví dụ không nằm trong tập này. Một cây quyết định ví dụ mà giải thuật ID3 có thể quy nạp được là: Hình 7.1 - Cây quyết định cho khái niệm ‘Có đi chơi tennis không?’ Các nút trong cây quyết định biểu diễn cho một sự kiểm tra trên một thuộc tính nào đó, mỗi giá trị có thể có của thuộc tính đó tương ứng với một nhánh của cây. Các nút lá thể hiện sự phân loại của các ví dụ thuộc nhánh đó, hay chính là giá trị của thuộc tính phân loại. Sau khi giải thuật đã quy nạp được cây quyết định, thì cây này sẽ được sử dụng để phân loại tất cả các ví dụ hay thể hiện (instance) trong tương lai. Và cây quyết định sẽ không thay đổi cho đến khi ta cho thực hiện lại giải thuật ID3 trên một tập dữ liệu rèn luyện khác. Ứng với một tập dữ liệu rèn luyện sẽ có nhiều cây quyết định có thể phân loại đúng tất cả các ví dụ trong tập dữ liệu rèn luyện. Kích cỡ của các cây quyết định khác nhau tùy thuộc vào thứ tự của các kiểm tra trên thuộc tính. Vậy làm sao để học được cây quyết định có thể phân loại đúng tất cả các ví dụ trong tập rèn luyện? Một cách tiếp cận đơn giản là học thuộc lòng tất cả các ví dụ bằng cách xây dựng một cây mà có một lá cho mỗi ví dụ. Với cách tiếp cận này thì có thể cây quyết định sẽ không phân loại đúng cho các ví dụ chưa gặp trong tương lai. Vì phương pháp này cũng giống như hình thức ‘học vẹt’, mà cây không hề học được một khái quát nào của khái niệm cần học. Vậy, ta nên học một cây quyết định như thế nào là tốt? Occam’s razor và một số lập luận khác đều cho rằng ‘giả thuyết có khả năng nhất là giả thuyết đơn giản nhất thống nhất với tất cả các quan sát’, ta nên luôn luôn chấp nhận những câu trả lời đơn giản nhất đáp ứng một cách đúng đắn dữ liệu của chúng ta. Trong trường hợp này là các giải thuật học cố gắng tạo ra cây quyết định nhỏ nhất phân loại một cách đúng đắn tất cả các ví dụ đã cho. Trong phần kế tiếp, chúng ta sẽ đi vào giải thuật ID3, là một giải thuật quy nạp cây quyết định đơn giản thỏa mãn các vấn đề vừa nêu. 79
II. Giải thuật ID3 xây dựng cây quyết định từ trên–xuống ID3 xây dựng cây quyết định (cây QĐ) theo cách từ trên xuống. Lưu ý rằng đối với bất kỳ thuộc tính nào, chúng ta cũng có thể phân vùng tập hợp các ví dụ rèn luyện thành những tập con tách rời, mà ở đó mọi ví dụ trong một phân vùng (partition) có một giá trị chung cho thuộc tính đó. ID3 chọn một thuộc tính để kiểm tra tại nút hiện tại của cây và dùng trắc nghiệm này để phân vùng tập hợp các ví dụ; thuật toán khi đó xây dựng theo cách đệ quy một cây con cho từng phân vùng. Việc này tiếp tục cho đến khi mọi thành viên của phân vùng đều nằm trong cùng một lớp; lớp đó trở thành nút lá của cây. Vì thứ tự của các trắc nghiệm là rất quan trọng đối với việc xây dựng một cây QĐ đơn giản, ID3 phụ thuộc rất nhiều vào tiêu chuẩn chọn lựa trắc nghiệm để làm gốc của cây. Để đơn giản, phần này chỉ mô tả giải thuật dùng để xây dựng cây QĐ, với việc giả định một hàm chọn trắc nghiệm thích hợp. Phần kế tiếp sẽ trình bày heuristic chọn lựa của ID3. Ví dụ, hãy xem xét cách xây dựng cây QĐ của ID3 trong hình sau từ tập ví dụ rèn luyện trong bảng 7.1. Hình 7.2 - Một phần cây quyết định xây dựng được Bắt đầu với bảng đầy đủ gồm 14 ví dụ rèn luyện, ID3 chọn thuộc tính quang cảnh để làm thuộc tính gốc sử dụng hàm chọn lựa thuộc tính mô tả trong phần kế tiếp. Trắc nghiệm này phân chia tập ví dụ như cho thấy trong hình 7.2 với phần tử của mỗi phân vùng được liệt kê bởi số thứ tự của chúng trong bảng. * ID3 xây dựng cây quyết định theo giải thuật sau: Function induce_tree(tập_ví_dụ, tập_thuộc_tính) begin if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then return một nút lá được gán nhãn bởi lớp đó else if tập_thuộc_tính là rỗng then return nút lá được gán nhãn bởi tuyển của tất cả các lớp trong tập_ví_dụ else begin chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại; 80
xóa P ra khỏi tập_thuộc_tính; với mỗi giá trị V của P begin tạo một nhánh của cây gán nhãn V; Đặt vào phân_vùng các ví dụ trong tập_ví_dụ có giá trị V V tại thuộc tính P; Gọi induce_tree(phân_vùng , tập_thuộc_tính), gắn kết quả V vào nhánh V end end end ID3 áp dụng hàm induce_tree một cách đệ quy cho từng phân vùng. Ví dụ, phân vùng của nhánh “Âm u” có các ví dụ toàn dương, hay thuộc lớp ‘Có’, nên ID3 tạo một nút lá với nhãn là lớp ‘Có’. Còn phân vùng của hai nhánh còn lại vừa có ví dụ âm, vừa có ví dụ dương. Nên tiếp tục chọn thuộc tính “Độ ẩm” để làm trắc nghiệm cho nhánh Nắng, và thuộc tính Gió cho nhánh Mưa, vì các ví dụ trong các phân vùng con của các nhánh cây này đều thuộc cùng một lớp, nên giải thuật ID3 kết thúc và ta có được cây QĐ như hình 7.3. Hình 7.3 - Cây quyết định đã xây dựng xong. Lưu ý, để phân loại một ví dụ, có khi cây QĐ không cần sử dụng tất cả các thuộc tính đã cho, mặc dù nó vẫn phân loại đúng tất cả các ví dụ. * Các khả năng có thể có của các phân vùng (partition): Trong quá trình xây dựng cây QĐ, phân vùng của một nhánh mới có thể có các dạng sau: 81
1. Có các ví dụ thuộc các lớp khác nhau, chẳng hạn như có cả ví dụ âm và dương như phân vùng “Quang cảnh = Nắng” của ví dụ trên => giải thuật phải tiếp tục tách một lần nữa. 2. Tất cả các ví dụ đều thuộc cùng một lớp, chẳng hạn như toàn âm hoặc toàn dương như phân vùng “Quang cảnh = Âm u” của ví dụ trên => giải thuật trả về nút lá với nhãn là lớp đó. 3. Không còn ví dụ nào => giải thuật trả về mặc nhiên 4. Không còn thuộc tính nào => nghĩa là dữ liệu bị nhiễu, khi đó giải thuật phải sử dụng một luật nào đó để xử lý, chẳng hạn như luật đa số (lớp nào có nhiều ví dụ hơn sẽ được dùng để gán nhãn cho nút lá trả về). Từ các nhận xét này, ta thấy rằng để có một cây QĐ đơn giản, hay một cây có chiều cao là thấp, ta nên chọn một thuộc tính sao cho tạo ra càng nhiều các phân vùng chỉ chứa các ví dụ thuộc cùng một lớp càng tốt. Một phân vùng chỉ có ví dụ thuộc cùng một lớp, ta nói phân vùng đó có tính thuần nhất. Vậy, để chọn thuộc tính kiểm tra có thể giảm thiểu chiều sâu của cây QĐ, ta cần một phép đo để đo tính thuần nhất của các phân vùng, và chọn thuộc tính kiểm tra tạo ra càng nhiều phân vùng thuần nhất càng tốt. ID3 sử dụng lý thuyết thông tin để thực hiện điều này. III. Thuộc tính nào là thuộc tính dùng để phân loại tốt nhất? Quinlan (1983) là người đầu tiên đề xuất việc sử dụng lý thuyết thông tin để tạo ra các cây quyết định và công trình của ông là cơ sở cho phần trình bày ở đây. Lý thuyết thông tin của Shannon (1948) cung cấp khái niệm entropy để đo tính thuần nhất (hay ngược lại là độ pha trộn) của một tập hợp. Một tập hợp là thuần nhất nếu như tất cả các phần tử của tập hợp đều thuộc cùng một loại, và khi đó ta nói tập hợp này có độ pha trộn là thấp nhất. Trong trường hợp của tập ví dụ, thì tập ví dụ là thuần nhất nếu như tất cả các ví dụ đều có cùng giá trị phân loại. Khi tập ví dụ là thuần nhất thì có thể nói: ta biết chắc chắn về giá trị phân loại của một ví dụ thuộc tập này, hay ta có lượng thông tin về tập đó là cao nhất. Khi tập ví dụ có độ pha trộn cao nhất, nghĩa là số lượng các ví dụ có cùng giá trị phân loại cho mỗi loại là tương đương nhau, thì khi đó ta không thể đoán chính xác được một ví dụ có thể có giá trị phân loại gì, hay nói khác hơn, lượng thông tin ta có được về tập này là ít nhất. Vậy, điều ta mong muốn ở đây là làm sao chọn thuộc tính để hỏi sao cho có thể chia tập ví dụ ban đầu thành các tập ví dụ thuần nhất càng nhanh càng tốt. Vậy trước hết, ta cần có một phép đo để đo độ thuần nhất của một tập hợp, từ đó mới có thể so sánh tập ví dụ nào thì tốt hơn. Phần kế tiếp sẽ trình bày công thức tính entropy của một tập hợp. III.1 Entropy đo tính thuần nhất của tập ví dụ Khái niệm entropy của một tập S được định nghĩa trong Lý thuyết thông tin là số lượng mong đợi các bít cần thiết để mã hóa thông tin về lớp của một thành viên rút ra một cách ngẫu nhiên từ tập S. Trong trường hợp tối ưu, mã có độ dài ngắn nhất. Theo lý thuyết thông tin, mã có độ dài tối ưu là mã gán –log p bits cho thông điệp có xác 2 suất là p. 82
Trong trường hợp S là tập ví dụ, thì thành viên của S là một ví dụ, mỗi ví dụ thuộc một lớp hay có một giá trị phân loại. Entropy có giá trị nằm trong khoảng [0 1], Entropy(S) = 0 tập ví dụ S chỉ toàn ví dụ thuộc cùng một loại, hay S là thuần nhất. Entropy(S) = 1 tập ví dụ S có các ví dụ thuộc các loại khác nhau với độ pha trộn là cao nhất. 0 < Entropy(S) < 1 tập ví dụ S có số lượng ví dụ thuộc các loại khác nhau là không bằng nhau. Để đơn giản ta xét trường hợp các ví dụ của S chỉ thuộc loại âm (-) hoặc dương (+). Cho trước: Tập S là tập dữ liệu rèn luyện, trong đó thuộc tính phân loại có hai giá trị, giả sử là âm (-) và dương (+) p là phần các ví dụ dương trong tập S. + p_ là phần các ví dụ âm trong tập S. Khi đó, entropy đo độ pha trộn của tập S theo công thức sau: Entropy(S) = -p log2 p -p_ log2 p_ + + Một cách tổng quát hơn, nếu các ví dụ của tập S thuộc nhiều hơn hai loại, giả sử là có c giá trị phân loại thì công thức entropy tổng quát là: c Entropy(S) = ∑ − pi log2 pi i=1 Hình 7.4 minh họa sự phụ thuộc của giá trị entropy vào xác suất xuất hiện của ví dụ dương. Hình 7.4 - Entropy(S) 83
III.2 Lượng thông tin thu được đo mức độ giảm entropy mong đợi Entropy là một số đo đo độ pha trộn của một tập ví dụ, bây giờ chúng ta sẽ định nghĩa một phép đo hiệu suất phân loại các ví dụ của một thuộc tính. Phép đo này gọi là lượng thông tin thu được, nó đơn giản là lượng giảm entropy mong đợi gây ra bởi việc phân chia các ví dụ theo thuộc tính này. Một cách chính xác hơn, Gain(S,A) của thuộc tính A, trên tập S, được định nghĩa như sau: | Sv | Gain(S,A) = Entropy(S) - ∑ Entropy(Sv ) v∈Value( A) | S | trong đó Values(A) là tập hợp có thể có các giá trị của thuộc tính A, và S là tập con v của S chứa các ví dụ có thuộc tính A mang giá trị v. Câu hỏi : Áp dụng giải thuật ID3 kết hợp với công thức entropy và gain để tạo ra cây quyết định đơn giản nhất cho bài toán phân loại xem ta ‘có đi chơi tennis’ từ tập dữ liệu rèn luyện đã cho trong bảng 7.1. IV. Tìm kiếm không gian giả thuyết trong ID3 Cũng như các phương pháp học quy nạp khác, ID3 cũng tìm kiếm trong một không gian các giả thuyết một giả thuyết phù hợp với tập dữ liệu rèn luyện. Không gian giả thuyết mà ID3 tìm kiếm là một tập hợp các cây quyết định có thể có. ID3 thực hiện một phép tìm kiếm từ đơn giản đến phức tạp, theo giải thuật leo-núi (hill climbing), bắt đầu từ cây rỗng, sau đó dần dần xem xét các giả thuyết phức tạp hơn mà có thể phân loại đúng các ví dụ rèn luyện. Hàm đánh giá được dùng để hướng dẫn tìm kiếm leo núi ở đây là phép đo lượng thông tin thu được. Từ cách nhìn ID3 như là một giải thuật tìm kiếm trong không gian các giả thuyết, ta có một số nhận xét như sau: Không gian giả thuyết các cây quyết định của ID3 là một không gian đầy đủ các cây quyết định trên các thuộc tính đã cho trong tập rèn luyện. Điều này có nghĩa là không gian mà ID3 tìm kiếm chắc chắn có chứa cây quyết định cần tìm. Trong khi tìm kiếm, ID3 chỉ duy trì một giả thuyết hiện tại. Vì vậy, giải thuật này không có khả năng biểu diễn được tất cả các cây quyết định khác nhau có khả năng phân loại đúng dữ liệu hiện có. Giải thuật thuần ID3 không có khả năng quay lui trong khi tìm kiếm. Vì vậy, nó có thể gặp phải những hạn chế giống như giải thuật leo núi, đó là hội tụ về cực tiểu địa phương. 84
Hình 7.5 - Không gian tìm kiếm của ID3. Vì ID3 sử dụng tất cả các ví dụ ở mỗi bước để đưa ra các quyết định dựa trên thống kê, nên kết quả tìm kiếm của ID3 rất ít bị ảnh hưởng bởi một vài dữ liệu sai (hay dữ liệu nhiễu). Trong quá trình tìm kiếm, giải thuật ID3 có xu hướng chọn cây quyết định ngắn hơn là những cây quyết định dài. Đây là tính chất thiên lệch quy nạp của ID3. V. Đánh giá hiệu suất của cây quyết định Một cây quyết định sinh ra bởi ID3 được đánh giá là tốt nếu như cây này có khả năng phân loại đúng được các trường hợp hay ví dụ sẽ gặp trong tương lai, hay cụ thể hơn là có khả năng phân loại đúng các ví dụ không nằm trong tập dữ liệu rèn luyện. Để đánh giá hiệu suất của một cây quyết định người ta thường sử dụng một tập ví dụ tách rời, tập này khác với tập dữ liệu rèn luyện, để đánh giá khả năng phân loại của cây trên các ví dụ của tập này. Tập dữ liệu này gọi là tập kiểm tra (validation set). Thông thường, tập dữ liệu sẵn có sẽ được chia thành hai tập: tập rèn luyện thường chiếm 2/3 số ví dụ và tập kiểm tra chiếm 1/3. 85
VI. Chuyển cây về các luật Thông thường, cây quyết định sẽ được chuyển về dạng các luật để thuận tiện cho việc cài đặt và sử dụng. Ví dụ cây quyết định cho tập dữ liệu rèn luyện trong bảng 9.1 có thể được chuyển thành một số luật như sau : If (Quang-cảnh =nắng) ∧ (Độ ẩm = Cao) Then Chơi-Tennis = No If (Quang-cảnh =nắng) ∧ (Độ ẩm = TB) Then Chơi-Tennis = Yes If (Quang-cảnh =Âm u) Then Chơi-Tennis = Yes VII. Khi nào nên sử dụng ID3 Giải thuật ID3 là một giải thuật học đơn giản nhưng nó chỉ phù hợp với một lớp các bài toán hay vấn đề có thể biểu diễn bằng ký hiệu. Chính vì vậy, giải thuật này thuộc tiếp cận giải quyết vấn đề dựa trên ký hiệu (symbol – based approach). Tập dữ liệu rèn luyện ở đây bao gồm các ví dụ được mô tả bằng các cặp “Thuộc tính – giá trị”, như trong ví dụ ‘Chơi tennis’ trình bày trong suốt chương này, đó là ‘Gió – mạnh’, hay ‘Gió – nhẹ’, và mỗi ví dụ đều có một thuộc tính phân loại, ví dụ như ‘chơi_tennis’, thuộc tính này phải có giá trị rời rạc, như có, không. Tuy nhiên, khác với một số giải thuật khác cũng thuộc tiếp cận này, ID3 sử dụng các ví dụ rèn luyện ở dạng xác suất nên nó có ưu điểm là ít bị ảnh hưởng bởi một vài dữ liệu nhiễu. Vì vậy, tập dữ liệu rèn luyện ở đây có thể chứa lỗi hoặc có thể thiếu một vài giá trị ở một số thuộc tính nào đó. Một giải pháp thường được áp dụng đối với các dữ liệu bị thiếu là sử dụng luật đa số, chương trình tiền xử lý dữ liệu sẽ điền vào các vị trí còn trống giá trị có tần số xuất hiện cao nhất của thuộc tính đó. Bên cạnh các vấn đề cơ bản được trình bày trong phần này, ID3 còn được thảo luận nhiều vấn đề liên quan như làm sao để tránh cho cây quyết định không bị ảnh hưởng quá nhiều (overfitting) vào dữ liệu rèn luyện, để nó có thể tổng quát hơn, phân loại đúng được cho các trường hợp chưa gặp. Có nhiều giải pháp đã được đưa ra như cắt tỉa lại cây quyết định sau khi học, hoặc cắt tỉa các luật sau khi chuyển cây về dạng luật. Một vấn đề khác nữa đó là nếu như một vài thuộc tính nào đó có giá trị liên tục thì sao. Giải quyết các vấn đề này dẫn đến việc sinh ra nhiều thế hệ sau của ID3, một 86
giải thuật nổi bật trong số đó là C4.5 (Quinlan 1996). Ngoài ra, một số kỹ thuật được tạo ra để thao tác trên dữ liệu nhằm tạo ra các cây quyết định khác nhau trên cùng tập dữ liệu rèn luyện đã cho như kỹ thuật bagging and boosting. 87
Chương VIII TIẾP CẬN KẾT NỐI: MẠNG NEURON I. Giới thiệu Các mô hình học theo tiếp cận này bắt chước theo cách học của các hệ thần kinh sinh vật. Các hệ thống theo mô hình này có khi còn được gọi là các hệ kết nối (connectionist systems), tính toán neural (Neural computing), mạng neural (Neural Networks), các hệ xử lý phân tán song song (parallel distributed processing – PDP). Không giống như các giải thuật của tiếp cận ký hiệu, các mô hình này không sử dụng ký hiệu một cách tường minh để giải quyết vấn đề. Thay vào đó, chúng giữ cho trí tuệ phát triển trong các hệ thống gồm các thành phần (neuron sinh học hay neuron nhân tạo) đơn giản, tương tác thông qua một quá trình học hay thích nghi mà nhờ đó kết nối giữa các thành phần này được điều chỉnh. Việc xử lý của các hệ thống này được phân tán trên một tập hợp các lớp neuron. Các hệ thống này giải quyết vấn đề song song theo nghĩa rằng tất cả các neuron trong tập hợp hay trong các lớp sẽ xử lý tín hiệu vào một cách đồng thời và độc lập. Trong khi các giải thuật của tiếp cận ký hiệu sử dụng ký hiệu để mô tả các mẫu của bài toán như ta đã thấy trong giải thuật ID3 thì những nhà thiết kế mạng neuron phải tạo ra một sơ đồ mã hóa các mẫu (pattern) của bài toán thành các đại lượng số để đưa vào mạng. Việc chọn lựa một sơ đồ mã hóa thích hợp đóng vai trò quyết định cho sự thành công hay thất bại trong việc học của mạng. Các mẫu (pattern) của bài toán được mã hóa thành các vector số. Các kết nối giữa các thành phần, hay neuron, cũng được biểu diễn bằng các giá trị số. Cuối cùng, sự biến đổi của các mẫu cũng là kết quả của các phép toán số học, thông thường là phép nhân ma trận. Sự chọn lựa kiến trúc kết nối của nhà thiết kế mạng neuron góp phần vào tính thiên lệch quy nạp (inductive bias) của hệ thống. Các giải thuật và kiến trúc dùng để cài đặt mạng neuron thường được huấn luyện (trained) hay tạo điều kiện (conditioned) chứ không được lập trình một cách tường tận. Và đây chính là sức mạnh chủ yếu của tiếp cận này. Các phương pháp của tiếp cận này phát huy sức mạnh của chúng trong các bài toán mà khó có thể giải quyết bằng các mô hình ký hiệu. Tiêu biểu là các bài toán đòi hỏi các kỹ năng dựa vào nhận thức, hay các bài toán thiếu một cú pháp định nghĩa rõ ràng. Các bài toán thích hợp với tiếp cận kết nối thường là: Bài toán phân loại (classification): quyết định một giá trị đưa vào thuộc loại hay nhóm nào Bài toán nhận dạng mẫu (pattern recognition): nhận dạng cấu trúc trong các dữ liệu có thể là bị nhiễu. Bài toán dự đoán (prediction): chẳng hạn như nhận dạng bệnh từ các triệu chứng, nhận dạng tác nhân từ các hiệu ứng, Bài toán tối ưu (optimization): tìm một tổ chức ràng buộc tốt nhất 88
Bài toán lọc nhiễu (noise filtering): hay phân biệt các tín hiệu với nền, tìm ra các thành phần không quan trọng trong một tín hiệu. II. Cơ bản về mạng kết nối Thành phần cơ bản của một mạng neuron là một neuron nhân tạo, như mô tả trong hình 9.6 sau đây. II.1 Một neuron nhân tạo Hình 8. 1 minh họa một neuron nhân tạo bao gồm: Hình 8.1- Một neuron nhân tạo. Các tín hiệu đầu vào x . Các dữ liệu này có thể đến từ môi trường, hay được kích i hoạt từ các neuron khác. Các mô hình khác nhau có thể có miền giá trị của đầu vào khác nhau; thông thường các giá trị đầu vào này là các số rời rạc (discrete) lấy từ tập {0,1} hay {-1,1} hay số thực. Một tập các trọng số (weight) có giá trị thực wi. Các trọng số này dùng để mô tả sức mạnh kết nối, hay sức mạnh của các kết nối thiên lệch (bias link) Một mức kích hoạt (activation level) hay hàm kích hoạt Σwixi. Mức kích hoạt của một neuron được xác định bởi sức mạnh tích lũy từ các tín hiệu đầu vào của nó nơi mà mỗi tín hiệu đầu vào được tỷ lệ lại bằng trọng số kết nối wi ở đầu vào đó. Vì vậy, mức kích họat được tính toán bằng cách lấy tổng các giá trị đầu vào sau khi được tỉ lệ hóa, Σwixi. Một hàm ngưỡng (threshold function) f. Hàm này tính kết quả đầu ra của neuron bằng cách xác định xem mức kích hoạt nằm dưới hay trên một giá trị ngưỡng là ít hay nhiều. Hàm ngưỡng này có khuynh hướng tạo ra trạng thái tắt/mở của các neuron. II.2 Các đặc trưng của một mạng Neuron Ngoài các tính chất của một neuron đơn lẻ, một mạng neuron còn được đặc trưng bởi các tính chất toàn cục như sau: Hình thái mạng (network topology): là mô hình hay mẫu kết nối giữa các neuron đơn lẻ. 89
Hình 8.2 - Các hình thái mạng neuron khác nhau. Giải thuật học (learning algorithm): là giải thuật dùng để điều chỉnh các trọng số ở các đầu vào của các neuron. Trong các phần tiếp theo của chương này sẽ trình bày một số giải thuật học tiêu biểu. Sơ đồ mã hóa (encoding schema): Bao gồm việc thông dịch dữ liệu thực tế thành các giá trị đầu vào của mạng, và việc thông dịch giá trị đầu ra của mạng thành một kết quả có ý nghĩa. II.3 Mạng neuron McCulloch-Pitts Ví dụ đầu tiên về tính toán neural được MacCulloch và Pitts đưa ra vào 1943. Đầu vào của một neuron McCulloch-Pitts là +1 (kích thích) hoặc –1 (ức chế). Hàm kích hoạt nhân mỗi đầu vào với giá trị trọng số tương ứng và cộng chúng lại; nếu tổng lớn hơn hay bằng không, thì neuron trả về 1, ngược lại, là –1. McCulloch-Pitts cho thấy các neuron này có thể được xây dựng để tính toán bất cứ hàm logic nào, chứng minh rằng các hệ thống gồm các neuron này cung cấp một mô hình tính toán đầy đủ. Hình 8.3 minh họa các neuron McCulloch-Pitts dùng để tính hàm logic and và or. Hình 8.3 - Các neuron McCulloch-Pitts dùng để tính toán các hàm logic and và or. Các neuron này có 3 đầu vào: x và y là các giá trị cần đưa vào, còn đầu vào thứ ba, đôi khi còn được gọi là một thiên lệch (bias), có giá trị hằng là +1. Ba đầu vào của neuron and có 3 trọng số tương ứng là +1, +1 và –2. Vì vậy, với các giá trị bất kỳ của x, y, neuron tính giá trị x+y-2; nếu giá trị này nhỏ hơn 0, nó trả về – 1. Ngược lại trả về 1. 90
Bảng bên dưới minh họa cho tính toán neuron x and y. Mặc dù McCulloch-Pitts chứng minh cho sức mạnh của tính toán neural, nhưng sức hấp dẫn của tiếp cận này chỉ thực sự bắt đầu khi các giải thuật học thực tế bắt đầu phát triển. Phiên bản đầu tiên của mạng neuron có kèm giải thuật học được Frank Rosenblatt đưa ra vào cuối thập niên 1950, có tên gọi là perceptron. III. Học perceptron III.1 Giải thuật học perceptron Perceptron là mạng neuron đơn tầng. Cách lan truyền tín hiệu của perceptron tương tự với neuron McCulloch-Pitts. Các giá trị đầu vào và các mức kích hoạt của perceptron là -1 hoặc 1; trọng số là các số thực. Mức kích hoạt được xác định qua tổng Σwixi. Perceptron sử dụng một hàm ngưỡng giới hạn cứng, khi một kích hoạt nằm bên trên ngưỡng, hàm sẽ cho kết quả là 1, và -1 nếu ngược lại. Cho trước các giá trị đầu vào x , i các trọng số w , và một ngưỡng, t, hàm ngưỡng f của perceptron sẽ trả về: i Perceptron sử dụng một hình thức đơn giản của học có giám sát (supervised learning). Sau khi perceptron cố gắng giải quyết một mẫu bài toán (mẫu này rút ra từ tập dữ liệu rèn luyện), chương trình đóng vai trò như một người thầy giáo sẽ cung cấp cho nó kết quả đúng của mẫu bài toán đó (giá trị này cũng lấy từ tập dữ liệu rèn luyện). Dựa vào sự khác biệt giữa kết quả đúng được cung cấp và kết quả mà perceptron tính toán được, nó sẽ tự điều chỉnh các trọng số của nó để làm thu hẹp khoảng cách lỗi. Perceptron sử dụng luật như sau: với c là một hằng số cho trước, hằng số này thể hiện tốc độ học và d là giá trị đầu ra mong muốn, perceptron sẽ điều chỉnh trọng số trên thành phần thứ i của vectơ đầu vào một lượng Δwi = c(d – f(Σwixi))xi f(Σwixi) chính là giá trị đầu ra của perceptron, nó có giá trị +1 hoặc -1. Vì vậy, hiệu giữa d và f(Σwixi) là 0, 2 hoặc -2. Vì vậy, với mỗi thành phần của vectơ đầu vào: Nếu giá trị đầu ra mong muốn và giá trị đầu ra thật bằng nhau, thì không làm gì cả. Nếu giá trị đầu ra thực là -1 và 1 là giá trị mong muốn, thì tăng trọng số của đường thứ i lên 2cxi. 91
Nếu giá trị đầu ra thực là 1 và -1 là giá trị mong muốn, thì giảm trọng số của đường thứ i -2cxi Sở dĩ c được gọi là hằng số thể hiện tốc độ học vì nếu c lớn thì các giá trị điều chỉnh Δwi sẽ lớn, như vậy, đẩy nhanh quá trình wi hội tụ về giá trị đúng của nó. Sau khi được huấn luyện bằng một tập hợp khá lớn các ví dụ rèn luyện cho trước, thủ tục này sẽ sinh ra một tập các trọng số có tính chất làm giảm thiểu trung bình lỗi trên toàn tập ví dụ rèn luyện. Theo Minsky và Papert 1969, nếu tồn tại một tập hợp các trọng số đem lại đầu ra đúng cho mọi ví dụ rèn luyện, thì thủ tục học perceptron sẽ học được nó. III.2 Sử dụng mạng perceptron cho bài toán phân loại Bài toán phân loại Hình 8.4 - Một hệ thống phân loại đầy đủ. Hình trên đưa ra một cái nhìn khái quát về bài toán phân loại. Dữ liệu thô từ một không gian các điểm có thể có sau khi qua bộ chuyển đổi (transducer) sẽ được chọn và chuyển đổi thành một không gian các dữ liệu hay mẫu mới. Trong không gian mẫu mới này, bộ trích lọc đặc trưng (feature extractor) sẽ chọn ra các đặc trưng của dữ liệu, và cuối cùng, dữ liệu thể hiện qua các đặc trưng sẽ được đưa vào máy phân loại (classifier) để cho ra kết quả lớp phân loại (class) của dữ liệu đó. Trong dây chuyền này, mạng perceptron nói riêng và mạng neuron nói chung đóng vai trò như một máy phân loại. Một dữ liệu đầu vào sẽ được biểu diễn như một vectơ gồm n thành phần (thể hiện cho n đặc trưng) x , x , , x . Các dữ liệu này có thể thuộc một trong m lớp class , class , 1 2 n 1 2 class . Máy phân loại sẽ có nhiệm vụ xác định xem dữ liệu đầu vào thuộc về lớp m nào. Ví dụ perceptron Trong ví dụ đơn giản dưới đây, bộ chuyển đổi và bộ trích lọc đặc trưng đã chuyển thông tin của bài toán thành các tham số của không gian hai chiều. Bảng 8.1 thể hiện dữ liệu rèn luyện của perceptron gồm có 2 đặc trưng (x và x ) mang giá trị thực, và 1 2 kết quả mong muốn (output) gồm hai giá trị 1 hoặc -1, thể hiện cho hai lớp phân loại 92
của dữ liệu. Hình 8.5 thể hiện hình ảnh của các điểm dữ liệu trong bảng 8.1 cùng với đường phân cách hai lớp dữ liệu được tạo ra sau khi mạng percpetron được huấn luyện trên tập dữ liệu này. Bảng 8.1 - Tập dữ liệu cho bài toán phân loại của perceptron. Hình 8.5 - Đồ thị hai chiều của các điểm dữ liệu trong bảng 8.1. Perceptron cung cấp một phép tách tuyến tính của các tập hợp dữ liệu. Perceptron dùng để phân loại bài toán này được thiết kế như sau: Tín hiệu đầu vào: 2 tham số x và x , cùng với một đầu vào thiên lệch (bias) luôn có 1 2 giá trị 1. 93
Mức kích hoạt: net = w x + w x + w 1 1 2 2 3 Hàm ngưỡng f(net) là một hàm dấu, hay còn gọi là hàm ngưỡng hai cực tuyến tính Hình 8.6 - Mạng perceptron cho ví dụ của bảng 8.1. f(net) = +1, nếu net>0 f(net) = -1, nếu net<=0 Tín hiệu thiên lệch phục vụ cho việc chuyển dịch hàm ngưỡng trên trục tung. Phạm vi của chuyển dịch này sẽ được học bằng cách điều chỉnh trọng số w3 trong khi huấn luyện mạng. Bây giờ chúng ta sử dụng các điểm dữ liệu của bảng 8.1 để luyện tập perceptron của hình 8.1. Giả thiết ban đầu các trọng số w có giá trị ngẫu nhiên lần lượt là: [0.75,0.5,-0.6] i Sử dụng giải thuật học perceptron trình bày ở trên với tốc độ học c được chọn là một số dương nhỏ 0.2 Chúng ta bắt đầu bằng ví dụ đầu tiên trong bảng 8.1: 1 f(net) = f(0.75 * 1 + 0.5 * 1 – 0.6 *1 ) = f(0.65) = 1 1 Ta thấy f(net) có giá trị đúng với giá trị đầu ra mong muốn, nên ta không điều chỉnh 2 1 trọng số. Cho nên W = W , W là vectơ trọng số đại diện cho 3 trọng số w1, w2,w3. Đến ví dụ thứ 2: 2 f(net) = f(0.75 * 9.4 + 0.5 * 6.4 – 0.6 *1 ) = f(9.65) = 1 Nhưng giá trị mong đợi ở đây là -1, vì vậy, ta cần điều chỉnh trọng số theo luật học: t t-1 t-1 t-1 t-1 W = W + c( d – f(net) )X 94
trong đó c là hằng số học W, X là vectơ trọng số, và vectơ dữ liệu đầu vào t là thời điểm 2 2 Trong trường hợp này: c = 0.2, d = -1, và f(net) = 1 Áp dụng luật học trên, ta có: ⎡ 0.75 ⎤ ⎡9.4⎤ ⎡− 3.01⎤ 3 2 2 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ W = W +0.2(-1-1)X = ⎢ 0.5 ⎥ − 0.4⎢6.4⎥ = ⎢− 2.06⎥ ⎣⎢− 0.6⎦⎥ ⎣⎢1.0⎦⎥ ⎣⎢ −1.0 ⎦⎥ Bây giờ chúng ta xét ví dụ thứ 3: 3 f(net) = f(-3.01 * 2.5 -2.06 * 2.1 – 1.0 *1 ) = f(-12.84) = -1 Trong khi giá trị mong đợi của ví dụ này là 1, nên các trọng số tiếp tục được điều chỉnh ⎡− 3.01⎤ ⎡2.5⎤ ⎡− 2.01⎤ 4 3 3 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ W = W +0.2(-1-(-1))X = ⎢− 2.06⎥ + 0.4⎢2.1⎥ = ⎢−1.22⎥ ⎣⎢ −1.6 ⎦⎥ ⎣⎢1.0⎦⎥ ⎣⎢− 0.60⎦⎥ Cứ tiếp tục như thế, sau 10 lần lặp, đường phân cách tuyến tính như trong hình 8.5 xuất hiện. Sau khi lặp lại việc huấn luyện perceptron trên tập dữ liệu đã cho, khoảng 500 lần lặp tổng cộng, vectơ trọng số hội tụ về giá trị [-1.3, -1.1, 10.9]. Và đây chính là các hệ số của phương trình đường phân cách tuyến tính trong hình 8.5: -1.3 * x – 1.1 * x + 10.9 = 0. 1 2 III.3 Giới hạn của perceptron – tính tách rời tuyến tính của bài toán Ban đầu, mạng perceptron được chào đón một cách nhiệt tình. Tuy nhiên, Nils Nilsson (1965) và những người khác đã phân tích những giới hạn của mô hình perceptron. Họ chứng minh rằng perceptron không thể giải quyết một lớp các bài toán khó, cụ thể là các bài toán mà các điểm dữ liệu không thể tách rời tuyến tính. Một ví dụ cho bài toán phân loại không tuyến tính đó là phép toán ex-or. Ex-or có bảng chân lý như sau: x1 x2 Output 1 1 0 1 0 1 0 1 1 0 0 0 Bảng 8.2 - Bảng chân lý của phép toán logic ex-or. 95
Hình 8.7 - Đồ thị thể hiện các điểm dữ liệu của bài toán Ex-Or Từ đồ thị hình 8.7, ta thấy không thể tìm được bất cứ một đường thẳng nào có thể tách rời các điểm dữ liệu của lớp 0: {(0,0), (1,1)} ra khỏi các điểm dữ liệu của lớp 1: {(0,1),(1,0)}. Chúng ta có thể quan niệm tập hợp các giá trị dữ liệu đối với một mạng neuron như dùng để định nghĩa một không gian. Mỗi tham số của dữ liệu đầu vào tương ứng với một chiều trong không gian, và mỗi giá trị đầu vào sẽ định nghĩa một điểm trong không gian đó. Trong bài toán ex-or trên, bốn giá trị đầu vào, được đánh chỉ số theo các tọa độ x1, x2, tạo thành các điểm dữ liệu trong hình 8.7. Bài toán học một phân loại nhị phân của các dữ liệu rèn luyện rút lại thành bài toán tách các điểm này thành hai nhóm. Như vậy, đối với một không gian n chiều, một sự phân loại là phân tách được một cách tuyến tính nếu như các lớp của nó có thể được tách ra bởi một mặt phẳng n-1 chiều. (Trong không gian hai chiều thì mặt siêu phẳng n-1 chiều là một đường thẳng, trong không gian 3 chiều thì nó là một mặt phẳng, ). III.4 Luật Delta Một cách dễ dàng để tổng quát hóa mạng perceptron là thay hàm ngưỡng giới hạn cứng bằng một hàm kích hoạt kiểu khác. Chẳng hạn như, hàm kích hoạt liên tục (để có khả năng lấy vi phân) tạo điều kiện cho các giải thuật học phức tạp hơn. 96
a. A hard limiting and bipolar b. A sigmoidal and c. The sigmoidal, biased linear threshold unipolar threshold and squashed. As getλ larger the sigmoid approximates a linear threshold Hình 8.8 - Các hàm ngưỡng. Hình 8.8 minh họa đồ thị của một số hàm ngưỡng: hình 8.8a là một hàm ngưỡng hai cực, hình 8.8b minh họa một hàm kích hoạt sigmoidal thông dụng (hàm sigmoidal là hàm có hình cong như chữ S), được gọi là hàm logistic, hàm này có công thức như sau: -λ*net f(net) = 1/(1 + e ) với net = Σiwixi Cũng như các hàm định nghĩa trước đây, xi là đầu vào của đường thứ i, wi là trọng số trên đường vào i, và λ là “tham số nén” được sử dụng để điều chỉnh độ cong của đường. Khi λ càng lớn, thì đường cong càng tiệm cận với hàm ngưỡng tuyến tính (trong hình 8.8a). Khi càng tiến gần đến 1, nó càng gần như là một đường thẳng. Hàm logistic có một tính chất đặc biệt là, đạo hàm của hàm này có một công thức rất đơn giản: f ’(net) = f(net) * (1- f(net)) (1-1) Từ hình 8.8 ta thấy với các hàm ngưỡng liên tục, neuron sẽ cho kết quả chính xác hơn nhờ vào việc điều chỉnh tham số λ. Việc đưa ra các hàm kích hoạt liên tục đã làm đề xuất các tiếp cận mới để làm giảm lỗi trong khi học. Qui luật học do Widrow-Hoff đưa ra vào khoảng 1960 độc lập với hàm kích hoạt, tối thiểu hóa bình phương của lỗi giữa giá trị đầu ra mong muốn và kích hoạt của neuron, neti = WXi. Một trong số luật học quan trọng cho các hàm kích hoạt liên tục là luật delta (Rumelhart et al. 1986). Để sử dụng luạt delta, mạng phải sử dụng một hàm ngưỡng liên tục để có thể lấy vi phân. Hàm logistic đã trình bày bên trên có được tính chất này. Khi đó công thức học theo luật delta cho việc điều chỉnh trọng số ở đầu vào thứ j của nút thứ i là: Δw = c(di – Oi) f’(neti)xj 97
trong đó, c là hằng số điều khiển tốc độ học, di và Oi là các giá trị đầu ra thực sự và mong muốn của nút thứ i. f’(net ) là đạo hàm của hàm kích hoạt cho nút thứ i, và x là i j đầu vào thứ j của nút thứ i. Thay thế công thức đạo hàm (1-1) của hàm logistic f’(net), ta được công thức để điều chỉnh trọng số như sau: Δw = c(di – Oi) Oi (1 – Oi) xj (1-2) Từ công thức này cho thấy, công thức điều chỉnh trọng số này chỉ có thể áp dụng cho các nút của mạng perceptron đơn tầng, vì tại đó ta mới có các giá trị đầu ra mong muốn d . i IV. Học Lan truyền ngược Như đã phân tích ở trên, ta thấy các mạng perceptron đơn tầng có khả năng giới hạn, chúng không thể phân loại được các bài toán không tách rời tuyến tính. Trong phần tiếp theo, chúng ta sẽ thấy rằng các mạng đa tầng có thể giải quyết được các bài toán này. Hình 8.9 - Học lan truyền ngược trong mạng kết nối có một tầng ẩn. Các neuron trong một mạng đa tầng (xem hình 8.9) được kết nối với nhau theo từng lớp, trong đó các neuron ở tầng k sẽ truyền kích hoạt của chúng chỉ cho các neuron ở tầng k+1. Xử lý tín hiệu đa tầng có nghĩa là các lỗi nằm sâu bên trong mạng có thể lan ra và phát triển một cách phức tạp thông qua các tầng liên tiếp. Vì vậy, việc phân tích nguyên nhân gây ra lỗi ở tầng ra (output layer) là rất phức tạp. Giải thuật học lan truyền ngược sẽ cung cấp một phương pháp điều chỉnh trọng số trong trường hợp này. IV.1 Giải thuật học lan truyền ngược Từ lập luận cho rằng tại các nút của một mạng đa tầng, lỗi mà một nút phải chịu trách nhiệm cũng phải được chia phần cho các nút ở tầng ẩn trước nó và vì vậy các trọng số phải được điều chỉnh một cách phù hợp. 98
Giải thuật lan truyền ngược bắt đầu tại tầng ra và truyền các lỗi ngược về xuyên qua các tầng ẩn (như hình 8.10). Hình 8.10 - Σ –delta *w là tổng đóng góp của nút i vào lỗi ở tầng ra. j j ij Luật delta tổng quát để điều chỉnh trọng số của đầu vào thứ k của nút thứ i: Δw = c(d – O ) O (1 – O ) x cho nút ở tầng ra k i i i i k Δw = c Σ (delta w ) O (1 – O ) x cho nút ở tầng ẩn k j j ij i i k với delta = (d – O ) O (1 – O ) j j j j j j chạy trên các nút của tầng kế tiếp mà tại đó nút i truyền các đầu ra của nó. Đối với mạng có nhiều hơn một tầng ẩn, ta cũng áp dụng thủ tục tương tự một cách đệ quy để truyền lỗi từ tầng ẩn thứ n vào tầng ẩn thứ n-1. IV.2 Ví dụ 1: Mạng NetTalk Mạng NETtalk là một ví dụ hay cho việc sử dụng giải pháp mạng neuron để giải quyết một vấn đề học khó. NETtalk học để đọc được văn bản tiếng Anh. Đây là một nhiệm vụ khó khăn đối với tiếp cận học dựa trên ký hiệu, vì phát âm trong tiếng Anh mang tính bất quy tắc. Mặc dù có các chương trình dựa trên luật (rule-based) đã được viết để giải quyết vấn đề này, nhưng chúng đều phức tạp và thực hiện chưa hoàn hảo. NETtalk học để đọc một chuỗi văn bản và trả về một âm vị cùng với trọng âm liên hệ cho mỗi chữ cái trong chuỗi. Vì phát âm của một chữ cái đơn nhất phụ thuộc vào các chữ cái xung quanh nó, người ta đưa vào NETtalk một cửa sổ gồm 7 ký tự. Khi văn bản dịch chuyển qua cửa sổ này, NETtalk trả về một cặp âm vị/trọng âm cho mỗi chữ cái. Hình 8.11 minh họa kiến trúc của mạng NETtalk. Mạng gồm có 3 tầng neuron. Các neuron đầu vào tương ứng với cửa sổ 7 ký tự của văn bản. Mỗi vị trí trong cửa sổ được biểu diễn bởi 29 neuron đầu vào, 26 neurons cho 26 ký tự alphabet, và 3 neurons cho dấu và khoảng trắng. Ký tự ở mỗi ví trí trong cửa sổ sẽ kích hoạt neuron tương ứng. Các neuron đầu ra mã hóa âm sử dụng 21 đặc điểm khác nhau của cách phát âm 99
của con người. 5 neurons còn lại mã hóa dấu nhấn và giới hạn âm tiết. NETtalk có 80 neuron ở tầng ẩn, 26 giá trị đầu ra và 18.629 kết nối. Hình 8.11 - Hình thái mạng của NETtalk. Kết quả của NETtalk là có thể phát âm đúng 60% sau khi rèn luyện với một tập dữ liệu rèn luyện gồm 500 ví dụ và lặp lại 100 lượt. Ngoài kết quả đạt được trên, NETtalk còn cho thấy một số tính chất đáng chú ý của mạng neuron, có nhiều tính chất trong số đó phản ánh bản chất tự nhiên của việc học ở người. Chẳng hạn như, việc học, khi được đo bằng phần trăm câu trả lời đúng, sẽ tiến triển nhanh lúc đầu, sau đó chậm dần khi tỉ lệ đúng tăng lên. Và cũng như con người, khi neuron càng học phát âm được nhiều từ, thì nó càng phát âm đúng các từ mới nhiều hơn. IV.3 Ví dụ 2: Exclusive–or Một ví dụ khác cho mạng đa tầng là dùng để giải quyết bài toán Ex-or mà mạng đơn tầng không thể phân loại được. Hình 8.12 minh họa mạng với hai đầu vào, một nút ẩn và một nút đầu ra. Mạng cũng có hai đầu vào thiên lệch (bias), một đi vào nút ẩn và một đi vào nút đầu ra. Một điểm đặc biệt là các đầu vào cũng được nối trực tiếp vào nút đầu ra. Liên kết thêm vào này cho phép nhà thiết kế mạng neuron đạt được một mạng với ít nút hơn trên tầng ẩn và hội tụ nhanh hơn. Giá trị net cho nút ẩn và nút đầu ra cũng được tính như cách thông thường, là tổng của các tích giữa giá trị đầu nhân với trọng số. Các trọng số được điều chỉnh theo giải thuật học lan truyền ngược và sử dụng hàm kích hoạt sigmoidal. Thật ra, mạng neuron trong hình 8.12 không phải là một mạng duy nhất có thể giải quyết bài toán này. 100
Hình 8.12 - Một mạng lan truyền ngược dùng để giải quyết bài toán exclusive-or. Mạng này được rèn luyện với 4 ví dụ: (0,0) → 0; (1,0) → 1; (0,1) → 1; (1,1) → 0 Sau khi được huấn luyện 1400 lượt với 4 dữ liệu trên, các trọng số hội tụ về các giá trị như sau: W = -7.0 W = 2.6 W = -5.0 W = -7.0 H1 HB O1 H2 W = 7.0 W = -4.0 W = -11.0 OB O2 OH Với giá trị đầu vào là (0,0), giá trị đầu ra của nút ẩn sẽ là: f(0 * (-7.0) + 0 * (-7.0) + 1* 2.6 ) = f(2.6) → 1 Kết quả trả về của nút đầu ra cho (0,0) sẽ là: f(0 * (-5.0) + 0 * (-4.0) + 1 * (-11.0) + 1 * (7.0)) = f(-4.0) → 0 Như vậy, ta thấy rằng mạng lan truyền ngược đã phân loại được các điểm dữ liệu không tuyến tính. V. Nhận xét chung về mạng neuron Nói chung các mạng đa tầng là đầy đủ về mặt tính toán (computationally complete), có nghĩa là có thể giải quyết được mọi bài toán. Tuy nhiên, để thiết kế một mạng neuron đa tầng thì nhà thiết kế phải giải quyết được những vấn đề sau: - Làm sao để chọn số nút ẩn và số tầng ẩn thích hợp? - Khi nào sử dụng các nút thiên lệch? - Cách chọn một tập rèn luyện? - Điều chỉnh các trọng số như thế nào? - Nên chọn tốc độ học như thế nào? Nói chung, không có một quy luật nào về tất cả những điều này, nó phụ thuộc vào kinh nghiệm của nhà thiết kế, cũng như là kết quả của quá trình thử-sai lặp đi lặp lại. 101
Chương IX TIẾP CẬN XÃ HỘI VÀ NỔI TRỘI: GIẢI THUẬT DI TRUYỀN (GENETIC ALGORITHM - GA) Cũng như các mạng neuron, các thuật toán di truyền cũng dựa trên một ẩn dụ sinh học: Các thuật toán này xem việc học như là sự cạnh tranh trong một quần thể gồm các lời giải ứng viên đang tiến hóa của bài toán. Một hàm ‘thích nghi’ (fitness function) sẽ đánh giá mỗi lời giải để quyết định liệu nó có đóng góp cho thế hệ các lời giải kế tiếp hay không. Sau đó, thông qua các phép toán tương tự với biến đổi gene trong sinh sản hữu tính, giải thuật sẽ tạo ra một quần thể các lời giải ứng viên mới. I. Giải thuật Hình 9.1- Giải thuật di truyền. Hình 9.1 mô tả giải thuật di truyền tổng quát. Tùy theo từng bài toán mà nhà thiết kế giải thuật sẽ phải mô tả chi tiết hơn về: Phương pháp biểu diễn một cá thể trong quần thể các lời giải ứng viên của bài toán, hay nói khác hơn là hình thức biểu diễn một lời giải tiềm năng của bài toán. Không phải lời giải của mọi bài toán đều có thể được mã hóa một cách dễ dàng và tự nhiên dưới dạng biểu diễn mức bit như trong bài toán thỏa mãn CNF dưới đây. Độ lớn của quần thể là số lượng ứng viên có trong quần thể. Thông thường các ứng viên của quần thể ban đầu được chọn một cách ngẫu nhiên. Độ lớn của quần 102
thể là không đổi qua các thế hệ, vì vậy, sẽ có một quá trình chọn lọc và loại bỏ một số lời giải ứng viên có độ thích nghi thấp. Điều kiện dừng của vòng lặp: có thể là chương trình đạt tới một số lần lặp nhất định nào đó, hay đạt tới trung bình độ tốt nào đó của quần thể, Hàm đánh giá (fitness function): Dùng để đánh giá một ứng viên có tốt hay không. Một ứng viên càng tốt nghĩa là độ thích nghi của nó càng cao và tiến đến trở thành lời giải đúng của bài toán. Việc thiết kế một hàm đánh giá tốt là rất quan trọng trong thuật toán di truyền. Một hàm đánh giá không chính xác có thể làm mất đi các ứng viên tốt trong quần thể. Chọn lựa bao nhiêu phần trăm lời giải tốt để giữ lại? Hay chọn bao nhiêu lời giải ứng viên để kết hợp với nhau và sinh ra lời giải con? Phương pháp tạo thành viên mới từ thành viên hiện có, còn gọi là toán tử di truyền (genetic operators): Các toán tử di truyền phổ biến là o Lai ghép (cross-over): Toán tử lai ghép lấy hai lời giải ứng viên và chia từng lời giải ra thành hai phần, sau đó trao đổi các phần với nhau để tạo ra ứng viên mới. Ví dụ xem hình 9.18. o Đột biến (mutation): Đột biến lấy một ứng viên đơn lẻ và thay đổi một cách ngẫu nhiên một khía cạnh nào đó của nó. Ví dụ xem hình 9.2. Hình 9.2 - Ví dụ minh họa giải thuật và toán tử di truyền. Trong ví dụ minh họa bằng hình 9.2, ta thấy tại thế hệ thứ n ta có một lời giải có độ thích nghi rất thấp (2), và vì vậy, nó không được sử dụng trong quá trình tái sản xuất. Thay vào đó, lời giải có độ thích nghi cao nhất (13) sẽ được nhân đôi và đưa vào quá trình tái sản xuất. Hoặc ít phổ biến hơn là các toán tử di truyền: o Đảo ngược (inversion): Đảo ngược thứ tự các bit trong mẫu lời giải. o Trao đổi (Exchange): Trao đổi hai bit bất kỳ trong mẫu lời giải với nhau. 103
Một toán tử di truyền tốt đóng một vai trò quan trọng trong thuật toán di truyền. Toán tử di truyền phải bảo toàn những mối quan hệ cốt yếu trong quần thể; ví dụ, sự có mặt và sự duy nhất của tất cả các thành phố trong hành trình của người bán hàng trong bài toán người đi bán hàng. - Thay thế thành viên mới cho các thành viên hiện có như thế nào? - II Ví dụ 1: Bài toán thỏa CNF Bài toán thỏa mãn dạng chuẩn hội (Conjunctive normal form – CNF) là một bài toán đơn giản: Một biểu thức của các mệnh đề (clause) ở dạng chuẩn hội hay CNF khi nó là một dãy các biến mệnh đề được kết nối với nhau bởi toán tử quan hệ and (∧). Mỗi mệnh đề có dạng là một tuyển (disjunction), gồm các toán tử quan hệ or (∨) trên các biến mệnh đề (literal). Ví dụ : Nếu ta có 6 biến mệnh đề a, b, c, d, e và f, thì biểu thức sau đây là một CNF: (¬a ∨ c) ∧ (¬a ∨ c ∨ ¬e) ∧ (¬b ∨ c d ∨ ¬e) ∧ (a ∨ ¬b ∨ c) ∧ (¬e ∨ f) (1- 3) Thỏa mãn CNF có nghĩa rằng chúng ta phải tìm ra một phép gán true hoặc false (1 hoặc 0) cho mỗi biến mệnh đề a, b, c, d, e, f sao cho biểu thức CNF có giá trị là TRUE. Một cách biểu diễn tự nhiên cho lời giải của bài toán này là một dãy sáu bit, mỗi bit theo thứ tự a, b, c, d, e, f biểu diễn true (1) hoặc false (0) cho mỗi biến mệnh đề. Như vậy mẫu bit: 1 0 1 0 1 0 cho biết a, c, và e là true và b, d, và f là false, và do đó khi thay các giá trị này vào biểu thức (1-3), thì cho giá trị false. Chúng ta muốn rằng các toán tử di truyền sinh ra các thế hệ lời giải sao cho biểu thức CNF mang trị true, vì vậy mỗi toán tử phải sinh ra một mẫu 6-bit của phép gán true cho biểu thức. Cách biểu diễn lời giải dưới dạng một mẫu các bit như trên mang lại cho ta rất một điều rất thuận lợi là bất kỳ toán tử di truyền nào (lai ghép, đột biến, đảo ngược, hay trao đổi) đều tạo ra một mẫu bit mới là một lời giải khả dĩ hợp lệ. Việc chọn lựa một hàm thích nghi cho quần thể các chuỗi bit này không phải hoàn toàn dễ dàng. Thoạt nhìn chuỗi bit, ta khó có thể xác định một hàm thích nghi để đánh giá được chất lượng của nó như thế nào, nghĩa là khó đoán được độ tốt của nó so với 104
đáp án đúng. Đáp án đúng ở đây chính là chuỗi bit sao cho biểu thức CNF có giá trị true. Tuy nhiên có một số cách khác. Nếu ta chú ý đến biểu thức CNF (1-3), thì ta thấy rằng nó được tạo thành từ hội của 5 mệnh đề. Do đó chúng ta có thể thiết lập một hệ phân hạng cho phép chúng ta sắp hạng các lời giải (mẫu bit) tiềm năng trong khoảng giá trị từ 0 đến 5, tùy thuộc vào số mệnh đề mà mẫu đó thỏa mãn. Do đó mẫu: 1 1 0 0 1 0 có độ thích nghi là 1 0 1 0 0 1 0 có độ thích nghi là 2 0 1 0 0 1 1 có độ thích nghi là 3 1 0 1 0 1 1 có độ thích nghi là 5, và nó chính là một lời giải. III. Ví dụ 2: Bài toán người đi bán hàng TSP Bài toán người bán hàng (traveling salesperson problem – TSP) là một bài toán cổ điển đối với AI và khoa học máy tính1. Như chúng đã giới thiệu ở chương III, toàn bộ không gian trạng thái của nó đòi hỏi phải xem xét N! trạng thái để có thể tìm ra lời giải tối ưu, trong đó N là số thành phố cần đi qua. Khi N khá lớn thì bài toán sẽ bị bùng nổ tổ hợp, vì vậy người ta đặt vấn đề là có cần thiết hay không cho việc chạy một máy trạm làm việc đắt tiền trong nhiều giờ để cho một lời giải tối ưu hay chỉ nên chạy một PC rẻ tiền trong vài phút để có được những kết quả “đủ tốt”. Giải thuật di truyền chính là một giải pháp cho lựa chọn thứ hai. Ở bài toán này, dùng mẫu bit để biểu diễn cho lời giải của bài toán không phải là một cách hay. Chẳng hạn, ta có chín thành phố cần ghé thăm 1, 2, 9, ta xem mỗi thành phố như một mẫu 4 bit 0001, 0010, 1001. Khi đó một lời giải khả dĩ sẽ có hình thức như sau: 0001 0010 0011 0100 0101 0110 0111 1000 1001 Với cách biểu diễn như vậy, việc thiết kế các toán tử di truyền sẽ trở nên rất khó khăn. Toán tử lai ghép nhất định là không được, vì chuỗi mới được tạo từ hai cha mẹ khác nhau hầu như sẽ không biểu diễn một đường đi trong đó ghé thăm mỗi thành phố đúng một lần. Trong thực tế, với lai ghép, một số thành phố có thể bị xóa bỏ trong khi các thành phố khác được ghé thăm nhiều hơn một lần, và vì vậy đó không phải là một lời giải hợp lệ. Còn toán tử đột biến thì thế nào? Giả sử bit trái nhất của thành phố thứ sáu, 0110, được đột biến thành 1? 1110, hay là 14, thì nó không còn là một thành phố hợp lệ. Một cách tiếp cận khác là sẽ bỏ qua biểu diễn dạng mẫu bit và đặt cho mỗi thành phố một tên theo bảng chữ cái hoặc số, ví dụ 1, 2, 9; xem đường đi qua các thành phố là một sự sắp thứ tự của chín ký số này, và sau đó chọn toán tử di truyền thích hợp để tạo ra các đường đi mới. Ở đây ta thấy phép trao đổi (exchange) ngẫu nhiên hai thành phố trong đường đi có thể sử dụng được, còn phép toán lai ghép (crossover) thì không. Việc trao đổi các đoạn của một đường đi với những đoạn khác của cùng đường đi đó, hoặc bất cứ toán tử nào sắp xếp lại các chữ cái của đường đi ấy (mà không xóa bỏ, thêm, hay nhân đôi bất cứ thành phố nào) đều có thể sử dụng được. Tuy nhiên, những phương pháp này gây khó khăn cho việc đưa vào thế hệ con cháu những thành phần 105
“tốt hơn” của các mẫu trong các đường đi qua của các thành phố của hai cha mẹ khác nhau. Nhiều nhà nghiên cứu đã đưa ra các toán tử lai ghép có khả năng khắc phục những vấn đề này, trong đó có toán tử lai ghép có thứ tự (order crossover) do Davis đưa ra vào năm 1985. Lai ghép có thứ tự xây dựng con cháu bằng cách chọn một dãy con các thành phố trong đường đi của một mẫu cha mẹ. Nó cũng bảo toàn thứ tự tương đối các thành phố từ cha mẹ kia. Đầu tiên, chọn hai điểm cắt, biểu thị bởi dấu “|”, điểm cắt này được chen vào một cách ngẫu nhiên vào cùng một vị trí của mỗi mẫu cha mẹ. Những điểm cắt này là ngẫu nhiên, nhưng một khi được chọn, thì những vị trí như nhau sẽ được sử dụng cho cả hai cha mẹ. Ví dụ, có hai mẫu cho mẹ p1 và p2, với các điểm cắt sau thành phố thứ ba và thứ bảy: p1 = (1 9 2 | 4 6 5 7 | 8 3) p2 = (4 5 9 | 1 8 7 6 | 2 3) 1 Phát biểu của bài toán TSP: Một người bán hàng có nhiệm vụ ghé thăm N thành phố như là một phần của lộ trình bán hàng. Đường đi giữa mỗi cặp thành phố có một chi phí (ví dụ như độ dài đoạn đường, giá vé máy bay). Hãy tìm ra đường đi có chi phí thấp nhất cho người bán hàng để bắt đầu lên đường tại một thành phố, thăm tất cả các thành phố khác chỉ đúng một lần rồi quay lại thành phố xuất phát. Hai mẫu con c1 và c2 sẽ được sinh ra theo cách sau. Đầu tiên, các đoạn giữa hai điểm cắt sẽ được chép vào các mẫu con: c1 = (x x x | 4 6 5 7 | x x) c2 = (x x x | 1 8 7 6 | x x) Bước kế tiếp là bắt đầu từ điểm cắt thứ hai của một trong hai mẫu cha mẹ, nếu ta đang muốn hoàn tất mẫu c1, thì ta sẽ bắt đầu từ điểm cắt thứ hai của mẫu p2, ta chép các thành phố từ điểm cắt này theo thứ tự vào các chỗ còn trống của c1, bỏ qua những thành phố mà c1 đã có (các ký số được in đậm và nghiêng trong sơ đồ bên dưới). Khi đến cuối mẫu p2, thì quay lại đầu mẫu p2 tiếp tục chép sang c1 cho đến khi c1 đủ. p2 = (4 5 9 | 1 8 7 6 | 2 3) p1 = (1 9 2 | 4 6 5 7 | 8 3) c1 = (2 3 9 | 4 6 5 7 | 1 8) c2 = (3 9 2 | 1 8 7 6 | 4 5) Với giải thuật lai ghép này, các đường đi của thế hệ con sẽ được đảm bảo là các đường đi hợp lệ, đi qua mỗi thành phố một lần duy nhất. Tóm lại, trong lai ghép thứ tự, các mảnh của một đường đi được truyền từ một cha mẹ, p1, sang một con, c1, trong khi sắp xếp của các thành phố còn lại của con c1 được thừa kế từ cha mẹ kia, p2. Điều này ủng hộ cho trực giác hiển nhiên là thứ tự của các thành phố đóng vai trò quan trọng trong việc tạo ra đường đi với chi phí thấp nhất, và vì vậy việc truyền lại các đoạn thông tin có thứ tự này từ các cha mẹ có độ thích nghi cao sang con cái là một điều rất quan trọng. 106
Ngoài toán tử lai ghép thứ tự trên, còn có rất nhiều toán tử lai ghép và đột biến khác được đưa ra để giải quyết bài toán này. Bảng 9.1 liệt kê các toán tử lai ghép, bảng 9.2 liệt kê các toán tử đột biến. Bảng 9.1 - Danh sách các toán tử lai ghép cho bài toán TSP. Bảng 9.2 - Danh sách các toán tử đột biến cho bài toán TSP. IV. Đánh giá giải thuật Các ví dụ vừa nêu trên làm nổi bật những vấn đề mang tính duy nhất của thuật toán di truyền về biểu diễn tri thức, chọn toán tử di truyền, và thiết kế hàm thích nghi. Biểu diễn được chọn phải hỗ trợ cho các toán tử di truyền. Một điểm dáng lưu ý nữa là các toán tử di truyền phải được thiết kế sao cho bảo lưu được những mảnh thông tin có ý nghĩa trong lời giải tiềm năng từ thế hệ này sang các thế hệ tiếp theo. Một sức mạnh quan trọng của thuật toán di truyền là bản chất song song trong tìm kiếm của nó. Các thuật toán này thực hiện một dạng mạnh của leo núi (hill climbing) 107
trong đó duy trì nhiều lời giải (trong quần thể các lời giải), loại bỏ những lời giải không có triển vọng, và nâng cao chất lượng của những lời giải tốt. Hình 9.3 phỏng theo Holland (1986), cho thấy nhiều lời giải hội tụ về các điểm tối ưu trong không gian tìm kiếm. Trong hình này, trục hoành biểu diễn các điểm có thể có trong không gian lời giải, trong khi trục tung phản ánh chất lượng của những lời giải đó. Các điểm chấm nằm trên cung là các thành viên của quần thể hiện tại. Khởi đầu, những lời giải được rải trong không gian những lời giải có thể có. Sau một vài thế hệ, chúng có khuynh hướng cụm lại xung quanh những vùng có chất lượng lời giải cao hơn. Hình 9.3- Các thuật toán di truyền được xem là leo núi song song (theo Holland 1986) Tuy nhiên, với sức mạnh như vậy, giải thuật genetic cũng không thể áp dụng cho tất cả các bài toán có thể có. Vì như ta thấy qua hai ví dụ trên, lời giải của bài toán phải được biểu diễn dưới một dạng mẫu thích hợp cho các toán tử di truyền hoạt động. Trong thực tế có nhiều bài toán không thể làm được điều này. Vì vậy, khi nghiên cứu về giải thuật này, có rất nhiều câu hỏi đã được đưa ra nhằm hiểu rõ hơn nữa về bản chất hoạt động của nó: 1. Liệu chúng ta có thể đưa ra những đặc điểm về các loại bài toán mà giải thuật di truyền (GA) có thể thực hiện tốt 2. Các loại bài toán nào thì không thích hợp với GA. 3. Dựa vào đâu để ta có thể nói là GA thực hiện tốt hay không tốt đối với một loại bài toán nào đó? 4. Liệu có những qui luật nào mô tả hành vi của GA ở mức vĩ mô? Hay cụ thể hơn, là liệu có bất kỳ sự phán đoán nào về sự thay đổi của độ thích nghi của các nhóm con trong quần thể theo thời gian? 5. Có cách nào để mô tả các hiệu ứng khác nhau của các toán tử di truyền như lai ghép, đột biến, đảo ngược, v.v 6. Trong những trường hợp nào (bài toán nào, toán tử di truyền nào) thì GA sẽ thực hiện tốt hơn các phương pháp nghiên cứu của TTNT truyền thống. Những câu hỏi này (và còn nhiều hơn nữa) vẫn đã và đang được các nhà khoa học như Holland, Mitchell, Golderg, nghiên cứu. 108