chương 1. Trong phần này chúng ta sẽ tìm hiểu sâu hơn về giải thuật di truyền này thông qua một bài toán tối ưu số [4]. Không làm mất tính tổng quát, ta giả định bài toán tối ưu là bài toán tìm cực đại của hàm nhiều biến f. Bài toán tìm cực tiểu hàm g chính là bài toán tìm cực đại hàm f = -g, hơn nữa ta có thể giả định hàm mục tiêu f có giá trị dương trên miền xác định của nó, nếu không ta có thể cộng thêm một hằng số C dương Cụ thể bài toán được đặt ra như sau: Tìm cực đại một hàm k biến f(x1,.
Giả sử thêm là mỗi biến xi có thể nhận giá trị trong miền Di = [ai,bi] R và f(x1,., xk) 0 với mọi xi Di. Ta muốn tối ưu hàm f với độ chính xác cho trước: giả sử cần n số lẻ đối với giá trị của các biến Để đạt được độ chính xác như vậy mỗi miền Di cần được phân cắt thành (bi - ai) 10n miền con bằng nhau, gọi m là số nguyên nhỏ nhất sao cho (bi a i ) 10 n 2 mi 1 Như vậy mỗi biến xi được biểu diễn bằng một chuỗi nhị phân có chiều dài mi. Biểu diễn như trên rõ ràng thoả mãn điều kiện về độ chính xác theo yêu cầu. Công thức sau tính giá trị thập phân của mỗi chuỗi nhị phân biểu diễn bi a i biến xi xi ai decimal( string 2 ) 2 mi 1 (1.1) Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.vn/ 12 Trong đó hàm decimal(string2) cho biết giá trị thập phân của chuỗi nhị phân đó.
Bây giờ, mỗi nhiễm sắc thể (là một lời giải) được biểu diễn bằng một k chuỗi nhị phân có chiều dài m i 1 mi , m1 bit đầu tiên biểu diễn giá trị trong khoảng [a1,b1], m2 bit kế tiếp biểu diễn giá trị trong khoảng [a2,b2], … Để khởi tạo quần thể, chỉ cần đơn giản tạo pop_size nhiễm sắc thể ngẫu nhiên theo từng bit Phần còn lại của giải thuật di truyền rất đơn giản, trong mỗi thế hệ, ta lượng giá từng nhiễm sắc thể (tính giá trị hàm f trên các chuỗi biến nhị phân đã được giải mã), chọn quần thể mới thoả mãn phân bố xác suất dựa trên độ thích nghi và thực hiện các phép đột biến và lai để tạo ra các cá thể thế hệ mới. Sau một số thế hệ, khi không còn cải thiện thêm được gì nữa, nhiễm sắc thể tốt nhất sẽ được xem như lời giải của bài toán tối ưu (thường là toàn cục). Thông thường ta cho dừng giải thuật sau một số bước lặp cố định tuỳ ý tuỳ thuộc vào điều kiện tốc độ và tài nguyên máy tính. Đối với tiến trình chọn lọc (chọn quần thể mới thoả phân bố xác suất dựa trên các độ thích nghi), ta dùng bánh xe quay Rulet với các rãnh được định kích thước theo độ thích nghi.
Ta xây dựng bánh xe Rulet như sau (giả định rằng các độ thích nghi đều dương) + Tính độ thích nghi eval(vi) của mỗi nhiễm sắc thể vi (i = 1,…, pop_size) pop size + Tìm tổng giá trị thích nghi toàn quần thể: F i 1 eval(vi ) (1.2) + Tính xác suất chọn pi cho mỗi nhiễm sắc thể vi, (i = 1,…, pop_size): pi eval (v i ) / F (1.3) Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.vn/ 13 + Tính vị trí xác suất qi của mỗi nhiễm sắc thể vi, (i = 1,…, pop_size): i qi j 1 pi (1.4) Tiến trình chọn lọc thực hiện bằng cách quan bánh xe Rulet pop_size lần, mỗi lần chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới theo cách sau: + Phát sinh ngẫu nhiên một số r trong khoảng [0.1] + Nếu r q1 thì chọn nhiễm sắc thể đầu tiên v1, ngược lại thì chọn nhiễm sắc thể thứ i, vi (2 i pop_size) sao cho qi-1 r qi Như vậy có thể có một số nhiễm sắc thể được chọn nhiều lần, điều này là phù hợp vì các nhiếm sắc thể tốt nhất cần có nhiều bản sao hơn, các nhiễm sắc thể trung bình không thay đổi, các nhiễm sắc thể kém nhất thì chết đi. Minh họa bánh xe rulet Bây giờ ta có thể áp dụng phép toán di truyền: kết hợp và lai ghép các cá thể trong quần thể vừa được chọn từ quần thể cũ như trên. Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.vn/ 14 Một trong những tham số của giải thuật là xác suất lai pc. Xác suất này cho ta số nhiếm sắc thể pop_size pc mong đợi, các nhiễm sắc thể này được dùng trong tác vụ lai tạo.
Ta tiến hành theo cách sau đây: Đối với mỗi nhiễm sắc thể trong quần thể mới: + Phát sinh ngẫu nhiên một số r trong khoảng [0,1] + Nếu r pc, hãy chọn nhiễm sắc thể đó để lai tạo Bây giờ ta ghép đôi các nhiễm sắc thể đã được chọn một cách ngẫu nhiên: đối với mỗi cặp nhiễm sắc thể được ghép đôi, ta phát sinh ngẫu nhiên một số nguyên pos trong khoảng [1, m-1] (m là tổng chiều dài - số bit - của một nhiễm sắc thể). Số pos cho biết vị trí của điểm lai. Hai nhiễm sắc thể: (b1b2…bposbpos+1…bm) và (c1c2.…cposcpos+1…cm) được thay bằng một cặp con của chúng: (b1b2…bposcpos+1…cm) và (c1c2.…cposbpos+1…bm) Phép toán kế tiếp là phép đột biến, được thực hiện trên cơ sở từng bit. Một tham số khác của giải thuật là xác suất đột biến pm, cho ta số bit đột biến pm m pop_size mong đợi.
Mỗi bit (trong tất cả các nhiễm sắc thể trong quần thể) có cơ hội bị đột biến như nhau, nghĩa là đổi từ 0 thành 1 hoặc ngược lại. Vì thế ta tiến hành theo cách sau đây: Đối với mỗi nhiễm sắc thể trong quần thể hiện hành (nghĩa là sau khi lai) và đối với mỗi bit trong nhiễm sắc thể: + Phát sinh ngẫu nhiên một số r trong khoảng [0,1] + Nếu r<pm hãy đột biến bit đó Sau quá trình chọn lọc, lai và đột biến, quần thể mới đến lượt lượng giá kế tiếp của nó. Lượng giá này được dùng để xây dựng phân bố xác suất (cho Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.vn/ 15 tiến trình chọn lựa kế tiếp), nghĩa là để xây dựng lại bánh xe Rulet với các rãnh được định kích thước theo các giá trị thích nghi hiện hành. Phần còn lại của tiến hoá chỉ là lặp lại chu trình của những bước trên Toàn bộ tiến trình sẽ được minh hoạ trong một ví dụ cực đại hoá hàm: f ( x1 , x 2 ) 21 .5 x1 sin(4 x1 ) x 2 sin(20 x 2 ) Giả sử kích thước quần thể pop_size = 20, các xác suất di truyền tương ứng là Pc = 0.01 Giả sử cần tính chính xác đến 4 số lẻ đối với mỗi biến.
Miền của biến x1 có chiều dài 15.1, điều kiện chính xác đòi hỏi đoạn [-3.1] cần được chia thành các khoảng có kích thước bằng nhau, ít nhất là 15.1 10000 khoảng, điều này cần 18 bit làm phần đâu tiên của nhiễm sắc thể: 2 17 151000 218 Miền của biến x2 có chiều dài là 1.7, điều kiện chính xác đòi hỏi đoạn [4.8] cần được chia thành các khoảng có kích thước bằng nhau là 1.7 10000 khoảng, điều này nghĩa là cần 15 bit làm thành phần cuối của nhiễm sắc thể: 214 17000 215 Chiều dài toàn bộ nhiễm sắc thể (vectơ lời giải) là m =18+15 = 33 Để cực đại hoá hàm f bằng giải thuật di truyền ta tạo ra một quần thể có pop_size = 20 nhiễm sắc thể. Cả 33 bit trong tất cả các nhiễm sắc thể đều được khởi tạo ngẫu nhiên Giả sử sau tiến trình khởi tạo ta có quần thể sau đây: v1 = (100110100000001111111010011011111) v2 = (111000100100110111001010100011010) v3 = (000010000011001000001010111011101) v4 = (100011000101101001111000001110010) Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.406725 Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.666916 Rõ ràng nhiễm sắc thể v15 mạnh nhất và nhiễm sắc thể v2 yếu nhất Tiếp theo ta xây dựng bánh xe Rulet cho tiến trình chọn lọc. Tổng độ thích nghi của quần thể là: 20 F i 1 eval(vi ) 387.776822 Xác suất chọn lọc pi của mỗi nhiễm sắc thể vi (i = 1,…,20) là: p1 = eval(v1)/F = 0.067099 Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.035244 Các vị trí xác suất qi của mỗi nhiễm sắc thể vi (i = 1,.181890 Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.000000 Tiếp theo ta quanh bánh xe Rulet 20 lần, mỗi lần chọn một nhiễm sắc thể cho quần thể mới. Giả sử thứ tự (ngẫu nhiên) của 20 số trong khoảng [0,1] được phát sinh là: 0.780237 Số đầu tiên r = 0.513870 lớn hơn q10 và nhỏ hơn q11, nghĩa là nhiễm sắc thể v11 được chọn vào quần thể mới, số thứ hai r = 0.175741 lớn hơn q3 nhỏ hơn q4, nghĩa là v4 được chọn cho quần thể mới,….
Như vậy quần thể mới gồm các nhiễm sắc thể sau: v’1 = v11 = (011001111110110101100001101111000) Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www. Xác suất lai ghép Pc = 0.25 vì thế ta hy vọng 25% nhiễm sắc thể sẽ tham gia lai tạo. Ta tiến hành theo cách sau: Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.vn/ 21 + Đối với mỗi nhiễm sắc thể trong quần thể mới ta phát sinh ngẫu nhiên một số r trong khoảng [0,1], + Nếu r 0.25 ta chọn một nhiễm sắc thể cho trước để lai tạo Giả sử thứ tự các số ngẫu nhiên là 0.826927 Điều này có nghĩa là các nhiễm sắc thể v’2, v’11, v’13 và v’18 đã được chọn để lai tạo. Tiếp theo ta cho lai tạo một cách ngẫu nhiên, ví dụ (v’2, v’11) và (v’13, v’18) được kết cặp.
Đối với mỗi cặp trong 2 cặp này, ta phát sinh một số nguyên ngẫu nhiên pos thuộc khoảng {1,. Số pos cho biết vị trí của điểm lai tạo. Cặp nhiễm sắc thể đầu tiên là: v’2 = (100011000|101101001111000001110010) v’11 = (111011101|101110000100011111011110) và giả sử số phát sinh là pos = 9, kết quả lai tạo là: v’’2 = (100011000|101110000100011111011110) v’’11 = (111011101|101101001111000001110010) Cặp nhiễm sắc thể thứ hai là: Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.vn/ 22 v’13 = (00010100001001010100|1010111111011) v’18 = (11101111101000100011|0000001000110) và giả sử số phát sinh là pos = 20, kết quả lai tạo là: v’’13 = (00010100001001010100|0000001000110) v’’18 = (11101111101000100011|1010111111011) Cuối cùng quần thể hiện hành là v’1 = (011001111110110101100001101111000) v’2 = (100011000|101110000100011111011110) v’3 = (001000100000110101111011011111011) v’4 = (011001111110110101100001101111000) v’5 = (000101010011111111110000110001100) v’6 = (100011000101101001111000001110010) v’7 = (111011101101110000100011111011110) v’8 = (000111011001010011010111111000101) v’9 = (011001111110110101100001101111000) v’10 = (000010000011001000001010111011101) v’11 = (111011101|101101001111000001110010) v’12 = (011000000101100010110000001111100) v’13 = (00010100001001010100|0000001000110) v’14 = (100001100001110100010110101100111) v’15 = (101110010110011110011000101111110) v’16 = (100110100000001111111010011011111) Soá hoùa bôûi Trung taâm Hoïc lieäu –ĐHTN http://www.vn/ 23 v’17 = (000001111000110000011010000111011) v’18 = (11101111101000100011|1010111111011) v’19 = (111011101101110000100011111011110) v’20 = (110011110000011111100001101001011) Phép toán kế tiếp, đột biến thực hiện trên cơ sở từng bit một. Xác suất đột biến pm = 0.
