ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ






VŨ THỊ ANH TRÂM






SỬ DỤNG PHƯƠNG PHÁP XÂY DỰNG ĐẶC TRƯNG
DỰA TRÊN DI TRUYỀN ĐỂ TÓM TẮT DỮ LIỆU








LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

HÀ NỘI - 2012

1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ




VŨ THỊ ANH TRÂM





SỬ DỤNG PHƯƠNG PHÁP XÂY DỰNG ĐẶC TRƯNG
DỰA TRÊN DI TRUYỀN ĐỂ TÓM TẮT DỮ LIỆU


Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.05




LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN




NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN











HÀ NỘI - 2012

4
MỤC LỤC
TRANG PHỤ BÌA 1
NHỮNG LỜI ĐẦU TIÊN 2
LỜI CAM ĐOAN 3
MỤC LỤC 4
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT 6
DANH MỤC CÁC HÌNH VẼ 6

DANH MỤC CÁC BẢNG BIỂU 6
MỞ ĐẦU 7
CHƢƠNG 1: TÓM TẮT DỮ LIỆU QUAN HỆ VỚI THUẬT TOÁN DARA 9
1.1 Cơ sở dữ liệu quan hệ 9
1.1.1 Giới thiệu 9
1.1.2 Tổ chức dữ liệu 9
1.2 Tóm tắt dữ liệu trong cơ sở dữ liệu quan hệ 10
1.3 Thuật toán DARA 12
1.3.1 Giới thiệu 12
1.3.2 Tiền xử lí dữ liệu 13
1.3.3 Chuyển đổi dữ liệu 14
1.3.3.1 Quá trình mã hóa các mẫu tin thành số nhị phân 15
1.3.3.2 Biểu diễn dữ liệu trong mô hình không gian Vector 18
1.3.4 Phân cụm dữ liệu 18
1.3.5 Mô tả đặc điểm cụm và mô hình hoá dữ liệu 19
CHƢƠNG II - GIẢI THUẬT DI TRUYỀN 20
2.1 Giới thiệu 20
2.2 Giải thuật di truyền cổ điển 20
2.2.1 Phƣơng pháp mã hoá và giải mã. 22
2.2.2 Quá trình chọn lọc 22
2.2.3 Quá trình tái tạo 23
2.2.4 Sự hội tụ của GA 24
2.2.5 Ví dụ 24
2.3 Những cải tiến của giải thuật di truyền 27
2.3.1 Một số cách mã hoá nhiễm sắc thể 27
2.3.3 Phƣơng pháp chọn lọc 28
2.3.3 Các toán tử di truyền 29
2.3.3.1 Toán tử lai ghép 29
2.3.3.2 Toán tử đột biến 30
CHƢƠNG III - PHƢƠNG PHÁP XÂY DỰNG ĐẶC TRƢNG DỰA TRÊN

GIẢI THUẬT DI TRUYỀN ĐỂ TÓM TẮT DỮ LIỆU 31
3.1 Giới thiệu 31
3.2 Chuyển đổi đặc trƣng 31
3.2.1 Xây dựng đặc trƣng 31
3.2.2 Biểu diễn đặc trƣng: 34
3.2.3. Chấm điểm Đặc trƣng 35

5
3.3. Xây dựng đặc trƣng để tóm tắt dữ liệu 36
3.3.1 Chuyển đổi đặc trƣng dựa trên xây dựng đặc trƣng 36
3.3.2 Phƣơng pháp xây dựng đặc trƣng dựa trên giải thuật di truyền 38
3.3.2.1 Hàm thích nghi 38
3.3.2.2 Thuật toán xây dựng đặc trƣng dựa trên giải thuật di truyền 40
CHƢƠNG 4: KẾT QUẢ THỬ NGHIỆM 42
4.1 Giới thiệu 42
4.2 Chƣơng trình và dữ liệu thử nghiệm 42
4.2.1 Chƣơng trình 42
4.2.2 Dữ liệu thử nghiệm 45
4.3 Kết quả thử nghiệm 46
KẾT LUẬN 47
TÀI LIỆU THAM KHẢO 48
PHỤ LỤC 52

6
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

Chữ viết tắt
Tiếng Anh
Nghĩa Tiếng Việt
DARA

Dynamic Aggregation of
Relational Attributes
Tổng hợp động các thuộc tính
quan hệ
GA
Genetic Algorithm
Giải thuật di truyền




DANH MỤC CÁC HÌNH VẼ
Hình 1.1: Một tập dữ liệu với hai mức của liên kết 1:n 10
Hình 1.2 Tóm tắt dữ liệu trong nhiều bảng với các mối quan hệ một-nhiều 11
Hình 1.3: Ba giai đoạn chính trong quá trình tóm tắt dữ liệu quan hệ 12
Hình 1.4: Quá trình tóm tắt dữ liệu sử dụng thuật toán DARA 13
Hình 1.5: Liên kết một-nhiều giữa bảng đích và bảng tham chiếu 14
Hình 1.6: Chuyển đổi dữ liệu trong bảng tham chiếu với một thuộc tính 15
Hình 1.7: Chuyển đổi dữ liệu trong bảng tham chiếu với nhiều thuộc tính 17
Hình 2.1: Sơ đồ cấu trúc thuật toán di truyền 21
Hình 2.2: Bánh xe sổ xố với một quần thể có 6 cá thể 23
Hình 3.1: Phƣơng pháp tiếp cận lọc để lựa chọn tập con đặc trƣng 33
Hình 3.2: Phƣơng pháp tiếp cận bao gói để lựa chọn tập con đặc trƣng 34
Hình 3.3: Đối tƣợng O
j
đƣợc biểu diễn bởi một túi các mẫu nhƣ một tập các đặc trƣng
riêng biệt 37
Hình 3.4: Đối tƣợng O
j
đƣợc biểu diễn bởi một túi các mẫu nhƣ một đặc trƣng duy

nhất đƣợc xây dựng bằng cách kết hợp tất cả các thuộc tính 37
Hình 3.5: Đối tƣợng O
j
đƣợc biểu diễn bởi một túi các mẫu nhƣ một tập các đặc trƣng
đã đƣợc kết hợp từ tập các thuộc tính ban đầu 37
Hình 3.6: Quá trình xây dựng đặc trƣng dựa trên phƣơng pháp lọc 38
Hình 4.1: Giao diện chƣơng trình 42
Hình 4.2: Giao diện NetBean IDE tạo chƣơng trình 43
Hình 4.3: Mô hình quan hệ của dữ liệu thử nghiệm 45

DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1: Danh sách các mẫu đƣợc tạo ra 18
Bảng 2.1: Kết quả thực hiện quá trình chọn lọc 28
Bảng 4.1: Kết quả thử nghiệm 48


7
MỞ ĐẦU
Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và
ứng dụng của công nghệ thông tin trong nhiều lĩnh vực của đời sống xã hội,
lƣợng dữ liệu đƣợc các cơ quan thu thập và lƣu trữ ngày một nhiều lên. Dữ liệu
đƣợc tổ chức thành các cơ sở dữ liệu để đảm bảo đƣợc tính nhất quán, dễ quản lí
và đáp ứng nhu cầu khai thác đồng thời của nhiều ngƣời.
Với sự gia tăng bùng nổ của dữ liệu hiện nay, các cơ sở dữ liệu thực tế
chứa đựng rất nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có
những phƣơng pháp nhanh, phù hợp, chính xác, hiệu quả để lấy đƣợc những
thông tin bổ ích. Công nghệ phát hiện tri thức và khai phá dữ liệu đã ra đời đáp
ứng nhu cầu đó và đang đƣợc nghiên cứu, ứng dụng ngày càng rộng rãi.
Khai phá cơ sở dữ liệu quan hệ là một trong những lĩnh vực đang đƣợc
quan tâm nghiên cứu của khai phá dữ liệu. Trong một cơ sở dữ liệu quan hệ, dữ

