zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Chia sẻ: Thu Hiền Tin | Ngày: | Loại File: PPTX | Số trang:26

Báo xấu

468
lượt xem 75
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 NPKhó. 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à tọa độ. Ø Trọng số trong cột đầu tiên là số hiệu của đỉnh, trọng số thứ hai là hoành độ, trọng số thứ ba là tung độ. Ø Khoảng cách giữa hai đỉnh M(xi, yi) và N(xj, yj) của đồ thị (trọng số cho cạnh) được tính theo công thức: 16
III: Giải bài toán người du lịch bằng GA. v Mã hóa bài toán(chu trình) Ø Chu trình được mã hóa bằng mảng có thứ tự các số hiệu của đỉnh. Ví dụ chu trình của đồ thị 10 đỉnh: ØMỗi chu trình có thông số về chi phí của toàn bộ chu trình đó. Chi phí này được tính bằng tổng độ dài tất cả các cạnh tạo nên chu trình. ØMỗi chu trình là 1 lời giải, trong giải thuật di truyền coi đó như 1cá thể. 17
III: Giải bài toán người du lịch bằng GA. v Khởi tạo quần thể Ø Quần thể ban đầu được khởi tạo bằng cách sinh ngẫu nhiên các chu trình. Ø Số lượng chu trình khởi tạo là một nửa số kích thước cá thể tối đa. Ø Việc sinh ngẫu nhiên sử dụng hàm đột biến. Ø Số kích thước cá thể tối đa có thể tùy biến theo số đỉnh của đo thị cần giải, ở đây chọn kích thước quần thể là 100 cá thể. 18
III: Giải bài toán người du lịch bằng GA. v Lai ghép Ø Lai ghép thực hiện trên 2 cá thể đầuvào Ø Thực hiện lai ghép 1 điểm cắt với vị trí cắt là ngẫu nhiên : Ø Cắt từ điểm p đến hết chu trình của C2 đưa vào chu trình mới, lấy một ví dụ p = 5: Ø Xét từ đầu đến cuối chu trình 1, nạp dần các điểm chưa có trong con lai theo thứ tự duyệt ta được chu trình mới: 19
Tính lại chi phí cho chu trình mới: Private circle hybridize( circle cl, circle c2) { Circle child =new circle (c1.getLength()); Random rand = new Random(); int p =rand.nextInt(child.length 1) int I =0;j =0,k=0; For(i =p; i

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.