Áp dụng giải thuật di truyền giải bài toán người du lịch

- Tôi cũng xin gửi lời cảm ơn tới các anh chị em và các bạn trong nhóm nghiên cứu, tìm hiểu các phương thức phát triển, cải tiến để áp dụng giải thuật di truyền trong giải bài toán người du lịch đã giúp đỡ tôi trong suốt quá trình học tập và nghiên cứu.
- Tổng quan về giải thuật di truyền.
- Mô hình giải thuật di truyền.
- Cơ chế thực hiện giải thuật di truyền.
- Các ứng dụng của giải thuật di truyền.
- Giới thiệu bài toán.
- Ứng dụng của bài toán.
- Giải thuật chính xác.
- Giải thuật xấp xỉ.
- 28 CHƯƠNG 3 - GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NGƯỜI DU LỊCH.
- 46 3 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Từ viết tắt Thuật ngữ Giải thích GA Genetic Algorithm Giải thuật di truyền TSP Travelling Salesman problem Bài toán người du lịch PMX Partial Mappel Crossover Phép lai ánh xạ từng phần OX Order Crossover Phép lai thứ tự MSCX Modified Sequential Constructive Crossover Phép lai MSCX DSA Digital Subtraction Angiography Tên một hệ thống chụp động mạch RSM Reverse Sequence Mutation Đột biến đảo ngược trình tự THRORS Phép đột biến THRORS 4 DANH MỤC CÁC BẢNG Bảng 1: Ma trận khoảng cách (chi phí.
- 13 Hình 10: Mô hình giải thuật di truyền.
- 17 Hình 11: Bài toán người du lịch.
- 25 Hình 12: Một lời giải của bài toán người du lịch.
- Tính cấp thiết của đề tài Bài toán người du lịch (Traveling Saleman Problem – TSP) là một bài toán được nghiên cứu rộng rãi trong lĩnh vực khoa học máy tính.
- Từ những năm 1940, có rất nhiều bài báo, những công trình nghiên cứu giải quyết bài toán này.
- Tuy vậy, sau hơn nửa thế kỷ nghiên cứu, bài toán vẫn chưa hoàn toàn được giải.
- Vì vậy, bài toán người du lịch được xếp vào trong danh mục những bài toán khó.
- Không chỉ vậy, bài toán người du lịch còn có nhiều ứng dụng trong cuộc sống hàng ngày.
- Sau nhiều năm nghiên cứu, nhiều giải pháp đã được đưa ra nhằm giải bài toán người du lịch.
- Đề tài “Áp dụng giải thuật di truyền giải bài toán người du lịch” được thực hiện nhằm đưa ra những tìm hiểu khái quát nhất về giải thuật di truyền đặc biệt là cơ chế thực hiện và nguyên lý hoạt động của nó.
- Từ đó có thể xây dựng chương trình hoàn chỉnh về thuật giải và cách áp dụng thuật giải di truyền vào giải bài toán người du lịch để đưa ra lời giải tốt nhất trong thời gian ngắn nhất.
- Mục tiêu nghiên cứu Về mặt lý thuyết, trước tiên tác giả nghiên cứu những kiến thức nền tảng như cơ sở lý thuyết thuật giải di truyền, bài toán người du lịch và áp dụng giải thuật di truyền giải bài toán người du lịch.
- Chương 2: Bài toán người du lịch: Phát biểu bài toán người du lịch, các nghiên cứu liên quan và một số ứng dụng của bài toán trong thực tiễn.
- 8 Chương 3: Áp dụng giải thuật di truyền giải bài toán người du lịch Chương 4: Kết quả thực nghiệm: Các kết quả trong quá trình chạy thực nghiệm, các so sánh, đánh giá cũng sẽ được đưa ra trong chương này.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 9 CHƯƠNG 1 - TỔNG QUAN CƠ SỞ LÝ THUYẾT 1.1.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 10 Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0 , x1.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 11 Hình 4: Đồ thị có hướng và ma trận liên thuộc đỉnh – cạnh 1.1.3.3.
- Hình 9: Đồ thị đấu loại D5, Đồ thị đấu loại liên thông mạnh D6 Áp dụng giải thuật di truyền giải bài toán người du lịch 14 1.2.
- Tổng quan về giải thuật di truyền 1.2.1.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 15 1.2.2.1.
- Không giống như di truyền học trong tự nhiên, một cơ thể của một chủng loại đã cho mang một số nhiễm sắc thể nào đó nhưng trong giải thuật di truyền ta chỉ nói về những cá thể có một nhiễm sắc thể và các cá thể này biểu diễn một lời giải của bài toán đang được giải.
- Trong giải thuật di truyền quần thể chính là tập hợp các lời giải của bài toán đang giải.
- Trong giải thuật di truyền, lai ghép được coi là một sự tổ hợp lại các tính chất (thành phần) trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có Áp dụng giải thuật di truyền giải bài toán người du lịch 16 đặc tính mong muốn là tốt hơn thế hệ cha mẹ.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 17 Hình 10: Mô hình giải thuật di truyền 1.2.4.
- Mã hóa cá thể Vấn đề trước hết cần giải quyết là biểu diễn các cá thể như thế nào để phù hợp và thuận lợi khi giải bài toán.
- Tuỳ theo từng bài toán cụ thể mà có những cách biểu diễn khác nhau.
- Ví dụ trong bài toán đơn giản là tìm giá trị X sao cho.
- Mã hóa nhị phân khá phổ biến, tuy nhiên phương thức mã hóa này có một nhược điểm là có thể tạo ra không gian mã hóa lớn hơn so với không gian giá trị của Áp dụng giải thuật di truyền giải bài toán người du lịch 18 nhiễm sắc thể, hơn nữa có thể xảy ra trường hợp là các nhiễm sắc thể được tạo ra không thuộc không gian tìm kiếm.
- Vì vậy, đối với nhiều bài toán thì biểu diễn nhị phân là không hữu hiệu.
- Chẳng hạn cách biểu diễn này đã được áp dụng cho bài toán người du lịch: Một thương gia phải đi qua nhiều thành phố (n).
- Một hành trình được biểu diễn là danh sách l của các tham chiếu: Áp dụng giải thuật di truyền giải bài toán người du lịch 19 l.
- Mã hóa hoán vị phù hợp cho các bài toán liên quan đến thứ tự.
- Đối với các bài toán này, việc thao tác trên các nhiễm sắc thể chính là hoán vị các số trong chuỗi đó làm thay đổi trình tự ban đầu của chuỗi.
- c) Mã hóa bằng giá trị Biểu diễn giá trị trực tiếp có thể được dùng trong các bài toán có chứa những giá trị phức tạp.
- Nếu dùng biểu diễn nhị phân cho loại bài toán này thì rất phức tạp.
- Một ví dụ cho cách mã hóa này là bài toán tìm trọng số mạng nơron.
- Tùy theo mỗi bài toán thì các nút mang ý nghĩa khác nhau.
- Thông thường biểu diễn theo cây thường được áp dụng cho dạng bài toán xác định công thức tối ưu (xác định công thức hồi quy trong thí nghiệm hóa sinh).
- Áp dụng giải thuật di truyền giải bài toán người du lịch 20 1.2.4.2.
- Như đã đưa ra ở phần trước, quần thể là tập hợp các cá thể có cùng chung một số đặc điểm, trong giải thuật di truyền ta quan niệm quần thể là một tập các lời giải của bài toán.
- Giá trị của hàm mục tiêu là nhỏ nhất hay lớn nhất phụ thuộc vào bài toán được đưa ra và hàm mục tiêu được lựa chọn sao cho phù hợp với bài toán.
- Có rất nhiều phương thức chọn lọc và sau đây là các phương thức chọn lọc thường được sử dụng khi giải bài toán người du lịch.
- Lựa chọn theo yếu tố ngẫu nhiên Áp dụng giải thuật di truyền giải bài toán người du lịch 21  Lựa chọn theo xếp hạng  Lựa chọn tranh đấu  Lựa chọn theo tỷ lệ (bánh xe Roulet) b) Lai ghép.
- Có rất nhiều dạng đột biến khác nhau được các nhà khoa học nghiên cứu và sử dụng khi giải bài toán người du lịch nhưng thông thường đều là thực hiện các thao tác sau theo nhiều hình thức.
- Đảo: chọn một đọan nhiễm sắc thể con bất kỳ rồi đảo ngước chiều của đoạn nhiễm sắc thể đã chọn và đưa ra một nhiễm sắc thể mới  Chèn: chọn một thành phố và chèn thành phố đó vào vị trí ngẫu nhiên  Dời chỗ: chọn một hành trình con rồi chèn nó vào vị trí ngẫu nhiên  Trao đổi qua lại: hoán vị hai thành phố Mỗi gen trong tất cả các NST có cơ hội đột biến như nhau, nghĩa là đối với mỗi NST trong quần thể hiện hành (sau khi lai) và đối với mỗi gen trong NST, quá trình đột biến được thực hiện như sau: Áp dụng giải thuật di truyền giải bài toán người du lịch 22  Phát sinh ngẫu nhiên một số r trong khoảng [0..1.
- Đến nay GA đã phát triển mạnh và có nhiều ứng dụng thực tế, đặc biệt là các bài toán về trí tuệ nhân tạo.
- Tối ưu hoá và học máy: Trong lĩnh vực tối ưu hóa có nhiều bài toán được áp dụng giải thuật di truyền và đã thành công như tối ưu hoá hàm một biến, tối ưu hóa hàm nhiều biến, hay như bài toán người du lịch, bài toán hộp đen, các bài toán kinh doanh, nhận dạng điều khiển hệ thống… David E.Golderg đã ứng dụng GA để tối ưu hóa bài toán điều Áp dụng giải thuật di truyền giải bài toán người du lịch 23 khiễn hệ thống đường ống dẫn khí thiên nhiên.
- Bên cạnh đó, rất nhiều đề tài liên quan đến tối ưu hóa cũng được áp dụng giải thuật di truyền như tối ưu hóa khẩu phần thức ăn chăn nuôi, tối ưu quãng đường của xe buýt trong thành phố, tối ưu hóa trong lĩnh vực thiết kế mạng hoặc hệ thống máy, giải quyết các bài toán tối ưu kinh tế.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 24  Qũy đạo cho người máy.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 25 CHƯƠNG 2 - BÀI TOÁN NGƯỜI DU LỊCH 2.1.
- Bài toán người du lịch (Travelling Salesman problem (TSP)) được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và được ghi trong cuốn giáo trình Lý thuyết đồ thị nổi tiếng của Oxford.
- Bài toán này nhanh chóng trở thành bài toán khó thách thức toàn thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (trong chuyên ngành thuật toán người ta còn gọi chúng là những bài toán NP-hard).
- Nội dung của bài toán là: Một người du lịch muốn đi tham quan n thành phố khác nhau.
- Hình 11: Bài toán người du lịch Áp dụng giải thuật di truyền giải bài toán người du lịch 26 Bài toán người du lịch được mô hình hóa như sau.
- Ứng dụng của bài toán Ứng dụng đầu tiên và phổ biến nhất của bài toán người du lịch chính là định tuyến giao thông và lập lịch.
- Một ứng dụng thực tiễn khác của bài toán TSP là trong các dây chuyền lắp ráp.
- Một lời giải của bài Áp dụng giải thuật di truyền giải bài toán người du lịch 27 toán TSP có thể sử dụng để tìm ra thứ tự tối ưu để di chuyển giữa các lỗ khoan.
- Để giải bài toán này dựa trên bài toán TSP, ta mô hình hóa bài toán bằng đồ thị trong đó các nút là các lỗ khoan và các cạnh là khoảng cách giữa chúng.
- Lời giải của bài toán người du lịch có thể sử dụng trong việc thiết kế các chi tiết máy hoặc thiết bị điện tử.
- Các nghiên cứu liên quan Có rất nhiều nghiên cứu được đưa ra để giải bài toán người du lịch, bao gồm giải thuật chính xác và giải thuật xấp xỉ 2.3.1.
- Giải pháp Áp dụng giải thuật di truyền giải bài toán người du lịch 28 chính xác cho 15.112 thị trấn Đức từ TSPLIB đã được tìm thấy vào năm 2001, bằng cách sử dụng phương pháp mặt cắt (cutting – plane) được đề xuất bởi George Dantzig, Ray Fulkerson, và Selmer M.
- Việc để một người dùng phổ thông tiếp cận đến lời giải của những bài toán như bài toán người du lịch là không thực tế.
- Trong khi đó, có rất nhiều vấn đề thực tế liên quan đến bài toán người du lịch.
- Thuật toán láng giềng gần nhất (NN – Nearest Neighbor) là một trong những thuật toán đầu tiên được dùng để tìm lời giải cho bài toán người bán hàng (bài toán người du lịch), và thường cho kết quả chênh lệch trong phạm vi 25% so với đường đi tối ưu [9].
- Tuy nhiên, vẫn còn tồn tại nhiều bản dữ liệu phân phối thành phố sắp xếp đặc biệt làm cho thuật toán láng giềng gần Áp dụng giải thuật di truyền giải bài toán người du lịch 29 đưa ra lời là các tuyến đường tồi tệ nhất (Gutin, Yeo và Zverovich, 2002) [4].
- Năm 2007, thuật toán dựa trên học thuyết tối ưu hóa bầy đàn (PSO) cho bài toán TSP được trình bày và so sánh với các thuật toán hiện có để giải quyết bài toán.
- Tác giả đã chứng minh rằng kích thước lớn hơn của bài toán Áp dụng giải thuật di truyền giải bài toán người du lịch 30 được giải quyết khi sử dụng thuật toán được đề xuất [22].
- Năm 2005, Lawrence V.Snyder trình bày một heuristic để giải quyết bài toán người du lịch tổng quát.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 31 CHƯƠNG 3 - GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NGƯỜI DU LỊCH 3.1.
- Với bài toán người du lịch, mỗi lời giải là một hoán vị biểu diễn thứ tự đến thăm các thành phố trong chu trình.
- Hình 12: Một lời giải của bài toán người du lịch Lời giải được thể hiện ở hình 12 sẽ được mã hóa như sau .
- Luận văn đề xuất hai phương pháp khởi tạo quần thể: Áp dụng giải thuật di truyền giải bài toán người du lịch 32 - Khởi tạo liệt kê: Liệt kê n hoán vị các thành phố đầu tiên làm quần thể ban đầu.
- sizepopiivfF_1)(ijjiPq1 Áp dụng giải thuật di truyền giải bài toán người du lịch 33  Nếu r < q1 (tức là r d(1,5) nên đỉnh 5 được chọn đưa vào nhiễm sắc thể con.
- Theo [2], [19] tác giả đã giới thiệu hai phép lai có hiệu quả tốt khi đưa vào cài đặt để giải bài toán TSP, trong đó MSCX có hiệu quả tốt hơn hai phép lai PMX và OX.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 36 3.5.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 38 CHƯƠNG 4 - KẾT QUẢ THỰC NGHIỆM 4.1.
- Dữ liệu thực nghiệm Luận văn sử dụng các bộ dữ liệu được cung cấp trên trang http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ bao gồm những bài toán được nhiều nhóm nghiên cứu sử dụng.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 39 4.3.
- Vì vậy, khả năng đưa ra lời giải Áp dụng giải thuật di truyền giải bài toán người du lịch 41 cha mẹ tốt hơn và đa dạng hơn để cải thiện các thế hệ sau sẽ cao hơn khi sử dụng chiến lược chọn lọc tỷ lệ (chỉ so sánh hai NST i-1 và i.
- Vì vậy, có thể kết luận rằng việc cài đặt giải Áp dụng giải thuật di truyền giải bài toán người du lịch 43 thuật di truyền sử dụng phép lai MSCX đưa ra kết quả tốt hơn nhiều so với hai phép lai OX và PMX thường được biết đến, đặc biệt là đối với các bộ dữ liệu lớn.
- Hình 19: So sánh kết quả tốt nhất đạt được khi sử dụng phép lai OX, PMX và MSCX qua từng thế hệ (xét 500 thế hệ đầu) của bộ dữ liệu wi29 Hình 20: So sánh kết quả tốt nhất đạt được khi sử dụng phép lai OX, PMX và MSCX qua từng thế hệ (xét 10.000 thế hệ đầu) của bộ dữ liệu gil262 Áp dụng giải thuật di truyền giải bài toán người du lịch 44 Hình 21: So sánh kết quả tốt nhất đạt được khi sử dụng phép lai PMX và MSCX qua từng thế hệ (xét 50.000 thế hệ đầu) của bộ dữ liệu pr1002 Sự hội tụ của kết quả tốt nhất thu được qua từng thế hệ khi sử dụng phép lai MSCX tốt hơn PMX và OX ở bộ dữ liệu nhỏ (wi29), bộ dữ liệu vừa (gil262) và bộ dữ liệu lớn (pr1002) do phương thức hoạt động của MSCX dựa trên ma trận khoảng cách (ma trận chi phí).
- Kết luận Qua quá trình nghiên cứu và chạy thử nghiệm nhiều lần trên máy tính, giải thuật di truyền có thể giải quyết bài toán người du lịch với các bộ dữ liệu có số lượng thành phố nhỏ trong một thời gian rất ngắn.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 45 4.5.
- Hướng phát triển Với những kiến thức nền tảng về giải thuật di truyền và bài toán người du lịch, trong tương lai, việc nghiên cứu có thể tiếp tục với một số hướng như sau.
- Tiếp tục phát triển ứng dụng cho một số lớp bài toán tối ưu khác.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 46 TÀI LIỆU THAM KHẢO [1].
- Hoàng Kiếm, Giải một bài toán trên máy tính như thế nào, NXB Giáo Dục.
- Áp dụng giải thuật di truyền giải bài toán người du lịch 47 [10].
- Áp dụng giải thuật di truyền giải bài toán người du lịch 48 [21]

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt