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,. nội dung chi tiết. | 4/27/2017 Lịch sử • • • • Giải thuật di truyền GA đề xuất bởi John Holland năm 1970 Phổ biến những năm 1980 Dựa trên ý tưởng về luật tiến hóa Darwin Dù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ác 1 2 Tiế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àu mắ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ản sao • Độ phù hợp (fitness) của 1 cá thể là số con nó có thể sinh ra trướ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ải Có thể làm gì? Sử dụng máy tính để tìm lời giải? Làm thế nào? 4 1 4/27/2017 Giải pháp tệ nhất Có 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 gian Repeat • Với đa phần các vấn đề - không: Sinh một giải pháp ngẫu nhiên Thử 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ốt 5 6 Làm cách nào để mã hóa 1 giải phá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ố định các bit (ví dụ 101110, 111111, 000101) • Mỗi bit biểu diễn một số đặc điểm của giải pháp đề xuất • Để có thể sử dụng GA, cần “thử” các chuỗi và cho điểm mức độ “tốt” của giải pháp Sinh 1 tập các giải pháp ngẫu nhiên Repeat Thử 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ập Nhân các giải pháp tốt lên Tạo ra một số thay đổi trong các cá thể này Until giải pháp tốt nhất đủ tốt 7 8 2 4/27/2017 Khoan chỗ nào Ví dụ, khoan dầu Giải pháp 1 = 300 • Giả sử cần khoan dầu ở đâu đó dọc theo 1km đường sa mạc •
