Luận văn: TOÁN TỬ OWA TRONG MỘT SỐ BÀI TOÁN TỐI ƯU

Chia sẻ: Qsczaxewd Qsczaxewd | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

150
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn: 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 trng 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è Mét vect¬ §Þnh nghÜa 1.1.1. n cña kh«ng gian n chiÒu nÕu 0 ≤ wi ≤ 1 víi mçi i = 1, ..., n vµ wj = 1. j =1 To¸n tö OWA víi vect¬ träng sè W lµ mét ¸nh x¹ F : §Þnh nghÜa 1.1.2. Rn −→ R ®îc x¸c ®Þnh nh sau: Víi mçi vect¬ a = (a1 , a2 , . . . , an ) ∈ Rn n F (a) = wj bj , j =1 trong ®ã bj lµ phÇn tö lín thø j cña vect¬ a. Gi¶ sö cho vect¬ VÝ dô 1.1.1. 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: 4 F (a) = 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 = 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 ∗ . lµ 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 = 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 1 hiÖu to¸n tö OWA øng víi träng sè Wave lµ Fave . Ta cã Fave (a) = aj . 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 = 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 = n+1 . NÕu 2 2 1 NÕu n lµ ch½n lÊy w n = w n +1 = vµ ®Æt wj = 0 cho tÊt c¶ c¸c sè h¹ng 2 2 2 kh¸c. 1.1.3. Mét sè tÝnh chÊt W = (w1 , ..., wn )T lµ vect¬ träng sè. Sau ®©y ta ®Òu gi¶ thiÕt §èi víi mçi to¸n tö OWA, ta cã: TÝnh chÊt 1.1.1. F ∗ (a1 , ..., an ), F∗ (a1 , ..., an ) F (a1 , ..., an ) ⇔ min(ai ) F (a1 , ..., an ) 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 Gi¶ sö to¸n tö OWA víi vect¬ träng sè Chøng minh. ®· 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 ) = b1 0 + b2 0 + ... + bn 1 = bn = min(ai ), n 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 n n wi bi ≥ wi bn = bn wi = bn = min(ai ), i=1 i=1 i=1 n n n wi bi ≤ wi b1 = b1 wi = b1 = max(ai ). i=1 i=1 i=1 6
Tõ ®ã n F ∗. max(ai ) hay F∗ min(ai ) wi bi F i=1 2 (TÝnh ho¸n vÞ) TÝnh chÊt 1.1.2. Ta cã F (a1 , ..., an ) = F (d1 , ..., dn ), víi mäi ho¸n 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 Chøng minh. 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 ®¬n ®iÖu) TÝnh chÊt 1.1.3. 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 ) Gi¶ sö vect¬ sau khi s¾p xÕp cña vect¬ a lµ b = (b1 , ..., bn ), Chøng minh. 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 ) = 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 luü ®¼ng) TÝnh chÊt 1.1.4. NÕu vect¬ c = (c1 , . . . , cn ) víi c1 = c2 = . . . = cn = a th× ta cã F (c1 , . . . , cn ) = a. 7
Ta cã Chøng minh. F (c1 , . . . , cn ) = a.w1 + ... + a.wn = a.(w1 + ... + wn ) = a.1 = a 2 1.1.4. §Æc trng 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 trng ho¸ c¸c to¸n tö OWA [1]. §é ®o thø nhÊt lµ cña vect¬ W ®îc x¸c §Þnh nghÜa 1.1.3. ®é ®o ph©n t¸n n ®Þnh bëi c«ng thøc: Disp(W ) = − wi ln wi i=1 §é ®o thø hai lµ cña vect¬ W ®îc cho §Þnh nghÜa 1.1.4. ®é ®o tÝnh tuyÓn n 1 bëi c«ng thøc: (n − i)wi . Orness(W ) = n−1 i=1 Ta xÐt mét vÝ dô sau VÝ dô 1.1.2. 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 Ta thÊy c¸c träng sè nµy cµng gÇn nhau th× Disp cµng lín, cµng NhËn xÐt: 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, cho bëi c«ng thøc: §Þnh nghÜa 1.1.5. §é ph©n t¸n Shannon n Hs (W ) = − wi log2 wi . i=1 b, Hα (còng ®îc gäi lµ ®é ph©n t¸n cña α.) §é ph©n t¸n RÐnyi's Víi mäi sè thùc α = 1 th×: n 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 β = 1 th×: n 1 β wi − 1 . Hβ (W ) = 21−β −1 i=1 d, HR (W ) §é ph©n t¸n R- chuÈn Víi mäi R = 1 vµ x¸c ®Þnh theo c«ng thøc: n R 1 R 1− HR (W ) = wi . R R−1 i=1 Sö dông c«ng thøc tÝnh giíi h¹n ta cã: NhËn xÐt: Hs (W ) = lim Hα (W ) = lim Hβ (W ) = lim HR (W ). α→1 R→1 β →1 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. Q(i) = i2 , vµ n = 3. Cho lîng tö mê Q ®îc x¸c ®Þnh VÝ dô 1.2.1. Khi ®ã vect¬ träng sè W x¸c ®Þnh nh sau: 1 0 1 1 w1 = Q( ) − Q( ) = ( )2 − 0 = , 3 3 3 9 2 1 22 12 41 1 w2 = Q( ) − Q( ) = ( ) − ( ) = . = , 3 3 3 3 99 3 3 2 2 45 w3 = Q( ) − Q( ) = (1)2 − ( )2 = 1 − = . 3 3 3 99 115 Ta cã vect¬ träng sè W = ( , , ). 939 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¸cai . 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, i n Si = v k , T = Sn = vk . k =1 k =1 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. n ∗ Cuèi cïng ta tÝnh gi¸ trÞ kÕt hîp a= bi wi . i=1 XÐt ®èi tîng x víi 4 thuéc tÝnh A1 , A2 , A3 , A4 . C¸c quan VÝ dô 1.2.2. 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). Q = r2 (ch¼ng h¹n nh lµ 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: 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 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 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 = , i = 1, . . . , n. n eλi 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 − dk ek = bk 1 n + bk 2 n + . . . + bkn n . 2 λ1 λ2 λn e e e 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 − dk )(dk − 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 eλi (l) i=1 cña wi sau lÇn lÆp thø l vµ dk = 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: Mét hµm Q : [0, 1] −→ [0, 1] lµ mét Lîng ho¸ mê kh«ng §Þnh nghÜa 1.3.1. nÕu tho¶ m·n: gi¶m ®¬n ®iÖu chÝnh quy (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 = 0, (ii)Qn (1) = 1, Qn (x) = 0, x = 1. W M : Rn −→ R Cho P lµ mét vect¬ n chiÒu th× ¸nh x¹ §Þnh nghÜa 1.3.2. lµ mét n chiÒu nÕu W M p (a1 , . . . , an ) = p i ai . Träng sè 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. Cho Q lµ mét lîng ho¸ mê kh«ng gi¶m, ¸nh x¹ cho bëi §Þnh nghÜa 1.3.3. OW AQ : Rn −→ R lµ nÕu To¸n tö OWA n chiÒu n (Q(i/n) − Q((i − 1)/n))aσ(i) , OW AQ (a1 , . . . , an ) = 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 §Þnh nghÜa to¸n tö OWA trong kh«ng gian 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. §Æt P vµ W lµ hai vect¬ träng sè cña kh«ng gian n §Þnh nghÜa 1.3.4. W OW A : Rn −→ R lµ chiÒu, ¸nh x¹ ( 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 ) = 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: wi = W ∗ ( pσ(i) ) − W ∗ ( pσ(i) ), j ≤i j ≤i W ∗ lµ hµm ®¬n ®iÖu t¨ng trong kho¶ng (i/n, víi 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). Cho Q lµ mét lîng ho¸ mê kh«ng gi¶m, P lµ mét vect¬ §Þnh nghÜa 1.3.5. W OW A : Rn −→ R lµ mét träng sè n chiÒu, ¸nh x¹ n to¸n tö WOWA chiÒu nÕu: W OW Ap,Q (a1 , . . . , an ) = wi aσ(i) , i 15
trong ®ã pσ(i) ) − Q( wi = Q( pσ(i) ), j ≤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Þ. Mét ®é ®o mê µ cña tËp X lµ mét hµm TÝnh chÊt 1.3.1. µ : ρ(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ê. Cho µ lµ mét ®é ®o mê trong X. cña §Þnh nghÜa 1.3.6. TÝch ph©n Choquet hµm f : X −→ R ®îc ®Þnh nghÜa: n (f (xs(i) ) − f (xs(i−1) ))µ(As(i) ), i=1 trong ®ã 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) ) = ∅. As(i) 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 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: Cho mét lîng ho¸ mê Q, ®îc §Þnh nghÜa 1.3.7. §é ®o Orness cña Q ®Þnh nghÜa: 1 Orness(Q) = Q(x)dx . 0 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Þ trongS. 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 . Cho W = {w1 , w2 , . . . , wm } lµ vect¬ träng sè, wi ∈ [0, 1] vµ i wi = 1. Cho tËp a = {a1 , a2 , . . . , am }, W = {w1 , w2 , . . . , wm } §Þnh nghÜa 1.3.8. lµ vect¬ träng sè, lµ mét tæ hîp thùc cña vect¬ a víi träng to¸n tö LOWA 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 ))}, wj ë ®©y a = {ai(m−1) , . . . , ai1 }, w = {wi1 , wi2 , . . . , wi(m−1) }, 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)). S nhËn c¸c gi¸ trÞ trªn R1 th× to¸n tö Low cho Râ rµng nÕu tËp NhËn xÐt: 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). Cho a = (s1 , s2 , s3 ), w = (0.2; 0.3; 0.5). VÝ dô 1.3.1. 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]. n chiÒu lµ mét ¸nh x¹ §Þnh nghÜa 1.3.9. To¸n tö GOWA GOW A : Rn −→ R liªn kÕt víi vect¬ träng sè W vµ n 1 wj bλ GOW A(a1 , . . . , an ) = , λ j j =1 n trong ®ã 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è Mét n chiÒu lµ mét ¸nh x¹ §Þnh nghÜa 1.3.10. To¸n tö IGOWA IGOW A : Rn −→ R liªn kÕt bëi c¸c vect¬ träng sè n chiÒu vµ n 1 wj bλ IGOW A((u1 , a1 ), . . . , (un , an )) = , λ j j =1 18
n trong ®ã 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ö ý 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 OWA. gi¸ trÞ cña ®èi sè ai mµ lµ viÖc ph¸t triÓn thø tù biÕn c¶m sinh. IOW A : Rn −→ n chiÒu lµ mét ¸nh x¹ §Þnh nghÜa 1.3.11. To¸n tö IOWA R ®îc liªn kÕt bëi c¸c vect¬ träng sè n chiÒu vµ n IGOW A((u1 , a1 ), . . . , (un , an )) = wj bj , j =1 n trong ®ã 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