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

PHAN MINH HẢI

CÁC KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU
SỬ DỤNG TÍNH TOÁN TIẾN HÓA

Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. BÙI THU LÂM

Hà Nội, 2014


2

LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của bản thân, được xuất phát từ
yêu cầu do giáo viên hướng dẫn đề ra để hình thành hướng nghiên cứu. Các số
liệu có nguồn gốc rõ ràng tuân thủ đúng nguyên tắc và kết quả trình bày trong
luận văn được thu thập được trong quá trình nghiên cứu là trung thực chưa từng
được ai công bố trước đây.
Hà Nội, tháng 10 năm 2014
Tác giả luận văn

Phan Minh Hải

1.1.3. Các phương pháp khai phá dữ liệu ......................................................................... 12
1.1.4. Các lĩnh vực ứng dụng thực tiễn của KPDL ........................................................... 12
1.1.5. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL. ................................ 13
1.1.6. Các yêu cầu của phân cụm ...................................................................................... 13
1.1.7. Phân cụm với giải thuật Kmean ............................................................................. 15

1.2. Tổng quan về giải thuật tiến hóa ...................................................................... 16
1.2.1. Giải thuật di truyền ................................................................................................. 16
1.2.1.1. Lịch sử phát triển ............................................................................................. 18
1.2.1.2. Các bước áp dụng giải thuật di truyền .............................................................. 19
1.2.1.2.1. Mã hóa dữ liệu .......................................................................................... 19
1.2.1.2.2. Khởi tạo quần thể ...................................................................................... 19
1.2.1.2.3. Xác định hàm thích nghi ........................................................................... 19
1.2.1.2.4. Quá trình lai ghép...................................................................................... 20
1.2.1.2.5. Quá trình đột biến ..................................................................................... 21
1.2.1.2.6. Quá trình chọn lọc ..................................................................................... 21
1.2.1.3. Các tham số của giải thuật di truyền................................................................. 21
1.2.1.4. Sơ đồ quá trình tính toán của giải thuật di truyền ............................................. 22
1.2.2. Giải thuật tiến hóa vi phân ...................................................................................... 25
1.2.2.1. Nguyên lý hoạt động ........................................................................................ 25
1.2.2.2. Sơ đồ giải thuật tiến hóa vi phân ...................................................................... 25

1.3. Kết luận ............................................................................................................. 28
CHƯƠNG 2 GIẢI THUẬT PHÂN CỤM DỰA TRÊN LAI GHÉP GIẢI THUẬT
TIẾN HÓA VÀ KMEANS ...................................................................................... 29
2.1. Giải thuật phân cụm trong tính toán tiến hóa ................................................. 29
2.1.1.Giải thuật tổng quát cho phân cụm sử dụng giải thuật di truyền ............................... 29
2.1.2. Biểu diễn cá thể ...................................................................................................... 30
2.1.3. Tính toán độ thích nghi ........................................................................................... 30
2.1.4. Phép chọn (Selection) ............................................................................................. 31

CDL

Cụm dữ liệu

CNTT

Công nghệ thông tin

CSDL

Cơ sở dữ liệu

DE

Giải thuật tiến hóa vi phân

DL

Dữ liệu

GA

Giải thuật di truyền

KPDL

Khai phá dữ liệu

KPTT


Bảng 3.6: Kết quả thử nghiệm các giải thuật với số cụm bằng 7..................... 44


8

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ
Hình 1.1: Quá trình KPTT ............................................................................. 11
Hình 1.2: Ví dụ về mã hóa nhiễm sắc thể ...................................................... 19
Hình 1.3: Lai ghép hai cá thể ......................................................................... 20
Hình 1.4: Đột biến một nhiễm sắc thể ........................................................... 21
Hình 1.5: Sơ đồ quá trình tính toán của giải thuật di truyền ............................ 23
Hình 1.6: Sơ đồ giải thuật tiến hóa vi phân ..................................................... 26
Biểu đồ 3.1: Tổng hợp kết quả của các giải thuật với giá trị trung bình trong
trường hợp 1 (hình a) và trường hợp 2 (hình b) .............................................. 45


9

