Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặn

Bài viết đề xuất giải thuật tối ưu hóa đàn kiến song song tìm cây khung nhỏ nhất có bậc bị chặn trên đồ thị có số đỉnh tương đối lớn.
Nội dung trích xuất từ tài liệu:
Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặnJOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1075.2015-0052Educational Sci., 2015, Vol. 60, No. 7A, pp. 53-60This paper is available online at http://stdb.hnue.edu.vn GIẢI THUẬT KIẾN SONG SONG GIẢI BÀI TOÁN CÂY KHUNG NHỎ NHẤT CÓ BẬC BỊ CHẶN Bùi Thị Thủy, Phạm Thị Lan Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội Tóm tắt. Cho một đồ thị G = (V, E) liên thông, có trọng số và một số nguyên dương d. Cây khung có bậc bị chặn của G là một cây khung trong đó các đỉnh của nó đều có bậc nhỏ hơn d. Bài toán tìm cây khung nhỏ nhất có bậc bị chặn của một đồ thị cho trước đã được chứng minh là bài toán NP - khó. Trong bài báo này, chúng tôi đề xuất giải thuật tối ưu hóa đàn kiến song song tìm cây khung nhỏ nhất có bậc bị chặn trên đồ thị có số đỉnh tương đối lớn. Từ khóa: Giải thuật kiến, cây khung tối ưu có bậc bị chặn, chiến lược song song, bài toán Np - khó, thuật toán song song.1. Mở đầu Bài toán cây khung nhỏ nhất có bậc bị chặn (Degree – Constrained Minimum SpanningTree (DCMST)) được nghiên cứu lần đầu tiên bởi 2 tác giả Deo và Hakimi [2]. Bài toán được phátbiểu như sau: Input: Cho trước một đồ thị G = (V, E) với |V | = n, các cạnh được gán trọng số và mộtsố nguyên dương d. Question: Có tồn tại hay không một cây khung nhỏ nhất T của G thỏa mãn điều kiện mọiđỉnh của T đều có bậc không vượt quá d. Có thể phát biểu lại bài toán dưới dạng tối ưu như sau: Cho đồ thị G = (V, E) có n đỉnh, m cạnh và cij > 0 là trọng số của mỗi cạnh eij . Giả sử ( cij , eij ∈ E Xij = (1.1) 0, eij 6∈ EVới một số d nguyên dương, hãy xác định giá trị nhỏ nhất của biểu thức sau: X WT = cij Xij (1.2) i,j∈V,i6=jNgày nhận bài: 20/7/2015. Ngày nhận đăng: 20/11/2015.Liên hệ: Bùi Thị Thủy, e-mail: btthuy@hnue.edu.vn 53 Bùi Thị Thủy, Phạm Thị LanTrong đó X Xij ≤ d với i ∈ V (1.3) j∈V,i6=j X Xij ≥ 1 với i ∈ V (1.4) j∈V,i6=j X Xij ≤ |N | − 1 với ∀N ⊆ V (1.5) i6=j Bài toán này có rất nhiều ứng dụng trong đời sống. Một số ứng dụng quan trọng của nóđược kể đến như thiết kế tối ưu các mạng máy tính, viễn thông, thiết kế các mạch tích hợp, cácmạng năng lượng, mạng lưới giao thông, thiết kế các hệ thống thủy lợi [3, 10]. Xác định cây khung nhỏ nhất có bậc bị chặn được chứng minh là bài toán NP-khó [2, 13].Đã có nhiều giải thuật metaheuristic được giới thiệu để giải bài toán này như giải thuật tiến hóa[9], giải thuật di truyền [1], giải thuật đàn kiến [11, 12, 13]. . . Tuy giải thuật đàn kiến đã được sửdụng để giải quyết bài toán DCMST nhưng mới chỉ dừng lại ở thuật toán tuần tự, chưa có thuậttoán song song. Trong bài báo này, chúng tôi sử dụng giải thuật tối ưu hóa đàn kiến để giải quyếtbài toán theo hướng song song hóa với các mô hình song song khác nhau nhằm tối ưu hóa kết quảvà tăng tốc trong tính toán. Để chứng tỏ hiệu quả của các thuật toán song song so với tuần tự, chúng tôi đã cài đặt thựcnghiệm. Kết quả nhận được cho thấy mô hình song song hiệu quả hơn mô hình tuần tự.2. Nội dung nghiên cứu2.1. Giải thuật tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) Trong khoa học máy tính, giải thuật tối ưu hóa đàn kiến (Ant Colony Optimization – ACO)là một mô hình cho việc thiết kế các giải thuật tìm kiếm siêu kinh nghiệm (metaheuristic) để giảiquyết các bài toán tối ưu tổ hợp có thể quy về việc tìm kiếm đường đi tốt nhất trên đồ thị. Giảithuật này là một thành viên của họ các giải thuật đàn kiến trong các phương pháp tri thức bầy đàn(swarm intelligence). Phương pháp này là một hướng tiếp cận khá mới mẻ để giải quyết các bàitoán dựa trên các hành xử xã hội của các loài vật, trong đó có loài kiến. ...