HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG PHẠM VĂN TUẤN
NGHIÊN CỨU THUẬT GIẢI DI TRUYỀN VÀ
ỨNG DỤNG ĐỂ PHÂN LỚP DỮ LIỆU
BẰNG TẬP THÔ DUNG SAI Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2013

HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: PGS.TS. NGUYỄN BÁ TƯỜNG

Phản biện 1: ……………………………………

Phản biện 2: ……………………………………

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận
văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn
thông
Vào lúc: giờ ngày tháng năm…

Có thể tìm hiểu luận văn tại:

- Thư viện của Học viện Công nghệ Bưu chính Viễn thông MỞ ĐẦU
Tìm kiếm lời giải tối ưu cho các bài toán thực tiễn luôn là
vấn đề quan trọng trong khoa học công nghệ nói chung và tin
học nói riêng. Các thuật giải tiến hóa dựa trên nguyên tắc
những gì tự nhiên đã thực hiện để tìm kiếm lời giải tối ưu,
khắc phục được các nhược điểm của các kỹ thuật tìm kiếm
truyền thống trong các vấn đề tìm kiếm có không gian tìm
kiếm lớn và nhiều ràng buộc phức tạp.
Thuật giải di truyền là thuật giải tìm kiếm dựa trên quá
trình chọn lọc tự nhiên, di truyền và tiến hóa. Thuật giải di

dung sai.

CHƢƠNG I: TỔNG QUAN VỀ THUẬT GIẢI
DI TRUYỀN

1.1. Tổng quan thuật giải di truyền
1.1.1. Nội dung thuật giải di truyền
Thuật giải di truyền sử dụng các thuật ngữ vay mượn
của di truyền học. Mỗi kiểu (nhóm) gen (ta gọi là một nhiễm
sắc thể) sẽ biểu diễn một lời giải của bài toán, một tiến trình
tiến hoá được thực hiện trên một quần thể các nhiễm sắc thể
tương ứng với một quá trình tìm kiếm trong không gian lời
giải. Thuật giải di truyền duy trì một quần thể các lời giải có
thể của bài toán tối ưu hóa. Mỗi lời giải gọi là một cá thể hay
một nhiễm sắc thể, thường được mã hóa dưới dạng một
chuỗi các gen.
Quần thể mới được tạo ra bằng cách sử dụng các quá
trình chọn lọc, lai ghép và đột biến. Quá trình chọn lọc sao
chép các cá thể có độ phù hợp tốt vào một quần thể tạm thời
được gọi là quần thể bố mẹ. Các cá thể trong quần thể bố mẹ
được ghép đôi một cách ngẫu nhiên và tiến hành lai ghép tạo
ra các cá thể con. Sau khi tiến hành quá trình lai ghép, thuật
giải di truyền mô phỏng một quá trình khác trong tự nhiên là
quá trình đột biến, trong đó các gen của các cá thể con tự
thay đổi giá trị với một xác xuất nhỏ.
Như vậy, thuật giải di truyền xuất phát với tập lời giải
ban đầu, thông qua nhiều bước trong quá trình tiến hoá hình
thành các tập lời giải mới tốt hơn, và cuối cùng tìm ra lời giải
đủ tốt chấp nhận được .
1.1.2. Các bước chính trong việc áp dụng thuật giải

1.2.3. Toán tử đột biến (Mutation)
Các toán tử đột biến nhằm tạo ra các thông tin mới
trong quần thể thu được sau khi lai ghép tại các vị trí bít nào
đó.
Tóm lại, ba toán tử nêu trên được tiến hành trong một
vòng lặp cho đến khi các chuỗi con chiếm toàn bộ quần thể
mới.
1.2.4. Hàm thích nghi (Fitness)
Hàm thích nghi giống như là một hàm đánh giá độ tốt
của cá thể. Nó dùng để so sánh giữa hai cá thể để xét xem cá
thể nào tốt hơn. Giá trị thích nghi được xác định dựa vào một
hàm mục tiêu cho trước.
1.2.5. Thuật giải SGA
Cá thể có giá trị hàm mục tiêu tốt nhất của mọi thế hệ
là lời giải cuối cùng của thuật giải SGA. Quần thể đầu tiên
được khởi tạo một cách ngẫu nhiên.
1.3. Nền tảng toán học của thuật giải di truyền
1.3.1. Khái niệm và ký hiệu
Nền tảng lý thuyết của thuật giải di truyền dựa trên
biểu diễn chuỗi nhị phân và lý thuyết lược đồ. Một lược đồ là
một chuỗi, dài bằng chuỗi NST, các thành phần của nó có thể
có thể nhận một trong các giá trị trong tập ký tự biểu diễn
gen hoặc một ký tự đại diện ’*’. 1.3.2. Định lý giản đồ
Định lý: Trong thuật giải SGA, nếu số thể hiện của
giản đồ H tại thế hệ t là m(H,t) thì số thể hiện của giản đồ H
tại thế hệ tiếp theo được ước lượng như sau:
   