MỞ ĐẦU
Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng tương tự nhau trong
tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một cụm là tương
đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân
cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì
thế, có thể coi phân cụm dữ liệu là một cách học không giám sát (unsupervised
learning). Các Kỹ thuật phân cụm được ứng dụng rất nhiều trong các lĩnh vực tài
chính ngân hành để phân lọai các nhóm khách hàng khác nhau. Ngoài ra phân
cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các giải thuật
khai phá dữ liệu khác như phân loại và mô tả đặc điểm, có tác dụng phát hiện ra
các cụm.
Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp phân cụm

nghiên cứu và ứng dụng, đó là khám phá tri thức và khai phá dữ liệu.
Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các
ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một
chương trình dưới một dạng nhất định. Các bits thường được sử dụng để đo
thông tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và
rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức
được xem như là các thông tin tích hợp, bao gồm các sự kiện và mối quan
hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu. Nói cách khác,
tri thức có thể được coi là dữ liệu ở mức độ cao của sự trừu tượng và tổng
quát[2].
Khám phá tri thức hay phát hiện tri thức trong CSDL là một quy trình nhận biết
các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng
hợp, hợp thức, khả ích và có thể hiểu được.
Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, gồm các giải
thuật khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán
chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu.
Nói cách khác, mục tiêu của Khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình
tồn tại trong CSDL nhưng ẩn trong khối lượng lớn dữ liệu.
1.1.2. Quá trình khám phá tri thức
Quá trình khám phá dữ liệu có thể chia thành các giai đoạn như sau, xem
hình 1.1 [3]:
Giai đoạn 1. Trích chọn dữ liệu: Đây là bước trích chọn những tập dữ liệu cần
được khai phá từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định.
Giai đoạn 2. Tiền xử lý dữ liệu: Đây là bước làm sạch dữ liệu (xử lý những dữ
liệu không đầy đủ, nhiễu, không nhất quán, ...), rút gọn dữ liệu (sử dụng hàm


11

nhóm và tính tổng, các phương pháp nén dữ liệu, lấy mẫu, ...), rời rạc hóa dữ


Flat files

Hình 1.1: Quá trình khám phá tri thức

Tri thức


12

1.1.3. Các phương pháp khai phá dữ liệu
Với hai mục đích khai phá dữ liệu là Mô tả và Dự đoán, người ta thường
sử dụng các phương pháp sau cho khai phá dữ liệu [3]:
o Luật kết hợp (association rules)
o Phân lớp (Classfication)
o Hồi qui (Regression)
o Trực quan hóa (Visualiztion)
o Phân cụm (Clustering)
o Tổng hợp (Summarization)
o Mô hình ràng buộc (Dependency modeling)
o Biểu diễn mô hình (Model Evaluation)
o Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)
o Phương pháp tìm kiếm (Search Method)
Có nhiều phương pháp khai phá dữ liệu được nghiên cứu ở trên, trong đó có ba
phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết
hợp, Phân lớp dữ liệu và Phân cụm dữ liệu.
1.1.4. Các lĩnh vực ứng dụng thực tiễn của KPDL
KPDL là một lĩnh vực mới phát triển nhưng thu hút được khá nhiều nhà nghiên
cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực ứng
dụng thực tế điển hình của KPDL[2]:

sát - Học không thày (unsupervised learning).
- Luật kết hợp (association rules): Là dạng luật biểu diễn tri thức ở dạng khá
đơn giản (Ví dụ: 80% sinh viên đăng ký học CSDL thì có tới 60% trong số họ
đăng ký học Phân tích thiết kế hệ thống thông tin). Hướng tiếp cận này được
ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, viễn
thông, tài chính và thị trường chứng khoán,...
- Phân tích chuỗi theo thời gian (sequential/temporal patterns): Cũng tương tự
như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính thứ tự và tính thời
gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y, phản ánh sự xuất
hiện của biến cố X sẽ dẫn đến việc xuất hiện biến cố Y. Hướng tiếp cận này
được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi
chúng có tính dự báo cao.
- Mô tả khái niệm (concept desccription & summarization): Lớp bài toán
này thiên về mô tả, tổng hợp và tóm tắt khái niệm (Ví dụ: tóm tắt văn bản).
1.1.6. Các yêu cầu của phân cụm
Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng
dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc biệt
của chúng. Sau đây là những yêu cầu cơ bản của phân cụm trong KPDL
[3]:


14

Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những
tập dữ liệu khoảng vài trăm đối tượng, tuy nhiên, một CSDL lớn có thể chứa tới
hàng triệu đối tượng. Việc phân cụm với một tập dữ liệu lớn có thể làm ảnh
hưởng tới kết quả. Vậy làm cách nào để chúng ta có thể phát triển các giải
thuật phân cụm có khả năng mở rộng cao đối với các CSDL lớn?
Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều giải thuật
được thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy nhiên,

15

cụm là có chất lượng tốt nếu nó áp dụng được cho dữ liệu có từ 3 chiều trở lên.
Nó là sự thách thức với các đối tượng dữ liệu cụm trong không gian với số
chiều lớn, đặc biệt vì khi xét những không gian với số chiều lớn có thể rất thưa
và có độ nghiêng lớn.
Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể cần thực hiện phân
cụm dưới các loại ràng buộc khác nhau. Một nhiệm vụ đặt ra là đi tìm những
nhóm dữ liệu có trạng thái phân cụm tốt và thỏa mãn các ràng buộc.
Dễ hiểu và dễ sử dụng: Người sử dụng có thể chờ đợi những kết quả phân cụm
dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần được giải
thích ý nghĩa và ứng dụng rõ ràng.
1.1.7. Phân cụm với giải thuật Kmean
Cho tập dữ liệu D gồm n đối tượng trong không gian Euclidean. Phương pháp
này sẽ phân hoạch các đối tượng trong D vào trong k cụm, C1, .., Ck, trong đó Ck
⊂ D và Ci ∩ Cj = ∅ (trong đó, 1 ≤ i, j ≤ k). Hàm mục tiêu được sử dụng để đánh
giá độ các đối tượng trong một cụm tương tự nhau, các đối tượng thuộc các cụm
khác nhau sẽ không tương tự. Sự khác nhau giữa một đối tượng p ∈ Ci và ci
được thể hiện bằng phép đo khoảng cách Euclidean dist(p, ci) [3].
Đặc tính của cụm Ci được xác định bởi sự khác nhau trong cụm theo công thức
sau:

trong đó, ci là trọng tâm cụm của Ci, p là điểm thuộc Ci
Giải thuật phân cụm Kmean:
Input:
k: số cụm
D: tập dữ liệu chứa n đối tượng
Output:
một tập hợp k các cụm
Thứ tự thực hiện giải thuật:

1.2.1. Giải thuật di truyền
Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải
pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải
thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý
của tiến hóa như di truyền, đột biến, chọn lọc tự nhiên và trao đổi chéo [12].
Ngày nay, giải thuật di truyền được dùng phổ biến trong một số ngành như tin
sinh học, khoa học máy tính, trí tuệ nhân tạo, tài chính và một số ngành khác.
Giải thuật di truyền được lấy cảm hứng từ thuyết tiến hóa của giới tự nhiên do
nhà bác học Darwin xây dựng. Nguyên lý sinh học khởi nguồn của tư tưởng lập
trình tiến hóa như sau: Trong tất cả cá thể sống đều chứa các tế bào. Mỗi mội tế
bào đều chứa cùng tập hợp bộ nhiễm sắc thể giống nhau. Nhiễm sắc thể chứa
các chuỗi DNA. Các chuỗi DNA được nhóm lại thành các khối (block) hay còn


17

gọi là gen, mỗi một gen này là một Protein. Hay có thể nói mỗi một gen này
biểu diễn một đặc điểm của sinh vật, ví dụ như đặc điểm của màu mắt (nâu, đen,
xanh, vàng), đặc điểm của màu tóc (đen, bạch kim, nâu, vàng), kiểu tóc (thẳng,
xoăn…). Các Gen tương ứng là các Gen có cùng một đặc tính với giá trị khác
nhau, hoặc giống nhau. Ví dụ Gen quy định màu tóc vàng ở cá thể A tương ứng
với Gen quy định tóc đen ở cá thể B. Tập hợp toàn bộ các nguyên liệu di truyền
học (tất cả các nhiễm sắc thể) được gọi là bộ di truyền. Kiểu Gen là tập hợp con
các gen trong bộ các nguyên liệu di truyền. Kiểu gen này sẽ quy định đặc tính cơ
thể (thể xác) và tinh thần của cá thể sống như màu mắt, mức độ thông minh.
Sự sinh sản: Trong quá trình sinh sản sự tổ hợp (trao đổi chéo). Gen từ các cá
thể cha mẹ sẽ được chuyển cho thế hệ sau. Quá trình tạo mới cá thể con cháu có
thể là đột biến. Đột biến xảy ra khi các thành phần DNA có một chút thay đổi,
nguyên nhân chính của quá trình đột biến thường là lỗi trong quá trình sao chép
các Gen từ các cá thể cha-mẹ. Sự phù hợp của một cá thể (fitness) được đánh giá

