i

LỜI CẢM ƠN

Lời đầu tiên em xin gửi lời cảm ơn chân thành đến toàn thể các thầy cô
giáo Viện Công nghệ Thông tin, cùng toàn thể quý Thầy Cô trong trường Đại
học Công nghệ Thông tin & Truyền thông đã tận tình dạy dỗ tận tình truyền
đạt những kiến thức quý báu và tạo điều kiện thuận lợi cho tôi trong suốt quá
trình học tập, nghiên cứu và thực hiện luận văn tốt nghiệp.
Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới Thầy giáo PGSTS.Nguyễn Văn Long, Trường Đại học Giao thông vận tải - Hà Nội đã quan
tâm hướng dẫn và đưa ra những gợi ý, góp ý, chỉnh sửa vô cùng quý báu cho
em trong quá trình làm luận văn tốt nghiệp.
Cuối cùng xin chân thành cảm ơn những người bạn đã giúp đỡ, chia sẽ
với tôi trong suốt quá trình làm luận văn.
Thái Nguyên, tháng 07 năm 2014
Học viên thực hiện


ii

MỤC LỤC

PHẦN MỞ ĐẦU .................................................................................. 1
CHƯƠNG 1: PHƯƠNG PHÁP LẬP LUẬN MỜ SỬ DỤNG ĐẠI
SỐ GIA TỬ……. .................................................................................. 3
1.1 Tập mờ và các phép toán trên tập mờ ..................................................... 3
1.1.1.Tập mờ (fuzzy set)............................................................................... 3
1.1.2 Các phép toán đại số trên tập mờ ......................................................... 6
1.1.3 Khử mờ ............................................................................................... 8
1.2 Phương pháp lập luận mờ đa điều kiện ................................................... 8
1.2.1 Mô hình mờ ......................................................................................... 8

DANH MỤC CÁC HÌNH
Hình 1.1: Tập mờ hình thang .......................................................................... 5
Hỉnh 1.2 Ví dụ về hệ khoảng ........................................................................ 24
Hình 1.3 Các hàm thuộc của các tập mờ của biến h ...................................... 30
Hình 1.4 Các hàm thuộc của các tập mờ của biến v ...................................... 30
Hình 1.5 Các hàm thuộc của các tập mờ của biến f ...................................... 30
Hình 1.6 Đường cong định lượng ngữ nghĩa ................................................ 34
Hình 2.1. Minh họa bánh xe rulet ................................................................. 44
Hình 3.1. Đường cong thực nghiệm của mô hình EX1. ................................ 50
Hình 3.2 Kết quả xấp xỉ mô hình EX1 bằng vHAR. ..................................... 55
Hình 3.3 Đường cong thực nghiệm của mô hình EX6. ................................. 57
Hình 3.4 Kết quả xấp xỉ mô hình EX6 bằng vHAR. ..................................... 62


v

DANH MỤC CÁC BẢNG
Bảng 1.1. Các giá trị ngôn ngữ của các biến HEALTH và AGE .................... 17
Bảng 1.2. Ví dụ về tính âm dương giữa các gia tử ........................................ 19
Bảng 1.3. Các nhãn tập mờ của các biến ngôn ngữ h, v, f ............................. 29
Bảng 1.4. Mô hình FAM của bài toán hạ cánh máy bay................................ 31
Bảng 1.5. Kết quả điều khiển sử dụng lập luận mờ qua 4 chu kỳ .................. 31
Bảng 1.6: Mô hình SAM .............................................................................. 33
Bảng 1.7. Kết quả điều khiển mô hình máy bay hạ cánh .............................. 35
Bảng 2.1. Minh họa quá trình chọn lọc ......................................................... 41
Bảng 2.2. Minh họa quá trình lai ghép.......................................................... 42
Bảng 3.1. Mô hình EX1 của Cao – Kandel. .................................................. 49
Bảng 3.2. Các kết quả xấp xỉ EX1 tốt nhất của Cao - Kandel [8] .................. 50
Bảng 3.3. Mô hình định lượng ứng với vPAR1 ............................................. 52
Bảng 3.4. Mô hình EX6 của Cao – Kandel ................................................... 56