tăng và có vai trò quan trọng trong thuật giải di truyền. Các
giản đồ như vậy được gọi là các khối xây dựng.
J.H.Holland đã đưa ra giả thuyết về khối xây dựng
như sau: Thuật giải di truyền tối ưu hoá (tối thiểu hoá) hàm
mục tiêu bằng việc kết hợp các khối xây dựng tạo ra các cá
thể dần tốt hơn từ các phần tử tốt nhất của các điểm đã thăm
dò trước đấy.
1.4. Các nguyên nhân dẫn đến thất bại trong quá trình áp
dụng các thuật giải di truyền.
- Những vấn đề dễ nhầm lẫn
- Lỗi trong việc lấy mẫu
- Tình trạng phá vỡ lược đồ
1.5. Các cải tiến của thuật giải di truyền
1.5.1. Vấn đề tạo ra quần thể ban đầu
1.5.2. Sử dụng nhiều quần thể con
1.5.3. Những cải tiến trong chiến lược chọn lọc
- Ưu tiên cá thể tốt (elitism)
- Lấy mẫu tiền định (deterministic sampling)
- Lấy mẫu xác suất phần dư và thay thế (remainder
stochastic sampling with replacement)
- Lấy mẫu xác suất phần dư và không thay thế
(remainder stochastic sampling with replacement)
- Thủ tục phân hạng (ranking procedure)
1.5.4. Mở rộng toán tử lai ghép
- Lai ghép nhiều điểm
- Toán tử xếp lại 1.5.5. Cải tiến chiến lược thay thế
Chiến lược thay thế sản sinh ra quần thể trong thế hệ
CHƢƠNG II: ỨNG DỤNG THUẬT GIẢI DI TRUYỀN
NHẰM TĂNG CƢỜNG HIỆU QUẢ PHÂN LỚP DỮ
LIỆU BẰNG TẬP THÔ DUNG SAI

2.1. Các khái niệm về tập thô.
Xét một không gian các đối tượng U, P = {p
1
, p
2
,
p
k
} là một phân hoạch của U, khi đó trong họ các tập con 2
U

của U sẽ có một số tập là những tập rõ, số còn lại là những
tập thô ứng với phân hoạch P. Về mặt trực quan tập thô là
tập những đối tượng không phân loại được. Tập rõ là những
tập phân loại được.
Cho tập U hữu hạn, khác rỗng bất kỳ, U được gọi là
tập các đối tượng. E = {E
1

i
có phần tử chung
với X hay X
E
=
X
(E) ) =

{E
i

E : E
i


X


}. Xấp xỉ
dưới của X trong Apr = (U, E), ký hiệu X
E
( hoặc X(E)) là
hợp của các nhóm E
i
mà E
i
là tập con của X hay X
E
= X(E)
=

U
được gọi là rõ trong không gian Apr= ( U,
E) ( hay X là rõ ứng với phân hoạch E ) nếu X
E
= X
E
. Hoặc
Tập X được gọi là thô trong Apr = ( U, E) nếu

X
E

< 1.
Tập X được gọi là rõ trong Apr = ( U, E) nếu

X
E
=
1 .
2.1.3. Định nghĩa tập thô, tập rõ theo tập hợp.
Định nghĩa 2.3 Định nghĩa tập thô, tập rõ theo tập
hợp
Cho không gian Apr = (U, E )
X

2
U
là tập rõ trong Apr = ( U, E) nếu X

