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 tố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 Tố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 TỐ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 q 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 q
trình học tập và hồ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 để hồ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 tốn .............................................................................................. 15
1.2 Mơ hình đồ thị của bài tố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 TỐ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 Q trình tiến hố độ 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 tố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 tốn PMX ..................................................................................... 53
Hình 3.2 Mơ tả phép tốn CX ........................................................................................ 54
Hình 3.3 Mơ tả phép tốn CX ........................................................................................ 56
Hình 3.4 Mơ tả phép tốn DM ....................................................................................... 58
Hình 3.4 Mơ tả phép tốn ISM....................................................................................... 59
Hình 3.5 Mơ tả phép tốn SIM....................................................................................... 59
Hình 3.7 Mơ tả phép tố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 tốn tử OX2 ............................................. 72
Hình 4.5 Lược đồ mơ tả bước thực hiện của tốn tử POS ............................................. 73
Hình 4.6 Lược đồ mơ tả bước thực hiện của tố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 hố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 tố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 tốn cực tiểu hố độ trễ (MLP – Minimum Latency Problem) thuộc lớp bài
toán tối ưu tổ hợp và là bài tố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 tố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 tốn
Chương này trình bày bài tốn cực tiểu hố độ trễ, ứng dụng của bài toán trong
thực tế, cách biểu diễn bài tốn trên mơ hình đồ thị, cũng như các giải thuật giải
bài tố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 tốn cực tiểu
hố độ trễ MLP.
Chương 4: Tính tốn thực nghiệm
Chương này trình bày tính tố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 tốn cực tiểu hố độ 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 tố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 hố độ 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 hố 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 tố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.


- 17 -


• Ví dụ 2 [6]: Trong trường hợp các điểm là các đỉnh của đồ thị đầy đủ trong
file dữ liệu Berlin52

Hình 1.1 Đường đi tối ưu MLP trong file dữ liệu Berlin 52

Hình 1.2 Đường đi tối ưu TSP trong file dữ liệu Berlin 52


- 18 -

1.3 Các giải thuật giải bài toán
MLP là bài tốn NP- khó trong trường hợp tổng qt [1, 2, 3, 4], thậm chí là bài
tốn NP- khó trong trường hợp các đỉnh của nó là các đỉnh của cây có trọng lượng [7].
Do đó, trong trường hợp tổng qt, khơng tồn tại một giải thuật có độ phức tạp đa thức
để giải bài toán trên. Nếu giải bằng phương pháp quy hoạch động trong trường hợp
tổng quát, độ phức tạp của giải thuật sẽ là hàm số mũ O(n 2 2 n ) [8]. Bang Ye Wu,
ZhengNan Huang, Fu-Jie Zhan đề xuất giải thuật kết hợp phương pháp quy hoạch động
và phương pháp nhánh cận có độ phức tạp hàm số mũ giải bài toán MLP trong trường
hợp các đỉnh của bài toán là các đỉnh của đồ thị vơ hướng có trọng lượng [9].
Các giải thuật có độ phức tạp đa thức giải bài toán MLP trong một số trường
hợp đặc biệt:
• Cây khơng trọng lượng - độ phức tạp giải thuật trong trường hợp này là đa
thức [9].
• Các đỉnh p i nằm trên một đường thẳng - phương pháp giải quy hoạch động O(n 2 ) [1].
• Các đỉnh p i là các đỉnh của cây có số lượng lá là hằng số (trees of constant
number of leaves) [10].
Một số giải thuật giải bài toán MLP trong trường hợp tổng quát:
• Các giải thuật gần đúng: Trong trường hợp tổng quát, Blum đưa ra giải thuật
gần đúng với hệ số gần đúng là 144, Geomans và Klein-berg đưa ra hệ số

gần đúng là 21.55, còn Grag đưa ra hệ số là 10.78 [3]. Aaron Archer, Asaf
Levin, David Williamson đề xuất giải thuật gần đúng tốt nhất với hệ số gần
đúng sấp sỉ 3.01 [6].
• Một số giải thuật tìm kiếm địa phương: 2-opt, 3-opt, giải thuật luyện kim,
giải thuật Tabu Reasearch, một số giải thuật Heuristic.


