Bài thuyết trình: Thuật toán di truyền và ứng dụng giải bài toán người du lịch - ĐH Hải Phòng

 Bài thuyết trình gồm các nội dung sau: Giải thuật di truyền, bài toán người du lịch, giải bài toán người du lịch bằng giải thuật di truyền. Tham khảo nội dung bài thuyết trình để nắm bắt nội dung chi tiết.

Nội dung trích xuất từ tài liệu:
Bài thuyết trình: Thuật toán di truyền và ứng dụng giải bài toán người du lịch - ĐH Hải Phòng Trường Đại học Hải Phòng Khoa: Công nghệ thông tin Đề tài: Thuật toán di truyền và ứng dụng giải bài toán người du lịch.    Giảng viên hướng dẫn:  Th.S LÊ ĐẮC NHƯỜNG          Sinh viên:   Bùi Thị Hạnh. Hoàng T.Thu Hiền Trần Hồng Lân 1 Nội dung trình bày: 2 I: Giải thuật di truyền.         *Khái niệm,   Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm  tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp.   Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận  dụng các nguyên lý của tiến hóa như  di truyền, đột biến, chọn lọc  tự nhiên, và trao đổi chéo 3 I: Giải thuật di truyền.         *  Tư tưởng   Mô phỏng các hiện tượng tự nhiên: Kế thừa và đấu tranh sinh tồn  để cái tiến.   Ví dụ: Sự tiến hóa của loài thỏ. Thỏ đần  Thỏ thông  độn, chậm  minh nhanh  chạp nhẹn Thỏ bị  loại bỏ 4 I: Giải thuật di truyền.         *  Tư tưởng Quần thể ban đầu 5 I: Giải thuật di truyền.         *  Tư tưởng Quá trình sinh sản 6 I: Giải thuật di truyền.         *  Tư tưởng Quần thể còn lại, bắt đầu quá trình sinh  sản 7 I: Giải thuật di truyền.         *  Tư tưởng Thế hệ sau. 8 I: Giải thuật di truyền.         *  Lưu đồ Lưu đồ thuật giải cơ bản. 9 I: Giải thuật di truyền.         *  Các toán tử di truyền Biểu  diễn cá  thể. Hàm  Văn bản  của bạn. mục  tiêu. Đột biến Toán tử di truyền Lai tạo Lai  ghép 10 I: Giải thuật di truyền.         *  Các toán tử di truyền v Biểu diễn cá thể:    Là việc ánh xạ các tham số của bài toán lên một chuỗi có chiều dài  xác định.  v Một hàm mục tiêu (fitness):  Lấy một chuỗi NST là đầu vào và trả về giá trị tượng trưng cho  chuỗi NST đó để đánh giá trên vấn đề cần giải quyết.  v Toán tử tái tạo  Là quá trình các chuỗi được lựa chọn tùy thuộc vào giá trị hàm mục  tiêu..  11 I: Giải thuật di truyền.         *  Các toán tử di truyền v Lai ghép.    Phép lai là quá trình hình thành NST mới trên cơ sở NST cha mẹ,       bằng cách ghép một hay nhiều đoạn gen của hai (hay nhiều) NST  cha    mẹ khác nhau.  ü Lai ghép một điểm cắt, nhiều  ü Lai ghép nhiều  điểm cắt đoạn v Đột biến  Đột biến là tình trạng NST con không có một (hoặc một số) tính  trạng có trong mã di truyền của cha mẹ.  12 I. Giải thuật di truyền.         *  Đấu tranh sinh  tồ n Chọn những NST từ quần thể kết quả theo một quy  tắc nào đó thay thế cho cha mẹ để sinh ra thế hệ mới. Phương thức  Phương thức 2 Phương thức 3 1 TT Tráo đổi hoàn toàn  Tráo đổi ngẫu nhiên (k  Chọn những cá thể  05 con mẹ thay thế  bằng  ưu tú nhất cha mẹ bằng con. k  con con) 13 I. Giải thuật di truyền.         *  Các bước giải thuật             Bước 1: Chọn mô hình cho giải pháp của vấn đề.        Bước 2: Chỉ định cho mỗi giải pháp một ký hiệu        Bước 3: Tìm hàm số thích nghi cho vấn đề và tính hệ số thích nghi cho từng giải pháp          Bước 4: Dựa trên hệ số thích nghi của các giải pháp để thực hiện sự tạo sinh (reproduction) và biến  hóa    các giải pháp. Các phương thức biến hóa gồm: lai ghép (cross over), đột biến (mutation).       Bước 5: Tính các hệ số thích nghi cho các giải pháp mới là loại bỏ những giải pháp kém nhất để chỉ  cong giữ lại một số nhất định các giải pháp          Bước 6: Nếu chưa tìm được giải pháp tối  ưu hay tương đối khá nhất hay chưa hết  hạn kỳ  ấn định,  trở lại bước thứ 4 để tìm giải pháp mới.        Bước 7: Tìm được giải pháp tối ưu hoặc nếu thời gian cho phép để chấm dứt thì báo cáo kết quả tính  được. 14 II. Bài toán người du lịch.         *Định nghĩa, độ phức tạp v Định nghĩa. Cho  đồ  thị  đầy  đủ  n  đỉnh  vô  hướng,  có    trọng                                                                                                                          s ố G = (V, E). Tìm  chu trình  v1→v2     →…→vn→v1 Với vi  Một  chu  trình  như  vậy  còn  gọi  là  chu  trình  Hamilton. vĐộ phức tạp Bài toán TSP thuộc lớp bài toán NP­Khó.    15 III: Giải bài toán người du lịch bằng GA. v     Mã hóa bài toán (đồ thị) Ø Đồ thị được mã hóa bằng danh sách mảng các điểm và ...