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

Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn ĐẠ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 Mục lục Mở đầu 2 Chương 1. Toán tử OWA 4 1.1. Toán tử OWA . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Cách xác định vectơ trọng số w . . . . . . . . . . . . . . . 9 1.3. Một số biến thể của OWA . . . . . . . . . . . . . . . . . . 14 Chương 2. Tối ưu các trọng số 20 2.1. Độ phân tán cực đại . . . . . . . . . . . . . . . . . . . . . . 20 2.2. Độ phân tán cực tiểu . . . . . . . . . . . . . . . . . . . . . 24 Chương 3. Một số ứng dụng của toán tử OWA 36 3.1. Ra quyết định dựa trên độ quan trọng . . . . . . . . . . . . 36 3.2. Thuật toán phân cụm . . . . . . . . . . . . . . . . . . . . . 40 3.3. Bài toán áp dụng . . . . . . . . . . . . . . . . . . . . . . . 43 1 Mở đầu Toán tử trung bình trọng số có sắp xếp (Ordered Weighted Averaging operater- OWA) được Yager giới thiệu năm 1988 là một công cụ hữu ích nhằm tích hợp các thuộc tính của đối tượng theo các tiêu chí khác nhau. Toán tử này đã được sử dụng trong nhiều dạng bài toán và đã thu được những kết quả tốt [7] [8]. Tiếp sau Yager, nhiều nhà toán học khác cũng đã nghiên cứu, phát triển toán tử OWA và đạt được nhiều thành công như: O'Hagan [6], Perter Majlender [3], Robert Fuller [4], .... Mục đích của đề tài này là nghiên cứu về toán tử OWA, các tính chất quan trọng của nó và bước đầu ứng dụng trong một số bài toán cụ thể. Nội dung bản luận văn gồm có phần mở đầu, ba chương, phần kết luận và tài liệu tham khảo. Chương 1 trình bày về toán tử OWA cùng một số tính chất đặc trưng của nó và được dẫn giải bởi các ví dụ cụ thể. Chương này cũng nêu một số dạng khác của toán tử OWA. Chương 2 trình bày các thuật toán nhằm tối ưu độ phân tán của các trọng số khi xây dựng véc tơ trọng số. . . . Chương 3 trình bày một vài ứng dụng toán tử OWA trong những bài toán cụ thể. Em mong muốn bày tỏ lòng biết ơn sâu sắc tới Thầy giáo Tiến sĩ Vũ Mạnh Xuân, thầy đã rất tận tình hướng dẫn, chỉ bảo em rất nhiều trong suốt thời gian em thực hiện khóa luận và trực tiếp hướng dẫn em hoàn thành khóa luận này. Em xin gửi lời cảm ơn chân thành tới các thầy giáo, cô giáo trường Đại học Khoa học, khoa Toán - Tin và các giáo sư đã hết lòng giảng dạy, truyền đạt cho em nhiều kiến thức khoa học trong suốt thời gian em học tập tại đây. 2 Cuối cùng, tôi xin gửi lời cảm ơn tới những người thân, những người bạn của tôi đã động viên và cổ vũ tôi rất nhiều trong suốt thời gian vừa qua. Do điều kiện về thời gian và trình độ có hạn nên bản luận văn không tránh khỏi những thiếu sót. Em rất mong nhận được những ý kiến đóng góp quý báu của các quý thầy cô và toàn thể các bạn. Thái Nguyên, tháng 09 năm 2009 Đỗ Thuỳ Ninh 3 Chương 1 Toán tử OWA Quá trình tích hợp thông tin xuất hiện trong rất nhiều ứng dụng của các hệ tri thức chẳng hạn như trong mạng nơron, điều khiển mờ, hệ chuyên gia và hệ trợ giúp quyết định, đặc biệt trong các bài toán phải xử lý những thông tin bất định. Năm 1988, R.Yager [8] [9] đã định nghĩa toán tử trung bình trọng số có sắp xếp (Ordered Weighted Averaging operator) viết tắt là OWA nhằm cung cấp một phương pháp kết hợp các thuộc tính gắn với sự thoả mãn những tiêu chí nào đó. Chương này trình bày về toán tử OWA, các tính chất cơ bản và một số dạng khác của toán tử này. 1.1. Toán tử OWA 1.1.1. Khái niệm Đị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) (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