liệu đƣợc lƣu trữ trong các bảng có mối quan hệ với nhau. Khi giải quyết bài
toán phân loại trong khai phá dữ liệu quan hệ, các phƣơng pháp truyền thống
thƣờng yêu cầu liên kết dữ liệu đƣợc lƣu trong nhiều bảng thành một bảng duy
nhất. Trong nhiều trƣờng hợp, quá trình này là không hiệu quả vì bảng đã nối
quá lớn cho việc xử lí và một số thông tin có thể bị mất khi phép nối thực hiện
[2]. Mặt khác, việc áp dụng các phƣơng pháp tóm tắt dữ liệu trên nhiều bảng có
quan hệ một-nhiều thƣờng bị hạn chế bởi sự phức tạp của lƣợc đồ cơ sở dữ
liệu. Một phƣơng pháp tóm tắt dữ liệu sử dụng thuật toán DARA đã đƣợc đề
xuất để giải quyết vấn đề này.
Trong một cơ sở dữ liệu quan hệ mà các bảng có mối quan hệ một-nhiều,
mỗi bản ghi trong bảng đích đƣợc liên kết với một hoặc nhiều bản ghi trong
bảng tham chiếu. Thuật toán DARA chuyển đổi dữ liệu trong bảng tham chiếu
vào một mô hình không gian vector và thực hiện phân cụm. Sau đó, dữ liệu tóm
tắt từ bảng tham chiếu sẽ đƣợc cập nhật vào bảng đích. Khi thực hiện chuyển đổi
dữ liệu, các bản ghi trong bảng tham chiếu đƣợc đƣa vào các túi mẫu tƣơng ứng
với các bản ghi đích. Nghĩa là, mỗi bản ghi đích đƣợc biểu diễn nhƣ một túi các
mẫu. Thông thƣờng, tập đặc trƣng đƣợc lấy để xây dựng các mẫu chính là tập
các thuộc tính ban đầu trong bảng tham chiếu. Tập đặc trƣng này cũng có thể
đƣợc xây dựng dựa trên sự kết hợp các thuộc tính bằng một số thuật toán đơn
giản. Tuy nhiên, các phƣơng pháp hiện có này chƣa thực sự hiệu quả. Do vậy,
vấn đề xây dựng một tập đặc trƣng thích hợp cho thuật toán DARA đƣợc đặt ra
nhƣ một bài toán tối ƣu cần giải.

8
Trƣớc các vấn đề nêu trên, luận văn tập trung nghiên cứu một phƣơng
pháp xây dựng đặc trƣng dựa trên di truyền để nâng cao hiệu quả tóm tắt dữ liệu
với thuật toán DARA. Nghiên cứu này dựa trên ý tƣởng nghiên cứu của Rayner
Alfred [3]. Thử nghiệm cho thuật toán đƣợc thực hiện trên cơ sở dữ liệu về thuê
bao di động phát sinh của thành phố Hà Nội.
Ngoài phần kết luận và các phụ lục, phần còn lại của luận văn đƣợc chia

thành 4 chƣơng chính:
Chƣơng I giới thiệu về cơ sở dữ liệu quan hệ, quá trình tóm tắt dữ liệu
trong cơ sở dữ liệu quan hệ và trình bày chi tiết các giai đoạn thực hiện của thuật
toán DARA để tóm tắt dữ liệu.
Chƣơng II trình bày về giải thuật di truyền cổ điển và những cải tiến về
cách biểu diễn nhiễm sắc thể, phƣơng pháp chọn lọc và một số toán tử di truyền
thƣờng dùng.
Chƣơng III trình bày một số vấn đề về chuyển đổi đặc trƣng liên quan đến
xây dựng đặc trƣng và giới thiệu một phƣơng pháp xây dựng đặc trƣng dựa trên
GA để tóm tắt dữ liệu.
Chƣơng IV trình bày các kết quả thực nghiệm về phƣơng pháp xây dựng
đặc trƣng dựa trên giải thuật di truyền. Chƣơng trình cài đặt thử nghiệm cho
thuật toán đƣợc thực hiện bằng ngôn ngữ Java trên tập dữ liệu.
Phần Kết luận trình bày tổng hợp các kết quả thực hiện luận văn và hƣớng
nghiên cứu tiếp theo.

9
CHƢƠNG 1: TÓM TẮT DỮ LIỆU QUAN HỆ VỚI THUẬT TOÁN DARA
1.1 Cơ sở dữ liệu quan hệ
1.1.1 Giới thiệu
Một cơ sở dữ liệu là một tập hợp dữ liệu có liên quan với nhau đƣợc tổ chức và
lƣu trữ theo một cấu trúc chặt chẽ.
Một mô hình cơ sở dữ liệu là một tập hợp các khái niệm dùng để biểu diễn cấu
trúc của cơ sở dữ liệu. Các mô hình cơ sở dữ liệu có thể đƣợc phân loại dựa trên những
khái niệm mà chúng sử dụng để mô tả cấu trúc cơ sở dữ liệu [19]
 Các mô hình dữ liệu bậc cao hay mô hình dữ liệu mức quan niệm cung
cấp các khái niệm gắn liền với cách cảm nhận dữ liệu của nhiều ngƣời sử
dụng
 Các mô hình dữ liệu thể hiện hay mô hình dữ liệu mức logic cung cấp
những khái niệm mà ngƣời sử dụng có thể hiểu đƣợc và không khác

nhiều với cách tổ chức dữ liệu bên trong máy tính
 Các mô hình dữ liệu bậc thấp hay các mô hình dữ liệu vật lí, cung cấp
các khái niệm mô tả chi tiết về việc dữ liệu đƣợc lƣu trữ trong máy tính.
Các mô hình dữ liệu thể hiện là các mô hình đƣợc sử dụng nhiều nhất. Ba mô
hình cơ bản thuộc loại này là mô hình mạng, mô hình phân cấp và mô hình quan hệ.
 Mô hình mạng cung cấp ba khái niệm cơ bản: mẫu tin hay bản ghi, loại
mẫu tin và loại liên hệ. Trong mô hình này, dữ liệu đƣợc biểu diễn trong
các bản ghi liên kết với nhau bằng các mối nối liên kết tạo thành một đồ
thị có hƣớng.
 Mô hình phân cấp cũng sử dụng ba khái niệm cơ bản ở mô hình mạng
nhƣng trong mô hình này, dữ liệu đƣợc biểu diễn dƣới dạng cây với các
đỉnh của cây là các bản ghi. Các bản ghi liên kết với nhau theo mối quan
hệ cha-con, một bản ghi cha có thể có nhiều con nhƣng mỗi bản ghi con
chỉ có một cha.
 Mô hình quan hệ cung cấp những khái niệm cơ bản là thuộc tính, miền,