{

2.1.4. Sự tương đương của hai định nghĩa tập thô,
tập rõ.
2.2. Các phép toán tập hợp trên các tập thô, tập rõ.
2.2.1. Các phép toán tập hợp trên các tập rõ.
Bổ đề 2.3.
Cho không gian Apr = (U, E); X

U.
X là tập rõ khi và chỉ khi X =

hoặc X =

E
i
.

Bổ đề 2.4.
Cho không gian Apr = (U, E); X, Y

U.
a. Nếu X, Y

RO thì X

Y là tập rõ
b. Nếu X, Y

RO thì X

Y là tập rõ

Y là tập thô hoặc tập rõ.
c. Nếu X, Y

THO thì X \ Y là tập thô hoặc tập rõ.
d. Nếu X

THO thì - X (phần bù của X) là tập thô.
2.3. Phủ và tập thô dung sai.
2.3.1. Phủ và phân hoạch.
a. Phân hoạch
Cho tập đối tượng U = { o1, o2, , om}
Họ các tập con của U, P = { p1, , pk} được gọi là
phân hoạch của U nếu P thỏa 3 điều kiện:
(1) pi


với mọi i
(2) pi

Pj =

với i

j
(3) U =

k
i
pi
1

X
C

2.4. Tập thô dung sai (TRS-Tolerance Rough Set)
Cho U= { o1, o2, om};
2.4.1. Quan hệ tương đương.
Định nghĩa 2.6.
Quan hệ R

U

U được gọi là quan hệ tương đương
trên U nếu R thỏa mãn ba điều kiện
(*) Phản xạ:

o

U thì (o, o)

R
(**) Đối xứng:

o, o’

U nếu (o, o’)

R thì (o’,
o)

R

U nếu (o, o’)

R thì (o’, o)

R.
Như vậy quan hệ tương đương là quan hệ dung sai.
2.5. Đo độ tƣơng tự của hai đối tƣợng. Định nghĩa 2.7
Độ đo tương tự của x và y trên thuộc tính a, ký hiệu là
S
a
(x,y), được tính bởi công thức sau:
S
a
(x,y) = 1-
a
d
yaxa )()( 

Định nghĩa 2.8
Độ đo tương tự của x và y trên tập thuộc tính A, ký
hiệu là S
A
(x,y), được tính bởi công thức sau:
S
A
(x,y) =
A

 
A
x

.
2.8. Áp dụng thuật giải di truyền xác định ngƣỡng tƣơng
tự tối ƣu.
Ta cần giải quyết các vấn đề sau :
 Biểu diễn các biến của vấn đề .
 Tạo quần thể ban đầu .
 Xác định hàm thích nghi của vấn đề, xác định giá
trị thích nghi của các cá thể .
 Thực hiện các phương thức tiến hoá .
Mô tả thuật giải :
1. Khởi tạo :
Đọc bảng quyết định ;
Định nghĩa độ đo tương tự ;
Tạo quần thể ban đầu : Lấy các ngưỡng ban đầu
trong khoảng [0,1];
Tính độ thích nghi của quần thể ban đầu ;
2. Tiến hành thuật giải di truyền
while ( not( điều kiện kết thúc ))
{ Tạo sinh; Lai ghép; Đột biến;
Tính hàm thích nghi của quần thể mới
}
3. Xác định giá trị ngưỡng tương tự tối ưu.
2.8.1. Đặt vấn đề
2.8.2. Biểu diễn các biến.
2.8.3. Phát sinh quần thể ban đầu.
2.8.4. Hàm thích nghi.

ưu trong nhiều lần thực hiên, kết quả thu được thường tốt
hơn .
2.10. Kết luận
Chương này áp dụng giải quyết bài toán tối ưu hoá
các giá trị ngưỡng tương tự.
Chương này cũng mô tả phương pháp phân lớp 2 giai
đoạn dựa vào tập thô dung sai và thuật giải di truyền.
Bằng cách thực hiện nhiều lần chức năng kết hợp
thuật giải di truyền và thuật giải phân lớp, các số liệu kết quả
thu được cho ta một nhận xét : nếu giá trị ngưỡng càng lớn
(trong miền đã xác định) thì số phần tử không phân lớp được
càng ít đi.
KẾT LUẬN

Luận văn trình bày việc ứng dụng thuật giải di truyền
xác định ngưỡng tối ưu nhằm tăng hiệu quả của việc phân
lớp dữ liệu bằng tập thô dung sai. Để thực hiện công việc
này, luận văn tiến hành nghiên cứu các vấn đề lý thuyết về
thuật giải di truyền, thuật giải phân lớp dữ liệu trên tập thô
dung sai và vấn đề xác định ngưỡng tương tự tối ưu của thuật
giải di truyền. Các kết luận được rút ra từ luận văn bao gồm
các điểm như sau:
- Tiếp cận tập thô dung sai để giải quyết bài toán phân
lớp dữ liệu. Phân lớp dữ liệu được tiến hành theo 2 giai đoạn:
Giai đoạn 1 sử dụng công cụ tập xấp xỉ dưới để phân lớp dữ
liệu. Giai đoạn 2 được tiến hành cho các mục dữ liệu không
phân lớp được trong giai đoạn 1 bằng cách sử dụng tập xấp xỉ