xindung_l4mt4nn4t_tr4itim3m95
New Member
Download Luận văn Toán tử Owa trong một số bài toán tối ưu
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
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
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ỳ từng trường hợp 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 ...
Download miễn phí Luận văn Toán tử Owa trong một số bài toán tối ưu
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
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Tóm tắt nội dung:
ằ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ỳ từng trường hợp 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 ...