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)

- Phát triển thuật toán gần đúng cận tỷ lệ α (α – approximation algoirthm).
- Phát triển thuật toán meta-heuristic 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.
- Thời gian chạy của thuật toán đề xuất là nhanh hơn thuật toán của Wu et al.
- Sau đó, chúng tôi đề xuất thuật toán gần đúng dựa trên phương pháp Subgradient với cận tỷ lệ được đánh giá bởi thực nghiệm là tốt hơn so với các thuật toán gần đúng cận tỷ lệ hiện biết trên nhiều bộ dữ liệu.
- Theo hướng tiếp cận meta-heuristic, chúng tôi đề xuất ba thuật toán giải bài toán MLP.
- Đầu tiên, đề xuất thuật toán dựa trên lược đồ thuật toán di truyền giải bài toán MLP.
- Sau đó, đề xuất về thuật toán lai ghép giữa thuật toán di truyền và thuật toán đàn kiến.
- Cuối cùng, đề xuất về thuật toán lai ghép giữa thuật toán Tabu và thuật toán đa lân cận để giải bài toán MLP.
- Kết quả thực nghiệm cho thấy các thuật toán đề xuất đưa ra lời giải với chất lượng 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.
- 9.20 Kết quả thực nghiệm từ các Bảng chỉ ra rằng đối với các bài toán kích thước nhỏ, thuật toán có thể tìm được lời giải tối ưu trong khoảng thời gian nhỏ.
- 1.3.1 Thuật toán đúng Wu.
- [12] đề xuất thuật toán quy hoạch động với độ phức tạp thời gian là hàm mũ để giải bài toán MLP.
- Kết quả thực nghiệm chỉ ra rằng thuật toán của Wu et al.
- Tuy nhiên, hiệu quả của thuật toán trong bài toán MLP có kích thước lớn hơn chưa được xem xét.
- 1.3.2 Thuật toán gần đúng cận tỷ lệ Blum et al.
- [3] đưa ra một thuật toán có cận tỷ lệ 144 trong trường hợp metric.
- [2] đề xuất thuật toán gần đúng với cận tỷ lệ 17.24.
- Thuật toán của Archer et al.
- [4] đưa ra thuật toán gần đúng với cận tỷ lệ là 3.59.
- 1.3.3 Thuật toán meta-heuristic Hiện tại, có hai công trình nghiên cứu đã được công bố [8, 11].
- thực nghiệm thuật toán của họ trên các bộ dữ liệu.
- Kết quả thực nghiệm cho thấy, chất lượng lời giải thu được từ các thuật toán meta-heuristic tốt hơn rất nhiều so với chất lượng lời giải của các thuật toán gần đúng cận tỷ lệ.
- Phát triển thuật toán đúng cho phép giải bài toán với kích thước lớn hơn.
- Phát triển ba thuật toán theo hướng tiếp cận meta-heuristic: Thuật toán di truyền (GA), 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 đa lân cận (VNS).
- Để đá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.
- 1.5 Dữ liệu thực nghiệm Một trong những cách để đánh giá hiệu quả của thuật toán đó là thực thi thuật toán trên các bộ dữ liệu chuẩn.
- Thuật toán tìm được càng nhiều kỷ lục thì càng hiệu quả.
- Cuối cùng, chúng ta thảo luận điều kiện dừng thuật toán.
- Thuật toán sẽ dừng nếu sau một vài vòng lặp (ký hiệu: NL), lời giải tốt nhất không được cải thiện.
- Một vấn đề nữa là các thuật toán meta-heuristic trong [8, 11] đều dựa trên thuật toán VNS.
- Tuy nhiên, thứ tự thực hiện thì lại không được trình bày trong các thuật toán meta-heuristic trên.
- Trong mục này, chúng tôi trình bày cấu trúc của các thuật toán lân cận trong VNS.
- Để đánh giá hiệu quả của thuật toán đề xuất, chúng tôi tiến hành thực nghiệm thuật toán trên các bộ dữ liệu chuẩn.
- Từ kết quả thực nghiệm, chúng tôi đưa ra những đánh giá và so sánh hiệu quả của thuật toán với các thuật toán khác.
- Hiệu quả của thuật toán được đánh giá trên các bộ dữ liệu chuẩn.
- Kết quả thực nghiệm cũng được so sánh với kết quả của thuật toán Wu et al.
- Điều này gây ra khó khăn cho việc đánh giá một cách chính xác hiệu quả của các thuật toán giải bài toán MLP.
- Chúng tôi sử dụng thuật toán đúng để thu được lời giải tối ưu bài toán cho các file dữ liệu nhỏ.
- Từ các lời giải tối ưu có được, chúng ta có thể đánh giá một cách chính xác hiệu quả của các thuật toán gần đúng sau này.
- 2.1 Lược đồ thuật toán Giả sử, chúng ta có T = (v1, v2, v3.
- Thuật toán luôn cập nhập giá trị cận trên (UB) của lời giải tối ưu.
- Tiếp theo, thuật toán thực hiện thủ tục đệ quy.
- Rõ ràng hiệu quả của thuật toán phụ thuộc vào chất lượng hàm ước lượng LB và UB.
- 2.2 Kết quả thực nghiệm Cận trên UB1 và UB2 lần lượt là lời giải của thuật toán lân cận gần nhất và thuật toán ACO–GA (xem trong chương 4).
- Thêm vào đó, thuật toán đề xuất cũng hiệu quả hơn so với thuật toán của Wu et al.
- Đối với bộ dữ liệu ngẫu nhiên, kết quả thực nghiệm cho thấy, thuật toán đề xuất cho kết quả lời giải tốt hơn các thuật toán meta-heuristic tốt nhất hiện biết tại nhiều file dữ liệu.
- Đối với bộ dữ liệu thực, thì thuật toán lại hiệu quả hơn khi đưa ra lời giải tốt hơn hoặc không thua so với các thuật toán meta-heuristic tốt nhất.
- Tuy nhiên, thời gian chạy của thuật toán không tốt bằng thời gian chạy thuật toán của M.
- 1 Kết quả thực nghiệm thuật toán với n = 30 Bộ dữ liệu EA1 EA2 Bộ dữ liệu ngẫu nhiên Bộ dữ liệu ngẫu nhiên Bộ dữ liệu thực Bảng 2.
- 2 Kết quả thực nghiệm thuật toán với n = 35 Bộ dữ liệu EA1 EA2 Bộ dữ liệu ngẫu nhiên Bộ dữ liệu ngẫu nhiên Bộ dữ liệu thực Bảng 2.
- 3 Kết quả thực nghiệm thuật toán với n = 40 Bộ dữ liệu EA1 EA2 Bộ dữ liệu ngẫu nhiên Bộ dữ liệu ngẫu nhiên Bộ dữ liệu thực Bảng 2.
- Đầu tiên, trình bày 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ệ giải bài toán.
- Các kết quả thực nghiệm trên bộ dữ liệu chuẩn là cơ sở để đưa ra các đánh giá và so sánh về hiệu quả giữa các thuật toán trên ba khía cạnh: cận tỷ lệ thực nghiệm, thời gian chạy và chất lượng cận dưới.
- Sau đó, chúng tôi trình bày thuật toán dựa trên phương pháp Subgradient.
- 3.1 Nghiên cứu thực nghiệm về hiệu quả của các thuật toán 3.1.1 Các thuật toán gần đúng cận tỷ lệ 3.1.1.1 Thuật toán Blum et al.
- Thuật toán của Blum et al.
- có cận tỷ lệ là 16 nếu sử dụng thuật toán gần đúng cận tỷ lệ 2 cho bài toán k−MST [5].
- 3.1.1.2 Thuật toán Goemans et al.
- 3.1.1.3 Thuật toán Archer et al.
- đề xuất thuật toán tạo ra một tập các cây k–MST (k = 2.
- Cận tỷ lệ của thuật toán được Archer et al.
- Thuật toán không giảm cận tỷ lệ so với thuật toán của Goemans et al.
- 3.1.1.4 Thuật toán Chauhuri et al.
- 3.1.1.5 Thuật toán Arora et al.
- Thuật toán ACO-GA duy trì ba loại kiến.
- Thực nghiệm cho thấy cận tỷ lệ thực tế của các thuật toán tốt hơn rất nhiều so với cận tỷ lệ lý thuyết.
- Chất lượng lời giải đưa ra bởi thuật toán Arora et al.
- Tuy nhiên, thuật toán Arora et al.
- Thuật toán Blum et al.
- Cận tỷ lệ của thuật toán Goemans et al.
- nhỉnh hơn so với cận tỷ lệ của thuật toán Archer et al.
- Thời gian chạy của các thuật toán của Arora et al., Chaudhuri et al.
- Thực vậy, thuật toán của K.
- Thuật toán của K.
- Trong bước 1, thuật toán tìm một tập các lời giải của bài toán k-troll (k = 2, 3.
- Sau đó, thuật toán chuyển các Tk thành các hành trình Euler Ck (k = 2.
- từ đó suy ra thuật toán có cận tỷ lệ tương ứng là 3.59.
- 3.2.1 Lược đồ thuật toán Chúng tôi đề xuất một thuật toán dựa trên phương pháp Subgradient.
- Thuật toán đàn kiến được sử dụng để khởi tạo quần thể ban đầu cho thuật toán di truyền.
- Chúng ta gọi AA, AS, MS, GA lần lượt là thuật toán của Archer et al.
- [11], và thuật toán di truyền.
- Chúng ta gọi12,,gap gap Tlà gap1, gap2 và thời gian chạy trung bình của các thuật toán tính theo phút đối với mỗi bộ dữ liệu.
- Kết quả thực nghiệm cho thấy, đối với các file dữ liệu nhỏ, thuật toán GA có chất lượng lời giải sát với lời giải tối ưu.
- Đặc biệt, thuật toán đưa ra lời giải tối ưu tại một vài file dữ liệu.
- Ngoài ra, chất lượng lời giải thu được từ thuật toán GA tốt hơn chất lượng lời giải của các thuật toán gần đúng cận tỷ lệ hiện biết tại hầu hết các file dữ liệu.
- Đối với các file dữ liệu lớn, thuật toán GA vẫn cho 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 gần đúng cận tỷ lệ.
- So với chất lượng lời giải và thời gian chạy của các thuật toán của Salehipour et al., và M.
- Silva, thì thuật toán GA không tốt bằng.
- Bảng 4.1 Kết quả thực nghiệm của thuật toán GA với các bộ dữ liệu nhỏ Bộ dữ liệu 1.
- 3.2.2 Kết quả thực nghiệm Chúng ta gọi KA, SGA lần lượt là thuật toán của K.
- Chaudhuri et al’s [4] và thuật toán đề xuất.
- Gọi Li, pi, Ti (i = 1, 2) lần lượt là độ trễ của lời giải, cận tỷ lệ và thời gian chạy tính theo phút của các thuật toán KA, và SGA.
- Đối với các file dữ liệu nhỏ, khi mà lời giải tối ưu được biết từ thuật toán đúng, thì21421.
- 2T 1T Bộ dữ liệu thực Bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx Trung bình CHƯƠNG 4 CÁC THUẬT TOÁN META-HEURISTIC Chương này trình bày ba thuật toán giải bài toán MLP theo hướng tiếp cận meta-heuristic.
- Đầu tiên, chương này trình bày thuật toán dựa trên lược đồ thuật toán di truyền giải bài toán MLP.
- Sau đó, trình bày về thuật toán lai ghép giữa thuật toán di truyền và thuật toán đàn kiến.
- Cuối cùng, trình bày về thuật toán lai ghép giữa thuật toán Tabu và thuật toán đa lân cận để giải bài toán MLP.
- Chương này kết thúc bởi phần trình bày các kết quả thực nghiệm, đánh giá và so sánh với các thuật toán hiện biết.
- Các cá thể còn lại được tạo ra theo thuật toán láng giềng gần nhất.
- Thuật toán tìm kiếm địa phương: Chúng ta sử dụng thuật toán 2-opt, swap-adjacent, swap và 3-opt [7]

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