EVOLUTION ALGORITHM (EA)
Lê Phi Trường Nguyễn Đức Tú Nguyễn Tôn Thất Tú
Nguyễn Quốc Tuấn Nguyễn Ngọc Tuyên Đặng Minh Úc
Dương Hoàng Việt Mai Quốc Việt
1
NỘI DUNG TRÌNH BÀY

Đặt bài toán

Lược đồ tổng quát của EA

Các nguyên lý cơ bản trong EA

Biểu diễn gen (Cấu trúc dữ liệu)

Lựa chọn độ fitness (Độ đo sự thích nghi)

Các quy tắc chọn lọc

Các quy tắc lai ghép

Các quy tắc đột biến
2
GIẢI THUẬT TIẾN HÓA

Thuật toán tiến hóa dựa trên lý thuyết tiến hóa của Darwin bằng cách mô
phỏng các quá trình tiến hóa và cơ chế sinh học để giải quyết vấn đề.

Thuật toán thông qua sinh sản, đột biến, lựa chọn để giải quyết vấn đề tối
ưu hóa.
3

chính xác đến 6 số lẻ tức có nghĩa, ta cần có 3 x 106 khoảng có kích thước bằng
nhau.

Ta cần 22 bit để biểu diễn cho một nhiễm sắc thể

2097152 = 221 < 3 x 106 < 222 = 4194304

Chuyển đổi từ chuỗi nhị phân <<b21b20…b0>> thành số thực:

với

Đây cũng chính là hàm định giá


7
ĐẶT BÀI TOÁN

Khởi tạo quần thể:

Ta tạo một quần thể các nhiễm sắc thể, trong đó mỗi
nhiễm sắc thể là một vectơ nhị phân 22 bit, tất cả 22 bit
của mỗi nhiểm sắc thể đều được khởi tạo ngẫu nhiên.

Hàm lượng giá: là hàm f(x)

Đột biến và lai:

Đột biến:

Lai ghép:

10
LƯỢC ĐỒ THUẬT TOÁN
BẮT ĐẦU
PHÁT SINH QUẦN
THỂ BAN ĐẦU
XÁC ĐỊNH ĐỘ THÍCH
NGHI CỦA CÁ THỂ
TRONG QUẦN THỂ
CÓ CÁ THỂ NÀO ĐẠT ĐẾN
LỜI GIẢI TỐI ƯU CHƯA?
TRÌNH BÀY
LỜI GIẢI
CHỌN LỌC
LAI GHÉP
XÂY DỰNG
QUẦN THỂ MỚI
ĐỘT BIẾN
Yes
No
11
LƯỢC ĐỒ THUẬT TOÁN

Bước 1: Khởi tạo một quẩn thể ban đầu (các đáp án ban đầu của bài toán).

Bước 2: Xác định giá trị hàm mục tiêu (fitness) cho mỗi cá thể trong quần thể.

Bước 3: Tạo ra quần thể mới bằng cách lai ghép chéo (crossover) từ các cá thể hiện tại có chọn lọc
(selection), đồng thời tạo ra các đột biến (mutation) trong quần thể mới theo một xác xuất nhất định.

Bước 4. Các cá thể trong quần thể mới sinh ra được thay thế cho các cá thể trong quần thể cũ

Khó khăn trong chọn lọc:

Vấn đề hội tụ sớm

Nguyên nhân:

Áp lực chọn lọc

Tính đa dạng của quần thể

Giải pháp:

Nghiên cứu về cơ chế tạo mẫu

Nghiên cứu về bản chất hàm mục tiêu
15
PHƯƠNG PHÁP TẠO MẪU
16
TRUNCATION SELECTION

Đặc tính:

Là phương pháp đơn giản nhất

Dùng đối với quần thể cá thể lớn

Mã Giả:
TRS_code{
1. Sếp theo thứ tự giảm dần theo độ thích nghi các phần tử trong P(t)
2. Chọn p phần trăm các phần tử được giữ lại (trong khoảng 10% -50%)

19
LINEAR RANK SELECTION

Với P(i) =

Rank(i) được sắp xếp theo thứ tự giảm dần của độ thích nghi của cá thể, thích nghi tốt nhất rank(x) = n, thích nghi tồi nhất
rank(k)=1

LRS_code{

Xếp hạng các cá thể trong quần thể theo sự giảm của giá trị thích nghi, giá trị rank(worst) =n, rank(best) =1 (n = pop_size)

S(0) =0; p(i) = ; với a chọn thỏa dk: 1≤ a ≤ 2 và b = 2-a

For i =0 to n do {
S(i) = S(i-1)p(i) ;
}
-
For j = 0 to k do { // k là số cá thể cần chọn sau mỗi phép chọn
r = random(0, S(n))
chọn cái thể i sao cho S(i-1) <= r <= S(i);
j++;
}
}


20
EXPONENTIAL RANK SELECTION
21
TOURAMENT SELECTION

được quyết định bởi thêm vào một chuỗi mặt nạ lai ghép.
24
LAI GHÉP
25