1

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TT & TT
ĐÀO NGỌC TUẤT
KẾT HỢP GIẢI THUẬT DI TRUYỀN VÀ LOGIC MỜ
GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH


Thái Nguyên, tháng 10 -2012
3

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

MỞ ĐẦU
Nhiều bài toán tối ưu trong thực tế là bài toán tối ưu đa mục tiêu, đặc biệt
là trong thiết kế. Chẳng hạn người ta muốn thiết kế sản phẩm sao cho chi phí
thấp, tiết kiệm nguyên liệu nhưng chất lượng tốt, hoặc thiết kế một bể chứa
nước với yêu cầu dung lượng lớn mà chi phí thấp…. Đã có nhiều nhà toán học
và tin học đã nghiên cứu về vấn đề này và đưa ra nhiều phương pháp giải khác
nhau. Một số những phương pháp thường được sử dụng để giải bài toán đa
mục tiêu như: phương pháp nhượng bộ dần, phương pháp tìm nghiệm có
khoảng cách ngắn nhất đến nghiệm lý tưởng, phương pháp trọng số,….
Được sự đồng ý của Hội đồng Khoa học khoa Công Nghệ Thông Tin,
cùng sự hướng dẫn của thầy giáo Vũ Mạnh Xuân, em chọn đề tài khóa
luận của mình nhằm nghiên cứu một phương pháp tiếp cận khác để giải
bài toán tối ưu đa mục tiêu là sử dụng giải thuật di truyền kết hợp logic
mờ.
Mục đích nghiên cứu: tìm hiểu một số phương pháp giải bài toán tối ưu

(GA) làm cơ sở cho việc ứng dụng giải bài toán tối ưu đa mục tiêu.[2], [6]
1.1. Khái quát chung
Giải thuật di truyền GA(GENETIC ALGORITHM) do D.E. Goldberg
đề xuất, sau đó được L. Davis và Z. Michalevicz phát triển, đây cũng chính là
một trong các thuật toán tiến hóa. Thuật toán tiến hóa là các chương trình máy
tính có dùng các thuật toán tìm kiếm, tối ưu hóa dựa trên nguyên lý tiến hóa
tự nhiên.
Giải thuật di truyền được hình thành dựa trên quan niệm: quá
trình tiến hóa tự nhiên là quá trình hoàn hảo và hợp lý nhất, tự quá trình này
đã mang tính tối ưu. Quan niệm này là một tiên đề đúng, không chứng minh
được nhưng phù hợp với thực tế khách quan. Tính tối ưu của quá trình tiến
hóa thể hiện ở đặc điểm, thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn
thiện hơn) thế hệ trước. Tiến hóa tự nhiên được duy trì nhờ hai quá trình cơ
bản là sinh sản và chọn lọc tự nhiên, trong suốt quá trình tiến hóa tự nhiên,
các thế hệ mới luôn được sinh ra để bổ sung thay thế thế hệ cũ. Cá thể nào
phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại, cá thể nào không thích
ứng được với môi trường sẽ bị đào thải. Sự thay đổi của môi trường là động
lực thúc đẩy quá trình tiến hóa, ngược lại tiến hóa cũng tác động trở lại góp
phần thay đổi môi trường.
Giải thuật di truyền (GA-Genetic Algorithms) là giải thuật tìm kiếm,
chọn lựa các giải pháp tối ưu để giải quyết các bài toán thực tế khác nhau, dựa
trên cơ chế chọn lọc của tự nhiên: từ tập lời giải ban đầu, thông qua nhiều
bước tiến hoá, hình thành tập lời giải mới phù hợp hơn, và cuối cùng dẫn đến
lời giải tối ưu toàn cục.
Trong tự nhiên, mỗi cá thể muốn tồn tại và phát triển phải thích nghi
5

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

với môi trường, cá thể nào thích nghi hơn thì tồn tại, cá thể nào kém thích

Ví dụ: Biểu thức sau x+(y / 5) được mã hoá thành: Mã hoá số thực : Mỗi NST được mã hoá là một véc tơ trong không gian R
m

