Tiến Sĩ Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất

LUẬN ÁN TIẾN SĨ
NĂM 2015
MỤC LỤC

MỞ ĐẦU 1
Chương 1. TỔNG QUAN . 5
1.1.BÀI TOÁN MRCST 5
1.1.1.Một số định nghĩa 5
1.1.2.Thuật toán tính chi phí định tuyến của cây khung 7
1.1.3.Đánh giá chi phí định tuyến của cây khung 9
1.2.ỨNG DỤNG 11
1.2.1.Ứng dụng của bài toán MRCST trong lĩnh vực thiết kế mạng 11
1.2.2.Ứng dụng của bài toán MRCST trong lĩnh vực tin sinh học 11
1.3.CÁC NGHIÊN CỨU LIÊN QUAN BÀI TOÁN MRCST . 12
1.3.1.Thuật toán giải đúng 12
1.3.2.Thuật toán gần đúng cận tỉ lệ 13
1.3.3.Thuật toán heuristic . 16
1.3.4.Thuật toán metaheuristic . 18
1.3.5.Danh sách các thuật toán giải bài toán MRCST hiện biết 25
1.4.TIÊU CHÍ ĐÁNH GIÁ THUẬT TOÁN . 26
1.5.HỆ THỐNG DỮ LIỆU THỰC NGHIỆM CHUẨN . 29
1.5.1.Đồ thị đầy đủ Euclid 30
1.5.2.Đồ thị đầy đủ ngẫu nhiên 30
1.5.1.Đồ thị thưa . 31
1.6.KHẢO SÁT THỰC NGHIỆM CÁC THUẬT TOÁN GIẢI BÀI TOÁN MRCST . 32
1.6.1.Cấu hình máy tính thực nghiệm các thuật toán . 32
1.6.2.Chất lượng lời giải . 32
1.6.3.Thời gian tính 34
1.6.4.Hình vẽ minh họa so sánh chất lượng của các thuật toán hiện biết . 36
1.7.KẾT LUẬN CHƯƠNG 1 37
Chương 2. THUẬT TOÁN TÌM KIẾM LEO ĐỒI 39
2.1.CÂY KHUNG LÂN CẬN . 39
2.2.THUẬT TOÁN HCSRI . 40
2.2.1.Ý tưởng thuật toán HCSRI 40
2.2.2.Sơ đồ thuật toán HCSRI 41
2.2.3.Độ phức tạp của thuật toán HCSRI . 42
2.3.THUẬT TOÁN HCSIR . 42
2.3.1.Ý tưởng thuật toán HCSIR 42
2.3.2.Sơ đồ thuật toán HCSIR 43
2.3.3.Độ phức tạp của thuật toán HCSIR . 44
2.4.THỰC NGHIỆM VÀ ĐÁNH GIÁ 45
2.4.1.Môi trường thực nghiệm 45
2.4.2.Tham số thực nghiệm 45
2.4.3.Chất lượng lời giải . 45
2.4.4.Thời gian tính 51
2.4.5.Hình vẽ minh họa chất lượng HCSRI, HCSIR với các thuật toán khác 53
2.5.KẾT LUẬN CHƯƠNG 2 55
Chương 3. THUẬT TOÁN DI TRUYỀN 56
3.1.THUẬT TOÁN GST . 56
3.1.1.Tạo quần thể ban đầu . 56
3.1.2.Phép lai 57
3.1.3.Phép đột biến . 60
3.1.4.Phép chọn lọc 62
3.1.5.Sơ đồ thuật toán GST . 63
3.1.6.Độ phức tạp của thuật toán GST 64
3.2.THỰC NGHIỆM VÀ ĐÁNH GIÁ 64
3.2.1.Môi trường thực nghiệm 64
3.2.2.Tham số thực nghiệm 65
3.2.3.Chất lượng lời giải . 65
3.2.4.Thời gian tính 69
3.2.5.Hình vẽ minh họa chất lượng thuật toán GST với các thuật toán khác . 70
3.3.KẾT LUẬN CHƯƠNG 3 73
Chương 4. THUẬT TOÁN TÌM KIẾM TABU . 74
4.1.THUẬT TOÁN TST 74
4.1.1.Ý tưởng và một số khái niệm của thuật toán tìm kiếm Tabu 74
4.1.2.Thuật toán TST tìm bước chuyển tốt nhất . 75
4.1.3.Thuật toán TST cập nhật danh sách Tabu 76
4.1.4.Chiến lược đa dạng hóa lời giải của thuật toán TST 76
4.1.5.Sơ đồ của thuật toán TST . 77
4.1.6.Độ phức tạp của thuật toán TST 79
4.2.THỰC NGHIỆM VÀ ĐÁNH GIÁ 79
4.2.1.Môi trường thực nghiệm 79
4.2.2.Tham số thực nghiệm 79
4.2.3.Chất lượng lời giải . 80
4.2.4.Thời gian tính 84
4.2.5.Hình vẽ minh họa chất lượng thuật toán TST với các thuật toán khác 86
4.3.KẾT LUẬN CHƯƠNG 4 88
Chương 5. THUẬT TOÁN BẦY ONG . 89
5.1.THUẬT TOÁN BẦY ONG CƠ BẢN 89
5.2.THUẬT TOÁN BST 91
5.2.1.Tạo quần thể ban đầu . 91
5.2.2.Phân nhóm các cá thể 92
5.2.3.Tìm cây khung lân cận 93
5.2.4.Chiến lược đa dạng hóa lời giải . 95
5.2.5.Sơ đồ của thuật toán BST . 96
5.2.6.Độ phức tạp của thuật toán BST 98
5.3.THỰC NGHIỆM VÀ ĐÁNH GIÁ 98
5.3.1.Môi trường thực nghiệm 98
5.3.2.Tham số thực nghiệm 98
5.3.3.Chất lượng lời giải . 99
5.3.4.Thời gian tính 104
5.3.5.Hình vẽ minh họa chất lượng thuật toán BST với các thuật toán khác 106
5.3.6.Hình vẽ minh họa độ lệch chuẩn của các thuật toán . 109
5.4.KẾT LUẬN CHƯƠNG 5 111
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 112
KẾT LUẬN . 112
HƯỚNG PHÁT TRIỂN 113 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN . 114
TÀI LIỆU THAM KHẢO 115
PHỤ LỤC. KẾT QUẢ THỰC NGHIỆM TỪ CÁC CÔNG TRÌNH LIÊN QUAN . 119