bộ và quan hệ. Trong mô hình này, dữ liệu đƣợc biểu diễn dƣới dạng
bảng.
Mô hình quan hệ là mô hình đƣợc sử dụng phổ biến nhất hiện nay. Cơ sở dữ
liệu đƣợc tổ chức theo mô hình quan hệ đƣợc gọi là cơ sở dữ liệu quan hệ.
1.1.2 Tổ chức dữ liệu
Dữ liệu lƣu trữ trong cơ sở dữ liệu quan hệ đƣợc tổ chức thành các bảng có mối
quan hệ với nhau. Một cơ sở dữ liệu quan hệ bao gồm một tập hợp các bảng T1, , Tn

10
và một tập các mối quan hệ R1, , Rm. Mỗi bảng Ti bao gồm các cột và các hàng, các
cột đại diện cho một dãy các thuộc tính, attr(T)=A1, , Ak, và các hàng đại diện cho
các bản ghi trong bảng. Do đó, Ti.Aj biểu thị thuộc tính thứ j của bảng Ti, Aj 
attr(Ti).
Định nghĩa 1.1 Miền của thuộc tính Ti.Aj ký hiệu là D(Ti.Aj) đƣợc định nghĩa
là tập của tất cả các giá trị khác nhau đƣợc phép đƣợc gán cho thuộc tính Aj trong

bảng Ti.
Định nghĩa 1.2 Khóa chính của bảng Ti, ký hiệu là Ti.ID, có giá trị duy nhất
cho mỗi hàng trong bảng.
Định nghĩa 1.3 Khóa ngoại của bảng Tj tham chiếu tới bảng Ti, ký hiệu là
Tj.TiID, nhận giá trị từ D(Ti.Aj).
Tập các mối quan hệ R1, , Rm mô tả mối liên kết giữa các bảng trong cơ sở
dữ liệu quan hệ. Một bảng Ti có thể có một trong ba kiểu liên kết với bảng Tj, căn cứ
vào lực lƣợng trong liên kết giữa Ti và Tj, đó là: 1:1 (một-một), 1:n (một-nhiều) và
m:n (nhiều-nhiều)

Hình 1.1: Một tập dữ liệu với hai mức của liên kết 1:n
Định nghĩa 1.4 Một bảng đích T là một bảng bao gồm các hàng của các đối
tƣợng mà mỗi hàng đại diện cho một đối tƣợng duy nhất.
Định nghĩa 1.5 Một bảng tham chiếu NT là một bảng bao gồm các hàng của
các đối tƣợng mà một tập con những hàng này có thể đƣợc liên kết với một đối tƣợng
duy nhất đƣợc lƣu trữ trong bảng đích.
1.2 Tóm tắt dữ liệu trong cơ sở dữ liệu quan hệ
Thuật ngữ tóm tắt dữ liệu thƣờng đƣợc dùng để nói đến tóm tắt dữ liệu đƣợc
lƣu trữ trong cơ sở dữ liệu quan hệ với các mối quan hệ một-nhiều [8].
Xét dữ liệu đƣợc cho nhƣ sau:
 Một bảng đích T
 Các bản ghi trong bảng đích RT

11
 Một bảng tham chiếu NT
 Các bản ghi trong bảng tham chiếu R
NT

Trong đó, một hoặc nhiều bản ghi R
NT

trong bảng tham chiếu NT đƣợc liên kết
với một bản ghi duy nhất RT trong bảng đích T. Tóm tắt dữ liệu trong nhiều bảng với
các mối quan hệ một-nhiều có thể đƣợc định nghĩa nhƣ sau:
Định nghĩa 1.6 Một quá trình tóm tắt dữ liệu cho tất cả các bản ghi R
NT
trong
bảng NT là một quá trình nối thêm vào bảng đích T ít nhất một trƣờng dữ liệu đặc
trƣng cho các giá trị của các bản ghi R
NT
liên kết với mỗi bản ghi RT trong bảng T.

Hình 1.2 Tóm tắt dữ liệu trong nhiều bảng với các mối quan hệ 1:n
Hình 1.2 minh họa trình tự tóm tắt dữ liệu cho một bảng đích T có mối quan hệ
ràng buộc một-nhiều với tất cả các bảng tham chiếu (NT1, NT2, NT3, NT4, NT41). Vì
bảng NT4 có mối quan hệ một-nhiều với bảng NT41 nên NT4 trở thành bảng đích để
tóm tắt dữ liệu từ bảng tham chiếu NT41. Dữ liệu tóm tắt từ các bảng NT1, NT2, NT3
và NT4 tạo nên các trƣờng đặc trƣng cho các giá trị của các bảng tham chiếu liên kết
với T, các trƣờng này đƣợc nối thêm vào danh sách thuộc tính đã có trong bảng đích T.
Một quá trình tóm tắt dữ liệu quan hệ bao gồm ba giai đoạn chính nhƣ mô tả
trong hình 1.3.

12

Hình 1.3: Ba giai đoạn chính trong quá trình tóm tắt dữ liệu quan hệ
Trong giai đoạn thứ nhất, dữ liệu đƣợc xử lí để chuẩn bị cho quá trình chuyển
đổi dữ liệu. Giai đoạn này liên quan đến một số kỹ thuật giảm dữ liệu để rời rạc hóa
các thuộc tính liên tục, lựa chọn và xây dựng đặc trƣng. Ở giai đoạn thứ hai, dữ liệu
đƣợc chuyển đổi vào mô hình không gian vector. Trong mô hình không gian vector,
các bản ghi đƣợc biểu diễn nhƣ một ma trận mẫu, trong đó, hàng đại diện cho một bản
ghi đơn đƣợc lƣu trong bảng đích và cột đại diện cho một mẫu tồn tại trong các bản

ghi. Cuối cùng, dữ liệu đƣợc tóm tắt bằng cách phân cụm dựa trên đặc điểm của chúng
và các mẫu mô tả đặc điểm mỗi cụm đƣợc trích xuất.
1.3 Thuật toán DARA
1.3.1 Giới thiệu
Thuật toán DARA (Dynamic Aggregation of Relational Attributes: tổng hợp
động các thuộc tính quan hệ) [4] đƣợc thiết kế cho mục đích tóm tắt dữ liệu trong cơ
sở dữ liệu quan hệ.
Để phân loại các bản ghi đƣợc lƣu trữ trong bảng đích có quan hệ một-nhiều
với các bản ghi đƣợc lƣu trữ trong các bảng tham chiếu, thuật toán DARA chuyển đổi
biểu diễn của dữ liệu đƣợc lƣu trữ trong bảng tham chiếu vào một ma trận TF-IDF [21]
kích thƣớc (n × p) và thực hiện phân cụm. Trong đó, n là số lƣợng bản ghi đƣợc phân
cụm và p là số lƣợng mẫu đƣợc xem xét để phân cụm. Khi thực hiện chuyển đổi dữ
liệu, bảng tham chiếu đƣợc chuyển vào các túi các mẫu tƣơng ứng với các đối tƣợng

