Tiểu luận môn Thuật Toán và Phương Pháp Giải Quyết Vấn Đề ỨNG DỤNG GIẢI THUẬT DI TRUYỀN XÂY DỰNG LỊCH PHÂN CÔNG LÀM VIỆC
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (701.75 KB, 46 trang )
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN THUẬT TOÁN VÀ
PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỂ
ỨNG DỤNG GIẢI THUẬT
DI TRUYỀN XÂY DỰNG LỊCH
PHÂN CÔNG LÀM VIỆC
Giảng viên phụ trách:
PGS.TS ĐỖ VĂN NHƠN
Học viên thực hiện:
LÊ PHÚ QUÍ - CH1301108
TP. Hồ Chí Minh, 10 - 2014
LỜI CÁM ƠN
Đầu tiên, em xin chân thành cám ơn thầy PGS.TS ĐỖ VĂN NHƠN – người đã
truyền đạt cho em những kiến thức quý báu trong môn Thuật toán và phương pháp
giải quyết vấn đề.
Tiếp theo, em xin gửi lời cám ơn đến các thầy cô ở các khoa cũng như tại các phòng
ban tại trường ĐH Công Nghệ Thông Tin đã tận tình giúp đỡ em trong thời gian
học vừa qua.
Do kiến thức có hạn cũng như kinh nghiệm nghiên cứu khoa học trên thực tế không
nhiều nên bài làm của em không tránh khỏi thiếu sót. Em rất mong nhận được sự
đóng góp quí báu của quí thầy cô.
TpHCM, ngày 11 tháng 10 năm 2014
Lớp Cao học KHMT khóa 8
Lê Phú Quí
HVTH: Lê Phú Quí
NHẬN XÉT CỦA GIẢNG VIÊN
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
……………………………………………………………………………………………….
HVTH: Lê Phú Quí
Mục lục
!"#$%&$'($)
*+%,$'($)
-./0$'"123"$'($)
45$'67"189:$
;$'<$"&=$"1/>$''?<@A"#$%&B
*C#$%&D1'EFB
**='?D1'EFB
*-GH@I8$''?"#$%&J
*4/>$''?<@A"#$%&
;$'<$"&='?IK@&$L
-='?IK@&$L
-*@A.M=$IK@&$%>$'?$
--N>%O8$='?IK@&$-
-4$PIK@&$
-13,$'"1Q8$DJ
-B!$'?@A
-JRKS$'='?IK@&$*T
-='?IK@&$Q"/>$'K@&$.$'*
C)$'I+$'M='?IK@&$*-
4./"13@*-
4*?$@"='?IK@&$*4
4-U1$QVWADXK8*4
44SQ.)$'I+$'7*4
CY$'I+$'='?IK@&$"1WADXH$Z$'D13"*
1$WADXH$Z$'D13"*
*@KE$[K1$' S"13ZE$$*
*Z?<@KE$D13"R A$1*
**ZE$$*B
-\I+$''?=IK@&$"1 1$WADXH$Z$'D13"*
-U!I:$<]$!*L
HVTH: Lê Phú Quí
-*$'!*L
--$P-T
-4A$D/0^37A3-T
41I_/>$'KE$-
4 A$Q.<$K$'-
4*2DXD13"$H$"($-*
4-13,$'-
44+!13%S A$-B
I$/>$'KE$-
BA$1$2@8$'34*
C;$'7A4-
BA<?%2%/04-
B*2$A4-
B-/$'K!$K$'/>$'D44
C1D37?44
HVTH: Lê Phú Quí
I. Giới thiệu
1.1. Phát biểu vấn đề nghiên cứu
Trong ngành khoa học máy tính, tìm kiếm lời giải tối ưu cho các bài toán là vấn
đề được các nhà khoa học máy tính đặc biệt rất quan tâm. Mục đích chính của các thuật
toán tìm kiếm lời giải là tìm ra lời giải tối ưu nhất cho bài toán trong thời gian nhỏ nhất.
Các thuật toán như tìm kiếm không có thông tin / vét cạn ( tìm kiếm trên danh sách, trên
cây hoặc đồ thị ) sử dụng phương pháp đơn giản nhất và trực quan nhất hoặc các thuật
toán tìm kiếm có thông tin sử dụng heurictics để áp dụng các tri thức về cấu trúc của
không gian tìm kiếm nhằm giảm thời gian cần thiết cho việc tìm kiếm được sử dụng
nhiều nhưng chỉ với không gian tìm kiếm nhỏ và không hiệu quả khi tìm kiếm trong
không gian tìm kiếm lớn. Tuy nhiên, trong thực tiễn có rất nhiều bài toán tối ưu với không
gian tìm kiếm rất lớn cần phải giải quyết. Vì vậy, việc đòi hỏi thuật giải chất lượng cao và
sử dụng kỹ thuật trí tuệ nhân tạo đặc biệt rất cần thiết khi giải quyết các bài toán có
không gian tìm kiếm lớn. Thuật giải di truyền (genetic algorithm) là một trong những kỹ
thuật tìm kiếm lời giải tối ưu đã đáp ứng được yêu cầu của nhiều bài toán và ứng dụng
1.2. Mục đích nghiên cứu
Nghiên cứu, tìm hiểu thuật giải di truyền và trên cơ sở đó tiếp cận để ứng dụng
giải thuật di truyền vào bài toán xếp lịch phân công làm việc.
1.3. Đối tượng và phạm vi nghiên cứu
Nghiên cứu các đặc điểm, đặc trưng của giải thuật di truyền, các thành phần cơ bản
của giải thuật di truyền như khởi động quần thể ban đầu, đánh giá độ thích nghi của cá
thể, các toán tử di truyền (chọn lọc, lai ghép, đột biến), điều kiện dừng.
Ứng dụng giải thuật di truyền vào bài toán xếp lịch phân công làm việc với
các ràng buộc và những yêu cầu cơ bản.
1.4. Ý nghĩa khoa học và thực tiễn
Trong lĩnh vực lập lịch (hay lập thời khóa biểu), giải thuật di truyền đã thu hút
được rất nhiều các nghiên cứu và đề xuất. Lý do cho xu hướng này có thể thấy là bài toán
lập lịch nhìn chung thuộc lớp các bài toán NP-khó (NP hard) và vì vậy, rất cần các giải
thuật xấp xỉ.
Về cơ bản, bài toán lập lịch được coi như là việc gán các mốc thời gian (time slots)
thực hiện cho các công việc (tasks) sao cho phù hợp với khả năng về tài nguyên
HVTH: Lê Phú Quí Trang
(resources). Tuy nhiên, sự đa dạng thể hiện ở các thể loại ràng buộc khác nhau và mỗi
một bài toán thực tế sẽ có những ràng buộc đặc trưng riêng.
II. Tổng quan về thuật toán và phương pháp giải quyết vấn đề
2.1. Vấn đề là gì?
• Là một câu hỏi cần phải được trả lời.
• Là thứ cần phải giải quyết hoặc đang trong quá trình giải quyết.
• Một vấn đề là mối liên quan giữa ý chí của con người và thực tế.
Có 2 loại vấn đề:
• Vấn đề có cấu trúc tốt: mục tiêu rõ ràng, thông tin đầy đủ, bài toán quen thuộc.
Ví dụ: mua sắm đầu tư nhỏ, tuyển dụng,…
• Vấn đề có cấu trúc kém: thông tin không rõ ràng, thiếu thông tin, bài toán mới
và/hoặc phức tạp.
Ví dụ: Chiến lược công ty, mở rộng thị trường,…
2.2. Thuật giải là gì?
Thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay
phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái
ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau
cùng như đã dự đoán.
Nói cách khác, thuật toán là một bộ các qui tắc hay qui trình cụ thể nhằm giải
quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập
hợp của các dữ kiện đưa vào.
Ví dụ: thuật toán để giải phương trình bậc nhất P(x): ax + b = c, (a, b, c là các số
thực), trong tập hợp các số thực có thể là một bộ các bước sau đây:
1. Nếu a = 0
• b = c thì P(x) có nghiệm bất kì
• b ≠ c thì P(c) vô nghiệm
HVTH: Lê Phú Quí Trang B
2. Nếu a ≠ 0
• P(x) có duy nhất một nghiệm x = (c - b)/a
Một thuật toán có các tính chất sau:
• Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực
hiện được là chính xác.
• Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh bạch; các câu
lệnh được sắp xếp theo thứ tự nhất định.
• Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính
vẫn phải cho kết quả như nhau.
• Tính phổ dụng: Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có
thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.
• Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán.
2.3. Xây dựng giải pháp cho vấn đề
Mô hình hóa vấn đề
• Các bước thực hiện: Vấn đề thực tế Vấn đề cần giải quyết mô hình hóa vấn
đề
Vấn đề thực tế và vấn đề cần giải quyết:
+ Khảo sát và thu thập dữ liệu, thông tin và tri thức (DIK).
+ Chọn lọc vấn đề và chuẩn hóa DIK.
+ Xác định cơ sở DIK cho vấn đề.
+ Xác định phạm vi gây giới hạn của vấn đề.
+ Thu thập mẫu vấn đề và phân lớp.
+ Mô tả giả thiết của vấn đề.
+ Mô tả mục tiêu hay kết luận của vấn đề.
+ Mô tả các điều kiện hay ràng buộc liên quan.
Xây dựng mô hình:
+ Mô hình cho DIK.
HVTH: Lê Phú Quí Trang J
+ Mô hình cho giả thiết.
+ Mô hình cho mục tiêu.
+ Mô hình cho các điều kiện và các ràng buộc.
Mô hình cho vấn đề tổng thể:
(1) Dạng frame.
(2) Dạng tổng quát.
(3) Các dạng lai.
Thiết kế thuật toán / thuật giải
• Chọn lựa phương pháp giải quyết vấn đề dựa trên những phương pháp đã biết.
• Hình thành ý tưởng thiết kế thuật toán.
• Mô tả cụ thể: tác vụ, chiến lược, …
• Biểu diễn thuật toán dạng mã giả.
Chứng minh tính đúng đắn
• Chứng minh lý thuyết (dựa trên toán học).
• Kiểm chứng bằng thực nghiệm
Phân tích thuật toán / thuật giải
• Sử dụng công cụ toán học.
Nghiên cứu cải thiện, nâng cao hiệu quả thuật giải
• Phương pháp “phân chia và kết hợp”.
• Phương pháp heuristic
• Phương pháp giải quyết vấn đề dựa trên (dùng) tri thức
2.4. Các phương pháp giải quyết vấn đề
Phương pháp trực tiếp:
• Áp dụng trực tiếp công thức hay định lý, algorithm.
• Chuyển đổi dạng bài toán.
Các phương pháp gián tiếp hoặc tìm kiếm lời giải thông dụng:
• Phương pháp thử sai.
• Phương pháp vét cạn.
• Phương pháp quay lui.
• Phương pháp đệ quy.
HVTH: Lê Phú Quí Trang
Các phương pháp heuristic:
• Vét cạn thông minh.
• Tham lam, và quy hoạch động.
• Thứ tự.
• Hướng đích.
• Hàm heuristic.
Phương pháp giải quyết vấn đề dùng tri thức (HCG)
• Suy luận cơ bản.
• Suy luận với heuristic.
• Suy luận với mẫu bài toán.
• Suy luận với bài toán mẫu.
III. Tổng quan về thuật giải di truyền
3.1. Thuật giải di truyền
Giải thuật di truyền (GA) là một trong những mô hình tính toán phổ biến và
thành công nhất trong lĩnh vực tính toán thông minh. Cùng với các kỹ thuật tính toán
thông minh khác như tính toán mờ (fuzzy computing), mạng Nơ-ron (neural networks),
hệ đa tác tử (multi- agent systems), trí tuệ bầy đàn (swarm intelligence), giải thuật di
truyền ngày càng phát triển, được áp dụng rộng rãi trong các lĩnh vực của cuộc sống.
Có thể nói, GA đã bước đầu được áp dụng thành công trong các trường hợp, mà việc
mô tả toán học cho bài toán gặp rất nhiều khó khăn. Ví dụ: các hệ thống phức hợp
(complex systems) với các hàm mục tiêu ẩn và các mối ràng buộc phức tạp, các bài
toán thiết kế với các hàm mục tiêu quá phức tạp không tuyến tính, hay các bài toán
lập kế hoạch/lập lịch với không gian tìm kiếm NP-khó (NP-hard).
Thuật giải di truyền (GA) là kỹ thuật chung giúp giải quyết vấn đề bài toán bằng
cách mô phỏng sự tiến hóa của con người hay của sinh vật nói chung (dựa trên thuyết tiến
hóa muôn loài của Darwin) trong điều kiện qui định sẵn của môi trường. GA là một thuật
HVTH: Lê Phú Quí Trang L
giải, nghĩa là mục tiêu của GA không nhằm đưa ra lời giải chính xác tối ưu mà là đưa ra
lời giải tương đối tối ưu.
Các nguyên lý cơ bản của Thuật giải di truyền được tác giả J.H.Holland công bố
lần đầu tiên vào năm 1962. Sau đó, các nền tảng toán học của giải thuật lần đầu tiên được
công bố vào năm 1975 trong cuốn sách “Adaptation in Natural and Artificial System”
cũng của tác giả J.H.Holland. Có thể nói Holland là người đi tiên phong nghiên cứu trong
lĩnh vực Thuật giải di truyền cùng với những tác giả Goldbeg, Beglay…
Thuật giải di truyền là một giải thuật dựa trên cơ chế của chọn lọc tiến hoá trong tự
nhiên: “Trong mọi thế hệ, một tập mới các sinh vật được tạo ra bằng cách lai ghép những
nhân tố thích nghi nhất với môi trường của những sinh vật trong thế hệ cũ cùng với sự
xuất hiện đột biến ngẫu nhiên của các cá thể trong thế hệ mới”. Vận dụng cơ chế đó,
Thuật giải di truyền được bắt đầu với một quần thể ngẫu nhiên có n chuỗi , rồi sao chép
các chuỗi theo khuynh hướng đến cái tốt, ghép cặp và đổi các chuỗi con thành phần, thỉnh
thoảng làm đột biến giá trị bit để có số đo tốt.
Thuật giải di truyền cung cấp một cách tiếp cận cho việc học dựa vào mô phỏng sự
tiến hóa. Các giả thuyết thường được mô tả bằng các chuỗi bit, việc hiểu các chuỗi bit này
tùy thuộc vào ứng dụng, ý tưởng các giả thuyết cũng có thể được mô tả bằng các biểu
thức kí hiệu hoặc ngay cả các chương trình máy tính. Tìm kiếm giả thuyết thích hợp bắt
đầu với một quần thể, hay một tập hợp có chọn lọc ban đầu của các giả thuyết. Các cá thể
của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép
và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa sinh học. Ở mỗi bước,
các giả thuyết trong quần thể hiện tại được ước lượng liên hệ với đại lượng thích nghi
được cho, với các giả thuyết phù hợp nhất được chọn theo xác suất là các hạt giống cho
việc sản sinh thế hệ kế tiếp. Thuật giải di truyền đã được ứng dụng một cách thành công
cho những tác vụ học khác nhau và cho các vấn đề tối ưu hóa khác. Ví dụ, chúng đã được
dùng để học tập luật điều khiển robot và để tối ưu hóa các thông số học cho mạng nơron
nhân tạo.
Thuật giải di truyền cung cấp một phương pháp học được thúc đẩy bởi sự tương tự với
sự tiến hóa sinh học. Thay vì tìm kiếm các giả thuyết từ tổng quát đến cụ thể hoặc từ đơn
HVTH: Lê Phú Quí Trang T
giản đến phức tạp, GAs tạo ra các giả thuyết kế tiếp bằng cách lặp việc đột biến và việc
tái hợp các phần của giả thuyết được biết hiện tại là tốt nhất ở mỗi bước, một tập các giả
thuyết được gọi là quần thể hiện tại được cập nhật bằng cách thay thế vài phần nhỏ quần
thể bởi cá thể con của các giả thuyết tốt nhất ở thời điểm hiện tại. Sự phổ biến của GAs
được thúc đẩy bởi các yếu tố sau:
Tiến hóa là một phương pháp mạnh, thành công cho sự thích nghi bên trong các hệ
thống sinh học.
GA có thể tìm kiếm trên các không gian giả thuyết có các phần tương tác phức tạp,
ở đó ảnh hưởng của mỗi phần lên toàn thể độ thích nghi giả thuyết khó có thể mô
hình.
Thuật giải GA có thể được thực hiện song song và có thể tận dụng thành tựu của
phần cứng máy tính mạnh.
3.2. Các yếu tố của thuật toán di truyền đơn giản
Representation (sự biểu diễn): trong thuật giải di truyền (GA), giải pháp tiềm
ẩn được mã hóa thành chuỗi các ký tự từ bảng chữ cái, A=a
1
a
2
a
L
. Thường thì nó là
các ký tự nhị phân tuy nhiên cũng có thể là các ký tự mở rộng của bảng chữ cái, thỉnh
thoảng sử dụng đọc số.
Thuật toán di truyền sử dụng ngôn ngữ riêng để mô tả, chuỗi A được gọi là
nhiễm sắc thể, những thành phần của chuỗi như a
1
, a
2
, được gọi là gen, giá trị mà
gen nhận được gọi là thuộc tính gen, trong hầu hết các chuỗi nhị phân phổ biến là 0
hoặc 1, ví dụ như trong nhiễm sắc thể A= 11110000 thì 4 gen đầu có thuộc tính 1 còn
4 gen sau có thuộc tính 0.
Fitness Function (hàm mục tiêu): Fitness Function có nhiệm vụ tìm ra chuỗi
tối ưu. Tính chất tốt của chuỗi được đặc trưng trong GA ở chức năng của nó, các tính
chất này được gọi là chức năng mục tiêu (objective function) và số lượng sẽ được tối
ưu hóa. Một chức năng cần thiết được dùng gọi là chức năng thích hợp (Fitness
Function). Trong GA, Fitness Function là 1 chức năng chính đơn lẻ của objective
function, nó có nhiệm vụ quyết định chuỗi nào được dùng để nhân lên hoặc chuỗi nào
là không cần thiết và sẽ bị loại bỏ. Fitness Function thường xuyên được xác định để
tăng chuỗi thích hợp từ đó có những kết quả tương ứng phù hợp hơn. Kiểu di truyền
HVTH: Lê Phú Quí Trang
(genotype) là sự biểu diễn lại chuỗi, kết quả tạo ra gọi là phenotype. Thường thì trong
thuật giải di truyền,
có sự khác nhau lớn giữa một sinh vật sinh học (phenotype) và DNA
(kiểu di truyền) của nó. Objective function là một loại của phenotype, trong GA,
Objective function và fitness function thường được thay thế cho nhau, fitness được tăng
phụ thuộc vào quá trình chọn lọc.
Population
Dquainter (sự biến động quần thể): Thuật giải di truyền cung cấp một
phương pháp học được thúc đẩy bởi sự tương tự với sự tiến hóa sinh học. Thay vì tìm
kiếm các giả thuyết từ tổng quát đến cụ thể hoặc từ đơn giản đến phức tạp, GA tạo ra các
giả thuyết kế tiếp bằng cách lặp việc đột biến và việc tái hợp các phần của giả thuyết được
biết hiện tại là tốt nhất. Ở mỗi bước, một tập các giả thuyết được gọi là quần thể hiện tại
được cập nhật bằng cách thay thế vài phần nhỏ quần thể bởi cá thể con của các giả thuyết
tốt nhất ở thời điểm hiện tại. Có nhiều cách thực hiện một giải thuật di truyền học, ở đây
chúng ta xét giải thuật di truyền học đơn giản với một quần thể có kích thước N với 3 hoạt
động chính của thuật giải:
Quá trình chọn lọc: quá trình này chọn ra một giả thuyết (cá thể) được cho là
tốt nhất trong số các lời giải (quần thể), quá trình này không sinh ra bất kỳ cá thể mới
nào, quá trình này lặp lại nhiều lần sẽ chọn ra được ngày càng nhiều những cá thể phù
hợp và làm giảm đi những cá thể không cần thiết.
Quá trình lai ghép: quá trình này sinh ra hai hay nhiều hơn cá thể mới từ một cặp
cá thể trước đó (gọi là cha mẹ) bằng việc kết hợp một phần chuỗi của cha mẹ.
Quá trình đột biến: quá trình này đơn giản thay đổi những đặc tính trong chuỗi con
một cách ngẫu nhiên. Mỗi đặc tính được thay đổi với một xác suất nhỏ.
HVTH: Lê Phú Quí Trang *
3.3. Sơ đồ thực hiện Thuật giải di truyền
Hình 1 – Sơ đồ thực hiện Thuật giải di truyền
Đây là sơ đồ chung nhất áp dụng cho rất nhiều lớp bài toán sử dụng Thuật giải di
truyền. Một số khái niệm có thể rất mới mẻ đối với người bắt đầu tìm hiểu về Thuật giải
di truyền.
Thuật toán cụ thể cho bài toán
GA (Fitness, Fitness_threshold, p, r, m)
HVTH: Lê Phú Quí Trang -
{
// Fitness: hàm gán thang điểm ước lượng cho một giả thuyết.
// Fitness_threshold: Ngưỡng xác định tiêu chuẩn dừng giải thuật tìm kiếm.
// p: Số cá thể trong quần thể giả thuyết.
// r: Phân số cá thể trong quần thể được áp dụng toán tử lai ghép ở mỗi bước.
// m: Tỉ lệ cá thể bị đột biến.
• Khởi tạo quần thể: P ← Tạo ngẫu nhiên p cá thể giả thuyết
• Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)
• while [max Fitness(h)] < Fitness_threshold do
Tạo thế hệ mới, P
S
• Chọn cá thể: chọn theo xác suất (1 – r)p cá thể trong quần thể P thêm vào
P
S
. Xác suất Pr(h
i
) của giả thuyết h
i
thuộc P được tính bởi công thức:
• Lai ghép: chọn lọc theo xác suất cặp giả thuyết từ quần thể P,
theo Pr(h
i
) đã tính ở bước trên. Ứng với mỗi cặp <h
1
, h
2
>, tạo ra hai con bằng cách
áp dụng toán tử lai ghép. Thêm tất các các con vào P
S
.
• Đột biến: Chọn m% cá thể của P
S
với xác suất cho mỗi cá thể là như nhau.
Ứng với mỗi cá thể biến đổi một bit được chọn ngẫu nhiên trong cách thể hiện của
nó.
• Cập nhật: P ← P
S
.
• Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)
• Trả về giả thuyết trong P có độ thích nghi cao nhất.
}
HVTH: Lê Phú Quí Trang 4
3.4. Các toán tử di truyền
Những thế hệ sau trong GAs được quyết định bởi tập các toán tử tái hợp và đột
biến các cá thể được chọn từ quần thể hiện tại. Các toán tử GAs tiêu biểu để thực hiện các
giả thiết chuỗi bit được mô tả trong bảng 2. Các toán tử này tương ứng với các phiên bản
được ý tưởng hóa của các hoạt động di truyền trong tiến hóa sinh học. Hai toán tử phổ
biến nhất là lai ghép và đột biến.
Toán tử lai ghép tạo ra hai con từ hai chuỗi cha bằng cách sao chép các bit được
chọn lựa từ mỗi cha. Bit ở vị trí i trong mỗi con được sao chép từ bit ở vị trí i của một
trong hai cha. Chọn lựa cha nào phân phối bit cho vị trí i được quyết định bởi thêm vào
một chuỗi mặt nạ lai ghép. Để minh họa, xem xét toán tử lai ghép điểm đơn (single-point)
ở đầu bảng 2. Xem xét hai con trên nhất trong trường hợp này. Con này lấy năm bit đầu
tiên của nó từ cha thứ nhất và sáu bit còn lại từ cha thứ hai, bởi mặt nạ lai ghép là
11111000000 xác định các lựa chọn này cho mỗi vị trí bit. Con thứ hai dùng cùng mặt nạ
lai ghép, nhưng đổi vai trò của hai cha. Do đó, nó chứa các bit không được dùng bởi con
đầu tiên. Trong lai ghép điểm đơn, mặt nạ lai ghép luôn luôn được xây dựng sao cho nó
bắt đầu với chuỗi chứa n giá trị 1 liên tục, được theo sau một số giá trị 0 cần thiết để hoàn
chỉnh chuỗi. Cách này tạo ra cá thể con có n bit đầu được phân phối bởi một cha và các
bit còn lại bởi cha thứ hai. Mỗi lần toán tử lai ghép điểm đơn được áp dụng, điểm lai ghép
n được chọn ngẫu nhiên, rồi mặt nạ lai ghép được tạo và áp dụng.
HVTH: Lê Phú Quí Trang
Bảng 2. Các toán tử chung cho thuật giải di truyền
Trong lai ghép hai điểm, cá thể con được tạo ra bởi thay thế các đoạn trung gian
của một cá thể cha vào giữa của chuỗi cha thứ hai. Nói một cách khác, mặt nạ lai ghép là
một chuỗi bắt đầu với n
0
trị 0, được theo sau bởi chuỗi liên tục n
1
trị 1, được theo sau bởi
một số trị 0 cần thiết để hoàn chỉnh chuỗi. Mỗi lần toán tử lai ghép hai điểm được áp
dụng, một mặt nạ được tạo ra bằng cách chọn ngẫu nhiên các số nguyên n
0
và n
1
. Thí dụ,
trong ví dụ được chỉ ra ở bảng 2. cá thể con được tạo ra dùng một mặt nạ với n
0
= 2 và n
1
= 5. Như lai ghép trước, hai cá thể con được tạo ra bằng cách hoán đổi vai trò của hai cá
thể cha.
Lai ghép đồng nhất kết hợp các bit được lấy mẫu đồng nhất từ hai cá thể cha, như
được minh họa trong trong bảng 2. Trong trường hợp này, mặt nạ lai ghép được tạo ra
HVTH: Lê Phú Quí Trang B
11101001000
00001010101
11101010101
00001001000
11111000000
11101001000
00001010101
11001011000
00101000101
00111110000
11101001000
00001010101
10001000100
01101011001
00111110000
11101001000 11101011000
Các chuỗi ban đầu Mặt nạ lai ghép Các cá thể con
Lai ghép điểm đơn:
Lai ghép điểm kép:
Lai ghép đồng nhất:
Đột biến điểm:
như là một chuỗi bit ngẫu nhiên với mỗi bit được chọn ngẫu nhiên và độc lập với các bit
khác.
Thêm vào các toán tử tái kết hợp - tạo ra cá thể con bằng cách kết hợp các phần
của hai cá thể cha, một loại toán tử thứ hai tạo ra cá thể con từ một cá thể cha. Cụ thể là
toán tử đột biến tạo ra những thay đổi ngẫu nhiên nhỏ cho chuỗi bit bằng cách chọn một
bit ở vị trí ngẫu nhiên, rồi thay đổi giá trị của nó.
Một vài hệ thống GAs mượn thêm một vài toán tử, các toán tử đặc biệt được
chuyên biệt hóa cho biểu diễn giả thuyết cụ thể được sử dụng bởi hệ thống.Ví dụ,
Grefenstette et al. (1991) mô tả hệ thống học tập luật điều khiển robot. Nó sử dụng đột
biến và lai ghép cùng với một toán tử để chuyên biệt hóa các luật.
3.5. Hàm thích nghi và sự chọn lọc
Hàm thích nghi định nghĩa tiêu chuẩn để xếp hạng các giả thuyết tiềm ẩn và để
chọn lọc chúng theo xác suất để đưa vào quần thể thế hệ kế tiếp. Nếu tác vụ là học các
luật phân loại, thì hàm thích nghi thông thường có một thành phần cho điểm độ chính xác
phân loại của luật trên tập mẫu huấn luyện được cho. Thường các tiêu chuẩn khác có thể
được bao hàm, chẳng hạn như độ phức tạp và mức độ tổng quát của luật. Một cách tổng
quát hơn, khi giả thuyết chuỗi bit được hiểu như là một thủ tục phức tạp (ví dụ, khi chuỗi
bit thể hiện tập chọn lọc, các luật if-then sẽ được móc xích với nhau, để điều khiển thiết bị
robot), hàm thích nghi có thể đo hiệu suất tổng của thủ tục kết quả hơn là hiệu suất của
các luật riêng biệt.
Trong thuật giải GA, xác suất để một giả thuyết được chọn được cho bởi tỉ số của
độ thích nghi của nó với độ thích nghi của các thành viên khác của quần thể hiện tại.
Phương pháp này thỉnh thoảng thường được gọi là sự chọn lọc tỉ lệ độ thích nghi, hoặc sự
chọn lọc vòng roulette. Các phương pháp khác dùng độ thích nghi để chọn lọc các giả
thuyết cũng sẽ được đề xuất. Ví dụ, sự chọn lọc kiểu vòng thi đấu, hai giả thuyết đầu tiên
được chọn ngẫu nhiên từ quần thể hiện tại. Với một vài xác suất p được định nghĩa trước
HVTH: Lê Phú Quí Trang J
hai cá thể này cáng phù hợp càng được chọn và với xác suất (1 – p) giả thuyết càng ít phù
hợp càng được chọn. Sự chọn lọc theo vòng thi đấu thường tạo ra quần thể khác nhau
nhiều hơn so với sự chọn lọc tỉ lệ với độ thích nghi (Goldberg và Deb 1991). Trong
phương pháp sự chọn lọc theo hạng, các giả thuyết trong quần thể hiện tại đầu tiên sẽ
được sắp xếp theo độ thích nghi. Xác suất để giả thuyết sẽ được chọn tỉ lệ với hạng của nó
trong danh sách đã sắp xếp hơn là độ thích nghi của nó.
3.6. Thể hiện các giả thuyết
Các giả thuyết trong GAs thường được thể hiện dưới dạng chuỗi các bit, để chúng có
thể dễ dàng được thực hiện bởi các toán tử di truyền: đột biến và lai ghép. Các giả thuyết
được thể hiện bởi chuỗi bit này có thể khá phức tạp. Ví dụ, tập các luật if-then có thể dễ
dàng được thể hiện theo cách này, bằng cách chọn một cách thức mã hóa các luật để phân
bố các chuỗi con riêng cho mỗi điều kiện trước và điều kiện sau của luật. Các ví dụ về sự
thể hiện các luật này trong các hệ thống GAs được mô tả bởi Hooland (1986);
Grefenstette (1988); và DeJong et al. (1993).
Để thấy các luật if-then có thể được mã hóa bằng các chuỗi bit như thế nào, trước
tiên hãy xem chúng ta có thể sử dụng chuỗi bit như thế nào để mô tả ràng buộc trên giá trị
của thuộc tính đơn. Để lấy một ví dụ, hãy xem xét thuộc tính Outlook, thuộc tính này có
thể lấy bất kì giá trị nào trong ba giá trị: Sunny, Overcast hoặc Rain. Một cách rõ ràng để
thể hiện ràng buộc cho Outlook là dùng một chuỗi bit có chiều dài 3, mỗi vị trí bit tương
ứng với một trong ba giá trị có thể của nó. Đặt giá trị 1 ở một vài vị trí để chỉ ra rằng
thuộc tính được phép lấy giá trị tương ứng. Ví dụ, chuỗi 010 thể hiện ràng buộc Outlook
phải lấy giá trị thứ hai trong các giá trị này, hay là Outlook = Overcast. Một cách tương
tự, chuỗi 011 thể hiện ràng buộc tổng quát hơn là cho phép hai giá trị có thể, hay là
Outlook = Overcast ∨ Rain. Chú ý 111 thể hiện ràng buộc có thể tổng quát nhất, chỉ ra
rằng chúng ta không quan tâm giá trị nào trong các giá trị có thể của nó mà thuộc tính giữ.
HVTH: Lê Phú Quí Trang
Đưa ra phương pháp này để thể hiện các ràng buộc trên thuộc tính đơn, các liên kết
của các ràng buộc trên nhiều thuộc tính có thể dễ dàng được thể hiện bằng cách nối các
chuỗi bit tương ứng. Ví dụ, xem xét thuộc tính thứ hai, Wind, có thể lấy giá trị Strong
hoặc Weak. Điều kiện trước của luật chẳng hạn như,
(Outlook = Overcast ∨ Rain) ∧ (Wind = Strong)
có thể được thể hiện bởi chuỗi bit có chiều dàl là 5 sau:
Outlook Wind
011 10
Các điều kiện sau của luật (chẳng hạn như PlayTenis = yes) có thể được thể hiện
theo kiểu tương tự. Vì vậy, toàn bộ luật có thể được mô tả bởi móc nối các chuỗi bit mô tả
các điều kiện đầu, cùng với chuỗi bit mô tả điều kiện sau của luật. Ví dụ, luật
IF Wind = Strong THEN PlayTennis = yes
sẽ được thể hiện bởi chuỗi
Outlook Wind PlayTennis
111 10 10
ở đây 3 bit đầu tiên mô tả ràng buộc “không quan tâm” trên Outlook , hai bit kế tiếp mô tả
ràng buộc trên Wind, và hai bit cuối cùng mô tả điều kiện sau của luật (ở đây chúng ta giả
sử PlayTennis có thể lấy giá trị Yes hoặc No). Chú ý chuỗi bit thể hiện luật chứa một
chuỗi con cho mỗi thuộc tính trong không gian giả thuyết, thậm chí thuộc tính không bị
ràng buộc bởi các điều kiện trước. Điều này tạo ra một chuỗi bit có chiều dài cố định để
thể hiện các luật, trong đó các chuỗi con ở các vị trí cụ thể mô tả các ràng buộc trên các
thuộc tính cụ thể. Đưa ra cách thể hiện này cho các luật đơn, chúng ta có thể thể hiện tập
các luật bằng cách móc nối các thể hiện chuỗi bit của các luật riêng biệt.
HVTH: Lê Phú Quí Trang L
Trong thiết kế mã hóa chuỗi bit cho một vài không gian giả thuyết, thật là hữu ích để
sắp xếp cho mọi chuỗi bit tuân thủ theo cú pháp để thể hiện một giả thuyết được định
nghĩa tốt. Để mô tả, chú ý cách mã hóa luật ở đoạn trên, chuỗi bit 111 10 11 thể hiện luật
có điều kiện trước không ràng buộc thuộc tính mục tiêu PlayTennis. Nếu chúng ta tránh
xem xét giả thuyết này, chúng ta có thể mượn một cách mã hóa khác (ví dụ phân bố chỉ
một bit cho điều kiện sau để chỉ định giá trị là Yes hoặc No), thay đổi các toán tử di
truyền để tránh một cách tường minh việc xây dựng các chuỗi bit như thế, hoặc đơn giản
gán một độ thích nghi rất thấp cho các chuỗi bit như vậy.
3.7. Mở rộng thuật giải di truyền
Có nhiều cách để thực thi thuật giải tùy theo bài toán cụ thể, tuy nhiên cách tìm kiếm
thì hiếm khi sử dụng hình thức đơn giản như mô tả trên. Dưới đây là một số mở rộng cho
thuật toán:
Phương pháp chọn loại trừ: hầu hết các phương pháp chọn loại trừ đều được thiết lập
lại để tránh sự hội tụ yếu. Chẳng hạn như:
• Cá thể tốt nhất được giữ lại để đưa vào quá trình tiến hóa cho bước tiếp theo, cá
thể này được dùng làm mẫu để chọn các cá thể khác trong quần thể nhằm duy trì
tính đa dạng.
• Hai cá thể trong quần thể được chọn ngẫu nhiên, đoạn nào xấu thì được loại bỏ và
thay thế bằng đoạn khác tốt hơn.
• Các cá thể trong quần thể hầu như không thay đổi trạng thái mà chỉ có một vài cá
thể có sự thay đổi trong mỗi bước.
• Để duy trì được tính đa dạng trong quần thể thì Fitness của mỗi cá thể được chia
sẻ lẫn nhau giữa các cá thể có cùng kiểu di truyền. Vì thế những cá thể khác nhiều
so với các cá thể còn lại sẽ được tăng cường Fitness trong khi các cá thể tương tự
nhau trong quẩn thể sẽ bị giảm Fitness.
HVTH: Lê Phú Quí Trang *T
• Thao tác lai ghép thay thế: việc cắt một phần giả thuyết và đem ghép lại với nhau
không phải là cách tốt để tạo ra cá thể mới. ví dụ bài toán người du lịch, trong
trường hợp này lời giải tiềm ẩn là sự hoán vị, ví dụ kết quả là 362154, thì có nghĩa
là đi tới thành phố 3 trước rồi tới thành phố 6, kế đến là 2, nếu áp dụng lai ghép
điểm đơn giữa 2 danh sách thì sẽ không đưa ra được một hành trình hợp lệ.
• Sử dụng toàn bộ quần thể: trong hầu hết các giải thuật di truyền thì đáp án cho bài
toán chính là một cá thể tốt nhất trong quần thể còn những cá thể khác được sử
dụng nhằm giúp cho quá trình tìm kiếm nhưng bị loại bỏ khi kết thúc thuật toán.
Điều này không hoàn toàn tốt. Trong thuật toán đầu tiên được đưa ra bởi Holland
thì mỗi cá thể của quần thể là một lớp – một luật IF-THEN, quần thể là một hệ
thống các lớp, trong quá trình chọn thì mỗi cá thể là một giả thuyết hoàn hảo. Một
tiến trình khác mà cũng sử dụng toàn bộ quần thể đó là tiến trình do Yao và Liu đề
xuất sử dụng chuỗi hạt mạng Neural. Nó được sử dụng khi tồn tại một số lớp mà
để giải quyết cùng một bài toán. Một lớp phổ biến được cho rằng tốt hơn cho tiến
trình so với các lớp khác. Yao và Liu đề xuất sử dụng 4 phương pháp khác nhau
để kết hợp kết quả của mạng Neural. Họ sử dụng sự chia sẻ Fitness tuyệt đối để
kích thích quá trình học với các mẫu khác nhau.
Phần tiếp theo sau đây sẽ phân tích cách hoạt động của giải thuật, so sánh và giải
thích tại sao nó tốt hơn so với các phương pháp truyền thống.
3.8. Thuật giải di truyền so với các phương pháp truyền thống
Chúng ta xét bài toán đơn giản sau đây: tối ưu hoá hàm y = f(x) trên khoảng
xácđịnh D.
Khi dùng phương pháp truyền thống có một số cách giải sau đây:
• Phương pháp liệt kê: Duyệt tất cả các điểm nằm trong vùng khảo sát D để tìm ra
điểm cực trị của nó. Phương pháp này không thích hợp khi dữ liệu đầu vào quá
lớn. Trong trường hợp này miền D có không gian quá lớn để có thể đếm được.
HVTH: Lê Phú Quí Trang *
• Phương pháp giải tích: Tìm điểm cực trị bằng cách giải tập các phương trình khi
cho Gradient bằng 0. Để xét được Gradient phải tính đạo hàm của hàm số. Điều
này không giải quyết được trong trường hợp hàm số không liên tục hoặc không có
đạo hàm. Ngoài ra đối với hàm nhiều cực trị thì có thể phương pháp này bỏ mất
cực trị, cực trị tìm được chỉ mang tính chất địa phương.
• Phương pháp tìm kiếm ngẫu nhiên: là phương pháp kết hợp giữa phương pháp
tính toán giải tích và sơ đồ liệt kê. Tuy nhiên những việc làm ngẫu nhiên cùng với
giải thuật tìm kiếm ngẫu nhiên cũng phải bị suy yếu bởi thiếu tính hiệu quả.
Đối với Thuật giải di truyền, các thông số của bài toán tìm kiếm phải được mã hoá
thành một chuỗi hữu hạn các ký tự trên một tập hữu hạn các ký tự. Chuỗi này tương tự
như các chuỗi gen của các cơ thể sinh vật. Có rất nhiều cách để mã hóa tập thông số. Một
cách đơn giản là chúng ta có thể mã hoá thành các chuỗi bit trên tập ký tự {0,1}. Mỗi một
chuỗi đại diện cho một điểm tìm kiếm trong không gian. GA xuất phát với một quần thể
các chuỗi được khởi tạo một cách ngẫu nhiên sau đó sẽ sản sinh các quần thể tiếp theo
thông qua việc sử dụng lựa chọn ngẫu nhiên như một công cụ. Nhờ đó Thuật giải di
truyền tìm kiếm trên nhiều điểm song song có khả năng leo lên nhiều cực trị cùng một
lúc. Thông qua các toán tử của mình, giải thuật trao đổi thông tin giữa các cực trị với
nhau, từ đó làm giảm thiểu khả năng giải thuật kết thúc tại các cực trị địa phương và bỏ
qua mất cực trị toàn cục
Đây là các đặc trưng của Thuật giải di truyền so với các phương pháp truyền
thống:
• Các Thuật giải di truyền làm việc với sự mã hoá của tập thông số chứ không làm
việc với các giá trị của các thông số.
• Các Thuật giải di truyền tìm kiếm từ một quần thể các điểm chứ không phải từ
một điểm.
• Các Thuật giải di truyền chỉ sử dụng thông tin về các tiêu chuẩn tối ưu của hàm
mục tiêu chứ không dùng các thông tin hỗ trợ nào khác.
HVTH: Lê Phú Quí Trang **
• Các Thuật giải di truyền sử dụng các luật chuyển đổi mang tính xác suất chứ
không phải là các luật chuyển đổi mang tính xác định.
• Các Thuật giải di truyền thường dễ cài đặt, áp dụng. Tuy nhiên không phải lúc nào
cũng cho lời giải chính xác. Một số Thuật giải di truyền có thể cung cấp lời giải
tiềm năng cho một bài toán xác định để người sử dụng lựa chọn.
IV. Các ứng dụng của Thuật giải di truyền
Ban đầu Thuật giải di truyền ra đời được áp dụng cho tối ưu hoá và học máy là chủ
yếu. Đến nay nó đã phát triển mạnh và có nhiều ứng dụng thực tế, đặc biệt là các bài toán
về trí tuệ nhân tạo. Ví dụ: ta có thể tối ưu công việc dự báo thời tiết sao cho chính xác
nhất dựa trên các thông số khí tượng do được. Năm 1967 Beglay xây dựng máy chơi cờ
Hexapawn dựa trên Thuật giải di truyền và nhận ra rằng Thuật giải di truyền có thể thực
hiện tốt mà không phụ thuộc độ phức tạp của trò chơi.
4.1. Tối ưu hoá và máy học
Trong lĩnh vực tối ưu hóa có nhiều bài toán được áp dụng Thuật giải di truyền và
đã thành công như tối ưu hoá hàm một biến, tối ưu hóa hàm nhiều biến, hay như bài toán
người du lịch, bài toán hộp đen, các bài toán kinh doanh, nhận dạng điều khiển hệ thống
. Sau đây sẽ giới thiệu một số bài toán tối ưu hóa:
David E.Golderg đã ứng dụng GA để tối ưu hóa bài toán điều khiển hệ thống
đường ống dẫn khí thiên nhiên. Trong bài toán này, mục tiêu là cực tiểu hóa năng lượng
do quá trình nén, phụ thuộc vào áp suất tối đa và áp suất tối thiểu và các ràng buộc tỉ lệ áp
suất.
Tối ưu hoá kết cấu: Mục tiêu của bài toán này là cực tiểu hóa trọng lượng của kết
cấu, phụ thuộc vào các ràng buộc về ứng suất lớn nhất và ứng suất nhỏ nhất của mỗi
thanh. Một bộ mã cho khung kết cấu theo ma trận tiêu chuẩn được dùng để phân tích mỗi
thiết kế tạo ra bởi Thuật giải di truyền.
Trong lĩnh vực máy học, Thuật giải di truyền được sử dụng cho việc tìm hiểu các
quy luật có cấu trúc như cấu trúc IF-THEN trong môi trường nhân tạo.
HVTH: Lê Phú Quí Trang *-
4.2. Ghi ảnh y học với Thuật giải di truyền
Thuật giải di truyền đơn giản đã được sử dụng để thực hiện ghi hình ảnh, như là bộ
phận của hệ thống lớn có tên là Digital Subtraction Angiography (DSA). Trong DSA, bác
sĩ sẽ cố gắng xem xét bên trong của một động mạch khả nghi bằng cách so sánh hình ảnh
x-quang, một được chụp trước khi tiêm thuốc đã nhuộm màu vào động mạch, một và một
được chụp sau khi tiêm thuốc. Cả hai hình được số hóa và được trừ nhau theo từng điểm
một, với kết quả mong muốn cuối cùng nhận được một hình ảnh sai khác phác họa rõ
ràng hình ảnh bên trong động mạch chủ. Tuy nhiên sự chuyển động nhẹ của bệnh nhân có
thể tạo ra hai hình ảnh kế nhau, làm rối loạn phần hình ảnh sai khác. Kết quả là, các hình
ảnh phải được xếp kế nhau, để tính toán phần hình ảnh sai khác.
Thuật giải di truyền được dùng để tìm kiếm các hệ số biến đổi để tìm kiếm các hệ
số giúp cực tiểu hóa sự sai biệt hình ảnh trước và sau khi tiêm, trên cơ sở các sai khác
hình ảnh tuyệt đối.
4.3. Bài toán sắp xếp lịch trực
Trong lĩnh vực lập lịch (hay lập thời khóa biểu), giải thuật di truyền đã thu hút
được rất nhiều các nghiên cứu và đề xuất. Lý do cho xu hướng này có thể thấy là bài
toán lập lịch nhìn chung thuộc lớp các bài toán NP-khó (NP hard) và vì vậy, rất cần
các giải thuật xấp xỉ. Tính đến nay có rất nhiều các đề xuất sử dụng giải thuật di truyền
cho bài toán lập lịch. Tuy nhiên, một điều cần phải chỉ rõ ở đây là bài toán lập lịch là
một trong những bài toán mà có nhiều thể loại đa dạng, mỗi một thể loại cần có thiết kế
giải thuật di truyền đặc biệt. Về cơ bản, bài toán lập lịch được coi như là việc gán các
mốc thời gian (time slots) thực hiện cho các công việc (tasks) sao cho phù hợp với khả
năng về tài nguyên (resources). Tuy nhiên, sự đa dạng thể hiện ở các thể loại ràng buộc
khác nhau và mỗi một bài toán thực tế sẽ có những ràng buộc đặc trưng riêng. Chính vì
vậy, mà các nghiên cứu đề xuất giải thuật di truyền cho bài toán lập lịch luôn luôn là
một chủ đề nóng.
4.4. Một số ứng dụng khác
• Thiết kế mạng nơron, kiến trúc lẫn trọng số.
• Quỹ đạo cho người máy.
• Các hệ phi tuyến động - phỏng đoán, phân tích dữ liệu.
• Tìm dạng của các phân tử protein.
• Cải tiến chương trình LISP (lập trình gen).
HVTH: Lê Phú Quí Trang *4
