i
..

đại học thái nguyên
Tr-ờng đại học CÔNG NGHệ THÔNG TIN Và TRUYềN THÔNG

O TH MINH HON

XY DNG H LUT M MAMDANI
TỪ CƠ SỞ DỮ LIỆU SỐ

Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số

: 60.48.01

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

THÁI NGUYÊN - 2014

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

/>

ii

LỜI CAM ĐOAN
Tơi xin cam đoan đây 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 hồn tồn

chịu trách nhiệm trƣớc Hội đồng khoa học và trƣớc Pháp luật.
Thái Ngun, tháng 11 năm 2014
Tác giả

Đào Thị Minh Hồn

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

/>

iii

LỜI CẢM ƠN
Lời đầu tiên cho phép tôi bày tỏ lòng biết ơn sâu sắc tới TS. Trần Thái
Sơn – Viện Công Nghệ Thông Tin – Viện Hàn Lâm Khoa Học và Công Nghệ Việt
Nam đã giúp đỡ và chỉ dẫn tận tình cho tơi về định hƣớng đề tài, hƣớng dẫn tôi
trong việc tiếp cận và khai thác các tài liệu tham khảo cũng nhƣ chỉ bảo cho tôi
trong q trình tơi viết luận văn và hồn thành luận văn.
Tôi xin chân thành cảm ơn Ban giám hiệu, Khoa sau đại học trƣờng Đại
học Công Nghệ Thông Tin và Truyền Thông Thái Nguyên đã tạo mọi điều kiện
giúp tôi nghiên cứu và hoàn thành luận văn này.
Do điều kiện thời gian và phạm vi nghiên cứu có hạn, luận văn khơng
tránh khỏi những thiếu sót, tác giả luận văn kính mong nhận đƣợc sự chỉ dẫn và
góp ý thêm của các thầy giáo, cô giáo và các anh chị học viên để luận văn trở nên
hoàn thiện hơn.
Tác giả
Đào Thị Minh Hồn

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


/>

iv

MỤC LỤC
LỜI CAM ĐOAN ...................................................................................................... i
LỜI CẢM ƠN .......................................................................................................... iii
MỤC LỤC ................................................................................................................ iv
DANH MỤC CÁC HÌNH ...................................................................................... vi
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ..................................... vii
MỞ ĐẦU ................................................................................................................... 1
Chƣơng 1: TẬP MỜ VÀ GIẢI THUẬT DI TRUYỀN ........................................ 3
1.1. Tổng quan về tập mờ .................................................................................... 3
1.1.1. Mở đầu ................................................................................................................ 3
1.1.2. Kiến thức cơ sở về tập mờ ................................................................................. 3
1.1.3. Biến ngôn ngữ .................................................................................................... 8
1.1.4. Lôgic mờ ............................................................................................................. 9
1.1.5. Lập luận xấp xỉ ................................................................................................. 13

1.2. Giải thuật di truyền ...................................................................................... 17
1.2.1. Những khái niệm cơ bản về giải thuật di truyền ........................................... 17
1.2.2. Các tính chất đặc thù của thuật giải di truyền ................................................ 19
1.2.3. Các bƣớc quan trọng trong việc áp dụng giải thuật di truyền ...................... 20
1.2.4. Các phƣơng thức biến hoá của giải thuật di truyền....................................... 20

Chƣơng 2:: GIẢI BÀI TOÁN XÂY DỰNG HỆ LUẬT MỜ THEO CÁCH
TIẾP CẬN CỦA LÝ THUYẾT TẬP MỜ. ỨNG DỤNG VÀO BÀI TỐN
HỒI QUY MỜ......................................................................................................... 23
2.1. Bài tốn trích chọn luật mờ từ cơ sở dữ liệu ............................................. 23
2.1.1. Chuyển đổi CSDL số sang CSDL mờ: mục đích và phƣơng pháp giải. .... 24

2.1.2. Bài toán hồi quy mờ ......................................................................................... 24

2.2. Xây dựng hệ luật mờ từ CSDL - nhóm giải pháp 2 giai doạn. ............... 28
2.3. Xây dựng hệ luật mờ từ CSDL – nhóm giải pháp 1 giai doạn. .............. 36
Chƣơng 3:CHƢƠNG TRÌNH THỬ NGHIỆM................................................... 38
Số hóa bởi Trung tâm Học liệu

/>

v

3.1. Đặt bài tốn .................................................................................................. 38
3.2. Tìm kiếm hệ luật tối ƣu dựa trên giải thuật di truyền lai ......................... 39
3.3. Chƣơng trình ................................................................................................ 44
3.3.1. Cài đặt chƣơng trình......................................................................................... 44
3.3.2. Giao diện của chƣơng trình ............................................................................. 44

KẾT LUẬN ............................................................................................................. 53
TÀI LIỆU THAM KHẢO ..................................................................................... 54

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

/>

vi