Mục tiêu của đề tài
- Nghiên cứu các khái niệm cơ bản về đại số gia tử, phương pháp lập
luận mờ sử dụng đại số gia tử.
- Nghiên cứu các khái niệm cơ bản của giải thuật di truyền
- Nghiên cứu ứng dụng giải thuật di truyền để tối ưu hóa các tham số
trong phương pháp lập luận mờ sử dụng đại số gia tử.
Phạm vi của đề tài
- Nghiên cứu các khái niệm cơ bản về đại số gia tử, phương pháp lập
luận mờ sử dụng đại số gia tử.
- Nghiên cứu ứng dụng giải thuật di truyền để tối ưu hóa các tham số
trong phương pháp lập luận mờ sử dụng đại số gia tử.
Phương pháp nghiên cứu.


2

+ Nghiên cứu tài liệu, các bài báo trên các tạp chí và trên internet và viết
tổng quan để nắm vững nội dung lý thuyết chuyên ngành và khả năng ứng dụng.
+ Nghiên cứu so sánh tìm ra sự khác biệt giữa các cách tiếp cận, giữa các
phương pháp lập luận làm cơ sở cho việc đề xuất các giải pháp của đề tài.
+ Lập trình mô phỏng thuật toán trên máy tính để thuận lợi trong nghiên
cứu hiệu quả của phương pháp.


3

CHƯƠNG 1: PHƯƠNG PHÁP LẬP LUẬN MỜ SỬ DỤNG
ĐẠI SỐ GIA TỬ
1.1 Tập mờ và các phép toán trên tập mờ
Để mô tả những khái niệm mơ hồ, chẳng hạn như nhiệt độ “cao”, tốc độ


4

Tập hợp thông thường A  U có một ranh giới rất rõ ràng. Chẳng hạn, A
là tập những người có tuổi dưới 19 là một tập thông thường. Mỗi người (phần
tử) chỉ có hai khả năng: hoặc là phần tử của A hoặc không. Tuy nhiên nếu ta
xét tập à gồm những người trẻ thì trường hợp này sẽ không có ranh giới rõ
ràng. Khó có thể khẳng định một người là phần tử của à hay không, khi đó
ranh giới của nó là mờ. Ta chỉ có thể nói một người sẽ thuộc tập à ở một mức
độ nào đó.
Chẳng hạn chúng ta có thể thống nhất với nhau rằng một người 35 tuổi
thuộc về tập à với độ thuộc 60% hay 0.6. Zadeh gọi một tập à như vậy là tập
mờ và đồng nhất tập hợp à với một hàm trẻ: Y  [0,1], gọi là hàm thuộc của
tập mờ Ã, trong đó Y là tập số tự nhiên để đo độ tuổi tính theo năm, còn gọi là
không gian tham chiếu. Từ trẻ được gọi là khái niệm mờ.
Nếu không nhầm lẫn thì từ đây về sau ta ký hiệu tập mờ A thay cho à và
chúng ta có định nghĩa tập mờ dưới đây.
Cho U là vũ trụ các đối tượng. Tập mờ A trên U là tập các cặp có thứ tự
(x, A(x)), với A(x) là hàm từ U vào [0,1] gán cho mỗi phần tử x thuộc U giá
trị A(x) phản ánh mức độ của x thuộc vào tập mờ A.
Nếu A(x) = 0 thì ta nói x hoàn toàn không thuộc vào tập A, ngoài ra nếu

A(x)= 1 thì ta nói x thuộc hoàn toàn vào A. Trong định nghĩa trên, hàm  còn
được gọi là hàm thuộc (membership function).
Hàm thuộc có thể được biểu diễn dưới dạng liên tục hoặc rời rạc. Đối với
vũ trụ U là vô hạn thì tập mờ A trên U thường được biểu diễn dạng

A    A ( x) / x , còn đối với vũ trụ hữu hạn hoặc rời rạc U = {x1, x2, …, xn}, thì
tập mờ A có thể được biểu diễn A = {µ1/x1 + µ2/x2 + … + µn/xn}, trong đó các
giá trị µi (i = 1, …, n) biểu thị mức độ thuộc của xi vào tập A.

c


0, x  d


xR

trong đó a, b, c, d là các số thực và a ≤ b ≤ c ≤ d . Hình vẽ tương ứng của hàm
thuộc A được mô tả như Hình 1.1.

1
µA

a

