Phương pháp mới giải bài toán người bán hàng sử dụng thuật toán runner – Root

Nội dung text: Phương pháp mới giải bài toán người bán hàng sử dụng thuật toán runner – Root

1. TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Nguyễn Thị Quyên PHƯƠNG PHÁP MỚI GIẢI BÀI TOÁN NGƯỜI BÁN HÀNG SỬ DỤNG THUẬT TOÁN RUNNER – ROOT A NEW METHOD FOR SOLVING TRAVELING SALESMAN PROBLEM USING RUNNER-ROOT ALGORITHM NGUYỄN THỊ QUYÊN TÓM TẮT: Bài toán người bán hàng (Travelling Salesman Problem - TSP) là bài toán tìm đường đi ngắn nhất giữa nhiều thành phố cho người bán hàng nhằm tiết kiệm thời gian và chi phí. Đây là bài toán tối ưu rời rạc phức tạp, đòi hỏi phải có các phương pháp giải hiệu quả. Bài viết trình bày một phương pháp mới dựa trên thuật toán Runner - Root (RRA) để tìm đường đi ngắn nhất cho TSP. Trong đó, RRA là thuật toán được phát triển dựa trên ý tưởng về sự nhân giống của các loại thực vật bò lan. Hiệu quả của RRA cho bài toán TSP được kiểm chứng trên TSP 14 thành phố. Dựa trên kết quả tính toán cho thấy, phương pháp đề xuất RRA là một trong những công cụ đáng được xem xét cho bài toán TSP. Từ khóa: thuật toán runner (RRA) – root; bài toán người bán hàng (TSP); đường đi ngắn nhất. ABSTRACT: The traveling salesman problem (TSP) is the problem of finding the shortest route between many cities for sellers to save time and costs. This is a complex discrete optimization problem that requires effective solutions. The article presents a new method based on the runner- root algorithm (RRA) to find the shortest route to the TSP. In which, RRA is an algorithm developed based on the idea of propagation of creeping plants. The effectiveness of RRA for the TSP is verified on the TSP of 14 cities. The calculation results show that the proposed RRA method is one of the tools worth considering for the TSP. Key words: runner-root algorithm; traveling salesman problem; shortest route. 1. ĐẶT VẤN ĐỀ biên [14], phương pháp Lagrangian [7] và các Bài toán TSP là bài toán tối ưu nổi tiếng phương pháp dựa trên các thuật toán tối ưu như nhằm tìm đường đi ngắn nhất giữa các thành giải thuật di truyền [3], tối ưu bầy đàn (Particle phố cho người bán hàng, bao gồm thành phố Swarm Optimization - PSO) [16], tối ưu đàn bắt đầu và thành phố kết thúc cùng các thành kiến [4], thuật toán tìm kiếm cuckoo [11], thuật phố đi qua nhưng tất cả chúng chỉ xuất hiện toán tìm kiếm hài hòa [1] và thuật toán đàn ong một lần trong đường đi. Bài toán TSP đã được nhân tạo [12]. Nhìn chung, sử dụng các phương ứng dụng trong cắt giấy, đi dây máy tính, định pháp cổ điển có thể thu được giải pháp tối ưu tuyến, lập lịch, mạng xã hội [2], [6]. Kể từ khi nhưng quá trình tính toán thường mất thời gian, được đề xuất lần đầu vào năm 1970 [10], bài Vì vậy, đòi hỏi phải có phương pháp giải hiệu toán TSP đã được giải bằng nhiều phương pháp quả rút ngắn thời gian hơn. Các thuật toán tối khác nhau bao gồm các phương pháp cổ điển ưu có thể thu được lời giải bài toán với thời như phương pháp nhánh và cắt [15], nhánh và gian tương đối ngắn. Do đó, sử dụng phương ThS. Trường Đại học Văn Lang, quyen.nt@vlu.edu.vn, Mã số: TCKH25-04-2021 85
2. TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Số 25, Tháng 01 - 2021 pháp mới cho bài toán TSP luôn là một vấn đề mẹ đại diện cho một thành phố như trong biểu cần thiết. thức: 푡ℎ 표푡ℎ푒 ,𝑖 = [ 1, 2, , j, ] (3) Thuật toán runner – root (RRA) được phát Trong đó, 푡ℎ 표푡ℎ푒 ,𝑖 là đường đi thư i triển dựa trên ý tưởng nhân giống qua thân của trong quần thể N đường đi. j là thành phố thứ j một số loài cây như cỏ nhện, dâu tây hay cây trong đường đi. là số thành phố. mẫu tử [8]. Để giải bài toán tối ưu, mỗi giải Để bắt đầu quá trình tìm kiếm, mỗi đường pháp được xem như một cây mẹ. Cây mẹ sinh đi được khởi tạo như sau: 푡ℎ 표푡ℎ푒 ,𝑖 = ra các cây con qua thân của nó để khai thác 푡ℎ푙표푤 + 푛 . ( 푡ℎℎ𝑖 ℎ − 푡ℎ푙표푤) (4) nguồn tài nguyên. Các cây con sinh ra ở nơi có Trong đó, 푡ℎ푙표푤 và 푡ℎℎ𝑖 ℎ là véc tơ nguồn tài nguyên phong phú sẽ phát triển mạnh giới hạn của các biến trong đường đi. và tiếp tục sinh ra các cây con khác ngược lại Do mỗi thành phố được biểu diễn dưới chúng sẽ chết đi. Thuật toán RRA đã thể hiện dạng số nguyên dương, nên các phần tử trong được nhiều ưu điểm trong việc tìm giải pháp tối đường đi 푡ℎ sẽ được sắp xếp theo ưu cho các hàm toán chuẩn [8]. Ngoài ra, thuật 표푡ℎ푒 ,𝑖 thứ tự tăng dần. Khi đó, vị trí của các biến toán RRA cũng đã được áp dụng thành công trong mảng đã được sắp xếp sẽ được quy ước là trong một số lĩnh vực như kỹ thuật điện [9], dự thành phố tương ứng với biến đó. Chẳng hạn báo sản xuất [5]. Tính cấp thiết của bài viết là như bài toán tìm đường đi ngắn nhất qua 4 trình bày chi tiết các bước áp dụng thuật toán thành phố, giá trị của 푡ℎ = RRA để tìm đường đi ngắn nhất cho bài toán 표푡ℎ푒 ,𝑖 TSP hiệu quả hơn với thời gian ngắn hơn. [2.3, 5.6, 4.3, 1.8] thì đường đi tương ứng sẽ là 2. NỘI DUNG [2, 4, 3, 1]. Sau khi được khởi tạo, các đường đi 2.1. Mô hình bài toán TSP sẽ được đánh giá hàm mục tiêu như mô tả ở biểu thức (1) để xác định chiều dài của mỗi Cho 𝑖푡 thành phố và tọa độ của mỗi đường đi. Khi đó, đường đi có chiều dài ngắn thành phố, chiều dài đường đi giữa các thành phố nhất (퐿 푒푠푡) sẽ được xem như là đường đi tốt 푡ℎ = [ 1, 2, , ] được xác định như 푖푡 nhất 푡ℎ . −1 푒푠푡 ( ) ∑ 푖푡 ( ) sau: 퐿 푡ℎ = 𝑖=1 𝑖, 𝑖+1 + ( 푛, 1) (1) Bước 2: Tạo ra quần thể đường đi mới. Ý Trong đó, ( 𝑖, 𝑖+1) là khoảng cách Euler tưởng mỗi cây mẹ sinh ra một cây con qua thân giữa hai thành phố được xác định như sau: của nó được thể hiện trong thuật toán RRA trong 2 2 ( 𝑖, 𝑖+1) = √( 𝑖 − 𝑖+1) + ( 𝑖 − 𝑖+1) (2) quá trình tạo ra các giải pháp mới như sau: Trong đó, ( 𝑖, 𝑖) và ( 𝑖+1, 𝑖+1) lần lượt 푡ℎ ℎ푡푒 , = là tọa độ của hai thành phố i và j. 푡ℎ , = 1 { 푒푠푡 (5) 2.2. Thuật toán RRA cho bài toán TSP 푡ℎ 표푡ℎ푒 , + 푛푛푒 . 푛 , = 2, , Thuật toán RRA đã được áp dụng cho các Trong đó, 푡ℎ ℎ푡푒 , là đường đi mới hàm toán chuẩn. Tuy nhiên, để áp dụng thành thứ k được tạo ra từ đường đi 푡ℎ 표푡ℎ푒 , . công RRA cho bài toán TSP, các bước thực 푛푛푒 là khoảng cách lớn nhất từ biến hiện hiện của thuật toán cần được điều chỉnh [8]. Vì tại đến biến mới được đặt bằng 200. vậy, trong mục này chi tiết áp dụng thuật toán Các đường đi mới sẽ được đánh giá hàm RRA cho bài toán TSP được mô tả như sau: mục tiêu như mô tả ở biểu thức (1) để xác định Bước 1 - Khởi tạo: Để tìm đường đi ngắn chiều dài của mỗi đường đi 퐿 ℎ푡푒 , . Dựa nhất cho bài toán TSP, mỗi đường đi khả thi được trên chiều dài của mỗi đường đi mới, giá trị xem như một cây mẹ. Trong đó, mỗi biến của cây 푡ℎ 푒푠푡 được cập nhật lại. 86
3. TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Nguyễn Thị Quyên Bước 3: Cập nhật đường đi tốt nhất. Sau tại chưa đạt tới giá trị lớn nhất đặt trước hai vòng lặp liên tiếp mà đường đi tốt nhất thu (𝑖푡푒 ), thuật toán sẽ quay trở lại bước 2 để được không có sự cải thiện về chiều dài đường tiếp tục quá trình tìm kiếm. Ngược lại, thuật đi, thì thủ tục cập nhật đường đi tốt nhất được toán sẽ được dừng lại và đường đi tốt nhất thực hiện. Trong đó, sẽ có 2. đường đi mới 푡ℎ 푒푠푡 được xem như là lời giải cho bài toán. được tạo ra bằng cách điều chỉnh lần lượt từng Toàn bộ các bước thực hiện của thuật toán biến của 푡ℎ 푒푠푡 như sau: RRA cho bài toán TSP được trình bày trong lưu 푡ℎ1, = , . 푛푛푒 . 푡ℎ 푒푠푡 + 푡ℎ 푒푠푡 (6) đồ ở Hình 1. Bắt đầu 푡ℎ2, = , . 표표푡. 푡ℎ 푒푠푡 + 푡ℎ 푒푠푡 (7) - Khởi tạo ngẫu nhiên quần thể đường đi ban đầu sử dụng (4) Trong đó, 푡ℎ1, và 푡ℎ2, là đường đi - Tính hàm mục tiêu cho mỗi đường đi sử dụng (1) - Xác định đường đi tốt nhất pathbest với chiều dài Lbest thứ d được tạo ra với d = 1, 2, , . , là - Đặt vòng lặp i = 1 dòng thứ d của ma trân đơn vị có kích thước ( × ). 표표푡 là hằng số có giá trị nhỏ hơn Lbest_old = Lbest so với 푛푛푒 , nó thường được chọn bằng ½ Tạo ra quần thể đường đi mới sử dụng (5) giá trị của 푛푛푒 . Tính hàm mục tiêu cho mỗi đường đi sử dụng (1) Các đường đi mới được tính toán hàm mục tiêu. Cập nhật đường đi tốt nhất pathbest với chiều dài Lbest Nếu tồn tại đường đi có chiều dài ngắn hơn 푡ℎ 푒푠푡 Lbest = Lbest_old Sai nó sẽ được chọn để thay thế cho 푡ℎ 푒푠푡. Đúng Bước 4: Lựa chọn đường đi cho thế hệ tiếp Tạo ra 2.NC đường đi mới sử dụng (6) và (7) theo. Quần thể cây mẹ cho vòng lặp sau được chọn Tính hàm mục tiêu cho mỗi đường đi mới sử dụng (1) từ quần thể cây con. Khi đó, xác suất để cây con Cập nhật đường đi tốt nhất pathbest với chiều dài Lbest 푡ℎ ℎ푡푒 , được chọn để trở thành một cây mẹ ở vòng lặp tiếp theo được xác định như sau: Lựa chọn quần thể cây mẹ từ các cây con sử dụng (8) và (9) ( 푡ℎ 𝑔ℎ푡푒 , ) Sai L = L = N (8) best best_old ∑ ( 푡ℎ 𝑔ℎ푡푒 ,j) 푗=1 Đúng ct = ct + 1 ct = 0 Trong đó, ( 푡ℎ ℎ푡푒 , ) là giá trị thích nghi của cây con 푡ℎ ℎ푡푒 , được tính như sau: Sai ct = iterrestart 1 Đúng ( 푡ℎ ℎ푡푒 , ) = (9) 휎+퐿 𝑔ℎ푡푒 , −퐿 푒푠푡 Khởi tạo ngẫu nhiên quần thể đường đi ban đầu sử dụng (4) Trong đó, 휎 là hằng số nhỏ nhằm loại trừ Sai i = i + 1 i itermax phép chia cho 0 trong trường hợp giá trị của Đúng Xuất kết quả: pathbest và Lbest 퐿 ℎ푡푒 , và 퐿 푒푠푡 bằng nhau. Bước 5: Khởi động lại quần thể cây mẹ. Kết thúc Trong trường hợp sau một số vòng lặp định Hình 1. Lưu đồ thuật toán RRA cho bài toán TSP 2.3. Kết quả tính toán trước (𝑖푡푒 푒푠푡 푡) mà đường đi tốt nhất vẫn không được cải thiện, thì thuật toán RRA sẽ Trong phần này, phương pháp RRA đề khởi tạo ngẫu nhiên lại quần thể cây mẹ bằng xuất được sử dụng để tìm đường đi ngắn nhất cách sử dụng biểu thức (4) nhằm gia tăng cơ cho một bài toán TSP có 14 thành phố được gọi hội khai phá không gian tìm kiếm. là Burma14 [13]. Trong đó, tọa độ của mỗi Bước 6: Kiểm tra điều kiện dừng. Thuật thành phố được cho trong Bảng 1. Phương toán RRA cho bài toán TSP hoạt động dựa trên pháp đề xuất RRA được lập trình từ phần mềm số lượng vòng lặp tối đa. Nếu số vòng lặp hiện Matlab 2016a chạy trên máy tính cá nhân CPU core i5 2x2.4GH, 8GB RAM. Thông số RRA 87
4. TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Số 25, Tháng 01 - 2021 bao gồm kích thước quần thể N và số vòng lặp đi tốt nhất trong hầu hết các lần chạy. Điều này lớn nhất 𝑖푡푒 được chọn lần lượt bằng 20 và cho thấy, sự ổn định và độ tin cậy cao của thuật 50. Trong khi đó, giá trị của 𝑖푡푒 푒푠푡 푡 được toán RRA cho bài toán TSP. chọn bằng ½ giá trị của 𝑖푡푒 . Phương pháp Bảng 1. Tọa độ các thành phố của bài toán Burma14 đề nghị được chạy 100 lần độc lập để đánh giá x 16.47 16.47 20.09 22.39 25.23 22.00 20.47 hiệu quả của phương pháp. Kết quả tính toán cho bài toán được trình y 96.10 94.44 92.54 93.37 97.24 96.05 97.02 bày ở Bảng 2. Trong đó, chiều dài đường đi ngắn x 17.20 16.30 14.05 16.53 21.52 19.41 20.09 nhất thu được từ RRA cho Burma14 là 30.8785 tương ứng với đường đi ngắn nhất là {13, 7, 5, y 96.29 97.38 98.12 97.38 95.59 97.13 94.55 12, 6, 4, 3, 14, 2, 1, 10, 9, 11, 8} được mô tả ở Hình 2. Kết quả này hoàn toàn tương tự với kết quả thu được từ phương pháp PSO [16]. Tuy nhiên, giá trị trung bình của hàm mục tiêu thu được bởi RRA trong 100 lần chạy bé hơn so với phương pháp PSO [16]. Đặc tuyến hội tụ lớn nhất, nhỏ nhất và trung bình trong 100 lần chạy độc lập ở Hình 3a cho thấy đường đặc tuyến hội tụ trung bình rất gần với đường hội tụ nhỏ nhất. Giá trị hàm mục tiêu thu được trong 100 lần chạy Hình 2. Đường đi tốt nhất thu được từ RRA ở Hình 3b cho thấy RRA có thể tìm được đường Bảng 2. Kết quả tính toán cho bài toán TSP Burma14 Phương pháp Đường đi tốt nhất 푳 풙 푳 풊풏 푳 풆 풏 STD Thời gian tính toán (s) 13, 7, 5, 12, 6, 4, 3, RRA 31.8283 30.8785 30.9012 0.1140 0.2098 14, 2, 1, 10, 9, 11, 8 13, 7, 5, 12, 6, 4, 3, PSO [16] 31.022 30.8785 30.9245 - - 14, 2, 1, 10, 9, 11, 8 Hình 3. Đặc tuyến hộ tụ trung bình và giá trị hàm mục tiêu trong 100 lần chạy 3. KẾT LUẬN thực hiện. RRA là một phương pháp hiệu quả và Bài viết trình bày ứng dụng của thuật toán tin cậy trong việc tìm lời giải cho bài toán TSP. RRA cho bài toán TSP. Hiệu quả của RRA được Trong tương lai, chúng tôi sẽ sử dụng thuật toán kiểm chứng trên bài toán TSP có 14 thành phố. RRA cho các bài toán TSP có nhiều thành phố Kết quả thu được bởi RRA trong 100 lần chạy hơn cũng như áp dụng phương pháp đề xuất vào độc lập được so sánh với phương pháp PSO đã một số ứng dụng thực tế. 88
5. TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Nguyễn Thị Quyên TÀI LIỆU THAM KHẢO [1] Boryczka U. and Szwarc K. (2019), The Harmony Search algorithm with additional improvement of harmony memory for Asymmetric Traveling Salesman Problem, 122, Elsevier, Expert Systems with Applications. [2] Campuzano G., Obreque C., and Aguayo M. M. (2020), Accelerating the Miller–Tucker–Zemlin model for the asymmetric traveling salesman problem, 148, Elsevier, Expert Systems with Applications. [3] Dong X. and Cai Y. (2018), A novel genetic algorithm for large scale colored balanced traveling salesman problem, 95, Elsevier, Future Generation Computer Systems. [4] Ebadinezhad S. (2020), DEACO: Adopting dynamic evaporation strategy to enhance ACO algorithm for the traveling salesman problem, 92, Elsevier, Engineering Applications of Artificial Intelligence. [5] Goli A., Moeini E., Shafiee A. M., Zamani M., and Touti E. (2020), Application of Improved Artificial Intelligence with Runner-Root Meta-Heuristic Algorithm for Dairy Products Industry: A Case Study, 29(5), World Scientific Publishing, International Journal on Artificial Intelligence Tools. [6] Hu Y., Yao Y., and Lee W. S. (2020), A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs, 204, Elsevier, Knowledge-Based Systems. [7] Laporte G. (1992), The traveling salesman problem: An overview of exact and approximate algorithms, 59 (2), Elsevier, European Journal of Operational Research. [8] Merrikh-Bayat F. (2015), The runner-root algorithm: A metaheuristic for solving unimodal and multimodal optimization problems inspired by runners and roots of plants in nature, 33, Elsevier, Applied Soft Computing. [9] Nguyen T. T., Nguyen T. T., Truong A. V., Nguyen Q. T., and Phung T. A. (2017), Multi- objective electric distribution network reconfiguration solution using runner-root algorithm, 52, Elsevier, Applied Soft Computing. [10] Oliver I. M., Smith Dj. And Holland J. R. (1987), Study of permutation crossover operators on the traveling salesman problem, The Massachusetts Institute of Technology, Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms. [11] Ouaarab A., Ahiod B., and Yang X. S. (2014), Discrete cuckoo search algorithm for the travelling salesman problem, 24, Springer, Neural Computing and Applications. [12] Pandiri V. and Singh A. (2019), An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem, 78, Elsevier, Applied Soft Computing. [13] Reinelt G. (1991), TSPLIB. A traveling salesman problem library, 3(4), The Institute for Operations Research and the Management Sciences, ORSA journal on computing. [14] Salman R., Ekstedt F., and Damaschke P. (2020), Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem, 48(2), Elsevier, Operations Research Letters. [15] Yuan Y., Cattaruzza D. Ogier M. and Semet F. (2020), A branch-and-cut algorithm for the generalized traveling salesman problem with time windows, 286, Elsevier, European Journal of Operational Research. [16] Yuan Z., Yang L., Wu Y., Liao L., and Li G. (2007), Chaotic particle swarm optimization algorithm for traveling salesman problem, IEEE, Proceedings of the IEEE International Conference on Automation and Logistics. Ngày nhận bài: 26-8-2020. Ngày biên tập xong: 11-01-2021. Duyệt đăng: 22-01-2021 89