DANH MỤC CÁC HÌNH
Hình 1.1: Đồ thị biểu diễn hàm thuộc của tập mờ già (old) ......................... 6
Hình 1.2: Mã hóa cá thể từ khơng gian các lời giải của bài tốn ................ 18
Hình 2.1: Các bộ phận của khơng gian đầu vào và đầu ra thành các vùng

mờ có chức năng thành viên tƣơng ứng. (a) rn(ri). (b) 01(12). (c) oi(y). .. 36
Hình 3.1: Sơ đồ mã hóa cá thể chọn hệ luật cho thuật toán SGA ............... 40

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

/>

vii

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Các kí hiệu,
các chữ viết tắt
U
A
A(x)

Ỹ

Ý nghĩa
Tập vũ trụ
Tập mờ
Ánh xạ từ U vào [0,1]
Là đầu ra mờ

FRBCS

Fuzzy Rule Based Classification Systems

CSDL


Cơ sở dữ liệu

GA

Giải thuật di truyền

MF

Hàm thuộc

FB

CSDL mờ

SGA

Thuật toán di truyền lai

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

/>

1

MỞ ĐẦU
Khai phá dữ liệu, rộng hơn là khai phá tri thức đã và đang thu hút sự chú ý
mạnh mẽ của các nhà nghiên cứu trên thế giới và ở Việt Nam. Do sự bùng nổ
thông tin trong mọi lĩnh vực của đời sống, địi hỏi phải có những phƣơng pháp
khoa học và cơng nghệ để khai thác có hiệu quả từ khối lƣợng thông tin khổng lồ
những tri thức cần thiết giúp cho con ngƣời hoạch định những chiến lƣợc, chính

sách cho xã hội. Hồi quy (regression), một trong những hƣớng nghiên cứu chính
trong khai phá dữ liệu, có nhiệm vụ từ những tập dữ liệu mẫu rút ra các quy luật
để dự báo mơ hình và kết quả có thể xẩy ra trong dữ liệu tƣơng lai. Hồi quy toán
học đã phát triển từ khá lâu và cũng đạt đƣợc nhiều kết quả tốt đẹp, tuy nhiên so
với u cầu thực tế thì vẫn cịn nhiều việc phải làm, nhƣ tăng tính chính xác của
mơ hình, giảm thời gian tính tốn đến mức tối thiểu, nghiên cứu các mối tƣơng
quan nhiều biến phức tạp... Với sự phát triển mạnh mẽ của công nghệ thông tin,
gần đây nhiều hƣớng nghiên cứu mới giải bài toán hồi quy đã ra đời, trong đó có
hƣớng nghiên cứu hồi quy mờ dựa trên hệ luật mờ đặc biệt đƣợc quan tâm do
tính hiệu quả kết hợp với độ chính xác khá cao của thuật toán, đáp ứng nhu cầu
khai thác dữ liệu mờ hiện nay. Hệ luật mờ Mamdani (MFRBS) bao gồm M luật
có dạng
Rm: IF X1 is

AND …AND XF is

THEN XF+1 is

(1)

m = 1, ..., M
Trong đó X = {X1,..., Xf,..., XF} là tập các biến ngôn ngữ đầu vào và XF+1 là biến
đầu ra.
Nhƣ vậy, MFRBS có đặc điểm khác các mơ hình khác là các biến đầu vào
và ra đều là mờ dƣới dạng từ của ngôn ngữ tự nhiên. Đặc điểm này mang lại tính
“thân thiện” với con ngƣời vì suy luận trên các từ của ngơn ngữ tự nhiên là đặc
điểm của con ngƣời. Các luật cũng đƣợc biểu diễn dƣới dạng quen thuộc với suy
nghĩ và lập luận của con ngƣời. Hiện tại MFRBS đƣợc nghiên cứu sử dụng rộng
rãi trong nghiên cứu ở các lĩnh vực điều khiển tự động, khai phá dữ liệu... Với
bài toán hồi quy mờ, MFRBS đƣợc coi nhƣ một biểu diễn xấp xỉ của một siêu

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

/>

2
mặt trong không gian M+1 chiều, cho phép với đầu vào là một vecto M chiều các
giá trị thực (hoặc ngơn ngữ) có thể suy ra giá trị đầu ra (giá trị số). Luận văn có
nhiệm vụ nghiên cứu tổng hợp và đề xuất giải pháp xây dựng một hệ luật mờ
Mamdani ứng dụng vào giải quyết bài toán hồi quy mờ trong thực tế.
Về bố cục, luận văn gồm phần mở đầu, 3 chƣơng, phần kết luận và tài liệu
tham khảo.
Phần mở đầu nêu mục đích yêu cầu và cách tiếp cận giải bài tốn hồi quy
mờ thơng qua hệ luật mờ Mandani theo cách tiếp cận lý thuyết tập mờ.
Chƣơng 1: Tập mờ và giải thuật di truyền
Trong chƣơng này trình bày các kiến thức cơ bản về tập mờ và giải thuật di
truyền.
Chƣơng 2: Giải bài toán xây dựng hệ luật mờ theo cách tiếp cận của lý
thuyết tập mờ. Ứng dụng vào bài toán hồi quy mờ
Đề xuất cách xây dựng hệ luật mờ Mandani và sử dụng hệ luật mờ này giải
quyết bài toán hồi quy mờ.
Chƣơng 3: Chƣơng trình thử nghiệm
Trình bày chƣơng trình thử nghiệm minh họa cho cách tiếp cận lý thuyết
tập mờ trong việc giải bài tốn hồi quy mờ.

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

