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
ế s r ề t ọ ũ ứ t
trể t tử t ợ ề t Prtr
r rt r
ụ í ủ ề t ứ ề t tử tí t
q trọ ủ ó ớ ứ ụ tr ột số t ụ tể
ộ ồ ó ở ết
t ệ t
trì ề t tử ù ột số tí t tr ủ
ó ợ ở í ụ ụ tể ũ ột số
ủ t tử
trì tt t tố ộ t ủ trọ
số ự é t trọ số. . . .
trì ột ứ ụ t tử tr ữ t
ụ tể
ố tỏ ò ết s s tớ ế sĩ ũ
t rt t tì ớ ỉ rt ề tr sốt
tờ tự ệ ó trự tế ớ t
ó
ử ờ t tớ t trờ
ọ ọ s ết ò trề
t ề ế tứ ọ tr sốt tờ ọ t t


❈✉è✐ ❝ï♥❣✱ t➠✐ ①✐♥ ❣ö✐ ❧ê✐ ❝➯♠ ➡♥ tí✐ ♥❤÷♥❣ ♥❣➢ê✐ t❤➞♥✱ ♥❤÷♥❣ ♥❣➢ê✐ ❜➵♥
❝ñ❛ t➠✐ ➤➲ ➤é♥❣ ✈✐➟♥ ✈➭ ❝æ ✈ò t➠✐ r✃t ♥❤✐Ò✉ tr♦♥❣ s✉èt t❤ê✐ ❣✐❛♥ ✈õ❛ q✉❛✳
❉♦ ➤✐Ò✉ ❦✐Ö♥ ✈Ò t❤ê✐ ❣✐❛♥ ✈➭ tr×♥❤ ➤é ❝ã ❤➵♥ ♥➟♥ ❜➯♥ ❧✉❐♥ ✈➝♥ ❦❤➠♥❣
tr➳♥❤ ❦❤á✐ ♥❤÷♥❣ t❤✐Õ✉ sãt✳ ❊♠ r✃t ♠♦♥❣ ♥❤❐♥ ➤➢î❝ ♥❤÷♥❣ ý ❦✐Õ♥ ➤ã♥❣ ❣ã♣
q✉ý ❜➳✉ ❝ñ❛ ❝➳❝ q✉ý t❤➬② ❝➠ ✈➭ t♦➭♥ t❤Ó ❝➳❝ ❜➵♥✳
❚❤➳✐ ◆❣✉②➟♥✱ t❤➳♥❣ ✵✾ ♥➝♠ ✷✵✵✾
➜ç ❚❤✉ú ◆✐♥❤

= 1.
ị ĩ tử ớ t trọ số W ột F :
R
n
R ợ ị s ớ ỗ t a = (a
1
, a
2
, . . . , a
n
) R
n
F (a) =
n

j=1
w
j
b
j
,
tr ó b
j
tử ớ tứ j ủ t a.
í ụ sử t
W = (0, 4; 0, 3; 0, 2; 0, 1)
T
a = (0, 7; 1; 0, 3; 0, 6). ó t ó t
b = (1; 0, 7; 0, 6; 0, 3),


1
= 1 w
j
= 0 ớ ọ j = 1 t trọ số ý ệ
W

= (1, 0, . . . , 0)
T
ý ệ t tử ứ ớ trọ số W

F

.
ó F

(a) = F

(a
1
, ..., a
n
) = max
j
(a
j
) t tử ọ số ớ
t (max) ột ủ t tử
ế trọ số w
n
= 1 w

ớ ọ j t trọ số í ệ W
ave
, ý
ệ t tử ứ ớ trọ số W
ave
F
ave
. ó F
ave
(a) =
1
n
n

j=1
a
j
.
ừ ó t tử tr ì ũ ột ủ t tử

ế w
k
= 1 w
j
= 0 ớ ọ j = k t tử F (a
1
, ..., a
n
) = b
k

n
)
T
t trọ số
í t ố ớ ỗ t tử t ó
F

(a
1
, ..., a
n
) F(a
1
, ..., a
n
) F

