Các thuật toán gần đúng giải bài toán cực tiểu hóa độ trễ (minimum latency problem-MLP)

- 2 1.2 Một số hướng tiếp cận giải bài toán tối ưu hóa tổ hợp.
- 5 1.2.1 Thuật toán nhánh cận.
- 5 1.2.2 Thuật toán di truyền.
- 8 1.2.3 Thuật toán đàn kiến.
- 10 1.2.4 Thuật toán Tabu.
- 10 1.2.5 Thuật toán lân cận biến đổi.
- 11 1.3 Các nghiên cứu liên quan giải bài toán MLP.
- 11 1.3.1 Thuật toán đúng.
- 12 1.3.2 Thuật toán gần đúng cận tỷ lệ.
- 12 1.3.3 Thuật toán meta-heuristic.
- 20 CHƢƠNG 2 THUẬT TOÁN NHÁNH CẬN.
- 21 2.1 Thuật toán của Wu et al.
- 22 2.2 Lược đồ thuật toán đề xuất.
- 37 iv CHƢƠNG 3 CÁC THUẬT TOÁN GẦN ĐÚNG CẬN TỶ LỆ.
- 38 3.1 Đánh giá thực nghiệm hiệu quả của các thuật toán gần đúng cận tỷ lệ.
- 39 3.1.1 Các thuật toán gần đúng cận tỷ lệ.
- 47 3.2 Thuật toán dựa trên phương pháp Subgradient.
- 55 3.2.1 Lược đồ thuật toán.
- 67 CHƢƠNG 4 CÁC THUẬT TOÁN META-HEURISTIC.
- Thuật toán di truyền.
- 69 4.1.1 Lược đồ của thuật toán.
- 74 4.2 Thuật toán di truyền lai ghép đàn kiến.
- 85 4.2.1 Lược đồ của thuật toán.
- 91 4.3 Thuật toán lai thuật toán Tabu và thuật toán lân cận biến đổi.
- 98 4.3.1 Lược đồ của thuật toán.
- Bài toán MLP có nhiều ứng dụng trong thực tiễn.
- Mục đích nghiên cứu của chúng tôi trong luận án này là đề xuất các thuật toán giải bài toán MLP với chất lượng lời giải tốt hơn chất lượng lời giải của các thuật toán giải bài toán MLP đã được công bố.
- Đối với một bài toán NP-khó như bài toán MLP, hiện tại có ba hướng tiếp cận chính để phát triển thuật toán giải: 1) hướng tiếp cận đúng, 2) hướng tiếp cận gần đúng cận tỷ lệ, 3) hướng tiếp cận meta-heuristic.
- Đóng góp của chúng tôi trong luận án là đề xuất các thuật toán giải theo cả ba hướng tiếp cận.
- Phát triển thuật toán đúng đưa ra lời giải tối ưu cho bài toán MLP với kích thước bài toán lên đến 40 đỉnh.
- Khảo sát thực nghiệm về hiệu quả của các thuật toán gần đúng cận tỷ lệ hiện biết, là cơ sở để đề xuất thuật toán gần đúng mới có cận tỷ lệ tốt hơn.
- Phát triển ba thuật toán theo hướng tiếp cận meta-heuristic.
- Chúng tôi đề xuất thuật toán dựa trên lược đồ của thuật toán di truyền để giải bài toán MLP và một số kỹ thuật mới được tích hợp vào từng bước của thuật toán.
- Nhằm nâng cao chất lượng lời giải và thời gian chạy thuật toán, chúng tôi đề xuất hai thuật toán meta-heuristic lai là: Thuật toán (ACO-GA) lai ghép giữa thuật toán di truyền (GA) và thuật toán đàn kiến (ACO).
- và thuật toán TS-VNS lai ghép giữa thuật toán Tabu (TS) và thuật toán lân cận biến đổi (VNS).
- vi Để đánh giá hiệu quả của các thuật toán đề xuất, chúng tôi tiến hành thực nghiệm trên các bộ dữ liệu chuẩn và so sánh kết quả thu được với kết quả của các công trình nghiên cứu liên quan.
- Kết quả thực nghiệm chỉ ra các thuật toán đề xuất đưa ra lời giải tốt hơn các thuật toán tốt nhất hiện biết trên nhiều bộ dữ liệu.
- vii 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 1 ACO Ant conoly optimization Tối ưu hoá đàn kiến 2 ACO-GA - Thuật toán di truyền lai ghép thuật toán đàn kiến 3 GA Genetic algorithm Thuật toán di truyền 4 TS Tabu search Tìm kiếm Tabu 5 VNS Variable neighborhood search Tìm kiếm lân cận biến đổi 6 TS-VNS - Thuật toán tabu lai ghép thuật toán đa lân cận 7 MLP Minimum latency problem Bài toán cực tiểu hóa độ trễ 8 TSP Traveling salesman problem Bài toán người du lịch 9 TRP Traveling repairman problem Bài toán thợ sửa chữa lưu động 10 DMP Delivery man problem Bài toán người giao hàng 11 TDTSP Time dependent traveling Salesman pproblem Bài toán người du lịch với thời gian bị chặn 12 DP Dynamic programming Quy hoạch động 13 B&B Branch and bound Phương pháp nhánh cận 14 CP Constraint programming Quy hoạch ràng buộc 15 - Approximation algoirthm Thuật toán gần đúng 16 - Simulated annealing algorithm Thuật toán phỏng tôi luyện 17 - Local search Tìm kiếm địa phương 18 GRASP Greedy randomized adaptive search procedure Thủ tục tìm kiếm tham lam ngẫu nhiên tự thích nghi 19 ILS Iterated local search Tìm kiếm địa phương leo đồi 20 RVND Random variable neighborhood descend Tụt lân cận biến đổi ngẫu nhiên 21 k-MST k-minimum spanning tree Bài toán cây khung nhỏ nhất đi qua k đỉnh 22 k-troll Minimum k-troll problem Bài toán hành trình ngắn nhất đi qua k đỉnh 23 PCST Prize collecting steiner tree Bài toán cây Steiner 24 - Polynomial time algorithm (Polynomial algorithm) Thuật toán thời gian tính đa thức 25 Benchmark test Bộ dữ liệu chuẩn 26 OPT Best known solution Lời giải tốt nhất hiện biết 27 SDT Social disaster technique Kỹ thuật hủy diệt viii DANH MỤC BẢNG Bảng 1.
- 1 Mô tả các bộ dữ liệu.
- 1 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 1 (tính theo phút.
- 2 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 2 (tính theo phút.
- 3 Thời gian chạy của thuật toán trong bộ dữ liệu thực 2 (tính theo phút.
- 4 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 3 (TPR-10-Rx) (tính theo giây.
- 5 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 3 (TPR-20-Rx) (tính theo giây.
- 6 Thời gian chạy của thuật toán cho các file dữ liệu nhỏ trong.
- 1 Kết quả thực nghiệm các thuật toán trong các bộ dữ liệu nhỏ.
- 2 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx.
- 3 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx.
- 4 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu thực 1.
- 5 Kết quả thực nghiệm cho các bộ dữ liệu nhỏ.
- 7 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu nhỏ.
- 8 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx.
- 9 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx.
- 10 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-200-Rx) 83 Bảng 4.
- 11 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu thực 1.
- 13 Kết quả thực nghiệm của các thuật toán.
- 14 Kết quả so sánh các thuật toán cho cho các bộ dữ liệu nhỏ.
- 15 Kết quả so sánh các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx.
- 16 Kết quả so sánh các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx.
- 17 Kết quả so sánh các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-200-Rx.
- 18 Kết quả so sánh các thuật toán cho bộ dữ liệu thực 2.
- 20 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu nhỏ.
- 21 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx.
- 22 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx.
- 23 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu ngẫu nhiên 3 (TPR-200-Rx.
- 24 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu ngẫu nhiên 3 (TPR-500-Rx.
- 25 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu thực 1.
- 26 So sánh độ lệch chuẩn độ trễ lời giải của các thuật toán.
- 1 Tổng hợp các thuật toán đề xuất.
- 1 Minh họa bài toán MLP trên cây có trọng số.
- 2 Minh họa bài toán MLP trên đường thẳng.
- 5 Cận tỷ lệ thực nghiệm trung bình của các thuật toán đối với các bộ dữ liệu nhỏ.
- 6 Cận dưới trung bình của các thuật toán đối với các bộ dữ liệu nhỏ.
- 7 Thời gian chạy trung bình của các thuật toán đối với các bộ dữ liệu nhỏ.
- 8 Cận tỷ lệ trung bình của các thuật toán đối với các bộ dữ liệu lớn.
- 9 Thời gian chạy trung bình của các thuật toán đối với các bộ dữ liệu lớn.
- 1 Minh họa sự hội tụ của thuật toán GA−SDT và GA−no−SDT tại file test 1 trong bộ dữ liệu ngẫu nhiên 1 qua các thế hệ.
- 2 Minh họa sự hội tụ của thuật toán GA−SDT và GA−no−SDT tại file test 1 trong bộ dữ liệu ngẫu nhiên 2 qua các thế hệ.
- 3 Minh họa sự hội tụ của thuật toán GA−SDT và GA−no−SDT tại file KroA100 trong bộ dữ liệu thực 2 qua các thế hệ.
- n – i, ta thu được bài toán MLP.
- Điều này cho thấy, chúng ta khó có thể thiết kế một thuật toán theo hướng chia để trị để giải bài toán MLP.
- Bên cạnh đó, trong một số trường hợp đặc biệt, bài toán giải được bởi thuật toán có độ phức tạp thời gian đa thức, được đề cập trong các công trình .
- 1 Minh họa bài toán MLP trên cây có trọng số Hình 1.
- 2 Minh họa bài toán MLP trên đường thẳng cạnh e  E.
- [50] đã chỉ ra rằng hành trình MLP tối ưu của hai đồ thị là như nhau và nếu chúng ta có một thuật toán giải bài toán MLP trong đồ thị metric với độ phức tạp thời gian là O(T(n.
- thì cùng chất lượng lời giải tương tự, thuật toán đó giải bài toán MLP tổng quát với độ phức tạp thời gian là O(T(n.
- trong đó, f(n) là độ phức tạp thời gian cho việc tính đường đi ngắn nhất giữa các cặp đỉnh trong đồ thị G (chẳng hạn, nếu sử dụng thuật toán Floyd-Warshall, ta có f(n.
- 5 1.2 Một số hƣớng tiếp cận giải bài toán tối ƣu hóa tổ hợp Đối với bài toán thuộc lớp NP – khó như bài toán MLP, hiện tại có một số hướng tiếp cận thường được áp dụng để phát triển thuật toán sau đây.
- Phát triển thuật toán đúng tìm lời giải tối ưu.
- Các thuật toán theo hướng này có độ phức tạp bùng nổ tổ hợp trong trường hợp tồi nhất, mặc dù trong thực tế chúng thường chạy nhanh hơn đánh giá lý thuyết này.
- Thuật toán quy hoạch động (Dynamic programming – DP) [7], thuật toán nhánh cận (Branch and bound – B&B), quy hoạch có ràng buộc (Constraint programming – CP), quy hoạch tuyến tính dựa trên nhánh cận (Linear programming based branch and bound – LP), Branchcut, Branchprice, và Branchcutprice [29, 38] thuộc lớp thuật toán này.
- Phát triển thuật toán gần đúng cận tỷ lệ α (α – approximation algoirthm).
- Ưu điểm của lớp thuật toán là nó đảm bảo đưa ra lời giải với chi phí không lớn hơn α lần chi phí của lời giải tối ưu .
- Phát triển thuật toán meta-heuristic có độ phức tạp thời gian không quá lớn và tiến hành thực nghiệm đánh giá hiệu quả của thuật toán trên các bộ dữ liệu chuẩn.
- Thuật toán di truyền (Genetic algorithm thuật toán phỏng tôi luyện (Simulated annealing algorithm) [19], thuật toán Tabu (Tabu search) [20, 46] thuật toán lân cận biến đổi (Variable neighborhood search-VNS và thuật toán tìm kiếm địa phương (Local search) [37] thuộc lớp thuật toán này.
- Tiếp theo, là phần trình bày tổng quan về sơ đồ của một số thuật toán cơ bản để giải bài toán tối ưu tổ hợp: Thuật toán nhánh cận [29, 38], thuật toán di truyền [13, 32], thuật toán đàn kiến [10], thuật toán tabu và thuật toán lân cận biến đổi .
- 1.2.1 Thuật toán nhánh cận Ý tưởng của thuật toán trên mô hình bài toán tối ưu tổ hợp tổng quát được mô tả như sau: min {f(x): x  D}, trong đó D là tập hữu hạn phần tử.
- 6 Thuật toán nhánh cận bao gồm hai thủ tục: Phân nhánh (Branching procedure) và tính cận (Bounding procedure).
- Quá trình phân nhánh được thực hiện nhờ thuật toán quay lui.
- Ở bước tổng quát của thuật toán quay lui, ta sẽ làm việc với phương án bộ phận (a1, a2

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