Số hóa bởi Trung tâm Học liệu

i

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

TỐI ƢU HÓA THAM SỐ CỦA PHƢƠNG PHÁP
LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH


Học viên thực hiện
Số hóa bởi Trung tâm Học liệu

iii

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
1.2.2 Phƣơng pháp lập luận mờ đa điều kiện 9
1.3 Đại số gia tử của biến ngôn ngữ 15
1.3.1 Khái niệm biến ngôn ngữ 15
1.3.2 Đại số gia tử của biến ngôn ngữ 18
1.4 Độ đo tính mờ và ánh xạ định lƣợng ngữ nghĩa 21
1.5 Phƣơng pháp lập luận mờ sử dụng đại số gia tử 26
CHƢƠNG 2: GIẢI THUẬT DI TRUYỀN 37
2.1 Giải thuật di truyền 37
2.1.1 Các khái niệm cơ bản của giải thuật di truyền 37


Số hóa bởi Trung tâm Học liệu

v

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


Số hóa bởi Trung tâm Học liệu

vii

DANH MỤC VIẾT TẮT

FAM : Fuzzy Associate Memory
SAM : Semantization Associate Memory
ĐSGT : Đại số gia tử
FMCR: Fuzzy Multiple Conditional Reasoning
GA: Genetic Algorithm

Số hóa bởi Trung tâm Học liệu

1
PHẦN MỞ ĐẦU

Đặt vấn đề
Đại số gia tử (ĐSGT) và phƣơng pháp lập luận mờ sử dụng ĐSGT đã
đƣợc ứng dụng vào một số lĩnh vực nhƣ xây dựng mô hình cơ sở dữ liệu mờ.
Đánh giá kết quả học tập và giải quyết bài toán hƣớng nghiệp cho học sinh
phổ thông. Gần đây phƣơng pháp lập luận mờ sử dụng ĐSGT đã đƣợc ứng
dụng vào lĩnh vực điều khiển mờ. Các kết quả ứng dụng đã bƣớc đầu cho thấy

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 độ
“nhanh”,… ngƣời ta thƣờng sử dụng lý thuyết tập mờ. Dƣới đây là các định
nghĩa và các phép toán cơ bản trong lý thuyết này.
1.1.1.Tập mờ (fuzzy set)
Cho tập vũ trụ U (còn gọi là không gian tham chiếu), một tập con thông
thƣờng A (tập rõ) của U có thể đƣợc đặc trƣng bởi hàm

A
nhƣ sau:






Ax
Ax
x
A
,0
,1
)(


Ví dụ cho tập U = {x
1


A
(x
4
) = 0,

A
(x
5
) = 1.
Gọi
A
là phần bù của tập A, ta có
A
 A = ,
A
 A = U. Nếu x  A
thì x 
A
, ta viết

A
(x) = 1,
A

(x) = 0.
Dễ dàng ta có, nếu A, B là hai tập con của U, thì hàm đặc trƣng của các
tập AB, AB đƣợc xác định:


Số hóa bởi Trung tâm Học liệu

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á

/x
1
+ µ
2
/x
2
+ … + µ
n
/x
n
}, trong đó các
giá trị µ
i
(i = 1, …, n) biểu thị mức độ thuộc của x
i
vào tập A.

Số hóa bởi Trung tâm Học liệu

5
Có nhiều dạng hàm thuộc để biểu diễn cho tập mờ A, mà trong đó dạng
hình thang, hình tam giác và hình chuông là thông dụng nhất. Sau đây là một
ví dụ về hàm thuộc đƣợc cho ở dạng hình thang.
Ví dụ cho A là một tập mờ, A có thể đƣợc biểu diễn dƣới dạng hình thang
với hàm thuộc liên tục

A
(x) nhƣ sau:
Rx
dx













 ,
,0
,
,1
,
,0
),,,;(


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.


(x) = 1.
1
a
c
b
d
µ
ASố hóa bởi Trung tâm Học liệu

6
Cho A là một họ các tập con của tập vũ trụ U và

 A. Một ánh xạ

: A
[0,) được gọi là độ đo mờ nếu thoả các điều kiện sau:
i)