13
liên kết trong bảng đích. Có thể tạo ra các mẫu làm phong phú thêm đại diện các đối
tƣợng bằng cách xây dựng các đặc trƣng mới từ tập đặc trƣng ban đầu trong bảng tham
chiếu. Các đặc trƣng mới đƣợc xây dựng bằng cách kết hợp ngẫu nhiên các thuộc tính
ban đầu trong bảng tham chiếu. Các mẫu liên kết với mỗi bản ghi đích tham chiếu tới
các mục đƣợc tạo ra bằng cách lấy giá trị của các cột ở các bản ghi liên quan đƣợc lƣu
trữ trong các bảng tham chiếu. Kết quả là, các bản ghi trong bảng tham chiếu đƣợc
tóm tắt bằng cách phân cụm các đối tƣợng nhận đƣợc sau khi chuyển đổi dữ liệu thành
các nhóm có chung những đặc điểm tƣơng tự.

Hình 1.4: Quá trình tóm tắt dữ liệu sử dụng thuật toán DARA
Sau khi dữ liệu trong bảng tham chiếu đƣợc chuyển đổi và phân cụm, một cột
mới, Fnew, đƣợc thêm vào tập hợp các đặc trƣng ban đầu trong bảng đích. Cột mới
chứa thông tin mô tả cụm đại diện cho các nhóm bản ghi trong bảng tham chiếu. Bằng
cách này, dữ liệu lƣu trữ trong bảng tham chiếu đƣợc ánh xạ đến các bản ghi trong
bảng đích.

Quá trình tóm tắt dữ liệu sử dụng thuật toán DARA đƣợc minh hoạ trong hình
1.4, các giai đoạn cụ thể sẽ đƣợc trình bày sau đây.
1.3.2 Tiền xử lí dữ liệu
Trong giai đoạn tiền xử lí dữ liệu, thuật toán DARA thực hiện hai quá trình cơ
bản là rời rạc hóa đặc trƣng và xây dựng đặc trƣng.
Các nhiệm vụ phân loại trong học máy thƣờng liên quan đến học để phân biệt
giữa các giá trị lớp danh nghĩa, nhƣng cũng có thể liên quan đến các đặc trƣng có thứ
tự hoặc liên tục. Một trong những phƣơng pháp phổ biến nhất khi làm việc với các đặc

14
trƣng liên tục là rời rạc hóa. Rời rạc hóa là quá trình chuyển đổi các đặc trƣng có giá
trị liên tục thành tên danh nghĩa. Quá trình này làm giảm số lƣợng giá trị của một đặc
trƣng liên tục bằng các chia miền giá trị đặc trƣng thành các khoảng, nhãn đƣợc gán
tƣơng ứng cho mỗi khoảng và đƣợc dùng thay cho giá trị thực của đặc trƣng.
Quá trình xây dựng đặc trƣng tạo ra các đặc trƣng mới, dựa trên một số biểu
thức hàm số sử dụng các giá trị của các đặc trƣng ban đầu, mô tả các giả thuyết ít nhất
cũng tốt nhƣ tập ban đầu. Chƣơng 3 sẽ thảo luận về phƣơng pháp xây dựng đặc trƣng
ảnh hƣởng đến hiệu quả tóm tắt dữ liệu với thuật toán DARA.
1.3.3 Chuyển đổi dữ liệu
Trong một cơ sở dữ liệu quan hệ, mỗi bản ghi đơn Ri đƣợc lƣu trữ trong bảng
đích có thể đƣợc liên kết với các bản ghi khác nhau đƣợc lƣu trữ trong bảng tham
chiếu. Trong hình 1.5, R biểu thị một tập gồm m bản ghi trong bảng đích và S biểu thị
một tập gồm n bản ghi (T1, T2, T3 , , Tn) trong bảng tham chiếu. Gọi Si là một tập
hợp con của S, Si   S, liên kết thông qua một khóa ngoại với một bản ghi đơn Ra
đƣợc lƣu trong bảng đích, trong đó Ra  R, liên kết của các bản ghi này có thể đƣợc
mô tả là Ra ← Si. Trong trƣờng hợp này, mỗi bản ghi duy nhất đƣợc lƣu trong bảng
đích T đƣợc liên kết với nhiều bản ghi đƣợc lƣu trong bảng tham chiếu NT.
Các bản ghi trong bảng tham chiếu tƣơng ứng với một bản ghi đích có thể đƣợc
biểu diễn dƣới dạng vector của các mẫu. Nhƣ vậy, dựa trên mô hình không gian
vector, mỗi bản ghi riêng biệt ở bảng đích có thể đƣợc biểu diễn bởi một vector các

mẫu dữ liệu trong bảng tham chiếu. Nói cách khác, mỗi bản ghi trong bảng đích liên
kết với một số bản ghi trong bảng tham chiếu đƣợc biểu diễn nhƣ một túi các mẫu
(bag of patterns), tức là các mẫu và tần số xuất hiện của chúng.

Hình 1.5: Liên kết 1:n giữa bảng đích và bảng tham chiếu
Túi các mẫu đƣợc định nghĩa nhƣ sau:
Định nghĩa 1.7 Trong một biểu diễn theo túi các mẫu, mỗi bản ghi đích lƣu trữ
trong bảng tham chiếu NT đƣợc biểu diễn bởi tập các mẫu và tần số các mẫu.

15
1.3.3.1 Quá trình mã hóa các mẫu tin thành số nhị phân
Trong thuật toán DARA, mỗi đối tƣợng đƣợc đại diện bởi một túi các mẫu. Các
mẫu này sẽ đƣợc mã hóa thành số nhị phân. Quá trình mã hóa các mẫu thành số nhị
phân phụ thuộc vào số lƣợng thuộc tính tồn tại trong bảng tham chiếu. Có hai trƣờng
hợp: bảng có duy nhất một thuộc tính và bảng có nhiều thuộc tính.
Bảng với một thuộc tính duy nhất
Trong trƣờng hợp này, chỉ có đúng một thuộc tính mô tả nội dung của bảng
tham chiếu liên kết với bảng đích. Quá trình chuyển đổi dữ liệu của bảng tham chiếu
đƣợc mô tả nhƣ hình 1.6 [2]. Ở đây, thuộc tính Trans là khóa chính của bảng Sales và
thuộc tính Customer là khóa ngoại, khóa này liên kết các bản ghi trong bảng tham
chiếu (bảng Sales) với các bản ghi trong bảng đích (bao gồm các Customer riêng biệt).
Đầu tiên, thuật toán tính lực lƣợng của miền thuộc tính trong bảng tham chiếu. Lực
lƣợng của một thuộc tính đƣợc định nghĩa là số các giá trị mà thuộc tính đó có thể có.
Một số mô hình chỉ áp dụng cho các dữ liệu rời rạc thì cần thực hiện rời rạc dữ liệu.

Hình 1.6: Chuyển đổi dữ liệu trong bảng tham chiếu với một thuộc tính
Để mã hóa các giá trị thành các số nhị phân, thuật toán tìm số bit n nhỏ nhất có
thể biểu diễn đƣợc tất cả các giá trị khác nhau của miền thuộc tính, ta có 2n-1 < |miền
của thuộc tính| ≤ 2n. Ví dụ, nếu thuộc tính có 5 giá trị khác nhau (London, New York,
Chicago, Paris, Kuala Lumpur) thì chỉ cần 3 bit (22 <5 ≤ 23) đại diện cho một trong

các giá trị (001, 010, 011, 100, 101). Một túi các mẫu đƣợc duy trì để theo dõi số
lƣợng mẫu và tần số xuất hiện của các mẫu này. Đối với mỗi mẫu đã đƣợc mã hóa, bộ

