ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ HUỆ

BÀI TOÁN SẮP XẾP MỜ DÙNG
TRONG ĐÁNH GIÁ THEO HƢỚNG
TIẾP CẬN ĐẠI SỐ GIA TỬ

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH


NGƢỜI HƢỚNG DẪN KHOA HỌC
TS.Trần Thái Sơn Thái Nguyên - 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CAM ĐOAN
Tên tôi là : Nguyễn Thị Huệ
Sinh ngày 12 tháng 12 năm 1983
Học viên cao học lớp: K9B- trường Đại học CNTT&TT Thái Nguyên
Xin cam đoan : Đề tài luận văn“Bài toán sắp xếp mờ dùng trong
đánh giá theo hướng tiếp cận đại số gia tử” do TS.Trần Thái Sơn hướng
dẫn là công trình nghiên cứu của riêng tôi. Tất cả tài liệu tham khảo đều có
nguồn gốc, xuất xứ rõ ràng.
Tôi xin cam đoan tất cả những nội dung trong luận văn đúng như nội
dung trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi xin hoàn
toàn chịu trách nhiệm trước Hội đồng khoa học và trước pháp luật.

Thái Nguyên, ngày 15 tháng 9 năm 2012
Ngƣời cam đoan Nguyễn Thị Huệ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

PHẦN MỞ ĐẦU…………………………………………………………….1
CHƢƠNG 1. NHỮNG KIẾN THỨC CƠ BẢN VỀ LÝ THUYẾT TẬP
MỜ
1.1. Kiến thức cơ sở về tập mờ……………………………………………… 3
1.2. Lôgic mờ …………………………………………………………………8
1.3. Biến ngôn ngữ………………………………………………………… 13
1.4. Bài toán sắp xếp mờ …………………………………………………….14
1.4.1. Bài toán kết nhập……………………………………………………14
1.4.2. Các phương pháp giải bài toán sắp xếp mờ…………………………15
1.4.2.1. Phương pháp tính toán ngôn ngữ dựa trên nguyên lý mở rộng
của tập mờ …………………………………………………………… 15
1.4.2.2. Phương pháp tính toán trên các ký hiệu ngôn ngữ ……… 16
1.3.2.3. Phương pháp tính toán ngôn ngữ dựa trên biểu diễn dữ liệu bộ 2
………………………………………………………………………… 17
1.4.2.4. Phương pháp tính toán ngôn ngữ dựa trên biểu diễn dữ liệu bộ 3
18
CHƢƠNG 2. NHỮNG KIẾN THỨC CƠ BẢN VỀ ĐẠI SỐ GIA TỬ
2.1. Đại số gia tử ……………………………………………………………19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii

2.2. Định nghĩa đại số gia tử ……………………………………………… 21
2.3. Các định lý …………………………………………………………… 23
2.4. Các đại lương đo trên đại số gia tử …………………………………… 25
2.5. Một số tính chất của quan hệ thứ tự trong đại số gia tử ……………… 27
CHƢƠNG 3. PHƢƠNG PHÁP GIẢI BÀI TOÁN SẮP XẾP MỜ THEO
CÁCH TIẾP CẬN CỦA ĐẠI SỐ GIA TỬ
3.1. Thuật toán giải bài toán sắp xếp mờ dùng trong đánh giá theo hướng tiếp
cận của đại số gia tử………………………………………………………….33
3.1.1.Bài toán…………………………………………………………… 33

Đại số gia tử tuyến tính đầy đủ
W
Phần tử trung hòa trong đại số gia tử
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iv DANH MỤC CÁC HÌNH ẢNH

Hình
Mô tả
Hình 1
Đồ thị biểu diễn hàm thuộc của tập mờ già (old)
Hình 2
Biểu diễn bộ 2
Hình 3
Độ đo tính mờ của biến TRUTH
Hình 4
Giao diện của chương trình
Hình 5
Kết quả thực hiện chương trình thử nghiệm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1

