Một hướng tiếp cận mới giải bài toán cực tiểu độ trễ MLP

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:3

Thêm vào BST

Báo xấu

10
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Một hướng tiếp cận mới giải bài toán cực tiểu độ trễ MLP đi sâu vào nghiên cứu tìm kiếm địa phương trong phương pháp ACO. Thuật toán ACO được Dorigo đề xuất lần đầu tiên là AS (Ant System) đến nay có rất nhiều biến thể như MMSA (Max-Min Ant System), SMMAS (Smooth Min-Max Ant System) do chưa có tìm kiếm địa phương đã bộc lộ nhược điểm.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Một hướng tiếp cận mới giải bài toán cực tiểu độ trễ MLP

Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1 MỘT HƯỚNG TIẾP CẬN MỚI GIẢI BÀI TOÁN CỰC TIỂU ĐỘ TRỄ MLP Đặng Thị Thu Hiền Trường Đại học Thủy lợi, email: hiendt@tlu.edu.vn 1. GIỚI THIỆU CHUNG này đi sâu vào nghiên cứu tìm kiếm địa phương trong phương pháp ACO. Thuật toán Bài toán cực tiểu độ trễ (Minimum ACO được Dorigo đề xuất lần đầu tiên là AS Latency Problem - MLP) thuộc lớp NP-Khó. (Ant System) đến nay có rất nhiều biến thể Bài toán luôn nhận được rất nhiều sự quan như MMSA (Max-Min Ant System), SMMAS tâm nghiên cứu của các học giả. Tác giả Wu (Smooth Min-Max Ant System) do chưa có et al. đề xuất thuật toán theo hướng quy tìm kiếm địa phương đã bộc lộ nhược điểm. hoạch động với độ phức tạp thời gian hàm số Bài báo này sẽ kết hợp SMMAS và tìm kiếm mũ để giải bài toán MLP. Theo hướng gần địa phương nên đã thể hiện ưu điểm vượt trội đúng cận tỷ lệ có Blum et al., Goemans et al., thông qua kết quả thực nghiệm chạy trên các Arora et al.. Gần đây, K.Chaudhuri et al. [1] bộ dữ liệu chuẩn TSPLIB[4]. đưa ra thuật toán gần đúng với cận tỷ lệ là 3.59 đây là cận tỷ lệ nhỏ nhất hiện nay cho 2. PHƯƠNG PHÁP NGHIÊN CỨU bài toán MLP. Hiện nay, có hai công trình nghiên cứu theo hướng tiếp cận meta- 2.1. Bài toán MLP heuristic giải bài toán MLP đã được công bố. Cho đồ thị đầy đủ Kn với tập đỉnh V = Đó là A. Salehipour et al. [2] đề xuất thuật {1,2,…,n} và ma trận chi phí không âm C = { toán meta-heuristic dựa trên GRASP (Greedy cij | i,j=1,2,…,n} với cij là khoảng cách giữa randomized adaptive search procedure) và hai đỉnh i và j. Giả sử T = (v1, v2,…,vn) là một VNS (Variable neighborhood search). Sau hành trình xuất phát từ v1 (đường đi xuất phát đó, M. Silva et al. [3] cũng đề xuất một thuật từ v1 đi qua mỗi đỉnh của đồ thị đúng một toán meta-heuristic khác dựa trên lược đồ của lần) trên Kn. Kí hiệu P(v1,vk) là đoạn đường GRASP, ILS (Iterated local search) và đi từ v1 đến vk trên hành trình T. Ta gọi độ trễ RVND (Random variable neighborhood của đỉnh vk trên hành trình T, ký hiệu bởi descend) thực nghiệm cho thấy, chất lượng lat(vk), là độ dài của đường đi P(v1,vk): lời giải thu được từ các thuật toán meta- k 1 heuristic tốt hơn rất nhiều so với chất lượng lat(v k )   i1 C  vi, vi  1 , k = 2, 3,…, n. lời giải của các thuật toán gần đúng cận tỷ lệ Độ trễ của hành trình T, ký hiệu là L(T) hiện biết. Điều đó chứng tỏ, meta-heuristic là được định nghĩa như là tổng độ trễ của tất cả hướng tiếp cận tiềm năng cho bài toán MLP. các đỉnh thuộc nó: L(T) = lat(vk). Trong bài báo này chúng tôi dùng phương Giả sử v1 là đỉnh cho trước, bài toán MLP pháp tối ưu hóa đàn kiến (Ant Colony yêu cầu tìm hành trình xuất phát từ đỉnh v1 Optimization - ACO) là cách tiếp cận meta- với độ trễ là nhỏ nhất. heuristic tương đối mới. Để giải quyết một 2.2. Phương pháp ACO bài toán bằng phương pháp ACO thì có 4 điểm quan trọng: lập đồ thị cấu trúc, thông Dựa theo quy luật di chuyển theo vết mùi tin heuristic, quy tắc cập nhật mùi. Bài báo (pheromone trail) của đàn kiến. Các thuật 120
Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1 toán ACO sử dụng kết hợp thông tin kinh 3. KẾT QUẢ NGHIÊN CỨU nghiệm (heuristic) và học tăng cường qua các 3.1. Thuật toán mới cải tiến SMMAS_LS vết mùi của các con kiến nhân tạo để giải các bài toán tối ưu tổ hợp bằng cách đưa về tìm Kết hợp thuật toán SMMAS với tìm kiếm đường đi tối ưu trên đồ thị cấu trúc của bài địa phương để giải quyết bài toán MLP là toán. Thuật toán ACO đầu tiên là hệ kiến một cách tiếp cận đầy tiềm năng. Thuật toán (AS) đến nay có rất nhiều biến thể. SMMAS áp dụng trực tiếp cho bài toán MLP Thuật toán SMMSA: Có tư tưởng giống với đồ thị cấu trúc G (V, E, H, ) không gian như MMAS. Sau khi cá thể kiến xây dựng lời tìm kiếm là tập hành trình có thể. Ràng buộc giải xong. Chỉ cho phép cá thể kiến tốt nhất sẽ được thỏa mãn khi hành trình do kiến xây dựng là một hành trình đúng (là chu trình được cập nhật mùi trong mọi vòng lặp của Hamiton), biểu diễn một hoán vị các chỉ số thuật toán (I-best (cá thể kiến tốt nhất tại của các đỉnh. vòng lặp hiện tại) hoặc G-best (cá thể kiến tốt Quá trình kiến xây dựng lời giải theo thủ nhất đến thời điểm hiện tại)). Để tránh hiện tục bước ngẫu nhiên được thực hiện như sau : tượng tắc nghẽn SMMAS sử dụng hai cận Lựa trọn đỉnh xuất phát (kiến được đặt bởi trên max, min để khống chế vết mùi trên mỗi hàm ngẫu nhiên trong khoảng từ (1,n). cạnh. Các vết mùi ban đầu được khởi tạo Thực hiện lặp bước mở rộng bằng cách bằng max cho tất cả các cạnh. Sau mỗi vòng thêm một đỉnh kiến chưa đi qua cho đến khi lặp đều được bay hơi với hệ số . Hơn nữa, tất cả đỉnh được thăm. 1 Tại mỗi đỉnh kiến lựa trọn đỉnh tiếp theo việc thay k bởi max không ảnh thông qua thông tin heuristic và thông tin vết L  w(t)  mùi, chọn ngẫu nhiên đỉnh thêm vào theo hưởng tới việc học tăng cường. Do đó, thuật phân bố xác xuất này. toán SMMAS đưa ra quy tắc cập nhật mùi Quay trở lại đỉnh xuất phát. như sau: Sau khi tất cả kiến xây dựng lời giải xong. ij  t  1  1    ij  t   ij  t  Ta tìm kiếm cục bộ cải thiện lời giải. Cuối cùng là cập nhật vết mùi trên đường trong đó: mà kiến đã đi qua lặp lại các bước cho đến  max nÕu c¹nh (i, j) thuéc w(t) khi tìm được lời giải tối ưu. ij (t)    min nÕu kh¸c Procedure Thuật toán SMMAS_LS Khi giải các bài toán tối ưu tổ hợp MLP, Input: G = (V,E) các thuật toán ACO cho hiệu quả rất tốt khi Output: Một chu trình và tổng độ dài của nó; kết hợp với tìm kiếm địa phương. Các thuật BEGIN toán tìm kiếm địa phương tìm ra các lời giải Khởi tạo tham số, ma trận mùi, khởi tạo m tối ưu cục bộ và áp dụng chúng để cập nhật con kiến; repeat mùi. Công việc của chúng là tìm ra một miền for k = 1 to m do cục bộ của lời giải hiện tại (thông qua các Kiến k xây dựng lời giải; phép biến đổi láng giềng) rồi thực hiện tìm Cải tiến lời giải do kiến k xây dựng kiếm địa phương trong phạm vi này để có bằng tìm kiếm cục bộ; được lời giải tối ưu toàn cục. end for Tuy nhiên, tìm kiếm địa phương trong giai Cập nhật mùi; đoạn đầu của các thuật toán ACO thực sự Cập nhật lời giải tốt nhất; không hiệu quả khi các lời giải còn được sinh until (Điều kiện kết thúc); Đưa ra lời giải tốt nhất; ra ngẫu nhiên. Vì thế nên áp dụng tìm kiếm END địa phương khi vết mùi giữa các cạnh đã khác nhau khá lớn. Hình 1. Lược đồ thuật toán SMMAS_LS 121
Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1 3.2. Dữ liệu thực nghiệm Nhận xét: Kết quả thực nghiệm cho thấy, với cùng thời gian chạy 20 giây, thuật toán Thực nghiệm trên bộ dữ liệu chuẩn của bài SMMAS_LS đều tốt hơn hẳn so với toán TSP đó là TSPLIB [14]: eil51.tsp, SMMAS, ngoài ra ở cột giá trị trung bình, tốt eil76.tsp, att532.tsp… Bộ dữ liệu phức tạp có nhất, tồi nhất, kết quả không chênh lệch kích thước là 51 đến 2392 đỉnh. Chúng tôi cài nhiều, thể hiện tính ổn định thuật toán. đặt hai thuật toán SMMAS và SMMAS_LS. Với mỗi bộ dữ liệu chạy 10 lần để lấy kết quả Bảng 1. Các tham số thực nghiệm tốt nhất, xấu nhất và kết quả trung bình để so Tham số Giá trị sánh. Cả hai thuật toán đều được viết bằng Tham số bay hơi (rho) 0.5 ngôn ngữ C++. Số lần lặp (Nc) 50000 3.3. So sánh SMMAS và SMMAS_LS Số con kiến (nant) 25 Α 1.0 Thực hiện trên thuật toán SMMAS có tìm Β 2.0 kiếm địa phương đổi 2 đỉnh cải thiện lời giải. M 2 Cứ sau 250 bước lặp mà không tìm thấy lời Tmax 1/rho.nn_tour() giải tốt hơn thì khởi tạo lại vết mùi. Tmin Tmax/M Bảng 2: Kết quả so sánh SMMAS, SMMAS_LS SMMAS SMMAS_LS Dữ liệu Tốt Nhất Tồi Nhất TB Tốt Nhất Tồi Nhất TB eil51 11304 11891 11594.6 9778 9867 9833.1 eil76 22271 23492 22995.4 17863 18117 17979.5 eil101 34372 36315 35468.6 27779 28505 28201.6 d198 1235769 1300265 1273921 984011 1005367 996461.7 kroA100 1235681 1293697 1267358 956108 969423 962482.8 lin318 8163565 8371530 8276317 6355808 6471739 6413166.7 pcb442 16212359 16763344 16557123 11140846 11315859 11221289.1 att532 8720962 8907848 8790766 8720962 8907848 8790766 st70 24171 25547 24861.3 20887 20988 20916.2 4. KẾT LUẬN 5. TÀI LIỆU THAM KHẢO Tối ưu hóa đàn kiến là một phương pháp [1] K. Chaudhuri, B. Goldfrey, S. Rao (2003), tiếp cận có nhiều ứng dụng để giải các bài and K. Talwar, Path, Tree and minimum toán tối ưu tổ hợp. Bài báo trình bày về latency tour, Proc. FOCS, 2003, pp. 36-45 phương pháp tối ưu đàn kiến, đề xuất một [2] A. Salehipour, K. Sorensen, P. Goos, and thuật toán mới kết hợp giữa SMMAS và tìm O.Braysy (2011), Efficient GRASP+VND kiếm địa phương để giải bài toán MLP. and GRASP+VNS metaheuristics for the Kết quả thực nghiệm cho thấy traveling repairman problem, J. Operations SMMAS_LS có tìm kiếm địa phương bước Research, Vol 9. No. 2, pp. 189-209. đầu cho kết quả tốt hơn hẳn SMMAS không [3] M. Silva, A. Subramanian, T. Vidal, and L. có tìm kiếm địa phương với cùng thời gian Ochi (2012), A simple and effective chạy. Trong thời gian tới chúng tôi tiếp tục metaheuristic for the Minimum Latency Problem, J. Operations Research, Vol 221, thực nghiệm đánh giá về tốc độ hội tụ của No. 3, pp. 13-520. thuật toán mới cũng như so sánh với một số [4] http://www.iwr.uniheidelberg.de/groups thuật toán khác. Chúng tôi hi vọng các kết quả /comopt/software/TSPLIB95. này sẽ là động lực để mở ra các hướng nghiên cứu khác trong tương lai, như dùng mạng nơ- ron RBF cho việc tìm kiếm địa phương cũng là một cách tiếp cận đầy hứa hẹn. 122