- 19 -

• Giải thuật di truyền: Giải thuật di truyền thường áp dụng tốt cho những bài
toán tối ưu hố tổ hợp như bài tốn TSP và MLP. Ngồi ra, có thể kết hợp
giải thuật di truyền với giải thuật tìm kiếm địa phương. Trong đó, giải thuật
di truyền đóng vai trị trong việc tìm các cực trị, cịn giải thuật địa phương sẽ
“leo” lên các đỉnh đó để tìm cực đại (cực tiểu) tồn cục.

1.4 Đề xuất hướng áp dụng giải thuật di truyền
Giải thuật gần đúng mà Aaron Archer, Asaf Levin, David Williamson đề xuất
giải bài toán MLP có hệ số gần đúng nhỏ nhất, song kết quả đạt được vẫn chưa cao.
Với mục đích nâng cao chất lượng lời giải, hướng áp dụng giải thuật di truyền giải bài
tốn MLP là có cơ sở khoa học vì:
Thứ nhất, hướng áp dụng giải thuật di truyền giải bài toán người bán hàng (bài
toán cũng thuộc lớp bài toán tối ưu tổ hợp) đạt được nhiều kết quả khả quan cả về lý
thuyết lẫn thực nghiệm [13, 14]. Điều này chứng tỏ giải thuật di truyền có thể áp dụng
tốt cho bài toán MLP.
Thứ hai, giải thuật di truyền có nhiều ưu điểm so với các phương pháp tối ưu
truyền thống [11, 15]:
• Giải thuật di truyền tác động vào mã biểu diễn lời giải thay vì trực tiếp vào lời
giải đó. Do đó, miền xác định và miền giá trị của mã biểu diễn là rời rạc. Như
vậy, giải thuật di truyền có thể khắc phục được các hạn chế về vấn đề liên tục,
về sự tồn tại đạo hàm, …

• Các phương pháp tối ưu truyền thống tác động trực tiếp lên từng lời giải thông
qua một vài bước lặp để biến đổi thành lời giải khác. Tuy nhiên, các phương
pháp này thường gặp phải vấn đề khi đạt đến trạng thái cực trị địa phương.
Trong khi đó, giải thuật di truyền tác động lên quần thể các lời giải. Nhờ vậy,
nhược điểm trên được hạn chế thơng qua tính đa dạng của các lời giải.


- 20 -

• Các phương pháp tối ưu truyền thống thường yêu cầu tập các rằng buộc hoặc
các giá trị đạo hàm, … . Trong khi đó, giải thuật di truyền chỉ cần quan tâm đến
giá trị hàm mục tiêu.
• Các phương pháp truyền thống biến đổi lời giải ban đầu thành lời giải khác
thông qua các luật cố định. Do vậy, các phương pháp này chỉ áp dụng cho một
lớp các bài tốn xác định, mà khơng thể áp dụng rộng rãi cho các lớp bài toán
khác nhau. Ngược lại, giải thuật di truyền sử dụng các luật xác suất để tìm kiếm
lời giải; dẫn đến việc tìm kiếm có thể diễn ra theo nhiều hướng khác nhau và hội
tụ ở những lời giải gần tối ưu.
Với những ưu điểm này, tác giả tập trung hướng nghiên cứu áp dụng giải thuật
di truyền vào giải bài toán MLP.


- 21 -

1.5 Nhiệm vụ của luận văn
Từ những yêu cầu đặt ra, nhiệm vụ của luận văn là:
• Tìm hiểu và nghiên cứu bài toán cực tiểu hoá độ trễ, các ứng dụng thực tế của
bài toán, các giải thuật giải bài toán và kết quả đạt được. Đồng thời nghiên cứu
hướng áp dụng giải thuật di truyền giải bài tốn MLP.
• Nghiên cứu tổng quan về các vấn đề cơ bản của giải thuật di truyền, đồng thời

nghiên cứu các phương pháp, kỹ thuật nâng cao kết quả của giải thuật.
• Từ các cở sở lý thuyết trên, tiến hành thiết kế giải thuật di truyền giải bài tốn
MLP.
•

Cài đặt mơ hình và tiến hành thử nghiệm giải thuật đã đề xuất.