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

ằ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