Tối ưu hóa một biến

Tổng số bài gửi : 9 Registration date : 19/05/2007

Trích dẫn từ: "Trí tuệ nhân tạo - Lập trình tiến hoá" do TS Nguyễn Đình Thúc chủ biên

1.1.Tối ưu hàm một biến

Xét bài toán tối ưu không ràng buộc sau:
Max F(x)=x*sin(10pi*x)+1.0 ; x thuộc [-1;2]
Bài toán có nghĩa là tìm x trong đoạn [-1;2] để f có gía trị lớn nhất, nghĩa là tìm x0 sao cho:
F(x0)>=f(x) với mọi x thuộc [-1;2]
Khi đạo hàm bậc nhất bằng 0, nghĩa là
F'(x)=sin(10pi*x)+10pi*x*cos(10pi*x)=0
<=>tang(10pi*x)=-10pi*x
Rõ ràng là phương trình trên có vô số lời giải
Xi=(2i-1)/20+ei ,i=1,2,...
Xi=0
Xi=(2i+1)/20-ei ,i=1,2,...
Trong đó các số hạng ei là các dãy số thực giảm (i=1,2,..., và i= -1,-2, ...) dần về 0
Cũng chú ý rằng hàm f đạt đến cực đại (cục bộ) tại điểm xi, khi i là số nguyên lẻ. và đạt đến cực tiểu của nó tại xi, khi i chẵn (có hình trong sách)
Vì miền giá trị củaq bài toán là [-1;2], hàm đạt cực đại tại x19=37/20+e19 = 1.85 + e19, ở đây f(x19) hơi lớn hơn f(1.85)=1.85*sin(18pi+pi/2)+1.0=2.85
Bây giờ ta dùng thuật giải di truyền để giải bài toán nói trên, nghĩa là tìm 1 điểm trong đoạn [-1;2] sao cho tại đó f có giá trị lớn nhất
Ta sẽ lần lượt bàn về 5 thành phần chính của thuật giải di truyền giải bài toán này.

1.1.1.Biểu diễn

Ta sử dụng 1 vecto nhị phân làm nhiễm sắc thể để biểu diễn các giá trị thực của biến x. Chiều dài của vecto phụ thuộc vào độ chính xác cần có, trong ví dụ này, ta tính chính xác đến 6 số lẻ.
Miền giá trị của x có thể có chiều dài 2-(-1)=3; với yêu cầu về độ chính xác 6 số lẻ như thế phải chia đoạn [-1;2] thành ít nhất 3*10^6 hoảng có kích thước bằng nhau. Điều này có nghĩa là cần có 22 bit cho vecto nhị phân (nhiễm sắc thể):
Ánh xạ biến chuỗi nhị phân (b21b20...b0) thành số thực x trong đoạn [-1;2] được thực hiện qua 2 bước sau:
+ đổi chuỗi nhị phân (b21b20...b0) từ cơ số 2 sang cơ số 10:
(<b21b20...b0>)=b0*2^0+....+b21*2^21=x'
+ tìm số thực x tương ứng
x=-1+x'*3/(2^22-1)
với -1 là cận dưới của miền giá trị và 3 là chiều dài của miền
Ví dụ, nhiễm sắc thể (1000101110110101000111) biểu diễn số 0.637197 vì
X'=(1000101110110101000111)=2288967
Và x=1.0+2288967*3/4194303=0.637197
Đương nhiên nhiễm sắc thể
(000000000000000000000) và (1111111111111111111111) biểu diễn các cận của các miền, -1 và 2 cho mỗi cận

1.1.2.Khởi động tạo quần thể

Tiến trình khởi tạo rất đơn giản: Ta tạo 1 quần thể các nhiễm sắc thể trong đó mỗi nhiễm sắc thể là 1 vecto nhị phân 22 bit, tất cả 22 bit của mỗi nhiễm sắc thể đều được tạo ngẫu nhiên.

1.1.3.Hàm lượng giá

