Tài liệu Toán tử owa trong một số bài toán tối ưu

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------------- ĐỖ THÙY NINH TOÁN TỬ OWA TRONG MỘT SỐ BÀI TOÁN TỐI ƯU Chuyên ngành : Toán Ứng Dụng Mã số : 60.46.36 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS VŨ MẠNH XUÂN Thái Nguyên – Năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Môc lôc Më ®Çu 2 Ch­¬ng 1. To¸n tö OWA 4 1.1. To¸n tö OWA . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. C¸ch x¸c ®Þnh vect¬ träng sè w . . . . . . . . . . . . . . . 9 1.3. Mét sè biÕn thÓ cña OWA . . . . . . . . . . . . . . . . . . 14 Ch­¬ng 2. Tèi ­u c¸c träng sè 20 2.1. §é ph©n t¸n cùc ®¹i . . . . . . . . . . . . . . . . . . . . . . 20 2.2. §é ph©n t¸n cùc tiÓu . . . . . . . . . . . . . . . . . . . . . 24 Ch­¬ng 3. Mét sè øng dông cña to¸n tö OWA 36 3.1. Ra quyÕt ®Þnh dùa trªn ®é quan träng . . . . . . . . . . . . 36 3.2. ThuËt to¸n ph©n côm . . . . . . . . . . . . . . . . . . . . . 40 3.3. Bµi to¸n ¸p dông 43 . . . . . . . . . . . . . . . . . . . . . . . 1 Më ®Çu To¸n tö trung b×nh träng sè cã s¾p xÕp (Ordered Weighted Averaging operater- OWA) ®­îc Yager giíi thiÖu n¨m 1988 lµ mét c«ng cô h÷u Ých nh»m tÝch hîp c¸c thuéc tÝnh cña ®èi t­îng theo c¸c tiªu chÝ kh¸c nhau. To¸n tö nµy ®· ®­îc sö dông trong nhiÒu d¹ng bµi to¸n vµ ®· thu ®­îc nh÷ng kÕt qu¶ tèt [7] [8]. TiÕp sau Yager, nhiÒu nhµ to¸n häc kh¸c còng ®· nghiªn cøu, ph¸t triÓn to¸n tö OWA vµ ®¹t ®­îc nhiÒu thµnh c«ng nh­: O'Hagan [6], Perter Majlender [3], Robert Fuller [4], .... Môc ®Ých cña ®Ò tµi nµy lµ nghiªn cøu vÒ to¸n tö OWA, c¸c tÝnh chÊt quan träng cña nã vµ b­íc ®Çu øng dông trong mét sè bµi to¸n cô thÓ. Néi dung b¶n luËn v¨n gåm cã phÇn më ®Çu, ba ch­¬ng, phÇn kÕt luËn vµ tµi liÖu tham kh¶o. Ch­¬ng 1 tr×nh bµy vÒ to¸n tö OWA cïng mét sè tÝnh chÊt ®Æc tr­ng cña nã vµ ®­îc dÉn gi¶i bëi c¸c vÝ dô cô thÓ. Ch­¬ng nµy còng nªu mét sè d¹ng kh¸c cña to¸n tö OWA. Ch­¬ng 2 tr×nh bµy c¸c thuËt to¸n nh»m tèi ­u ®é ph©n t¸n cña c¸c träng sè khi x©y dùng vÐc t¬ träng sè. . . . Ch­¬ng 3 tr×nh bµy mét vµi øng dông to¸n tö OWA trong nh÷ng bµi to¸n cô thÓ. Em mong muèn bµy tá lßng biÕt ¬n s©u s¾c tíi ThÇy gi¸o TiÕn sÜ Vò M¹nh Xu©n, thÇy ®· rÊt tËn t×nh h­íng dÉn, chØ b¶o em rÊt nhiÒu trong suèt thêi gian em thùc hiÖn khãa luËn vµ trùc tiÕp h­íng dÉn em hoµn thµnh khãa luËn nµy. Em xin göi lêi c¶m ¬n ch©n thµnh tíi c¸c thÇy gi¸o, c« gi¸o tr­êng §¹i häc Khoa häc, khoa To¸n - Tin vµ c¸c gi¸o s­ ®· hÕt lßng gi¶ng d¹y, truyÒn ®¹t cho em nhiÒu kiÕn thøc khoa häc trong suèt thêi gian em häc tËp t¹i ®©y. 2 Cuèi cïng, t«i xin göi lêi c¶m ¬n tíi nh÷ng ng­êi th©n, nh÷ng ng­êi b¹n cña t«i ®· ®éng viªn vµ cæ vò t«i rÊt nhiÒu trong suèt thêi gian võa qua. Do ®iÒu kiÖn vÒ thêi gian vµ tr×nh ®é cã h¹n nªn b¶n luËn v¨n kh«ng tr¸nh khái nh÷ng thiÕu sãt. Em rÊt mong nhËn ®­îc nh÷ng ý kiÕn ®ãng gãp quý b¸u cña c¸c quý thÇy c« vµ toµn thÓ c¸c b¹n. Th¸i Nguyªn, th¸ng 09 n¨m 2009 §ç Thuú Ninh 3 Ch­¬ng 1 To¸n tö OWA Qu¸ tr×nh tÝch hîp th«ng tin xuÊt hiÖn trong rÊt nhiÒu øng dông cña c¸c hÖ tri thøc ch¼ng h¹n nh­ trong m¹ng n¬ron, ®iÒu khiÓn mê, hÖ chuyªn gia vµ hÖ trî gióp quyÕt ®Þnh, ®Æc biÖt trong c¸c bµi to¸n ph¶i xö lý nh÷ng th«ng tin bÊt ®Þnh. N¨m 1988, R.Yager [8] [9] ®· ®Þnh nghÜa to¸n tö trung b×nh träng sè cã s¾p xÕp (Ordered Weighted Averaging operator) viÕt t¾t lµ OWA nh»m cung cÊp mét ph­¬ng ph¸p kÕt hîp c¸c thuéc tÝnh g¾n víi sù tho¶ m·n nh÷ng tiªu chÝ nµo ®ã. Ch­¬ng nµy tr×nh bµy vÒ to¸n tö OWA, c¸c tÝnh chÊt c¬ b¶n vµ mét sè d¹ng kh¸c cña to¸n tö nµy. 1.1. To¸n tö OWA 1.1.1. Kh¸i niÖm W = (w1 , w2 , . . . , wn )T lµ mét vect¬ träng sè n P cña kh«ng gian n chiÒu nÕu 0 ≤ wi ≤ 1 víi mçi i = 1, ..., n vµ wj = 1. §Þnh nghÜa 1.1.1. Mét vect¬ j=1 W lµ mét ¸nh x¹ F : Rn −→ R ®­îc x¸c ®Þnh nh­ sau: Víi mçi vect¬ a = (a1 , a2 , . . . , an ) ∈ Rn §Þnh nghÜa 1.1.2. To¸n tö OWA víi vect¬ träng sè F (a) = n X wj bj , j=1 trong ®ã bj lµ phÇn tö lín thø VÝ dô 1.1.1. j cña vect¬ a. Gi¶ sö cho vect¬ W = (0, 4; 0, 3; 0, 2; 0, 1)T vµ a = (0, 7; 1; 0, 3; 0, 6). Khi ®ã, ta cã vect¬ b = (1; 0, 7; 0, 6; 0, 3), 4 vµ to¸n tö OWA: F (a) = 4 X wj bj = 0, 4.1 + 0, 3.0, 7 + 0, 2.0, 6 + 0, 1.0, 3 = 0, 76. j=1 ý nghÜa c¬ b¶n cña to¸n tö nµy lµ s¾p xÕp l¹i vect¬ cÇn tÝch hîp, nghÜa lµ phÇn tö cÇn tÝch hîp ai kh«ng liªn kÕt víi träng sè wi mµ träng sè wi sÏ kÕt hîp víi mét phÇn tö ë vÞ trÝ t­¬ng øng cña tËp c¸c phÇn tö tÝch hîp sau khi ®· ®­îc s¾p xÕp. Sù kh¸c nhau gi÷a c¸c to¸n tö OWA ®­îc ph©n biÖt bëi c¸c träng sè nµy. TÝnh tæng qu¸t cña to¸n tö OWA lµ ë chç b»ng viÖc lùa chän nh÷ng träng sè, ta cã thÓ thùc hiÖn c¸c d¹ng to¸n tö kÕt hîp kh¸c nhau. B»ng c¸ch lùa chän thÝch hîp c¸c träng sè trong vect¬ W , ta cã thÓ nhÊn m¹nh c¸c tham sè kh¸c nhau trªn c¬ së vÞ trÝ cña chóng trong thø tù sau khi xÕp. NÕu ta ®Æt hÇu hÕt c¸c träng sè gÇn ®Çu cña W , ta cã thÓ nhÊn m¹nh c¸c ®iÓm cao h¬n, trong khi ®ã, nÕu ®Æt c¸c träng sè gÇn cuèi cña W sÏ nhÊn m¹nh c¸c ®iÓm thÊp h¬n. 1.1.2. Mét sè tr­êng hîp ®Æc biÖt • NÕu träng sè w1 = 1 vµ wj = 0 víi mäi j 6= 1, vect¬ träng sè ký hiÖu W ∗ = (1, 0, . . . , 0)T , ký hiÖu to¸n tö OWA øng víi träng sè W ∗ lµ F ∗ . Ta cã F ∗ (a) = F ∗ (a1 , ..., an ) = maxj (aj ). Nh­ vËy to¸n tö chän sè lín nhÊt (max) lµ mét d¹ng cña to¸n tö OWA. lµ • NÕu träng sè wn = 1 vµ wj = 0 víi mäi j 6= n, vect¬ träng sè ký hiÖu lµ W∗ = (0, 0, . . . , 1)T , ký hiÖu to¸n tö OWA øng víi träng sè W∗ lµ F∗ . Ta cã F∗ (a) = F∗ (a1 , ..., an ) = minj (aj ). Nh­ vËy to¸n tö chän sè bÐ nhÊt (min) lµ mét d¹ng cña to¸n tö OWA. 1 • NÕu c¸c träng sè wj = víi mäi j , vect¬ träng sè kÝ hiÖu lµ Wave , ký n n 1X aj . hiÖu to¸n tö OWA øng víi träng sè Wave lµ Fave . Ta cã Fave (a) = n j=1 Tõ ®ã to¸n tö trung b×nh ®¬n gi¶n còng lµ mét d¹ng cña to¸n tö OWA. 5 • NÕu wk = 1 vµ wj = 0 víi mäi j 6= k , to¸n tö OWA F (a1 , ..., an ) = bk ( gi¸ trÞ lín thø k cña vect¬ a). Nh­ vËy viÖc chän mét thµnh phÇn cña vect¬ còng lµ tr­êng hîp ®Æc biÖt cña hä to¸n tö OWA. Tr­êng hîp riªng ta thu ®­îc phÇn tö ë gi÷a vect¬ a b»ng c¸ch: n lµ lÎ lÊy w n+1 = 1 vµ ®Æt wj = 0, j 6= n+1 2 . 2 1 NÕu n lµ ch½n lÊy w n2 = w n2 +1 = vµ ®Æt wj = 0 cho tÊt c¶ c¸c sè h¹ng 2 NÕu kh¸c. 1.1.3. Mét sè tÝnh chÊt Sau ®©y ta ®Òu gi¶ thiÕt TÝnh chÊt 1.1.1. W = (w1 , ..., wn )T lµ vect¬ träng sè. §èi víi mçi to¸n tö OWA, ta cã: F∗ (a1 , ..., an ) 6 F (a1 , ..., an ) 6 F ∗ (a1 , ..., an ), ⇔ min(ai ) 6 F (a1 , ..., an ) 6 max(ai ). (Hay gi¸ trÞ cña to¸n tö OWA bÞ chÆn bëi gi¸ trÞ lín nhÊt vµ nhá nhÊt cña vect¬ a). W = (w1 , ..., wn )T ®· cho nh­ trªn vµ b = (b1 , ..., bn ) lµ vect¬ s¾p xÕp l¹i cña vect¬ a. (NghÜa lµ b1 ≥ b2 ≥ . . . ≥ bn .) Ta cã Chøng minh. Gi¶ sö to¸n tö OWA víi vect¬ träng sè F∗ (a1 , ..., an ) = b1 0 + b2 0 + ... + bn 1 = bn = min(ai ), n X F (a1 , ..., an ) = b1 w1 + b2 w2 + ... + bn wn = wi bi , i=1 ∗ F (a1 , ..., an ) = b1 1 + b2 0 + ... + bn 0 = b1 = max(ai ). Râ rµng n X i=1 n X i=1 wi bi ≥ wi bi ≤ n X i=1 n X wi bn = bn wi b1 = b1 i=1 n X i=1 n X i=1 6 wi = bn = min(ai ), wi = b1 = max(ai ). Tõ ®ã min(ai ) 6 n X wi bi 6 max(ai ) hay F∗ 6 F 6 F ∗ . i=1 2 TÝnh chÊt 1.1.2. (TÝnh ho¸n vÞ) Ta cã F (a1 , ..., an ) = F (d1 , ..., dn ), víi mäi ho¸n vÞ Chøng minh. vÞ d = (d1 , ..., dn ) cña a = (a1 , ..., an ). V× sù s¾p xÕp lµ duy nhÊt nªn vect¬ cÇn tÝch hîp a vµ ho¸n d ®Òu cã chung vect¬ sau khi s¾p xÕp lµ b = (b1 , ..., bn ). VËy F (a1 , ..., an ) = F (d1 , ..., dn ). 2 TÝnh chÊt 1.1.3. (TÝnh ®¬n ®iÖu) Gi¶ sö a = (a1 , a2 , . . . , an ) vµ c = (c1 , c2 , . . . , cn ) lµ hai vect¬ cña to¸n tö OWA tho¶ m·n ai ≥ ci (i = 1, ..., n). ThÕ th× F (a1 , ..., an ) ≥ F (c1 , ..., cn ) a lµ b = (b1 , ..., bn ), vect¬ sau khi s¾p xÕp cña vect¬ c lµ d = (d1 , ..., dn ). V× hai vect¬ a, c tho¶ Chøng minh. m·n ai Gi¶ sö vect¬ sau khi s¾p xÕp cña vect¬ ≥ ci , nªn bi ≥ di víi mäi i. Ta cã F (a1 , a2 , . . . , an ) = b1 w1 + b2 w2 + . . . + bn wn , F (c1 , c2 , . . . , cn ) = d1 w1 + d2 w2 + . . . + dn wn . Râ rµng F (a1 , ..., an ) ≥ F (c1 , ..., cn ). 2 TÝnh chÊt 1.1.4. (TÝnh luü ®¼ng) NÕu vect¬ c = (c1 , . . . , cn ) víi c1 = c2 = . . . = cn = a th× ta cã F (c1 , . . . , cn ) = a. 7 Chøng minh. Ta cã F (c1 , . . . , cn ) = a.w1 + ... + a.wn = a.(w1 + ... + wn ) = a.1 = a 2 1.1.4. §Æc tr­ng cña to¸n tö OWA Trong phÇn nµy ta nghiªn cøu hai phÐp ®o quan träng, phô thuéc vµo vect¬ träng sè, h÷u Ých cho viÖc ®Æc tr­ng ho¸ c¸c to¸n tö OWA [1]. §Þnh nghÜa 1.1.3. §é ®o thø nhÊt lµ ®Þnh bëi c«ng thøc: Disp(W ) = − ®é ®o ph©n t¸n n P cña vect¬ W ®­îc x¸c cña vect¬ W ®­îc cho wi ln wi i=1 §Þnh nghÜa 1.1.4. bëi c«ng thøc: VÝ dô 1.1.2. §é ®o thø hai lµ Orness(W ) = ®é ®o tÝnh tuyÓn 1 n−1 n X (n − i)wi . i=1 Ta xÐt mét vÝ dô sau Vect¬ träng sè W Disp(W) Orness(W) W=(0.4,0.3,0.2,0.1) 1.2798 0.6666 W=(0.1,0.2,0.3,0.4) 1.2798 0.3333 W=(0.9,0.07,0.02,0.01) 0.4053 0.9533 W=(0.04,0.06,0.1,0.8) 0.7063 0.1133 W=(0.24,0.25,0.25,0.26) 1.3859 0.49 B¶ng 1.1 NhËn xÐt: Ta thÊy c¸c träng sè nµy cµng gÇn nhau th× Disp cµng lín, cµng xa nhau th× Disp cµng nhá. §iÒu ®ã chøng tá nÕu ta xÐt c¸c thuéc tÝnh mét c¸ch ®ång ®Òu nhau th× Disp lín vµ ng­îc l¹i. Nãi c¸ch kh¸c, ®é ®o Disp chØ møc ®é sö dông c¸c thuéc tÝnh. Víi ®é ®o Orness, nÕu träng sè cao ë ®Çu th× Orness lín, träng sè cao ë cuèi th× Orness nhá. NÕu c¸c träng sè ®Òu b»ng nhau th× Orness tiÕn tíi 0.5. NghÜa lµ ®é ®o Orness x¸c ®Þnh ®iÓm nhÊn m¹nh. 8 Ngoµi hai ®é ®o c¬ b¶n trªn, ng­êi ta cßn ph¸t triÓn thªm mét sè ®é ®o kh¸c [3], ch¼ng h¹n a, §Þnh nghÜa 1.1.5. §é ph©n t¸n Shannon Hs (W ) = − n X cho bëi c«ng thøc: wi log2 wi . i=1 b, §é ph©n t¸n RÐnyi's Víi mäi sè thùc Hα (còng ®­îc gäi lµ ®é ph©n t¸n cña α.) α 6= 1 th×: n X 1 Hα (W ) = log2 wiα . 1−α i=1 c, β ®­îc s¾p kÝ hiÖu lµ Hβ ®­îc giíi thiÖu bëi Daroczy. §é ph©n t¸n cña Víi mäi β 6= 1 th×: Hβ (W ) = d, §é ph©n t¸n R- chuÈn Víi mäi n X 1 21−β − 1
wiβ − 1 . i=1 HR (W ) R 6= 1 vµ x¸c ®Þnh theo c«ng thøc: n X
1 R  R R HR (W ) = 1− wi . R−1 i=1 NhËn xÐt: Sö dông c«ng thøc tÝnh giíi h¹n ta cã: Hs (W ) = lim Hα (W ) = lim Hβ (W ) = lim HR (W ). α→1 1.2. β→1 R→1 C¸ch x¸c ®Þnh vect¬ träng sè w Ta ®· thÊy ý nghÜa vµ hiÖu qu¶ cña to¸n tö OWA phô thuéc vµo c¸ch chän vect¬ träng sè W. Tuú theo bµi to¸n cô thÓ mµ cã nh÷ng c¸ch chän lùa kh¸c nhau. Trong phÇn nµy ta sÏ xÐt mét vµi c¸ch x¸c ®Þnh vect¬ 9 W. 1.2.1. X¸c ®Þnh vect¬ träng sè qua c¸c l­îng tö mê XÐt mét hµm ®Þnh l­îng Q nh­ mét l­îng tö mê (ch¼ng h¹n nh­ "®a sè") lµ mét hµm ®¬n ®iÖu, kh«ng gi¶m trªn [0,1] tho¶ m·n Q(0) = 0, Q(1) = 1. Khi ®ã víi mçi i = 1, 2, . . . , n tÝnh wi = Q(i/n) − Q((i − 1)/n). Tõ ®ã ta cã vect¬ W. C¸ch x¸c ®Þnh nµy dïng cho líp bµi to¸n ®¸nh gi¸ ph­¬ng ¸n sù tho¶ m·n mét sè c¸c tiªu chuÈn nµo ®ã. Ch¼ng h¹n, xÐt tËp h÷u h¹n c¸c tiªu chuÈn T (ch¼ng h¹n: gi¸ c¶, mÉu m·, ®é bÒn,... cña s¶n phÈm) vµ tËp X c¸c ph­¬ng ¸n lùa chän. Víi mçi ph­¬ng ¸n x, ®é thuéc cña nã vµo tiªu chuÈn thø i x¸c ®Þnh bëi Ai (x). §Ó ®¸nh gi¸ mÖnh ®Ò P: "x tho¶ m·n c¸c tiªu chuÈn" ta lµm nh­ sau: 1. X¸c ®Þnh hµm ®Þnh l­îng tõ mê Q (ch¼ng h¹n "tho¶ m·n ®a sè c¸c tiªu chuÈn"). 2. TÝnh wi theo c«ng thøc wi = Q(i/n) − Q((i − 1)/n). 3. TÝnh vect¬ a, trong ®ã ai = Ai (x). 4. Sö dông to¸n tö OWA víi vect¬ träng sè VÝ dô 1.2.1. W vµ vect¬ a võa x¸c ®Þnh. Cho l­îng tö mê Q ®­îc x¸c ®Þnh Q(i) = i2 , vµ n = 3. Khi ®ã vect¬ träng sè W x¸c ®Þnh nh­ sau: 0 1 1 1 w1 = Q( ) − Q( ) = ( )2 − 0 = , 3 3 3 9 1 2 2 1 2 4 1 1 2 w2 = Q( ) − Q( ) = ( ) − ( ) = . = , 3 3 3 3 9 9 3 3 2 2 4 5 w3 = Q( ) − Q( ) = (1)2 − ( )2 = 1 − = . 3 3 3 9 9 Ta cã vect¬ träng sè 1 1 5 W = ( , , ). 9 3 9 1.2.2. X¸c ®Þnh vect¬ W g¾n víi ®é quan träng Gi¶ sö ta cã n cÆp (uj , aj ) trong ®ã uj ∈ [0, 1] lµ träng sè quan träng vµ 10 (ai ∈ [0, 1]) lµ thuéc tÝnh t­¬ng øng. Cã thÓ xem uj lµ sù quan träng cña ®iÒu kiÖn thø j vµ aj lµ sù tho¶ m·n cña mét lùa chän ®· cho ®èi víi tiªu chuÈn thø j. Tr­íc hÕt ta s¾p xÕp l¹i c¸c aj , kÝ hiÖu bi lµ gi¸ trÞ lín nhÊt thø i cña c¸c ai . KÝ hiÖu vi lµ sù quan träng g¾n víi ®iÓm cã gi¸ trÞ lín nhÊt thø i. Khi ®ã ta cã thÓ xem xÐt tËp n cÆp (vi , bi ) trong ®ã c¸c bi ®­îc s¾p xÕp theo thø tù gi¶m. B­íc tiÕp theo lµ thu nhËn c¸c träng sè OWA nh­ sau wi = Q(Si /T ) − Q(Si−1 /T ) víi i = 1, . . . , n trong ®ã Q lµ mét l­îng tõ mê nh­ nªu trªn, Si = i X v k , T = Sn = n X vk . k=1 k=1 Do ®ã T lµ tæng tÊt c¶ nh÷ng quan träng vµ tÝnh ®Õn ®iÓm cao thø i. Cuèi cïng ta tÝnh gi¸ trÞ kÕt hîp ∗ a = n P Si lµ tæng c¸c quan träng bi wi . i=1 A1 , A2 , A3 , A4 . C¸c quan träng g¾n víi thuéc tÝnh nµy lµ u = (1; 0.6; 0.5; 0.9). Khi ®ã T=3. VÝ dô 1.2.2. XÐt ®èi t­îng x víi 4 thuéc tÝnh Gi¶ sö gi¸ trÞ cña ®èi t­îng x trªn c¸c thuéc tÝnh nµy ®­îc cho bëi: (0.7; 1; 0.5; 0.6). Gi¶ sö l­îng tõ chØ dÉn cho kÕt hîp nµy lµ "hÇu hÕt"). Sö dông thuËt to¸n trªn ta ®­îc: A1 bj vj 1 0.6 A2 0.7 1 A3 0.6 0.9 A4 0.5 0.5 B¶ng 1.2 TÝnh c¸c träng sè wi g¾n víi x ta cã: 11 Q = r2 (ch¼ng h¹n nh­ lµ w1 (x) = Q(0.6/3) − Q(0/3) = (0.2)2 − 0 = 0.04 w2 (x) = Q(1.6/3) − Q(0.6/3) = 0.28 − 0.04 = 0.24 w3 (x) = Q(2.5/3) − Q(1.6/3) = 0.69 − 0.28 = 0.41 w4 (x) = Q(3/3) − Q(2.5/3) = 1 − 0.69 = 0.31. Tõ ®ã: F (x) = 0.4 ∗ 1 + 0.24 ∗ 0.7 + 0.41 ∗ 0.6 + 0.31 ∗ 0.5 = 0.609. 1.2.3. X¸c ®Þnh vect¬ W tõ d÷ liÖu Gi¶ sö cã mét tËp m quan s¸t, mçi quan s¸t gåm mét bé n gi¸ trÞ (ak1 , ak2 , . . . , akn ) (k=1,2,...,m) gäi lµ tham sè vµ mét gi¸ trÞ kÕt hîp ®¬n ký hiÖu lµ dk . Môc ®Ých cña chóng ta lµ t×m ®­îc mét to¸n tö OWA víi vect¬ träng sè W cã thÓ lµ m« h×nh tèt nhÊt cho qu¸ tr×nh kÕt hîp ®­îc sö dông trong tËp d÷ liÖu nµy. §iÒu nµy cã nghÜa lµ t×m mét vect¬ träng sè W sao cho víi toµn bé tËp d÷ liÖu, ta tho¶ m·n ®iÒu kiÖn mét c¸ch chÝnh x¸c nhÊt cã thÓ víi mäi quan s¸t F (a1 , a2 , . . . , an ) = dk , trong ®ã F chØ ra sù kÕt hîp OWA cña c¸c tham sè sö dông W. Ta ký hiÖu c¸c ®èi t­îng ®· ®­îc s¾p l¹i thø tù cña mÉu thø k lµ (bk1 , bk2 , . . . , bkn ) trong ®ã bkj lµ thµnh phÇn lín nhÊt thø j cña tËp tham sè (ak1 , ak2 , . . . , akn ). Sö dông nh÷ng tham sè cã thø tù nµy, bµi to¸n trë thµnh t×m vect¬ träng sè W = (w1 , w2 , . . . , wn )T tho¶ m·n tèt nhÊt bk1 w1 + bk2 w2 + . . . + bkn wn = dk , víi mäi k ch¹y tõ 1 tíi m. Sö dông kü thuËt gi¶m ®é dèc gradient ta t×m mét vect¬ träng sè W = (w1 , w2 , . . . , wn )T 12 tèi thiÓu ho¸ nh÷ng sai sè ek 1 ek = ((bk1 w1 + bk2 w2 + . . . + bkn wn ) − dk )2 , 2 vµ c¸c wi ph¶i tho¶ m·n c¸c ®iÒu kiÖn: n X wi = 1; wi ∈ [0, 1], i = 1, . . . , n. i=1 §Ó ph¸ vì c¸c rµng buéc cña c¸c träng sè, ta biÓu diÔn wi nh­ sau: eλi wi = P , i = 1, . . . , n. n λ i e i=1 Nh­ vËy ®èi víi bÊt kú gi¸ trÞ nµo cña c¸c tham sè λi th× c¸c träng sè wi sÏ d­¬ng vµ tæng b»ng 1. Bëi vËy bµi to¸n tèi thiÓu ho¸ cã r»ng buéc cã thÓ chuyÓn thµnh bµi to¸n quy ho¹ch phi tuyÕn kh«ng rµng buéc t×m kiÕm λi lµm cùc tiÓu  2 eλ1 eλ2 eλn 1 bk1 P + bk2 P + . . . + bkn P − dk . ek = n n n 2 λ λ λ e 1 e 2 e n i=1 i=1 i=1 Sö dông ph­¬ng ph¸p ®é dèc gradient, ta cã thÓ thu ®­îc luËt sau cho viÖc cËp nhËt c¸c tham sè λi (l + 1) = λi (l) − βwi (l)(bki − dbk )(dbk − dk ), trong ®ã λi (l + 1) lµ ­íc l­îng míi cña chóng ta vÒ λi . KÝ hiÖu β lµ mét eλi (l) h»ng sè chØ tØ lÖ häc (0 ≤ β ≤ 1), víi mçi i, wi (l) = n lµ ­íc l­îng P λ e i (l) cña i=1 wi sau lÇn lÆp thø l vµ dbk = bk1 w1 (l) + bk2 w2 (l) + . . . + bkn wn (l). Qu¸ tr×nh cËp nhËt λi tiÕp tôc cho ®Õn khi thu ®­îc ®¸nh gi¸ tham sè sau ®ñ nhá: δi = lλi (l + 1) − λi (l)l, i = 1, . . . , n. 13 1.3. Mét sè biÕn thÓ cña OWA Ngoµi d¹ng c¬ b¶n trªn cña to¸n tö OWA, ng­êi ta cßn xÐt mét sè d¹ng kh¸c cña nã tuú thuéc vµo c¸c øng dông còng nh­ kh¶ n¨ng tæng qu¸t ho¸. Sau ®©y sÏ tr×nh bµy mét sè d¹ng th­êng gÆp. 1.3.1. To¸n tö WOWA Tr­íc hÕt xÐt mét sè kh¸i niÖm sau: §Þnh nghÜa 1.3.1. Mét hµm Q gi¶m ®¬n ®iÖu chÝnh quy : [0, 1] −→ [0, 1] lµ mét L­îng ho¸ mê kh«ng nÕu tho¶ m·n: (i)Q(0) = 0, (ii)Q(1) = 1, (iii)x > y ⇒ Q(x) ≥ Q(y). Hai l­îng ho¸ ®Æc biÖt lµ: (i)Qx (0) = 0, Qx (x) = 1, x 6= 0, (ii)Qn (1) = 1, Qn (x) = 0, x 6= 1. W M : Rn −→ R P lµ mét Träng sè n chiÒu nÕu W M p (a1 , . . . , an ) = p i ai . §Þnh nghÜa 1.3.2. Cho P lµ mét vect¬ n chiÒu th× ¸nh x¹ i B©y giê ta ®i xÐt ®Þnh nghÜa to¸n tö OWA sö dông l­îng ho¸ mê kh«ng gi¶m. §Þnh nghÜa 1.3.3. Cho Q lµ mét l­îng ho¸ mê kh«ng gi¶m, ¸nh x¹ cho bëi OW AQ : Rn −→ R lµ To¸n tö OWA n chiÒu OW AQ (a1 , . . . , an ) = n X nÕu (Q(i/n) − Q((i − 1)/n))aσ(i) , i=1 14 trong ®ã {σ(1), . . . , σ(n)} lµ mét ho¸n vÞ cña {1, . . . , n}, tøc lµ ta cã aσ(i−1) ≥ aσ(i) víi mäi i = {2, . . . , n}, hay aσ(i) lµ phÇn tö lín thø i cña tËp (a1 , . . . , an ). Rn vµ to¸n tö OWA trong l­îng ho¸ mê kh«ng gi¶m lµ t­¬ng ®­¬ng nhau v× wi cã thÓ ®Þnh nghÜa qua Q: wi = Q(i/n) − Q(i − 1)/n vµ Q cã thÓ ®­îc ®Þnh nghÜa nh­ lµ mét hµm §Þnh nghÜa to¸n tö OWA trong kh«ng gian néi suy c¸c ®iÓm {i/n, Q(i/n)} víi i ∈ {0, 1, . . . , n} §Ó thõa nhËn hai träng sè trong mét bµi to¸n ta xÐt mét d¹ng to¸n tö OWA träng sè (WOWA). To¸n tö nµy tËp hîp mét tËp c¸c gi¸ trÞ sö dông hai vect¬ träng sè: mét t­¬ng øng tíi vect¬ P trong ý nghÜa träng sè, vµ mét t­¬ng øng tíi W trong to¸n tö OWA. §Þnh nghÜa 1.3.4. chiÒu, ¸nh x¹ §Æt P vµ W lµ hai vect¬ träng sè cña kh«ng gian n W OW A : Rn −→ R lµ ( Weighted Or- To¸n tö WOWA dered Weighted Averaging) cña kh«ng gian n chiÒu nÕu: W OW Ap,w (a1 , . . . , an ) = X wi aσ(i), i trong ®ã aσ(i) lµ phÇn tö lín thø i trong tËp (a1 , . . . , an ), vµ vect¬ wi ®­îc ®Þnh nghÜa bëi: X X ∗ wi = W ( pσ(i) ) − W ( pσ(i) ), ∗ j≤i víi j≤i W ∗ lµ hµm ®¬n ®iÖu t¨ng trong kho¶ng (i/n, P wj ) cïng víi ®iÓm cã j≤i to¹ ®é (0, 0). Còng t­¬ng tù nh­ to¸n tö OWA, ta cã thÓ ®Þnh nghÜa WOWA sö dông l­îng ho¸ mê (thay cho vect¬ träng sè w). §Þnh nghÜa 1.3.5. Cho Q lµ mét l­îng ho¸ mê kh«ng gi¶m, P lµ mét vect¬ träng sè n chiÒu, ¸nh x¹ W OW A : Rn −→ R lµ mét chiÒu nÕu: W OW Ap,Q (a1 , . . . , an ) = X i 15 wi aσ(i) , to¸n tö WOWA n trong ®ã wi = Q( P pσ(i) ) − Q( j≤i P pσ(i) ), j≤i Chó ý r»ng to¸n tö WOWA còng lµ mét tæ hîp tuyÕn tÝnh cña c¸c gi¸ trÞ. TÝnh chÊt 1.3.1. Mét ®é ®o mê µ cña tËp X lµ mét hµm µ : ρ(X) −→ [0, 1] tho¶ m·n tiªn ®Ò sau: 1. µ(∅) = 0, µ(X) = 1, ( ®iÒu kiÖn biªn) 2. A ⊆ B kÐo theo µ(A) ≤ µ(B), ( tÝnh ®¬n ®iÖu) §é ®o mê thay thÕ tiªn ®Ò cña tÝnh chÊt céng ®é ®o bëi tÝnh ®¬n ®iÖu. Suy ra nh÷ng tÝnh chÊt ®é ®o còng lµ ®é ®o mê. §Þnh nghÜa 1.3.6. hµm Cho µ lµ mét ®é ®o mê trong X. TÝch ph©n Choquet cña f : X −→ R ®­îc ®Þnh nghÜa: n X (f (xs(i) ) − f (xs(i−1) ))µ(As(i) ), i=1 trong ®ã As(i) f (xs(i) ) chØ ra tÝnh ho¸n vÞ, 0 ≤ f (xs(1) ) ≤ . . . ≤ f (xs(N ) ) ≤ 1, = {xs(i) , . . . , xs(N ) } vµ f (xσ(0) ) = ∅. Mét to¸n tö WOWA trªn l­îng ho¸ mê kh«ng gi¶m Q vµ mét vect¬ träng sè W lµ mét tÝch ph©n Choquet trªn ®é ®o mê µ(A) = Q X µ ®­îc ®Þnh nghÜa:
p(x) . x∈A C¸c to¸n tö WOWA cã thÓ ®­îc biÓu thÞ nh­ lµ tÝch ph©n Choquet khi xÊp xØ ®é ®o mê ®­îc ®Þnh nghÜa. Ta cã thÓ ®Þnh nghÜa ®é ®o tÝnh tuyÓn cña l­îng ho¸ Q nh­ sau: §Þnh nghÜa 1.3.7. Cho mét l­îng ho¸ mê Q, ®Þnh nghÜa: Z Orness(Q) = 1 Q(x)dx . 0 16 §é ®o Orness cña Q ®­îc 1.3.2. To¸n tö LOWA Sö dông kh¸i niÖm tæ hîp låi cña J.Delgado, F.Herrera vµ céng sù ®· ®Þnh nghÜa mét líp to¸n tö LOWA trùc tiÕp suy réng to¸n tö OWA cña R.Yager vµ ¸p dông trong c¸c bµi to¸n quyÕt ®Þnh tËp thÓ. Tuy nhiªn trong qu¸ tr×nh t×m c¸ch øng dông ®Þnh nghÜa vµo trong bµi to¸n ®¸nh gi¸ vµ ­íc l­îng c¸c dù ¸n c«ng thøc ®· cho tá ra kh«ng phï hîp. Víi gîi ý ®ã, t¸c gi¶ ®· sö dông c«ng thøc d­íi ®©y [1]: Cho S = {s1 , s2 , . . . , sT } lµ tËp nh·n, s¾p toµn phÇn s1 < s2 < . . . < sT . Cho a = {a1 , a2 , . . . , am } lµ tËp c¸c phÇn tö cÇn tÝch hîp, mçi ai nhËn gi¸ trÞ trong S. TËp b = {b1 , b2 , . . . , bm } lµ tËp a ®· s¾p xÕp, trong ®ã bj lµ phÇn tö lín thø j cña a. Nh­ vËy b = {sim , si(m−1) , . . . , si1 } víi im ≥ im−1 ≥ . . . ≥ i1 . P Cho W = {w1 , w2 , . . . , wm } lµ vect¬ träng sè, wi ∈ [0, 1] vµ i wi = 1. §Þnh nghÜa 1.3.8. lµ vect¬ träng sè, sè Cho tËp a = {a1 , a2 , . . . , am }, W = {w1 , w2 , . . . , wm } to¸n tö LOWA lµ mét tæ hîp thùc cña vect¬ a víi träng w, Low : (a, w) −→ S cho bëi c«ng thøc truy to¸n sau: 0 0 Low(a, W ) = C{(wim , aim ), (1 − wim , Low(a , w ))}, wj , 1 − wim C lµ phÐp tæ hîp cña hai nh·n (sj , si ), j ≥ i víi träng sè wj > 0, wi > 0, wj + wi = 1, C{(wj , sj ), (wi , si )} = sk , víi k = i + round(wj , (j − i)). ë ®©y a 0 0 0 0 0 0 = {ai(m−1) , . . . , ai1 }, w = {wi1 , wi2 , . . . , wi(m−1) }, wj = NhËn xÐt: Râ rµng nÕu tËp S nhËn c¸c gi¸ trÞ trªn R1 th× to¸n tö Low cho phÐp lÊy trung b×nh cã träng sè quen biÕt, (do vËy Low(a,W) sÏ lµ kú väng to¸n häc khi W lµ vect¬ x¸c suÊt). VÝ dô 1.3.1. Cho a = (s1 , s2 , s3 ), w = (0.2; 0.3; 0.5). Khi ®ã ta tÝnh ®­îc b = (s3 , s2 , s1 ), w3 = 0.5, w2 = 0.3, w1 = 0.2 vµ Low(a, w) = C{(0.5, s3 ), (0.5, Low((s2 , s1 ), (0.2/0.5, 0.3/0.5)))}. 17 Mµ Low((s2 , s1 ), (0.2/0.5, 0.3/0.5)) = C{(3/5, s3 ), (2/5, s2 )} = sk1 , k1 = 1 + round((3/5)(2 − 1)) = 1 + 1 = 2. Do vËy Low(a, w) = C{(0.5, s3 ), (0.5, s2 )} = sk , k = 2 + round((0.5)(3 − 2)) = 3. VËy Low(a, W ) = s3 . 1.3.3. To¸n tö IOWA Yager ®· ph¸t triÓn mét d¹ng to¸n tö OWA tæng qu¸t (Generalized OWA operator- GOWA) mµ OWA lµ tr­êng hîp ®Æc biÖt cña lo¹i tæng qu¸t nµy [4]. §Þnh nghÜa 1.3.9. To¸n tö GOWA n chiÒu lµ mét ¸nh x¹ GOW A : Rn −→ R liªn kÕt víi vect¬ träng sè W vµ GOW A(a1 , . . . , an ) = n X wj bλj
λ1 , j=1 trong ®ã n P wj = 1, wj ∈ [0, 1], bj lµ phÇn tö lín thø j cña tËp ai , vµ j=1 λ ∈ (−∞, ∞) lµ tham sè §Þnh nghÜa 1.3.10. Mét To¸n tö IGOWA n chiÒu lµ mét ¸nh x¹ IGOW A : Rn −→ R liªn kÕt bëi c¸c vect¬ träng sè n chiÒu vµ IGOW A((u1 , a1 ), . . . , (un , an )) = n X j=1 18 wj bλj
λ1 , trong ®ã n P wj = 1, wj ∈ [0, 1], bj lµ gi¸ trÞ ai cña cÆp IGOWA (ui , ai ) lín j=1 thø j, ui biÕn thø tù c¶m sinh, ai lµ biÕn ®èi sè, λ ∈ (−∞, ∞) lµ tham sè To¸n tö IOWA ®­îc giíi thiÖu bëi Yager vµ lµ mét më réng cña to¸n tö OWA. ý nghÜa kh¸c biÖt cña to¸n tö nµy kh«ng ph¶i lµ viÖc ph¸t triÓn víi gi¸ trÞ cña ®èi sè ai mµ lµ viÖc ph¸t triÓn thø tù biÕn c¶m sinh. §Þnh nghÜa 1.3.11. To¸n tö IOWA n chiÒu lµ mét ¸nh x¹ IOW A : Rn −→ R ®­îc liªn kÕt bëi c¸c vect¬ träng sè n chiÒu vµ IGOW A((u1 , a1 ), . . . , (un , an )) = n X
wj bj , j=1 trong ®ã n P wj = 1, wj ∈ [0, 1], bj lµ gi¸ trÞ ai cña cÆp IOWA (ui , ai ) lín j=1 thø j, ui biÕn thø tù c¶m sinh, ai lµ biÕn ®èi sè. 19