!"
MỤC LỤC
1
#$%&'()*+,*,*-
TÊN ĐỀ TÀI:
ỨNG DỤNG LOGIC MỜ TRONG VIỆC GIẢI QUYẾT
BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI TIỂU LUẬN MÔN
TOÁN HỌC CHO KHOA HỌC MÁY TÍNH
Giảng viên hướng dẫn: PGS. TS. Đỗ Văn Nhơn
Họ tên học viên: Đặng Thị Mỹ Hạnh
Mã số học viên: CH1301012
!"
.$
Chương 1:
Một số vấn đề cơ bản về Logic mờ
1
I. Giới thiệu Logic mờ 1
II. Khái niệm Logic mờ 1
III. Các phép toán trên tập mờ 7
IV. Suy luận xấp xỉ dựa trên logic mờ 8
V. Xây dựng tập mờ 10
VI. Khái niệm số mờ 11
Chương 2: Ứng dụng Logic mờ trong việc giải quyết bài toán tìm
đường đi ngắn nhất 14
I. Ý tưởng 14
II. Phát biểu bài toán 14
III. Hướng giải quyết bài toán 15
tập hợp (set membership function) nhận giá trị thựcgiữa 0 và 1.
1. Định nghĩa tập mờ
Tập mờ : được xác định trên không gian nền kinh điển ; là một tập mà mỗi phần tử
của nó là một cặp
))x(,x(
A
µ
trong đó <
∈
; và
)x(
A
µ
là ánh xạ
[ ]
1,0X:
A
→
µ
Ánh xạ
A
µ
được gọi là hàm liên thuộc (hàm phụ thuộc) của tập mờ :
/3=
3
#$%&'()*+,*,*-
!"
Giả sử tập mờ 0 các số tự nhiên nhỏ hơn nhiều so với 6. Xác định phụ thuộc hàm
)x(
B
A
µ
dưới dạng bảng)
- Tìm các giá trị tương ứng trên đồ thị (nếu
)x(
A
µ
được biểu diễn dạng đồ thị )
Trong nhiều tài liệu để biểu diễn tập mờ người ta cũng thường dùng ký hiệu sau:
∑
=
=
++++=
:
::
::
<
<
<
<
Phép cộng (+) được hiểu là phép hợp.
Ví dụ: Đồ thị hàm liên thuộc của tập mờ
1
m1 m2 m3 m4
)x(
A
µ
4
#$%&'()*+,*,*-
!"
/E%FG6H3=
Các hàm liên thuộc
)x(
A
µ
có dạng “trơn” như ở hình vẽ được gọi là hàm liên
thuộc kiểu S. Đối với hàm liên thuộc kiểu S do các công thức biểu diễn có độ phức tạp
lớn nên thời gian tính độ phụ thuộc cho một phần tử lâu. Bởi vậy trong kỹ thuật điều
khiển mờ thông thường các hàm liên thuộc kiển S hay được thay gần đúng bằng một hàm
tuyến tính từng đoạn.
Một hàm liên thuộc có dạng tuyến tính từng đoạn được gọi là hàm liên thuộc có
mức chuyển đổi tuyến tính. Hàm liên thuộc
)x(
A
µ
như ở hình vẽ với *>-IF+>C
chính là hàm thuộc của một tập kinh điển
2. Khái niệm hàm liên thuộc
Như trên đã trình bày, nếu : là một tập hợp trong không gian nền ;, khi đó phần tử
< bất kỳ của ;, chỉ có thể có hai khả năng xảy ra, hoặc x
Hình sau mô tả hàm thuộc của tập : :
-R
3. Một số khái niệm liên quan của tập mờ
Trong những ví dụ trên các hàm liên thuộc đều có độ cao bằng *. Điều đó nói rằng
5
#$%&'()*+,*,*-
Miền U
Miền tin cậy
Miền xác định
!"
các tập mờ đó đều có ít nhất một phần tử với độ phụ thuộc bằng *.
Trong thực tế không phải tập mờ nào cũng có phần tử có độ phụ thuộc bằng *.
Tương ứng với điều đó thì không phải mọi hàm liên thuộc đều có độ cao là *.
Định nghĩa 1:Độ cao của một tập mờ : trên không gian nền ; là giá trị
)x(h
sup
Xx
µ
∈
=
.
Ký hiệu:
)x(
sup
Xx
µ
∈
chỉ giá trị nhỏ nhất trong tất cả các giá trị chặn trên của hàm
)x(
µ
6
#$%&'()*+,*,*-
!"
/TH3=
Định nghĩa 5: Tập cắt α (α∈ [0,1]) của tập mờ tập mờ : trên không gian nền ;
được ký hiệu bởi :
α
là tập con của ; thoả mãn
:
α
=N<P
µ
:
?<A
≤α
S
và được gọi là tập cắt mạnh nếu :
α
+
=N<P
µ
:
?<AQ
α
S
Định nghĩa 6: Tập mức, hay là tập các nhát cắt của tập mờ tập mờ : trên không gian
nền ; được ký hiệu bởi Λ(:A là tập các tập con của ; thoả mãn
:=N<P
µ
:
ASXvới
∀
<
*
@<
-
∈
;@
∀λ∈
Y,@*Z
Định nghĩa 8: Lực lượng của tập mờ : trên không gian nền ; được biểu diễn như
sau:
∑
∈
=
:<
:
<<:!
:
)())(,(
µµ
4. Tính chất
- Hai tập mờbằng nhau: A = B nếu ∀x ∈X, μA (x) = μB (x)
- Tập con: A ⊆B nếu ∀x ∈X, μA (x) ≤ μB (x)
- Một phần tửcó thểthuộc vềnhiều hơn một tập mờ. Một người đàn ông cao 1m60có
thể thuộc vềcảhai tập “trung bình” và “cao”.
- Tổng các giá trịmờcủa một phần tửkhác 1:
μThấp(x) + μTrungbình(x) + μCao(x) ≠1
- Từhàm thành viên cho trước, ta có thểsuy ra được mức độmột thành viên thuộc
vềmột tập hợp, hay có thểxác định được giá trịmờcủa nó đối với một tập mờ.
20x10 nÕu 210/x
10x45- nÕu 1
Ví dụ trên có thể được hiểu như sau:
- Nếu nhiệt độ thấp hơn *,
) ( WC\Q<Q*, ) tất cả mọi người đều đánh giá mức độ
lạnh là * (tương ứng với 100%).
- Nếu nhiệt độ đạt khoảng từ *,
) đến -,
)( *,]<]-,) thì số người đánh giá mức
độ lạnh khác nhau nằm trong khoảng từ , ( ,^) đến * (*,,^), đạt *\
) mức độ lạnh
được đánh giá ,\ (tương ứng với việc có \,^ số người cho là lạnh), nếu nhiệt độ là
*D
) mức độ lạnh được đánh giá ,+ (tương ứng với việc có +,^ số người cho là lạnh).
Ta có đồ thị sau:
8
#$%&'()*+,*,*-
1
1020 30 40
lạnh
mát
ấm
nóng
!"
/E%5$
≤≤+
<≤−
≥≤
40x30 nÕu 4x/10-
30x20 nÕu 210/x
40x hoÆc 20x nÕu 0
Nóng =
≤
≤≤−
≥
30x nÕu 0
40x30 nÕu 310/x
40x nÕu 1
/E%5$456
III. CÁC PHÉP TOÁN TRÊN TẬP MỜ
Những phép toán cơ bản trên tập mờ là phép hợp, phép giao và phép bù giống như
định nghĩa về tập mờ các phép toán trên tập mờ cũng sẽ được định nghĩa thông qua các
hàm liên thuộc được xây dựng tương tự như các hàm thuộc của các phép hợp, giao, bù
giữa hai tập hợp kinh điển. Nói cách khác việc xây dựng các phép toán trên tập mờ được
hiểu là việc xác định các hàm liên thuộc cho phép hợp :
∪
0, giao :
∩
0, bù : …từ những
=> μ
Tre
∨
Trung Niên
(An) = max( 0.8, 0.3) = 0.8
2 Phép giao hay toán tửAND
Giao của hai tập mờ(A∩B) thểhiện mức độmột phần tửthuộc vềcảhai tập là bao
nhiêu.
Công thức: μ
A
∧
B
(x) = min (μA(x) , μB(x) )
Ví dụ:μ
Tre
(An) = 0.8 và μ
Trung niên
(An) = 0.3
=> μ
Tre
∧
Trung Niên
(An) = min( 0.8, 0.3) = 0.3
3 Phép bù hay toán tửNOT
Bù của một tập mờthểhiện mức độmột phần tửkhông thuộc vềtập đó là bao nhiêu.
Công thức: μ
¬A
(x) = 1 - μ
A
(x)
Suy diễn xấp xỉ hay còn gọi là suy luận mờ đó là quá trình suy ra những kết luận
dưới dạng các mệnh đề mờ trong điều kiện các quy tắc, các luật, dữ liệu đầu vào cho
trước cũng không hoàn toàn xác định.
Trong công trình của mình Zadeh đưa ra khái niệm lập luận xấp xỉ như sau:
Bảng Suy luận xấp xỉ
Tiền đề 1 !_FH`aFF5bF5c/`aF5bF
Điều kiện FHFdF.e5c
Kết luận daFd.e
Chúng ta thấy lược đồ này tương tự như luật Modus ponens trong logic kinh điển: :
⇒
0, có : cho phép ta rút ra kết luận 0. Tuy nhiên ở lược đồ trên trong giả thiết (tiền đề)
ta không có : mà có A' =' Oe5c' một biến tướng của :, khi đó ta có thể rút ra kết luận
nào đó <e3<f0 là 0g>gOeg chẳng hạn. Vấn đề là cần xây dựng phương pháp luận
cho phép lựa chọn kết luận 0g như thế nào phù hợp với quy luật thực tiễn.
Nhờ tính mềm dẻo của phương pháp lập luận mờ chúng ta sẽ có nhiều phương pháp
suy diễn xấp xỉ. Xét lược đồ lập luận mờ đa điều kiện sau:
Bảng điều kiện suy diễn xấp sỉ
Tiên đề 1 h;>:
*
Ji>0
*
Tiên đề 2 h;>:
-
Ji>0
-
:
:
:
:
, 0
là
các nhãn của tập mờ biểu thị ngữ nghĩa của :
, 0
. Để cho tiện ta ký hiệu hàm giá trị chân
lý tương ứng :
?Avà 0
?IA trên không gian tham chiếu U và .
Một cách trực cảm, mỗi mệnh đề !_/ được hiểu là một phép kéo theo logic
mờ :
?A
⇒
0
?IA . Khi và I biến thiên, biểu thức này xác định ánh xạ hàm giá trị chân lý
µ
U;
→
Y,@*Z
Bước 2:k_3?$$.J$A Qua các phép toán logic mờ chúng ta thu được
công thức dạng
i
"tương ứng" với giá trị chân lý của 0
,
được gọi là phương pháp khử mờ. Sẽ không có
phương pháp nào "tốt nhất" được đưa ra mà chỉ có thể đánh giá theo một giá trị ngưỡng
nào đó tuỳ thuộc quá trình thử nghiệm hoặc trực cảm nào đó. Ví dụ ta có thể khử mờ theo
trung bình cộng có trọng số, được cho bởi công thức:
∑
∈
∑
∈
=
Vv
)v(
0
B
Vv
)v(
0
vB
)
0
B(defuz
Có thể hình dung phương phương pháp lập luận mờ bằng mô hình tổng quát sau:
12
#$%&'()*+,*,*-
!"
0a$/L12<e3<f
V. XÂY DỰNG TẬP MỜ
Tập mờ A xác định trên không gian nền X là một tập hợp thỏa mãn:
+ Mỗi phần tử của A có dạng (x,µ
20)(
0
10
20)(
1
1
≥
<<
≤
−
−=
<$J
<$J
<$J
<$J
$
µ
Hàm liên thuộc được thể hiện dưới dạng đồ thị như sau:
13
#$%&'()*+,*,*-
$
µ
1
$J?<A
3020
≤<
−
−
≤<
−
−
≤
=
3
32
23
3
21
12
1
1
0
0
)(
<
<
<
<
<
<
<
:
µ
0
],(1
],[1
),[1
β
β
α
α
+∈
−
−
∈
−∈
−
−
- Hàm thuộc được xác định như sau:
Thường được biểu diễn qua bộ 4 số:
),,,(
_
~
βα
−
=
/012Lq=1'$/$
15
#$%&'()*+,*,*-
!"
CHƯƠNG 2
ỨNG DỤNG LOGIC MỜ TRONG VIỆC GIẢI QUYẾT BÀI TOÁN TÌM
Bài toán được đề cập đến ở đây là bài toán ở dạng thứ nhất: tìm đường đi ngắn nhất
từ một nút nguồn đến một nút đích cho trước.
Input:
3v'5f@3$x@u$E*?y$*Azu5?y$-A
a $?#T1FAH$
Output
s=$5$ter5f*5_5f
n5FKF5s=$5$teIT1'$KF`'
_
* Xây dựng đường đi trong đồ thị:
Theo định nghĩa với bài toán đường đi ngắn nhất ta xây dựng đường đi trên cung i,j
là một hàm x(i,j) thỏa mãn các tính chất sau:
- x
ij
=0 hoặc x
ij
=1 ứng với việc có hay không sử dụng cung i,j trong đường đi
Tổng đường đi ra tại nút nguồn bằng 1; tổng đường đi vào tại nút đích bằng 1
Tổng đường đi vào một nút i bất kỳ bằng tổng đường đi ra tại nút đó.
* Giới hạn đường đi:
Đường đi trên cung không vượt quá tải năng của cung
),(),( IIh ≤
* Cân bằng đường đi tại nút đỉnh:
17
#$%&'()*+,*,*-
!"
Tổng đường đi vào tại một đỉnh bằng tổng đường đi ra tại đỉnh đó (trừ đỉnh đầu và
đỉnh đích)
∑ ∑
= =
{
{{
<
1 1
* Các ràng buộc:
=
=
−=−
∑ ∑
= =
J.|LJ
<<
{
{
{
{
{
<
1 1
~
Các ràng buộc:
=
=
−=−
∑ ∑
= =
J.|LJ
<<
{
),,(
222
~
2
K• =
Khi đó:
),,(
212121
~
2
~
1
KK•• +++=⊕
* Chiều dài nhỏ nhất:
Với hai số mờ tam giác
),,(
111
~
1
K• =
và
),,(
222
~
2
K• =
~
•
min
}{
Giả sử có 2 số mờ dạng tam giác
),,(
~
K• =
và
),,(
~
K• =
Ta tìm cách thể hiện độ tương tự giữa hai số này.
Khi giao của hai tam giác càng lớn thì độ tương tự giữa hai số mờ càng cao. Ký
hiệu S
i
là độ tương tự giữa
~
•
và
~
•
][
∅≠∩
∅=∩
−+−−
−
3.3. Ví dụ áp dụng bài toán
í d* í dụ 1. Cho sơ đồ mạng như hình sau. Tìm đường đi ngắn nhất từ
đỉnh 1 đến đỉnh 6
1. Cho sơ đồ mình sau. Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6
Bước 1: Tính độ dài các đường đi có thể có từ đỉnh 1 đến đỉnh 6
P
1
: 1-2-3-5-6 à L
1
=(201,262,285)
P
2
: 1-2-4-5-6 à L
2
=(196,253,282)
20
#$%&'()*+,*,*-
(56,58,72)
42
(88,92,134)
(33,45,50)
(32,40,46)
1 6
(51,79,85)
(50,52,61)
5
(75,110,114)(42,57,61)
3
(43,55,60)
!"
Path
S(L,
~
•
min
)
Ranking
P
1
: 1-2-3-5-6 6.81 5
P
2
: 1-2-4-5-6 9.11 4
P
3
: 1-2-4-6 36.70 2
P
4
: 1-2-5-6 27.9 3
P
5
: 1-3-5-6 36.76 1
Bước 4: Đưa ra đường đi có độ tương tự lớn nhất. Ta thu được kết quả đó là P
5
đi
qua các đỉnh 1-3-5-6.
Từ những hướng giải quyết như trên, ta có thể áp dụng cho sơ đồ đường đi của
trường ĐH CSND.
/"5E'$H.s=$)!
21
: 1-3-11-8-9-12-13-17-2 à L
4
=(181,228,286)
P
5
: 1-22-26-10-7-15-12-13-17-2 à L
5
=(140,185,246)
Bước 2: Tìm
~
•
min
Ta được
~
•
min
= (133,163,205)
22
#$%&'()*+,*,*-
!"
Bước 3: Tính độ tương tự giữa
~
•
min
và các L
i
Path
S(L,
~
•
nhất giữa hai điểm với độ dài các cung được biểu diễn dưới dạng số mờ, để giải quyết
yêu cầu đối với công tác trực ban tại trường ĐH CSND.
Tiểu luận mới chỉ dừng lại ở mặt lý thuyết và nêu ra ý tưởng, do khả năng lập trình
không thành thạo nên vẫn chưa có chương trình cụ thể. Nếu có cơ hội tiếp tục nghiên cứu
vấn đề này, sẽ cố gắng hoàn thiện phần viết chương trình.
Cuối cùng, chân thành cảm ơn thầy. Thầy đã truyền cảm hứng cho em nghiên cứu
những hướng phát triển đối với những kiến thức về Logic mờ.
Trong tiểu luận này, em có tham khảo một số tài liệu sau đây:
- Introduction to fuzzy logic – Andrea Bonarini
- Luận văn Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất
với dữ liệu mờ dạng khoảng – Phan Như Minh – Học viện Kỹ thuật Quân sự
- Lý thuyết tập mờ và logic mờ - Thư viện Học liệu mở Việt Nam
24
#$%&'()*+,*,*-
Copyright: Tài liệu đại học ©