16
đếm tƣơng ứng trong túi các mẫu đƣợc tăng lên hoặc mẫu đƣợc thêm vào túi các mẫu
nếu mẫu đó chƣa có trong túi. Kết quả là, các túi các mẫu thu đƣợc nhƣ hình 1.6 có thể
đƣợc dùng để mô tả đặc điểm của các bản ghi tƣơng ứng.
Trong hình 1.6, số "2" đặt trƣớc các số nhị phân cho biết chỉ số của thuộc tính
có dạng số nhị phân. Vì chỉ có một thuộc tính tồn tại trong các bộ dữ liệu, tất cả các
mẫu đã đƣợc tạo ra đều thuộc về thuộc tính tƣơng ứng với cột thứ hai.
Bảng với nhiều thuộc tính
Bảng tham chiếu có thể có nhiều thuộc tính. Trong trƣờng hợp này, thuật toán
có thể xây dựng các đặc trƣng mới từ các thuộc tính ban đầu. Kết quả là, có nhiều đại
diện phong phú hơn của mỗi bản ghi đích trong bảng tham chiếu. Phƣơng pháp đƣợc
sử dụng để mã hóa các mẫu từ các thuộc tính sẽ ảnh hƣởng đến kết quả cuối cùng của
công việc mô hình hóa [5].
Trong trƣờng hợp này, giả sử có nhiều hơn một đặc trƣng mô tả nội dung của
bảng tham chiếu liên kết với bảng đích. Tất cả các giá trị liên tục của các thuộc tính
đƣợc rời rạc hoá và các khoảng đƣợc lấy làm số các yếu tố trong một tập hợp của miền
thuộc tính. Sau khi mã hóa các mẫu bằng số nhị phân, thuật toán xác định tập con các
thuộc tính đƣợc sử dụng để xây dựng một đặc trƣng mới.
Sau đây là ví dụ về một thuật toán đơn giản để xây dựng đặc trƣng mà không sử
dụng phép chấm điểm đặc trƣng để tạo ra các mẫu biểu diễn dữ liệu vào cho thuật toán
DARA. Cho F=(F1,F2,F3, ,Fk) biểu thị các cột thuộc k trƣờng hay các thuộc tính
trong bảng tham chiếu. Đặt dom(Fi)=(Fi, 1 ,Fi, 2 , Fi, 3, , Fi, n) biểu thị miền của
thuộc tính Fi, với n giá trị khác nhau. Nhƣ vậy, ta có biểu diễn của một bản ghi đƣợc
lƣu trữ trong bảng tham chiếu với các giá trị này (F1,a , F2, b, F3, c, F4, d, , Fk-1, b,
Fk, n), trong đó F1,adom(F1), F2,bdom(F2), F3,c  dom(F3), F4,d dom(F4), ,
Fk-1,b dom(Fk-1), Fk,n  dom(Fk). Chọn p là số thuộc tính đƣợc kết hợp để tạo ra
một đặc trƣng mới (1≤p≤k). Danh sách các mẫu đƣợc tạo ra với các giá trị khác nhau

của p đƣợc mô tả trong bảng 3.1.
Bảng 1.1: Danh sách các mẫu được tạo ra
p
Danh sách các mẫu đƣợc tạo ra
1
F1,a, F2,b, F3,c, F4,d, , Fk−1,b, Fk,n
2
F1,aF2,b, F3,cF4,d, , Fk−1,bFk,n với n chẵn
F1,aF2,b, F3,cF4,d, , Fk,n với n lẻ
k
F1,aF2,bF3,cF4,d Fk−1,bFk,n
Đối với mỗi bản ghi, một túi các mẫu đƣợc duy trì để theo dõi các mẫu xuất
hiện và tần số của chúng. Với mỗi một mẫu mới đƣợc mã hóa, nếu mẫu đã tồn tại
trong túi, biến đếm tƣơng ứng đƣợc tăng lên, ngƣợc lại mẫu đó đƣợc thêm vào túi và

17
biến đếm đƣợc khởi tạo cho mẫu này là 1. Kết quả là, túi các mẫu này đƣợc sử dụng để
mô tả bản ghi đích liên kết với chúng.
Ví dụ, hình 1.7 cho thấy quá trình chuyển đổi dữ liệu đã đƣợc lƣu trong bảng
tham chiếu với nhiều thuộc tính [2]. Trong ví dụ này, thuộc tính Trans là khóa chính
của bảng Sales và thuộc tính Customer là khóa ngoại liên kết các bản ghi đƣợc lƣu
trong bảng tham chiếu (bảng Sales) với bản ghi đƣợc lƣu trong bảng đích (bao gồm
các Customer riêng). Định dạng của các mẫu đƣợc tạo ra phụ thuộc vào tham số p (p =
1, p = 2 và p = k), trong đó p là số các thuộc tính đƣợc kết hợp để tạo ra các mẫu và k
là tổng số thuộc tính. Thuật toán này đƣợc gọi là P
Single
khi p = 1 và P
all
khi p = k.


Hình 1.7: Chuyển đổi dữ liệu trong bảng tham chiếu với nhiều thuộc tính
Trong hình 1.7, vì có nhiều hơn một thuộc tính tồn tại trong bảng dữ liệu, khi
p=1, các mẫu mã hóa đƣợc đặt trƣớc chỉ số thuộc tính tƣơng ứng từ "2" đến k, với k là
số các thuộc tính trong bảng dữ liệu.

18
Quá trình mã hóa đƣợc thực hiện để chuyển dữ liệu trong bảng tham chiếu có
quan hệ nhiều-một với bảng đích thành dữ liệu đại diện trong một mô hình không gian
vector [20]. Với dạng biểu diễn này, có thể phân cụm dữ liệu dễ dàng bằng cách sử
dụng kỹ thuật phân cụm phân cấp hoặc kỹ thuật phân cụm phân hoạch nhƣ một
phƣơng pháp để tóm tắt dữ liệu.
1.3.3.2 Biểu diễn dữ liệu trong mô hình không gian Vector
Giả sử một cơ sở dữ liệu quan hệ DB có bảng đích gồm n bản ghi. Trong đó,
P = P1, , Pm là tập các mẫu khác nhau tồn tại trong bản ghi Oi và mỗi mẫu Pi có thể
không xuất hiện hoặc xuất hiện nhiều lần trong bản ghi đích Oi, nghĩa là |Pi|≥ 0, với i
= 1, , m. Mỗi bản ghi đích Oi  DB (i = 1, 2, , n) đƣợc mô tả bởi tối
đa m mẫu khác nhau mà mỗi mẫu có tần số xuất hiện tƣơng ứng [2]:
(1.1)
Pj (Oi) đại diện cho mẫu thứ j của bản ghi thứ i và |Pj (Oi)| đại diện cho tần
số của mẫu thứ j của bản ghi thứ i, |Ob (Pj)| đại diện cho số bản ghi đích tồn tại
trong các dữ liệu có mẫu thứ j. Nếu tất cả các mẫu tồn tại trong Oi thì số lƣợng mẫu
của Oi là |Oi|=m ngƣợc lại |Oi|<m.
Mỗi bản ghi đích Oi đƣợc coi là một vector trong không gian mẫu và có thể
đƣợc biểu diễn nhƣ sau:

