Toán tử Owa trong một số bài toán tối ưu

. . . . . . . . . . . . . . . 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 Định nghĩa 1.1.1. Một vectơW = (w1, w2, . . . , wn) T là một vectơ trọng số của không gian n chiều nếu 0 ≤ wi ≤ 1 với mỗi i = 1, ..., n và n∑ j=1 wj = 1. Định nghĩa 1.1.2. Toán tử OWA với vectơ trọng số 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 F (a) = n∑ j=1 wjbj, trong đó bj là phần tử lớn thứ j của vectơ a. Ví dụ 1.1.1. 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∑ j=1 wjbj = 0, 4.1 + 0, 3.0, 7 + 0, 2.0, 6 + 0, 1.0, 3 = 0, 76. ý 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ủ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._.