Hàm lượng giá eval của các vecto nhị phân v chính là hàm f:
Eval(v)=f(x)
Trong đó, nhiễm sắc thể v biểu diễn giá trị thực x như đã nói ở trên, hàm lượng giá đóng vai trò môi trường, đánh giá từng lời giải theo độ thích nghi của chúng. Ví dụ, 3 nhiễm sắc thể:
V1=(1000101110110101000111),
V2=(0000001110000000010000),
V3=(1110000000111111000101)
Tương ứng với các giá trị x1=0.637197, x2=-0.958973, và x3=1.627888. Và có độ thích nghi tương ứng:
Eval(x1)=f(x1)=1.586345
Eval(x2)=f(x2)=0.078878
Eval(x3)=f(x3)=2.250650
Rõ ràng, nhiễm sắc thể v3 là tốt nhất trong 3 nhiễm sắc thể này vì hàm lượng giá nó trả về giá trị cao nhất

1.1.4.Các phép toán di truyền

Trong giai đoạn tiến hoá quần thể, ta có thể dùng 2 phép toán di truyền cổ điển: đột biến và lai
Như đã trình bày ở trên, đột biến làm thay đổi 1 (số) gen (các vị trí trong 1 nhiễm sắc thể) với xác xuất bằng tốc độ đột biến. Giả định rằng gen thứ 5 trong nhiễm sắc thể v3 được chọn để đột biến. Và đột biến này chính là thay đổi giá trị gen này: 0 thành 1 và 1 thành 0. Như vậy sau đột biến v3 sẽ là:
V'3=(1110100000111111000101)
nhiễm sắc thể này biểu diễn giá trị x'3=1.721638 và f(x'3)=0.082257. Điều này có nghĩa là đột biến cụ thể làm giảm khá nhiều giá trị của nhiễm sắc thể v3. Bây giờ, nếu gen thứ 10 được chọn để đột biến nhiễm sắc thể v3 thì
v'"3=(1110000001111111000101)
giá trị tương ứng x"3=1.630818 và f(x"3)=2.343555, khá hơn giá trị f(x3)=2.250650
ta sẽ minh hoạ phép lai trên các nhiễm sắc thể v2 và v3. Giả định điểm lai được chọn (ngẫu nhiên) ở vị trí thứ 6:
v2=(00000|01110000000010000)
v3=(11100|00000111111000101)
v'2=(00000|00000111111000101)
v'3=(11100|01110000000010000)
các con này có độ thích nghi:
f(v'2)=f(-0.998113)=0.940965
f(v'3)=f(1.666028)=2.459245
chú ý rằng con thứ 2 thích nghi hơn cả cha lẫn mẹ nó

1.1.5.Các tham số

Đối với bài toán đặt biệt này, ta dùng các tham số sau đây: kích thước quần thề pop-size=50, xác xuất lai Pc=0.25 nghĩa là cá thể v trong quần thể có 25% cơ hội được chọn để thực hiện phép lai; còn xác xuất đột biến Pm=0.01 lại là 1% 1 bit bất kì của 1 các thể bất kì trong quần thể bị đột biến.

1.1.6.Các kết quả thử nghiệm

Bảng dưới đây trình bày 1 số kết quả hàm mục tiêu f ở 1 số thế hệ. Cột bên trái cho biết thế hệ được xem xét, và cột bân phải cho biết giá trị hàm f. Nhiễm sắc thể tốt nhất sau 150 thế hệ là
Vmax=(111001101000100000101) tương ứng với giá trị xmax=1.850773
Đúng như chúng ta mong đợi, xmax=1.85+ e và f(xmax) lớn hơn 2.85 1 chút.
Kết quả 150 thế hệ
Thế hệ thứ hàm lượng giá
1 1.441942
6 2.250003
8 2.250283
9 2.250284
10 2.250363
12 2.329077
39 2.344251
40 2.345087
51 2.738930
99 2.849246
137 2.850217
145 2.850227

Ngày mai chẳng biết ra sao nữa

Mà có ra sao cũng chẳng sao

Chúc mọi người học tốt!

Tổng số bài gửi : 4 Registration date : 16/05/2007

Ban oi, TS. Ng Dinh Thuc la ai the ban???

Tổng số bài gửi : 76 Registration date : 24/04/2007

Chắc ông viết nhầm tiến sĩ nguyên đình thuân áy mà! lol!