truyền) hoặc mang những đặc tính mới hoàn toàn (đột biến). Di truyền và đột
biến là hai cơ chế quan trọng như nhau trong quá trình tiến hóa mặc dù xác suất
để xảy ra hiện tượng đột biến nhỏ nhiều so với hiện tượng di truyền” [1]. Mặc
dù cơ chế là ngẫu nhiên nhưng giải thuật di truyền không phải là một giải thuật
ngẫu nhiên. Giải thuật khai thác và tận dụng được một cách hiệu quả thông tin
quá khứ để có được những kết quả mới đạt kết quả như mong muốn. Các cải tiến
trong việc sử dụng giải thuật di truyền đã làm tăng thêm hiệu quả của việc sử
dụng giải thuật trong các bài toán phức tạp. Điều này thể hiện ở việc giảm thời
gian tính toán ngày càng hiệu quả mà ta sẽ tìm hiểu cụ thể hơn ở dưới đây.
1.2.1.1. Lịch sử phát triển
Năm 1954, GP bắt đầu với giải thuật tiến hóa, nó được sử dụng lần đầu tiên bởi
Nils Aall Barricelli trong việc mô phỏng quá trình tiến hóa.
Vào những năm 1960 và nửa đầu những năm 1970 giải thuật tiến hóa (EA) được
biết đến như là các phương pháp tối ưu hóa. I. Rechenberg và nhóm của ông ấy
đã giải quyết được nhiều vấn đề phức tạp trong ngành công nghệ bằng chiến
lược tiến hóa (Evolution strategies). Ông đã giới thiệu ý tưởng về lập trình tiến
hóa trong tác phẩm "Evolution strategies" (Evolutions strategie in original). Sau
đó các nhà nghiên cứu khác tiếp tục phát triển ý tưởng này của ông. Năm 1971
ông làm luận án tiến sỹ về evolution strategies và năm 1973 ông xuất bản thành
sách.
Trong những năm 1970 Jonh Holland có những ảnh hưởng rất lớn trong quá
trình phát triển của giải thuật di truyền. Giải thuật di truyền (GA) được Holland
phát minh và sau đó ông cùng các sinh viên và cộng sự của mình phát triển tiếp.
Các kết quả này được giới thiệu trong cuốn sách "Adaption in Natural and
Artificial Systems" xuất bản vào năm 1975 của ông.
Vào năm 1992, John Koza đã sử dụng giải thuật di truyền để thực hiện một vài
nhiệm vụ trong chương trình tiến hóa. Ông đã gọi phương pháp này là Lập trình
tiến hóa ("Genetic Programming" (GP)) [17].



Hay hàm lượng giá cho mỗi nhiễm sắc thể hay chính là cho các phương án
nghiệm trong tập nghiệm. Hàm này dùng để đánh giá độ thích nghi của các
nhiễm sắc thể. Hàm thích nghi cần phải đánh giá được mức độ thích nghi cho tất
cả các nghiệm khả thi và luôn được giả định là không âm để hiện độ thích nghi
của các cá thể. Công thức biểu diễn hàm cần phải thể hiện được tất cả các đặc
tính mong muốn của nhiễm sắc thể, thông qua đó có thể chọn lọc được các quần
thể nghiệm tốt nhất cho bài toán.


20

1.2.1.2.4. Quá trình lai ghép