chẳng hạn X = (a
1
, a
2
, , a
m
) với các a
i
 R. Cách mã hoá này thường tự nhiên
đối với các bài toán tối ưu số và được phát triển rất mạnh trong thời gian gần
đây.
1.2.2. Tạo lập lời giải ban đầu (khởi tạo quần thể)
Tập lời giải ban đầu thường được khởi tạo ngẫu nhiên từ miền xác định của
các lời giải. Cách tạo lập tập lời giải ban đầu phụ thuộc rất nhiều vào cách mã
hoá NST.
Với phương pháp mã hoá nhị phân: xây dựng NST bằng cách tạo ngẫu nhiên
chuỗi các bit 0 hoặc 1.
Với phương pháp mã hoá thứ tự: xây dựng NST ban đầu bằng cách hoán vị
ngẫu nhiên các thứ tự.
Với phương pháp mã hoá theo giá trị: tạo ngẫu nhiên từng giá trị trong miền
xác định của lời giải để tạo ra chuỗi NST ban đầu.

Chọn theo trọng số: tạo trọng số tích luỹ cho M NST theo công thức:



M
k
i
k
i
p
1
(với bài toán tìm min)




M
k
i
k
iM
p
1
1
(với bài toán tìm max)
Sau khi có trọng số tích luỹ cho NST, ta lần lượt tạo các xác suất ngẫu nhiên r
và duyệt từ NST đầu tiên đến khi gặp NST có trọng số tích luỹ lớn hơn r thì
chọn nó.
Bước 2: Sau khi chọn được N NST, lần lượt lấy ra từng cặp NST để lai ghép
tạo ra hai NST mới. Một số dạng toán tử lai ghép hay dùng là :