b
c
d
Hình 1.1: Tập mờ hình thang

Tiếp theo là những định nghĩa về tập mờ lồi và tập mờ chuẩn
Cho A là tập mờ trên vũ trụ U.
i)A là tập mờ lồi khi và chỉ khi A(x1 + (1 – )x2)  min{A(x1), A(x2)}
x1, x2  U,   [0,1].
ii) A là tập mờ chuẩn khi và chỉ khi tồn tại ít nhất một phần tử x  U sao
cho A(x) = 1.


6

A  B  A(x)  B(x), x  U.


7

Chúng ta có nguyên lý suy rộng cho nhiều biến sau đây.
Cho A1, A2,..., An là các tập mờ trên các vũ trụ U1, U2, ..., Un tương ứng,
quan hệ mờ f(A1, A2,..., An) được định nghĩa là tập mờ
f(A1, A2,..., An) = {((x1, ..., xn), f(x1, ..., xn)) (x1, ..., xn)  U1U2...Un,

f(x1,..., xn) = f(A1(x), ..., An(x))}.
Ngoài các phép toán trên, sau đây chúng tôi cũng xin nhắc lại một số
định nghĩa về họ toán tử t-norms, t-conorms và N-Negative.
Hàm T: [0,1][0,1]  [0,1] được gọi là t-norm khi và chỉ khi T thoả mãn
các điều kiện: với mọi x, y, z  [0,1]
i)T(x, y) = T(y, x),
ii)

T(x, y)  T(x, z), y  z,

iii)

T(x, T(y, z)) = T(T(x, y), z),

iv)

T(x, 1) = x, T(0, 0) = 0.

Hàm S: [0,1][0,1]  [0,1] được gọi là t-conorm khi và chỉ khi S thoả
mãn các điều kiện: với mọi x, y, z  [0,1]

Trong điều khiển kỹ thuật, các dữ liệu vào và ra thường là các giá trị số.
Giá trị đầu vào được mờ hoá bằng các hàm đặc trưng. Giá trị đầu ra được khử
mờ dựa trên hàm đặc trưng đó. Có nhiều phương pháp để khử mờ, ở đây
chúng tôi chỉ đề cập đến phương pháp khử mờ của R.Yager.
Giả sử A là một tập mờ trên vũ trụ U gắn với hàm thuộc , khi đó ta có
công thức khử mờ theo tham số  như sau:
n

 x (x ) 
i

x* 

i

i 1
n

 (x )

,   0,  



i

i 1

Một số dạng khử mờ được sử dụng khi U là tập số thực



chỉ chứa một điều kiện và một kết luận được cho như sau:
if X = A1

then Y = B1

if X = A2

then Y = B2

(1.2)

........
if X = AM then Y = Bm
trong đó X, Y là các biến ngôn ngữ và A1, A2,…, Am, B1, B2, …, Bm là các giá
trị ngôn ngữ tương ứng.
Mô hình mờ dạng tổng quát là một tập các luật (ifthen) mà phần tiền đề
của mỗi luật là một điều kiện phức có dạng như sau:
If X1 = A11 and ... and Xm = A1n then Y = B1
If X1 = A21 and ... and Xm = A2n then Y = B1
..........

(1.2)

If X1 = Am1 and ... and Xm = Amn then Y = Bm
ở đây X1, X2,.., Xm và Y là các biến ngôn ngữ, Aij, Bi (i = 1,.., n; j = 1,.., m) là
các giá trị ngôn ngữ tương ứng.
(1.1) còn được gọi là mô hình mờ đơn điều kiện và (1.2) được gọi là mô
hình mờ đa điều kiện, ngoài ra (1.2) còn được gọi là bộ nhớ kết hợp mờ
(Fuzzy Associate Memory - FAM) vì nó biểu diễn tri thức của chuyên gia

U = {u1, u2, u3}
A1 = 0,5/u1 + 1,0/u2 + 0,6/u3 ;
A2 = 0,7/u1 + 0,4/u2 + 0,9/u3 ;


11

V = { v1, v2}
B1 = 1,0/v1 + 0,4/v2;
B2 = 0,3/v1 + 0,8/v2;
Cho sự kiện X = A’ với A’ = 0,6/u1 + 0,9/u2 + 0,7/u3. Hãy tính B’
Trước hết ta tính các quan hệ mờ cho mỗi luật R = A  B, dựa vào phép
kéo mờ theo Lukasiewicz:

R(u, v) = min(1, 1 – A(u) + B(v)), u  U và v  V.
Ta có
 1 .0 0 .9 
 0 .6 1 .0 




R1   1 . 0 0 . 4  R 2   0 .9 1 .0 




 1 .0 0 .8 
 0 .4 0 .9 




0
.
4
0
.
8



Sử dụng phép hợp thành max – min:

B’(v)=max (min ((u), (u, v))) với u  U và v  V.
Ta có B’ = (0.9 0.7), như vậy ta suy ra B’ = 0,9/v1 + 0,7/v2.


12

Ví dụ trên đề cập tới việc lập luận trên mô hình đơn điều kiện, do đó ta
không phải kết nhập các đầu vào, sau đây ta lấy một ví dụ lập luận dựa trên
mô hình đa điều kiện:
Xét bài toán lập luận với mô hình đa điều kiện chứa 2 luật
If x is A1 and y is B1 then z is C1
If x is A2 and y is B2 then z is C2
Với A1, A2 là 2 tập mờ của biến ngôn ngữ x trên vũ trụ A
A=[10 20 30 40]
A1=[0.3 0.5 0.7 0.9];
A2=[0.8 0.7 0.2 0.6];
B1, B2 là 2 tập mờ của biến ngôn ngữ y trên vũ trụ B

1.0000 1.0000

1.0000 0.9000 0.8000

1.0000 1.0000

1.0000 0.8000 0.7000

1.0000 1.0000

0.9000 0.6000 0.5000

1.0000 1.0000

1.0000 0.9000 0.8000

1.0000 1.0000

0.9000 0.6000 0.5000

1.0000 0.8000

0.7000 0.4000 0.3000

1.0000 1.0000

1.0000 0.9000 0.8000

1.0000 0.8000



0.7000 1.0000

1.0000 1.0000 1.0000

0.6000 0.9000

1.0000 1.0000 1.0000


14

R2=

1.0000 1.0000

1.0000 1.0000 1.0000

1.0000 1.0000

1.0000 1.0000 1.0000

1.0000 1.0000

1.0000 1.0000 1.0000

1.0000 1.0000

1.0000 1.0000 1.0000


1.0000 0.9000 0.8000

0.6000 0.9000

0.9000 0.6000 0.5000

1.0000 0.8000

0.7000 0.4000 0.3000

1.0000 1.0000

1.0000 0.9000 0.8000

1.0000 0.8000

0.7000 0.4000 0.3000

1.0000 0.8000 0.7000

0.4000 0.3000

0.7000 1.0000 1.0000

0.9000 0.8000

0.7000 0.7000

0.6000 0.3000 0.2000


C0=[0.60 0.90 0.90 0.60 0.50]


15

Tiến hành khử mờ theo phương pháp lấy max, ta tìm được giá trị lớn nhất
0.9 và vị trí lớn nhất 2, do đó giá trị khử mờ 2000.
Phương pháp lập luận mờ đa điều kiện được ứng dụng trong việc xây
dựng các hệ mờ dựa tập luật, trên thực tế đã có một loạt các hệ mờ đã được
xây dựng và ứng dụng trong thực tế như các hệ chuyên gia, các hệ trợ giúp
quyết định, các hệ điều khiển,…
Hiệu quả của phương pháp lập luận mờ nói chung phụ thuộc vào nhiều
yếu tố rất căn bản chẳng hạn như:
- Lựa chọn tập mờ (bài toán xây dựng các hàm thuộc).
- Bài toán lựa chọn phép kết nhập.
- Xây dựng quan hệ mờ mô phỏng tốt nhất mô hình mờ (bài toán lựa
chọn phép kéo theo).
- Bài toán lựa chọn phép hợp thành để tính giá trị đầu ra.
- Bài toán khử mờ.
Đó chính là những khó khăn không nhỏ khi xây dựng phương pháp giải
có hiệu quả bài toán lập luận mờ đa điều kiện.
1.3 Đại số gia tử của biến ngôn ngữ
1.3.1 Khái niệm biến ngôn ngữ
Khái niệm biến ngôn ngữ đươc Zadeh giới thiệu và được đề cập trong
nhiều tài liệu, ta có thể hình dung khái niệm này qua định nghĩa sau [1]:
Biến ngôn ngữ được đặc trưng bởi một bộ gồm năm thành phần (X,T(X),
U, R, M), ở đây X là tên biến, T(X) là tập các giá trị ngôn ngữ của biến X, U
là không gian tham chiếu của biến cơ sở u, mỗi giá trị ngôn ngữ xem như là
một biến mờ trên U kết hợp với biến cơ sở u, R là một qui tắc cú pháp sinh


