Bài giảng Trí tuệ nhân tạo: Giải thuật di truyền

4/27/2017

Lịch sử

Giải thuật di truyền

• 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

Đặt vấn đề

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 1 tậ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)

• 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?

• 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 1 cá 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” 3

4/27/2017

Giải pháp tệ nhất

Có thể làm như vậy không?

• Đôi khi – có:

Thuật toán “thử và sai”

– Nếu chỉ có vài đáp án – Và có đủ thời gian

Repeat

• Với đa phần các vấn đề - không:

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ó

– Có quá nhiều đáp án – Không có thời gian thử

Until giải pháp đủ tốt

Ý tưởng ít tệ hơn (GA)

Làm cách nào để mã hóa 1 giải pháp

Sinh 1 tập các giải pháp ngẫu nhiên Repeat

• 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

Thử mỗi giải pháp trong tập (xếp hạng chúng) Loại bỏ 1 số 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

• Để 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

Until giải pháp tốt nhất đủ tốt

4/27/2017

Khoan chỗ nào

Ví dụ, khoan dầu

• Giả sử cần khoan dầu ở đâu đó dọc theo

1km đường sa mạc

Giải pháp 1 = 300

Giải pháp2 = 900

• 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

Đường

số trong khoảng [0..1000]

0

500 1000

Khoan dầu

Giải pháp1 = 300 (0100101100)

Giải pháp2 = 900 (1110000100)

• 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

1000

Đường 0

900 1 1 1 0 0 0 0 1 0 0

L I

1023

300 0 1 0 0 1 0 1 1 0 0

1 1 1 1 1 1 1 1 1 1

30

5 Vị trí

4/27/2017

Bề mặt

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ư

1 bề 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

• 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

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

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

– 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ị độ

• Việc kết hợp 2 cá thể bố mẹ phụ thuộc vào

phù hợp (Fitness)

xác suất lai ghép

– 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ừ P1 tạo ra quần thể các con

• Sinh 2 cá thể mới (offspring) • Mỗi cá thể mới có thể bị thay đổi một cách

P2

ngẫu nhiên (đột biến - mutation)

– Tiến hành toán tử đột biến trên P2 tạ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ệ 15

tiếp theo từ hai quần thể P2 và P3

• UNTIL (Điều kiện dừng thoả)

4/27/2017

mutate

Lai ghép

Đột biến

1011001111 1011011111 Offspring1 Offspring1

1000000000 1010000000 1011011111 1010000000 Offspring2 Offspring2 Parent1 Offspring1

1010000000 1001011111 Original offspring Offspring2 Parent2 Mutated offspring

Lai ghép 1 điểm – ngẫu nhiên Lai ghép được áp dụng với tỉ lệ cao (khoảng 0.8 đến 0.95) mutation rate được áp dụng với tỉ lệ thấp (thường giữa 0.1 và 0.001)

Các biến thể của GA

Các tham số

• Các chiến lược lựa chọn (không phải roulette)

• 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ả

• Các chiến lược trao đổi chéo

mong muốn

• Các giá trị thường dùng

N = 50, m = 0.05, c = 0.9

– Vòng loại (Tournament) – Elitism, v.v…

– Multi-point crossover – 3 way 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

4/27/2017

Các bước tiến hành

Đặc điểm của giải thuật GA

Bước 1: • Chọn biểu diễn gen:

– Nhị phân: tập ký tự {0,1} – Biểu diễn với tập ký tự lớn hơn ví dụ {a,b,..., z} – Biểu diễn số thực

• GA tìm kiếm trên một quần thể các cá thể • GA làm việc với mã của các thông số • GA chỉ sử dụng thông tin của hàm mục tiêu • GA sử dụng các luật chuyển đổi mang tính ngẫu

nhiên

mp cp

• Xây dựng các toán tử thao tác trên biểu diễn gen đã chọn • Xây dựng sơ đồ mã hoá và giải mã cho các cá thể • Xây dựng hàm chuyển đổi từ giá trị hàm mục tiêu sang giá trị độ phù hợp