Đây là quá trình nhiễm sắc thể mới được hình thành dựa trên nhiễm sắc thể chamẹ bằng cách lai ghép một hay nhiều đoạn nhiễm sắc thể cha mẹ với nhau. Lai
ghép có xét tới các đặc tính trội và lặn trong tự nhiên. Các đặc tính này được quy
định trước trong khi biểu diễn cấu trúc nhiễm sắc thể. Bằng việc xem xét tới các
đặc tính trội-lặn, quá trình sản sinh ra các "quần thể chất lượng tốt" sẽ nhanh
hơn và do đó thời gian tính toán cũng được rút ngắn. Phép lai ghép xảy ra với
xác suất là p1 có thể được mô phỏng như sau:
− Chọn hai (hay nhiều) cá thể bất kỳ trong quần thể. Quần thể ở đây bao
gồm các nhiễm sắc thể (cha-mẹ) có độ dài bằng nhau.
− Chọn điểm lai là một điểm có vị trí bất kỳ (như nhau) trên nhiễm sắc thể
cha-mẹ và thực hiện hoán đổi các đoạn gen của nhiễm sắc thể cha-mẹ tại
điểm lai này.
− Đưa hai cá thể này vào quần thể để thực hiện vào các quá trình tiến hóa

tiếp theo
Nhiễm sắc thể cha-mẹ:
0


0

1

1

Điểm lai ghép
1

0

1

0

0

1

0

Hai nhiễm sắc thể con được sinh ra sau quá trình lai ghép:
0

1

1

1


0

0

0

1

1

0

0

Hình 1.3: Lai ghép giữa hai cá thể
Trong quá trình tồn tại và phát triển, giải thuật di truyền đã được bổ sung rất
nhiều các phương pháp lai ghép để nhằm thích ứng với nhiều kiểu bài toán và
cũng là để tăng hiệu quả của giải thuật. Có thể kể một số phép lai cải tiến như
sau:
− Lai ghép từng phần: Việc giữ lại những đoạn mã đã "tối ưu" trong nhiễm
sắc thể cũng là một cách để quá trình lai ghép trở nên hiệu quả hơn.
− Lai ghép có trật tự
− Lai ghép dựa trên vị trí
− Lai ghép chu trình
− Lai ghép thứ tự tuyến tính


21

Lai ghép đa điểm: Với phương pháp này, chúng ta có thể cho 2 cá thể lai ghép ở


0

0

1

1

1

1

0

0

1

1

Điểm tạo đột biến
Nhiễm sắc thể sau đột biến:
0

1

1

0

quá trình lai ghép.
− Xác suất đột biến (pm): xác suất để mỗi bit trong nhiễm sắc thể bị đột biến
− Xác suất sinh ngẫu nhiên một số cá thể mới và truyền vào thế hệ kế tiếp.
Thông thường, kích cỡ của quần thể phụ thuộc vào độ phức tạp của bài toán. Bài
toán càng phức tạp, nhiều ràng buộc-đơn hoặc đa mục tiêu- thì số lượng cá thể
trong mỗi thế hệ càng phải lớn. Hai thông số xác suất trong quá trình di truyền
có khoảng giá trị rất khác nhau. Đối với xác suất lai tạo, giá trị thường là 0,25
[1], nhưng giá trị thông thường của xác suất đột biến thấp hơn nhiều, chỉ ở
khoảng 0,01-0,05. Điều này cũng phản ánh đúng xác suất xảy ra hai quá trình
trong thực tế.
1.2.1.4. Sơ đồ quá trình tính toán của giải thuật di truyền
Giải thuật di truyền được mô hình hóa theo các bước giống như lưu đồ trên hình
1.5.
Trong lưu đồ trên các bước được thực hiện lần lượt như sau:
Bước 1: Khởi tạo/lựa chọn các thông số cho quá trình tính toán: Bước này người
lập trình tính toán phải lựa chọn các thông số như: Số lượng cá thể trong quần
thể, cách thức hóa bài toán cần tính toán dưới dạng các nhiễm sắc thể (độ dài
của nhiễm sắc thể, kiểu số biểu diễn dữ liệu,…), số thế hệ tính toán, xác suất lai
ghép, xác suất đột biến, hàm thích nghi,…
Bước 2: Khởi tạo quần thể ban đầu: xác định bằng phương pháp tạo số ngẫu
nhiên để tạo giá trị cho các nhiễm sắc thể cho quần thể ban đầu. Tùy vào
cách biểu diễn của các nhiễm sắc thể mà ta chọn phương pháp tạo số ngẫu
nhiên thích nghi.
Bước 3: Đánh giá các nhiễm sắc thể bằng hàm thích nghi đã xác định ở bước 1.
Trong bước này, ngoài việc đánh giá các nhiễm sắc thể riêng rẽ, chúng ta còn có
thể đánh giá độ thích nghi của một nhiễm sắc thể hay cả quần thể. Nếu một
nhóm hay cả quần thể có độ thích nghi "trung bình" (theo tiêu chí của từng
trường hợp của người lập trình) thấp thì có thể loại nhóm nhiễm sắc thể hay
quần thể đó ra khỏi quá trình di truyền.
Bước 4: Thực hiện quá trình di truyền thông qua các cơ chế lai ghép và đột biến.

