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. | Đề 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: LÊ ĐẮC NHƯỜNG Sinh viên: Bùi Thị Hạnh. Hoàng Hiền Trần Hồng Lân Trường Đại học Hải Phòng Khoa: Công nghệ thông tin 1/23 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 độn, chậm chạp Thỏ thông minh nhanh 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: | Đề 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: LÊ ĐẮC NHƯỜNG Sinh viên: Bùi Thị Hạnh. Hoàng Hiền Trần Hồng Lân Trường Đại học Hải Phòng Khoa: Công nghệ thông tin 1/23 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 độn, chậm chạp Thỏ thông minh nhanh 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 Biểu diễn cá thể. Lai ghép Lai tạo Hàm mục tiêu. Văn bản của bạn. I: Giải thuật di truyền. * Các toán tử di truyền Đột biến Toán tử di truyền 10 Cơ sỏ của giải thuật di truyền 10 I: Giải thuật di truyền. * Các toán tử di truyền 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. 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. 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 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 nhiều đoạn Độ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