/>

3


Chƣơng 1
TẬP MỜ VÀ GIẢI THUẬT DI TRUYỀN
1.1. Tổng quan về tập mờ
1.1.1. Mở đầu
Lý thuyết tập mờ đƣợc đề xuất bởi L. A. Zadeh năm 1965, và có lẽ đến nay
thuật ngữ “fuzzy” trở nên rõ ràng đối với các nhà nghiên cứu và các kỹ sƣ. Nó đã
và đang đƣợc tiếp tục nghiên cứu rất mạnh mẽ. Bằng các phƣơng pháp tiếp cận
khác nhau, các nhà nghiên cứu nhƣ Dubois, Prade, Mamdani, Tagaki, Sugeno,…
đã đƣa ra những kết quả cả về lý thuyết và ứng dụng trong các bài toán điều
khiển mờ, khai phá dữ liệu mờ, cơ sở dữ liệu mờ, các hệ hỗ trợ và quyết định....
Hệ suy diễn mờ áp dụng cho lập luận xấp xỉ đƣợc phát triển dựa trên lý
thuyết tập mờ, với những ràng buộc nhất định, đƣợc xem nhƣ là một bộ xấp xỉ vạn
năng. Hơn nữa, thế mạnh của hệ mờ là có thể xấp xỉ các hành vi hệ thống mà ở đó
các hàm giải tích hoặc các quan hệ dạng số khơng tồn tại. Vì vậy, hệ mờ có tiềm
năng to lớn để ứng dụng giải quyết các hệ thống phức tạp nhƣ hệ sinh học, hệ xã
hội, hệ kinh tế và hệ thống chính trị. Mặt khác, hệ mờ cịn có thể ứng dụng trong
các hệ thống ít phức tạp, ở đó khơng cần một giải pháp chính xác mà chỉ cần một
giải pháp xấp xỉ nhƣng nhanh hơn, hiệu quả hơn khi giảm chi phí tính toán.
1.1.2. 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. Ý 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 tốn học, đƣợc gọi là tập mờ và đƣợc định nghĩa nhƣ sau.
Định nghĩa 1.1. 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 A(x) mà nó liên
kết mỗi phần tử xU với một số thực trong đoạn [0,1]. Giá trị hàm A(x) biểu

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


/>

4
diễn mức độ thuộc của x trong A. A(x) là một ánh xạ từ U vào [0,1] và đƣợc gọi
là hàm thuộc của tập mờ A.
Nhƣ vậy, giá trị hàm A(x) càng gần tới 1 thì mức độ thuộc của x trong A
càng cao. Khi A là một tập hợp kinh điển, hàm thuộc của nó, A(x), chỉ nhận 2
giá trị 1 hoặc 0, tƣơng ứng với x có nằm trong A hay không. Rõ ràng, tập mờ là
sự mở rộng của khái niệm tập hợp kinh điển. Các khái niệm, phép toán trong lý
thuyết tập kinh điển cũng đƣợc mở rộng cho các tập mờ.
Họ tất cả các tập mờ trên miền cơ sở U là không gian các hàm từ U vào
đoạn [0,1], tức là F (U ,[0,1]) = {A : U[0,1]}, một không gian tƣơng đối giàu
về cấu trúc tính tố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={ui : 1i n}, ta có thể viết
A = A(u1)/u1 + A(u2)/u2 + … + A(un)/un = 1i nA(ui)/ui
- Trƣờng hợp U vô hạn đếm đƣợc, U={ui : i=1,2,… }, ta viết
A = 1i <A(ui)/ui
- Trƣờng hợp U vô hạn liên tục, U=[a,b], ta viết
b

A =   A (u ) / u
a

Sau đây ta định nghĩa một số khái niệm đặc trƣng liên quan đến tập mờ.
Định nghĩa 1.2. Cho một tập mờ A trên tập vũ trụ U và [0,1]. Tập lát cắt
 của A là một tập kinh điển, ký hiệu A, đƣợ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 1.3. 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}.
Số hóa bởi Trung tâm Học liệu

/>

5
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 xác
định nhƣ sau:
core(A) = {uU: A(u) = high(A)}.
Định nghĩa 1.4. Cho một tập mờ A trên tập vũ trụ U,
i) Lực lƣợng vô hƣớng hay bản số của tập mờ A, ký hiệu count(A),
đƣợc xác định là:
count(A) = uUA(u), nếu U là hữu hạn hay đếm đƣợc,
= UA(u)du, nếu U là vô hạn liên tụ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.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 [2] (hình 1.1):
u  [0, 60]

0

2