Trong đó, rfj là tần số của mẫu thứ j trong bản ghi đích, ofj là số bản ghi đích
chứa mẫu thứ j và n là số các bản ghi đích.
1.3.4 Phân cụm dữ liệu
Dữ liệu sau khi đƣợc chuyển đổi thành một dạng biểu diễn trong mô
hình không gian vector sẽ trở thành đầu vào cho một thuật toán phân cụm. Ý

tƣởng của phƣơng pháp này là chuyển dữ liệu đại diện của tất cả các bản ghi đích
trong môi trƣờng đa quan hệ vào mô hình không gian vector và xác định
khoảng cách tƣơng quan cho tất cả các đối tƣợng để phân nhóm chúng. Những đối
tƣợng này đƣợc nhóm lại dựa trên sự tƣơng đồng của chúng. Ví dụ, trong hình 1.2 ta
tính đƣợc:
O
1
=
((X
,111):2:2,
(X
,112):2:2,
(X
,113):2:2,
(Z,117):1:2),
O
2
=
((X
,111):1:2,
(X
,112):1:2,
(X
,113):1:2,
(Y ,116):1:2),
O
3
=
((Y
,116):1:2,

(Z ,117):1:2),
Các vector đặc trƣng cho O1, O2 and O3 tƣơng ứng cho các trƣờng hợp
((X,111), (X ,112), (X ,113), (Z ,117), (Y ,116)) đƣợc tính nhƣ sau:

19

Độ tƣơng đồng (similarity) giữa hai đối tƣợng đƣợc xác định bởi khoảng cách
cosine nhƣ biểu thức 1.3

Trong ví dụ này, các giá trị cho cos (O1, O2), cos (O1, O3) và cos (O2, O3) lần
lƣợt đƣợc tính nhƣ sau:

Với khoảng cách cosine, giá trị góc càng lớn thì độ tƣơng đồng càng lớn, nghĩa
là khoảng cách giữa các vector càng nhỏ. Vì vậy, có thể kết luận rằng độ tƣơng đồng
của bản ghi đích O1 với bản ghi đích O2 lớn hơn độ tƣơng đồng của bản ghi đích O1
với bản ghi đích O3.
1.3.5 Mô tả đặc điểm cụm và mô hình hoá dữ liệu
Mô tả đặc điểm cụm là quá trình tìm kiếm các mẫu mô tả tốt nhất
cho đặc điểm của các cụm. Mô tả đặc điểm cụm có thể đƣợc thực hiện
bằng cách tìm kiếm một vài mẫu chung cho cụm. Một cách thục hiện thông thƣờng là
lấy đại diện năm hay mƣời mẫu xuất hiện thƣờng xuyên nhất trong các vector trọng
tâm của cụm. Khi thuật toán DARA đƣợc phát triển dựa trên ma trận TF-IDF, các mẫu
này có thể đƣợc trích xuất trực tiếp để đặc trƣng cho cụm đƣợc hình thành. Vấn đề xây
dựng đặc trƣng để cải thiện kết quả của phƣơng pháp tiếp cận tóm tắt dữ liệu trong
nghiên cứu này sẽ đƣợc đề cập đến ở phần sau. Kết quả cho thấy các mẫu thƣờng
xuyên nhất trích xuất từ các vector trọng tâm của cụm đƣợc rút ra dựa trên những đặc
trƣng đã xây dựng.
Sau khi tóm tắt dữ liệu đƣợc lƣu trữ trong các bảng tham chiếu, công việc khai
phá dữ liệu thực sự chuyển sang giai đoạn mô hình hoá, dựa trên các mục tiêu đã xác
định và sự đánh giá dữ liệu sẵn có, một thuật toán thích hợp đƣợc lựa chọn và thực

hiện trên dữ liệu đã đƣợc xử lí.

20
CHƢƠNG II - GIẢI THUẬT DI TRUYỀN
2.1 Giới thiệu
Giải thuật di truyền, cũng nhƣ các thuật toán tiến hoá nói chung, đƣợc hình
thành dựa trên quan niệm cho rằng quá trình tiến hoá tự nhiên là hoàn hảo nhất, hợp lý
nhất và tự nó đã mang tính tối ƣu.
Trong tự nhiên, mỗi cá thể có một tập các tính chất và đặc điểm riêng biệt đƣợc
thể hiện ra ngoài môi trƣờng gọi là kiểu hình. Kiểu hình này đƣợc quyết định bởi cấu
trúc của các gene trong cơ thể, đƣợc gọi là kiểu gene. Sự đa dạng về kiểu gene của các
cá thể dẫn đến sự đa dạng về kiểu hình của một quần thể sinh học. Quá trính phát triển
của mỗi quần thể tuân theo quy luật chọn lọc tự nhiên mà tiến hoá qua các thế hệ kế
tiếp nhau. Trong đó, các cá thể của thế hệ sau đƣợc sinh ra từ thế hệ trƣớc thông qua
quá trình sinh sản. Thông thƣờng, cấu trúc gien của mỗi cá thể đƣợc sinh ra mang một
phần cấu trúc gien của cha và mẹ nhƣng nó cũng có thể chứa các gien mà cả cha và mẹ
đều không có khi hiện tƣợng đột biến xảy ra. Trải qua cạnh tranh tự nhiên, cá thể nào
có kiểu hình (và do đó là kiểu gene) thích nghi cao hơn với môi trƣờng phát triển thì
sẽ có khả năng lớn hơn trong tồn tại và sản sinh con cháu, do đó kiểu gene này tiến
hoá và dần đƣợc hoàn thiện. Quá trình tiến hoá này đƣợc lặp đi lặp lại, những cá thể có
kiểu gene phù hợp sẽ sống sót và phát triển, các cá thể kém thích nghi dần bị loại bỏ.
Dựa trên ý tƣởng trừu tƣợng hoá quá trình tiến hoá tự nhiên để giải bài toán tối
ƣu, mỗi lời giải tiềm năng đƣợc xem nhƣ một cá thể và đƣợc mã hoá dƣới dạng thích
hợp gọi là một nhiễm sắc thể. Giải thuật di truyền (GA) mô phỏng quá trình tiến hoá tự
nhiên trên một quần thể nhiễm sắc thể để tìm lời giải cho bài toán.
2.2 Giải thuật di truyền cổ điển
GA cổ điển đƣợc Holland giới thiệu để tối ƣu hoá bài toán:
max{f(x)/ x

M


R
n
} (2.1)
Ở đây, M là hình hộp
 

n
i
ii
ba
1
,

trong không gian vector thực n chiều R
n
, f nhận
các giá trị dƣơng trên M.
Thủ tục GA đƣợc xây dựng nhƣ sau.
- Mỗi x trong M đƣợc mã hoá bởi một chuỗi nhị phân độ dài m z=(z
1
, ,z
m
)
gọi là nhiễm sắc thể hay một cá thể, mỗi z
i
đƣợc gọi là một gene.
- Xây dựng hàm thích nghi eval trên tập nhiễm sắc thể để đánh giá độ thích
nghi của mỗi cá thể: eval(z) = f(x), trong đó x là vector tƣơng ứng với z.
- Với t = 0, quần thể ban đầu P(0) đƣợc khởi tạo ngẫu nhiên gồm N nhiễm sắc

thể và thực hiện quá trình tiến hoá theo cấu trúc:

21
Procedure GA
Begin
t 0;
Khởi tạo P(t); // P(t) là quần thể thế hệ thứ t
Đánh giá P(t);
Repeat
t t+1;
Chọn lọc Q(t) từ P(t-1);
Tái tạo P(t) từ Q(t); // bởi các toán tử di truyền,
Đánh giá P(t) và chọn các thể tốt nhất;
Until điều_kiện_kết_thúc,
Biểu diễn lời giải;
End;
Thuật toán di truyền có thể mô tả nhƣ hình 2.1

Hình 0.2: Sơ đồ cấu trúc thuật toán di truyền

22
Các bƣớc của quá trình tiến hóa đƣợc lặp lại qua các thế hệ. Tại thế hệ thứ t,
giải thuật duy trì một tập lời giải P (t) ={x
t
1
, …, x
t
n
}. Mỗi lời giải x
t

i
đƣợc đánh giá “độ
thích nghi”. Một tập lời giải mới đƣợc xây dựng bằng cách “chọn lọc” các cá thể theo
một cơ chế thích hợp dựa vào độ thích nghi, kết quả thu đƣợc là một tập lời giải trung
gian. Tiếp theo, một số cá thể trong tập lời giải này đƣợc biến đổi bằng các toán tử di
truyền để tạo thành các lời giải mới cho thế hệ t+1. Các toán tử di truyền đƣợc sử dụng
là lai ghép (crossover) và đột biến (mutation) sẽ đƣợc giới thiệu trong phần 2.2.2.
2.2.1 Phƣơng pháp mã hoá và giải mã.
Giải thuật di truyền cổ điển biểu diễn nhiễm sắc thể dƣới dạng mã nhị phân và
lời giải tƣơng ứng thu đƣợc sau khi thực hiện quá trình giải mã.
- Mã hoá:
Giả sử ta cần cực đại hàm f với sai số mỗi biến x
i
là 10
-p
. Ta chia mỗi đoạn
[a
i
,b
i
] thành (b
i
-a
i
)10
p
đoạn bằng nhau và ký hiệu m
i
là số tự nhiên nhỏ nhất thoả mãn:


1210)( 
i
m
p
ii
ab
.
Khi đó, nếu x=(x
1
, ,x
i
, x
n
) và x
i
thuộc đoạn thứ k thì x
i
đƣợc mã hoá bởi
chuỗi nhị phân độ dài m
i
có dạng
), ,(
01
bb
i
m 
sao cho





1
0
2
i
m
j
j
j
bk
sẽ thoã mãn yêu cầu
về độ chính xác và x đƣợc biễu diễn bởi chuỗi nhị phân có độ dài



n
j
j
mm
1
.
- Giải mã:
Với mỗi đoạn gene
), ,(
01
bb
i
m 
ta xác định k
i

theo hệ số 10:




1
0
10
)2(
i
m
j
j
ji
bk

Từ đó,
12
)(
.



i
m
ii
iii
ab
kax
nghĩa là

12
)(
.)2(
1
0
10






i
i
m
ii
m
j
j
jii
ab
bax
.
2.2.2 Quá trình chọn lọc
Các cá thể đƣợc chọn lọc theo độ thích nghi. Cá thể có độ thích nghi cao hơn sẽ
có khả năng đƣợc chọn nhiều hơn.
Với mỗi quần thể hiện tại P(t-1) gồm N cá thể: P(t-1) ={v
1
, ,v
N

}, bánh xe sổ xố
(roulette Wheel) đƣợc xây dựng để thực hiện quá trình chọn lọc nhƣ sau:
- Bánh xe sổ xố
Tính tổng độ thích nghi của các cá thể trong quần thể



N
i
i
vevalF
1
)(
.
Tính xác suất chọn p
i
của từng cá thể v
i
:
Fvevalp
ii
/)(
.
Tính xác suất tích luỹ q
i
của v
i
:




i
j
ji
pq
1
.

23
Bánh xe sổ xố đƣợc chia thành N phần, mỗi phần tƣơng ứng với xác suất chọn
p
i
của một cá thể. Mỗi lần quay bánh xe, khi bánh xe dừng, mũi tên chỉ điểm chọn
thuộc phần nào thì cá thể ứng với phần đó đƣợc chọn.
Ví dụ, hình 0.2 minh họa cho bánh xe sổ xố với quần thể có 6 cá thể. Trong đó,
cá thể 1 có xác suất chọn lọc là 25%, có nghĩa là khi bánh xe quay, nó có khả năng
đƣợc chọn là 0.25. Tƣơng tự nhƣ vậy với các cá thể còn lại.

Hình 0.3: Bánh xe sổ xố với một quần thể có 5 cá thể
- Quá trình chọn lọc
Quá trình chọn lọc đƣợc thực hiện bằng cách quay bánh xe sổ xố N lần, mỗi lần
chọn một cá thể từ quần thể hiện tại vào quần thể trung gian Q(t). Trong thực tế, cách chọn
lọc này có thể đƣợc thực hiện nhƣ sau:
 Với mỗi số tự nhiên k {1,2, ,N}, tạo một số ngẫu nhiên r
k
[0,1].
 Nếu r
k
<q
1

thì chọn v
1
, ngƣợc lại, chọn v
i
mà q
i
 r
k
> q
i-1

Hiển nhiên, ở đây mỗi cá thể có thể đƣợc chọn nhiều lần và quần thể mới vẫn
đƣợc xem là có N cá thể. Các cá thể có độ thích nghi lớn sẽ có khả năng đƣợc chọn
nhiều hơn. Điều này phù hợp với lý thuyết sơ đồ [1]: các cá thể tốt nhất có nhiều bản
sao hơn, các cá thể trung bình không thay đổi và các cá thể kém thích nghi nhất thì mất
đi.
2.2.3 Quá trình tái tạo
Quá trình tái tạo dựa trên các toán tử di truyền là lai ghép và đột biến.
- Lai ghép
Lai ghép (tƣơng giao chéo) hai nhiễm sắc thể x=( x
1,
x
2
… x
m
) và y=(y
1
,y
2
,y

m
)
với điểm lai k (có thể ngẫu nhiên) sẽ đƣợc hai nhiễm sắc thể mới là:
x’ = (x
1,
x
k ,
y
k+1
y
m
)
y’ =( y
1
y
k
,x
k+1
x
m
)

24
- Đột biến
Nếu gene x
k
của nhiễm sắc thể x=( x
1,
x
2

… x
m
) đột biến thì ta đƣợc nhiễm sắc
thể mới x’ có:







kix
kix
x
i
i
i
1

- Thủ tục tái tạo
Cho trƣớc các xác suất tƣơng giao chéo p
c
và xác suất đột biến p
m,
quá trình tái
tạo đƣợc thực hiện nhƣ sau:
 Đối với mỗi nhiễm sắc thể v
i
thuộc Q(t), tạo một số ngẫu nhiên r[0,1].
Nếu r < p

c
thì v
i
đƣợc đƣa vào tập cá thể cha mẹ để lai ghép.
 Tập lai ghép đƣợc chia thành cặp (nếu lẻ thì có thể thêm hoặc bớt ngẫu
nhiên một nhiễm sắc thể khác) để áp dụng toán tử lai ghép.
 Sau khi tƣơng giao chéo, đối với mỗi gene của mỗi nhiễm sắc thể ta tạo
một số ngẫu nhiên r[0,1]. Nếu r < p
m
thì gene này đƣợc đột biến.
Quá trình trên cho ta quần thể P(t) của thế hệ thứ t và đƣợc đánh giá để chọn cá
thể có độ thích nghi tốt nhất. Sau đó, quần thể này lại đƣợc đƣa vào chu trình lặp với
các bƣớc chọn lọc, lai ghép và đột biến. Điều kiện kết thúc quá trình tiến hoá thông
thƣờng là số lần lặp định trƣớc và lời giải là một hay một số cá thể tốt nhất ở lần lặp
cuối hoặc của mọi lần lặp.
2.2.4 Sự hội tụ của GA
Những kết quả nghiên cứu, đánh giá về sự hội tụ của GA hiện nay còn rất
nghèo nàn. Các nghiên cứu thƣờng chỉ ở mức chứng minh sự hội tụ theo xác suất tới
lời giải tối ƣu của bài toán. Tuy nhiên, giải thuật di truyền vẫn là một giải thuật đƣợc
ƣa thích để giải các bài toán tối ƣu khó trong thực tế và cho lời giải đủ tốt. Đặc biệt,
GA tỏ ra rất hiệu quả đối với các bài toán mà hàm mục tiêu phức tạp, có nhiều cực trị
địa phƣơng và không trơn. Đối với các bài toán đã có phƣơng pháp giải tốt bằng
phƣơng pháp truyền thống thì GA thƣờng kém hiệu quả hơn.
Vì GA không đảm bảo hội tụ đến lời giải tối ƣu toàn cục nên điều kiện để kết
thúc quá trình tiến hóa quần thể thƣờng là khi đạt đến một mức giá trị yêu cầu của bài
toán hoặc dựa vào số thế hệ: xác định trƣớc số thế hệ cần tiến hóa, khi trải qua đủ số
thế hệ đó thì dừng. Điều kiện kết thúc cũng có thể tính theo thời gian và quá trình tiến
hoá sẽ kết thúc sau một khoảng thời gian định trƣớc.
2.2.5 Ví dụ
Cho bài toán:


25
Tìm bộ hai giá trị (x
1
,x
2
) để hàm: f(x
1
,x
2
)= 10 +x
1
sinx
1
+ x
2
sinx
2
, đạt giá trị cực
đại trên miền -1≤ x
1
≤3 ; 3 ≤ x
2
≤5 với sai số các biến là 10
-2
.
Có thể áp dụng giải thuật di truyền để giải bài toán này nhƣ sau:
- Biểu diễn nhiễm sắc thể:
Vì a
1

-b
1
=3-(-1)=4, 4 x100 =400 và 2
8
< 400<2
9
nên cần 9 gene để biểu diễn x
1
.
Tƣơng tự, cần 8 gene để biễu diễn x
2
.
Nhƣ vậy, có thể dùng một xâu nhị phân 17 bit để biểu diễn một nhiễm sắc thể
tƣơng ứng với mỗi bộ 2 giá trị (x
1
,x
2
) thoã mãn điều kiện của bài toán.
Hàm thích nghi eval(v
i
) = f(x
1
,x
2
)
- Khởi tạo quần thể:
Giả sử khởi tạo ngẫu nhiên 10 cá thể đƣợc:
v
1
=(10011010000000111) tƣơng ứng với x

1
=1,41 ; x
2
=3,15 ; eval(v
1
)=12,68 ;
v
2
=(11100010010011011) tƣơng ứng với x
1
=2,54 ; x
2
=4,22 ; eval(v
2
)=14,78 ;
v
3
=(00001000001100100) tƣơng ứng với x
1
=-0,87; x
2
=3,78 ; eval(v
3
)=10,94 ;
v
4
=(10001100010110100) tƣơng ứng với x
1
=1,19 ; x
2

=4,41 ; eval(v
4
)=10,81 ;
v
5
=(00011101100101001) tƣơng ứng với x
1
=-0,54 ; x
2
=3,32 ; eval(v
5
)=7,67 ;
v
6
=(00010100001001010) tƣơng ứng với x
1
=-0,69 ; x
2
=3,58 ; eval(v
6
)=7,53 ;
v
7
=(00100010000011010) tƣơng ứng với x
1
=-0,47 ; x
2
=3,20 ; eval(v
7
)=9,23 ;

v
8
=(10000110000111010) tƣơng ứng với x
1
=1,01 ; x
2
=3,45 ; eval(v
8
)=7,52 ;
v
9
=(01000000011010001) tƣơng ứng với x
1
=0,00 ; x
2
=4,64 ; eval(v
9
)=5,67 ;
v
10
=(00010100001001010) tƣơng ứng với x
1
=0,88 ; x
2
=3,19 ; eval(v
10
)=9,94 .
Cá thể tốt nhất là v2=(11100010010011011) với eval(v2)=14,78.
Tổng độ thích nghi của quần thể F=96,77.
- Chọn lọc:

Giả sử chọn ngẫu nhiên đƣợc các r
i
tƣơng ứng là:
r
1
=0,52; r
2
=0,17;
r
3
=0,70; r
4
=0,01;
r
5
=0,78; r
6
=0,31;
r
7
=0,42; r
8
=0,28;
r
9
=0,64; r
10
=0,95
thì kết quả chọn lọc đƣợc quần thể trung gian Q(1) nhƣ bảng 2.1


26
Bảng 2.1 Kết quả thực hiện quá trình chọn lọc
Stt
p
i

q
i

Số ngẫu
nhiên
Cá thể đƣợc chọn
Đánh số lại
1.
0,13
0,13
0,52
v
5
=(00011101100101001)
u
1
2.
0,15
0,28
0,17
v
2
=(11100010010011011)
u

2
3.
0,11
0,40
0,70
v
7
=(00100010000011010)
u
3
4.
0,11
0,51
0,78
v
1
=(10011010000000111)
u
4

5.
0,08
0,59
0,42
v
8
=(10000110000111010)
u
5
6.

0,08
0,67
0,31
v
3
=(00001000001100100)
u
6
7.
0,10
0,76
0,42
v
4
=(10001100010110100)
u
7
8.
0,08
0,84
0,28
v
2
=(11100010010011011)
u
8
9.
0,06
0,90
0,64

v
6
=(00010100001001010)
u
9
10.
0,10
1,00
0,95
v
6
=(00010100001001010)
u
10
- Lai ghép:
Giả sử với p
c
=0,25 ta chọn đƣợc cặp nhiễm sắc thể cha mẹ là
u
3
= (00100010000011010)
u
5
= (10000110000111010)
Với điểm trao đổi k=5, thực hiện lai ghép sẽ đƣợc hai cá thể con:
u
3
'=(00100110000111010)
u
5

'=(10000010000001010)

- Đột biến:
Với xác suất đột biến là p
m
=0,01, các gene đánh số từ 1 đến 170, giả sử chọn
đƣợc gene thứ 81 (gene thứ 13 của cá thể thứ 5) và gene thứ 127 (gene thứ 8 của cá thể
thứ 8), thực hiện đột biến các gene này sẽ đƣợc hai cá thể mới:
v
’
5
=(100000100000011010)
v’
8
=(11100011010011011)
Kết quả P(1) là :
v’1=(00011101100101001)
v’2=(11100010010011011)
v’3=(00100110000111010)
v’4=(10011010000000111)
v’5=(100000100000011010)
v’6=(00001000001100100)