PHẦN MỞ ĐẦU
Trong đời sống hàng ngày hay trong công việc giảng dạy, chúng ta
thường xuyên gặp phải yêu cầu phải lựa chọn, đánh giá. Chẳng hạn, đánh giá

sắp xếp mờ dùng trong đánh giá theo hƣớng tiếp cận đại số gia tử”
Luận văn có bố cục như sau:
Chƣơng 1: Những kiến thức cơ bản về lý thuyết tập mờ
Trong chương này trình bày những kiến thức cơ bản về lý thuyết tập
mờ, bài toán sắp xếp mờ và một số phương pháp giải bài toán sắp xếp mờ.
Chƣơng 2: Những kiến thức cơ bản về đại số gia tử
Trong chương này trình bày khái niệm về đại số gia tử, các định lý, các
đại lương đo trên đại số gia tử, một số tính chất của quan hệ thứ tự trong đại
số gia tử.
Chƣơng 3 : Phƣơng pháp giải bài toán sắp xếp mờ theo cách tiếp cận của
đại số gia tử.
Trong chương này trình bày bài toán, thuật toán và cách giải bài toán
sắp xếp mờ theo hướng tiếp cận của đại số gia tử bằng cách sử dụng quan hệ
thứ tự của các từ trong đại số gia tử.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3

Chƣơng 1
NHỮNG KIẾN THỨC CƠ BẢN VỀ LÝ THUYẾT TẬP MỜ
1.1. Kiến thức cơ sở về tập mờ
Là người khởi xướng cho lý thuyết tập mờ, L. A. Zadeh đã có rất nhiều
nghiên cứu mở đường cho sự phát triển và ứng dụng [14]. Ý tưởng nổi bật của
Zadeh là từ những khái niệm trừu tượng về ngữ nghĩa của thông tin mờ,
không chắc chắn như trẻ-già, nhanh-chậm, cao-thấp,… Ông đã tìm cách biểu
diễn chúng bằng một khái niệm toán học, được gọi là tập mờ và được định
nghĩa như sau.
Định nghĩa 1. [14] Cho một tập vũ trụ U với các phần tử ký hiệu bởi x,
U={x}. Một tập mờ A trên U là tập được đặc trưng bởi một hàm


[0,1]}, một không gian tương đối
giàu về cấu trúc tính toán mà nhiều nhà nghiên cứu đã sử dụng cho việc mô
phỏng các phương pháp suy luận của con người.
Chúng ta có thể biểu diễn tập mờ bằng các cách sau, tùy theo tập U là
hữu hạn, đếm được hay vô hạn liên tục:
- Trường hợp U hữu hạn, U={u
i
: 1 i  n}, ta có thể viết
A =

A
(u
1
)/u
1
+

A
(u
2
)/u
2
+ … +

A
(u
n
)/u
n
= 


, được xác định như sau :
A

= {u  U :

A
(u)}.
Tập A

còn gọi là tập mức  của A.
Định nghĩa 3. [1] Cho một tập mờ A trên tập vũ trụ U,
i) Giá của tập mờ A, ký hiệu support(A), là tập con của U trên đó

A
(u)0, tức là support(A) = {u  U :

A
(u)0}.
ii) Độ cao của tập mờ A, ký hiệu high(A), là cận trên đúng của hàm
thuộc

A
(u) trên U, tức là high(A) = sup{

A
(u) : uU}.
iii) A được gọi là tập mờ chuẩn nếu high(A)=1. Ngược lại gọi là tập
mờ dưới chuẩn.
iv) Lõi của tập mờ A, ký hiệu core(A), là một tập con của U được

ii) Lực lượng mờ hay bản số mờ của tập mờ A, ký hiệu card(A), là
một tập mờ trên tập các số nguyên không âm N, được xác định như sau:
card(A) = 
N


card(A)
(n)dn , trong đó,

card(A)
(n) được xác
định theo công thức sau, với |A

| là lực lượng tập mức A

,