(a
1
, ..., a
n
),
min(a
i
) F (a
1
, ..., a
n
) max(a
i

2
0 + ... + b
n
1 = b
n
= min(a
i
),
F (a
1
, ..., a
n
) = b
1
w
1
+ b
2
w
2
+ ... + b
n
w
n
=
n

i=1
w
i


i=1
w
i
b
n
= b
n
n

i=1
w
i
= b
n
= min(a
i
),
n

i=1
w
i
b
i

n

i=1
w

∗
 F  F
∗
.
✷
❚Ý♥❤ ❝❤✃t ✶✳✶✳✷✳ ✭❚Ý♥❤ ❤♦➳♥ ✈Þ✮
❚❛ ❝ã
F (a
1
, ..., a
n
) = F(d
1
, ..., d
n
),
✈í✐ ♠ä✐ ❤♦➳♥ ✈Þ d = (d
1
, ..., d
n
) ❝ñ❛ a = (a
1
, ..., a
n
).
❈❤ø♥❣ ♠✐♥❤✳ ❱× sù s➽♣ ①Õ♣ ❧➭ ❞✉② ♥❤✃t ♥➟♥ ✈❡❝t➡ ❝➬♥ tÝ❝❤ ❤î♣ a ✈➭ ❤♦➳♥
✈Þ d ➤Ò✉ ❝ã ❝❤✉♥❣ ✈❡❝t➡ s❛✉ ❦❤✐ s➽♣ ①Õ♣ ❧➭ b = (b
1
, ..., b
n

1
, ..., a
n
) ≥ F(c
1
, ..., c
n
)
❈❤ø♥❣ ♠✐♥❤✳ ●✐➯ sö ✈❡❝t➡ s❛✉ ❦❤✐ s➽♣ ①Õ♣ ❝ñ❛ ✈❡❝t➡ a ❧➭ b = (b
1
, ..., b
n
)✱
✈❡❝t➡ s❛✉ ❦❤✐ s➽♣ ①Õ♣ ❝ñ❛ ✈❡❝t➡ c ❧➭ d = (d
1
, ..., d
n
). ❱× ❤❛✐ ✈❡❝t➡ a, c t❤♦➯
♠➲♥ a
i
≥ c
i
, ♥➟♥ b
i
≥ d
i
✈í✐ ♠ä✐ ✐✳
❚❛ ❝ã
F (a
1

2
+ . . . + d
n
w
n
.
❘â r➭♥❣ F (a
1
, ..., a
n
) ≥ F(c
1
, ..., c
n
).
✷
❚Ý♥❤ ❝❤✃t ✶✳✶✳✹✳ ✭❚Ý♥❤ ❧✉ü ➤➻♥❣✮
◆Õ✉ ✈❡❝t➡ c = (c
1
, . . . , c
n
) ✈í✐ c
1
= c
2
= . . . = c
n
= a t❤× t❛ ❝ã
F (c
1

i
ị ĩ ộ tứ ộ tí tể ủ t W ợ
ở tứ Orness(W ) =
1
n 1
n

i=1
(n i)w
i
.
í ụ ét ột í ụ s
t trọ số s rss






ét t trọ số tì s ớ
tì s ỏ ề ó ứ tỏ ế t ét tộ tí ột
ồ ề tì s ớ ợ ó ộ s
ỉ ứ ộ sử ụ tộ tí
ớ ộ rss ế trọ số ở tì rss ớ trọ số
ở ố tì rss ỏ ế trọ số ề tì rss tế tớ
ĩ ộ rss ị ể

ộ tr ờ t ò t trể t ột số ộ

ị ĩ ộ t ở tứ

.
ộ t ủ ợ s í ệ H

ợ ớ tệ ở r
ớ ọ = 1 tì
H

(W ) =
1
2
1
1

n

i=1
w

i
1

.
ộ t H
R
(W )
ớ ọ R = 1 ị t tứ
H
R
(W ) =
R

(W ).
ị t trọ số
t ý ĩ ệ q ủ t tử ụ tộ
ọ t trọ số W. ỳ t t ụ tể ó ữ ọ
ự r t sẽ ét ột ị t W.

ị t trọ số q ợ tử ờ
ét ột ị ợ ột ợ tử ờ số
ột ệ tr t Q(0) = 0, Q(1) = 1.
ó ớ ỗ i = 1, 2, . . . , n tí w
i
= Q(i/n) Q((i 1)/n). ừ ó t
ó t W.
ị ù ớ t sự t
ột số t ó ét t ữ t
ộ ề ủ s t
ự ọ ớ ỗ ộ tộ ủ ó t
tứ ị ở A
i
(x). ể ệ ề P t
t t s
ị ị ợ từ ờ t số
t
í w
i
t tứ w
i
= Q(i/n) Q((i 1)/n).
í t a tr ó a
i

) Q(
1
3
) = (
2
3
)
2
(
1
3
)
2
=
4
9
.
1
9
=
1
3
,
w
3
= Q(
3
3
) Q(
2

) tr ó u
j
[0, 1] trọ số q trọ

(a
i
[0, 1]) tộ tí t ứ ó tể u
j
sự q trọ ủ
ề ệ tứ a
j
sự t ủ ột ự ọ ố ớ t
tứ
rớ ết t s ế a
j
í ệ b
i
trị ớ t tứ ủ
a
i
. í ệ v
i
sự q trọ ớ ể ó trị ớ t tứ
ó t ó tể ét t (v
i
, b
i
) tr ó b
i
ợ s ế

ố ù t tí trị ết ợ a

=
n

i=1
b
i
w
i
.
í ụ ét ố tợ ớ tộ tí A
1
, A
2
, A
3
, A
4
. q
trọ ớ tộ tí u = (1; 0.6; 0.5; 0.9). ó
sử trị ủ ố tợ tr tộ tí ợ ở

sử ợ từ ỉ ết ợ Q = r
2

ết ử ụ tt t tr t ợ
b
j
v

4
(x) = Q(3/3) Q(2.5/3) = 1 0.69 = 0.31.
ừ ó
F (x) = 0.4 1 + 0.24 0.7 + 0.41 0.6 + 0.31 0.5 = 0.609.
ị t từ ữ ệ
sử ó ột t q st ỗ q st ồ ột ộ n trị
(a
k1
, a
k2
, . . . , a
kn
) ọ t số ột trị ết ợ
ý ệ d
k
. ụ í ủ ú t tì ợ ột t tử ớ
t trọ số W ó tể ì tốt t q trì ết ợ ợ sử
ụ tr t ữ ệ ề ó ĩ tì ột t trọ số W
s ớ t ộ t ữ ệ t t ề ệ ột í
t ó tể ớ ọ q st
F (a
1
, a
2
, . . . , a
n
) = d
k
,
tr ó ỉ r sự ết ợ ủ t số sử ụ W. ý ệ

+ b
k2
w
2
+ . . . + b
kn
w
n
= d
k
,
ớ ọ từ tớ
ử ụ ỹ tt ộ ố rt t tì ột t trọ số
W = (w
1
, w
2
, . . . , w
n
)
T

tố tể ữ s số e
k
e
k
=
1
2
((b

w
i
=
e

i
n

i=1
e

i
, i = 1, . . . , n.
ố ớ t ỳ trị ủ t số
i
tì trọ số
w
i
sẽ tổ ở t tố tể ó r ộ ó
tể ể t t q tế r ộ tì ế

i
ự tể
e
k
=
1
2

b


n
d
k

2
.
ử ụ ộ ố rt t ó tể t ợ t s
ệ t t số

i
(l + 1) =
i
(l) w
i
(l)(b
ki


d
k
)(

d
k
d
k
),
tr ó
i

w
2
(l) + . . . + b
kn
w
n
(l).
trì t
i
tế tụ ế t ợ t số s
ủ ỏ

i
= l
i
(l + 1)
i
(l)l, i = 1, . . . , n.

ột số ế tể ủ
tr ủ t tử ờ t ò ét ột số
ủ ó tỳ tộ ứ ụ ũ tổ qt
sẽ trì ột số tờ
tử
rớ ết ét ột số ệ s
ị ĩ ột Q : [0, 1] [0, 1] ột ợ ờ
ệ í q ế t
(i)Q(0) = 0,
(ii)Q(1) = 1,
(iii)x > y Q(x) Q(y).

ị ĩ ột ợ ờ ở
OW A
Q
: R
n
R tử ề ế
OW A
Q
(a
1
, . . . , a
n
) =
n

i=1
(Q(i/n) Q((i 1)/n))a
(i)
,

tr ó {(1), . . . , (n)} ột ị ủ {1, . . . , n} tứ t ó
a
(i1)
a
(i)
ớ ọ i = {2, . . . , n}, a
(i)
tử ớ tứ ủ t
(a
1

i
w
i
a
(i),
tr ó a
(i)
tử ớ tứ tr t (a
1
, . . . , a
n
), t w
i
ợ
ị ĩ ở
w
i
= W

(

ji
p
(i)
) W

(

ji
p

(i)
,

tr ó w
i
= Q(

ji
p
(i)
) Q(

ji
p
(i)
),
ú ý r t tử ũ ột tổ ợ tế tí ủ
trị
í t ột ộ ờ à ủ t ột
à : (X) [0, 1]
t t ề s
à() = 0, à(X) = 1, ề ệ
A B é t à(A) à(B), tí ệ
ộ ờ t tế t ề ủ tí t ộ ộ ở tí ệ
r ữ tí t ộ ũ ộ ờ
ị ĩ à ột ộ ờ tr í qt ủ
f : X R ợ ị ĩ
n

i=1


.
t tử ó tể ợ ể tị tí qt
ỉ ộ ờ ợ ị ĩ
ó tể ị ĩ ộ tí tể ủ ợ s
ị ĩ ột ợ ờ ộ rss ủ ợ
ị ĩ
Orness(Q) =

1
0
Q(x)d
x
.

tử
ử ụ ệ tổ ợ ồ ủ rrr ộ sự
ị ĩ ột ớ t tử trự tế s rộ t tử ủ
r ụ tr t qết ị t tể tr
q trì tì ứ ụ ị ĩ tr t ớ
ợ ự tứ tỏ r ù ợ ớ ợ ý ó t
sử ụ tứ ớ
S = {s
1
, s
2
, . . . , s
T
} t s t s
1

i
m
i
m1
. . . i
1
.
W = {w
1
, w
2
, . . . , w
m
} t trọ số w
i
[0, 1]

i
w
i
= 1.
ị ĩ t a = {a
1
, a
2
, . . . , a
m
}, W = {w
1
, w

i2
, . . . , w

i(m1)
}, w

j
=
w
j
1 w
im
,
C é tổ ợ ủ (s
j
, s
i
), j i ớ trọ số w
j
> 0, w
i
> 0,
w
j
+ w
i
= 1, C{(w
j
, s
j

2
= 0.3, w
1
= 0.2
Low(a, w) = C{(0.5, s
3
), (0.5, Low((s
2
, s
1
), (0.2/0.5, 0.3/0.5)))}.

▼➭
Low((s
2
, s
1
), (0.2/0.5, 0.3/0.5)) = C{(3/5, s
3
), (2/5, s
2
)} = s
k1
,
k
1
= 1 + round((3/5)(2 − 1)) = 1 + 1 = 2.
❉♦ ✈❐②
Low(a, w) = C{(0.5, s
3

λ
j

1
λ
,
tr♦♥❣ ➤ã
n

j=1
w
j
= 1, w
j
∈ [0, 1], b
j
❧➭ ♣❤➬♥ tö ❧í♥ t❤ø ❥ ❝ñ❛ t❐♣ a
i
, ✈➭
λ ∈ (−∞, ∞) ❧➭ t❤❛♠ sè
➜Þ♥❤ ♥❣❤Ü❛ ✶✳✸✳✶✵✳ ▼ét ❚♦➳♥ tö ■●❖❲❆ ♥ ❝❤✐Ò✉ ❧➭ ♠ét ➳♥❤ ①➵
IGOW A : R
n
−→ R
❧✐➟♥ ❦Õt ❜ë✐ ❝➳❝ ✈❡❝t➡ trä♥❣ sè ♥ ❝❤✐Ò✉ ✈➭
IGOW A((u
1
, a
1
), . . . , (u

❝ñ❛ ❝➷♣ ■●❖❲❆ (u
i
, a
i
) ❧í♥
t❤ø ❥✱ u
i
❜✐Õ♥ t❤ø tù ❝➯♠ s✐♥❤✱ a
i
❧➭ ❜✐Õ♥ ➤è✐ sè✱ λ ∈ (−∞, ∞) ❧➭ t❤❛♠ sè
❚♦➳♥ tö ■❖❲❆ ➤➢î❝ ❣✐í✐ t❤✐Ö✉ ❜ë✐ ❨❛❣❡r ✈➭ ❧➭ ♠ét ♠ë ré♥❣ ❝ñ❛ t♦➳♥ tö
❖❲❆✳ ý ♥❣❤Ü❛ ❦❤➳❝ ❜✐Öt ❝ñ❛ t♦➳♥ tö ♥➭② ❦❤➠♥❣ ♣❤➯✐ ❧➭ ✈✐Ö❝ ♣❤➳t tr✐Ó♥ ✈í✐
❣✐➳ trÞ ❝ñ❛ ➤è✐ sè a
i
♠➭ ❧➭ ✈✐Ö❝ ♣❤➳t tr✐Ó♥ t❤ø tù ❜✐Õ♥ ❝➯♠ s✐♥❤✳
➜Þ♥❤ ♥❣❤Ü❛ ✶✳✸✳✶✶✳ ❚♦➳♥ tö ■❖❲❆ ♥ ❝❤✐Ò✉ ❧➭ ♠ét ➳♥❤ ①➵ IOW A : R
n
−→
R ➤➢î❝ ❧✐➟♥ ❦Õt ❜ë✐ ❝➳❝ ✈❡❝t➡ trä♥❣ sè ♥ ❝❤✐Ò✉ ✈➭
IGOW A((u
1
, a
1
), . . . , (u
n
, a
n
)) =

n

✶✾