Luận văn Toán tử owa trong một số bài toán tối ưu

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ñaW , 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 lµ 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. • 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. • NÕu c¸c träng sè wj = 1 n víi mäi j, vect¬ träng sè kÝ hiÖu lµWave, ký hiÖu to¸n tö OWA øng víi träng sèWave lµ Fave. Ta cã Fave(a) = 1 n n∑ j=1 aj. 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Õu n lµ lÎ lÊy wn+1 2 = 1 vµ ®Æt wj = 0, j 6= n+12 . NÕu n lµ ch½n lÊy wn 2 = wn 2+1 = 1 2 vµ ®Æt wj = 0 cho tÊt c¶ c¸c sè h¹ng kh¸c. 1.1.3. Mét sè tÝnh chÊt Sau ®©y ta ®Òu gi¶ thiÕt W = (w1, ..., wn) T lµ vect¬ träng sè. TÝnh chÊt 1.1.1. §è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). Chøng minh. Gi¶ sö to¸n tö OWA víi vect¬ träng sè 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ã F∗(a1, ..., an) = b10 + b20 + ...+ bn1 = bn = min(ai), F (a1, ..., an) = b1w1 + b2w2 + ...+ bnwn = n∑ i=1 wibi, F ∗(a1, ..., an) = b11 + b20 + ...+ bn0 = b1 = max(ai). Râ rµng n∑ i=1 wibi ≥ n∑ i=1 wibn = bn n∑ i=1 wi = bn = min(ai), n∑ i=1 wibi ≤ n∑ i=1 wib1 = b1 n∑ i=1 wi = b1 = max(ai). 6 Tõ ®ã min(ai) 6 n∑ i=1 wibi 6 max(ai) hay F∗ 6 F 6 F ∗. 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Þ d = (d1, ..., dn) cña a = (a1, ..., an). Chøng minh. V× sù s¾p xÕp lµ duy nhÊt nªn vect¬ cÇn tÝch hîp a vµ ho¸n vÞ 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) Chøng minh. Gi¶ sö vect¬ sau khi s¾p xÕp cña vect¬ 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¶ m·n ai ≥ ci, nªn bi ≥ di víi mäi i. Ta cã F (a1, a2, . . . , an) = b1w1 + b2w2 + . . .+ bnwn, F (c1, c2, . . . , cn) = d1w1 + d2w2 + . . .+ dnwn. 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µ ®é ®o ph©n t¸n cña vect¬W ®­îc x¸c ®Þnh bëi c«ng thøc: Disp(W ) = − n∑ i=1 wi lnwi §Þnh nghÜa 1.1.4. §é ®o thø hai lµ ®é ®o tÝnh tuyÓn cña vect¬W ®­îc cho bëi c«ng thøc: Orness(W ) = 1 n− 1 n∑ i=1 (n− i)wi. VÝ dô 1.1.2. 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 §Þnh nghÜa 1.1.5. a, §é ph©n t¸n Shannon cho bëi c«ng thøc: Hs(W ) = − n∑ i=1 wi log2 wi. b, §é ph©n t¸n RÐnyi's Hα (còng ®­îc gäi lµ ®é ph©n t¸n cña α.) Víi mäi sè thùc α 6= 1 th×: Hα(W ) = 1 1− α log2 n∑ i=1 wαi . c, §é ph©n t¸n cña β ®­îc s¾p kÝ hiÖu lµ Hβ ®­îc giíi thiÖu bëi Daroczy. Víi mäi β 6= 1 th×: Hβ(W ) = 1 21−β − 1 ( n∑ i=1 wβi − 1 ) . d, §é ph©n t¸n R- chuÈn HR(W ) Víi mäi R 6= 1 vµ x¸c ®Þnh theo c«ng thøc: HR(W ) = R R− 1 ( 1− ( n∑ i=1 wRi ) 1 R ) . NhËn xÐt: Sö dông c«ng thøc tÝnh giíi h¹n ta cã: Hs(W ) = lim α→1 Hα(W ) = lim β→1 Hβ(W ) = lim R→1 HR(W ). 1.2. 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¬ W. 9 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è W vµ vect¬ a võa x¸c ®Þnh. VÝ dô 1.2.1. 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: w1 = Q( 1 3 )−Q(0 3 ) = ( 1 3 )2 − 0 = 1 9 , w2 = Q( 2 3 )−Q(1 3 ) = ( 2 3 )2 − (1 3 )2 = 4 9 . 1 9 = 1 3 , w3 = Q( 3 3 )−Q(2 3 ) = (1)2 − (2 3 )2 = 1− 4 9 = 5 9 . Ta cã vect¬ träng sè W = ( 1 9 , 1 3 , 5 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∑ k=1 vk, T = Sn = n∑ k=1 vk. Do ®ã T lµ tæng tÊt c¶ nh÷ng quan träng vµ Si lµ tæng c¸c quan träng tÝnh ®Õn ®iÓm cao thø i. Cuèi cïng ta tÝnh gi¸ trÞ kÕt hîp a∗ = n∑ i=1 biwi. VÝ dô 1.2.2. XÐt ®èi t­îng x víi 4 thuéc tÝnh 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. 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µ Q = r2 (ch¼ng h¹n nh­ lµ "hÇu hÕt"). Sö dông thuËt to¸n trªn ta ®­îc: bj vj A1 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 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 bk1w1 + bk2w2 + . . .+ bknwn = 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 ek = 1 2 ((bk1w1 + bk2w2 + . . .+ bknwn)− dk)2, vµ c¸c wi ph¶i tho¶ m·n c¸c ®iÒu kiÖn: n∑ i=1 wi = 1;wi ∈ [0, 1], i = 1, . . . , n. §Ó ph¸ vì c¸c rµng buéc cña c¸c träng sè, ta biÓu diÔn wi nh­ sau: wi = eλi n∑ i=1 eλi , i = 1, . . . , n. 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 ek = 1 2 ( bk1 eλ1 n∑ i=1 eλ1 + bk2 eλ2 n∑ i=1 eλ2 + . . .+ bkn eλn n∑ i=1 eλn − dk )2 . 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 − d̂k)(d̂k − dk), trong ®ã λi(l + 1) lµ ­íc l­îng míi cña chóng ta vÒ λi. KÝ hiÖu β lµ mét h»ng sè chØ tØ lÖ häc (0 ≤ β ≤ 1), víi mçi i, wi(l) = e λi(l) n∑ i=1 eλi(l) lµ ­íc l­îng cña wi sau lÇn lÆp thø l vµ d̂k = bk1w1(l) + bk2w2(l) + . . .+ bknwn(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µmQ : [0, 1] −→ [0, 1] lµ mét L­îng ho¸ mê kh«ng gi¶m ®¬n ®iÖu chÝnh quy 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. §Þnh nghÜa 1.3.2. Cho P lµ mét vect¬ n chiÒu th× ¸nh x¹WM : Rn −→ R lµ mét Träng sè n chiÒu nÕu WM p(a1, . . . , an) = ∑ i piai. 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 OWAQ : Rn −→ R lµ To¸n tö OWA n chiÒu nÕu OWAQ(a1, . . . , an) = n∑ i=1 (Q(i/n)−Q((i− 1)/n))aσ(i), 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). §Þnh nghÜa to¸n tö OWA trong kh«ng gian 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 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. §Æt P vµ W lµ hai vect¬ träng sè cña kh«ng gian n chiÒu, ¸nh x¹ WOWA : Rn −→ R lµ To¸n tö WOWA( Weighted Or- dered Weighted Averaging) cña kh«ng gian n chiÒu nÕu: WOWAp,w(a1, . . . , an) = ∑ i wiaσ(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: wi = W ∗( ∑ j≤i pσ(i))−W ∗( ∑ j≤i pσ(i)), víi W ∗ lµ hµm ®¬n ®iÖu t¨ng trong kho¶ng (i/n, ∑ j≤i wj) cïng víi ®iÓm cã 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¹ WOWA : Rn −→ R lµ mét to¸n tö WOWA n chiÒu nÕu: WOWAp,Q(a1, . . . , an) = ∑ i wiaσ(i), 15 trong ®ã wi = Q( ∑ j≤i pσ(i))−Q( ∑ j≤i pσ(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. Cho µ lµ mét ®é ®o mê trong X. TÝch ph©n Choquet cña hµm f : X −→ R ®­îc ®Þnh nghÜa: n∑ i=1 (f(xs(i))− f(xs(i−1)))µ(As(i)), trong ®ã f(xs(i)) chØ ra tÝnh ho¸n vÞ, 0 ≤ f(xs(1)) ≤ . . . ≤ f(xs(N)) ≤ 1, As(i) = {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ê µ ®­îc ®Þnh nghÜa: µ(A) = Q (∑ x∈A p(x) ) . 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, §é ®o Orness cña Q ®­îc ®Þnh nghÜa: Orness(Q) = ∫ 1 0 Q(x)dx. 16 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. ChoW = {w1, w2, . . . , wm} lµ vect¬ träng sè, wi ∈ [0, 1] vµ ∑ i wi = 1. §Þnh nghÜa 1.3.8. Cho tËp a = {a1, a2, . . . , am}, W = {w1, w2, . . . , wm} lµ vect¬ träng sè, to¸n tö LOWA lµ mét tæ hîp thùc cña vect¬ a víi träng sè w, Low : (a, w) −→ S cho bëi c«ng thøc truy to¸n sau: Low(a,W ) = C{(wim, aim), (1− wim,Low(a′, w′))}, ë ®©y a ′ = {ai(m−1), . . . , ai1}, w′ = {w′i1, w ′ i2, . . . , w ′ i(m−1)}, w ′ j = 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)). 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¹ GOWA : Rn −→ R liªn kÕt víi vect¬ träng sè W vµ GOWA(a1, . . . , an) = ( n∑ j=1 wjb λ j ) 1 λ , trong ®ã n∑ j=1 wj = 1, wj ∈ [0, 1], bj lµ phÇn tö lín thø j cña tËp ai, vµ λ ∈ (−∞,∞) lµ tham sè §Þnh nghÜa 1.3.10. Mét To¸n tö IGOWA n chiÒu lµ mét ¸nh x¹ IGOWA : Rn −→ R liªn kÕt bëi c¸c vect¬ träng sè n chiÒu vµ IGOWA((u1, a1), . . . , (un, an)) = ( n∑ j=1 wjb λ j ) 1 λ , 18 trong ®ã n∑ j=1 wj = 1, wj ∈ [0, 1], bj lµ gi¸ trÞ ai cña cÆp IGOWA (ui, ai) lín 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¹ IOWA : Rn −→ R ®­îc liªn kÕt bëi c¸c vect¬ träng sè n chiÒu vµ IGOWA((u1, a1), . . . , (un, an)) = ( n∑ j=1 wjbj ) , trong ®ã n∑ j=1 wj = 1, wj ∈ [0, 1], bj lµ gi¸ trÞ ai cña cÆp IOWA (ui, ai) lín thø j, ui biÕn thø tù c¶m sinh, ai lµ biÕn ®èi sè. 19 Ch­¬ng 2 Tèi ­u c¸c träng sè Ta ®· biÕt viÖc x¸c ®Þnh vÐc t¬ träng sè W quyÕt ®Þnh ®Õn hiÖu qu¶ cña to¸n tö OWA. Ng­êi ta th­êng quan t©m ®Õn hai khÝa c¹nh: Sö dông hÇu hÕt c¸c thuéc tÝnh hay chØ sö dông mét sè thuéc tÝnh ®Æc tr­ng cña ®èi t­îng. §iÒu nµy dÉn ®Õn viÖc kh¶o s¸t ®é ph©n t¸n cña vÐc t¬ träng sè. Ngoµi ra viÖc sö dông c¸c thuéc tÝnh cßn phô thuéc vµo ®iÓm nhÊn trong vÐct¬ träng sè, nghÜa lµ cÇn tho¶ mét rµng buéc nµo ®ã vÒ ®é ®o tÝnh tuyÓn. Ch­¬ng nµy tr×nh bµy hai bµi to¸n tèi ­u vÐc t¬ träng sè W theo hai h­íng cùc ®¹i vµ cùc tiÓu ®é ph©n t¸n [3] [6]. 2.1. §é ph©n t¸n cùc ®¹i Trong ch­¬ng tr­íc ta ®· biÕt ®ä ®o Disp ®o ®é ph©n t¸n vect¬ träng sè W , c¸c gi¸ trÞ träng sè gÇn nhau chØ møc ®é sö dông c¸c thµnh phÇn cña vect¬ kÕt hîp lµ t­¬ng ®èi ®Òu nhau. Tuy nhiªn viÖc ®¸nh gi¸ còng cÇn tho¶ ®iÒu kiÖn nµo ®ã vÒ ®iÓm nhÊn, nghÜa lµ cho tr­íc mét gi¸ trÞ α ∈ [0, 1] ®Ó ®¸nh gi¸ møc ®é cùc ®¹i nµy. Tõ ®ã ta cã bµi to¸n sau. Cùc ®¹i ho¸: Disp(W ) = − n∑ i=1 wi lnwi, víi ®iÒu kiÖn: α = 1 n− 1 n∑ i=1 (n− i)wi, 0 ≤ α ≤ 1, n∑ i=1 wi = 0, 0 ≤ wi ≤ 1, i = 1, . . . , n. (2.1) Ta còng cã thÓ ph¸t biÓu bµi to¸n. 20 Cùc ®¹i ho¸: Disp(W ) = − n∑ i=1 wi lnwi, víi ®iÒu kiÖn: Orness(W ) = α, 0 ≤ α ≤ 1, w1 + . . .+ wn = 1, 0 ≤ wi ≤ 1, i = 1, . . . , n. NÕu n = 2 th× tõ Orness(w1, w2) = α, chóng ta ®Æt w1 = α,w2 = 1−α. Ngoµi ra nÕu α = 0 hoÆc α = 1 th× vect¬ träng sè liªn kÕt lµ duy nhÊt vµ ®­îc ®Þnh nghÜa: (0, 0, . . . , 0, 1)T vµ (1, 0, . . . , 0, 0)T . NÕu n > 3 vµ 0 < α < 1, víi λ1, λ2 lµ c¸c sè thùc ta ®Æt: L(W,λ1, λ2) = − n∑ i=1 wi lnwi +λ1 ( n∑ i=1 n− i n− 1wi−α ) +λ2 ( n∑ i=1 wi− 1 ) , lµ hµm Lagrange cña bµi to¸n tèi ­u víi r»ng buéc (2.1). §¹o hµm riªng L víi mäi wj ta ®­îc: ∂L ∂wj = − lnwj − 1 + n− j n− 1λ1 + λ2 = 0, (2.2) vµ ∂L ∂λ1 = n∑ i=1 wi − 1 = 0, ∂L ∂λ2 = n∑ i=1 n− i n− 1wi − α = 0. Cho j = n th× ph­¬ng tr×nh (2.2) trë thµnh: − lnwn − 1 + λ1 = 0 ⇔ λ1 = lnwn + 1. Cho j = 1 ta ®­îc: − lnw1 − 1 + λ1 + λ2 = 0, ⇒ λ2 = lnw1 + 1− λ1 = lnw1 + 1− lnwn − 1, ⇔ λ2 = lnw1 − lnwn. 21 Cho 1 ≤ j ≤ n ta t×m ®­îc: lnwj = j − 1 n− 1 lnwn + n− j n− 1 lnw1, ⇒ wj = n−1 √ wn−j1 w j−1 n . (2.3) NÕu w1 = wn th× (2.3) trë thµnh w1 = w2 = . . . = wn = 1 n , ⇒ Disp(W ) = lnW. §©y lµ lêi gi¶i tèi ­u cña (2.1) cho α = 0, 5 ( thùc tÕ ®©y lµ gi¸ trÞ tèi ­u toµn côc cho ®é ph©n t¸n cña c¸c to¸n tö OWA n chiÒu). Gi¶ sö w1 6= wn. KÝ hiÖu u1 = w 1 (n−1) 1 , un = w 1 (n−1) n , th× (2.3) ®­îc viÕt l¹i wj = u n−j 1 u j−1 n víi mäi 1 ≤ j ≤ n. Tõ ®iÒu kiÖn Orness(W ) = α ta t×m ®­îc: n∑ i=1 n− i n− 1wi = α, ⇔ n∑ i=1 (n− i)un−i1 ui−1n = (n− 1)α, vµ tõ n∑ i=1 (n− i)un−i1 ui−1n = 1 u1 − un [ (n− 1)un1 − n−1∑ i=1 ui1u n−i n ] , = 1 u1 − un [ (n− 1)un1 − u1un un−11 − un−1n u1 − un ] , = 1 (u1 − un)2 [ (n− 1)un1(u1 − un)− un1un + u1unn ] , = 1 (u1 − un)2 [ (n− 1)un+11 − nun1un + u1unn ] . Suy ra: (n− 1)un+11 − nun1un + u1unn = (n− 1)α(u1 − un)2, nun1 − u1 = (n− 1)α(u1 − un), un = 1 (n− 1)α [ ((n− 1)α + 1)u1 − nun1 ] . 22 un u1 = (n− 1)α + 1− nw1 (n− 1)α . (2.4) Tõ ®iÒu kiÖn thø hai w1 + ...+ wn = 1 ta cã: n∑ j=1 un−j1 u j−1 n = 1 ⇔ un1 − unn u1 − un = 1 ⇔ un1 − unn = u1 − un. (2.5) n∑ j=1 un−j1 u j−1 n = 1 ⇔ un−11 − un u1 un−1n = 1− un u1 . (2.6) KÕt hîp (2.4) vµ (2.6) ta cã: w1 − (n− 1)α + 1− nw1 (n− 1)α wn = nw1 − 1 (n− 1)α, vµ suy ra wn = ((n− 1)α− n)w1 + 1 (n− 1)α + 1− nw1 . (2.7) ViÕt l¹i ph­¬ng tr×nh (2.5) un1 − unn = u1 − un, u1(w1 − 1) = un(wn − 1), w1(w1 − 1)n−1 = wn(wn − 1)n−1, w1(w1 − 1)n−1 = ((n− 1)α− n)w1 + 1 (n− 1)α + 1− nw1 [ (n− 1)α(w1 − 1) (n− 1)α + 1− nw1 ]n−1 . Tøc lµ: w1[(n− 1)α + 1− nw1]n = [(n− 1)α]n−1[((n− 1)α− n)w1 + 1]. (2.8) V× thÕ gi¸ trÞ tèi ­u cña w1 sÏ tho¶ m·n ph­¬ng tr×nh (2.8). w1 ®­îc tÝnh theo wn cã thÓ x¸c ®Þnh tõ ph­¬ng tr×nh (2.7) vµ träng sè kh¸c tÝnh ®­îc tõ ph­¬ng tr×nh (2.3). 23 VÝ dô 2.1.1. X¸c ®Þnh vect¬ cùc ®¹i víi n = 5, α = 0, 4: Ta cã bµi to¸n cùc ®¹i ho¸: − n∑ i=1 wi lnwi, tho¶ ®iÒu kiÖn: α = 1 n− 1 n∑ i=1 (n− i)wi, 0 ≤ α ≤ 1, n∑ i=1 wi = 0, 0 ≤ wi ≤ 1, i = 1, . . . , n. VËy lêi gi¶i cña bµi to¸n trªn lµ: w1[4 ∗ 0.4 + 1− 5w1]5 = [4 ∗ 0.4]4[(4 ∗ 0.4− 5)w1 + 1], Ta t×m ®­îc kÕt qu¶ nh­ sau w∗1 = 0.1278 w∗5 = (4 ∗ 0.4− 5)w∗1 + 1 4 ∗ 0.4 + 1− 5w∗1 = 0.2884 w∗2 = 4 √ (w∗1)3(w ∗ 5) = 0.1566 w∗3 = 4 √ (w∗1)2(w ∗ 5) 2 = 0.192 w∗4 = 4 √ (w∗1)(w ∗ 5) 3 = 0.2353. Ta cã Disp(W ∗) = 1, 5692. 2.2. §é ph©n t¸n cùc tiÓu B©y giê ta xÐt bµi to¸n. Cùc tiÓu ho¸: Disp(W ) = − n∑ i=1 wi lnwi, 24 víi ®iÒu kiÖn (2.1) PhÇn trªn ®· ®­a ra lêi gi¶i tèi ­u cña bµi to¸n (2.1) tíi ph­¬ng tr×nh ®a thøc (2.8). Mét c©u hái thó vÞ kh¸c lµ x¸c ®Þnh tÝnh cùc tiÓu cña vect¬ träng sè nh­ thÕ nµo? Tr­íc tiªn ta tÝnh ph­¬ng sai cña mét vect¬ träng sè nh­ sau D2(W ) = n∑ i=1 1 n (wi − E(W ))2 = 1 n n∑ i=1 w2i − (1 n n∑ i=1 wi )2 = 1 n n∑ i=1 w2i − 1 n2 . Trong ®ã E(W ) = 1 n (w1 + . . .+ wn). XÐt bµi to¸n: Cùc tiÓu ho¸: D2(W ) = 1 n n∑ i=1 w2i − 1 n2 . víi ®iÒu kiÖn w1 + . . .+ wn = 1, 0 ≤ wi, i = 1, . . . , n vµ Orness(W ) = n∑ i=1 n− i n− 1wi = α, 0 ≤ α ≤ 1, (2.9) Ta xÐt bµi to¸n (2.9) trong tr­êng hîp n = 2. V×Orness(w1, w2) = α nªn träng sè tèi ­u ®­îc ®Þnh nghÜa duy nhÊt w∗1 = α, w ∗ 2 = 1−α. Ngoµi ra nÕu α = 0 hoÆc α = 1 th× vect¬ träng sè liªn kÕt ®­îc ®Þnh nghÜa (0, . . . , 0, 1)T vµ (1, 0, . . . , 0)T víi c¸ch tÝnh: D2(1, 0, . . . , 0) = D2(0, . . . , 0, 1) = 1 n − 1 n2 . Gi¶ sö n ≥ 3 vµ 0 < α < 1 ta xÐt hµm Lagrange: L(W,λ1, λ2) = 1 n n∑ i=1 w2i − 1 n2 + λ1 ( n∑ i=1 n− i n− 1wi − α ) + λ2 ( n∑ i=1 wi − 1 ) , 25 víi λ1, λ2 lµ c¸c sè thùc. §¹o hµm riªng L theo wj víi 1 ≤ j ≤ n ta ®­îc: ∂L ∂wj = 2wj n + n− j n− 1λ1 + λ2 = 0, (2.10) ∂L ∂λ1 = n∑ i=1 wi − 1 = 0, ∂L ∂λ2 = n∑ i=1 n− i n− 1wi − α = 0. Gi¶ sö vect¬ träng sè tèi ­u cã d¹ng: W = (0, . . . , 0, wp, . . . , wq, 0, . . . , 0) T , (2.11) trong ®ã 1 ≤ p ≤ q ≤ n vµ ta kÝ hiÖu I{p,q} = {p, p+ 1, . . . , q − 1, q}. NÕu j 6∈ I{p,q} th× wj = 0. NÕu j ∈ I{p,q} th× wj ≥ 0. Cho j = p ta cã ∂L ∂wp = 2wp n + λ1 + n− p n− 1λ2 = 0, vµ cho j = q ta cã ∂L ∂wq = 2wq n + λ1 + n− q n− 1λ2 = 0. Tõ ®ã ta cã: 2(wp − wq) n + q − p n− 1λ2 = 0, vµ suy ra gi¸ trÞ tèi ­u cña λ1, λ2 ( kÝ hiÖu bëi λ ∗ 1, λ ∗ 2) sÏ tho¶ m·n hÖ ph­¬ng tr×nh λ∗1 = 2 n [ n− q q − pwp − n− p q − pwq ] , λ∗2 = n− 1 q − p . 2 n (wq − wp). (2.12) 26 Thay thÕ λ∗1 cho λ1 vµ λ ∗ 2 cho λ2 trong (2.10) ta cã 2 n wj + 2 n [ n− q q − pwp − n− p q − pwq ] + n− j n− 1 . n− 1 q − p . 2 n (wq − wp). Trong ®ã träng sè tèi ­u thø j ∈ I{p,q} sÏ tho¶ m·n ph­¬ng tr×nh: w∗j = q − j q − pwp + j − p q − pwq. (2.13) Tõ biÓu diÔn (2.11) ta cã q∑ i=p w∗i = 1, tøc lµ q∑ i=p ( q − i q − pwp + i− p q − pwq ) = 1, wp + wq = 2 q − p+ 1 . V× Orness(W ) = α ta t×m ®­îc q∑ i=p n− i n− 1wi = q∑ i=p n− i n− 1 . q − i q − pwp + q∑ i=p n− i n− 1 . i− p q − pwq = α. Tøc lµ w∗p = 2(2q + p− 2)− 6(n− 1)(1− α) (q − p+ 1)(q − p+ 2) , (2.14) vµ w∗q = 2 (q − p+ 1) − w ∗ p = 6(n− 1)(1− α)− 2(q + 2p− 4) (q − p+ 1)(q − p+ 2) . (2.15) Vect¬ träng sè W ∗ = (0, . . . , 0, w∗p, . . . , w ∗ q , 0, . . . , 0) T cã thÓ lµ vect¬ träng sè nÕu vµ chØ nÕu w∗p, w ∗ q ∈ [0, 1]. Sö dông d¹ng (2.14) vµ (2.15) ta t×m ®­îc: w∗p, w ∗ q ∈ [0, 1] ⇔ α ∈ [ 1− 1 3 . 2q + p− 2 n− 1 , 1− 1 3 . q + 2p− 4 n− 1 ] . XÐt ph©n ho¹ch (0, 1) = n−1⋃ r=2 Jr,n ∪ J1,n ∪ n−1⋃ s=2 J1,s, (2.16) 27 trong ®ã r = 2, . . . , n− 1 vµ s = 2, . . . , n− 1 Jr,n = ( 1− 1 3 . 2n+ r − 2 n− 1 , 1− 1 3 . 2n+ r − 3 n− 1 ] , J1,n = ( 1− 1 3 . 2n− 1 n− 1 , 1− 1 3 . n− 2 n− 1 ) , J1,s = [ 1− 1 3 . s− 1 n− 1 , 1− 1 3 . s− 2 n− 1 ) . XÐt l¹i bµi to¸n (2.9) vµ gi¶ sö α ∈ Jr,s víi mçi r, s x¸c ®Þnh theo (2.16).(r vµ s lu«n tån t¹i víi bÊt kú α ∈ (0, 1)) XÐt W ∗ = (0, . . . , 0, w∗r , . . . , w ∗ s , 0, . . . , 0) T , (2.17) trong ®ã w∗j = 0, nÕuj 6∈ I{r,s}, w∗r = 2(2s+ r − 2)− 6(n− 1)(1− α) (s− r + 1)(s− r + 2) , w∗s = 6(n− 1)(1− α)− 2(s+ 2r − 4) (s− r + 1)(s− r + 2) , w∗j = s− j s− rwr + j − r s− rws, nÕuj ∈ I{r+1,s−1}. (2.18) I{r+1,s−1} = {r + 1, . . . , s− 1}. Tõ c¸ch x©y dùng vect¬ W ∗ ta cã n∑ i=1 w∗i = s∑ i=r w∗i = 1, w∗i ≥ 0, i = 1, . . . , n Orness(W ∗) = α, tøc lµ W ∗ tho¶ m·n bµi to¸n cùc tiÓu (2.9). VËy vect¬ W ∗ lµ vect¬ träng sè cña bµi to¸n (2.9). §Ó chøng minh D2 ®¹t gi¸ trÞ nhá nhÊt ta chøng minh bæ ®Ò sau. Bæ ®Ò 2.2.1. Cho to¸n tö OWA cã träng sè w cè ®Þnh. i, Tån t¹i λ∗1, λ ∗ 2 ∈ R vµ µ∗1 ≥ 0, . . . , µ∗n ≥ 0 sao cho: 28 ∂∂wk ( D2(W ) + λ∗1 [ n∑ i=1 wi − 1 ] + λ∗2 [ n−1∑ i=1 n− i n− 1wi − α ] + n∑ j=1 µ∗j(−wj) )∣∣∣∣ W=W ∗ = 0, víi 1 ≤ k ≤ n vµ µ∗jw∗j = 0, j = 1, . . . , n. ii, W ∗ lµ ®iÓm chÝnh quy cña sù liªn kÕt. iii, Ma trËn Hessian ∂2 ∂W 2 ( D2(W ) + λ∗1 [ n∑ i=1 wi − 1 ] + λ∗2 [ n−1∑ i=1 n− i n− 1wi − α ] + n∑ j=1 µ∗j(−wj) )∣∣∣∣ W=W ∗ , lµ ®¹i l­îng d­¬ng x¸c ®Þnh trªn X̂ = { y ∣∣∣∣h1yT = 0, h2yT = 0, gjyT = 0, µj > 0}, víi mäi j, trong ®ã: h1 = (n− 1 n− 1 , n− 2 n− 1 , . . . , 1 n− 1 , 0 )T , vµ h2 = (1, 1, . . . , 1) T , lµ gradient cña sù liªn kÕt ®¼ng thøc tuyÕn tÝnh, gj = (0, 0, . . . , 0,−1, 0, . . . , 0)T lµ liªn kÕt cña bÊt ®¼ng thøc tuyÕn tÝnh thø j. Chøng minh. i, Ta ®Æt: λ∗1 = 2 n [ n− s s− rw ∗ r − n− r s− r w ∗ s ] , λ∗2 = n− 1 s− r . 2 n (w∗s − w∗r), vµ víi k = 1, . . . , n th× 2 n w∗k + λ ∗ 1 + n− k n− 1λ ∗ 2 − µk = 0. 29 NÕu k ∈ I{r,s} th×: µ∗k = 2 n [ s− k s− rw ∗ r + k − r s− rw ∗ s ] + 2 n [ n− s s− rw ∗ r − n− r s− r w ∗ s ] + n− k n− 1 . n− 1 s− r . 2 n (w∗s − w∗r) = 2 n . 1 s− r [ (s− k + n− s− n+ k)w∗r + (k − r − n+ r + n− k)w∗s ] = 0. NÕu k 6∈ I{r,s} th× w∗k = 0. Tõ ®¼ng thøc: λ∗1 + n− k n− 1λ ∗ 2 − µk = 0, chóng ta t×m ®­îc: µ∗k = λ ∗ 1 + n− k n− 1λ ∗ 2 = 2 n [ n− s s− rw ∗ r − n− r s− r w ∗ s ] + n− k n− 1 . n− 1 s− r . 2 n (w∗s − w∗r) = 2 n . 1 s− r [(k − s)w ∗ r + (r − k)w∗s . Víi µ∗k ≥ 0 vµ k 6∈ I{r,s} th×: (k − s)w∗r + (r − k)w∗s = (k − s). 2(2s+ r − 2)− 6(n− 1)(1− α) (s− r + 1)(s− r + 2) + (r − k).6(n− 1)(1− α)− 2(s+ 2r − 4) (s− r + 1)(s− r + 2) ≥ 0. NÕu r = 1, vµ s = n th× ®Æt µ∗k = 0, víi k = 1, . . . , n B©y giê gi¶ sö r = 1 vµ s s > 1 lµ ®óng vµ ph­¬ng tr×nh trªn phô thuéc vµo α, α ≥ 1− (s− 1)(3k − 2s− 2) 3(n− 1)(2k − s− 1) . Trong tr­êng hîp kh¸c, α ∈ J1,s vµ s < n ta cã: α ∈ [ 1− 1 3 . s− 1 n− 1 , 1− 1 3 . s− 2 n− 1 ) , 30 vµ suy ra α ≥ 1− 1 3 . s− 1 n− 1 . Cuèi cïng tõ bÊt ®¼ng thøc 1− 1 3 . s− 1 n− 1 ≥ 1− (s− 1)(3k − 2s− 2) 3(n− 1)(2k − s− 1) ta cã i, ®óng. ii, NÕu r = 1 vµ s = n th× víi j = 1, . . . , n ta cã w∗j 6= 0. h1, h2 lµ ®éc lËp tuyÕn tÝnh. NÕu r = 1, s < n víi j = s+ 1+ . . .+ n th× w∗j = 0. Trong tr­êng hîp nµy ta cã: gj = (0, 0, . . . , 0,−1, 0, . . . , 0, 0)T , XÐt ma trËn: G = [ hT1 , h T 2 , g T s+1, . . . , g T n ] ∈ Rn(n−s+2). th× sù x¸c ®Þnh ma trËn d­íi tr¸i (n− s+ 2)(n− s+ 2) chiÒu cña ma trËn G lµ ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ n− s+ 1 n− 1 1 0 · · · 0 n− s n− 1 1 0 · · · 0 n− s− 1 n− 1 1 −1 · · · 0 . . . . . . . . . . . . 0 0 1 0 · · · −1 ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ = (−1)n−s ∣∣∣∣∣∣∣ n− s+ 1 n− 1 1 n− s n− 1 1 ∣∣∣∣∣∣∣ = 1 n− 1(−1) n−s NghÜa lµ vect¬ cét cña G lµ ®éc lËp tuyÕn tÝnh vµ hÖ {h1, h2, gs+1, . . . , gn} ®éc lËp tuyÕn tÝnh. NÕu r > 1 vµ r = n th× w∗j = 0 víi j = 1, . . . , r − 1. Trong tr­êng hîp nµy gj = (0, 0, . . . , 0,−1, 0, . . . , 0, 0)T . 31 XÐt ma trËn F = [ hT1 , h T 2 , g T 1 , . . . , g T r−1 ] ∈ Rn(r+1) th× sù x¸c ®Þnh ma trËn tr¸i trªn (r + 1)(r + 1)chiÒu cña F lµ: ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ n− 1 n− 1 1 −1 · · · 0 . . . . . . . . . . . . 0 n− r + 1 n− 1 1 0 · · · −1 n− r n− 1 1 0 · · · 0 n− r − 1 n− 1 1 0 · · · 0 ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ = (−1)r−1 ∣∣∣∣∣∣∣ n− r n− 1 1 n− r − 1 n− 1 1 ∣∣∣∣∣∣∣ = 1 n− 1(−1) r−1 NghÜa lµ vect¬ cét cña F lµ ®éc lËp tuyÕn tÝnh vµ hÖ {h1, h2, gs+1, . . . , gn} lµ ®éc lËp tuyÕn tÝnh. V× thÕ W ∗ chÝnh quy. iii, KÝ hiÖu: K(W ) = D2(W ) + λ∗1 [ n∑ i=1 wi − 1 ] + λ∗2 [ n−1∑ i=1 n− i n− 1wi − α ] + n∑ j=1 µ∗j(−wj). Ma trËn Hessian cña K t¹i W ∗ lµ: ∂2 ∂wk∂wj K(W ) ∣∣∣∣ W=W ∗ = ∂2 ∂wk∂wj D2(W ) ∣∣∣∣ W=W ∗ = 2 n δkj, trong ®ã δkj = 1 nÕu j = k,0 nÕu j 6= k. Ma trËn K ′′ (W ∗) = 2 n  1 0 · · · 0 0 1 · · · 0 . . . . . . . . . . . . 0 0 · · · 1  32 lµ ma trËn x¸c ®Þnh d­¬ng trªn Rn 2 Quay l¹i bµi to¸n (2.9), ¸p dông c¸ch chøng minh cña bæ ®Ò trªn th× D2(W ) ®¹t nhá nhÊt t¹i W = W ∗, X = { W ∈ Rn ∣∣∣∣W ≥ 0, n∑ i=1 wi = 1, n∑ i=1 n− i n− 1wi = α } trong ®ã X lµ tËp lêi gi¶i thùc hiÖn ®­îc cña bµi to¸n (2.9). XÐt D2(W ) : Rn → R lµ chÆt chÏ låi, hµm X lµ tËp con låi compact cña tËp Rn, D2(W ) ®¹t tíi gi¸ trÞ nhá nhÊt trªn X t¹i W ∗. VÝ dô 2.2.1. X¸c ®Þnh cùc tiÓu cña vect¬ träng sè 5 chiÒu khi biÕt α = (0, 0.1, . . . , 0.9, 1) Ta cã bµi to¸n cùc tiÓu ho¸: D2(W ) = 1 n n∑ i=1 w2i − 1 n2 . víi ®iÒu kiÖn w1 + . . .+ wn = 1, 0 ≤ wi, i = 1, . . . , n Orness(W ) = n∑ i=1 n− i n− 1wi = α, 0 ≤ α ≤ 1, Tr­íc hÕt chóng ta xÐt ph©n ho¹ch t­¬ng øng: (0, 1) = 4⋃ r=2 Jr,5 ∪ J1,5 ∪ 4⋃ s=2 J1,s, trong ®ã Jr,5 = ( 1 3 . 5− r − 1 5− 1 , 1 3 . 5− r 5− 1 ] = ( 4− r 12 , 5− r 12 ] , cho r = 2, 3, 4 ta tÝnh ®­îc J1,5 = ( 1 3 . 5− 2 5− 1 , 1 3 . 10− 1 5− 1 ) = ( 3 12 , 9 12 ) , J1,s = ( 1− 1 3 . s− 1 5− 1 , 1− 1 3 . s− 2 5− 1 ) = [ 13− s 12 , 14− s 12 ) , 33 cho s = 2, 3, 4 ta cã (0, 1) = ( 0, 1 12 ] ∪ ( 1 12 , 2 12 ] ∪ ( 2 12 , 3 12 ] ∪ ( 3 12 , 9 12 ) ∪ [ 9 12 , 10 12 ) ∪ [ 10 12 , 11 12 ) ∪ [ 11 12 , 12 12 ) . Kh«ng lµm mÊt tÝnh tæng qu¸t, gi¶ sö α < 0.5, ®Þnh nghÜaWRi = wn−i+1 lµ lêi gi¶i tèi ­u cho bµi to¸n (2.9) d­íi ®é ®o tÝnh tuyÓn 1−α. Ph­¬ng sai D2(WR) = D2(W ) vµ Orness(WR) = 1−Orness(W ). • NÕu α = 0 th× W ∗(α) = W ∗(0) = (0, 0, . . . , 0, 1)T , W ∗(1) = (W ∗(0))R = (1, 0, . . . 0, 0)T . • NÕu α = 0.1 th× α ∈ J3,5 = ( 1 12 , 2 12 ] , vµ vect¬ träng sè nhá nhÊt lµ: w∗1(0.1) = 0, w∗2(0.1) = 0, w∗3(0.1) = 2(10 + 3− 2)− 6(5− 1)(1− 0.1) (5− 3 + 1)(5− 3 + 2) = 0.4 12 = 0.0333, w∗5(0.1) = 2 5− 3 + 1 − w ∗ 3(0.1) = 0.6334, w∗4(0.1) = 1 2 w∗3(0.1) + 1 2 w∗5(0.1) = 0.3333, do ®ã W ∗(α) = W ∗(0.1) = (0, 0, 0.033, 0.333, 0.633)T , vµ W ∗(0.9) = (W ∗(0.1))R = (0.633, 0.333, 0.033, 0, 0)T , víi ph­¬ng sai D2(W ∗(0.1)) = 0.0625. • NÕu α = 0.2 th× α ∈ J2,5 = ( 2 12 , 3 12 ] , vect¬ träng sè nhá nhÊt vµ 34 ph­¬ng sai lµ: W ∗(0.2) = (0, 0.04, 0.18, 0.32, 0.46)T , W ∗(0.8) = (0.46, 0.32, 0.18, 0.04, 0)T , D2(W ∗(0.2)) = 0.0296. • NÕu α = 0.3 th× α ∈ J1,5 = ( 3 12 , 9 12 ] , víi lèi tÝnh trªn ta cã: W ∗(0.3) = (0.04, 0.12, 0.2, 0.28, 0.36)T , W ∗(0.7) = (0.36, 0.28, 0.2, 0.12, 0.04)T , D2(W ∗(0.3)) = 0.0128. • NÕu α = 0.4 th× α ∈ J1,5 = ( 3 12 , 9 12 ] , t­¬ng tù trªn ta cã: W ∗(0.4) = (0.12, 0.16, 0.2, 0.24, 0.28)T , W ∗(0.6) = (0.28, 0.24, 0.2, 0.16, 0.12)T , D2(W ∗(0.4)) = 0.0032. • NÕu α = 0.5 th× W ∗(0.5) = (0.2, 0.2, 0.2, 0.2, 0.2)T vµ ph­¬ng sai D2(W ∗(0.5)) = 0. 35 Ch­¬ng 3 Mét sè øng dông cña to¸n tö OWA Trong ch­¬ng nµy ta ®i nghiªn cøu mét sè øng dông cña to¸n tö OWA trong mét sè bµi to¸n cô thÓ gåm ®¸nh gi¸ dùa trªn ®é quan träng, c¸c thuËt to¸n ph©n côm vµ øng dông trong mét d¹ng to¸n tèi ­u. 3.1. Ra quyÕt ®Þnh dùa trªn ®é quan träng Mét líp quan träng c¸c bµi to¸n kÕt hîp lµ c¸c bµi to¸n kÕt hîp ®a tiªu chuÈn ch¼ng h¹n nh÷ng bµi to¸n n¶y sinh trong c¸c øng dông nh­ ra quyÕt ®Þnh, nhËn d¹ng mÉu, thu thËp th«ng tin. Víi d¹ng thu thËp th«ng tin, ®iÒu kiÖn g¾n liÒn víi c¸c thuéc tÝnh cña t­ liÖu ®ang t×m kiÕm. §iÓm chung cña nh÷ng bµi to¸n nµy lµ c¸c tiªu chuÈn thu thËp Ai víi i = 1, . . . , n vµ mét tËp X c¸c gi¶i ph¸p. Víi mét lùa chän x ta cã mét gi¸ trÞ ai ∈ [0, 1] chØ ra møc ®é mµ x tho¶ m·n tiªu chuÈn Ai. Ta sö dông nh÷ng gi¸ trÞ ai nµy ®Ó kÕt hîp chóng thµnh mét ®iÓm tæng thÓ cho lùa chän x, kÝ hiÖu lµ a∗ = Agg(a1, a2, . . . , an). ë ®©y Agg lµ c¸c phÐp to¸n c¬ b¶n ®Ó kÕt hîp c¸c ®iÓm trung b×nh, cùc ®¹i, cùc tiÓu. Nh÷ng lùa chän riªng rÏ sÏ ®­îc so s¸nh víi c¸c ®iÓm tæng thÓ nµy. Ph­¬ng ph¸p ®Ó thùc hiÖn to¸n tö Agg lµ sö dông to¸n tö OWA a∗ = Fw(a1, a2, . . . , an), Fw ë trªn lµ mét to¸n tö OWA ®Æc biÖt. ViÖc chän to¸n tö OWA víi vÐc t¬ träng sè W nh»m ph¶n ¸nh mèi quan hÖ gi÷a nh÷ng ®iÒu kiÖn ®ang ®­îc kÕt hîp. NÕu ta yªu cÇu tÊt c¶ c¸c tiªu chuÈn ph¶i ®­îc tho¶ m·n th× ta sö dông min : W = W∗. NÕu cÇn tho¶ m·n víi mét bÊt kú tiªu chuÈn nµo th× 36 ta sö dông max : W = W ∗. NÕu yªu cÇu chän mét con sè trung b×nh cña c¸c tho¶ m·n ®iÒu kiÖn riªng rÏ th× cã thÓ sö dông W = Wave. Nãi c¸ch kh¸c c¸c to¸n tö OWA cho phÐp biÓu thÞ mèi quan hÖ gi÷a c¸c tiªu chuÈn. Ta tÝnh a∗ = Fw((u1, a1), (u2, a2), . . . , (un, an)), trong ®ã ai ∈ [0, 1] lµ ®iÓm cña tiªu chuÈn thø i vµ ui ∈ [0, 1] lµ sù quan träng cña tiªu chuÈn thø i. Ta sÏ xem xÐt mét sè tiÕp cËn cæ ®iÓn sö dông trong mét sè to¸n tö OWA kh¸c nhau. Trong tr­êng hîp to¸n tö trung b×nh, c¸c quan träng ®­îc xem lµ b×nh ®¼ng vµ ta sö dông trung b×nh cã träng sè a∗ = n∑ j=1 uj T aj = 1 n n∑ j=1 n T ujaj, trong ®ã T = n∑ j=1 uj lµ tæng cña c¸c träng sè quan träng. Trong tr­êng hîp to¸n tö min, mét tiÕp cËn chung lµ sö dông a∗ = min j [S(uj, aj)], trong ®ã uj = 1− uj vµ S lµ bÊt k× t- ®èi chuÈn nµo. Trong tr­êng hîp to¸n tö max, mét tiÕp cËn chung lµ sö dông a∗ = max j [T (uj, aj)], trong ®ã T lµ t- chuÈn bÊt k×. C¶ ba tr­êng hîp max, min, average ®Òu sö dông c¸c ph­¬ng ph¸p luËn kh¸c nhau nh­ng ®Òu cã tÝnh quy luËt. To¸n tö Agg nhËn n ®iÓm trong kho¶ng ®¬n vÞ vµ tr¶ vÒ mét gi¸ trÞ trong kho¶ng ®¬n vÞ Agg : In −→ I. Trong tr­êng hîp khi ta cã quan träng g¾n víi ®iÒu kiÖn, thay cho viÖc cã c¸c gi¸ trÞ ®¬n, ta cã c¸c d¹ng (uj, aj) vµ do ®ã ta kh«ng trùc tiÕp sö dông hµm Agg. Ta lÊy mçi cÆp (uj, aj) vµ ¸p dông mét phÐp chuyÓn ®æi 37 sù quan träng ®Ó thu ®­îc mét gi¸ trÞ hiÖu qu¶, bj = G(uj, aj). Sau ®ã ¸p dông phÐp to¸n Agg c¬ b¶n cho c¸c gi¸ trÞ ®· ®­îc chuyÓn ®æi nµy. a∗ = Agg(b1, b2, . . . , bn) B¶ng sau sÏ tãm t¾t ba tr­êng hîp nµy Tªn To¸n tö Average Sù chuyÓn ®æi cña (uj, aj) Max Maxj[bj] bj = T (uj, aj) Min Minj[bj] bj = S(u, aj) Average 1 n n∑ j=1 bj bj = n T ujaj B¶ng 3.1 VÝ dô 3.1.1. XÐt mét bµi to¸n thùc tÕ lµ bµi to¸n tÝnh ®iÓm trung b×nh häc tËp cho sinh viªn ®¹i häc theo chÕ ®é häc tr×nh. Theo c¸ch tÝnh ®iÓm hiÖn nay cña sinh viªn th× ch­¬ng tr×nh ®µo t¹o ®­îc chia ra nhiÒu häc phÇn mçi häc phÇn gåm nhiÒu häc tr×nh vµ kÕt qu¶ ®­îc tÝnh theo c«ng thøc: D′tb = ∑ d(i)ht(i)∑ ht(i) , trong ®ã d(i) lµ ®iÓm m«n thø i vµ ht(i) lµ sè häc tr×nh cña m«n thø i t­¬ng øng. C¸ch tÝnh ®iÓm nµy tiÖn lîi, dÔ tÝnh vµ kÕt qu¶ tØ lÖ víi thêi l­îng häc. Tuy nhiªn nã còng béc lé nh÷ng ®iÓm yÕu lµ: • C¸ch ph©n lo¹i häc tËp bÞ chÆn cøng, vÝ dô sinh viªn xÕp lo¹i trung b×nh nÕu 5 ≤ kq < 7 vµ xÕp lo¹i kh¸ nÕu 7 ≤ kq < 9. Nh­ vËy c¸c sinh viªn cã kÕt qu¶ lµ 5.0 vµ 6.9 ®Òu cïng mét lo¹i trong khi ®ã 6.9 víi 7.0 l¹i thuéc 2 lo¹i kh¸c nhau. • Nh­ ®· nªu ë trªn, c«ng thøc tÝnh ®iÓm kÕt qu¶ chñ yÕu dùa trªn thêi gian dµnh cho mçi m«n häc chø kh«ng chó ý ®Õn nh÷ng m«n häc cã kÕt qu¶ tèt hay kÐm. Nh­ vËy nÕu so s¸nh 2 sinh viªn cã kÕt qu¶ ®iÓm b»ng nhau th× khã cã thÓ nãi sinh viªn sÏ ®­îc ­u tiªn h¬n nÕu tuyÓn dông (vÒ n¨ng lùc chuyªn m«n) theo nhu cÇu c«ng viÖc nµo ®ã. 38 NÕu ¸p dông kÕt qu¶ nghiªn cøu trªn vÒ to¸n tö OWA th× cã thÓ ®Ò xuÊt c¸ch ph©n lo¹i kh¸c nhau dùa trªn ®é quan träng cña mçi m«n häc. §é quan träng nµy cã thÓ thu nhËn tõ ý kiÕn cña c¸c chuyªn gia. M« h×nh cña chóng t«i nh­ sau. XÐt b¶ng ®iÓm cña ba sinh viªn xin viÖc. §iÓm trung b×nh häc tËp cña hä ®­îc tÝnh theo c«ng thøc trªn. Song nÕu cÇn tuyÓn ng­êi theo mét tiªu chÝ nµo ®ã ta sÏ g¾n mçi gi¸ trÞ ®iÓm cña mét häc phÇn víi mét gi¸ trÞ lµ ®é quan träng cña häc phÇn ®ã. NghÜa lµ trong c«ng thøc trªn ta thay gi¸ trÞ ht(i) bëi ®é quan träng dqt(i) theo c«ng thøc: D′qt = ∑ d(i)dqt(i)∑ dqt(i) , trong ®ã d(i) lµ ®iÓm m«n thø i vµ dqt(i) lµ ®é quan träng cña m«n thø i t­¬ng øng. Víi c¸ch tÝnh ®iÓm nµy râ rµng sù ph©n lo¹i ®· theo chiÒu h­íng kh¸c: c¸c m«n häc phï hîp víi tiªu chÝ ®¸nh gi¸ sÏ cã träng sè cao h¬n nªn sÏ ®­îc ­u tiªn h¬n. B©y giê ta xÐt mét c¸ch tiÕp cËn kh¸c: C¸ch tÝnh ®iÓm theo vect¬ träng sè cña to¸n tö OWA. Gi¶ sö cÇn xÐt ­u tiªn nh÷ng sinh viªn cã nhiªu ®iÓm cao h¬n nh÷ng ng­êi cã ®iÓm sè c¸c m«n ®Òu nhau. Víi mét c¬ së d÷ liÖu lín th× viÖc xÐt chän b»ng tay lµ ®iÒu rÊt khã. Song ta cã thÓ gi¶i quyÕt ®iÒu nµy b»ng c¸ch sö dông to¸n tö OWA víi c¸c träng sè ®­îc xÕp theo thø tù gi¶m dÇn. NghÜa lµ ta sö dông c«ng thøc: D′OWA = ∑ d(i)w(i), trong ®ã W = (w1, . . . , wn) vµ c¸c wi ®­îc xÕp theo thø tù gi¶m dÇn. Gi¶ sö c¸c m«n häc kÝ hiÖu m1 −→ m20. Sè ®¬n vÞ häc tr×nh t­¬ng øng lµ: (6, 6, 6, 6, 3, 6, 5, 7, 5, 6, 4, 6, 4, 5, 5, 4, 4, 3, 3, 3) §é quan träng lµ V =(0.07, 0.03, 0.03, 0.02, 0.03, 0.07, 0.03, 0.03, 0.02, 0.1, 0.03, 0.05, 0.02, 0.05, 0.06, 0.03, 0.1, 0.1, 0.1, 0.03) 39 Vect¬ träng sè W =(0.103, 0.1, 0.098, 0.087, 0.083, 0.08, 0.075, 0.063, 0.06, 0.05, 0.047, 0.03, 0.025, 0.02, 0.019, 0.014, 0.013, 0.012, 0.011, 0.01) §iÓm cña ba sinh viªn vµ ®¬n vÞ häc tr×nh ®­îc cho bëi: TrÇn ThÞ Cóc (6, 8, 8, 6, 8, 6, 7, 9, 7, 5, 5, 8, 5, 9, 6, 8, 5, 6, 6, 9) Lª Thanh Mai (7, 7, 6, 8, 7, 5, 7, 6, 5, 7, 8, 7, 5, 7, 8, 7, 9, 8, 7, 7) Cao Thu Tróc (6, 8, 5, 8, 6, 7, 6, 7, 8, 8, 6, 5, 6, 8, 5, 7, 6, 6, 5, 5) D­íi ®©y ®­a ra kÕt qu¶ tÝnh ®iÓm cña 3 sinh viªn theo 3 c¸ch. Tªn §iÓm trung b×nh §iÓm quan träng §iÓm OWA Cóc 6.9 6.47 6.9 Mai 6.8 7.13 6.7 Tróc 6.5 6.3 6.6 B¶ng 3.2 KÕt qu¶ thÊy râ c¸ch tÝnh vµ ph©n lo¹i nµy ®· cã sù ph©n biÖt ®¸ng kÓ gi÷a c¸c sinh viªn cã cïng ®iÓm trung b×nh. Râ rµng nÕu xÐt theo ®é quan träng, th«ng tin nµy cã ý nghÜa ®¸ng kÓ cho ng­êi tuyÓn dông ch¼ng h¹n. T­¬ng tù nh­ vËy ®èi víi c¸c bµi to¸n cïng lo¹i. 3.2. ThuËt to¸n ph©n côm Tr­íc tiªn chóng ta xÐt bµi to¸n ®¸nh gi¸ c¸c dù ¸n, c¸c ph­¬ng ¸n sau. M« h×nh: • Cho A = {A1, A2, . . . , An} lµ n dù ¸n cÇn ®¸nh gi¸ vµ ph©n líp. • Cho E = {e1, e2, . . . , em} lµ m chuyªn gia- cè vÊn tham gia héi ®ång ®¸nh gi¸. • Cho W = {w(1), w(2), . . . , w(k), . . . , w(m)}, w(k) lµ träng sè cña chuyªn gia ek, 0 ≤ w(k) ≤ 1. Chän t­¬ng øng mét tËp nh·n S b»ng tõ ®Ó c¸c chuyªn gia lùa chän vµ thùc hiÖn ®¸nh gi¸ c¸c dù ¸n. 40 Ch¼ng h¹n cho S = (s1, s2, . . . , s9). ThÕ th× chóng ta cã thÓ chän tõ tiÕng viÖt t­¬ng øng lµ: S =(kh«ng thÓ x¶y ra, kh«ng cã kh¶ n¨ng, rÊt Ýt kh¶ n¨ng, Ýt kh¶ n¨ng, cã thÓ, cã nhiÒu kh¶ n¨ng, rÊt cã kh¶ n¨ng, hoµn toµn cã kh¶ n¨ng, hiÓn nhiªn) [1] . 3.2.1. ThuËt to¸n ph©n côm 1 ThuËt to¸n dùa vµo ®¸nh gi¸ trùc tiÕp cña c¸c chuyªn gia. Mçi chuyªn gia ek cho ®¸nh gi¸ c¸c dù ¸n Ai b»ng mét phÐp ®¸nh gi¸ Pk : A −→ S. Mäi th«ng tin ®¸nh gi¸ lµ {Pk : k = 1, . . . ,m}. ThuËt to¸n 1: B­íc 1: Thu thËp c¸c vect¬ {Pk}. B­íc 2: Dùa vµo vect¬ träng sè W = {w(1), w(2), . . . , w(k), . . . , w(m)}, w(k) lµ träng sè cña chuyªn gia ek, 0 ≤ w(k) ≤ 1, chuÈn ho¸ vect¬ träng sè w ′ (k) = w(k) w0 , ë ®©y w0 = ∑ k w(k). B­íc 3: TÝnh träng sè gép theo tõng nh·n st ®èi víi mçi ph­¬ng ¸n Ai - ®ã chÝnh lµ ®é nhÊt trÝ chän st cña c¶ héi ®ång khi ®¸nh gi¸ Ai. IC(i)[st] = ∑ k {w′(k) : Pk(Ai) = st}. B­íc 4: TÝnh ®é tréi cña mçi ph­¬ng ¸n Ai b»ng to¸n tö LOWA E(i) = Low(S, U(i)), ë ®©y U(i) = [u1, . . . , ut, . . . , uT ], víi ut = IC(i)[st], víi mçi t. B­íc 5: Ph©n côm. Dïng {E(i) : Ai ∈ A} ®Ó ph©n côm tËp ph­¬ng ¸n A thµnh c¸c líp Y1, Y2, . . . , YT = {AiE(i) = st}, víi mçi st ∈ S. Râ rµng A = ⋃ t Yt. Mçi tËp con Yt cã thÓ lµ tËp rçng, ®èi víi nh÷ng tËp Yt kh¸c rçng ta cã thÓ s¾p xÕp cña tËp nh·n S nh­ sau: Yt < Yt′ nÕu t < t ′ . 41 3.2.2. ThuËt to¸n ph©n côm 2 ThuËt to¸n dïng th«ng tin d¹ng ®¸nh gi¸ so s¸nh tõng cÆp cña c¸c chuyªn gia. Mçi chuyªn gia ek cho ®¸nh gi¸ d¹ng so s¸nh dù ¸n Ai víi dù ¸n Aj b»ng mét phÐp ®¸nh gi¸ Pk : A ∗ A −→ S. Mäi th«ng tin ®Ó ph©n côm lµ th«ng tin ®¸nh gi¸ lµ {Pk : k = 1, . . . ,m}. §Ó gän ta kÝ hiÖu Pk(i, j) = Pk(Ai, Aj). Chóng ta sÏ gi¶ thiÕt r»ng Pk(i, i) = sT+1 2 , víi mçi i vµ nÕu Pk(i, j) ≥ sT+1 2 th× Pk(j, i) ≤ sT+1 2 . ThuËt to¸n 2: B­íc 1: Thu nhËp c¸c quan hÖ mê {Pk}. B­íc 2: Dùa vµo vect¬ träng sè W = {w(1), w(2), . . . , w(k), . . . , w(m)}, w(k) lµ träng sè cña chuyªn gia ek, 0 ≤ w(k) ≤ 1, chuÈn ho¸ vect¬ träng sè w ′ (k) = w(k) w0 , ë ®©y w0 = ∑ k w(k). B­íc 3: TÝnh träng sè gép theo tõng nh·n st ®èi víi mçi cÆp ph­¬ng ¸n (Ai, Aj) - ®ã chÝnh lµ ®é nhÊt trÝ chän st trong so s¸nh cña c¶ héi ®ång IC(i, j)[st] = ∑ k {w′(k) : Pk(Ai, Aj) = st}. B­íc 4: TÝnh ®é tréi cña mçi cÆp ph­¬ng ¸n (Ai, Aj) b»ng to¸n tö LOWA E(i, j) = Low(S, U(i, j)), ë ®©y U(i, j) = [u1, . . . , ut, . . . , uT ], víi ut = IC(i, j)[st], víi mçi t. §Ó ý mçi E(i, j) lµ mét ma trËn, nh­ vËy ®ã lµ mét quan hÖ mê cÊp 2- quan hÖ mê nµy ®o ®é tréi t­¬ng ®èi theo ý kiÕn ®· tÝch hîp cña c¶ héi ®ång. B­íc 5: T×m nghiÖm tËp thÓ mê FCS. §©y lµ mét tËp mê lo¹i 2 x¸c ®Þnh trªn cho bëi: FCS = (µFCS(A1)/A1, . . . , µFCS(An)/An). 42 Víi µFCS(Ai) = Low(S, V (i)), vµ V (i) = [v1, . . . , vt, . . . , vT ], víi mçi t, vt = #{j : E(i, j) = st, j 6= i}/m− 1. B­íc 6: Ph©n côm. Dïng µFCS(Ai) : Ai ∈ A} ®Ó ph©n côm tËp ph­¬ng ¸n A thµnh c¸c líp Y1, Y2, . . . , YT , sao cho Yt = {AiµFCS(Ai) = st} víi mçi st ∈ S. Râ rµng A = ⋃ t Yt. Mçi tËp con Yt cã thÓ lµ tËp rçng, ®èi víi nh÷ng tËp Yt kh¸c rçng ta cã thÓ s¾p xÕp theo thø tù s¾p xÕp cña tËp nh·n S nh­ sau: Yt < Yt′ nÕu t < t ′ . 3.3. Bµi to¸n ¸p dông XÐt bµi to¸n [2]: f(x) = (x1 + 2x2 − c3x3 − 1.2x4) −→ min, tho¶ m·n ®iÒu kiÖn 2x1 + x2 + a13x3 + x4 ≤ 12, 2x1 + 2x2 + a24x4 ≤ b2, 3x1 + x2 + 2x3 ≤ 25, xj ≥ 0, j = 1, 2, 3. trong ®ã c¸c c3, a13, a24, b2 lµ c¸c tham sè. Sö dông to¸n tö OWA ®Ó gi¶i bµi to¸n nµy theo c¸c b­íc sau: B­íc 1: §Þnh nghÜa tËp tham sè UP = {c3, a13, a24, b2} B­íc 2: X¸c ®Þnh c¸c kho¶ng gi¸ trÞ víi mçi tham sè, ch¼ng h¹n: ∆(c3) = [3, 5], ∆(a13) = [6, 7], ∆(a24) = [3, 5], ∆(b2) = [20, 24], B­íc 3: Víi mçi tham sè ta thùc hiÖn tÝnh nh­ sau: Ch¼ng h¹n, ta xÐt ∆(a13) = [6, 7]. • Chia ®o¹n [6,7] thµnh c¸c kho¶ng D = {d1, d2, d3, d4, d5} trong ®ã d1 = [6, 6.2], d2 = [6.2, 6.4], d3 = [6.4, 6.6], d4 = [6.6, 6.8], d4 = [6.8, 7]. 43 • Gi¶ sö cho tËp c¸c chuyªn gia E = {e1, e2, e3, e4, e5, e6} víi träng sè e1 e2 e3 e4 e5 e6 0.23 0.21 0.12 0.25 0.15 0.32 B¶ng 3.3 • KÝ hiÖu tËp S = {st, t = 1, . . . , T} lµ tËp h÷u h¹n c¸c nh·n. TËp S cã thÓ hiÓu nh­ c¸c quan hÖ vÒ ng«n ng÷ biÓu thÞ ý kiÕn ®¸nh gi¸ cña c¸c chuyªn gia C Certain HiÓn nhiªn (1, 1, 1, 1) EL Extremely- likely Hoµn toµn cã kh¶ n¨ng (0.93, 0.98, 0.99, 1) ML Most- likely RÊt cã kh¶ n¨ng (0.72, 0.78, 0.92, 0.97) MC Meaningful-chance Cã kh¶ n¨ng (0.58, 0.63, 0.8, 0.86) IM It- may Cã thÓ (0.32, 0.41, 0.58, 0.65) SC Small- chance Cã Ýt kh¶ n¨ng (0.17, 0.22, 0.36, 0.42) VLC Very- slow- chance RÊt Ýt kh¶ n¨ng (0.04, 0.1, 0.18, 0.23) EU Extremely- unlikely Kh«ng cã kh¶ n¨ng (0, 0.01, 0.02, 0.07) I Impossible Kh«ng thÓ x¶y ra (0, 0, 0, 0) B¶ng 3.4 • Gi¶ sö ý kiÕn cña c¸c chuyªn gia lµ: P 1 =  IM V LC SC EU V LC MC IM MC MC MC EL EU IM SC ML EL EL EL IM EL MC EU I EU IM  44 P 2 =  IM EU I SC EU MC IM MC MC MC ML I IM V LC EL EL EL EL IM EL MC EU V LC SC IM  P 3 =  IM V LC ML I ML MC IM MC MC MC EU EU IM I SC EL EL C IM EL EU I ML EU IM  P 4 =  IM V LC I V LC MC MC IM MC MC MC C EU IM EU EL EL EL EL IM EL EU EU SC SC IM  P 5 =  IM SC EL I ML MC IM MC MC MC V LC V LC IM I SC EL EL EL IM EL EU EU MC V LC IM  P 6 =  IM EU ML I I MC IM MC MC MC V LC SC IM SC ML EL EL EL IM EL C SC V LC V LC IM  45 • TÝnh ma trËn E E =  IM V LC IM V LC SC MC IM MC MC MC MC EU IM EU MC EL EL EL IM EL MC EU IM V LC IM  • B©y giê ta tÝnh lêi gi¶i (fuzzy collective solution- FCS) trªn D cña tham sè a13 FCS = {SC/d1,MC/d2, SC/d3, EL/d4, SC/d5} Ta cã thÓ chän kho¶ng d4 víi ®é tréi EL vµ chän kho¶ng d2 víi ®é tréi MC nghÜa lµ ch än (EL, [6.6, 6.8]) vµ (MC, [6.2, 6.4]) cho a13. T­¬ng tù nh­ vËy ta tÝnh cho c¸c tham sè kh¸c. B­íc 4: Gi¶ sö chóng ta chän tËp tham sè UP = {c3, a13, a24, b2} trong ®ã: • c3 (EL, [-4.6,-4.2]), (MC, [-3.8,-3.4]). • a13 (EL, [6.6,6.8]), (MC, [6.2,6.4]). • a24 (ML, [4.2,4.6]), (MC, [3.4,3.8]). • b2 (EL, [22.4,23.2]), (MC, [20.8,21.6]). B­íc 5: KÕt hîp mét sè vect¬ tham sè cña UP. VÝ dô chän vect¬ tham sè (-3.6, 6.3, 3.6, 21.2) cho UP th× ta nhËn ®­îc kÕt qu¶ f(x) = (x1 + 2x2 − 3.6x3 − 1.2x4) −→ min, tho¶ m·n ®iÒu kiÖn 2x1 + x2 + 6.3x3 + x4 ≤ 12, 2x1 + 2x2 + 3.6x4 ≤ 21.2, 3x1 + x2 + 2x3 ≤ 25, xj ≥ 0, j = 1, 2, 3. 46 Lêi gi¶i tèi ­u lµ x∗ = (0, 0, 0.970018, 5.888889) vµ fmin = −10.55873015. Ta cã thÓ nãi r»ng tËp lêi gi¶i lµ MC = min(MC,MC,MC,MC). Ta còng cã thÓ chän vect¬ tham sè (-4.4, 6.7, 4.4, 22.8). T­¬ng tù trªn ta cã: f(x) = (x1 + 2x2 − 4.4x3 − 1.2x4) −→ min, tho¶ m·n ®iÒu kiÖn 2x1 + x2 + 6.7x3 + x4 ≤ 12, 2x1 + 2x2 + 4.4x4 ≤ 22.8, 3x1 + x2 + 2x3 ≤ 25, xj ≥ 0, j = 1, 2, 3. Lêi gi¶i tèi ­u lµ x∗ = (0, 0, 1.017639, 5.181818) vµ fmin = −10.695793788. Ta cã thÓ nãi r»ng tËp lêi gi¶i lµ ML = min(EL,EL,ML,EL). 47 kÕt luËn LuËn v¨n ®· tr×nh bµy vÒ to¸n tö OWA vµ mét sè tÝnh chÊt ®Æc tr­ng cña nã, ®ång thêi còng tr×nh bµy mét sè biÕn thÓ cña to¸n tö OWA. ViÖc chän x¸c ®Þnh c¸c träng sè cña vÐc t¬ träng sè cã ý nghÜa quyÕt ®Þnh ®Õn hiÖu qu¶ cña to¸n tö v× vËy trong luËn v¨n còng tr×nh bµy hai bµi to¸n nh»m tèi ­u vÐc t¬ träng sè theo h­íng cùc ®¹i hay cùc tiÓu vÒ ®é ph©n t¸n khi cho gi¸ trÞ x¸c ®Þnh vÒ ®iÓm nhÊn. Trong phÇn øng dông, luËn v¨n ®· kh¶o s¸t vµ tr×nh bµy mét vµi bµi to¸n cã ý nghÜa thùc tiÔn gåm bµi to¸n vÒ x¸c ®Þnh tiªu chuÈn ®¸nh gi¸ kÕt qu¶ häc tËp, bµi to¸n ph©n côm d÷ liÖu vµ x¸c ®Þnh tham sè trong bµi to¸n tèi ­u th«ng th­êng. C¨n cø môc ®Ých yªu cÇu ®Ò ra nh­ trong tªn gäi cña ®Ò tµi, lÏ ra cßn cÇn nghiªn cøu thªm vÒ mét sè bµi to¸n tèi ­u nhÊt lµ nh÷ng bµi to¸n tèi ­u tæ hîp vµ øng dông to¸n tö OWA ®Ó gi¶i. Song do thêi gian cã h¹n vµ n¨ng lùc cßn h¹n chÕ, luËn v¨n míi chØ b­íc ®Çu kh¶o s¸t ®­îc vµi øng dông cô thÓ nh­ ®· nªu. NÕu cã ®iÒu kiÖn, chóng t«i sÏ tiÕp tôc nghiªn cøu vµ ph¸t triÓn theo h­íng nµy. LuËn v¨n ch¾c ch¾n cßn nhiÒu thiÕu sãt kÝnh mong sù ®ãng gãp ý kiÕn cña tÊt c¶ mäi ng­êi. Xin tr©n träng c¸m ¬n. 48 Tµi liÖu tham kh¶o [1] Bïi C«ng C­êng, HÖ mê, m¹ng n¬ton vµ øng dông, Nhµ xuÊt b¶n Khoa Häc KÜ ThuËt, 2001. [2] Bui Cong Cuong, Nguyen Van Diep, Duong Thanh Long, Bui Duong Hai, A new method for fuzzy parameter programming, using expert's opin- ion and LOWA operator, [3] Peter Majlender, OWA operators with maximal entropy, [4] Jose' M. Merigo' and Anna M. Gil- Lafuente, The induced generalized OWA operator, [5] Robert Fuller, On obtaning OWA operator weights: a short survey of recent developments, 2007 [6] Robert Fuller and Peter Majlender, On obtaning minimal variability OWA operator weights, 2001 [7] M.O'Hagan, Aggregating template or rule antecedents in real- time ex- pert systems with fuzzy set logic in: Proc. 22nd Annual IEEE Asilomar Conf.Signals, Systems, Computer, Pacific Grove, CA,1988. [8] R.R.Yager, Ordered weighted averaging aggregation operators in milti- criteria decision making, IEEE Trans, on Systems, Man and Cybernetics, 1988. [9] R.R.Yager, Families of OWA operators, Fuzzy Sets and Systems, 1993. 49