MỞ ĐẦU
Tối ưu hóa mạng liên quan đến nhiều lĩnh vực như toán ứng dụng, khoa học máy tính, vận trù
học, kỹ thuật, mạng truyền thông, Nhiều bài toán thực tế trong lĩnh vực mạng truyền thông,
chẳng hạn như bài toán cây khung truyền thông tối ưu (Optimal Communication Spanning
Trees - OCST), bài toán cây Steiner nhỏ nhất (Steiner Minimal Trees - SMT), bài toán cây khung
nhỏ nhất với đường kính bị chặn (Bounded Diameter Minimum Spanning Trees - BDMST) [20],
bài toán cây khung với chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Trees -
MRCST) đã được chứng minh thuộc lớp bài toán NP-khó hoặc NP-đầy đủ.
MRCST là một bài toán tối ưu đồ thị nổi tiếng; bài toán này lần đầu tiên được giới thiệu bởi T.
C. Hu vào năm 1974 qua bài báo “Optimum communication spanning trees” [37]. Bài toán
MRCST được xem là một trường hợp đặc biệt của bài toán cây khung truyền thông tối ưu khi
mà lượng cầu truyền thông giữa tất cả mọi cặp đỉnh của bài toán OCST đều bằng nhau [9,10,37].
Mô hình toán học của bài toán MRCST có thể phát biểu như sau: Cho G là một đồ thị vô hướng
liên thông có chi phí định tuyến không âm trên cạnh. Giả sử T là một cây khung của G. Chi phí
định tuyến cho mỗi cặp đỉnh trên T được định nghĩa là tổng các chi phí định tuyến trên các cạnh
của đường đi đơn nối chúng trên T và chi phí định tuyến của T được định nghĩa là tổng của tất
cả các chi phí định tuyến giữa mọi cặp đỉnh của T. Bài toán MRCST đặt ra là tìm một cây khung
có chi phí định tuyến nhỏ nhất trong số tất cả các cây khung của G [10]. Bài toán MRCST đã



