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

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.
Nội dung trích xuất từ tài liệu:
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ố  ...