1
u  60

(1  ( 6 ) ) u  [61,120]

old (u )  

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

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

/>

6

Hình 1.1: Đồ thị biểu diễn hàm thuộc của tập mờ già (old)
Tiếp theo chúng ta định nghĩa một số phép toán cơ bản trên tập mờ, các
phép này làm cơ sở cho việc phát triển lơgíc mờ và lập luận xấp xỉ sau này.
Định nghĩa 1.5. Cho hai tập mờ A và B trên tập nền U có hàm thuộc tƣơng
ứng là A vàB, ba phép toán cơ bản là hợp, giao của hai tập mờ và lấy phần bù
của tập mờ A là một tập mờ C, đƣợc viết là
C = AB, hoặc C = AB, hoặc C = A~

với hàm thuộc đƣợc xác định nhƣ sau:

AB(u) = max(A(u), B(u)), uU,
AB(u) = min(A(u), B(u)), uU,
A~(u) = 1- A(u), uU.
Hay viết ở dạng thu gọn là

AB(u) = A(u)B(u)),
AB(u) = A(u) B(u)).
Ví dụ 1.2. Xét tập nền U = {1,2,3,4,5,6,8,9,10,11} là tập các giá trị trong
thang điểm 10 đánh giá kết quả học tập của học sinh. Hai tập mờ G và K 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.9

0.8

0.6

0.4

0.2

0.0

0.0

0.0

0.0

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

/>

7
Ta có kết quả của các phép tốn trên hai tập mờ này với hàm thuộc thể hiện
trong bảng sau:
1

2


3

4

5

6

7

8

9

10

GK(u) 0.0

0.0

0.0

0.6

0.5

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

0.9

0.7

0.5

0.3

0.1

0.0

0.0

uU

1.0

Một lớp đặc biệt các tập mờ là lớp các quan hệ mờ, chúng là các tập mờ
trên không gian tích Đề-các các miền cơ sở. Nhƣ tên gọi, quan hệ mờ mô tả mối
quan hệ mờ giữa các đối tƣợng trong miền cơ sở. Về mặt hình thức chúng ta định
nghĩa quan hệ mờ nhƣ sau.
Định nghĩa 1.6. Cho U là tích Đề-các của n miền cơ sở Ui, i=1, ,…, n. Khi
đó mỗi một tập mờ trên U đƣợc gọi là một quan hệ mờ n-ngôi và đƣợc kí hiệu là
R, gọi là tên của quan hệ đó, và nó đƣợc biểu thị bằng cơng thức sau:
R

U1 ...U n


 (u1 ,..., u1 ) / (u1 ,..., u1 )

Trong đó (u1,…,un) là hàm thuộc của tập mờ R. Dấu  biểu diễn hình thức
của hàm thuộc, có thể một trong ba trƣờng hợp là hữu hạn hoặc đếm đƣợc hoặc
liên tục.
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ờ. Ngồ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 1.7. 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 hố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.

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

/>

8
Ví dụ 1.3. Cho U = {u1, u2, u3}, V = {v1, v2} và W = {w1, w2}, với quan hệ
mờ R trên UV và S trên VW đƣợc cho hàm thuộc dƣới dạng ma trận
v1

v2

w1
w2

u1  0.4 1 
v
0.2
0.8

1 
R  u2  1 0.3 và S  
v2 0.7 0.1
u3 0.7 0.8 
w1

w2

u1  0.7 1 
khi đó phép hợp thành max-min là R  S  u2  0.3 0.8  ,
u3  0.7 0.7 
w1

w2

u1  0.8 0.32 
và max-product là R  S  u2  0.21 0.8  .
u3 0.56 0.56

Phép hợp thành các quan hệ mờ đóng vai trị quan trọng trong q trình lập
luận xấp xỉ sau này. Trong hầu hết các ứng dụng, tri thức đƣợc biểu diễn dƣới
dạng luật “if-then” và mỗi luật đƣợc xem nhƣ một quan hệ mờ
Chúng ta thấy rằng lý thuyết tập mờ với mục tiêu mơ hình hóa tốn học ngữ
nghĩa của các khái niệm mờ và, hơn nữa, mơ hình hóa cách lập luận của con
ngƣời. Tuy nhiên, những vấn đề này thuộc loại có cấu trúc yếu, khó có thể có

một cấu trúc tốn duy nhất mơ hình hóa trọn vẹn những vấn đề đó.
1.1.3. Biến ngơn ngữ
L. A. Zadeh đã viết “Khi thiếu hụt tính chính xác bề ngồi của những vấn
đề phức tạp cố hữu, một cách tự nhiên là tìm cách sử dụng các biến ngơn ngữ, đó
là các biến mà giá trị của chúng không phải là số mà là các từ hoặc các câu
trong ngôn ngữ tự nhiên hoặc nhân tạo. Động lực cho việc sử dụng các từ, các
câu hơn các số là ở chỗ đặc trưng ngơn ngữ của các từ và các câu thường ít xác
định cụ thể hơn của các số”, và ông đã đƣa ra một lớp khái niệm rộng hơn có thể
mơ hình qua các tập mờ, đó là biến ngơn ngữ.
Định nghĩa 1.8. Biến ngôn ngữ là một bộ năm (X,T(X),U,R,M), trong đó 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 hay còn gọi là miền cơ sở của biến X, R là một quy tắc ký pháp sinh các giá
Số hóa bởi Trung tâm Học liệu