(

) = 0,
ii) Nếu A, B  A và A  B thì

(A) 

(B).
1.1.2 Các phép toán đại số trên tập mờ

(x) = min{

A
(x),

B
(x)}}
Phép phủ định:
A
= {( x,
A

(x)) xU,
A

(x) = 1 –

A
(x)}
Rõ ràng ta có
A
 A   và
A
 A  U.
Cho A, B là hai tập mờ trên vũ trụ U và

A
,

B


A
(x).

B
(x)}
iii) Tổ hợp lồi
A
C
B = {( x,

AcB
(x)) x  U,

AcB
(x) = w
1
.

A
(x) + w
2
.

B
(x), w
1
+ w
2
= 1}

, , A
n
) được định nghĩa là tập mờ
f(A
1
, A
2
, , A
n
) = {((x
1
, , x
n
),

f
(x
1
, , x
n
)) (x
1
, , x
n
)  U
1
U
2
 U
n

Hàm N: [0,1]  [0,1] được gọi là hàm N-Negative khi và chỉ khi N thoả
mãn các điều kiện: với mọi x, y  [0,1]
i) N(0) = 1, N(1) = 0,
ii) N(x)  N(y), y  x.

Số hóa bởi Trung tâm Học liệu

8
1.1.3 Khử mờ
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:







