Chương 1 TỔNG QUAN VỀ GIẢI THUẬT DI TRUYỀN (Genetic Algorithm - GA) 1. CÁC GIẢI THUẬT TÍNH TOÁN TIẾN HÓA-GIẢI THUẬT DI TRUYỀN 1. Giải thuật di truyền ( GA – Genetic Algorithm) là giải thuật tìm kiếm, chọn lựa các giải pháp tối ƣu để giải quyết các bài toán thực tế khác nhau, dựa trên cơ chế chọn lọc của tự nhiên: Từ tập lời giải ban đầu, thông qua nhiều bƣớc tiến hóa, hình thành tập lời giải mới phù hợp hơn, và cuối cùng dẫn đến lời giải tối ƣu toàn cục. Trong tự nhiên, mỗi cá thể muốn tồn tại và phát triển phải thích nghi với môi trƣờng, cá thể nào thích nghi hơn thì tồn tại, cá thể nào kém thích nghi thì bị tiêu diệt.
Trong mỗi cá thể, các gen liên kết với nhau theo cấu trúc dạng chuỗi, gọi là nhiễm sắc thể (NST). Mỗi NST đặc trƣng cho mỗi loài và quyết định sự sống còn của cá thể đó. Do môi trƣờng tự nhiên luôn biến đổi nên cấu trúc NST cũng thay đổi để thích nghi với môi trƣờng và thế hệ sau luôn thích nghi hơn thế hệ trƣớc. Cấu trúc này có đƣợc do sự trao đổi thông tin có tính ngẫu nhiên với môi trƣờng bên ngoài hoặc giữa các NST với nhau.
Từ ý tƣởng đó, các nhà khoa học đã nghiên cứu và xây dựng nên giải thuật di truyền dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hóa. Giải thuật di truyền sử dụng các thuật ngữ đƣợc lấy từ di truyền học nhƣ: lai ghép, đột biến, NST, cá thể,… Ở đây mỗi cá thể đƣợc đặc trƣng bởi một tập nhiễm sắc thể, nhƣng để đơn giản khi trình bày, ta xét trƣờng hợp tế bào mỗi cá thể chỉ một NST. Các NST đƣợc chia nhỏ thành các gen đƣợc sắp xếp theo một dãy tuyến tính. Mỗi cá thể (hay NST) biểu diễn một lời giải có thể của bài toán.
Một xử lý tiến hóa duyệt trên tập các NST tƣơng đƣơng với việc tìm kiếm lời giải trong không gian lời giải của bài toán. Quá trình tìm kiếm phải đạt đƣợc hai mục tiêu: Khai thác lời giải tốt nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn 12 Xem xét trên toàn bộ không gian tìm kiếm. Giải thuật di truyền có thể mô tả vắn tắt nhƣ sau: Proceduce Giải_thuật_di_truyền; Begin t:=0; Khởi tạo ngẫu nhiên quần thể P(t); Đánh giá độ phù hợp từng cá thể trong P(t); Repeat t:= t + 1; Chọn các cá thể từ P(t – 1); Lai tạo các cá thể đã chọn tạo ra P(t) mới; Đột biến các cá thể trong P(t) theo xác suất Pm; Đánh giá độ phù hợp các cá thể trong tạp P(t); Until (thỏa mãn điều kiện dừng); End; Giải thích: Tại lần lặp thứ t, GA xác định một tập hợp các lời giải có thể (các cá thể hay NST) gọi là quần thể P t x1t , x2t ,.
Mỗi lời giải xit đƣợc đánh giá nhằm xác định độ phù hợp của nó. Sau đó, một tập hợp các lời giải đƣợc hình thành nhờ sự lựa chọn các lời giải phù hợp hơn. Một số phần tử của tập hợp này đƣợc tái xuất thông qua lai ghép và đột biến. Từ đó hình thành quần thể mới P(t + 1) với hy vọng chứa các cá thể phù hợp hơn quần thể trƣớc đó.
Toán tử “lai ghép” kết hợp các đặc trƣng của hai NST cha và mẹ hình thành hai NST con tƣơng ứng chẳng hạn bằng cách hoán vị các đoạn thích hợp của hai NST cha và mẹ. Ví dụ, nếu cặp nhiễm sắc thể cha mẹ đƣợc biểu diễn dƣới dạng hai véctơ: a1 , b1 , c1 , d1 , e1 ; a2 , b2 , c2 , d 2 , e2 thì cặp véctơ con cháu nhận đƣợc sau khi lai ghép có thể là: a1 , b1 , c1 , d 2 , e2 ; a2 , b2 , c2 , d1 , e1 . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn 13 Toán tử “đột biến” thay đổi một hay một số gen của NST đƣợc chọn theo quy tắc thay đổi ngẫu nhiên với xác suất bằng tỷ lệ đột biến. Nhƣ vậy, bản chất GA là một giải thuật lặp, nhằm giải quyết các bài toán tìm kiếm dựa trên cơ chế chọn lọc nhân tạo và sự tiến hóa của các gen.
Trong quá trình đó, sự sống còn của cá thể phụ thuộc vào hoạt động của các NST và quá trình chọn lọc (tham gia vào việc tái tạo ra các chuỗi NST mới bằng cách giải mã các chuỗi NST và tạo ra mối liên kết giữa các NST trong các cá thể khác nhau). GA sử dụng các toán tử: chọn lọc, lai ghép, đột biến trên các NST để tạo ra chuỗi mới. Những toán tử này thực chất là việc sao chép chuỗi, hoán vị các chuỗi con và sinh số ngẫu nhiên. Cơ chế của GA đơn giản nhƣng lại có sức mạnh hơn các giải thuật thông thƣờng khác nhờ có sự đánh giá và chọn lọc sau mỗi bƣớc thực hiện.
Do vậy, khả năng tiến gần đến lời giải tối ƣu của GA sẽ nhanh hơn nhiều so với các giải thuật khác. Có thể nói GA khác với những giải thuật tối ƣu thông thƣờng ở những đặc điểm sau: GA làm việc với tập mã của biến chứ không phải bản thân biến. GA thực hiện tìm kiếm trên một quần thể các cá thể chứ không phải trên một điểm nên giảm bớt khả năng kết thúc tại một điểm tối ƣu cục bộ mà không tìm thấy tối ƣu toàn cục. GA chỉ cần sử dụng thông tin của hàm mục tiêu để phục vụ tìm kiếm chứ không đòi hỏi các thông tin hỗ trợ khác.
Các thao tác cơ bản trong giải thuật dựa trên khả năng tích hợp ngẫu nhiên, mang tính xác suất chứ không tiềm định. Giải thuật di truyền kinh điển. Mô tả giải thuật Giải thuật di truyền kinh điển sử dụng mã hóa nhị phân, mỗi cá thể đƣợc mã hóa là một chuỗi nhị phân có chiều dài cố định. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.
Mã hóa – Biểu diễn các biến bằng véctơ nhị phân. Ta sử dụng véctơ nhị phân có độ dài L nhƣ một NST để biểu diễn giá trị thực của biến x lx ; ux . Độ dài L của NST phụ thuộc vào yêu cầu cụ thể của bài toán. Một bit mã hóa x ứng với một giá trị trong khoảng 0; 2 L sẽ đƣợc ánh xạ lên giá trị thực thuộc miền lx ; ux .
Nhờ đó, ta có thể kiểm soát miền giá trị của các biến và tính chính xác của chúng. Tỷ lệ co giãn của ánh xạ đƣợc tính nhƣ sau: Giá trị x tƣơng ứng với chuỗi NST nhị phân là: x lx decimal NST * g. Trong đó, decimal NST là giá trị thập phân của chuỗi NST nhị phân và u x lx g. 2L Chẳng hạn, ta muốn tìm cực tiểu của 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 và f x1 ,., xk 0 xi Di . Ta muốn tối ƣu hóa hàm f với độ chính xác cho trƣớc là 6 số lẻ đối với giá trị của các biến. Rõ ràng là để đạt đƣợc độ chính xác nhƣ vậy mỗi miền Di đƣợc phân cắt thành bi ai *106 miền con bằng nhau. Gọi mi là số nguyên nhỏ nhất sao cho: b a *10 2 1.
i i 6 m 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 thỏa mãn điều kiện về độ chính xác 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ến xi : b a xi ai decimal 1100. 2 1 Trong đó, decimal(chuỗi2) cho biết giá trị thập phân của chuỗi nhị phân đó.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn 15 Bây giờ, mỗi NST (là một lời giải) đƣợc biễu diễn bằng chuỗi nhị phân có k chiều dài L mi. Trong đó, mi bit đầu tiên biểu diễn các giá trị trong miền i 1 a ; b ;…; m bit cuối cùng biểu diễn các giá trị trong miền a ; b . i i k k k Để khởi tạo quần thể, chỉ cần đơn giản tạo pop – size (kích cỡ quần thể) nhiễm sắc thể ngẫu nhiên theo từng bit. Phần còn lại của thuật giải di truyền rất đơn giản: Trong mỗi thế hệ, ta lƣợng giá từng NST (tính giá trị của 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 thỏa 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, NST 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 thuật giải di truyền sau một số bƣớc lặp cố định tùy thuộc vào điều kiện về tốc độ về tài nguyên máy tính. Toán tử chọn lọc. a) Sử dụng bánh xe Roulette.
Có nhiều cách để thực hiện toán tử chọn lọc, nói chung đều theo tƣ tƣởng cá thể có độ thích nghi cao hơn thì khả năng đƣợc chọn nhiều hơn. Nhƣng có lẽ đơn giản và hiệu quả nhất là sử dụng bánh xe Roulette (roulette wheet), mỗi cá thể trong quần thể chiếm một khe có độ rộng tỷ lệ thuận với giá trị phù hợp. Độ rộng của khe đƣợc tính bằng tỷ lệ phần trăm giá trị phù hợp của một cá thể trên tổng giá trị phù hợp của toàn quần thể. Gọi f i là độ phù hợp của cá thể thứ i trong quần thể gồm N cá thể.
Khi đó, cá f thể i sẽ đƣợc chọn với xác suất pi N i. Trên vòng tròn Roulette, mỗi chuỗi fi i 1 trong quần thể chiếm một khe có độ rộng tỷ lệ với độ phù hợp của chuỗi. Độ rộng của khe đƣợc tính theo tỷ lệ phần trăm độ phù hợp của chuỗi với tổng độ phù hợp của toàn quần thể là 100%. Các bƣớc tiến hành thủ tục quay Roulette: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn 16 - Đánh số các cá thể trong quần thể.