/>

9
trị ngôn ngữ cho T(X), M là quy tắc gán ngữ nghĩa biểu thị bằng tập mờ trên U
cho các từ ngơn ngữ trong T(X).
Ví dụ 1.4. 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.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 tốn ngữ
nghĩa của các giá trị ngơn ngữ. Ngồi các giá trị sinh ngun 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,….

Trong thực tế có nhiều biến ngôn ngữ khác nhau về giá trị sinh nguyên
thủy, tuy nhiên cấu trúc miền giá trị của chúng tồn tại một “đẳng cấu” sai khác
nhau bởi giá trị sinh nguyên thủy này. Đây gọi là tính phổ quát của biến ngôn
ngữ.
Khác với giá trị nguyên thủy của các biến ngôn ngữ phụ thuộc vào ngữ
cảnh, ngữ nghĩa của các gia tử và các từ liên kết hoàn toàn độc lập với ngữ cảnh.
Đây là tính độc lập ngữ cảnh của gia tử và liên kết.
1.1.4. Lôgic mờ
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
Số hóa bởi Trung tâm Học liệu

/>

10
ngƣời rất phức tạp và do đó khơng thể sử dụng một cấu trúc tố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 trọng 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 1.9. Một hàm 2-biến T : [0,1][0,1]  [0,1] đƣợc gọi là phép tnorm 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 hố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)

Ngồ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:
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’) < T(b,b’)

Định nghĩa 1.10. Một hàm 2-biến S : [0,1][0,1]  [0,1] đƣợc gọi là phép
t-conorm nếu nó thỏa các tính chất sau với a,a’,b,c [0,1]:
i) Tính giới nội:


S(a,0) = a

ii) Tính giao hốn:

S(a,b) = S(b,a)

iii) Tính đơn điệu:

a a’S(a,b)  S(a’,b)

iv) Tính kết hợp:

S(a,S(b,c)) = S(S(a,b),c)

Nhƣ vậy, chỉ có hai tính chất điều kiện biên và giới nội làm nên sự khác
biệt giữa hai họ phép tính t-norm và t-conorm.
Chúng ta cũng có thể mở rộng định nghĩa cho phép t-norm và t-conorm này
đối với trƣờng hợp nhiều biến vào, tức là Tex:[0,1]n [0,1] và Sex : [0,1]n [0,1],
bằng cách áp dụng liến tiếp các phép t-norm và t-conorm ở trên.
Định nghĩa 1.11. Hàm N: [0,1]  [0,1] đƣợc gọi là phép phủ định
(negation) nếu nó thỏa các tính chất sau với a,a’ [0,1]:
Số hóa bởi Trung tâm Học liệu

/>

11
i) Tính đơn điệu giảm:
iv) Tính lũy đẳng:


a a’ N(a) N(a’)

N(N(a)) = a

Ví dụ 1.5. Các phép t-norm, t-conorm và phép phủ định hay đƣợc sử dụng nhƣ:
TM(a,b) = min{a,b}
TP(a,b) = a.b
TL(a,b) = max{0,a+b-1}
a

T (a, b)  b
0

*

khi b  1
khi a  1
khi a  1& b  1

SM(a,b) = max{a,b}
SP(a,b) = a+b-a.b
SL(a,b) = min{1,a+b}
a

S (a, b)  b
0

*

khi b  0

khi a  0
khi a  0 & b  0

N(a) = 1-a.
Định nghĩa 1.12. Ba phép tính t-normT, t-conorm S và phép phủ định N
đƣợc gọi là một hệ đối ngẫu (T,S,N) nếu chúng thỏa điều kiện sau:
N(S(a,b)) = T(N(a),N(b)), a,b[0,1].
Việc áp dụng các phép t-norm, t-conorm và phép phủ định cho việc tính
tốn các tốn tử hội, tuyển và phủ định trong lôgic mờ làm tăng tính mềm dẻo
trong ứng dụng. Thực vậy, khi hai mệnh đề “X is A” và “X is B” có giá trị chân lý
đƣợc biểu thị bởi hai hàm thuộc tƣơng ứng 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(A), ở đây S là một t-conorm và N là một phép phủ định đƣợc chọn nào đó.
Các mệnh đề mờ cùng với giá trị chân lý của chúng là những đối tƣợng
nghiên cứu chính của lơgíc mờ. Trong đó, một dạng mệnh đề mờ thƣờng biểu
Số hóa bởi Trung tâm Học liệu

/>

12
diễn cho tri thức dạng luật trong lập luận xấp xỉ và ứng dụng, đó là mệnh đề mờ
có điều kiện dạng “If X is A then Y is B” và đƣợc biểu diễn bằng toán tử kéo theo
mờ. Ở đây, một cách tổng quát, chúng ta đƣa ra một số tính chất cho một phép
kéo theo mờ.
Định nghĩa 1.13. Phép kéo theo là một hàm số I : [0,1]2 [0,1] có các tính
chất sau:
i) Tính đơn điệu giảm đối với biến thứ nhất

x zI(x,y)  I(z,y), y[0,1]
ii) Tính đơn điệu tăng đối với biến thứ hai
y uI(x,y)  I(x,u), x[0,1]
iii) Tính chi phối của giá trị chân lý sai
I(0,x) = 1
iv) Tính trung tính của giá trị chân lý đúng
I(1,x) = x
v) Tính đồng nhất
I(x,x) = x
vi) Tính chất hốn đổi
I(x,I(y,z)) = I(y,I(x,z))
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.
Ví dụ 1.6. Một số dạng phép kéo theo thƣờng dùng
 Mamdani
Số hóa bởi Trung tâm Học liệu

/>

13
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 tnorm, t-conorm và phép phủ định.
 Reichenbach
I(x,y) = 1-x+x.y
 Lukasiewicz
I(x,y) = min{1, 1-x+y}.
Một cách tiếp cận khác, phép kéo theo đƣợc định nghĩa thông qua phép tnorm bằng công thức sau:
I(x,y) = sup{ u[0,1] : T(x,u)  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 1.13.
Đị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) đến
ix) trong định nghĩa 1.13 nếu và chỉ nếu có tồn tại một hàm liên tục đơn điệu tăng
thực sự f : [0,1]  [0,+) sao cho f(0) = 0 và
I(x,y) = f-1(f(1)-f(x)+f(y)), với x,y  [0,1], và
N(x) = f-1(f(1)-f(x)), với x [0,1].
Tuy nhiên, bản chất ngữ nghĩa của phép kéo theo mờ trong lập luận của con
ngƣời rất phức tạp, khó có một hệ tiên đề chung cho mọi tình huống. Vì vậy, các
tính chất ở định nghĩa 1.13 khơng bắt buộc mọi phép kéo theo mờ đều phải thỏa
mãn. Hơn nữa, cũng khơng có quyền đặt ra các u cầu về một tính chất nào đó
khác mà một phép kéo theo cần phải có. Chỉ có ứng dụng thực tiễn là tiêu chuẩn
cuối cùng chứng minh tính phù hợp của một định nghĩa phép kéo theo mờ.
1.1.5. Lập luận xấp xỉ
Trong nghiên cứu của mình, L. A. Zadeh lần đầu đề xuất khái niệm lập luận
xấp xỉ phỏng theo cách lập luận của con ngƣời. Nó là q trình tìm kiếm kết luận
Số hóa bởi Trung tâm Học liệu

/>

14
từ một tập các tri thức dạng luật (biểu diễn bằng mệnh đề có điều kiện) và các sự

kiện, dựa trên lý thuyết tập mờ. Đặc trƣng của lập luận xấp xỉ là yếu tố không
chắc chắn, gần đúng và tính khơng duy nhất của kết quả thu đƣợc. Rõ ràng, tri
thức càng đầy đủ thì kết luận càng phù hợp với thực tiễn hơn.
Các quy tắc suy diễn trong lơgíc mờ dùng cho việc lập luận xấp xỉ đƣợc mở
rộng từ các quy tắc trong lôgic kinh điển nhƣ modus ponens, modus tollens, tam
đoạn luận (syllogism),…
Ở đây chúng ta xét trƣờng hợp lập luận mờ đa điều kiện, tức là phƣơng
pháp lập luận dựa vào nhiều luật, đƣợc áp dụng rộng rãi trong ứng dụng thực
tiễn. Hơn nữa, mỗi luật bao gồm nhiều biến ngôn ngữ tham gia trong phần tiền tố
và liên kết lơgíc với nhau bằng phép AND. Đây đƣợc gọi là mơ hình lập luận mờ
nhiều đầu vào một đầu ra (MISO).
Phƣơng pháp này đƣợc mô tả bằng sơ đồ sau:
Tiền đề 1 : If X1 is A1,1 AND…AND XN is A1,N then Y is B1
Tiền đề 2 : If X1 is A2,1 AND…AND XN is A2,N then Y is B2
………………………
Tiền đề n : If X1 is AM,1 AND…AND XN is AM,N then Y is BM
Sự kiện:

X1 is A1’ AND…AND XN is AN’


Kết luận :

Y is B’

Trong đó X1, X2,…, Xnvà Y là các biến ngơn ngữ, N là số biến vào và M là
số luật mờ, Ai,j (i=1,…,M và j=1,…,N) là các tập mờ trên khơng gian nền U1,
U2,…,Un và V tƣơng ứng. Tìm đƣợc tập mờ B’ có nghĩa là chúng ta đã lập luận từ
sự kiện X1 is A1’ AND … AND XN is AN’ dựa trên các tiền đề dạng luật If X1 is
Ai,1 AND… AND XN is Ai,N then Y is Bi (i=1,…,M).

