4/27/2017
1
Giả i thuậ t di truyề n
1
Lị ch sử
• GA đề xuấ t bở i John Holland năm 1970
• Phổ biế n nhữ ng năm 1980
• Dự a trên ý tư ở ng về luậ t tiế n hóa Darwin
• Dùng để giả i quyế t nhiề u bài toán không dễ
giả i quyế t bằ ng các kỹ thuậ t khác
2
3
Tiế n hóa trong thế giớ i thự c
• Mỗ i tế bào số ng bao gồ m các nhiễ m sắ c thể (chromosomes)
–là các xâu DNA
• Mỗ i NST bao gồ m 1tậ p các gene – các khố i DNA
• Mỗ i gene quyế t đị nh mộ t số đặ c điể m củ a cá thể (như màu
mắ t)
• Mộ t tậ p các gene đư ợ c gọ i là kiể u di truyề n (genotype)
• Mộ t tậ p các đặ c điể m (như màu mắ t) đư ợ c gọ i là kiể u hình (
phenotype)
• Việ c tái tạ o (reproduction) là việ c kế t hợ p các gene từ bố mẹ
cộ ng vớ i mộ t số lư ợ ng nhỏ các độ t biế n (mutation) trong bả n
sao
• Độ phù hợ p (fitness) củ a 1cá thể là số con nó có thể sinh ra
trư ớ c khi nó chế t
• Tiế n hóa dự a trên “sự số ng sót củ a các cá thể phù hợ p nhấ t”
4
Đặ t vấnđề
• Giả sử có 1 vấ n đề
• Ta chư a biế t cách giả i
• Có thể làm gì?
• Sử dụ ng máy tính để tìm lờ i giả i?
• Làm thế nào?
4/27/2017
2
Giả i pháp tệ nhấ t
Thuậ t toán “thử và sai”
Repeat
Sinh mộ t giả i pháp ngẫ u nhiên
Thử giả i pháp đó và kiể m tra sự phù hợ p củ a nó
Until giả i pháp đủ tố t
5
Có thể làm như vậ y không?
• Đôi khi – có:
– Nế u chỉ có vài đáp án
– Và có đủ thờ i gian
• Vớ i đa phầ n các vấ n đề - không:
– Có quá nhiề u đáp án
– Không có thờ i gian thử
6
Ý tư ở ng ít tệ hơ n (GA)
Sinh 1 tậ p các giả i pháp ngẫ u nhiên
Repeat
Thử mỗ i giả i pháp trong tậ p (xế p hạ ng chúng)
Loạ i bỏ 1số giả i pháp kém trong tậ p
Nhân các giả i pháp tố t lên
Tạ o ra mộ t số thay đổ i trong các cá thể này
Until giả i pháp tố t nhấ t đủ tố t
7
Làm cách nào để mã hóa 1giả i
pháp
• Phụ thuộ c vào vấ n đề
• GA mã hóa giả i pháp như 1 chuỗ i cố đị nh
các bit (ví dụ 101110, 111111, 000101)
• Mỗ i bit biể u diễ n mộ t số đặ c điể m củ a giả i
pháp đề xuấ t
• Để có thể sử dụ ng GA, cầ n “thử ” các chuỗ i
và cho điể m mứ c độ “tố t” củ a giả i pháp
8
4/27/2017
3
Ví dụ , khoan dầ u
• Giả sử cầ n khoan dầ u ở đâu đó dọ c theo
1km đư ờ ng sa mạ c
• Vấ n đề : chọ n chỗ tố t nhấ t trên đư ờ ng có thể
cho nhiề u dầ u nhấ t
• Mỗ i giả i pháp là 1 vị trí trên đư ờ ng, tứ c là 1
số trong khoả ng [0..1000]
9
Khoan chỗ nào
0500 1000
Đư ờ ng
Giả i pháp2
= 900
Giả i pháp
1 = 300
10
Khoan dầ u
• Tậ p các giả i pháp có thể [0..1000] đư ợ c gọ i
là không gian tìm kiế m hoặ c không gian
trạ ng thái
• Chuyể n sang xâu nhị phân
512 256 128 64 32 16 8 4 2 1
900 1 1 1 0 0 0 0 1 0 0
300 0 1 0 0 1 0 1 1 0 0
1023 1 1 1 1 1 1 1 1 1 1
11
Khoan dầ u
01000
Đư ờ ng
Giả i pháp2 = 900
(1110000100)
Giả i pháp1 = 300
(0100101100)
O I L
Vị trí
30 5
12
4/27/2017
4
Không gian tìm kiế m
• Không gian tìm kiế m ứ ng vớ i các hàm như f(x),
f(x,y), có thể mộ t chiề u hoặ c nhiề u chiề u.
• Không gian tìm kiế m có thể đư ợ c mô hình hóa như
1bề mặ t trong đó độ phù hợ p là độ sâu
• Mỗ i kiể u di truyề n (genotype) là 1điể m trong
không gian
• GA cố gắ ng tìm các điể m tố t hơ n (độ phù hợ p cao
hơ n) trong không gian
13
Bề mặ t
• GA có thể vấ p phả i tố i ư u hóa cụ c bộ (local maxima) nế u
KGTK có nhiề u điể m như vậ y 14
S¬ ®å tæng thÓ cña GA
• Khở i độ ng quầ n thể đầ u tiên P gồ m N cá thể mộ t cách ngẫ u
nhiên
•REPEAT
– Giả i mã các cá thể thành tham số
– Tính giá trị hàm mụ c tiêu cho từ ng cá thể trong P
– Chuyể n đổ i giá trị hàm mụ c tiêu (Target) thành giá trị độ
phù hợ p (Fitness)
– Tiế n hành toán tử chọ n lọ c tạ o ra quầ n thể bố mẹ tạ m
thờ i P1
– Tiế n hành toán tử lai ghép từ P1tạ o ra quầ n thể các con
P2
– Tiế n hành toán tử độ t biế n trên P2tạ o ra quầ n thể P3
– Tiế n hành toán tử tái tạ o để tạ o ra quầ n thể cho thế hệ
tiế p theo từ hai quầ n thể P2 và P3
• UNTIL (Điề u kiệ n dừ ng thoả )
15
Sinh thêm cá thể - Phép lai ghép
(Crossover)
• Kế t hợ p gene củ a 2 cá thể bố mẹ có độ phù
hợ p cao để tạ o nên cá thể con
• Việ c kế t hợ p 2 cá thể bố mẹ phụ thuộ c vào
xác suấ t lai ghép
• Sinh 2 cá thể mớ i (offspring)
• Mỗ i cá thể mớ i có thể bị thay đổ i mộ t cách
ngẫ u nhiên (độ t biế n -mutation)
16
4/27/2017
5
Lai ghép
1010000000
1001011111
Lai ghép 1
điể m–ngẫu
nhiên
1011011111
1010000000
Parent1
Parent2
Offspring1
Offspring2
Lai ghép đư ợ c áp dụ ng vớ i tỉ lệ cao
(khoả ng 0.8 đế n 0.95)
17
Độ t biế n
1011011111
1010000000
Offspring1
Offspring2
1011001111
1000000000
Offspring1
Offspring2
mutation rate đư ợ c áp dụ ng vớ i tỉ lệ thấ p (thư ờ ng giữ a 0.1
và 0.001)
mutate
Original offspring Mutated offspring
18
Các biế n thể củ a GA
• Các chiế n lư ợ c lự a chọ n (không phả i roulette)
– Vòng loạ i (Tournament)
– Elitism, v.v…
• Các chiế n lư ợ c trao đổ i chéo
–Multi-point crossover
–3way crossover, v.v…
•Các cách mã hóa khác
– Các giá trị nguyên
– Tậ p có thứ tự các ký tự
• Các kiể u biế n dị khác nhau
19
Các tham số
• Kích thư ớ c quầ n thể (N), tỉ lệ độ t biế n (m),
tỉ lệ lai ghép (c)
• Các giá trị này cầ n phù hợ p vớ i kế t quả
mong muố n
• Các giá trị thư ờ ng dùng
N = 50, m = 0.05, c = 0.9
20