ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KINH TẾ KHOA HỆ THỐNG THÔNG TIN KINH TẾ N H TẾ H U Ế - - H Ọ C KI KHÓA LUẬN TỐT NGHIỆP ẠI ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TR Ư Ờ N G Đ NGƯỜI DU LỊCH BẰNG WINFORM C# SINH VIÊN THỰC HIỆN: HỒ MINH TỒN Khóa học: 2014-2018 ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KINH TẾ KHOA HỆ THỐNG THÔNG TIN KINH TẾ N H TẾ H U Ế - - H Ọ C KI KHÓA LUẬN TỐT NGHIỆP ẠI ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TR Ư Ờ N G Đ NGƯỜI DU LỊCH BẰNG WINFORM C# Sinh viên thực hiện: Giảng viên hướng dẫn: Hồ Minh Toàn TS Hồ Quốc Dũng Lớp: K48A - Tin học kinh tế Huế, 04/2018 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp LỜI CÁM ƠN Trên thực tế khơng có thành cơng mà khơng gắn liền với hỗ trợ, giúp đỡ hướng dẫn người khác Lời em xin chân thành cảm ơn tất thầy cô trường Đại học kinh tế - Đại học Huế đặc biệt Quý Thầy, Cô khoa Hệ thống thông tin kinh tế người truyền đạt cho em nhiều kiến thức quý báu, tạo tảng kiến thức vững cho tương lai em, tạo điều kiện, giúp đỡ em thực khóa luận Em xin chân thành cám ơn Thầy Hồ Quốc Dũng người trực tiếp hướng U Ế dẫn cho em tiếp cận với sở thực tập Thầy người hướng dẫn tận H tình, ln tạo hội cho em phát triển tạo động lực cho em q TẾ trình làm đề tài khóa luận Ngồi ra, thầy truyền đạt bổ sung kiến N H thức em thiếu sót, cách làm việc nhiều điều quý báu khác KI Em xin chân thành gửi lời cám ơn đến Ban lãnh đạo Quý Công Ty Cổ Ọ C phần may thương mại Gio Linh, anh chị phòng Kỹ thuật cho em có H hội thực tập công ty, cảm ơn bảo nhiệt tình quan tâm ẠI tất anh chị em thực tập cơng ty G Đ Cuối lời, với lòng biết ơn sâu sắc lần em xin chân thành cảm ơn tất N người quan tâm giúp đỡ em hồn thành khóa luận Ư Ờ Trong trình thực tập, q trình làm báo cáo thực tập, TR khó tránh khỏi sai sót, mong Q Thầy, Cơ bỏ qua Đồng thời trình độ lý luận kinh nghiệm thực tiễn hạn chế nên báo cáo khơng thể tránh khỏi thiếu sót, em mong muốn nhận ý kiến đánh giá đóng góp Q Thầy, Cơ để em học thêm nhiều kinh nghiệm hoàn thành tốt nghiệp tương lai Em xin chân thành cám ơn ! Huế, ngày 30 tháng năm 2018 Sinh viên thực Hồ Minh Toàn SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang i GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp MỤC LỤC LỜI CÁM ƠN i MỤC LỤC ii DANH MỤC HÌNH VẼ v DANH MỤC BẢNG BIỂU vi DANH MỤC TỪ VIẾT TẮT vii U Ế PHẦN I : ĐẶT VẤN ĐỀ TẾ H Lý chọn đề tài N H Mục tiêu nghiên cứu KI 2.1 Mục tiêu tổng quát Ọ C 2.2 Mục tiêu cụ thể H Đối tượng phạm vi nghiên cứu Đ ẠI 3.1 Đối tượng nghiên cứu G 3.2 Phạm vi nghiên cứu Ờ N Phương pháp nghiên cứu TR Ư Ý nghĩa khoa học thực tiễn 5.1 Ý nghĩa khoa học 5.2 Ý nghĩa thực tiễn Nội dung khóa luận PHẦN II: NỘI DUNG VÀ KẾT QUẢ NGHIÊN CỨU CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1.1 Bài toán người du lịch 1.1.1 Lịch sử toán SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang ii GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp 1.1.2 Phát biểu tốn 1.2 Độ phức tạp toán người du lịch 1.2.1 Độ phức tạp tính tốn 1.2.2 Độ phức tạp tính tốn tốn người du lịch 12 1.3 Thuật toán di truyền 12 1.3.1 Lịch sử thuật toán di truyền 12 1.3.2 Đặc điểm thuật toán di truyền 13 U Ế 1.3.3 Áp dụng thuật toán di truyền cho toán người du lịch 18 TẾ H 1.4 Ứng dụng thuật toán di truyền 19 1.5 Các cơng trình liên quan 21 KI N H CHƯƠNG 2: PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN 32 Ọ C 2.1 Giải thuật đề xuất 32 H 2.2 Mã hóa đường 32 ẠI 2.3 Sơ đồ lớp 34 N G Đ 2.4 Xây dựng chương trình 34 Ờ 2.4.1 Lớp DuongDi 35 TR Ư 2.4.2 Lớp QuanThe 39 2.4.3 Lớp ThuatToanDiTruyen 41 2.4.4 Winform Form1 44 2.4.5 Winform Form 49 2.4.6 Hàm Main 52 2.5 Giới thiệu chương trình 52 CHƯƠNG 3: THÍ NGHIỆM VÀ ĐÁNH GIÁ 55 3.1 Mơ tả tốn vào thực tế 55 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang iii GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp 3.2 Kết chạy chương trình mẫu thí nghiệm 58 3.3.Thí nghiệm chương trình với số thành phố tăng dần 60 3.4 Kết luận 61 3.5 So sánh Thuật toán di truyền với kỹ thuật tối ưu khác 62 PHẦN III: KẾT LUẬN VÀ KIẾN NGHỊ .63 Kết đạt 63 Đóng góp thực tiễn 63 U Ế Hạn chế hướng phát triển 64 TR Ư Ờ N G Đ ẠI H Ọ C KI N H TẾ H DANH MỤC TÀI LIỆU THAM KHẢO 65 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang iv GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp DANH MỤC HÌNH VẼ Hình 1: Lịch sử tốn Hình 2: Đường khoảng cách điểm Hình 3: Máy Turing 10 Hình 4: Quan hệ lớp độ phức tạp quan trọng 12 Hình 5: Sơ đồ Giải thuật thuật tốn di truyền 15 U Ế Hình 1: Sơ đồ lớp cho thuật tốn di truyền 34 TẾ H Hình 2: Giao diện Form 53 Hình 3: Giao diện Form 54 N H Hình 1: Hình địa điểm chọn từ Google Map 56 Ọ C KI Hình 2: Biểu đồ thời gian chạy thuật toán di truyền số địa điểm tăng TR Ư Ờ N G Đ ẠI H lên 61 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang v GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp DANH MỤC BẢNG BIỂU Bảng 1: Khoảng cách địa điểm Bảng 2: Các lớp độ phức tạp 11 Bảng 1: Mẫu thí nghiệm địa điểm 55 Bảng 2: Mẫu thí nghiệm 10 địa điểm 56 Bảng 3: Mẫu thí nghiệm tên 50 địa điểm 57 TR Ư Ờ N G Đ ẠI H Ọ C KI N H TẾ H U Ế Bảng 1: Thời gian chạy thuật toán qua địa điểm 60 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang vi GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp DANH MỤC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt TSP Travelling Salesman Problem Bài toán người du lịch GA Genetic Algorithm Thuật toán di truyền Jobshop Scheduling Problem Bài toán lập lịch Job Shop Hàm sở bán kính Radial Basis Function TR Ư Ờ N G Đ ẠI H Ọ C KI N H TẾ H U RBF Ế JSP SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang vii GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp PHẦN I : ĐẶT VẤN ĐỀ Lý chọn đề tài Hiện ngành khoa học máy tính, việc tìm kiếm lời giải tối ưu cho tốn vấn đề ln nhà khoa học đặc biệt quan tâm Mục đích thuật tốn tìm kiếm lời giải tìm lời giải tối ưu cho toán thời gian nhỏ Với khơng gian tìm kiếm lớn có lời giải cách tối ưu vấn đề khó khăn cho thuật tốn Từ cần thiết phải có thuật giải tốt sử dụng kỹ thuật trí tuệ nhân tạo để giải tốt tốn có khơng gian lớn Bài tốn người du lịch (Travelling Saleman Problem - TSP) nêu lần U Ế đầu 1930 toán nghiên cứu rộng rãi lĩnh vực khoa học máy TẾ H tính Nó thường dùng làm thước đo cho nhiều phương pháp tối ưu Từ năm 1940 có nhiều báo, cơng trình nghiên cứu giải toán N H Tuy vậy, sau kỷ nghiên cứu, toán chưa giải Vì vậy, KI tốn người du lịch xếp vào danh mục tốn khó - chưa có lời Ọ C giải tối ưu cho dạng toán Tuy nhiên, toán người du lịch lại ẠI gần tối ưu cho loại tốn H ứng dụng nhiều ứng dụng sống hàng ngày Do đó, cần đưa lời giải G Đ Giải thuật di truyền (Genetic Algorithm - GA) kỹ thuật theo q N trình thích nghi tiến hóa quần thể sinh học dựa học thuyết Darwin Ư Ờ GA phương pháp tối ưu ngẫu nhiên cách mô theo tiến hóa TR người hay sinh vật Chính GA trở thành đề tài nghiên cứu thu hút nhiều quan tâm và đem đến nhiều ứng dụng thực tiễn Tư tưởng thuật toán di truyền mô tượng tự nhiên, kế thừa đấu tranh sinh tồn GA thuật giải mục tiêu GA không nhằm đưa lời giải xác tối ưu mà đưa lời giải tương đối tối ưu Thuật toán sử dụng nguyên lý di truyền thích nghi sống cá thể thích nghi tự nhiên Chính hấp dẫn đặc biệt toán người du lịch thuật toán di truyền Đồng thời xuất phát từ nhu cầu tìm đường ngắn với giải thuật tốt cho khơng gian tìm kiếm rộng lớn, áp dụng cho tốn tối ưu tổ hợp SVTH: Hồ Minh Tồn - K48A Tin Học Kinh Tế Trang GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp TR Ư Ờ N G Đ ẠI H Ọ C KI N H TẾ H U Ế Một số hình ảnh Form giao diện chương trình : Hình 2: Giao diện Form SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 53 GVHD: TS Hồ Quốc Dũng TR Ư Ờ N G Đ ẠI H Ọ C KI N H TẾ H U Ế Khóa luận tốt nghiệp Hình 3: Giao diện Form SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 54 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp CHƯƠNG 3: THÍ NGHIỆM VÀ ĐÁNH GIÁ 3.1 Mơ tả tốn vào thực tế Một người bán hàng online muốn giao đơn hàng cho địa điểm khác nhau, biết khoảng cách địa điểm lấy cụ thể Google Map Yêu cầu người giao hàng phải vận chuyển hàng đến địa điểm cần nhận hàng phải đạt tối thiểu chi phí thời gian (thời gian chọn thấp lúc chọn khoảng cách) Để đáp ứng yêu cầu tốn đưa ta phải tìm chu trình đường ngắn nhất, qua điểm lần phải trở lại địa điểm nơi U Ế bắt đầu Cho phép người dùng chọn địa điểm bắt đầu chương trình cho kết H có chu trình ngắn cho người giao hàng đạt yêu cầu qua tất điểm quảng TẾ đường giao hàng tối ưu N H Ứng dụng toán người du lịch để giải trường hợp cụ thể : KI + Người giao hàng Ọ C + Người đưa thư H Dưới liệu 50 địa điểm địa bàn thành phố Huế, thu thập ẠI khoảng cách từ Google Map lập ma trận khoảng cách sau : Đ -Bao gồm mẫu nghiên cứu : TR Ư Ờ N G Mẫu 1: địa điểm Bảng 1: Mẫu thí nghiệm địa điểm Ga Huế Đại Nội Cầu Tràng BigC Huế Chợ Đông Ba Tiền Ga Huế 2200 2000 2500 2500 Đại Nội 2200 1300 2900 1300 Cầu Tràng Tiền 2000 1300 1600 600 BigC Huế 2500 2900 1600 2900 Chợ Đông Ba 2500 1300 600 2900 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 55 GVHD: TS Hồ Quốc Dũng N H TẾ H U Ế Khóa luận tốt nghiệp KI Hình 1: Hình địa điểm chọn từ Google Map H Ọ C Mẫu 2: 10 địa điểm Huế Nội Cầu G Đại Tràng N Ga Đ ẠI Bảng 2: Mẫu thí nghiệm 10 địa điểm BigC Chợ Chợ An Bến xe Bến xe Chùa Trường Huế Đông Cựu Phía Phía Bắc Thiên DHKT Huế Ờ Tiền Mụ Nam 2200 2000 2500 2500 2700 3800 5400 4200 4600 2200 1300 2900 1300 3700 4400 5200 4200 5200 1600 600 2600 3100 6600 5300 3900 2500 2900 1600 2900 300 1600 7800 6500 2400 Chợ Đông 2500 1300 600 2900 3100 4000 6900 5600 4800 2600 300 3100 1100 8100 6800 3300 Ga Huế Đại Nội TR Ư Ba Cầu Tràng 2000 1300 Tiền BigC Huế Ba Chợ An 2700 3700 Cựu SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 56 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp Bến xe Phía 3800 4400 3100 1600 4000 1100 9200 7700 1400 6600 7800 6900 8100 9200 7000 9900 5300 6500 5600 6800 7700 7000 8600 3900 2400 4800 3300 1400 9900 8600 Nam Bến xe Phía 5400 5200 Bắc Chùa Thiên 4200 4200 Mụ Trường 4600 5200 ĐHKT Huế Ế Mẫu 3: 50 địa điểm Trường Ga Huế ĐHNN 11 21 Huế 12 31 ĐHNL 22 Huế ĐHSP 41 Thái Hậu Từ 32 23 Huế Kí Túc Xá Trường Bia Trường 42 Chí Minh 33 Trung tâm Trường Thể dục Cao đẳng Thể thao 43 BigC Huế 14 Bệnh viênh TW 24 Hue Hotel & nghiệp Thiên Huế Huế Bệnh viện Mường 34 Spa Thanh 44 Holiday Ba Khách sạn 15 SaiGon Morin 25 Học viện Âm nhạc Huế SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Đại học 35 Huế Trường đại Trường Đại Học Y Dược Huế Huế Chợ Đông Công Thừa Khách Sạn La Residence Cao đẳng Y tế Huế Cung Bảo tàng Hồ Suối Voi Trung Đ G N Ờ 13 Ư Tiền Trường TR Cầu Tràng Quang KI Niệm Hoàng Ọ C Đại Nội ẠI dục thể chất Tượng Đài Nhà Lưu H Trường Khoa Giáo N H TẾ H U Bảng 3: Mẫu thí nghiệm tên 50 địa điểm 45 Bia Quốc Học Trang 57 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp học Nghệ thuật Trường Chợ An ĐHKH 16 Cựu Trường THPT 26 Huế chuyên Quốc Chợ Tây 36 Lộc Học Huế Chùa 46 Không Bệnh Viện Trường Bến xe Phía Nam ĐHYD 17 Nhà Thờ Đức 27 Huế Mẹ Hằng Cứu Trường Y Học Cổ Truyền 37 47 Thừa Giúp Phía Bắc Phú Cam 28 Phan Bội Châu Tâm Huế Ế KI Ọ C Thiên Mụ Hóa Trung 19 29 H Chùa Chùa Từ Đàm 39 Đ G Trường N 20 TR Huế Ờ ĐHKT Ư 10 Bệnh Viện Đa Khu Công Nghiệp 30 Phú Bài Khoa Hoàng 40 Viết Thắng Quốc tế Âu Lạc Trường U 38 ẠI Nhà Văn không H Nhà Thờ 18 TẾ Bến xe Cảng hàng N H Trung Cấp Huế Thiên Huế Nhà lưu niệm Huyền 48 Đại học Luật - Đại Phú Bài học Huế Trung tâm Cơng Ty giáo dục Cp Đầu Quốc phòng 49 Tư Dệt May Huế- Đại Thiên An Học Huế Phát Cầu Cảng Chân Mây 50 Bệnh Viện Mắt Huế 3.2 Kết chạy chương trình mẫu thí nghiệm Sử dụng file liệu txt tải vào chương trình ta kết sau (chọn điểm bắt đầu): - Mẫu thí nghiệm địa điểm Quãng đường từ đến cuối là: - - - - - Khoảng cách hết chu trình là(m): 8200 Thời gian chạy thuật tốn là: 00:00:00.009 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 58 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp - Mẫu thí nghiệm 10 địa điểm Quãng đường từ đến cuối là: - - - - - - - - - 10 - Khoảng cách di hết chu trình là(m): 33700 Thời gian chạy thuật tốn là: 00:00:00.020 - Mẫu thí nghiệm 20 địa điểm Quãng đường từ đến cuối: - - 18 - 11 - 10 - - - 15 - 17 - - 19 - - 14 - 13 - - 12 - - - 16 - 20 - Khoảng cách hết chu trình là(m): 79390 Thời gian chạy thuật tốn là: 00:00:00.041 Ế - Mẫu thí nghiêm 30 địa điểm H U Quãng đường từ đến cuối: - 23 - 22 - - 29 - 28 - - 11 - - 18 - 15 - 25 - N H Khoảng cách hết chu trình là(m): 106650 TẾ 10 - 14 - 26 - 21 - 13 - 17 - - 16 - 27 - - 24 - 20 - - 19 - - 12 - - 30 - Ọ C - Mẫu thí nghiêm 40 địa điểm KI Thời gian chạy thuật toán là: 00:00:00.071 H Quãng đường từ đến cuối: - 10 - 26 - 16 - 38 - 24 - 32 - - 34 - - 37 - - ẠI 20 - 39 - 17 - - - 19 - 36 - 33 - 11 - 14 - 15 - 28 - 23 - 31 - - - 22 - 29 - 13 - 18 - Đ 12 - 35 - - 27 - 25 - 30 - 21 - 40 - N G Khoảng cách hết chu trình là(m): 295750 Ờ Thời gian chạy thuật toán là: 00:00:01.014 TR Ư - Mẫu thí nghiệm 50 địa điểm Quãng đường từ đến cuối: - 31 - 23 - 10 - 20 - 11 - - 22 - - 39 - 34 - 15 - 14 - 47 - 32 - 28 - 40 - 41 - 33 - 27 - 25 - - 36 - 21 - 12 - 42 - 46 - 19 - 16 - 17 - 35 18 - - - 49 - 26 - 30 - 48 - 44 - - - - 45 - 38 - 43 - 29 - 24 - 13 - 37 - 50 - Khoảng cách hết chu trình là(m): 377800 Thời gian chạy thuật tốn là: 00:00:01.062 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 59 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp 3.3.Thí nghiệm chương trình với số thành phố tăng dần Cho liệu file txt tiến hành đưa liệu vào chạy kết Với số địa điểm ngày tăng lên thời gian chạy chương trình thay đổi Ta có bảng sau đưa kết chạy thử với số địa điểm tăng lên, với khoảng cách ma trận lấy từ file với khoảng cách từ i tới j mét (m)và thời gian thuật toán chạy mili giây (ms) Thời gian chạy chương trình số thành phố tăng dần (tiến hóa qua 1000 hệ) Ế Bảng 1: Thời gian chạy thuật toán qua địa điểm Số địa điểm H U Thời gian thuật toán xử lý (ms) TẾ N H 10 KI 15 Ọ C 20 H 25 ẠI 30 G N 40 Đ 35 20 29 41 54 71 92 1014 1031 50 1062 TR Ư Ờ 45 Từ kết trên, ta đưa biểu đồ biểu thời gian chạy thuật toán di truyền số địa điểm đến 50 địa điểm Qua cho ta thấy số địa điểm tăng lên thời gian chạy thuật toán tăng dần với khoảng cách tương đối nhỏ lần tăng lên địa điểm Cụ thể đến 30 tăng 62(ms) 30 đến 50 tăng 991(ms) nhanh so với thủ công hay thuật tốn khác.Từ cho ta thấy thuật tốn di truyền cho kết thời gian chấp nhận với số địa điểm tăng lên với 50 địa điểm chưa đầy giây SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 60 GVHD: TS Hồ Quốc Dũng N H TẾ H U Ế Khóa luận tốt nghiệp Hình 2: Biểu đồ thời gian chạy thuật toán di truyền số địa điểm Ọ C KI tăng lên 3.4 Kết luận ẠI H Qua kết cho ta thấy thời gian để thuật toán di truyền đưa kết Đ chấp nhận (với 50 địa điểm không giây, trung bình khoảng 0.342 giây) với G số lượng địa điểm ngày tăng tương đối lớn Cho phép người dùng dễ dàng đưa Ờ N định lựa chọn chu trình thích hợp, tối thiểu chi phí thời gian đồng TR Ư thời đưa kết không lâu cho người dùng Hoạt động GA đơn giản mô tiến hóa chọn lọc tự nhiên máy tính quần thể ngẫu nhiên Bên cạnh để tối ưu ta cần hàm thích nghi để chọn cá thể tốt đồng thời loại bỏ cá thể xấu Chung quy lại, GA phương pháp hiệu để giải toán tối ưu tổ hợp cụ thể toán người du lịch thể khóa luận Ngồi thuật tốn di truyền áp dụng vào tốn người du lịch có nhiều hướng khác để phát triển tối ưu tốt cho tốn, nội dung khn khổ khóa luận đề cập đầy đủ Tuy nhiên, kết nêu khóa luận cho ta thấy hiệu thuật tốn di truyền SVTH: Hồ Minh Tồn - K48A Tin Học Kinh Tế Trang 61 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp để giải tốn người du lịch trường hợp cụ thể người giao hàng ưu điểm bật thuật toán 3.5 So sánh Thuật toán di truyền với kỹ thuật tối ưu khác Thuật toán di truyền khác với kỹ thuật tối ưu khác chổ [18] : - Thuật toán di truyền làm việc với mã biến làm việc trực tiếp biến - Hầu hết kỹ thuật tối ưu thông thường tìm kiếm từ đỉnh, thuật tốn di truyền hoạt động tập hợp đỉnh (điểm tối ưu), điều ưu điểm thuật tốn giúp tăng hội tiếp cận tối ưu tồn cục tránh hội tụ sớm Ế điểm cục địa phương H U - Thuật toán di truyền đánh giá hàm mục tiêu để phục vụ trình tìm kiếm, TẾ ứng dụng cho toán tối ưu (liên tục hay rời rạc) N H -Thuật toán di truyền thuộc lớp thuật toán xác suất, thao tác TR Ư Ờ N G Đ ẠI H Ọ C KI thuật toán di truyền dựa khả tích hợp ngẫu nhiên q trình xử lý SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 62 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp PHẦN III: KẾT LUẬN VÀ KIẾN NGHỊ Kết đạt Trong khóa luận sử dụng thuật tốn di truyền thuật tốn có tư tưởng dựa tiến hóa tự nhiên tốn người du lịch để tìm chu trình ngắn để lại thành phố Đồng thời chứng minh tiềm to lớn tính ưu việt thuật giải di truyền để tìm kiếm lời giải tối ưu cho nhiều dạng vấn đề khác Ế Việc áp dụng thuật giải di truyền để giải toán trình H U bày cách cụ thể rõ ràng Thể phương pháp tiếp cận tinh tế để giải TẾ số lớp tốn lĩnh vực tìm chu trình đường ngắn, N H tốn khó với khơng gian tìm kiếm lớn để tìm lời giải toán đưa Với KI cách tiếp cận thuật tốn di truyền cho giảm thiểu chi phí, cơng Ọ C sức cho việc tính toán nhiều mà đạt kết gần tối ưu H Đã xây dựng chương trình chạy Winform hỗ trợ cho người ẠI giao hàng tìm lộ trình đường ngắn qua tất điểm cần giao hàng góp Đ phần giúp cho người giao hàng tối thiểu chi phí thời gian giao hàng N G đồng thời đưa kết không lâu cho người dùng Ờ Bài báo cáo nêu lý thuyết toán người du lịch TR Ư thuật toán di truyền lịch sử, lý thuyết đồ thị, ứng dụng, đặc điểm, Trình bày cách cài đặt thuật tốn di truyền ngơn ngữ C# cụ thể Winform C# áp dụng giải toán người du lịch với liệu ma trận khoảng cách định dạng file txt để đưa lời giải tối ưu giúp người du lịch tiết kiệm chi phí thời gian Đóng góp thực tiễn Với vấn đề nêu đề tài giúp cho ta thấy cách tiếp cận toán cách rõ ràng, dễ hiểu, hướng giải việc đưa lời giải cho toán tối ưu tương tự TSP Đồng thời hiểu ứng dụng thuật tốn di truyền để áp dụng nghiên cứu chuyên sâu thuật toán SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 63 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp áp dụng vào lĩnh vực cách hiệu Bên cạnh đề tài gợi ý cho cách tiếp cận khác toán tối ưu tổ hợp Hạn chế hướng phát triển - Hạn chế: Giải thuật di truyền phần lớn phụ thuộc vào độ “may mắn” để tìm kết Cách tiếp cận giải thuật di truyền cách tiếp cận gần tối ưu kết đạt phương án tiệm cận tối ưu Với số lượng địa điểm cần qua lớn (khoảng lớn 20 địa điểm ta phải đánh giá 2432902008176640000 tuyến đường khác ) giải thuật U Ế thường mang lại giá trị tiệm cận tối ưu H Thuật toán tối ưu phân tích nhiều yếu tố ảnh hưởng đến thuật tốn TẾ Lộ trình tối ưu sát phù hợp với thực tế ta quan tâm thêm yếu N H tố thời tiết, chất lượng đường, tình trạng giao thơng… KI Giải thuật di truyền giải tốn tối ưu với n biến vào Tuy Ọ C nhiên với số lượng nhiều giá trị hàm mục tiêu đạt thường không H gần với kết tối ưu thực Muốn khắc phục phải tăng số lượng vòng lặp ẠI thòi gian thuật tốn chạy lâu N kết ý muốn G Đ - Hướng phát triển: Tiếp tục nghiên cứu tiếp đề tài để hồn thiện có Ư Ờ Áp dụng thuật toán di truyền vào số toán tối ưu khác TR Trong tương lai, em tìm tòi, học hỏi thêm nhằm hồn thiện đề tài có điều kiện nghiên cứu chuyên sâu thuật toán di truyền để giải toán có tính phức tạp cao SVTH: Hồ Minh Tồn - K48A Tin Học Kinh Tế Trang 64 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp DANH MỤC TÀI LIỆU THAM KHẢO (2017) Bài toán người bán hàng Wikipedia tiếng Việt, Travelling salesman problem - Wikipedia (2017) Lý thuyết độ phức tạp tính tốn Wikipedia tiếng Việt, Antonick G (2014) Hamilton’s Icosian Game Wordplay Blog, Dantzig G., Fulkerson R., Johnson S (1954) Solution of a Large-Scale Ế Traveling-Salesman Problem J Oper Res Soc Am, 2(4), 393–410 TẾ spanning trees: Part II Math Program, 1(1), 6–25 H U Held M Karp R.M (1971) The traveling-salesman problem and minimum N H Grötschel M Holland O (1991) Solution of large-scale symmetric travelling KI salesman problems Math Program, 51(1–3), 141–202 Ọ C Padberg M Rinaldi G (1991) A Branch-and-Cut Algorithm for the Resolution H of Large-Scale Symmetric Traveling Salesman Problems SIAM Rev, 33(1), 60– ẠI 100 Đ Applegate D.L., Bixby R.E., Chvátal V cộng (2006), The Traveling N G Salesman Problem: A Computational Study, Princeton University Press Ờ 10 Reinelt G (1991) TSPLIB—A Traveling Salesman Problem Library ORSA J TR Ư Comput, 3(4), 376–384 11 Fraser A.S (1962) Simulation of genetic systems J Theor Biol, 2(3), 329–346 12 Holland J.H (1992), Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, MIT Press 13 Tran X.T Giới thiệu thuật toán di truyền 14 Tài liệu Bài tập lớn trí tuệ nhân tạo tìm hiểu giải thuật di truyền 15 GIẢI THUẬT DI TRUYỀN | Hong Phan - Academia.edu 16 tutorialspoint.com Các lĩnh vực ứng dụng thuật toán di truyền www.tutorialspoint.com, SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 65 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp 17 Đề tài Tìm hiểu giải thuật di truyền ứng dụng giải toán lập lịch - Luận văn, đồ án, đề tài tốt nghiệp 18 Sư K GIẢI THUẬT DI TRUYỀN (GAs) VÀ CÁC ỨNG DỤNG 19 Meta-heuristic kết hợp tuật tốn giải di truyền với thơng tin thống kê xác xuất giải toán người du lịch 20 Hữu Mùi N Đình Hòa V (2014) Một thuật toán di truyền hiệu cho tốn lập lịch Job shop Tạp Chí Khoa Học Và Công Nghệ, 50(5), 567–579 21 Một giải pháp tiến hóa cho tốn thời khóa biểu 22 CS16031 baibao anh Hung.pdf U Ế 23 TT_NguyenTranHiep.pdf H 24 Carter A.E Ragsdale C.T (2006) A new approach to solving the multiple TẾ traveling salesperson problem using genetic algorithms Eur J Oper Res, 175(1), N H 246–257 KI 25 Smith S.L Imeson F (2017) GLNS: An effective large neighborhood search Ọ C heuristic for the Generalized Traveling Salesman Problem Comput Oper Res, 87, H 1–19 ẠI 26 Ezugwu A.E.-S Adewumi A.O (2017) Discrete Symbiotic Organisms Search Đ Algorithm for Travelling Salesman Problem Expert Syst Appl N G 27 Yang Z., Xiao M.-Q., Ge Y.-W cộng (2017) A double-loop hybrid TR Oper Res Ư Ờ algorithm for the traveling salesman problem with arbitrary neighbourhoods Eur J 28 Chen Y., Jia Z., Ai X cộng (2017) A modified two-part wolf pack search algorithm for the multiple traveling salesmen problem Appl Soft Comput, 61, 714–725 29 Osaba E., Yang X.-S., Diaz F cộng (2016) An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems Eng Appl Artif Intell, 48, 59–71 30 Zhang H Zhou J (2016) Dynamic multiscale region search algorithm using vitality selection for traveling salesman problem Expert Syst Appl, 60, 81–95 SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 66 GVHD: TS Hồ Quốc Dũng Khóa luận tốt nghiệp 31 Chen X., Zhou Y., Tang Z cộng (2017) A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical travelling salesman problems Appl Soft Comput, 58, 104–114 32 Performance analyses over population seeding techniques of the permutationcoded genetic algorithm: An empirical study based on traveling salesman problems - ScienceDirect 33 Lin Y., Bian Z., Liu X (2016) Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing–tabu search algorithm to solve the symmetrical traveling salesman problem Appl Soft Comput, 49, 937–952 U Ế 34 Albayrak M Allahverdi N (2011) Development a new mutation operator to H solve the traveling salesman problem by aid of genetic algorithms Expert Syst TẾ Appl, 38(3), 1313–1320 N H 35 Viblo | Free service for technical knowledge sharing KI 36 Giải Thuật Lập Trình · Đồ thị — Introduction to Algorithmic Graph Theory Ọ C 37 (2016) Giải thuật tìm kiếm Wikipedia tiếng Việt, H 38 Panda A Pani S (2016) A Symbiotic Organisms Search algorithm with ẠI adaptive penalty function to solve multi-objective constrained optimization Đ problems Appl Soft Comput, 46, 344–360 Ờ ebook N G 39 Đề tài Thuật toán di truyền ứng dụng giải toán người du lịch - Tài liệu, 41 TR Ư 40 Phương pháp Math.Sin (Đôi) (Hệ thống) Tuần 10 - Học liệu: Ứng dụng thuật giải GA toán du lịch (tham khảo) | Hai V Pham, PhD - Academia.edu SVTH: Hồ Minh Toàn - K48A Tin Học Kinh Tế Trang 67 ... + Ứng dụng giải thuật di truyền cho toán người du lịch TẾ 2.2 M c tiêu c thể + Nghiên c u lịch sử, tư tưởng, lý thuyết sở lý luận toán N H người du lịch thuật toán di truyền KI + Nghiên c u c ch... nghiên c u Ờ N 3.1 Đối tượng nghiên c u Ư + Bài toán người du lịch TR + Thuật toán di truyền 3.2 Phạm vi nghiên c u Bao gồm: + Thuật toán di truyền + Bài toán người du lịch + C ch áp dụng thuật toán. .. nội dung, độ ph c tạp toán người du lịch Lịch sử, tư tưởng, bư c th c thuật toán di truyền - Chương 2: Thiết kế form áp dụng thuật toán di truyền, toán người du lịch để tìm chu trình ngắn Nội dung