Vì rằng chúng ta đang ở trong mơi trƣờng thơng tin mờ, khơng chắc chắn,
nên sẽ khơng có một phƣơng pháp lập luận chính xác và duy nhất. Mỗi phƣơng
pháp sẽ xuất phát từ một quan sát trực quan nào đó.

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

/>

15
Áp dụng quy tắc modus ponens tổng quát hóa, chúng ta xét mỗi luật mờ
nhƣ là một quan hệ mờ Ri trên khơng gian tích Đề-các U1…UnV có dạng:
Ai,1… Ai,n Bi,
trong đó,  là phép hợp của các tập mờ và  là phép kéo theo mờ. Áp dụng một
toán tử t-norm Tex mở rộng cho phép hội  và một phép kéo theo I nào đó, ta có
hàm thuộc của quan hệ mờ trên là

Ri  I (Tex ( Ai ,1 ,...,  Ai ,N ), Bi )

(1.1)

Mơ hình mờ ở đây đƣợc coi là tuyển của các luật, do vậy áp dụng phép hội
để kết nhập các quan hệ mờ Ri ở trên bằng toán tử t-conorm Sex mở rộng nhƣ sau:
R = R1… RN,
với  là phép hợp của các tập mờ, hay hàm thuộc của nó là
R  Sex (R ,..., R ) .
1

(1.2)

M


Áp dụng quy tắc suy diễn hợp thành, ta có kết quả tập mờ B’ sẽ là
B’ = (A1’ … AN’) R,
với  là phép hợp thành (định nghĩa 1.7) của tập mờ hợp các sự kiện A1’… 
AN’ và R. Cũng áp dụng phép t-norm Tex mở rộng để tính hợp các tập mờ sự kiện,
hàm thuộc của tập mờ B’ trong trƣờng hợp tổng quát là

B ' (v) 

sup

(u1 ,...,uN )U1...U N

