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

4/27/2017<br /> <br /> Lịch sử<br /> •<br /> •<br /> •<br /> •<br /> <br /> Giải thuật di truyền<br /> <br /> GA đề xuất bởi John Holland năm 1970<br /> Phổ biến những năm 1980<br /> Dựa trên ý tưởng về luật tiến hóa Darwin<br /> Dùng để giải quyết nhiều bài toán không dễ<br /> giải quyết bằng các kỹ thuật khác<br /> <br /> 1<br /> <br /> 2<br /> <br /> Tiến hóa trong thế giới thực<br /> • Mỗi tế bào sống bao gồm các nhiễm sắc thể (chromosomes)<br /> – là các xâu DNA<br /> • Mỗi NST bao gồm 1 tập các gene – các khối DNA<br /> • Mỗi gene quyết định một số đặc điểm của cá thể (như màu<br /> mắt)<br /> • Một tập các gene được gọi là kiểu di truyền (genotype)<br /> • Một tập các đặc điểm (như màu mắt) được gọi là kiểu hình (<br /> phenotype)<br /> • Việc tái tạo (reproduction) là việc kết hợp các gene từ bố mẹ<br /> cộng với một số lượng nhỏ các đột biến (mutation) trong bản<br /> sao<br /> • Độ phù hợp (fitness) của 1 cá thể là số con nó có thể sinh ra<br /> trước khi nó chết<br /> • Tiến hóa dựa trên “sự sống sót của các cá thể phù hợp nhất”<br /> 3<br /> <br /> Đặt vấn đề<br /> •<br /> •<br /> •<br /> •<br /> •<br /> <br /> Giả sử có 1 vấn đề<br /> Ta chưa biết cách giải<br /> Có thể làm gì?<br /> Sử dụng máy tính để tìm lời giải?<br /> Làm thế nào?<br /> <br /> 4<br /> <br /> 1<br /> <br /> 4/27/2017<br /> <br /> Giải pháp tệ nhất<br /> <br /> Có thể làm như vậy không?<br /> • Đôi khi – có:<br /> <br /> Thuật toán “thử và sai”<br /> <br /> – Nếu chỉ có vài đáp án<br /> – Và có đủ thời gian<br /> <br /> Repeat<br /> <br /> • Với đa phần các vấn đề - không:<br /> <br /> Sinh một giải pháp ngẫu nhiên<br /> Thử giải pháp đó và kiểm tra sự phù hợp của nó<br /> <br /> – Có quá nhiều đáp án<br /> – Không có thời gian thử<br /> <br /> Until giải pháp đủ tốt<br /> <br /> 5<br /> <br /> 6<br /> <br /> Làm cách nào để mã hóa 1 giải<br /> pháp<br /> <br /> Ý tưởng ít tệ hơn (GA)<br /> <br /> • Phụ thuộc vào vấn đề<br /> • GA mã hóa giải pháp như 1 chuỗi cố định<br /> các bit (ví dụ 101110, 111111, 000101)<br /> • Mỗi bit biểu diễn một số đặc điểm của giải<br /> pháp đề xuất<br /> • Để có thể sử dụng GA, cần “thử” các chuỗi<br /> và cho điểm mức độ “tốt” của giải pháp<br /> <br /> Sinh 1 tập các giải pháp ngẫu nhiên<br /> Repeat<br /> Thử mỗi giải pháp trong tập (xếp hạng chúng)<br /> Loại bỏ 1 số giải pháp kém trong tập<br /> Nhân các giải pháp tốt lên<br /> Tạo ra một số thay đổi trong các cá thể này<br /> <br /> Until giải pháp tốt nhất đủ tốt<br /> 7<br /> <br /> 8<br /> <br /> 2<br /> <br /> 4/27/2017<br /> <br /> Khoan chỗ nào<br /> <br /> Ví dụ, khoan dầu<br /> <br /> Giải pháp<br /> 1 = 300<br /> <br /> • Giả sử cần khoan dầu ở đâu đó dọc theo<br /> 1km đường sa mạc<br /> • Vấn đề: chọn chỗ tốt nhất trên đường có thể<br /> cho nhiều dầu nhất<br /> • Mỗi giải pháp là 1 vị trí trên đường, tức là 1<br /> số trong khoảng [0..1000]<br /> <br /> Giải pháp2<br /> = 900<br /> <br /> Đường<br /> 0<br /> <br /> 500<br /> <br /> 1000<br /> <br /> 9<br /> <br /> 10<br /> <br /> Khoan dầu<br /> <br /> Khoan dầu<br /> • Tập các giải pháp có thể [0..1000] được gọi<br /> là không gian tìm kiếm hoặc không gian<br /> trạng thái<br /> • Chuyển sang xâu nhị phân<br /> 64<br /> <br /> 32<br /> <br /> 16<br /> <br /> 8<br /> <br /> 4<br /> <br /> 2<br /> <br /> 1<br /> <br /> 900<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 0<br /> <br /> 0<br /> <br /> 0<br /> <br /> 0<br /> <br /> 1<br /> <br /> 0<br /> <br /> 0<br /> <br /> 300<br /> <br /> 0<br /> <br /> 1<br /> <br /> 0<br /> <br /> 0<br /> <br /> 1<br /> <br /> 0<br /> <br /> 1<br /> <br /> 1<br /> <br /> 0<br /> <br /> 0<br /> <br /> 1023<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> Giải pháp2 = 900<br /> (1110000100)<br /> <br /> Đường<br /> <br /> 0<br /> OIL<br /> <br /> 512 256 128<br /> <br /> Giải pháp1 = 300<br /> (0100101100)<br /> <br /> 11<br /> <br /> 1000<br /> <br /> 30<br /> <br /> 5<br /> Vị trí<br /> <br /> 12<br /> <br /> 3<br /> <br /> 4/27/2017<br /> <br /> Bề mặt<br /> <br /> Không gian tìm kiếm<br /> • Không gian tìm kiếm ứng với các hàm như f(x),<br /> f(x,y), có thể một chiều hoặc nhiều chiều.<br /> • Không gian tìm kiếm có thể được mô hình hóa như<br /> 1 bề mặt trong đó độ phù hợp là độ sâu<br /> • Mỗi kiểu di truyền (genotype) là 1 điểm trong<br /> không gian<br /> • GA cố gắng tìm các điểm tốt hơn (độ phù hợp cao<br /> hơn) trong không gian<br /> <br /> 13<br /> <br /> S¬ ®å tæng thÓ cña GA<br /> • Khởi động quần thể đầu tiên P gồm N cá thể một cách ngẫu<br /> nhiên<br /> • REPEAT<br /> – Giải mã các cá thể thành tham số<br /> – Tính giá trị hàm mục tiêu cho từng cá thể trong P<br /> – Chuyển đổi giá trị hàm mục tiêu (Target) thành giá trị độ<br /> phù hợp (Fitness)<br /> – Tiến hành toán tử chọn lọc tạo ra quần thể bố mẹ tạm<br /> thời P1<br /> – Tiến hành toán tử lai ghép từ P1 tạo ra quần thể các con<br /> P2<br /> – Tiến hành toán tử đột biến trên P2 tạo ra quần thể P3<br /> – Tiến hành toán tử tái tạo để tạo ra quần thể cho thế hệ<br /> tiếp theo từ hai quần thể P2 và P3<br /> 15<br /> • UNTIL (Điều kiện dừng thoả)<br /> <br /> • GA có thể vấp phải tối ưu hóa cục bộ (local maxima) nếu<br /> KGTK có nhiều điểm như vậy<br /> <br /> 14<br /> <br /> Sinh thêm cá thể - Phép lai ghép<br /> (Crossover)<br /> • Kết hợp gene của 2 cá thể bố mẹ có độ phù<br /> hợp cao để tạo nên cá thể con<br /> • Việc kết hợp 2 cá thể bố mẹ phụ thuộc vào<br /> xác suất lai ghép<br /> • Sinh 2 cá thể mới (offspring)<br /> • Mỗi cá thể mới có thể bị thay đổi một cách<br /> ngẫu nhiên (đột biến - mutation)<br /> 16<br /> <br /> 4<br /> <br /> 4/27/2017<br /> <br /> Lai ghép<br /> <br /> 1010000000<br /> <br /> Parent1<br /> <br /> Offspring1<br /> <br /> 1011011111<br /> <br /> 1001011111<br /> <br /> Parent2<br /> <br /> Offspring2<br /> <br /> 1010000000<br /> <br /> Lai ghép 1<br /> điểm – ngẫu<br /> nhiên<br /> <br /> mutate<br /> <br /> Đột biến<br /> Offspring1<br /> <br /> 1011011111<br /> <br /> Offspring1<br /> <br /> 1011001111<br /> <br /> Offspring2<br /> <br /> 1010000000<br /> <br /> Offspring2<br /> <br /> 1000000000<br /> <br /> Original offspring<br /> <br /> Lai ghép được áp dụng với tỉ lệ cao<br /> (khoảng 0.8 đến 0.95)<br /> <br /> Mutated offspring<br /> <br /> mutation rate được áp dụng với tỉ lệ thấp (thường giữa 0.1<br /> và 0.001)<br /> 17<br /> <br /> Các biến thể của GA<br /> <br /> 18<br /> <br /> Các tham số<br /> <br /> • Các chiến lược lựa chọn (không phải roulette)<br /> <br /> • Kích thước quần thể (N), tỉ lệ đột biến (m),<br /> tỉ lệ lai ghép (c)<br /> • Các giá trị này cần phù hợp với kết quả<br /> mong muốn<br /> • Các giá trị thường dùng<br /> N = 50, m = 0.05, c = 0.9<br /> <br /> – Vòng loại (Tournament)<br /> – Elitism, v.v…<br /> <br /> • Các chiến lược trao đổi chéo<br /> – Multi-point crossover<br /> – 3 way crossover, v.v…<br /> <br /> • Các cách mã hóa khác<br /> – Các giá trị nguyên<br /> – Tập có thứ tự các ký tự<br /> <br /> • Các kiểu biến dị khác nhau<br /> 19<br /> <br /> 20<br /> <br /> 5<br /> <br />