Bài giảng Trí tuệ nhân tạo: Giải thuật di truyền - PGS.TS. Lê Thanh Hương

Bài giảng "Trí tuệ nhân tạo: Giải thuật di truyền" cung cấp cho người học các kiến thức về lịch sử trí tuệ nhân tạo, tiến hóa trong thế giới thực, giải pháp tệ nhất, làm cách nào để mã hóa giải pháp,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Trí tuệ nhân tạo: Giải thuật di truyền - PGS.TS. Lê Thanh Hương4/27/2017Lịch sử••••Giải thuật di truyềnGA đề xuất bởi John Holland năm 1970Phổ biến những năm 1980Dựa trên ý tưởng về luật tiến hóa DarwinDù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ác12Tiế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àumắt)• 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ảnsao• Độ phù hợp (fitness) của 1 cá thể là số con nó có thể sinh ratrướ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Đặt vấn đề•••••Giả sử có 1 vấn đềTa chưa biết cách giảiCó thể làm gì?Sử dụng máy tính để tìm lời giải?Làm thế nào?414/27/2017Giải pháp tệ nhấtCó 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 gianRepeat• Với đa phần các vấn đề - không:Sinh một giải pháp ngẫu nhiênThử 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ốt56Làm cách nào để mã hóa 1 giảiphápÝ tưởng ít tệ hơn (GA)• Phụ thuộc vào vấn đề• GA mã hóa giải pháp như 1 chuỗi cố địnhcác bit (ví dụ 101110, 111111, 000101)• Mỗi bit biểu diễn một số đặc điểm của giảipháp đề xuất• Để có thể sử dụng GA, cần “thử” các chuỗivà cho điểm mức độ “tốt” của giải phápSinh 1 tập các giải pháp ngẫu nhiênRepeatThử 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ậpNhân các giải pháp tốt lênTạo ra một số thay đổi trong các cá thể nàyUntil giải pháp tốt nhất đủ tốt7824/27/2017Khoan chỗ nàoVí dụ, khoan dầuGiải pháp1 = 300• Giả sử cần khoan dầu ở đâu đó dọc theo1km đường sa mạc• 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à 1số trong khoảng [0..1000]Giải pháp2= 900Đường05001000910Khoan dầuKhoan dầu• Tập các giải pháp có thể [0..1000] được gọilà không gian tìm kiếm hoặc không giantrạng thái• Chuyển sang xâu nhị phân64321684219001110000100300010010110010231111111111Giải pháp2 = 900(1110000100)Đường0OIL512 256 128Giải pháp1 = 300(0100101100)111000305Vị trí1234/27/2017Bề mặtKhô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 trongkhông gian• GA cố gắng tìm các điểm tốt hơn (độ phù hợp caohơn) trong không gian13S¬ ®å 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ẫunhiên• REPEAT– 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ị độphù hợp (Fitness)– Tiến hành toán tử chọn lọc tạo ra quần thể bố mẹ tạmthời P1– Tiến hành toán tử lai ghép từ P1 tạo ra quần thể các conP2– 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ệtiếp theo từ hai quần thể P2 và P315• UNTIL (Điều kiện dừng thoả)• GA có thể vấp phải tối ưu hóa cục bộ (local maxima) nếuKGTK có nhiều điểm như vậy14Sinh 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• Việc kết hợp 2 cá thể bố mẹ phụ thuộc vàoxác suất lai ghép• Sinh 2 cá thể mới (offspring)• Mỗi cá thể mới có thể bị thay đổi một cáchngẫu nhiên (đột biến - mutation)1644/27/2017Lai ghép1010000000Parent1Offspring110110111111001011111Parent2Offspring21010000000Lai ghép 1điểm – ngẫunhiênmutateĐột biếnOffspring11011011111Offspring11011001111Offspring21010000000Offspring21000000000Original offspringLai ghép được áp dụng với tỉ lệ cao(khoảng 0.8 đến 0.95)Mutated offspringmutation rate được áp dụng với tỉ lệ thấp (thường giữa 0.1và 0.001)17Các biến thể của GA18Cá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ảmong muốn• Các giá trị thường dùngN = 50, m = 0.05, c = 0.9– Vòng loại (Tournament)– Elitism, v.v…• Các chiến lược trao đổi chéo– 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 nhau19205 ...