T (
ex

A1'



(u1 ),...,  A' (uN ))  R (u1,..., uN , v)
N

(1.3)

Từ các công thức (1.1), (1.2) và (1.3) viết dạng thu gọn của hàm thuộc tập
mờ B’ nhƣ sau:

B ' (v)  sup


(u1 ,...,u1 )U



N
j 1





 A (u j )   iM1 I ( Nj 1 A (u j ), B (v)) 
'
j

 

i, j

i

(1.4)

với U = U1…UN ,  là ký hiệu của phép t-norm Texmở rộng N ngôi và  là ký
hiệu phép t-conorm Sex mở rộng N ngôi. Phép  là min, hoặc product, hoặc một
phép tính 2-ngơi trong [0,1] có tính giao hốn, kết hợp và phân phối đối với phép
max .

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


/>

16
Rõ ràng, trong công thức (1.4) với nhiều cách chọn các phép t-norm, tconorm và negation cũng nhƣ phép kéo theo I do vậy có nhiều cách xác định
hàm thuộc của tập mờ B’, dẫn đến kết quả lập luận cũng khác nhau. Điều này
phù hợp với đặc trƣng của lập luận xấp xỉ. Cách chọn các phép trên nhƣ thế nào
để có một phƣơng pháp lập luận tốt. Nói chung khơng có câu trả lời khẳng định
mà phụ thuộc vào từng tình huống ứng dụng cụ thể và đƣợc kiểm chứng qua kết
quả thực nghiệm.
Công thức (1.4) cũng cho thấy một ánh xạ từ các tập mờ đến tập mờ thông
qua phƣơng pháp lập luận xấp xỉ trên, và đƣợc biểu diễn hình thức nhƣ sau:
B’ = F(A1’,…,AN’)

(1.5)

Đặc biệt, các tác giả cho thấy rằng với những ràng buộc nhất định, hệ mờ
theo phƣơng pháp lập luận nhƣ trên đóng vai trị nhƣ một bộ xấp xỉ vạn năng.
Dựa trên định lý nổi tiếng của Stone-Weierstrass, Wang (1994) đã chứng tỏ đƣợc
khả năng xấp xỉ của hệ mờ bằng định lý sau.
Định lý 1.2. Với một hàm thực liên tục f trên tập compactU RN và bất kỳ

, luôn tồn tại một hệ lơgíc mờ F với phƣơng pháp giải mờ trọng tâm (COG),
phép suy diễn mờ dạng tích, hàm mờ hóa dạng đơn tử và hàm thuộc của tập mờ
dạng Gauss thỏa mãn,
|F(X) – f(X)| 

(1.6)

với X = (x1,…,xN) RN là các giá trị đầu vào của hệ.
Định lý này cho thấy mọi hàm thực liên tục trên một tập compact có thể

đƣợc xấp xỉ với độ chính xác tùy ý bởi một hệ mờ F. Tuy nhiên, nó mới chỉ ra có
tồn tại một hệ mờ nhƣ vậy nhƣng không cho biết rõ tham số của hệ. Bắt buộc
chúng ta phải xây dựng một chiến lƣợc tìm kiếm và thiết lập các yếu tố này.
Chẳng hạn sử dụng cơ chế học của mạng nơron, hoặc tối ƣu theo giải thuật di
truyền để thực hiện điều này.

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

/>

17
1.2. Giải thuật di truyền
1.2.1. Những khái niệm cơ bản về giải thuật di truyền
Thế giới mà chúng ta thấy ngày hơm nay, trong đó có rất nhiều lồi khác
nhau, với sự thích nghi cao theo mơi trƣờng sống và sự cân bằng sinh thái, là sản
phẩm của 3 tỷ năm tiến hóa, một q trình dựa trên sự sinh sản hữu tính và vơ
tính, chọn lọc tự nhiên, đột biến,… Nếu nhìn vào bên trong chúng ta thấy sự
phức tạp và khả năng thích nghi của các lồi có đƣợc bằng việc cải tiến và kết
hợp các gen qua một quá trình rất dài. Giải thuật di truyền (genetic algorithm –
GA), đƣợc đề xuất bởi J. H. Holland (1967), là sự mơ phỏng q trình tiến hóa.
Tuy nhiên, ở một góc độ khác, giải thuật di truyền chính là phƣơng pháp tối ƣu
theo xác suất dựa trên nguyên lý tiến hóa. Đến nay đã đƣợc nhiều tác giả nghiên
cứu phát triển và ứng dụng, kết hợp với nhiều mô hình khác.
Xét ở góc độ GA là một phƣơng pháp tối ƣu, khi đó, một bài tốn tối ƣu
đƣợc phát biểu tổng quát nhƣ sau:
Tìm một x0∈X sao cho f đạt max tại x0, trong đó f : X → R là một hàm thực
bất kỳ, tức là : f(x0) = maxx∈X f(x)
Thực tế, một số trƣờng hợp việc tối ƣu tồn cục là rất khó và đơi khi là
khơng thể theo cách giải quyết tốn học thơng thƣờng. Vì vậy, tùy theo bài toán
mà chúng ta quan tâm đến giá trị của x sao cho hàm mục tiêu f càng cao càng tốt.

Khơng gian tìm kiếm X đƣợc xem nhƣ mơi trƣờng (hay cịn gọi là quần thể) bao
gồm các cá thể (individuals) cạnh tranh với nhau, trong đó hàm f ánh xạ mỗi cá
thể một độ phù hợp (fitness).
Với việc mơ phỏng q trình tiến hóa, GA duy trì một quần thể các lời giải
có thể của bài toán tối ƣu và khi thực thi, các lời giải này tiến gần đến lời giải
mong muốn. Thông thƣờng, các lời giải đƣợc mã hóa dƣới dạng chuỗi gen theo
một cú pháp cho trƣớc và đƣợc gán một giá trị độ phù hợp thông qua hàm f.
Định nghĩa 1.14 : Giả sử S là tập các chuỗi dƣới dạng không tầm thƣờng và
có cú pháp. Đặt X là khơng gian tìm kiếm của bài tốn tối ƣu, khi đó hàm
c:X→S
x → c(x)
đƣợc gọi là hàm mã hóa. Ngƣợc lại, hàm
c : S → X
s → c (s)
Số hóa bởi Trung tâm Học liệu

/>

18
đƣợc gọi là hàm giải mã.
Nhƣ vậy, thông qua mã hóa, mỗi phƣơng án trong X thành một cá thể trong
S, chúng ta tìm một s0 ∈S sao cho f = f 0 c càng lớn càng tốt.

c

Không gian lời giải -X

Khơng gian cá thể mã hóa -S

Hình 1.2: Mã hóa cá thể từ khơng gian các lời giải của bài toán

Thuật toán: Cấu trúc cơ sở của một giải thuật di truyền
Bước 1: Đặt t = 0 và tính toán quần thể xuất phát B0.
Bước 2: Kiểm tra điều kiện dừng theo hàm đánh giá fitness f, nếu
chƣa thỏa mãn sang bƣớc tiếp theo, ngƣợc lại dừng
thuật toán.
Bước 3: Chọn lọn (selection) các cá thể trong Bt làm bố mẹ
(parent) để lai ghép.
Bước 4: Thực hiện lai ghép (crossover) các cá thể bố mẹ tạo
thành các cá thể con (offspring).
Bước 5: Đột biến (mutation) trên các cá thể con.
Bước 6: Tái tạo (reproduction) từ các cá thể con và bố mẹ tạo ra
quần thể mới.
Bước 7: Tăng chỉ số thế hệ t lên 1 và lặp lại bƣớc 2.

Theo thuật tốn, mỗi lần tiến hóa là việc chuyển từ một thế hệ này sang một
thế hệ khác, với hy vọng tốt hơn dựa trên hàm đánh giá f. Quá trình này bao gồm
4 phép cơ bản (gọi là tốn tử gen) sau:

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

/>