Bước 2: • Tiến hành quá trình tiến hoá theo sơ đồ của giải thuật

• Chọn các tham số của GA: – Số cá thể trong quần thể N – Xác suất lai ghép – Xác suất đột biến – Số thế hệ cần tiến hoá G

Ví dụ

Toán tử lựa chọn

• Bài toán: tìm giá trị cực đại của hàm: x2

11100 11001 11011 10100

trên{0,1,…,31}

• GA:

– Biểu diễn dưới dạng chuỗi nhị phân. VD

01101  13

– Kích thước quần thể : 4 – toán tử lai ghép 1 điểm cắt, đột biến tại 1 điểm – Lựa chọn kiểu Roulette wheel – Khởi tạo ngẫu nhiên

4/27/2017

Lai ghép

Đột biến

784

400 2538 634.5

Ví dụ về tối ưu hoá hàm

C¸ thÓ

2 x 1

gi¸ trÞ ®é phï hîp

X¸c suÊt chän lùa

gi¸ trÞ hµm môc tiªu

Sè b¶n copy trong P2

Gi¸ trÞ trung b×nh

2x nguyên trong khoảng [0,15] và nguyên trong khoảng [0,31]

• Bước 2: • Khởi động quần thể đầu tiên ngẫu nhiên f x   • Bài toán: tìm giá trị cực đại của hàm: với

101001001 001110110 111010100 101101111

010011101

-13

0.0047

100001110

0.3033

101010011

0.4502

38.75

011101100

0.2417

• Sử dụng sơ đồ chọn lọc tỷ lệ, toán tử lai ghép 1 điểm cắt, toán tử

• Tiến hành lai ghép và đột biến tạo ra quần thể của thế hệ tiếp theo

đột biến biến đổi 0 thành 1 và ngược lại, toán tử tái tạo không tinh hoa quần thể con P3 trở thành quần thể cho thế hệ tiếp theo.

Bè mÑ

con

con sau ®ét biÕn

C¸ thÓ sè

Gi¸ trÞ hµm môc tiªu

Gi¸ trÞ trung b×nh

VÞ trÝ lai ghÐp

• Fitness = Target - min Target trong quần thể + 1 • Chọn tham số N = 4, Pc = 0.75, Pm = 0.25, G = 100

2 3

100001110 101010011

100010011 101001110

8 10

19 13

45 87

86.5

3 4

101010011 011101100

101010000 011101111

14 7

16 15

180 34

111010000 011101111

Bíc 1: • Chọn mã hoá nhị phân {0,1} với 4 gen cho x1, và 5 gen cho x2 011010001 tương ứng với x1 = 0110 =6; x2 = 10001=17

4/27/2017

Lai ghép đồng nhất

Lai ghép n điểm

• Chọn n điểm lai ghép ngẫu nhiên • Cắt dọc theo các điểm này • Gắn các đoạn giữa các cá thể • Gán ‘đầu’ vào 1 cha, ‘đuôi’ vào 1 cha khác • Tung đồng xu cho mỗi gene của con đầu tiên • Làm 1 bản sao đảo của gene cho con thứ 2 • Sự kế thừa độc lập vị trí

Lai ghép hay đột biến

Khám phá: Phát hiện các vùng hứa hẹn trong không gian tìm kiếm, tức là lấy được thông tin từ bài toán

– Phụ thuộc vào bài toán, nhưng – Tốt nhất nên có cả 2 – Nếu chỉ đột biến, có thể tiến hóa – Nếu chỉ lai ghép , không tiến hóa

Khai thác: Tối ưu hóa trong vùng hứa hẹn, tức là sử dụng thông tin

Thường kết hợp cả 2 phương pháp này.

• Lai ghép là việc khám phá, nó sẽ là 1 bước nhảy đến 1 miền nào đó trong 2 cá thể bố mẹ

• Đột biến là việc khai thác, nó tạo ra 1 sự thay đổi nhỏ, vì vậy nó ở gần miền của cha nó

4/27/2017

Lai ghép hay đột biến

Các cách biểu diễn khác

