Bài tập lớn Đề tài Giải thuật Di truyền | Môn Nhập môn về trí tuệ nhân tạo - Đại học Hải Phòng

lOMoAR cPSD| 58707906
TRƯỜNG ĐẠI HỌC HẢI PHÒNG
Khoa Công nghệ thông tin
BÀI TẬP LỚN TRÍ TUỆ NHÂN TẠO
Đề tài: Giải thuật di truyền SVTH : GVHD: Năm 2024 lOMoAR cPSD| 58707906 MỤC LỤC Giới thiệu I.
Giải thuật di truyền (GA) và ứng dụng giải một số bài toán……
II. Một số bài toán liên quan đến giải thuật di truyền (GA)……….
III. Ứng dụng python……………………………………….. IV.
KẾT LUẬN…………………………………………….. lOMoAR cPSD| 58707906 Giới thiệu
- Genetic Algorithms (GAs) - Giải thuật di truyền là một kỹ thuật khoa
học máy tính nhằm giải quyết các bài toán tối ưu tổ hợp. GAs dựa trên
quá trình thích nghi tiến hóa của các quần thể sinh học dựa trên học
thuyết của Darwin. Nó vận dụng các nguyên lý: di truyền, đột biến, chọn
lọc tự nhiên và trao đổi chéo. GAs dùng một số thuật ngữ của ngành di
truyền học như: nhiễm sắc thể, quần thể (Population), Gene... Nhiễm sắc
thể được tạo thành từ các Gene (được biểu diễn của một chuỗi tuyến
tính). Mỗi Gene mang một số đặc trưng và có vị trí nhất định trong nhiễm
sắc thể. Mỗi nhiễm sắc thể sẽ biểu diễn một lời giải của bài toán. Trong
bài viết này tôi sẽ giải thích các khái niệm song song với việc lập trình ở một bài toán cụ thể.
GAs được sử dụng cho những bài toán khó, và đã được ứng dụng thành
công cho một số bài toán như: lập kế hoạch, hệ thống điều khiển, bài
toán người đi du lịch,… I.
Giải thuật di truyền (GA) và ứng dụng giải một số bài toán
- Giải thuật di truyền (GA) cũng như các mạng neuron, các thuật toán di truyền
cũng dựa trên 1 ẩn dụ sinh học: Các thuật toán này xem việc học như là sự
khó khăn trong 1 quần thể gồm những lời giải người mua việc đang tiến hóa
của bài toán. Một hàm ‘thích nghi’ (fitness function) sẽ đánh giá mỗi lời giải
để quyết định liệu nó mang đóng góp cho thế hệ những lời giải kế tiếp hay
không. Sau đó, phê chuẩn những phép toán na ná có biến đổi gene trong sinh
sản hữu tính, giải thuật sẽ tạo ra một quần thể những lời giải người mua việc mới
1. Giải thuật di truyền là như thế nào ? lOMoAR cPSD| 58707906
- Trình bày giải thuật di truyền tổng quát. Tùy theo từng bài toán mà nhà – ngoại
hình giải thuật sẽ phải mô tả yếu tố hơn về:
- Phương pháp biểu diễn một cá thể trong quần thể những lời giải người tìm
việc của bài toán, hay nói khác hơn là hình thức trình diễn 1 lời giải tiềm năng
của bài toán. Không phải lời giải của mọi bài toán đều với thể được mã hóa 1
bí quyết dễ dàng và khi không dưới dạng biểu diễn mức bit như trong bài toán
thỏa mãn CNF dưới đây.
- Độ lớn của quần thể là số lượng ứng viên với trong quần thể. Thông thường
những ứng viên của quần thể ban đầu được sắm 1 phương pháp ngẫu nhiên.
Độ to của quần thể là ko đổi qua những thế hệ, vì vậy, sẽ mang một công đoạn
tậu lọc và dòng bỏ một số lời giải người chọn việc sở hữu độ thích nghi thấp.
- Điều kiện ngừng của vòng lặp: mang thể là chương trình đạt tới một số lần lặp
một mực nào đó, hay đạt đến trung bình độ phải chăng nào đó của quần thể,…
- Hàm đánh giá (fitness function): Dùng để đánh giá một ứng cử viên mang
thấp hay không. Một ứng cử viên càng phải chăng tức là độ thích ứng của nó
càng cao và tiến tới trở thành lời giải đúng của bài toán. Việc ngoại hình 1
hàm kiểm tra phải chăng là siêu quan yếu trong thuật toán di truyền. Một
hàm kiểm tra không chính xác mang thể làm mất đi các người mua việc rẻ trong quần thể.
- Chọn lựa bao nhiêu phần trăm lời giải tốt để giữ lại? Hay mua bao nhiêu lời
giải ứng viên để kết hợp sở hữu nhau và sinh ra lời giải con. Phương pháp tạo
thành viên mới từ thành viên hiện có, còn gọi là toán tử di truyền (genetic operators): lOMoAR cPSD| 58707906
- Các toán tử di truyền phổ biến là Lai ghép (cross-over): Toán tử lai ghép lấy
hai lời giải người tậu việc và chia từng lời giải ra thành hai phần, sau đó bàn
thảo các phần có nhau để tạo ra ứng viên mới.
- Đột biến (mutation): Đột biến lấy 1 người sắm việc đơn lẻ và thay đổi 1
phương pháp tự nhiên một khía cạnh nào đó của nó. Độ thích nghi(fitness)
2. ví dụ minh họa giải thuật và toán tử di truyèn
- Trong ví dụ minh họa bằng hình 9.18, ta thấy tại thế hệ thiết bị n ta với một
lời giải mang độ thích nghi siêu tốt (2), và vì vậy, nó ko được dùng trong quá
trình tái sản xuất. Thay vào đó, lời giải với độ thích ứng cao nhất (13) sẽ được
nhân đôi và đưa vào quá trình tái sản xuất.
Hoặc ít phổ biến hơn là các toán tử di truyền: •
Đảo ngược (inversion): Đảo ngược thứ tự các bit trong chiếc lời giải. •
Trao đổi (Exchange): Trao đổi hai bit bất kỳ trong dòng lời giải sở hữu nhau. lOMoAR cPSD| 58707906
- Một toán tử di truyền tốt đóng 1 vai trò quan trọng trong thuật toán di truyền.
Toán tử di truyền buộc phải bảo toàn các mối quan hệ cốt yếu trong quần thể;
ví dụ, sự với mặt và sự độc nhất của mọi những thành phố trong hành trình
của người bán hàng trong bài toán người đi bán hàng.
II. Một số bài toán liên quan đến giải thuật di truyền (GA) Bài toán thỏa CNF
Bài toán thỏa mãn dạng chuẩn hội (Conjunctive normal form – CNF) là 1 bài toán
đơn giản: Một biểu thức của các mệnh đề (clause) ở dạng chuẩn hội hay CNF lúc nó
là 1 dãy những biến mệnh đề được kết nối mang nhau bởi toán tử quan hệ and (∧).
Mỗi mệnh đề sở hữu dạng là 1 tuyển (disjunction), gồm các toán tử quan hệ or (∨)
trên các biến mệnh đề (literal).
Ví dụ : Nếu ta sở hữu 6 biến mệnh đề a, b, c, d, e và f, thì biểu thức sau đây là 1 CNF:
Thỏa mãn CNF với nghĩa rằng chúng ta bắt buộc tìm ra một phép gán true hoặc false
(1 hoặc 0) cho mỗi biến mệnh đề a, b, c, d, e, f sao cho biểu thức CNF có giá trị là TRUE.
Một phương pháp trình diễn trùng hợp cho lời giải của bài toán này là một dãy sáu
bit, mỗi bit theo đồ vật tự a, b, c, d, e, f trình diễn true (1) hoặc false (0) cho mỗi
biến mệnh đề. Như vậy cái bit:
1 0 1 0 một 0 cho biết a, c, và e là true và b, d, và f là false, và do đấy lúc thay
những giá trị này vào biểu thức (1-3), thì cho giá trị false.
Chúng ta muốn rằng những toán tử di truyền sinh ra những thế hệ lời giải sao cho
biểu thức CNF mang trị true, vì thế mỗi toán tử buộc phải sinh ra 1 dòng 6-bit của
phép gán true cho biểu thức. Cách biểu diễn lời giải dưới dạng 1 dòng các bit như
trên sở hữu lại cho ta vô cùng 1 điều vô cùng thuận tiện là bất kỳ toán tử di truyền
nào (lai ghép, đột biến, đảo ngược, hay trao đổi) đều tạo ra 1 chiếc bit mới là một
lời giải khả dĩ hợp lệ.
Việc tậu lựa một hàm thích ứng cho quần thể những chuỗi bit này không bắt buộc
hoàn toàn dễ dàng. Thoạt nhìn chuỗi bit, ta khó có thể xác định 1 hàm thích ứng để
đánh giá được chất lượng của nó như thế nào, tức thị khó đoán được độ rẻ của nó so
với đáp án đúng. Đáp án đúng ở đây chính là chuỗi bit sao cho biểu thức CNF với giá trị true.
Tuy nhiên sở hữu 1 số bí quyết khác. Nếu ta để ý đến biểu thức CNF (1-3), thì ta
thấy rằng nó được tạo thành từ hội của 5 mệnh đề. Do ấy chúng ta với thể thiết lập
một hệ phân hạng cho phép chúng ta gần hạng những lời giải (mẫu bit) tiềm năng
trong khoảng giá trị từ 0 đến 5, tùy thuộc vào căn số đề mà loại đấy thỏa mãn. Do
ấy mẫu: 1 một 0 0 1 0 sở hữu độ thích nghi là 1
0 1 0 0 một 0 với độ thích nghi là 2
0 1 0 0 1 1 với độ thích ứng là 3
1 0 một 0 một một mang độ thích ứng là 5, và nó chính là 1 lời giải. lOMoAR cPSD| 58707906
Bài toán người đi bán hàng TSP
- Bài toán người bán hàng (traveling salesperson problem – TSP) là một bài
toán cổ điển đối mang AI và khoa học máy tính
- Phát biểu của bài toán TSP: Một người bán hàng có nhiệm vụ lép thăm N
thành thị như là 1 phần của lịch trình bán hàng. Đường đi giữa mỗi cặp thị
thành với 1 chi phí (ví dụ như độ dài đoạn đường, giá vé máy bay). Hãy tìm
ra đường đi có chi phí tốt nhất cho người bán hàng để bắt đầu lên đường tại 1
thành phố, thăm mọi các thị thành khác chỉ đúng 1 lần rồi quay lại thành thị xuất phát.
- Như chúng đã giới thiệu ở chương III, hầu hết ko gian trạng thái của nó đòi
hỏi cần phê duyệt N! trạng thái để mang thể tậu ra lời giải tối ưu, trong ấy N
là số thành thị nên đi qua. Khi N hơi to thì bài toán sẽ bị bùng nổ tổ hợp, bởi
vậy người ta đặt vấn đề là mang buộc phải thiết hay ko cho việc chạy một máy
trạm làm cho việc đắt tiền trong nhiều giờ để cho 1 lời giải thông minh hay
chỉ cần chạy 1 PC rẻ tiền trong vài phút để sở hữu được những kết quả “đủ
tốt”. Giải thuật di truyền chính là một giải pháp cho lựa chọn đồ vật hai.
- Ở bài toán này, tiêu dùng chiếc bit để trình diễn cho lời giải của bài toán không
-phải là một bí quyết hay. Chẳng hạn, ta với chín tỉnh thành cần kẹ thăm 1, 2,
…9, ta xem mỗi thành thị như một loại 4 bit 0001, 0010,… 1001.
Khi đấy 1 lời giải khả dĩ sẽ có hình thức như sau:
0001 0010 0011 0100 0101 0110 0111 1000 1001.
- Với cách trình diễn như vậy, việc ngoại hình những toán tử di truyền sẽ trở
thành rất khó khăn. Toán tử lai ghép một mực là không được, vì chuỗi mới
được tạo từ hai cha mẹ khác nhau hầu như sẽ không biểu diễn một đường đi
trong đấy ghẹ thăm mỗi tỉnh thành đúng một lần. Trong thực tế, với lai ghép,
một số đô thị có thể bị xóa bỏ trong khi những thị thành khác được xẹp thăm
nhiều hơn 1 lần, và do đó đấy ko buộc phải là một lời giải hợp lệ. Còn toán tử
đột biến thì thế nào? Giả sử bit trái nhất của tỉnh thành trang bị sáu, 0110,
được đột biến thành 1? 1110, hay là 14, thì nó không còn là một thị thành hợp lệ.
- Một phương pháp tiếp cận khác là sẽ bỏ qua trình diễn dạng loại bit và đặt cho
mỗi thành phố một tên theo bảng chữ chiếc hoặc số, thí dụ 1, 2, …9; xem
đường đi qua những thành thị là 1 sự sắp vật dụng tự của chín ký số này, và
sau ấy sắm toán tử di truyền ưng ý để tạo ra những đường đi mới. Ở đây ta
thấy phép trao đổi (exchange) trùng hợp hai thị thành trong đường đi với thể
sử dụng được, còn phép toán lai ghép (crossover) thì không. Việc trao đổi các
đoạn của 1 đường đi với các đoạn khác của cộng đường đi đó, hoặc bất cứ
toán tử nào sắp xếp lại những chữ mẫu của đường đi ấy (mà không xóa bỏ,
thêm, hay nhân đôi bất cứ thành thị nào) đều có thể sử dụng được. Tuy nhiên,
những phương pháp này gây cạnh tranh cho việc đưa vào thế hệ con cháu
những thành phần “tốt hơn” của những chiếc trong những đường đi qua của
những thành thị của hai bố mẹ khác nhau. lOMoAR cPSD| 58707906
- Nhiều nhà nghiên cứu đã đưa ra các toán tử lai ghép với khả năng khắc phục
các vấn đề này, trong đó với toán tử lai ghép với đồ vật tự (order crossover)
do Davis đưa ra vào năm 1985. Lai ghép mang đồ vật tự xây dựng con cháu
bằng phương pháp chọn một dãy con các thành thị trong đường đi của một
mẫu cha mẹ. Nó cũng bảo toàn đồ vật tự khá những đô thị từ cha mẹ kia. Đầu
tiên, sắm hai điểm cắt, diễn tả bởi dấu “|”, điểm cắt này được chen vào 1 cách
khi không vào cộng một vị trí của mỗi cái cha mẹ.
- Những điểm cắt này là ngẫu nhiên, nhưng một lúc được chọn, thì những vị trí
như nhau sẽ được dùng cho cả hai cha mẹ. Ví dụ, sở hữu hai cái cho má p1 và
p2, với những điểm cắt sau thành thị vật dụng ba và vật dụng bảy:
p1 = (1 9 2 | 4 6 5 7 | 8 3) p2 = (4 5 9 | 1 8 7 6 | 2 3)
Hai chiếc con c1 và c2 sẽ được sinh ra theo bí quyết sau. Đầu tiên, các đoạn
giữa hai điểm cắt sẽ được chép vào những chiếc con:
c1 = (x x x | 4 6 5 7 | x x) c2 = (x x x | 1 8 7 6 | x x)
- Bước kế tiếp là khởi đầu từ điểm cắt đồ vật hai của một trong hai mẫu cha mẹ,
giả dụ ta đang muốn hoàn tất mẫu c1, thì ta sẽ khởi đầu từ điểm cắt trang bị
hai của dòng p2, ta chép các đô thị từ điểm cắt này theo vật dụng tự vào các
chỗ còn trống của c1, bỏ qua những thành phố mà c1 đã mang (các ký số được
in đậm và nghiêng trong lược đồ bên dưới). Khi tới cuối cái p2, thì quay lại
đầu loại p2 tiếp tục chép sang c1 cho tới khi c1 đủ.
- Với giải thuật lai ghép này, những đường đi của thế hệ con sẽ được bảo đảm
là những đường đi hợp lệ, đi qua mỗi tỉnh thành một lần duy nhất.
Tóm lại, trong lai ghép trang bị tự, những mảnh của 1 đường đi được truyền
từ 1 cha mẹ, p1, sang một con, c1, trong khi gần xếp của những đô thị còn lại
của con c1 được thừa kế từ ba má kia, p2. Điều này ủng hộ cho trực quan hiển
nhiên là thiết bị tự của các thành phố đóng vai trò quan yếu trong việc tạo ra
đường đi có mức giá phải chăng nhất, và do vậy việc truyền lại những đoạn
thông tin sở hữu vật dụng tự này từ những bố mẹ với độ thích ứng cao sang
con chiếc là 1 điều vô cùng quan trọng.
- Ngoài toán tử lai ghép vật dụng tự trên, còn sở hữu vô cùng đa dạng toán tử
lai ghép và đột biến khác được đưa ra để giải quyết bài toán này. Bảng 9.5 liệt
kê các toán tử lai ghép,
Danh sách những toán tử đột biến cho bài toán TSP.
Đánh giá giải thuật
- Các thí dụ vừa nêu trên làm cho vượt trội các vấn đề có tính duy nhất của thuật
toán di truyền về biểu diễn tri thức, tậu toán tử di truyền, và ngoại hình hàm
thích nghi. Biểu diễn được tậu phải tương trợ cho những toán tử di truyền.
Một điểm dáng để ý nữa là những toán tử di truyền phải được kiểu dáng sao lOMoAR cPSD| 58707906
cho bảo lưu được những mảnh thông tin có ý nghĩa trong lời giải tiềm năng từ
thế hệ này sang những thế hệ tiếp theo.
- Một sức mạnh quan yếu của thuật toán di truyền là bản chất đồng thời trong
tìm kiếm của nó. Các thuật toán này thực hành 1 dạng mạnh của leo núi (hill
climbing) trong đấy duy trì phổ biến lời giải (trong quần thể những lời giải),
chiếc bỏ những lời giải ko với triển vọng, và tăng chất lượng của những lời
giải tốt. Hình 9.19 phỏng theo Holland (1986), cho thấy nhiều lời giải tụ họp
về các điểm hợp lý trong không gian tậu kiếm.
- Trong hình này, trục hoành trình diễn các điểm với thể có trong ko gian lời
giải, trong khi trục tung phản ảnh chất lượng của các lời giải đó. Các điểm
chấm nằm trên cung là những thành viên của quần diễn đạt tại. Khởi đầu, các
lời giải được rải trong không gian những lời giải sở hữu thể có. Sau 1 vài thế
hệ, chúng có thiên hướng cụm lại kế bên các vùng có chất lượng lời giải cao hơn.
Các thuật toán di truyền được xem là leo núi song song
- (theo Holland 1986) Tuy nhiên, với sức mạnh như vậy, giải thuật genetic cũng
không thể áp dụng cho toàn bộ các bài toán sở hữu thể có. Vì như ta thấy qua
hai ví dụ trên, lời giải của bài toán buộc phải được trình diễn dưới một dạng
mẫu phù hợp cho các toán tử di truyền hoạt động. Trong thực tế mang phổ
biến bài toán ko thể khiến được điều này. Vì vậy, khi nghiên cứu về giải thuật
này, mang siêu rộng rãi câu hỏi đã được đưa ra nhằm hiểu rõ hơn nữa về thực
chất hoạt động của nó: •
Liệu chúng ta sở hữu thể đưa ra những đặc điểm về những loại bài toán
màgiải thuật di truyền (GA) với thể thực hành tốt • Các chiếc bài toán nào thì ko ưa thích với GA. •
Dựa vào đâu để ta với thể nói là GA thực hành phải chăng hay ko thấp
đối mang 1 loại bài toán nào đó? •
Liệu sở hữu những qui luật nào thể hiện hành vi của GA ở mức vĩ mô?
Hay cụ thể hơn, là liệu với bất kỳ sự phán đoán nào về sự đổi thay của độ
thích ứng của những nhóm con trong quần thể theo thời gian? •
Có phương pháp nào để diễn tả những hiệu ứng khác nhau của các toán
tử di truyền như lai ghép, đột biến, đảo ngược, v.v… •
Trong các trường hợp nào (bài toán nào, toán tử di truyền nào) thì GA
sẽ thực hiện thấp hơn những phương pháp nghiên cứu của TTNT truyền
thống. Những câu hỏi này (và còn rộng rãi hơn nữa) vẫn đã và đang được
những nhà kỹ thuật như Holland, Mitchell, Golderg,… nghiên cứu. III. Ứng dụng python lOMoAR cPSD| 58707906
1. Sơ đồ thuật toán
Giải thuật sẽ được thực hiện qua các bước sau: •
Khởi tạo quần thể: Sinh ra ngẫu nhiên một quần thể gồm n cá thể (trong đó
n là lời giải cho bài toán). •
Tính giá trị thích nghi: Ước lượng độ thích nghi của mỗi cá thể. •
Điều kiện dừng: Kiểm tra điều kiện để kết thúc giải thuật. •
Chọn lọc: Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng
(cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn). •
Trao đổi chéo: Với một xác suất được chọn, trao đổi chéo hai cá thể bố mẹ
để tạo ra một cá thể mới. •
Đột biến: Với một xác suất đột biến được chọn, biến đổi cá thể mới. •
Chọn kết quá: Nếu thỏa mãn điều kiện dừng thì giải thuật kết thúc và chọn
được lời giải tốt nhất trong quần thể hiện tại.
Ta có thể thấy rằng, khi Điều kiện dừng chưa được thỏa mán, quần thể mới sẽ liên
tục được tạo ra bằng cách lặp lại 3 bước Chọn lọc, Trao đổi chéo và Đột biến.
GAs có 2 điều kiện dừng cơ bản: lOMoAR cPSD| 58707906
1. Dựa trên cấu trúc nhiễm sắc thể, kiểm soát số gene được hội tụ, nếu số gene
được hội tụ tại một điểm hoặc vượt quá điểm đó thì giải thuật kết thúc.
2. Dựa trên ý nghĩa đặc biệt của nhiễm sắc thể, đo sự thay đổi của giải thuật sau
mỗi thế hệ, nếu thay đổi này nhỏ hơn một hằng số xác định thì giải thuật kết thúc.
3. Bài toán: Guessing Password - Đoán mật khẩu
Nào chúng ta bắt đầu ứng dụng giải thuật di truyền vào giải quyết bài toán đoán mật khẩu.
Về bài toán, sử dụng những ký tự trong bảng chữ cái để tái tạo lại mật khẩu. Cụ thể,
ở bài này chúng ta sẽ bắt đầu với những ký tự: a-z, A-Z, !. để tái tạo nên mật khẩu: "Hello World!".
Các bước giải bài toán: •
Khởi tạo quần thể: Sinh ra ngẫu nhiên một đoạn dài 11 ký tự (dài bằng với mục tiêu "Hello World". •
Tính giá trị thích nghi: Đếm số ký tự trùng giữa đoạn tạo ra và "Hello World". •
Điều kiện dừng: Kiểm tra xem số ký tự trùng bằng 11 hay không. •
Chọn lọc: Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng
(cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn). •
Trao đổi chéo (Không thực hiện ở bài toán này): Với một xác suất được
chọn, trao đổi chéo hai cá thể bố mẹ để tạo ra một cá thể mới. •
Đột biến: Với một xác suất đột biến được chọn, biến đổi cá thể mới. Chọn
kết quá: Khi số ký tự trùng bằng 11 thì dừng giải thuật. Chromosomes và Gene
Trong sinh học, nói một cách khái quát, trong một Chromosomes (nhiễm sắc thể) sẽ
có thể chứa rất nhiều loại gene khác nhau.
Ở bài toán của chúng ta, tất cả những trình tự đoạn 11 ký tự ( độ dài bằng với "Hello
World") được gọi là Chromosomes. Và mỗi loại ký tự sẽ đại diện cho 1 loại Gene khác nhau. geneSet = "
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" target = "Hello World"
Đầu tiên chúng ta khai báo biến geneSet chứa các ký tự trong bảng chữ cái, mỗi ký
tự đại diện cho một loại Gene. Cù ng với đó, khai báo biến target là đoạn ký tự mục tiêu "Hello World". lOMoAR cPSD| 58707906
Bước 1: Khởi tạo quần thể import random
def initialize_chromosomes(length): chromosomes = [] while
len(chromosomes) < length: sampleSize = min(length - len(chromosomes), len(geneSet))
chromosomes.extend(random.sample(geneSet, sampleSize))
return ''.join(chromosomes)
Sử dụng random.sample để tạo ngẫu nhiên từ geneSet theo độ dài cho trước.
Chúng ta có thể có test bằng initialize_chromosomes(11). Kết quả sẽ có dạng: 'yTtumWSgfkM'
Chú ý: Vòng While sinh ra nhằm xử lý vấn đề nếu độ dài của Chromosomes dài hơn
số lượng loại Gene ban đầu
Bước 2: Tính giá trị thích nghi
Chúng ta thấy rằng, Chromosomes có khả năng là những trường hợp như: • Sekmo xosmd • Seklo Wocle • Fello Wosld • Gello World • Hello World
Có thể nhận ra ngay đoạn cuối cùng là đoạn chính xác. Nhưng làm sao chúng ta có
thể "đo" được độ tối ưu của Chromosomes này?
Hàm lỗi (error function/ cost function/loss function) là một hàm số giúp đo độ tối
ưu của một Chromosome. Ở hàm này, chúng ta đang hướng tới giá trị càng nhỏ càng tốt.
Với bài toán Đoán mật khẩu, để đo độ tối ưu, chúng ta đếm số kí tự sai khác trên
cùng vị trí giữa Chromosome và đoạn kí tự mục tiêu "Hello World". Vì vậy, hàm lỗi
ở đây sẽ tối ưu ở số kí tự sai khác bằng 0.
Dùng quy luật trên để tính sai khác cho các trường hợp Chromosomes trên: • Sekmo xosmd(6) • Seklo Wocle(4) • Fello Wosld(2) • Gello World(1) • Hello World(0) lOMoAR cPSD| 58707906
def error_function(chromosome):
return len(target) - sum(1 for expected, actual \
in zip(target, chromosome) \ if expected == actual)
Hàm error_function sẽ tính số ký tự sai khác ở cùng một vị trí giữa Chromosome và
"Hello World". Có thể test hàm trên như sau: error_function("Hello World") sẽ cho kết quả bằng 0.
Bước 3: Điều kiện điểm dừng
Kiểm tra điều kiện điểm dừng là error_function có bằng 0 hay không. Bước 4: Tiến hóa
Trong bước này, chúng ta sẽ gộp chung cả 3 kỹ thuật: chọn lọc, trao đổi chéo và
đột biến. Mục tiêu của bước này là tạo ra thế hệ mới tối ưu hơn thế hệ cũ. Độ tối
ưu sẽ được đo theo hàm lỗi. Chúng ta có thể mường tượng ra rằng, đây là một vòng
lặp, mỗi vòng lặp sẽ thực hiện 3 kỹ thuật trên, sau đó check điều kiện dừng. Nếu
không đáp ứng được thì vòng lặp sẽ tiếp tục cho đến khi đáp ứng được thì thôi.
Ở bài toán này, chúng ta sẽ chỉ sử dụng chọn lọc và đột biến. Phần về trao đổi chéo
tôi sẽ có một bài riêng vì nó có chút phức tạp hơn.
def mutate(parent): index = random.randrange(0, len(parent)) childGenes = list(parent)
newGene, alternate = random.sample(geneSet, 2)
childGenes[index] = alternate \ if
newGene == childGenes[index] \
else newGene return ''.join(childGenes)
index sẽ là một số được chọn ngẫu nhiên tức là đột biến sẽ xảy ra một cách ngẫu
nhiên trên Chromosome. newGene và alternate cũng sẽ được ngẫu nhiên tạo ra từ geneSet.
Vì sao lại phải tạo ra tận 2 đột biến? Câu trả lời là đột biến có thể vô nghĩa tại 1 điểm
nên cần 1 đột biến khác thay thế. Hàm hỗ trợ
Xây dựng hàm display giúp hiển thị sự thay đổi qua từng thế hệ và thời gian chạy tương ứng lOMoAR cPSD| 58707906 import datetime
def display(guess): timeDiff = datetime.datetime.now() - startTime fitness = error_function(guess)
print("{0}\t{1}\t{2}".format(guess, fitness, str(timeDiff))) Main
Sau đây sẽ là phần chạy main cho giải thuật GAs: random.seed ( 1 )
startTime = datetime.datetime.now ()
bestParent = initialize_chromosomes ( len ( target ))
bestFitness = error_function ( bestParent ) display ( bestParent ) while True:
child = mutate ( bestParent )
childFitness = error_function ( child )
if bestFitness <= childFitness : continue display ( child )
if childFitness == 0 : break hJYVdpgEBDO 11 0:00:00 HJYVdpgEBDO 10 0:00:00 HJYVdpgEBDd 9 0:00:00.001003
bestFitness = childFitness bestParent = child HJYVopgEBDd 8 0:00:00.001003 HJYVopgErDd 7 0:00:00.004010 HJYVopgErld 6 0:00:00.005012 HJlVopgErld 5 0:00:00.008021 HJlVo gErld 4 0:00:00.008021 HelVo gErld 3 0:00:00.009036 lOMoAR cPSD| 58707906
HelVo gorld 2 0:00:00.010026 Hello gorld 1 0:00:00.017045 Hello World 0 0:00:00.020052
Khởi tạo quần thể với Chromosome đầu tiên bestParent . Tính hàm lỗi cho
Chromosome này cho chúng ta kết quả là 11,
cho thấy chưa có vị trí nào
giữa Chromosome khởi tạo và "Hello World" trùng nhau.
Chúng ta sẽ thấy rằng, việc chọn lọc đã diễn ra ở điều kiện vòng lặp, tức là cứ mỗi
khi hàm lỗi giảm là sẽ giữ lại bestParent t hay thế cho Chromosome cũ kém tối ưu hơn. IV. KẾT LUẬN
Chúng ta đã cùng nhau xây dựng một giải thuật di truyền và hiểu các bước diễn ra bên trong giải thuật.
Giải thuật trên gần như là dạng đơn giản nhất. Nếu có bài tiếp theo, tôi sẽ giới thiệu
thêm về một số vấn đề bên trong và xử lý những bài toán phổ biến và có đôi chút phức tạp hơn.
Xin cảm ơn vì đã đọc đến đây :D. Nguồn tham khảo:
1. https://github.com/handcraftsman/GeneticAlgorithmsWithPython