3. Khi (điều kiện dừng chưa thỏa mãn) lặp
t:=t+1;
Tái sinh P
‟
(t) từ P(t)
Lai Q(t) từ P(t-1);
Đột biến R(t) từ P(t-1);
Chọn lọc P(t) từ P(t-1)Q(t)R(t)P
‟
(t)
Kết thúc lặp
Cá thể tốt nhất P(t) là lời giải cần tìm
End.
9

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1.4. Giải thuật di truyền mã hóa số thực
1.4.1. Mã hóa RCGA
Trong phần này ta quan tâm tới giải thuật di truyền mã hóa số thực
(RCGA) để giải các bài toán tối ưu giá trị thực trong không gian R
n
và không
có các ràng buộc đặc biệt.
Một cách tổng quát, bài toán tối ưu số thực có thể xem là một cặp (S,f),
trong đó S  R
n
và f : S  R là một hàm n biến. Bài toán đặt ra là tìm véctơ
x=(x
1

nhau của toán tử lai ghép trong RCGA. Dưới đây là một số dạng toán tử lai
ghép thường dùng với giả thiết cặp cá thể cha mẹ đã chọn để tiến hành lai
ghép là
), ,,(
21 m
xxxX 
và
), ,,(
21 m
yyyY 
.
 Lai số học (Arithmetic Crossover)
Phép lai này chọn một số thực a (0<a<1); các con X' và Y' được tính bởi:
x'
i
= a*x
i
+ (1-a)*y
i
;
10

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

y'
i
= a*y
i
+ (1-a)*x
i

i
x
.
Đột biến biên: Từ cá thể cha đã chọn đột biến x và vị trí chọn đột biến k,
thành phần thứ k (x
k
) của x được thay bởi l
k
hay u
k
trong đó [l
k
, u
k
] là khoảng
xác định của x
k
. Trong những bài toán mà biên của các biến không lớn và giải
pháp cần tìm nằm gần biên thì phép đột biến này tỏ ra rất hữu ích.
Đột biến không đều:
Giả sử t
max
là một số cực đại định nghĩa trước, thành phần x
i
được thay
thế bởi một trong 2 giá trị tính theo các công thức sau :
x‟
i
= x
i

bố của đột biến trong miền [0, x].
1.5. Mô hình Markov của giải thuật di truyền.
11

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Trong giải thuật di truyền, mỗi quần thể được tạo sinh có đặc trưng là
chỉ phụ thuộc theo xác suất vào quần thể trước đó, do vậy GA có thể được mô
hình hóa bởi một xích Markov. Các tính chất của quần thể hữu hạn, chẳng hạn
như xu hướng di truyền có thể được khảo sát cẩn thận sử dụng xích Markov
hữu hạn. Không giống như nhiều phương pháp mô phỏng khác, xích Markov
có thể mô tả chính xác và chi tiết cho mỗi lớp đặc biệt. Từ năm 1992, Nix và
Vose đã mô hình hóa GA kinh điển (biểu diễn chuỗi nhị phân chiều dài cố
định, lai ghép một điểm, chọn lọc tỷ lệ) như một xích Markov trong đó mỗi
trạng thái là một quần thể. Vose đã mở rộng mô hình này đến mô hình “tìm
kiếm ngẫu nhiên Heuristic” trong đó mỗi cá thể của lần tạo sinh kế tiếp được
chọn theo một phân bố xác suất trên các cá thể của không gian tìm kiếm.
Suzuki đã giới thiệu mô hình của một lớp giải thuật di truyền ưu tú và đưa ra
kết quả về số lần tạo sinh cần thiết để hội tụ dựa trên xác suất đột biến. Năm
1996, Aytug và Koehler đưa ra chặn trên cho số lần tạo sinh cần thiết đối với
GA kinh điển để hội tụ đến quần thể có chứa chuỗi tối ưu dựa trên xác suất đột
biến.
Phần dưới đây trình bày vắn tắt mô hình xích Markov của giải thuật di
truyền đơn giản
1.5.1. Tính Markov
 Một hệ vật lý hoặc hệ trạng thái nào đó gọi là có tính Markov nếu sự
tiến triển của hệ trong tương lai chỉ phụ thuộc vào hiện tại và độc lập với
quá khứ. VD sự tăng dân số.
 Ký hiệu E là không gian trạng thái của X(t); nếu X(t) có tính Markov
và E là tập đếm được thì X(t) gọi là xích Markov. Nếu giá trị của thời điểm


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

 Đặt p(s,i,t,j) = P {X(t) = j | X(s) = i} (s<t) là xác suất có điều kiện để hệ tại
thời điểm s ở trạng thái i, đến thời điểm t chuyển đến trạng thái j và gọi là
xác suất chuyển của hệ. Nếu xác suất này chỉ phụ thuộc vào t-s hay
p(s,i,t,j) = p(s+h, i, t+h, j) thì hệ là thuần nhất theo thời gian.
 Ký hiệu p
ij
= P {X
n+1
= j | X
n
= i} và ma trận [p
ij
] gọi là ma trận xác
suất chuyển sau 1 bước. Theo công thức xác suất đầy đủ ta có
0  p
ij
 1 và 
j
p
ij
= 1 (ma trận ngẫu nhiên)
 Xác suất chuyển sau n bước :
p
ij
(n)
= P {X
n+m

n
jk
n
ik
mn
ij
ppp
)(
(1.1)

 Một ví dụ về GA được mô hình hóa bởi một xích Markov: Ta bắt đầu bằng
mô hình đơn tử (haploid model) của sự tái tạo ngẫu nhiên, khi không xét
đến những tác nhân đột biến và thiên hướng chọn lọc (mutation pressures
and selective forces). Giả sử ta xét cỡ loài cố định gồm 2N gene kết hợp từ
các cá thể loại a và loại A. Sự hình thành thế hệ sau được xác định bởi 2N
phép thử nhị thức độc lập như nhau: Nếu loài bố mẹ có j a-gene và (2N - j)
A-gene thì mỗi phép thử có kết quả là a hay A với xác suất tương ứng là

2
j
j
p
N

và
N
j
q
j
2

13

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Chú ý rằng các trạng thái X
n
= 0 (hoặc 2N) là hấp thụ hoàn toàn theo
nghĩa khi X
n
= 0 (hoặc 2N) thì X
n+k
= 0 (hoặc 2N, tương ứng) với mọi k  0.
Một trong những vấn đề thú vị là xác định xác suất để loài sẽ đạt tới
fixation (nghĩa VN) với điều kiện X
0
= i, tức là nó sẽ trở thành một quần thể
thuần chủng chỉ có a-gene hoặc A-gene. Việc xác định tốc độ đạt tới fixation
cũng là điều đáng quan tâm. Ta sẽ nghiên cứu những vấn đề như thế trong
phân tích tổng quát về xác suất hấp thụ.
Một mô hình đầy đủ hơn phải tính đến những mutation pressures (tác
nhân đột biến). Ta giả sử rằng trước khi hình thành thế hệ mới, mỗi gene có
xác suất đột biến, tức là xác suất chuyển thành gene của loại kia. Đặc biệt, ta
giả sử rằng đối với mỗi gene hiện tượng đột biến a  A xảy ra với xác suất x
1

và hiện tượng đột biến A  a xảy ra với xác suất x
2
.
Một lần nữa ta lại giả sử rằng sự hình thành của thế hệ sau được xác
định bởi 2N phép thử nhị thức. Các giá trị liên quan của p

(1.3)
Lập luận như sau: các tác nhân đột biến hoạt động đầu tiên, sau đó một
gene mới được chọn bằng cách chọn lọc ngẫu nhiên từ loài. Bây giờ xác suất
của chọn lọc một a-gene sau khi tác nhân đột biến hoạt động chính là 1/2N lần
số a-gene hiện có. Vì vậy xác suất trung bình (lấy trung bình đối với những
đột biến có thể) là 1/2N lần số trung bình của a-gene sau đột biến. Nhưng số
trung bình này rõ ràng là j(1-x
1
) + (2N - j)x
2
. Từ đó dẫn đến công thức (1.3).
Xác suất chuyển của xích Markov tương ứng được tính bởi công thức
(1.2) ở trên với các p
j
, q
j
được tính bởi công thức (1.3) vừa viết.
Nếu x
1
, x
2
> 0 thì fixation sẽ không xảy ra ở bất cứ trạng thái nào. Thay
vào đó, khi n   hàm phân phối của X
n
sẽ tiến đến phân phối trạng thái vững
của biến ngẫu nhiên  trong đó P{=k}=
k
; k = 0, 1, , 2N (
k
= 1, 


2
)1(
và q
j
= 1 - p
j
rồi xây dựng
thế hệ sau theo mẫu nhị thức như trước.
Nếu thế hệ cha mẹ có j a-gene, thì ở thế hệ sau cỡ loài trung bình của a-
gene và A-gene tương ứng là
 
sjN
js
N


2
1
2
và
 
sjN
jN
N


2
2
2

A
a

Điều này giải thích ý nghĩa của sự chọn lọc.

1.5.2. Một số kết quả
- Phân phối của hệ tại thời điểm n cho bởi công thức
p
j
(n)
= P(X
n
= j) ; n = 0, 1, 2, …; j  E
Đặt 
(n)
= {p
j
(n)
; jE) và gọi 

= 
(0)
là phân phối ban đầu của hệ.
- Phân phối ban đầu gọi là dừng nếu 
(n)
không phụ thuộc vào n
nghĩa là 

= 
(n)

j
=

Ek
kjk
px
; j  E
sao cho 
j
= 1 được gọi là phân phối dừng (hay bất biến) của xích
Markov với ma trận xác suất chuyển P = (p
ij
).
Ý nghĩa: Nếu ta lấy (
1
, ,
N
) là phân phối ban đầu của xích Markov,
tức là 
j
= P(X
0
= j); j = 1, 2, , N. Khi đó: 
j
(1)
= P(X
1
=j)=
j
k

11 21 1 1 1
12 22 2 2 2
12

N
N
N N NN N N
p p p
p p p
p p p



    
    
    

    
    
    
.

1.5.3. Xích Markov trong GA
Xét bài toán: Cho một hàm f : J  R
+
và J
L





r
h
ik
khZhf
kiZif
p
0
),(*)(
),(*)(

trong đó Z(i,k) là biến cố xảy ra khi cá thể i thuộc vào quần thể k.
- Toán tử lai ghép một điểm.
- Toán tử đột biến là phép đảo bit tại vị trí đột biến.
Với giải thuật này, GA có thể được mô hình hóa như một xích Markov
thời gian rời rạc, mỗi quần thể xem như một trạng thái của xích. Rõ ràng là
trạng thái hiện tại chỉ phụ thuộc vào một trạng thái ngay trước nó, vì nếu ký
hiệu X
n
là quần thể tại lần tạo sinh thứ n thì với n = 1,2, ta có:
P(X
n
= k | X
0
= k
0
, X

nếu
1*)(lim 

fBP
t
t
, ở đây f* = max{f(j) | j  J
L
} là lời giải tối ưu của bài
toán nêu trên.
Do các toán tử của GA độc lập với nhau nên có thể biểu diễn ma trận
chuyển là Q = SCM trong đó S, C, M theo thứ tự là ma trận chuyển của các
phép chọn lọc, lai ghép và đột biến.
Định nghĩa 2: Khoảng cách Hamming giữa hai chuỗi bit là số vị trí bit không
trùng nhau của hai chuỗi đó (chẳng hạn H(„0100‟, „0001‟) = 2). Đặt H
ij
là
tổng khoảng cách Hamming giữa các cá thể trong quần thể i và j:




1
0
),(
M
h
hhij
jiHH


Tuy nhiên để tăng hiệu lực của GA, De Jong đã đề xuất một chiến lược
ưu tú, Suzuki ([9]) đã chứng minh sự hội tụ đến lời giải toàn cục của GA với
chiến lược ưu tú sửa đổi. Cụ thể như sau: Giả sử số cá thể M của quần thể là
một số lẻ, i* là cá thể có giá trị thích nghi cao nhất của quần thể hiện tại.
Chiến lược ưu tú được sửa đổi là: quần thể kế tiếp luôn chứa i* .
Với chiến lược này, toán tử tạo sinh phần tử i* luôn được thực hiện đầu
tiên tại mỗi bước của quá trình. Sau đó M-1 cá thể còn lại được sinh ra theo
các toán tử di truyền thông thường. Dưới đây ta giả thiết là bài toán chỉ có một
lời giải tối ưu toàn cục.
Với mỗi quần thể k (k = 1,2, , N), ký hiệu i*(k) là cá thể có độ thích nghi cao
nhất trong quần thể. Đặt N(i) là số các quần thể mà trong quần thể đó, i là cá
thể có độ thích nghi cao nhất (i = 0,1, ,r-1). Ta gán nhãn cho mỗi cá thể i =
0,1, , r-1 theo thứ tự f(i) giảm dần sử dụng một quy tắc luân phiên tiền định
nào đó đối với các cá thể có cùng độ thích nghi. Ta cũng gán nhãn cho mỗi
quần thể k = 1,2, ,N theo thứ tự giảm dần của i*(k) theo một quy tắc luân
phiên tiền định nào đó cho những quần thể có cùng i*(k). Giả sử các trạng thái
trong tập K = {1, 2, , N(0)} là các trạng thái tối ưu toàn cục.
Với các ký hiệu trên, điều kiện hội tụ của GA có thể phát biểu là:
18

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Giải thuật di truyền hội tụ tới tối ưu toàn cục nếu và chỉ nếu
KX
t
t


lim


0
, Q
1
, , Q
r-1
, mỗi ma trận có phần trên đường
chéo chính bằng 0. Kích cỡ của Q
i
là N(i)xN(i). Có thể thấy N(i) tính được là
số tổ hợp chập (r-i-1) của (r-i+M-2).
Dựa trên các ký hiệu trên, Suzuki đã đưa ra công thức tính xác suất
chuyển từ trạng thái k đến trạng thái v là:











)(*)(*0
)(*)(*),(
)!,(
1
)!1(
1
0

kv
> 0 với k, v  K vì i*(k) = i*(v). Điều này cũng có nghĩa là
Q
0
là ma trận dương và là nguyên sơ. Tuy nhiên cấu trúc của ma trận không
thể suy ra nhờ trực giác bằng sự nghiên cứu mỗi toán tử di truyền. Toán tử
chọn lọc không thể tạo cá thể mới và cũng không thể làm tăng i*(k). Toán tử
lai ghép và đột biến đều tạo cá thể mới và có xác suất dương khi chuyển đến
quần thể mới có cá thể cao hơn i*(k).
Định lý 2: Giải thuật di truyền với chiến lược ưu tú sửa đổi như trên và
p
m
 (0, 1) hội tụ đến tối ưu toàn cục.
Chứng minh: Từ những phân tích trên, ta có Q
+
là không phân ly được
và Q
0
là ma trận nguyên sơ. Theo lý thuyết xích Markov, ta có












có thể tính toán chi tiết các yếu tố ảnh hưởng đến khả năng và tốc độ hội tụ
của giải thuật. Tuy nhiên, thực hiện thuật toán qua xích Markov sẽ gặp khó
khăn rất lớn do không gian trạng thái cần xét đến là rất lớn. Vì vậy mô hình
này thường chỉ được phát triển về phương diện lý luận.
Kết Luận: phần trên giới thiệu những vấn đề khái quát về giải thuật di truyền
(GA) làm cơ sở cho việc ứng dụng giải bài toán tối ưu đa mục tiêu.
20

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Chương 2: LOGIC MỜ

Chương này giới thiệu những vấn đề khái quát về logic mờ làm cơ sở cho
việc ứng dụng giải bài toán tối ưu đa mục tiêu.[1]
2.1. Tập mờ
2.1.1. Định nghĩa tập con mờ
Một tập con cổ điển A của X được định nghĩa bởi một hàm đặc trưng
A

lấy giá trị 0 đối với những phần tử của X không thuộc A và lấy giá trị 1
với những phần tử X thuộc A:

1,0: X
A


Định nghĩa 2.1: Một tập con mờ A của X được định nghĩa bởi một hàm
thuộc, gán cho mỗi phần tử x của X, độ thuộc f
A
(x), nằm giữa 0 và 1, theo đó

A
xxfA
xxfA
/)(
/)(

2.1.2. Các đặc trưng của một tập con mờ
Những đặc trưng hữu ích nhất của một tập con mờ A của X để mô tả nó
là những đặc trưng chỉ rõ nó khác với một tập con thông thường của X ở điểm
nào.
Đặc trưng thứ nhất là giá của A, là tập những phần tử của X ít nhất có
thuộc A một chút.
21

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Định nghĩa 2.2: Giá của A, ký hiệu supp(A), là bộ phận của X trên đó
hàm thuộc của A khác không:
Supp(A)=
 
0)(/  xfXx
A

Đặc trưng thứ hai của A là chiều cao của nó, ký hiệu h(A), là độ thuộc
lớn nhất mà một phần tử của X thuộc A.
Định nghĩa 2.3: Chiều cao, ký hiệu h(A), của tập con mờ A của X là giá
trị lớn nhất mà hàm thuộc có thể lấy được:
h(A)=
)(sup xf
AXx

Nếu A là tập con thông thường của X, chiều cao của nó bằng 1; nó
được chuẩn hóa và đồng nhất với giá và hạt nhân của nó; lực lượng của nó
chính là số phần tử của tập theo định nghĩa cổ điển.
2.1.3. Các phép toán trên các tập con mờ
a. Sự bằng nhau và sự bao hàm (chứa nhau) của các tập con mờ
Định nghĩa 2.7: Hai tập con mờ A và B của X là bằng nhau nếu các
hàm thuộc của chúng lấy cùng giá trị với mọi phần tử của X:
)()(: xfxfXx
BA


Định nghĩa 2.8: Cho hai tập con mờ A và B của X, ta nói rằng A bao
hàm trong B, ký hiệu
BA 
, nếu các hàm thuộc của chúng thỏa điều kiện
)()(: xfxfXx
BA


b. Giao và hợp của các tập con mờ
Định nghĩa 2.9: Giao của hai tập con mờ A và B của X là tập con mờ C,
ký hiệu
BA 
, sao cho:
))(),(min()(: xfxfxfXx
BAC

,
Min ký hiệu toán tử lấy cực tiểu
Định nghĩa 2.10: Hợp của hai tập con mờ A và B của X là tập con mờ


23

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn


BAABA 


)''()'()'''( BABABBA 


)''()'()'''( BABABBA 


BABABA 

c. Phần bù của một tập con mờ
Định nghĩa 2.11: Phần bù A
C
của một tập con mờ A của X được định
nghĩa là tập con mờ của X với hàm thuộc:
)(1)(: xfxfXx
AA


Tính chất 2:
 Các luật De Morgan:
ccc
BABA  )(

c
=ker(A), (ker(A
c
))
c
= supp(A).
d. Tích Descartes của các tập con mờ
Định nghĩa 2.12: Cho các tập con mờ A
1
, A
2
, …, A
r
được xác định
tương ứng trên X
1
,X
2
, …, X
r
, ta định nghĩa tích Descartes của chúng
A=A
1
*A
2
*…*A
r
như một tập con mờ của X có hàm thuộc:
))(), (min()(,), ,,(
121

xxfxfXx
AXxAoj
X



Hình chiếu của A trên X
2
cũng được định nghĩa tương tự.
Định nghĩa 2.14: hình chiếu trên X
a
*X
b
*….*X
k
của tập con mờ A của
X
1
*X
2
*…X
r
là tập con mờ Proj(A) của X
a
*X
b
*…*X
k
với hàm thuộc được
định nghĩa là:

xxfxfXxxxxx 

2.2. Quan hệ mờ
Quan hệ mờ đóng vai trò quan trọng trong Logic mờ và lập luận xấp xỉ.
Khái niệm quan hệ mờ là sự tổng quát hoá trực tiếp của khái niệm quan hệ
(quan hệ rõ). Trước hết ta nhắc lại về khái niệm quan hệ .
Giả sử U và V là hai tập . Một quan hệ R từ U đến V (sẽ được gọi là
quan hệ 2 ngôi, hoặc quan hệ nhị nguyên ) là một tập con của tích đề các UV.
Trong trường hợp U = V, ta nói R là quan hệ trên U. Chẳng hạn, tập R bao
gồm tất cả các cặp người (a, b) trong đó a là chồng của b, xác định quan hệ
“vợ _ chồng” trên tập người nào đó.
Khi U và V là các tập hữu hạn, chúng ta sẽ biểu diễn quan hệ R từ U
đến V bởi ma trận, trong đó các dòng được đánh dấu bởi các phần tử x  U và
các cột được đánh dấu bởi các phần tử y  V. Phần tử của ma trận nằm ở dòng
x, cột y là 
R
(x,y)
1 nếu (x,y) R

R
(x,y) =
25

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

0 nếu (x,y) R

Ví dụ 1: Giả sử U = {1,2,3} và V = {a,b,c,d} giả sử R là quan hệ từ U đến V
như sau:
R = {(1,a), (1,d), (2,a), (2,b), (3,c), (3,d)}

R
(v, u)
2. Phản xạ nếu: 
R
(u, u) = 1, u  U
3. Phản phản xạ nếu: 
R
(u, u) = 0 , u  U
4. Bắc cầu Max_Min nếu 
R
(u, v)  { 
R
(u, w)  
R
(w, v): wW}
5. Bắc cầu Min_Max nếu 
R
(u, v)  { 
R
(u, w)  
R
(w, v): wW}
6. Phép hợp thành R

S với RU W, S W U được định nghĩa như sau:

RS
(u, v) = { 
R
(u, w)  