Có thể mã hóa các biến số trực tiếp dưới dạng: • Chỉ có lai ghép có thể kết hợp các thông tin từ thế hệ cha • Số nguyên • Chỉ có đột biến tạo ra các thông tin mới (gene) • Các biến dấu phẩy động • lai ghép không thay đổi tần suất của gene trong quần thể

• Để đạt được kết quả tối ưu, cần 1 chút may mắn trong phép đột biến

Lai ghép theo công thức đơn

Biểu diễn dạng số nguyên

...,

)

...,





1( 





x k • Con thứ 2 ngược lại • VD:  = 0.5

• Một số bài toán sử dụng số nguyên để biểu diễn như xử lý ảnh • Một số bài toán khác sử dụng các giá trị từ 1 tập cố định, vd • Bố mẹ: x1,…,xn  và y1,…,yn Lấy ngẫu nhiên 1 NST k • • Con thứ 1 là ,1 x {blue, green, yellow, pink} • Có thể sử dụng phép toán lai ghép 1 điểm hoặc N điểm

4/27/2017

Lai ghép theo công thức đơn

Lai ghép toàn bộ theo công thức

• Bố mẹ: x1,…,xn  và y1,…,yn • Lấy ngẫu nhiên 1 NST k. Sau điểm này, các giá trị là

...,

)

...,

)





