Đề tài Thuật toán di truyền và ứng dụng giải bài toán người du lịch

Đề 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   Trường Đại học Hải PhòngKhoa: Công nghệ thông tin1/231Nội dung trình bày:2I: 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éo3I: Giải thuật di truyền. * Tư tưởngMô 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ạpThỏ thông minh nhanh nhẹnThỏ bị loại bỏ4I: Giải thuật di truyền. * Tư tưởngQuần thể ban đầu5I: Giải thuật di truyền. * Tư tưởngQuá trình sinh sản6I: Giải thuật di truyền. * Tư tưởngQuần thể còn lại, bắt đầu quá trình sinh sản7I: Giải thuật di truyền. * Tư tưởngThế hệ sau.8I: Giải thuật di truyền. * Lưu đồLưu đồ thuật giải cơ bản.9Biểu diễn cá thể.Lai ghépLai tạoHà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ếnToán tử di truyền10I: Giải thuật di truyền. * Các toán tử di truyềnBiể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.. 11I: Giải thuật di truyền. * Các toán tử di truyềnLai 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 cha mẹ. Lai ghép một điểm cắt, nhiều điểm cắt1205TTTráo đổi ngẫu nhiên (k con mẹ thay thế bằng k con con)Chọn những cá thể ưu tú nhấtI. Giải thuật di truyền. * Đấu tranh sinh tồnChọ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 1Phương thức 2Phương thức 3Tráo đổi hoàn toàn cha mẹ bằng con.1314 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.I. Giải thuật di truyền. * Các bước giải thuậtII. Bài toán người du lịch. *Định nghĩa, độ phức tạpĐị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.Độ phức tạpBài toán TSP thuộc lớp bài toán NP-Khó. 15III: Giải bài toán người du lịch bằng GA. 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: 16Chu 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ể. III: Giải bài toán người du lịch bằng GA. Mã hóa bài toán(chu trình)17III: Giải bài toán người du lịch bằng GA. 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ể. 18III: Giải bài toán người du lịch bằng GA. 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:19Tí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; i0 ){ P1 = rand.nextInt(n); P2 = rand.nextInt(n); Temp = nextgen.vertex[p1]; Nextgen.vertex[p1] = nextgen.vertex[p2]; Nextgen.vertex[p2] = temp; Count --;}Return nextgen;}22Chọnlọc để đảm bảo tính cân bằng của quần thể [Số cá thể ở, l thế hệ] = [Kích thước mặc định] + [Số cá thể mới sinh]Cách thức chọn lọc cá thể đánh giá dựa trên chi phí của mỗi chu trìnhCách thức chọn lọc tự nhiên.1. Sắp xếp quần thể theo chi phí tăng dần.2. Lựa chọn ngẫu nhiên l chỉ số : a (0 < a < l)III: Giải bài toán người du lịch bằng GA. Chọn lọc tự nhiên3.Loại bỏ cá thể thứ a kém thích nghi nhất từ cá thể đứng đầu danh sách quần thể.4. Loại đến khi số cá thể còn lại bằng kích thước mặc định.23private void sortList(){ int i =0, j =0,min;Circle temp;For(I =0;i<population .size() – 1; i++){Min =I;For(j =i+1;j<population.size();j++){If(population.get(j).cost<population.get(min).cost)Min =j;}Temp = population.get(i);Population.add(I, population.get(min));Population.remove(i+1);Population.remove(min);Population.add(min, temp);}24III: Giải bài toán người du lịch bằng GA. Chọn lọc tự nhiênVới quần thể khởi tạo ban đầu được tiến hóa ngẫu nhiên và thích nghi với điều kiện chọn lọc.Các cá thể kém thích nghi sẽ bị loại thải và cá thể tốt nhất được chọn làm lời giải. Việc tiến hóa diễn ra qua một số thế hệ, ở mỗi thế hệ ta thực hiện lai ghép và đột biến ngẫu nhiên trên toàn quần thể. 25Xin chân thành cảm ơn sự lắng nghe của các thầy cô giáo và rất mong sự góp ý từ phía quý thầy cô!!26