Tài liệu áp dụng giải thuật di truyền giải bài toán cực tiểu hoá độ trễ

BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------BAN HÀ BẰNG BAN HÀ BẰNG CÔNG NGHỆ THÔNG TIN ÁP DỤNG GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN CỰC TIỂU HOÁ ĐỘ TRỄ LUẬN VĂN THẠC SĨ KHOA HỌC 2006-2008 Hà Nội 11/2008 MỤC LỤC LỜI CẢM ƠN .................................................................... Error! Bookmark not defined. LỜI CAM ĐOAN ............................................................... Error! Bookmark not defined. MỤC LỤC ..................................................................................................................... 1 Danh mục hình vẽ ........................................................... Error! Bookmark not defined. Danh mục bảng ............................................................... Error! Bookmark not defined. Danh mục thuật ngữ ....................................................... Error! Bookmark not defined. LỜI NÓI ĐẦU ................................................................... Error! Bookmark not defined. CHƯƠNG 1 GIỚI THIỆU BÀI TOÁN ............................... Error! Bookmark not defined. 1.1 Phát biểu bài toán ............................................... Error! Bookmark not defined. 1.2 Mô hình đồ thị của bài toán ................................. Error! Bookmark not defined. 1.3 Các giải thuật giải bài toán .................................. Error! Bookmark not defined. 1.4 Đề xuất hướng áp dụng giải thuật di truyền ........ Error! Bookmark not defined. 1.5 Nhiệm vụ của luận văn ........................................ Error! Bookmark not defined. CHƯƠNG 2 GIẢI THUẬT DI TRUYỀN............................ Error! Bookmark not defined. 2.1 Một số khái niệm cơ bản trong sinh học .............. Error! Bookmark not defined. 2.1.1 Di truyền học ................................................ Error! Bookmark not defined. 2.1.2 Thuyết chọn lọc tự nhiên ............................. Error! Bookmark not defined. 2.1.3 Độ thích nghi và khung cảnh thích nghi ....... Error! Bookmark not defined. 2.2 Các vấn đề cơ bản của giải thuật di truyền ......... Error! Bookmark not defined. 2.2.1 Cấu trúc của giải thuật di truyền .................. Error! Bookmark not defined. 2.2.3. Các kỹ thuật biểu diễn ................................ Error! Bookmark not defined. 2.2.4 Phép toán di truyền ...................................... Error! Bookmark not defined. 2.2.5 Các tham số trong giải thuật di truyền ......... Error! Bookmark not defined. 2.2.6 Phương pháp lựa chọn ................................ Error! Bookmark not defined. 2.3 Cơ sở lý thuyết của giải thuật di truyền ............... Error! Bookmark not defined. 2.3.1 Thuộc tính của lược đồ ................................ Error! Bookmark not defined. 2.3.2 Phép toán di truyền ...................................... Error! Bookmark not defined. 2.3.5 Điều kiện dừng của giải thuật ...................... Error! Bookmark not defined. 2.3.6 Sự hội tụ của giải thuật ................................ Error! Bookmark not defined. 2.4 Giải thuật di truyền kết hợp ................................. Error! Bookmark not defined. 2.4.1 Giải thuật tìm kiếm địa phương.................... Error! Bookmark not defined. 2.4.1.1 Giải thuật 2-opt ....................................... Error! Bookmark not defined. 2.4.1.2 Giải thuật 3-opt ....................................... Error! Bookmark not defined. 2.4.1.3 Giải thuật luyện kim ................................ Error! Bookmark not defined. 2.4.2 Kết hợp hai giải thuật ................................... Error! Bookmark not defined. CHƯƠNG 3 THIẾT KẾ GIẢI THUẬT DI TRUYỀN ........... Error! Bookmark not defined. CHO BÀI TOÁN CỰC TIỂU HOÁ ĐỘ TRỄ ...................... Error! Bookmark not defined. 3.1 Kỹ thuật biểu diễn................................................ Error! Bookmark not defined. 3.1.1 Kỹ thuật biểu diễn nhị phân ......................... Error! Bookmark not defined. 3.1.2 Kỹ thuật biểu diễn liền kề ............................. Error! Bookmark not defined. 3.1.3 Kỹ thuật biểu diễn thứ tự ............................. Error! Bookmark not defined. 3.1.4 Kỹ thuật biểu diễn đường đi ......................... Error! Bookmark not defined. 3.2 Phép toán di truyền ............................................. Error! Bookmark not defined. 3.2.1 Phép toán lai ghép ....................................... Error! Bookmark not defined. 3.2.2 Phép toán đột biến ....................................... Error! Bookmark not defined. 3.3 Phương pháp lựa chọn ....................................... Error! Bookmark not defined. 3.4 Các tham số ........................................................ Error! Bookmark not defined. 3.5 Điều kiện dừng giải thuật .................................... Error! Bookmark not defined. 3.6 Giải thuật di truyền kết hợp ................................. Error! Bookmark not defined. 3.7 Một số đánh giá ban đầu ..................................... Error! Bookmark not defined. 3.7.1 Xác suất lai ghép ......................................... Error! Bookmark not defined. 3.7.2 Xác suất đột biến ......................................... Error! Bookmark not defined. 3.7.3 Toán tử di truyền.......................................... Error! Bookmark not defined. 3.7.4 Kích thước nhóm ......................................... Error! Bookmark not defined. 3.7.5 Kích thước quần thể .................................... Error! Bookmark not defined. 3.7.6 Giải thuật di truyền kết hợp .......................... Error! Bookmark not defined. CHƯƠNG 4 TÍNH TOÁN THỰC NGHIỆM ....................... Error! Bookmark not defined. 4.1 Mục đích thực nghiệm ......................................... Error! Bookmark not defined. 4.1.1 Giải thuật GA ............................................... Error! Bookmark not defined. 4.1.2 Giải thuật LS ................................................ Error! Bookmark not defined. 4.1.3 Giải thuật GAH ............................................. Error! Bookmark not defined. 4.2 Thiết kế và xây dựng chương trình ..................... Error! Bookmark not defined. 4.2.1 Thiết kế chương trình .................................. Error! Bookmark not defined. 4.2.2 Xây dựng chương trình ................................ Error! Bookmark not defined. 4.3 Hướng dẫn sử dụng ............................................ Error! Bookmark not defined. 4.4 Mô tả dữ liệu thực nghiệm .................................. Error! Bookmark not defined. 4.5 Kết quả thực nghiệm ........................................... Error! Bookmark not defined. 4.5.1 Thực nghiệm lựa chọn các tham số............. Error! Bookmark not defined. 4.5.2 Thực nghiệm với bộ dữ liệu TSPLIB95 ........ Error! Bookmark not defined. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................ Error! Bookmark not defined. TÀI LIỆU THAM KHẢO ..................................................... Error! Bookmark not defined. Phụ lục 1: Các bảng thực nghiệm ..................................... Error! Bookmark not defined. Phụ lục 2: Mô tả nội dung đĩa CD kèm theo ..................... Error! Bookmark not defined. -1- LỜI CẢM ƠN Để hoàn thành Luận Văn Tốt nghiệp Cao Học giai đoạn 2006-2008, em xin chân thành cảm ơn thầy giáo PGS.TS. Nguyễn Đức Nghĩa đã trực tiếp hướng dẫn và tận tình giúp đỡ em trong quá trình nghiên cứu. Em xin gửi lời cảm ơn tới các thầy cô trong Khoa Công Nghệ Thông Tin, cũng như các thầy cô trong trường Đại Học Bách Khoa Hà Nội đã truyền thụ những kiến thức bổ ích trong quá trình em học tập và nghiên cứu tại trường. Em xin gửi lời cảm ơn tới gia đình và bạn bè đã giúp đỡ động viên em trong quá trình học tập và hoàn thành Luận Văn Tốt nghiệp lần này. Mặc dù có nhiều cố gắng nhưng do thời thời gian và kiến thức còn hạn chế nên luận văn vẫn còn có nhiều thiếu sót. Em rất mong nhận được những ý kiến đóng góp quý báu từ thầy, cô và các bạn. Hà Nội, ngày 11 tháng 11 năm 2008. Học viên thực hiện: Ban Hà Bằng. -2- LỜI CAM ĐOAN Tôi xin cam đoan luận văn cao học này là kết quả nghiên cứu tôi trong suốt một năm qua, không sao chép nguyên si từ bất kỳ công trình nghiên cứu nào. Những kiến thức tham khảo để hoàn thành luận văn, tôi đều chú thích cẩn thận trong mục tài liệu tham khảo. -3- MỤC LỤC LỜI CẢM ƠN ................................................................................................................ 1 LỜI CAM ĐOAN ........................................................................................................... 2 MỤC LỤC...................................................................................................................... 3 Danh mục hình vẽ ....................................................................................................... 6 Danh mục bảng ........................................................................................................... 9 Danh mục thuật ngữ ................................................................................................. 12 LỜI NÓI ĐẦU .............................................................................................................. 13 CHƯƠNG 1 GIỚI THIỆU BÀI TOÁN .......................................................................... 15 1.1 Phát biểu bài toán .............................................................................................. 15 1.2 Mô hình đồ thị của bài toán ............................................................................... 16 1.3 Các giải thuật giải bài toán ................................................................................ 18 1.4 Đề xuất hướng áp dụng giải thuật di truyền ...................................................... 19 1.5 Nhiệm vụ của luận văn ...................................................................................... 21 CHƯƠNG 2 GIẢI THUẬT DI TRUYỀN ...................................................................... 23 2.1 Một số khái niệm cơ bản trong sinh học ............................................................ 23 2.1.1 Di truyền học .............................................................................................. 23 2.1.2 Thuyết chọn lọc tự nhiên ............................................................................ 24 2.1.3 Độ thích nghi và khung cảnh thích nghi ..................................................... 25 2.2 Các vấn đề cơ bản của giải thuật di truyền ....................................................... 27 2.2.1 Cấu trúc của giải thuật di truyền................................................................. 27 2.2.3. Các kỹ thuật biểu diễn ............................................................................... 28 2.2.4 Phép toán di truyền .................................................................................... 30 2.2.5 Các tham số trong giải thuật di truyền ........................................................ 32 2.2.6 Phương pháp lựa chọn .............................................................................. 32 2.3 Cơ sở lý thuyết của giải thuật di truyền ............................................................. 34 2.3.1 Thuộc tính của lược đồ .............................................................................. 34 2.3.2 Phép toán di truyền .................................................................................... 35 2.3.5 Điều kiện dừng của giải thuật..................................................................... 38 2.3.6 Sự hội tụ của giải thuật .............................................................................. 39 2.4 Giải thuật di truyền kết hợp ............................................................................... 39 2.4.1 Giải thuật tìm kiếm địa phương .................................................................. 39 2.4.1.1 Giải thuật 2-opt ..................................................................................... 41 -42.4.1.2 Giải thuật 3-opt ..................................................................................... 41 2.4.1.3 Giải thuật luyện kim .............................................................................. 42 2.4.2 Kết hợp hai giải thuật ................................................................................. 45 CHƯƠNG 3 THIẾT KẾ GIẢI THUẬT DI TRUYỀN...................................................... 48 CHO BÀI TOÁN CỰC TIỂU HOÁ ĐỘ TRỄ ................................................................ 48 3.1 Kỹ thuật biểu diễn .............................................................................................. 48 3.1.1 Kỹ thuật biểu diễn nhị phân ........................................................................ 48 3.1.2 Kỹ thuật biểu diễn liền kề ........................................................................... 49 3.1.3 Kỹ thuật biểu diễn thứ tự ............................................................................ 50 3.1.4 Kỹ thuật biểu diễn đường đi ....................................................................... 51 3.2 Phép toán di truyền ........................................................................................... 52 3.2.1 Phép toán lai ghép ..................................................................................... 52 3.2.2 Phép toán đột biến ..................................................................................... 58 3.3 Phương pháp lựa chọn...................................................................................... 60 3.4 Các tham số ...................................................................................................... 61 3.5 Điều kiện dừng giải thuật ................................................................................... 62 3.6 Giải thuật di truyền kết hợp ............................................................................... 62 3.7 Một số đánh giá ban đầu ................................................................................... 63 3.7.1 Xác suất lai ghép........................................................................................ 63 3.7.2 Xác suất đột biến ....................................................................................... 64 3.7.3 Toán tử di truyền ........................................................................................ 64 3.7.4 Kích thước nhóm ....................................................................................... 65 3.7.5 Kích thước quần thể .................................................................................. 65 3.7.6 Giải thuật di truyền kết hợp ........................................................................ 65 CHƯƠNG 4 TÍNH TOÁN THỰC NGHIỆM ................................................................. 68 4.1 Mục đích thực nghiệm ....................................................................................... 68 4.1.1 Giải thuật GA.............................................................................................. 68 4.1.2 Giải thuật LS .............................................................................................. 75 4.1.3 Giải thuật GAH ........................................................................................... 78 4.2 Thiết kế và xây dựng chương trình ................................................................... 80 4.2.1 Thiết kế chương trình ................................................................................. 80 4.2.2 Xây dựng chương trình .............................................................................. 82 4.3 Hướng dẫn sử dụng .......................................................................................... 84 4.4 Mô tả dữ liệu thực nghiệm ................................................................................. 91 -54.5 Kết quả thực nghiệm ......................................................................................... 95 4.5.1 Thực nghiệm lựa chọn các tham số ........................................................... 95 4.5.2 Thực nghiệm với bộ dữ liệu TSPLIB95 .................................................... 112 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN..................................................................... 116 TÀI LIỆU THAM KHẢO ............................................................................................. 119 Phụ lục 1: Các bảng thực nghiệm ............................................................................. 121 Phụ lục 2: Mô tả nội dung đĩa CD kèm theo .............................................................. 139 -6- Danh mục hình vẽ Hình 1.1 Đường đi tối ưu MLP trong file dữ liệu Berlin 52 .......................................... 17 Hình 1.2 Đường đi tối ưu TSP trong file dữ liệu Berlin 52 ........................................... 17 Hình 2.1 Cấu trúc nhiễm sắc thể .................................................................................... 24 Hình 2.2 Khung cảnh thích nghi của quần thế ............................................................... 26 Hình 2.3 Quá trình tiến hoá độ thích nghi của quần thể ................................................ 26 Hình 2.4 Các bước trong giải thuật di truyền................................................................ 28 Hình 2.5 Mô tả kỹ thuật biểu diễn cây ........................................................................... 30 Hình 2.6 Minh hoạ phép toán di truyền ......................................................................... 31 Hình 2.7 Hình vẽ mô tả sự hội tụ của giải thuật di truyền ............................................. 39 Hình 2.8 Hình minh hoạ các bước của giải thuật tìm kiếm địa phương ........................ 40 Hình 2.9 Mô tả cách thức tìm kiếm của giải thuật tìm kiếm địa phương ...................... 40 Hình 2.10 Giải thuật tìm kiếm địa phương 2-opt ........................................................... 41 Hình 2.11 Giải thuật tìm kiếm địa phương 3-opt ........................................................... 42 Hình 2.12 Hình mô tả giải thuật kết hợp ........................................................................ 45 Hình 3.1 Mô tả phép toán PMX ..................................................................................... 53 Hình 3.2 Mô tả phép toán CX ........................................................................................ 54 Hình 3.3 Mô tả phép toán CX ........................................................................................ 56 Hình 3.4 Mô tả phép toán DM ....................................................................................... 58 Hình 3.4 Mô tả phép toán ISM....................................................................................... 59 Hình 3.5 Mô tả phép toán SIM....................................................................................... 59 Hình 3.7 Mô tả phép toán SM ........................................................................................ 60 Hình 4.1 Lược đồ mô tả các bước của giải thuật GA .................................................... 69 Hình 4.2 Lược đồ mô tả bước xây dựng quần thể ban đầu ............................................ 70 Hình 4.3 Lược đồ mô tả bước lựa chọn tournament ...................................................... 71 Hình 4.4 Lược đồ mô tả bước thực hiện của toán tử OX2 ............................................. 72 Hình 4.5 Lược đồ mô tả bước thực hiện của toán tử POS ............................................. 73 Hình 4.6 Lược đồ mô tả bước thực hiện của toán tử đột biến DM ................................ 74 Hình 4.7 Lược đồ mô tả bước thay thế cá thể có tổng độ trễ cao .................................. 74 Hình 4.8 Lược đồ mô tả các bước tạo lời giải ban đầu S .............................................. 75 -7- Hình 4.9 Lược đồ mô tả các bước trong giải thuật 2-opt .............................................. 76 Hình 4.10 Lược đồ mô tả các bước trong giải thuật 3-opt ............................................. 77 Hình 4.11 Lược đồ mô tả các bước trong giải thuật luyện kim ..................................... 78 Hình 4.12 Lược đồ mô tả các bước trong giải thuật di truyền kết hợp .......................... 79 Hình 4.13 Một số chức năng chính của chương trình .................................................... 81 Hình 4.14 Sơ đồ minh hoạ các bước thực hiện của chương trình .................................. 82 Hình 4.15 Giao diện chính của chương trình ................................................................. 84 Hình 4.16 Giao diện bước chọn chức năng nạp dữ liệu ................................................. 85 Hình 4.17 Giao diện nhập dữ liệu từ file .txt ................................................................. 86 Hình 4.18 Toạ độ các đỉnh hiển trên khung hình ........................................................... 87 Hình 4.19 Giao diện bước chọn giải thuật ..................................................................... 88 Hình 4.20 Giao diện bước nhập tham số cho giải thuật GA .......................................... 89 Hình 4.21 Giao diện bước nhập tham số cho giải thuật GAH ....................................... 89 Hình 4.22 Giao diện bước chạy chương trình ................................................................ 90 Hình 4.23 Giao diện hiển kết quả giải thuật .................................................................. 91 Hình 4.24 Hình biểu diễn sự phân bố các điểm trong Eil101 ........................................ 93 Hình 4.25 Hình biểu diễn sự phân bố các điểm trong Berlin52..................................... 93 Hình 4.26 Hình biểu diễn sự phân bố các điểm trong Pr13 ........................................... 94 Hình 4.27 Hình biểu diễn sự phân bố các điểm trong Ts225......................................... 94 Hình 4.28 So sánh kết quả lời giải với ........................................................................... 99 N/Nt = 20, POS + DM, Pcrossover = (0.6, 0.7, 0.8, 0.9), Pmutation = (0.01, 0.02, 0.03)....... 99 Hình 4.29 So sánh kết quả lời giải với ........................................................................... 99 N/Nt = 20, OX2 + DM, Pcrossover = (0.6, 0.7, 0.8, 0.9), Pmutation = (0.01, 0.02, 0.03) ...... 99 Hình 4.30 So sánh kết quả lời giải hai phép toán lai ghép POS và OX2 với............... 100 N/Nt = 20, Pcrossover = 0.6, Pmutation = 0.02 .................................................................... 100 Hình 4.31 So sánh kết quả lời giải với ......................................................................... 103 N/Nt = (5, 10, 20, 40), POS + DM, Pcrossover = 0.6, Pmutation = 0.2 ............................... 103 Hình 4.32 So sánh kết quả lời giải với ......................................................................... 103 N/Nt = (5, 10, 20, 40), OX2 + DM, Pcrossover = 0.6, Pmutation = 0.2 ............................... 103 Hình 4.33 So sánh kết quả lời giải với ......................................................................... 105 N/Nt = (20, 30, 40), POS + DM, Pcrossover = 0.6, Pmutation = 0.2, N > 100 ................... 105 -8- Hình 4.34 So sánh kết quả lời giải với (N/Nt = 20, POS + DM, ................................. 107 Pcrossover = (0.6, 0.1), Pmutation = (0.2, 0.00) ................................................................... 107 Hình 4.35 So sánh kết quả lời giải với ......................................................................... 109 N = 20Nt, POS + DM, Pcrossover = 0.6, Pmutation = 0.02, Nk = 5, 10, 15 ........................ 109 Hình 4.36 So sánh kết quả lời giải ............................................................................... 111 N/Nt = 20, POS + DM, Pcrossover = 0.6, Pmutation = 0.02, các giải thuật khác nhau ........ 111 Hình 4.37 So sánh kết quả lời giải ............................................................................... 114 N/Nt = 20, POS + DM, Pcrossover = 0.6, Pmutation = 0.02, GA, GAH, LS, AA .............. 114 -9- Danh mục bảng Bảng 2.1 Bảng so sánh khái niệm giữa thuyết nhiệt động lực học và bài toán tối ưu ... 43 Bảng 4.1 So sánh sự phân bố các đỉnh trong các thành phố .......................................... 92 Bảng 4.2 Kết quả thực nghiệm N/Nt = 20, OX2 + DM, ................................................ 97 Nk = 5, Pcrossover = (0.9, 0.8, 0.7, 0.6), Pmutation = (0.01, 0.02, 0.03)................................. 97 Bảng 4.3 Kết quả thực nghiệm N/Nt = 20, POS + DM, ................................................ 98 Nk = 5, Pcrossover = (0.9, 0.8, 0.7, 0.6), Pmutation = (0.01, 0.02, 0.03)................................. 98 Bảng 4.4 Kết quả thực nghiệm ..................................................................................... 101 N/Nt = (5, 10, 40), POS + DM, Pcrossover = 0.6, Pmutation = 0.02, Nk = 5 ...................... 101 Bảng 4.5 Kết quả thực nghiệm N/Nt = (5, 10, 40), OX2 + DM, Pcrossover = 0.6, Pmutation = 0.02, Nk = 5 ...................... 102 Bảng 4.6 Kết quả thực nghiệm ..................................................................................... 104 N/Nt = (20, 30, 40), POS + DM, Pcrossover = 0.6, Pmutation = 0.02, Nt > 100, Nk = 5 .... 104 Bảng 4.7 Kết quả thực nghiệm Pcrossover = 0.1, Pmutation = 0.02, N/Nt = 20, Nk = 5 ...... 106 Bảng 4.7 Kết quả thực nghiệm Pcrossover = 0.6, Pmutation = 0.00, N/Nt = 20, Nk = 5 ...... 107 Bảng 4.9 Kết quả thực nghiệm Pcrossover = 0.6, Pmutation = 0.02, N/Nt = 20, Nk = 10 .... 108 Bảng 4.10 Kết quả thực nghiệm Pcrossover = 0.6, Pmutation = 0.02, N/Nt = 20, Nk = 15... 109 Bảng 4.11 Kết quả thực nghiệm ................................................................................... 110 Pcrossover = 0.6, Pmutation = 0.02, N/Nt = 20, Nk = 5, 2-opt, 3-opt, luyện kim.................. 110 Bảng 4.12 So sánh kết quả lời giải của các giải thuật .................................................. 113 Bảng 5.1 Kết quả với Pcrossover = 0.9 và Pmutation = 0.03, Berlin52 ................................ 121 Bảng 5.2 Kết quả với Pcrossover = 0.8 và Pmutation = 0.03, Berlin52 ................................ 121 Bảng 5.3 Kết quả với Pcrossover = 0.7 và Pmutation = 0.03, Berlin52 ................................ 121 Bảng 5.4 Kết quả với Pcrossover = 0.6 và Pmutation = 0.03, Berlin52 ................................ 121 Bảng 5.5 Kết quả với Pcrossover = 0.9 và Pmutation = 0.01, Berlin52 ................................ 122 Bảng 5.6 Kết quả với Pcrossover = 0.8 và Pmutation = 0.01, Berlin52 ................................ 122 Bảng 5.7 Kết quả với Pcrossover = 0.7 và Pmutation = 0.01, Berlin52 ................................ 122 Bảng 5.8 Kết quả với Pcrossover = 0.6 và Pmutation = 0.01, Berlin52 ................................ 122 Bảng 5.9 Kết quả với Pcrossover = 0.9 và Pmutation = 0.02, Berlin52 ................................ 123 Bảng 5.10 Kết quả với Pcrossover = 0.8 và Pmutation = 0.02, Berlin52 .............................. 123 - 10 - Bảng 5.11 Kết quả với Pcrossover = 0.7 và Pmutation = 0.02, Berlin52 .............................. 123 Bảng 5.12 Kết quả với Pcrossover = 0.6 và Pmutation = 0.02, Berlin52 .............................. 123 Bảng 5.13 Kết quả với Pcrossover = 0.9 và Pmutation = 0.03, KroC100 ............................. 124 Bảng 5.14 Kết quả với Pcrossover = 0.8 và Pmutation = 0.03, KroC100 ............................. 124 Bảng 5.15 Kết quả với Pcrossover = 0.7 và Pmutation = 0.03, KroC100 ............................. 124 Bảng 5.16 Kết quả với Pcrossover = 0.6 và Pmutation = 0.03, KroC100 ............................. 124 Bảng 5.17 Kết quả với Pcrossover = 0.9 và Pmutation = 0.01, KroC100 ............................. 125 Bảng 5.18 Kết quả với Pcrossover = 0.8 và Pmutation = 0.01, KroC100 ............................. 125 Bảng 5.19 Kết quả với Pcrossover = 0.9 và Pmutation = 0.01, KroC100 ............................. 125 Bảng 5.20 Kết quả với Pcrossover = 0.6 và Pmutation = 0.01, KroC100 ............................. 125 Bảng 5.21 Kết quả với Pcrossover = 0.9 và Pmutation = 0.02, KroC100 ............................. 126 Bảng 5.22 Kết quả với Pcrossover = 0.8 và Pmutation = 0.02, KroC100 ............................. 126 Bảng 5.23 Kết quả với Pcrossover = 0.7 và Pmutation = 0.02, KroC100 ............................. 126 Bảng 5.24 Kết quả với Pcrossover = 0.6 và Pmutation = 0.02, KroC100 ............................. 126 Bảng 5.25 Kết quả với Pcrossover = 0.9 và Pmutation = 0.03, St70 ..................................... 127 Bảng 5.26 Kết quả với Pcrossover = 0.8 và Pmutation = 0.03, St70 ..................................... 127 Bảng 5.27 Kết quả với Pcrossover = 0.7 và Pmutation = 0.03, St70 ..................................... 127 Bảng 5.28 Kết quả với Pcrossover = 0.6 và Pmutation = 0.03, St70 ..................................... 127 Bảng 5.29 Kết quả với Pcrossover = 0.9 và Pmutation = 0.01, St70 ..................................... 128 Bảng 5.30 Kết quả với Pcrossover = 0.8 và Pmutation = 0.01, St70 ..................................... 128 Bảng 5.31 Kết quả với Pcrossover = 0.7 và Pmutation = 0.01, St70 ..................................... 128 Bảng 5.32 Kết quả với Pcrossover = 0.6 và Pmutation = 0.01, St70 ..................................... 128 Bảng 5.33 Kết quả với Pcrossover = 0.9 và Pmutation = 0.02, St70 ..................................... 129 Bảng 5.34 Kết quả với Pcrossover = 0.8 và Pmutation = 0.02, St70 ..................................... 129 Bảng 5.35 Kết quả với Pcrossover = 0.9 và Pmutation = 0.02, St70 ..................................... 129 Bảng 5.36 Kết quả với Pcrossover = 0.6 và Pmutation = 0.02, St70 ..................................... 129 Bảng 5.37 Kết quả với Pcrossover = 0.9 và Pmutation = 0.03, Eil101 .................................. 130 Bảng 5.38 Kết quả với Pcrossover = 0.8 và Pmutation = 0.03, Eil101 .................................. 130 Bảng 5.39 Kết quả với Pcrossover = 0.7 và Pmutation = 0.03, Eil101 .................................. 130 Bảng 5.40 Kết quả với Pcrossover = 0.6 và Pmutation = 0.03, Eil101 .................................. 130 Bảng 5.41 Kết quả với Pcrossover = 0.9 và Pmutation = 0.01, Eil101 .................................. 131 - 11 - Bảng 5.42 Kết quả với Pcrossover = 0.8 và Pmutation = 0.01, Eil101 .................................. 131 Bảng 5.43 Kết quả với Pcrossover = 0.7 và Pmutation = 0.01, Eil101 .................................. 131 Bảng 5.44 Kết quả với Pcrossover = 0.6 và Pmutation = 0.01, Eil101 .................................. 131 Bảng 5.45 Kết quả với Pcrossover = 0.9 và Pmutation = 0.02, Eil101 .................................. 132 Bảng 5.46 Kết quả với Pcrossover = 0.8 và Pmutation = 0.02, Eil101 .................................. 132 Bảng 5.47 Kết quả với Pcrossover = 0.7 và Pmutation = 0.02, Eil101 .................................. 132 Bảng 5.48 Kết quả với Pcrossover = 0.6 và Pmutation = 0.02, Eil101 .................................. 132 Bảng 5.49 Kết quả với Pcrossover = 0.9 và Pmutation = 0.03, Pr76 ..................................... 133 Bảng 5.50 Kết quả với Pcrossover = 0.8 và Pmutation = 0.03, Pr76 ..................................... 133 Bảng 5.51 Kết quả với Pcrossover = 0.7 và Pmutation = 0.03, Pr76 ..................................... 133 Bảng 5.52 Kết quả với Pcrossover = 0.6 và Pmutation = 0.03, Pr76 ..................................... 133 Bảng 5.53 Kết quả với Pcrossover = 0.9 và Pmutation = 0.01, Pr76 ..................................... 134 Bảng 5.54 Kết quả với Pcrossover = 0.8 và Pmutation = 0.01, Pr76 ..................................... 134 Bảng 5.55 Kết quả với Pcrossover = 0.7 và Pmutation = 0.01, Pr76 ..................................... 134 Bảng 5.56 Kết quả với Pcrossover = 0.6 và Pmutation = 0.01, Pr76 ..................................... 134 Bảng 5.57 Kết quả với Pcrossover = 0.8 và Pmutation = 0.02, Pr76 ..................................... 135 Bảng 5.58 Kết quả với Pcrossover = 0.8 và Pmutation = 0.02, Pr76 ..................................... 135 Bảng 5.59 Kết quả với Pcrossover = 0.7 và Pmutation = 0.02, Pr76 ..................................... 135 Bảng 5.60 Kết quả với Pcrossover = 0.6 và Pmutation = 0.02, Pr76 ..................................... 135 Bảng 5.61 Kết quả với Pcrossover = 0.9 và Pmutation = 0.03, Lin105 ................................. 136 Bảng 5.62 Kết quả với Pcrossover = 0.8 và Pmutation = 0.03, Lin105 ................................. 136 Bảng 5.63 Kết quả với Pcrossover = 0.7 và Pmutation = 0.03, Lin105 ................................. 136 Bảng 5.64 Kết quả với Pcrossover = 0.6 và Pmutation = 0.03, Lin105 ................................. 136 Bảng 5.65 Kết quả với Pcrossover = 0.9 và Pmutation = 0.01, Lin105 ................................. 137 Bảng 5.66 Kết quả với Pcrossover = 0.8 và Pmutation = 0.01, Lin105 ................................. 137 Bảng 5.67 Kết quả với Pcrossover = 0.7 và Pmutation = 0.01, Lin105 ................................. 137 Bảng 5.68 Kết quả với Pcrossover = 0.6 và Pmutation = 0.01, Lin105 ................................. 137 Bảng 5.69 Kết quả với Pcrossover = 0.9 và Pmutation = 0.02, Lin105 ................................. 138 Bảng 5.70 Kết quả với Pcrossover = 0.8 và Pmutation = 0.02, Lin105 ................................. 138 - 12 - Danh mục thuật ngữ STT Từ viết tắt Giải nghĩa tiếng Anh Giải nghĩa tiếng Việt thông tin di truyền Phân tử acid nucleic mang 1 ADN Acid deoxyribonucleic 2 AP Alternating Position Crossover Lai ghép luân phiên 3 CX Cycles Crossover Lai ghép chu kỳ 4 DM Displacement Mutation Đột biến dịch chuyển nhóm phần tử 5 DNA Acid deoxyribonucleic Phân tử acid nucleic mang thông tin di truyền 6 EM Exchange Mutation Đột biến hoán đổi hai phần tử 7 ER Genetic Edge Recombination Crossover Lai ghép tái tổ hợp cạnh 8 ISM Invertion Mutation Đột biến chèn 9 IVM Inversion Mutation Đột biến đảo 10 GA Genetic Algorithm Giả thuật di truyền 11 GAH Genetic Algorithm Hybirdization with Local Search Giải thuật di truyền kết hợp 12 LS Local Search Giải thuật tìm kiếm địa phương 13 MLP Minimum latency problem Bài toán cực tiểu hóa độ trễ 14 MPX Maximal Preservative Crosssover Lai ghép bảo tồn cực đại 15 OX1 Order Crossover Lai ghép thứ tự 16 OX2 Order Based Crossover Lai ghép dựa trên thứ tự 17 POS Position Based Crossover Lai ghép dựa trên vị trí 18 PMX Paritally-Mapped Crossover Lai ghép ánh xạ bộ phận 19 SIM Simple Inversion Mutation Đột biến đảo đơn 20 TSP Travelling Salesman Problem Bài toán người bán hàng 21 VR Voting Recombination Crossover Lai ghép tái tổ hợp bầu chọn - 13 - LỜI NÓI ĐẦU Bài toán cực tiểu hoá độ trễ (MLP – Minimum Latency Problem) thuộc lớp bài toán tối ưu tổ hợp và là bài toán NP - khó trong trường hợp tổng quát [1]. Hiện nay, bài toán MLP có rất nhiều ứng dụng trong thực tế [2]. Do vậy, việc tìm ra được lời giải tối ưu cho bài toán đang là mối quan tâm của nhiều nhà nghiên cứu. Một số hướng tiếp cận giải bài toán được đề xuất, song các kết quả đạt được chưa cao. Hơn hai thập kỷ qua, ngành khoa học về các phương pháp tối ưu đã có những bước tiến lớn, rất nhiều phương pháp tối ưu được áp dụng. Một trong những phương pháp được áp dụng hiệu quả cho bài toán tối ưu, đặc biệt là lớp bài toán tối ưu tổ hợp là giải thuật di truyền. Giải thuật di truyền được đề xuất bởi Holland trong những năm 1970, 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 lớp 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 thuyết tiến hóa. Đến nay, giải thuật đã được ứng dụng vào nhiều ngành, nhiều lĩnh vực và thu được nhiều thành tựu. Với mục đích nâng cao kết quả, tác giả chọn hướng tiếp cận giải thuật di truyền (giải thuật thích hợp cho lớp bài toán tối ưu tổ hợp) giải bài toán cực tiểu hoá độ trễ. Nội dung của luận văn bao gồm những phần sau: • Chương 1: Giới thiệu bài toán Chương này trình bày bài toán cực tiểu hoá độ trễ, ứng dụng của bài toán trong thực tế, cách biểu diễn bài toán trên mô hình đồ thị, cũng như các giải thuật giải bài toán. Trên cơ sở đó, đề xuất hướng áp dụng giải thuật di truyền giải bài toán. Chương 2: Giải thuật di truyền Trong chương này, trình bày một số khái niệm cơ bản trong sinh học. Trên cơ sở đó, trình bày các vấn đề cơ bản của giải thuật di truyền. Cuối cùng là trình bày về giải thuật di truyền kết hợp. - 14 - • Chương 3: Thiết kế giải thuật di truyền cho bài toán cực tiểu hoá độ trễ Chương này tập trung thiết kế giải thuật di truyền áp dụng cho bài toán cực tiểu hoá độ trễ MLP. Chương 4: Tính toán thực nghiệm Chương này trình bày tính toán thực nghiệm theo hướng giải thuật di truyền được xây dựng trong chương trước để kiểm nghiệm và đánh giá hiệu quả của giải thuật. Kết luận và hướng phát triển nghiên cứu ở các giai đoạn tiếp theo. Ý nghĩa khoa học và thực tiễn luận văn: • Giải thuật di truyền là một phân ngành của giải thuật tiến hóa áp dụng hiệu quả cho bài toán tối ưu, đặc biệt là lớp bài toán tối ưu tổ hợp. Hiện này, giải thuật di truyền được ứng dụng vào nhiều ngành, nhiều lĩnh vực và thu được nhiều thành tựu [12]. • Bài toán cực tiểu hoá độ trễ thuộc lớp các bài toán tối ưu tổ hợp thường gặp và có nhiều ứng dụng trong thực tế [2]. Do vậy, việc nâng cao chất lượng lời giải của bài toán có ý nghĩa thực tế cao. Hướng áp dụng giải thuật di truyền giải bài toán cực tiểu hoá độ trễ là có cơ sở khoa học và thực tiễn. - 15 - CHƯƠNG 1 GIỚI THIỆU BÀI TOÁN Chương này phát biểu bài toán cực tiểu hoá độ trễ (MLP), một số ứng dụng của bài toán trong thực tế, cách biểu diễn bài toán trên cơ sở lý thuyết đồ thị, cũng như các giải thuật giải bài toán. Trên cơ sở đó đề xuất việc áp dụng giải thuật di truyền giải bài toán MLP. 1.1 Phát biểu bài toán Bài toán cực tiểu hoá độ trễ (minimum latency problem) cũng được biết như một dạng khác của bài toán người giao hàng, bài toán người bán hàng (Traveling Salesman Problem) [4, 5]. Cho một tập n điểm p1, …, pn, mỗi điểm đều có cạnh nối với các điểm còn lại. Tìm một đường đi đơn bắt đầu từ một điểm xuất phát đến thăm tất cả các điểm còn lại, sao cho tổng độ trễ của đường đi đó là cực tiểu. n ∑ l( p i ) à Min. Với l(pi) là độ trễ của điểm thứ i. 1 Trong đó, độ trễ đường đi là tổng độ trễ của tất cả các điểm có trong đường đi đó và độ trễ của một điểm bất kỳ là tổng độ dài cạnh nối các điểm liền nhau trong đường đi trước khi điểm đó được thăm lần đầu. Một số ứng dụng của bài toán cực tiều hoá độ trễ [2]: • Một máy chủ có một tập các yêu cầu. Máy chủ đó phải lập lịch sao cho cực tiểu hoá thời gian trung bình mà mỗi yêu cầu phải đợi. • Một ứng dụng khác của bài toán MLP được sử dụng để cực tiểu hoá thời gian tìm kiếm thông tin trên mạng. - 16 - 1.2 Mô hình đồ thị của bài toán Trong trường hợp tổng quát, coi mỗi điểm của đường đi là một đỉnh của đồ thị đầy đủ có trọng số. Khi đó, đường đi giữa hai điểm là cạnh nối giữa hai đỉnh. Bài toán được phát biểu: Cho một đồ thị đầy đủ có trọng số Kn với tập đỉnh V = {vi | i = 1, 2, …, n} và ma trận trọng số đối xứng C = {cij ≥ 0 | i, j = 1, 2, …, n}. Tìm một đường đi đơn bắt đầu từ một đỉnh xuất phát bất kỳ trong đồ thị đến thăm tất cả các đỉnh còn lại, sao cho độ trễ của đường đi đó là cực tiểu. Trong đó, độ trễ đường đi là tổng độ trễ của tất cả các đỉnh có trong đường đi đó và độ trễ của một đỉnh bất kỳ là tổng độ dài cạnh nối các đỉnh liền nhau trong đường đi trước khi đỉnh đó được thăm lần đầu. Nếu dãy đỉnh v1v2…vn là đường đi trên Kn, thì độ trễ của đường đi đó được tính như sau: n i −1 ∑∑ c i = 2 j=1 jj+1 Một số ví dụ: • Ví dụ 1 [5]: Xét đồ thị đầy đủ có trọng số K6 với ma trận trọng số đối xứng Cij = 0 12  40  10 9  10 12 0 19 12 70 15 40 19 0 21 60 17 10 12 21 0 10 16 9 70 60 10 0 10 16 15 17 16 10 0          Đường đi T = 1 – 5 – 4 – 2 – 3 – 6 có tổng độ trễ nhỏ nhất: (9 + (9 + 10) + (9 + 10 + 12) + (9 + 10 + 12 + 19) + (9 + 10 + 12 + 19 + 17)) = 192.