1( 









1( 





x 1





) ya 

• Hay dùng • Bố mẹ: x1,…,xn  và y1,…,yn • Con 1:

Biểu diễn phép hoán vị: VD bài toán TSP

• Con thứ 2 ngược lại • VD:  = 0.5 • Con thứ 2 ngược lại • VD:  = 0.5

Biểu diễn phép hoán vị

• Bài toán:

• Có n thành phố • Tìm hành trình với độ dài ngắn

nhất

• Các thành phố 1,2, … , n • 1 đường đi hoàn chỉnh là 1 phép

hoán vị (vd n =4 [1,2,3,4], [3,4,2,1] )

• Không gian tìm kiếm lớn :

30 thành phố  30!  1032 hành trình

• Bài toán sắp thứ tự • VD: thuật toán sắp xếp: các thành phàn quan trọng được xếp trước • VD bài toán người du lịch - Travelling Salesman Problem • Mã hóa: (TSP) :

4/27/2017

Phép đột biến cho hoán vị

Đột biến kiểu chèn

• Các phép đột biến thông thường đem lại giải

pháp vi phạm điều kiện bài toán

• Lấy ngẫu nhiên 2 NST • Chuyển NST thứ 2 theo sau cái thứ 1, dịch

phần còn lại sang phải

• Cần thay đổi ít nhất 2 biến • Tham số cho đột biến phản ánh xác suất 1 số thao tác được áp dụng cho toàn xâu, thay vì cho 1 vị trí

• Phép đột biến này giữ lại hầu hết trật tự các NST và thông tin về sự liền kề của chúng

Đột biến kiểu đảo

Đột biến kiểu trộn

• Lấy ngẫu nhiên 2 NST và đổi chỗ của

• Lấy ngẫu nhiên 2 NST và đổi chỗ các NST

chúng

nằm giữa chúng

• Giữ lại được hầu hết thông tin về sự liền kề

của chúng, phá vỡ trật tự nhiều hơn

• Giữ lại được hầu hết thông tin về sự liền kề của chúng, nhưng phá vỡ trật tự các NST

4/27/2017

Phép lai ghép cho chuỗi hoán vị

Đột biến kiểu ngẫu nhiên

• Phép lai ghép thông thường dẫn đến kết quả

vi phạm ràng buộc của hoán vị

• Lấy ngẫu nhiên 1 tập con các NST • Sắp xếp lại 1 cách ngẫu nhiên các NST đó

1 2 3 4 5 1 2 3 2 1

(các tập con không nhất thiết phải liên tục)

• Các giải pháp đề xuất tập trung vào trật tự khi kết hợp và thông tin về tính liền kề từ các cặp bố mẹ

5 4 3 2 1 5 4 3 4 5

Lai ghép 1 điểm

Ví dụ về lai ghép 1 điểm

1 4| 5 9 3| 2 7 8 6 2 5| 7 8 9| 1 6 3 4

• Lấy ngẫu nhiên 1 tập con từ cha thứ 1 • Ý tưởng: giữ nguyên trật tự của các phần tử • Thủ tục:

1. Chọn ngẫu nhiên 1 phần từ cha thứ 1 2. Chép nó sang con thứ 1 3. Chép các số còn lại sang con thứ 1 theo quy tắc sau:

• Chép phần còn lại từ cha thứ 2 theo trật tự 1,9,3,8,2 • Bắt đầu từ điểm cắt của phần sao chép • Sử dụng trật tự của cha thứ 2 • Đến đuôi thì quay vòng lại từ đầu 4. Làm tương tự với con thứ 2

4/27/2017

Lai ghép đối sánh một phần

Ví dụ

9 6| 1 2 5| 7 8 4 3 2 5| 7 8 9| 1 6 3 4

• Step 1

Lai ghép P1 và P2: 1. Chọn ngẫu nhiên 1 phần trong P1 và chép nó sang con thứ 1. 2. Bắt đầu từ điểm cắt đầu tiên, tìm các phần tử trong phần tương ứng

của P2 chưa được chép

3. Với mỗi phần tử i trong các phần tử đó, tìm phần tử j trong con đã

• Step 2

chiếm vị trí của nó

4. Đặt i vào vị trí của j trong P2, vì ta biết rằng sẽ không đặt j vào đó

(do j đã có trong xâu con rồi)

5. Nếu vị trí chiếm bởi j trong P2 đã bị chiếm trong xâu con bởi k, đặt

i vào vị trí của k trong P2

• Step 3

6. Sau khi đã xử lý hết các phần tử trong mảnh đã lai ghép, phần còn

lại được điền theo P2

Con thứ 2 được sinh ra tương tự.

Lai ghép chu trình

1 4 5 9 3 2 7 8 6 2 5 7 8 9 1 6 3 4

Lai ghép chu trình

• Bước 1: xác định các chu trình

Ý tưởng: Mỗi gen đến từ 1 cha kết hợp với vị trí của nó. Thủ tục: 1. Tạo 1 chu trình các gen từ P1 theo cách sau:

(a) Bắt đầu với gen thứ 1 của P1 (b) Tìm gen ở cùng vị trí trong P2 (c) Tìm vị trí chứa cùng gen đó trong P1 (d) Thêm gen đó vào chu trình (e) Lặp lại bước b đến d đến khi gặp lại gen đầu tiên của P1.

• Bước 2: chép chu trình khác vào con

2. Đặt các gen của chu trình trong con thứ 1 vào các vị trí nó có trong cha thứ 1 3. Thực hiện chu trình tiếp theo từ cha thứ 2

4/27/2017

Kết hợp cạnh

1 4 5 9 3 2 7 8 6 2 5 7 8 9 1 6 3 4

1. Lấy ngẫu nhiên 1 phần tử, đưa vào offspring 2. Đặt current element = entry 3. Loại tất cả các phần tử nối với phần tử hiện tại khỏi bảng 4. Kiểm tra danh sách của phần tử hiện tại:

– Nếu có cạnh chung, lấy phần tử đó làm phần tử tiếp theo – Nếu không, lấy phần tử trong danh sách mà bản thân nó có danh sách cạnh nối

ít nhất

– Các trường hợp còn lại: lấy ngẫu nhiên

5. Khi gặp danh sách rỗng:

– Mở rộng đầu kia của offspring – Nếu không chọn ngẫu nhiên 1 phần tử mới

• Xây dựng bảng liệt kê các cạnh xuất hiện trong 2 cha, nếu Sau khi xây dựng bảng, thực hiện các bước sau: 1 cạnh xuất hiện ở cả 2, đánh dấu bằng dấu + • vd. [1 2 3 4 5 6 7 8 9] và [9 3 7 8 2 6 5 1 4]