…

…

…

…

Các giá trị ngôn ngữ young và old được gọi là các giá trị nguyên thủy.
Mỗi giá trị ngôn ngữ trong T(AGE) là tên của một biến mờ trên U, tức là biến
có thể nhận giá trị trên U với mỗi giá trị ứng với một mức độ tương thích
trong đoạn [0,1], ràng buộc hạn chế trên mỗi giá trị ngôn ngữ hình thành ngữ
nghĩa cho giá trị ngôn ngữ đó, ví dụ ngữ nghĩa của old được cho như sau:
1

  u  50  2 
old(u) =  1  
  / u
5

 
50 
100

Tuy nhiên ngữ nghĩa của các giá trị khác trong T(AGE) có thể tính thông
qua tập mờ của các giá trị nguyên thủy bởi các phép toán tương ứng với các
gia tử tác động như very, possibly,...
Trong các nghiên cứu của mình về biến ngôn ngữ và lập luận xấp xỉ
Zadeh luôn nhấn mạnh hai đặc trưng quan trọng nhất của biến ngôn ngữ:
- Đặc trưng thứ nhất là tính phổ quát của cấu trúc miền giá trị của chúng,


…

Poor

Young

Very Poor

Very Young

More-or-Less poor

More-or-Less Young

……….

……….

Các đặc trưng của biến ngôn ngữ cho phép ta sử dụng một tập các gia tử
ngôn ngữ cho nhiều biến ngôn ngữ khác nhau và có thể mô tả hình thức miền
giá trị của các biến ngôn ngữ bởi một cấu trúc ngôn ngữ toán học thuần nhất.
Để mô hình hóa cấu trúc tự nhiên miền giá trị của các biến ngôn ngữ, một
cấu trúc đại số gọi là ĐSGT đã được đề xuất trong [3,9,10]. Sau đây luận văn
sẽ đề cập chi tiết khái niệm ĐSGT trong mục 1.1.2.


18

1.3.2 Đại số gia tử của biến ngôn ngữ

H  H+. Nếu cả hai gia tử h và k cùng thuộc H+ hoặc H, thì ta nói h, k sánh
được với nhau. Ngược lại, nếu h và k không đồng thời thuộc H+ hoặc H, khi
đó ta nói h, k ngược nhau.
iii) Hơn nữa, chúng ta nhận thấy mỗi gia tử đều có sự ảnh hưởng (làm
tăng hoặc làm giảm) đến ngữ nghĩa của các gia tử khác. Vì vậy, nếu k làm
tăng ngữ nghĩa của h, ta nói k là dương đối với h. Ngược lại, nếu k làm giảm
ngữ nghĩa của h, ta nói k là âm đối với h.
Chẳng hạn xét các gia tử V(Very), M(More), L(Little), P(Possible) của
biến ngôn ngữ TRUTH. Vì L true < true và VL true < L true < PL true nên V
là dương đối với L còn P là âm đối với L. Tính âm, dương của các gia tử đối
với các gia tử khác không phụ thuộc vào phần tử ngôn ngữ mà nó tác động.
Thật vậy, nếu V dương đối với L thì với bất kỳ phần tử x ta có: Nếu x  Lx thì
Lx  VLx hay Nếu x  Lx thì Lx  VLx.
Nhìn chung, với bất kỳ h, kH, h được gọi là dương đối với k nếu
(xX){( kx  x  hkx  kx) hay (kx  x  hkx  kx )}. Một cách tương tự, h
được gọi là âm đối với k nếu (xX){( kx  x  hkx  kx) hay (kx  x  hkx 
kx)}. Tính âm, dương của các gia tử được thể hiện trong Bảng 2.2.
Bảng 1.2. Ví dụ về tính âm dương giữa các gia tử
V

M

P

L

V

+