mãn

Thỏa mãn
Kết thúc - in (lưu) kết quả tính toán

Hình 1.5: Sơ đồ quá trình tính toán của giải thuật di truyền
Bước 5: Tạo quần thể mới bằng quá trình chọn lọc. Quá trình này cũng dựa
vào đánh giá các nhiễm sắc thể thông qua hàm thích nghi. Cá thể nào có độ
thích nghi cao sẽ được gữ lại cho thế hệ kế tiếp. Cũng giống như ở bước 3,
chúng ta có thể sử dụng những hàm thích nghi thích nghi để đánh giá từng
cá thể dơn lẻ hoạc cả một nhóm các cá thể. Sau quá trình này, nhóm cá thể
nào thỏa mã tiêu chuẩn đánh giá với mức độ từ cao xuống thấp sẽ được dưa
vào quần thể mới.


24

Bước 6: Đánh giá quần thể vừa có được trong bước 5. Thông thường có hai
tiêu chí để dừng quá trình di truyền tại bước này. Thứ nhất, độ thích nghi
của từng cá thể và cả quần thể thỏa mãn một điều kiện hội tụ đã được đặt ra
ban đầu. Các điều kiện hội tụ thể hiện mức độ chấp nhận được của kết quả
tìm được. Thứ hai, quần thể mới tạo thành là quần thể ở thế hệ thứ (N+1)
với N là số thế hệ dự định tính toán đã giả thiết ban đầu. Trong khi thực hiện
các quá trình di truyền, những người tính toán có thể đưa ra những tiêu chí
riêng để dừng quá trình di truyền. Các tiêu chí đưa ra góp phần quyết định
tới thành công của giải thuật.
Một số công thức tính toán trong giải thuật di truyền [1]:
Ký hiệu npop_size là số cá thể trong một quần thể; nếu bài toán có n biến độc
lập và mỗi biến được biểu diễn bởi mi(j) bit thì mỗi phương án cần
n


(1.2)

eval (vi )

i =1

− Tính vị trí xác suất qi cho mỗi cá thể vi (i= 1,2,…, npop_size)
i

qi = ∑ p j

(1.3)

j =1

− Tính vị trí đột biến: Phát (pm*nx*npop_size) lần số ngẫu nhiên r phân
bố đều trong khoảng [1, (nx*npop_size)]. Nếu r trùng với vị trí nào sẽ
tiến hành đột biến bit đó, có nghĩa là nếu giá trị của bit đó bằng 0 thì
chuyển thành 1 hoặc ngược lại.
Như vậy GA là một giải thuật lặp nhằm giải quyết các bài toán tìm kiếm, nó
khác với các giải thuật tối ưu thông thường ở những điểm cơ bản sau:


25

− Giải thuật di truyền làm việc với bộ mã của tập thông số chứ không làm
việc trực tiếp với giá trị của các thông số.
− Giải thuật di truyền tìm kiếm song song trên một quần thể chứ không tìm
kiếm từ một điểm, mặt khác nhờ áp dụng các toán tử di truyền, nó sẽ trao

của bài toán tối ưu;
BUij, BLij - giới hạn trên và giới hạn dưới của biến xij;
rand (0,1) - số ngẫu nhiên phân bố đều trong khoảng [0, 1].
Ngay sau quá trình tạo quần thể ban đầu, khác với GA, giải thuật DE thực hiện
luôn tiến trình đột biến (khối 3). Trong tiến trình này, DE tiếp tục tạo ra một
quần thể được đột biến [V] dựa trên quần thể ban đầu. Kỹ thuật đột biến trong