,0,
)(
)(
1


đạt giá trị cực đại, khi đó:
k
x
x
k
i
i



1*
.
 Phƣơng pháp điểm giữa x
*
= (x
1
+ x
k
)/2.
Lƣu ý rằng khi chọn phƣơng pháp khử mờ chúng ta cần quan tâm đến
phƣơng pháp mờ hoá ban đầu.
1.2 Phƣơng pháp lập luận mờ đa điều kiện
1.2.1 Mô hình mờ
Mô hình mờ là một tập các luật có dạng đề “if-then”, trong đó phần “if”
đƣợc gọi là tiền đề còn phần “then” đƣợc gọi là phần kết luận. Mô hình mờ có
hai dạng:
Mô hình mờ dạng đơn giản là tập các luật (if-then) mà trong đó mỗi luật

Số hóa bởi Trung tâm Học liệu

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 X
1
= A
11
and and X
m
= A
1n
then Y = B
1
If X
1
= A
21
and and X
m
= A
2n
then Y = B
1
. . . . . . . . . . (1.2)

If X
1
= A
m1

10
Một trong số những phƣơng pháp lập nhƣ vậy là các phƣơng pháp lập luận
mờ đa điều kiện (Fuzzy Multiple Conditional Reasoning - FMCR) nhằm giải
quyết bài toán lập luận mờ đa điều kiện sau:
Cho trƣớc mô hình mờ ở dạng (1.1) hoặc (1.2). Khi đó ứng với các giá trị
(hoặc giá trị mờ, hoặc giá trị thực) của các biến đầu vào đã cho, hãy tính giá
trị của biến đầu ra Y.
Dựa trên cách tiếp cận của lý thuyết tập mờ, các phƣơng pháp lập luận mờ
đa điều kiện nói chung dựa trên ý tƣởng sau:
- Ngữ nghĩa của các giá trị ngôn ngữ của các biến ngôn ngữ trong mô hình
mờ đƣợc biểu thị bằng các tập mờ.
- Kết nhập các đầu vào của các luật mờ trong mô hình (nếu n > 1) để
chuyển mô hình mờ về mô hình đơn điều kiện.
- Từ các luật mờ dạng if – then xây dựng quan hệ mờ tƣơng ứng bằng các
phép kéo theo.
- Xây dựng quan hệ mờ tổng hợp từ các quan hệ mờ trên. Khi đó mỗi mô
hình mờ sẽ đƣợc mô phỏng bằng một quan hệ mờ hai ngôi R.
- Khi đó ứng với vectơ đầu vào A
0
, giá trị của biến đầu ra đƣợc tính theo
công thức B
0
= A
0
R, trong đó  là một phép hợp thành.
Ví dụ: Xét bài toán lập luận với mô hình đơn điều kiện chứa 2 luật
If X = A
1
then Y = B
1


Số hóa bởi Trung tâm Học liệu

11
V = { v
1
, v
2
}
B
1
= 1,0/v
1
+ 0,4/v
2
;
B
2
= 0,3/v
1
+ 0,8/v
2
;
Cho sự kiện X = A’ với A’ = 0,6/u
1
+ 0,9/u
2
+ 0,7/u
3
. Hãy tính B’

1
R














9.04.0
0.19.0
0.16.0
2
R

Ta lấy quan hệ mờ tổng hợp bằng cách lấy giao của 2 quan hệ trên








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/v
1
+ 0,7/v
2
.

Số hóa bởi Trung tâm Học liệu

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
B=[100 200 300]
B1=[0.7 0.2 0.8];

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 0.4000 0.3000
1.0000 0.8000 0.7000 0.4000 0.3000
1.0000 1.0000 1.0000 0.9000 0.8000
1.0000 0.7000 0.6000 0.3000 0.2000
Từ luật 2 ta xác định đƣợc quan hệ R2
1.0000 1.0000 1.0000 1.0000 1.0000
0.7000 1.0000 1.0000 1.0000 1.0000
0.5000 0.8000 0.9000 1.0000 1.0000
1.0000 1.0000 1.0000 1.0000 1.0000
0.7000 1.0000 1.0000 1.0000 1.0000
0.6000 0.9000 1.0000 1.0000 1.0000

Số hóa bởi Trung tâm Học liệu

14
R2=
1.0000 1.0000 1.0000 1.0000 1.0000
1.0000 1.0000 1.0000 1.0000 1.0000

Tính tập mờ đầu ra C0= A0B0oR với o là phéo hợp thành max-min, ta có:
C0=[0.60 0.90 0.90 0.60 0.50]

Số hóa bởi Trung tâm Học liệu

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

1
2




















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,
tức là miền giá trị của hầu hết các biến ngôn ngữ có cùng cấu trúc cơ sở theo


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.

Số hóa bởi Trung tâm Học liệu

18
1.3.2 Đại số gia tử của biến ngôn ngữ
Giả sử X là một biến ngôn ngữ và miền giá trị của X là Dom(X).
Một ĐSGT AX tương ứng của X là một bộ 4 thành phần AX=(Dom(X),
G, H,

) trong đó G là tập các phần tử sinh, H là tập các gia tử và quan hệ
“

” là quan hệ cảm sinh ngữ nghĩa trên X. [3]
Ví dụ X là tốc độ quay của một mô tơ thì Dom(X) = {fast, very fast,
possible fast, very slow, slow }{0, W, 1 }, G = {fast, slow, 0, W, 1 }, với 0,
W, 1 là phần tử bé nhất, phần tử trung hòa và phần tử lớn nhất tƣơng ứng,
H={very, more, possible, little}.
Trong ĐSGT AX = (Dom(X), G, H, ) nếu Dom(X), G và H là tập sắp thứ
tự tuyến tính thì AX đƣợc gọi là ĐSGT tuyến tính. Nếu không nhầm lẫn
chúng ta có thể sử dụng ký hiệu X thay cho Dom(X).
Cấu trúc AX đƣợc xây dựng từ một số tính chất của các phần tử ngôn ngữ.
Các tính chất này đƣợc biểu thị bởi quan hệ thứ tự ngữ nghĩa  của X. Sau
đây ta sẽ nhắc lại một số tính chất trực giác:
i) Hai phần tử sinh của biến ngôn ngữ có khuynh hƣớng ngữ nghĩa trái
ngƣợc nhau: fast có khuynh hƣớng “đi lên” còn gọi là hƣớng dƣơng ký hiệu