Kết hợp mạng nơ ron RBF với thuật toán ACO giải bài toán MLP

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

Thêm vào BST

Báo xấu

17
lượt xem 5
download

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

Bài viết Kết hợp mạng nơ ron RBF với thuật toán ACO giải bài toán MLP trình bày việc cải tiến việc tìm kiếm địa phương khi dùng mạng nơ-ron RBF kết hợp với thuật toán SMMAS_LS, nên đã thể hiện ưu điểm vượt trội thông qua kết quả thực nghiệm chạy trên các bộ dữ liệu chuẩn TSPLIB[

Chủ đề:

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

Lưu

Nội dung Text: Kết hợp mạng nơ ron RBF với thuật toán ACO giải bài toán MLP

Tuyển tập Hội nghị Khoa học thường niên năm 2018. ISBN: 978-604-82-2548-3 KẾT HỢP MẠNG NƠ-RON RBF VỚI THUẬT TOÁN ACO GIẢI BÀI TOÁN MLP Đặng Thị Thu Hiền Khoa Công nghệ thông tin - Trường Đại học Thủy lợi, email: hiendt@tlu.edu.vn 1. GIỚI THIỆU CHUNG 2. PHƯƠNG PHÁP NGHIÊN CỨU Mạng nơ-ron nhân tạo (Artifical Neural 2.1. Bài toán MLP Network) nói chung và Mạng nơ-ron RBF (Radial Basis Function) là một trong những Cho đồ thị đầy đủ Kn với tập đỉnh công cụ hữu hiệu để giải các bài toán nội suy, V = {1,2,…,n} và ma trận chi phí không âm hồi quy, tìm kiếm địa phương… Bài toán cực C = { cij | i,j=1,2,…,n} với cij là khoảng cách tiểu độ trễ (Minimum Latency Problem - giữa hai đỉnh i và j. Giả sử T = (v1, v2,…,vn) là MLP) là bài toán thuộc lớp NP-Khó. Đây là một hành trình xuất phát từ v1 (đường đi xuất bài toán nhận được nhiều sự quan tâm nghiên phát từ v1 đi qua mỗi đỉnh của đồ thị đúng một cứu vì các ứng dụng thực tế của chúng. Có rất lần) trên Kn. Kí hiệu P(v1,vk) là đoạn đường đi nhiều phương pháp đã được đề xuất để giải từ v1 đến vk trên hành trình T. Ta gọi độ trễ quyết bài toán này. Trong đó nổi lên là các của đỉnh vk trên hành trình T, ký hiệu bởi phương pháp meta-heuristic, đã có hàng loạt lat(vk), là độ dài của đường đi P(v1,vk): k 1 các tác giả đề xuất như A. Salehipour et al. [3] lat  v k    i 1 c  vi , vi1  , k  1, 2,K , n đề xuất thuật toán meta-heuristic dựa trên Độ trễ của hành trình T, ký hiệu là L(T) GRASP (Greedy randomized adaptive search được định nghĩa như là tổng độ trễ của tất cả procedure) và VNS (Variable neighborhood n search), M. Silva et al. [4] cũng đề xuất một các đỉnh thuộc nó: L  T    k 1 lat  v k  thuật toán meta-heuristic khác dựa trên lược Giả sử v1 là đỉnh cho trước, bài toán MLP đồ của GRASP, ILS (Iterated local search) và yêu cầu tìm hành trình xuất phát từ đỉnh v1 RVND (Random variable neighborhood với độ trễ là nhỏ nhất. descend). Phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp 2.2 Phương pháp ACO cận meta-heuristic tương đối mới và hiệu quả Dựa theo quy luật di chuyển theo vết mùi với bài toán MLP. Thuật toán ACO được (pheromone trail) của đàn kiến. Các thuật Dorigo đề xuất lần đầu tiên là AS (Ant System) toán ACO sử dụng kết hợp thông tin kinh đến nay có rất nhiều biến thể như MMSA nghiệm (heuristic) và học tăng cường qua các (Max-Min Ant System), SMMAS (Smooth vết mùi của các con kiến nhân tạo để giải các Min-Max Ant System) do chưa có tìm kiếm địa bài toán tối ưu tổ hợp bằng cách đưa về tìm phương đã bộc lộ nhược điểm. Trong bài báo đường đi tối ưu trên đồ thị cấu trúc của bài [1] tác giả đã đề xuất việc kết hợp thêm tìm kiếm địa phương tạo ra thuật toán mới toán. Thuật toán ACO đầu tiên là hệ kiến SMMAS_LS bước đầu đã có những ưu điểm. (AS) đến nay có rất nhiều biến thể. Bài báo này sẽ tiếp tục cải tiến việc tìm kiếm Thuật toán SMMSA: Có tư tưởng giống địa phương khi dùng mạng nơ-ron RBF kết hợp như MMAS. Sau khi cá thể kiến xây dựng lời với thuật toán SMMAS_LS, nên đã thể hiện ưu giải xong. Chỉ cho phép cá thể kiến tốt nhất điểm vượt trội thông qua kết quả thực nghiệm được cập nhật mùi trong mọi vòng lặp của chạy trên các bộ dữ liệu chuẩn TSPLIB[5]. thuật toán (I-best (cá thể kiến tốt nhất tại vòng 163
Tuyển tập Hội nghị Khoa học thường niên năm 2018. ISBN: 978-604-82-2548-3 lặp hiện tại) hoặc G-best (cá thể kiến tốt nhất 3. KẾT QUẢ NGHIÊN CỨU đến thời điểm hiện tại)). Để tránh hiện tượng 3.1. Thuật toán mới cải tiến SMMAS_RBF tắc nghẽn SMMAS sử dụng hai cận trên max, min để khống chế vết mùi trên mỗi cạnh. Các Kết hợp thuật toán SMMAS và vết mùi ban đầu được khởi tạo bằng max cho SMMAS_LS với tìm kiếm địa phương bằng tất cả các cạnh. Sau mỗi vòng lặp đều được mạng RBF để giải quyết bài toán MLP là một bay hơi với hệ số . Hơn nữa, việc thay cách tiếp cận đầy tiềm năng. Thuật toán SMMAS áp dụng trực tiếp cho bài toán MLP 1 k bởi max không ảnh hưởng tới việc với đồ thị cấu trúc G(V, E, H, ) không gian tìm L  w(t)  kiếm là tập hành trình có thể. Ràng buộc  sẽ học tăng cường. Do đó, thuật toán SMMAS được thỏa mãn khi hành trình do kiến xây dựng đưa ra quy tắc cập nhật mùi như sau: là một hành trình đúng (là chu trình Hamiton), ij  t  1  1    ij  t   ij  t  biểu diễn một hoán vị các chỉ số của các đỉnh. trong đó: Bảng 1. Lược đồ thuật toán SMMAS_RBF  nÕu c¹nh  i, j thuéc w  t  Procedure Thuật toán SMMAS_RBF ij  t    max min nÕu kh¸c Input: G = (V,E) Khi giải các bài toán tối ưu tổ hợp MLP, Output: Một chu trình tốt nhất và tổng độ dài của các thuật toán ACO cho hiệu quả rất tốt khi nó; BEGIN kết hợp với tìm kiếm địa phương. Các thuật Khởi tạo tham số, ma trận mùi, m con kiến toán tìm kiếm địa phương tìm ra các lời giải repeat tối ưu cục bộ và áp dụng chúng để cập nhật for k = 1 to m do mùi. Nên áp dụng tìm kiếm địa phương khi Kiến k xây dựng lời giải; vết mùi giữa các cạnh đã khác nhau khá lớn. Cải tiến lời giải do kiến k xây dựng bằng 2.3. Mạng nơ-ron RBF tìm kiếm cục bộ dùng mạng RBF; end for Mạng nơ-ron RBF [6] là một mạng 3 tầng Cập nhật mùi; truyền tới. Để đơn giản chúng tôi phát biểu Cập nhật lời giải tốt nhất; mạng nơ-ron RBF thông qua bài toán Nội suy until (Điều kiện kết thúc); (hay còn gọi là mạng nội suy RBF cho gọn) Đưa ra lời giải tốt nhất; Mạng RBF dùng để nội suy hàm thực n biến END f :D (Rn)  Rm. Là mạng gồm 3 tầng, tầng Quá trình kiến xây dựng lời giải theo thủ vào gồm n nút cho vectơ tín hiệu vào x  Rn, tục bước ngẫu nhiên được thực hiện như sau: tầng ẩn gồm N nơ-ron trong đó nơ-ron thứ k Lựa chọn đỉnh xuất phát (kiến được khởi gán có tâm là mốc nội suy xk và đầu ra của nó là bởi hàm ngẫu nhiên trong khoảng từ (1,n) hàm bán kính k (x) tương ứng, tầng ra gồm m Thực hiện lặp bước mở rộng bằng cách nơ-ron xác định giá trị hàm nội suy của f(x). thêm một đỉnh kiến chưa đi qua cho đến khi Để đơn giản, ta xét m=1, khi m>1 các nơ-ron tất cả đỉnh được thăm. tầng ra sẽ được huấn luyện độc lập theo thuật Tại mỗi đỉnh kiến lựa chọn đỉnh tiếp theo toán. Đến nay các trọng số của tầng ra vẫn thông qua thông tin heuristic và thông tin vết thường được tìm nhờ phương pháp gradient mùi, chọn ngẫu nhiên đỉnh thêm vào theo hoặc biến thể của nó để cực tiểu hàm E. phân bố xác xuất này. N Quay trở lại đỉnh xuất phát. E   ((x k )  y k ) 2 Sau khi tất cả kiến xây dựng lời giải xong. k 1 Ta tìm kiếm cục bộ cải thiện lời giải bằng Hàm E không bị rơi vào cực tiểu địa mạng RBF. phương và luôn có cực tiểu toàn cục nên các Cuối cùng là cập nhật vết mùi trên đường phương pháp này luôn hội tụ. mà kiến đã đi qua. 164
Tuyển tập Hội nghị Khoa học thường niên năm 2018. ISBN: 978-604-82-2548-3 Lặp lại các bước cho đến khi tìm được lời 3.3. So sánh SMMAS, SMMAS_LS và giải tối ưu. SMMAS_RBF 3.2. Dữ liệu thực nghiệm Thực hiện trên thuật toán SMMAS có tìm Thực nghiệm trên bộ dữ liệu chuẩn của bài kiếm địa phương RBF đổi 2 đỉnh cải thiện lời toán TSP đó là TSPLIB [5]: eil51.tsp, giải. Cứ sau 250 bước lặp mà không tìm thấy eil76.tsp, att532.tsp… Bộ dữ liệu phức tạp có lời giải tốt hơn thì khởi tạo lại vết mùi. kích thước là 51 đến 2392 đỉnh. Chúng tôi cài Nhận xét: Kết quả thực nghiệm cho thấy, đặt ba thuật toán SMMAS, SMMAS_LS và với cùng thời gian chạy 20 giây, thuật toán SMMAS_RBF. Với mỗi bộ dữ liệu chạy 10 SMMAS_RBF đều tốt hơn so với SMMAS lần để lấy kết quả tốt nhất, xấu nhất và kết và SMMAS_LS, ngoài ra ở cột giá trị trung quả trung bình để so sánh. Cả ba thuật toán bình, tốt nhất, tồi nhất, kết quả không chênh đều được viết bằng ngôn ngữ C++. lệch nhiều, thể hiện tính ổn định thuật toán. Bảng 2. Kết quả so sánh SMMAS, SMMAS_LS và SMMAS_RBF SMMAS SMMAS_LS SMMAS_RBF Dữ Liệu Tốt Nhất Tồi Nhất TB Tốt Nhất Tồi Nhất TB Tốt Nhất Tồi Nhất TB eil51 11304 11891 11594 9778 9867 9833 9743 9823 9783 eil76 22271 23492 22995 17863 18117 17979 16489 17892 17190.5 eil101 34372 36315 35468 27779 28505 28201 265386 278932 272159 d198 1235769 1300265 1273921 984011 1005367 996461 964753 983248 974000.5 kroA100 1235681 1293697 1267358 956108 969423 962482 944256 967624 955940 lin318 8163565 8371530 8276317 6355808 6471739 6413166 6334356 6457324 6395840 pcb442 16212359 16763344 16557123 11140846 11315859 11221289 10435674 11287451 10861562 att532 8720962 8907848 8790766 8720962 8907848 8790766 8697543 8897465 8797504 st70 24171 25547 24861 20887 20988 20916 20123 20988 20555.5 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] Đặng Thị Thu Hiền (2017), “Một hướng tiếp cận có nhiều ứng dụng để giải các bài tiếp cận mới giải bài toán cực tiểu độ trễ toán tối ưu tổ hợp. Khi kết hợp với mạng nơ- MLP”, Hội nghị thường niên trường Đại ron nhân tạo có thể cho chúng ta những kết học Thủy Lợi 11/2017. quả khả quan. Bài báo trình bày về phương [2] K. Chaudhuri, B. Goldfrey, S. Rao (2003), and K. Talwar, Path, Tree and minimum pháp tối ưu đàn kiến, mạng nơ-ron RBF, đề latency tour, Proc. FOCS, 2003, pp. 36-45 xuất một thuật toán mới kết hợp giữa [3] A. Salehipour, K. Sorensen, P. Goos, and SMMAS và tìm kiếm địa phương dùng mạng O.Braysy (2011), Efficient GRASP+VND nơ-ron RBF để 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_RBF có tìm kiếm địa phương RBF Research, Vol 9. No. 2, pp. 189-209. bước đầu cho kết quả tốt hơn hẳn so với [4] M. Silva, A. Subramanian, T. Vidal, and L. SMMAS và AMMAS_LS 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 cải tiến các thuật toán của mạng nơ-ron RBF. Problem, J. Operations Research, Vol 221, Hy vọng sẽ có những kết quả đầy hứa hẹn. No. 3, pp. 13-520. [5] https://www.iwr.uni- heidelberg.de/groups/comopt/software/TSPLIB95/ [6] T.M. Mitchell, Machine learning, McGraw- Hill, 1997. 165