card(A)
(n) = sup{t[0,1] : |A

| = n}.
Ví dụ 1. Cho tập vũ trụ chỉ tuổi tính chẵn năm U={u : 0 u 120}, A là
một tập mờ chỉ tuổi già (old) được xác định bởi hàm thuộc sau (hình 1):

Khi đó tập mức =0.5 của A là A
0.5
= {u : 66 u 120} ;
support(A) = {u : 61 u 120} ; high(A) = 1.01
-1


A
(u),

B
(u)), u  U,

A~
(u) = 1-

A
(u), u  U.
21
60
6
0 [0,60]
()
(1 ( ) ) [61,120]
old
u
u
u
u








tương ứng là hai khái niệm mờ về năng lực học giỏi và học kém, với hàm
thuộc được cho dưới dạng bảng như sau:
uU
1
2
3
4
5
6
7
8
9
10

G
(u)
0.0
0.0
0.0
0.1
0.3
0.5
0.7
0.9
1.0
1.0

K
(u)
1.0

0.5
0.7
0.9
1.0
1.0

GK
(u)
0.0
0.0
0.0
0.1
0.3
0.2
0.0
0.0
0.0
0.0

G~
(u)
1.0
1.0
1.0
0.9
0.7
0.5
0.3
0.1
0.0


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7

Quan hệ mờ cũng có các phép tính cơ bản như trên tập mờ vì bản thân nó
cũng là tập mờ. Ngoài ra, quan hệ mờ có những phép tính đặc thù riêng mà
trên tập mờ không có, đó là phép hợp thành dưới đây.
Định nghĩa 7. [1] Cho R là một quan hệ mờ trên UV và S là quan hệ
mờ trên VW. Khi đó, phép hợp thành của hai quan hệ này là một quan hệ
trên UW, được ký hiệu là RS và được định nghĩa như sau:
RS = 
vV
[

R
(u,v)

S
(v,w)]/(u,w)
Trong đó  là một phép tính 2 ngôi trong [0,1] có tính giao hoán, kết hợp
và phân phối đối với phép max . Nếu  là phép min , thì ta có phép hợp
thành max-min, nếu  là phép nhân số học thì ta có phép hợp thành max-
product.
Ví dụ 3. Cho U = {u
1
, u
2
, u
3
}, V = {v




12
1
2
0.2 0.8
0.7 0.1
ww
v
S
v




12
1
2
3
0.7 1
0.3 0.8
0.7 0.7
ww
u
R S u
u




Cùng với khái niệm biến ngôn ngữ, L. A. Zadeh đã phát triển lôgic mờ
mà các giá trị chân lý nhận trong T(Truth) = {true, very true, more false,
possible false, very very false,…}, tập các giá trị của biến ngôn ngữ Truth. Khi
đó, một mệnh đề dạng “X is A”, với A là một khái niệm mờ, sẽ có giá trị chân
lý thuộc T(Truth) và được biểu thị bởi một tập mờ có hàm thuộc

A
trên không
gian tham chiếu U.
Lý thuyết tập mờ là cơ sở toán học cho việc phát triển các phương pháp
mô phỏng lập luận của con người. Về nguyên tắc, vấn đề tư duy, lập luận của
con người rất phức tạp và do đó không thể sử dụng một cấu trúc toán học duy
nhất để mô phỏng. Vì vậy, mục tiêu của chúng ta là càng xây dựng được nhiều
cấu trúc đại số các tập mờ càng tốt để linh hoạt trong tiếp cận các vần đề ứng
dụng. Ở đây, chúng ta sẽ định nghĩa một họ các cặp đối ngẫu t-norm và t-
conorm cùng với phép phủ định làm cơ sở cho lôgic mờ và lập luận xấp xỉ.
Định nghĩa 8 [1] Một hàm 2-biến T : [0,1][0,1]  [0,1] được gọi là
phép t-norm nếu nó thỏa các tính chất sau với a,a’,b,c [0,1]:
i) Tính chất điều kiện biên: T(a,1) = a
ii) Tính giao hoán: T(a,b) = T(b,a)
iii) Tính đơn điệu: a  a’  T(a,b)  T(a’,b)
iv) Tính kết hợp: T(a,T(b,c)) = T(T(a,b),c)
Ngoài ra, một số tính chất khác cần đòi hỏi phải có trong nhiều ứng dụng
đối với phép t-norm bao gồm:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9