được chứng minh thuộc lớp bài toán NP-khó [10,13,37].
Bài toán MRCST có nhiều ứng dụng trong lĩnh vực thiết kế mạng truyền thông
[7,10,15,27,31,33], chẳng hạn bài toán xây dựng các hệ thống mạng nhằm tối ưu chi phí đường
đi trung bình giữa các nút mạng; đặc biệt là ở các mạng ngang hàng – khi mà các nút có xác
suất truyền tin và độ ưu tiên là như nhau. Bài toán MRCST cũng tìm được những ứng dụng quan
trọng trong lĩnh vực tin sinh học [10,41].
Việc đề xuất thuật toán dạng metaheuristic giải bài toán MRCST có ý nghĩa quan trọng, một
mặt, nhằm giải quyết những bài toán ứng dụng thực tiễn vừa nêu; mặt khác, còn là cơ sở để giải
quyết những bài toán cây khung tối ưu dạng NP-khó khác trên đồ thị. Bài toán MRCST đã thu hút được sự quan tâm nghiên cứu của nhiều nhà khoa học trong hơn bốn
mươi năm qua. Hiện nay đã có hàng loạt thuật toán giải bài toán MRCST được đề xuất và có thể
chia chúng làm các hướng tiếp cận sau: Hướng thứ nhất là các thuật toán tìm lời giải đúng.
Hướng tiếp cận giải đúng phát triển trên thuật toán nhánh cận được đề xuất bởi R. Dionne và M.
Florian vào năm 1979 [30], thuật toán nhánh cận kết hợp với phương pháp sinh cột được đề xuất
bởi Matteo Fischetti, Giuseppe Lancia, Paolo Serafini vào năm 2002 [24]. Các thuật toán giải
đúng chỉ có thể giải được bài toán MRCST đối với đồ thị có không quá 40 đỉnh và do đó tính
ứng dụng thực tiễn của nó không cao [1,24,30]. Hướng thứ hai là các thuật toán tìm lời giải gần
đúng cận tỉ lệ, như thuật toán WONG được đề xuất bởi Richard T. Wong vào năm 1980 [31],
thuật toán GENERAL STAR được đề xuất bởi Bang Ye Wu và Kun-Mao Chao vào năm 1999
[8], sơ đồ xấp xỉ thời gian đa thức – PTAS được đề xuất bởi Bang Ye Wu và Kun-Mao Chao
vào năm 2004 [10], thuật toán xấp xỉ xử lý song song được đề xuất bởi Ching-Lueh Chang và
Yuh-Dauh Lyuu vào năm 2008 [12], thuật toán gần đúng cận tỉ lệ được đề xuất bởi Alexandra
Hochuli, Stephan Holzer, Roger Wattenhofer năm 2014 [4]. Ưu điểm của các thuật toán này là
có sự đảm bảo về mặt toán học theo nghĩa lời giải tìm được gần đúng một cận tỉ lệ α nào đó so
với lời giải tối ưu. Hướng thứ ba là các thuật toán heuristic, bao gồm thuật toán ADD được đề
xuất bởi Vic Grout vào năm 2005 [41], thuật toán CAMPOS được đề xuất bởi Rui Campos và
Manuel Ricardo vào năm 2008 [33]. Các thuật toán ADD, CAMPOS có độ phức tạp thời gian
tính tốt nhất trong số tất cả các thuật toán giải bài toán MRCST hiện biết. Thuật toán CAMPOS
tìm được lời giải với chất lượng tốt hơn so với các thuật toán WONG ở một số loại đồ thị cụ thể.
Hướng thứ tư là các thuật toán metaheuristic. Hướng tiếp cận metaheuristic phát triển trên các
thuật toán di truyền, thuật toán tìm kiếm địa phương và thuật toán bầy ong. Hướng tiếp cận này
bao gồm thuật toán di truyền mã hóa dạng cạnh – ESCGA được đề xuất bởi Bryant A. Julstrom
vào năm 2005 [11], thuật toán di truyền mã hóa dạng dãy số Prüfer – BCGA được đề xuất bởi
Bryant A. Julstrom vào năm 2005 [11], thuật toán tìm kiếm leo đồi ngẫu nhiên – SHC được đề
xuất bởi Bryant A. Julstrom vào năm 2005 [11], thuật toán tìm kiếm địa phương có sử dụng
chiến lược đa dạng hóa lời giải – PBLS được đề xuất bởi Alok Singh vào năm 2008 [5], thuật
toán tìm kiếm địa phương– CYCLELS được đề xuất bởi Steffen Wolf và Peter Merz vào năm
2010 [36], thuật toán bầy ong (Artificial Bee Colony - PABC) [6] và thuật toán bầy ong kết hợp
với thuật toán tìm kiếm địa phương (ABC+LS) cùng được đề xuất bởi Alok Singh vào năm 2011
[6] – hai thuật toán này được phát triển dựa vào sơ đồ của thuật toán Artificial Bee Colony
(ABC) [16,17]. Các thuật toán metaheuristic này cho lời giải với chất lượng tốt hơn các thuật
toán giải gần đúng còn lại. Tuy nhiên, hiệu quả của các thuật toán metaheuristic chủ yếu được
đánh giá thông qua thực nghiệm mà chưa chứng minh được về mặt toán học. Thời gian tính các thuật toán metaheuristic là chậm hơn rất nhiều so với các thuật toán WONG [10,31], ADD [41],
CAMPOS [33].
Mục đích của luận án là phát triển một số thuật toán gần đúng dạng metaheuristic giải bài toán
MRCST cho chất lượng lời giải tốt hơn so với các thuật toán có cùng cỡ thời gian tính hoặc đòi
hỏi thời gian tính ít hơn khi so sánh với các thuật toán có chất lượng lời giải tương đương hoặc
đưa ra lời giải tốt nhất mới cho một số bộ dữ liệu thực nghiệm chuẩn.