v) Tính liên tục: T là hàm hai biến liên tục
vi) Tính lũy đẳng dưới: T(a,b) < a
vii) Tính đơn điệu chặt: a  a’ và b  b’  T(a,a’) <

P
(a,b) = a.b
T
L
(a,b) = max{0,a+b-1}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10 *
khi 1
( , ) khi 1
0 khi 1& 1
ab
T a b b a
ab









S
M
(a,b) = max{a,b}
S
P

A
và

B
trên không gian
tham chiếu U và V thì mệnh đề mờ “X is A and B” có hàm thuộc biểu thị giá
trị chân lý là

AB
= T(

A
,

B
), với T là một t-norm nào đó. Tương tự, mệnh đề
“X is A or B” có hàm thuộc là

AB
= S(

A
,

B
) và mệnh đề “X is not A” có hàm
thuộc là

~A
= N(

vii) Tính chất về điều kiện giới nội
I(x,y) = 1 nếu và chỉ nếu x  y
viii) Tính chất khái quát hóa của phép kéo theo kinh điển
I(x,y) = I(N(y),N(x)), trong đó N là phép phủ
định
ix) I là hàm liên tục theo cả hai biến.
Rõ ràng mệnh đề điều kiện ở dạng “If X is A then Y is B” thể hiện mối
quan hệ giữa hai khái niệm mờ A và B. Vì vậy, chúng cảm sinh một quan hệ
mờ R thể hiện bởi một tập mờ trên không gian tích Đề-Các UV được xác
định bởi hàm thuộc thông qua một phép kéo theo được chọn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12

Ví dụ 5. Một số dạng phép kéo theo thường dùng
Mamdani
I(x,y) = min{x,y}
Dạng khái quát từ phép kéo theo kinh điển
I(x,y) = S(N(x),y), hoặc
I(x,y) = S(N(x),T(x,y)), hoặc
I(x,y) = S(T(N(x),N(y)),y), với T, S và N là các phép
t-norm, t-conorm và phép phủ định.
Reichenbach
I(x,y) = 1-x+x.y
Lukasiewicz
I(x,y) = min{1, 1-x+y}.
Định lý sau đây cho chúng ta xem xét liệu phép kéo theo như thế nào sẽ
thỏa mãn tất cả các tính chất trong định nghĩa 12.
Định lý 1. [1] Một hàm 2-biến I : [0,1]
2
 [0,1] thỏa các tính chất từ i)

bằng tập mờ trên U cho các từ ngôn ngữ trong T(X).
Ví dụ 6 Cho X là biến ngôn ngữ có tên AGE, miền tham chiếu của X là
U=[0,120]. Tập các giá trị ngôn ngữ T(AGE)={very old, old, possible old, less
old, less young, quite young, more young,…}. Chẳng hạn với giá trị ngôn ngữ
old, quy tắc gán ngữ nghĩa M cho old bằng tập mờ cho bởi ví dụ 1
M(old) = {(u,

old
(u)) : u[0,120]}.
Chúng ta thấy rằng một biến ngôn ngữ được cấu trúc theo hướng mà
trong đó có hai quy tắc cơ bản. Thứ nhất là quy tắc cú pháp, qui định cách
thức để sinh các giá trị ngôn ngữ. Thứ hai là quy tắc ngữ nghĩa, qui định thủ
tục tính toán ngữ nghĩa của các giá trị ngôn ngữ. Ngoài các giá trị sinh nguyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14

thủy, các giá trị ngôn ngữ có thể gồm các từ liên kết như and, or, not,… và các
gia tử ngôn ngữ như very, possible, less, quite, more,….Zadeh cũng nêu ra
một vài thí dụ về cách sinh ra các hàm thuộc từ các hàm thuộc đã có như nếu
A là nhãn ngôn ngữ mờ có hàm thuộc là μ
A
thì veryA có hàm thuộc là (μ
A
)
2

còn lessA có hàm thuộc là căn bặc hai của μ
A

Trong thực tế có nhiều biến ngôn ngữ khác nhau về giá trị sinh nguyên

ij
là ý kiến đánh giá của chuyên gia j về phương án A
i
.
Một yêu cầu tự nhiên là cần định giá ý kiến tổng hợp của các chuyên
gia đối với từng phương án, nghĩa là ta cần sử dụng một phép toán kết nhập R
tích hợp các ý kiến {x
ij
: j = 1, …, n} của các chuyên gia. Toán tử kết nhập là
một ánh xạ R : {s
0
, …, s
g
}n {s
0
, …, s
g
}. Ánh xạ này phải được xác định sao
cho kết quả của phép toán R(s
i1
, …, s
in
) có thể xem là biểu thị ý kiến tập thể
của n chuyên gia.
Giải bài toán sắp xếp mờ cũng chính là giải bài toán kết nhập mờ vì khi
có kết quả kết nhập, ta có thể sắp xếp các kết quả này theo thứ tự tăng (giảm )
dần của kết quả đó.
Có nhiều phương pháp tiếp cận tính toán khác nhau để giải quyết vấn
đề này. Dưới đây là một số phương pháp phổ biến.
1.4.2. Các phƣơng pháp giải bài toán sắp xếp mờ

hiện việc kết nhập số học. Ý tưởng này thể hiện như sau:
Giả sử ta lấy kết nhập tập các từ ngôn ngữ trong A = {a
1
, …, a
p
}, a
i
S. Ta
thực hiện một hoán vị các chỉ số của tập A, A = {aπ
1
, …, aπ
p
},
sao cho aπ
i
≥ aπ
j
nếu i ≤ j. Xét một phép kết nhập số học R nào đó. R sẽ cảm
sinh một phép kết nhập g* trên tập S được định nghĩa như sau:
Tính R(π
1
, …, π
p
)  [0, g], với π
1
, …, π
p
là các chỉ số của các phần tử trong A.
Đặt i* = round(R(π
1

* trong tập S. Tuy nhiên việc làm tròn làm
mất mát thông tin và các tác giả [12] đã đưa ra cách biểu diễn dữ liệu bộ 2 để
khắc phục sự mất mát thông tin này.
Ý tưởng của phương pháp như sau. Giá trị R(π
1
, …, π
p
) chưa làm tròn
sẽ là một số thực b [0, g], k – 0.5 ≤ b<k + 0.5. Để biểu thị rõ các thông tin
các tác giả trong [13] đề xuất dạng biểu diễn bộ 2, (sk, bk), trong đó bk = b –
k [-0,5, +0,5). Từ sk được gọi là tâm của thông tin còn ak biểu thị giá trị
chuyển dịch từ giá trị gốc b về từ ngôn ngữ sk. Biểu diễn này cũng xác định
một ánh xạ sau:
 : [0, g]S [-0,5, 0,5); (b) = (sk, bk), với bk = b – k, k = round(b)
và, do đó, ta có -1 : S [-0,5, 0,5) [0, g]; -1((sk, bk)) = k + bk [0, g]. Với biểu diễn như vậy, các phép kết nhập trên các từ ngôn ngữ được
định nghĩa thông qua các phép kết nhập số học nhờ việc chuyển đổi của ánh
xạ -1. Nói một cách đơn giản, phương pháp bộ 2 thực chất vẫn là phương
pháp kết nhập theo chỉ số nhưng có kèm theo tham số phụ b để đánh giá trong
trường hợp hai phép kết nhập cùng cho kết quả là giá trị ngôn ngữ sk thì phép
kết nhập nào cho sai số bk nhỏ hơn sẽ được ưu tiên lựa chọn hơn. k
k-1
b
g
Hình 1: Biểu diễn bộ 2