Thuật toán tìm kiếm Hill climbing giải bài toán Cây Steiner nhỏ nhất

- Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông Thuật toán tìm kiếm Hill climbing giải bài toán Cây Steiner nhỏ nhất Trần Việt Chương1 , Phan Tấn Quốc2 , Hà Hải Nam3 1 Trung tâm Công nghệ thông tin và Truyền thông, Sở Thông tin và Truyền thông tỉnh Cà Mau 2 Khoa Công nghệ thông tin, Trường Đại học Sài Gòn 3 Viện Khoa học Kỹ thuật Bưu điện, Học viện Công nghệ Bưu chính Viễn thông Tác giả liên hệ: Trần Việt Chương, [email protected] Ngày nhận bài ngày sửa chữa Định danh DOI: 10.32913/mic-ict-research-vn.vyyyy.nx.xysz Tóm tắt: Cây Steiner nhỏ nhất (Steiner Minimum Tree-SMT) là bài toán tối ưu tổ hợp có nhiều ứng dụng quan trọng trong khoa học và kỹ thuật.
- Đây là bài toán thuộc lớp NP-hard.
- Trước đây đã có nhiều công trình nghiên cứu theo các hướng tiếp cận khác nhau đưa ra các thuật toán để giải bài toán SMT.
- Bài báo này đề xuất thuật toán Hill climbing search để giải bài toán Cây Steiner nhỏ nhất, trong đó đề xuất cách thức tìm kiếm lân cận tất định và cách thức kết hợp tìm kiếm lân cận tất định với tìm kiếm lân cận ngẫu nhiên để giải quyết bài toán Cây Steiner nhỏ nhất.
- Kết quả thực nghiệm với hệ thống dữ liệu thực nghiệm chuẩn cho thấy thuật toán đề xuất của chúng tôi cho lời giải với chất lượng tốt hơn so với một số thuật toán heuristic hiện biết trên một số bộ dữ liệu.
- Từ khóa: thuật toán tìm kiếm leo đồi, Cây Steiner nhỏ nhất, thuật toán heuristic, thuật toán metaheuristic, lân cận tất định, lân cận ngẫu nhiên, tối ưu cục bộ.
- Bài toán thứ hai là bài toán Cây Steiner nhỏ nhất Giả sử chúng ta cần xây dựng một hệ thống giao với khoảng cách chữ nhật [11].
- Bài toán thứ ba là thông nối một số địa điểm trong khu đô thị.
- Đây là giới hạn nghiên cứu về bài toán Cây có độ dài ngắn nhất nhằm giảm kinh phí xây dựng.
- Yêu cầu của bài toán cho phép thêm vào một số địa Mục này trình bày một số định nghĩa và khả năng điểm trung gian để giảm thiểu tổng chiều dài hệ thống ứng dụng của bài toán Cây Steiner nhỏ nhất.
- Đây là bài toán có thể vận dụng kiến thức bài toán Cây Steiner nhỏ nhất để giải.
- Một số định nghĩa Bài toán Cây Steiner nhỏ nhất hiện được nghiên cứu ở một số dạng sau: Bài toán thứ nhất là bài toán Cây Định nghĩa 1: Cây Steiner [4] 1 Tập 2020, Số 1, Tháng 6 Cho 𝐺 = (𝑉 (𝐺), 𝐸 (𝐺)) là một đơn đồ thị vô hướng Steiner của đồ thị 𝐺 sai khác với 𝑇 không quá 𝑘 cạnh.
- Ứng dụng của bài toán Cây Steiner nhỏ nhất Cho 𝑇 = (𝑉 (𝑇), 𝐸 (𝑇)) là một Cây Steiner của đồ Bài toán SMT có thể được tìm thấy trong các thị 𝐺 .
- Í truyền thông, bài toán thiết kế VLSI (Very Large Scale 𝑒 ∈𝐸 (𝑇 ) 𝑤(𝑒.
- Integrated), các bài toán liên quan đến hệ thống mạng Định nghĩa 3: Cây Steiner nhỏ nhất [4] với chi phí nhỏ nhất .
- Cho đồ thị 𝐺 được mô tả như trên, bài toán tìm Cây Đóng góp chính của chúng tôi trong bài báo này Steiner có chi phí nhỏ nhất được gọi là bài toán Cây là đã đề xuất cách thức tìm kiếm lân cận mới để giải Steiner nhỏ nhất (Steiner Minimum Tree problem - bài toán Cây Steiner nhỏ nhất đồng thời cài đặt thực SMT) hoặc được gọi ngắn gọn là bài toán Cây Steiner nghiệm thuật toán trên hệ thống dữ liệu thực nghiệm (Steiner Tree problem).
- SMT là bài toán tối ưu tổ hợp của lý thuyết đồ thị.
- KHẢO SÁT MỘT SỐ THUẬT TOÁN GIẢI minh thuộc lớp NP-hard [4, 13].
- BÀI TOÁN CÂY STEINER NHỎ NHẤT Khác với bài toán cây khung nhỏ nhất (Minimum Spanning Trees Problem.
- đó là bài toán đơn giản.
- Hiện tại, có nhiều hướng tiếp cận giải bài toán Cây Cây Steiner là cây đi qua tất cả các đỉnh thuộc tập Steiner nhỏ nhất như các thuật toán rút gọn đồ thị, terminal 𝐿 và có thể thêm một số đỉnh khác nữa thuộc các thuật toán tìm lời giải đúng, các thuật toán tìm tập 𝑉 (𝐺) chứ không nhất thiết phải đi qua tất cả các lời giải gần đúng cận tỉ lệ, các thuật toán heuristic và đỉnh của đồ thị.
- các thuật toán metaheuristic.
- Các thuật toán rút gọn đồ thị số không âm trên cạnh.
- Nếu 𝑇 0 là một Cây Steiner thuộc 1-lân cận của 𝑇 thì Ý tưởng chung của các thuật toán rút gọn đồ thị là ta nói 𝑇 và 𝑇 0 là 1-lân cận với nhau.
- Chất lượng các thuật k-lân cận dưới đây là mở rộng trực tiếp của khái niệm toán giải bài toán SMT phụ thuộc vào độ lớn của hệ 1-lân cận.
- Do vậy, mục đích của các thuật toán rút Định nghĩa 5: k-lân cận của Cây Steiner 𝑇 gọn đồ thị là làm giảm thiểu tối đa hệ số 𝑛 − |𝐿.
- Ta Các thuật toán rút gọn đồ thị cũng được xem là gọi k-lân cận của Cây Steiner 𝑇 là tập tất cả các Cây bước tiền xử lý dữ liệu quan trọng trong việc giải bài 2 Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông toán SMT.
- Ưu điểm của các thuật toán heuristic là thời gian chạy nhanh hơn nhiều so với các thuật toán meta- B.
- Các thuật toán tìm lời giải đúng heuristic.
- Các nghiên cứu tìm lời giải đúng cho bài toán SMT như thuật toán quy hoạch động của Dreyfus và Wagner [33], thuật toán dựa trên phép nới lỏng Lagrange của E.
- Các thuật toán metaheuristic Beasley [9], các thuật toán nhánh cận của Koch và Thuật toán metaheuristic sử dụng nhiều heuristic Martin [26], Xinhui Wang [15, 30.
- kết hợp với các kỹ thuật phụ trợ nhằm khai phá không Ưu điểm của hướng tiếp cận này là tìm được lời gian tìm kiếm, metaheuristic thuộc lớp các thuật toán giải chính xác, nhược điểm của hướng tiếp cận này tìm kiếm tối ưu.
- là chỉ giải được các bài toán có kích thước nhỏ.
- nên Hiện đã có nhiều công trình sử dụng thuật toán khả năng ứng dụng của chúng không cao.
- Việc giải metaheuristic giải bài toán SMT.
- lân cận node-based neighborhood [19], path-based Hướng tiếp cận này là cơ sở quan trọng có thể được neighborhood [19], thuật toán local search [7], thuật sử dụng để đánh giá chất lượng lời giải của các thuật toán tìm kiếm lân cận biến đổi [23], thuật toán di toán giải gần đúng khác khi giải bài toán SMT.
- truyền [2], thuật toán tabu search [5], thuật toán di truyền song song [14], thuật toán bees [22.
- Các thuật toán gần đúng cận tỉ lệ Từ những hướng tiếp cận trên, bài báo này đề xuất một thuật toán metaheuristic dạng cá thể.
- Cụ thể là Thuật toán gần đúng cận tỉ lệ 𝛼 nghĩa là lời giải thuật toán Hill climbing search để giải bài toán SMT.
- tìm được gần đúng một cận tỉ lệ 𝛼 so với lời giải tối Cách tiếp cận này có thể giải được các bài toán SMT ưu.
- có kích thước lớn, có chất lượng tốt hơn so với các Ưu điểm của thuật toán gần đúng cận tỉ lệ là có sự hướng tiếp cận heuristic, các thuật toán gần đúng cận đảm bảo về mặt toán học theo nghĩa cận tỉ lệ trên, tỉ lệ và có thời gian chạy nhanh hơn so với các thuật nhược điểm của thuật toán dạng này là cận tỉ lệ tìm toán metaheuristic dạng quần thể [32].
- được trong thực tế thường là kém hơn nhiều so với chất lượng lời giải tìm được bởi nhiều thuật toán gần III.
- THUẬT TOÁN HILL CLIMBING SEARCH đúng khác dựa trên thực nghiệm.
- Ý tưởng thuật toán hill climbing search Thuật toán MST-Steiner của Bang Ye Wu và Kun- Mao Chao có cận tỉ lệ 2 [4], thuật toán Zelikovsky- Thuật toán Hill climbing search là một trong những Steiner có cận tỉ lệ 11/6 [4].
- Cận tỉ lệ tốt nhất tìm kỹ thuật dùng để tìm kiếm tối ưu cục bộ cho một bài được hiện tại cho bài toán SMT là .
- Thuật toán Hill climbing search là một trong những D.
- Các thuật toán heuristic giải pháp để giải bài toán tối ưu, đặc biệt là dạng bài toán ưu tiên về thời gian tính như bài toán dạng thiết Thuật toán heuristic chỉ ra những kinh nghiệm riêng kế.
- biệt để tìm kiếm lời giải cho một bài toán tối ưu cụ thể.
- Thuật toán heuristic thường tìm được lời giải có thể chấp nhận được trong thời gian cho phép nhưng B.
- Sơ đồ tổng quát thuật toán Hill climbing không chắc đó là lời giải chính xác.
- Các thuật toán search heuristic cũng không chắc hiệu quả trên mọi loại dữ Thuật toán Hill climbing search liên tục thực hiện liệu đối với một bài toán cụ thể.
- việc di chuyển từ một lời giải 𝑆 đến một lời giải mới Các thuật toán heuristic điển hình cho bài toán SMT 𝑆 0 trong một cấu trúc lân cận xác định trước theo sơ như: SPT [21], PD Steiner [21] (bài báo này sẽ gọi tắt đồ sau: 3 Tập 2020, Số 1, Tháng 6 Bước 1: Khởi tạo.
- Chọn tập lân cận 𝑁 (𝑆) và Chúng tôi đặt tên thuật toán Hill climbing search tìm lời giải 𝑆 0 trong tập lân cận này với giá trị hàm giải bài toán SMT là HCSMT.
- Sơ đồ thuật toán HCSMT di chuyển từ 𝑆 sang 𝑆 0.
- Nếu điều kiện dừng a) Vấn đề tạo lời giải ngẫu nhiên ban đầu thỏa mãn thì kết thúc thuật toán và đưa ra lời giải tốt Cũng lưu ý rằng Cây Steiner ban đầu được khởi tạo nhất tìm được.
- Giải quyết vấn đề tối ưu hóa cục bộ Bắt đầu từ cây chỉ gồm một đỉnh nào đó của đồ thị, tiếp theo, thuật toán sẽ thực hiện 𝑛 − 1 bước lặp với 𝑛 Vấn đề lớn nhất mà thuật toán Hill climbing search là số đỉnh của đồ thị đang xét.
- ưu cục bộ, để tìm được lời giải tốt hơn nữa ta có thể thuật toán này sử dụng ý tưởng của thuật toán Prim.
- lặp lại thuật toán Hill climbing search với nhiều điểm Duyệt các đỉnh treo 𝑢 ∈ 𝑇 , nếu 𝑢 ∉ 𝐿 thì xóa cạnh xuất phát khác nhau được chọn ngẫu nhiên và lưu lại chứa đỉnh 𝑢 khỏi 𝐸 (𝑇.
- bước nhiên với những bài toán mà không gian tìm kiếm này gọi là bước xóa các cạnh dư thừa.
- Thao tác tìm chu trình trong Cây Steiner 𝑇 sau khi Để giải quyết vấn đề tối ưu cục bộ, trong bài báo chèn thêm một cạnh 𝑒 được tiến hành như sau: Khi này chúng tôi đề xuất việc kết hợp thuật toán Hill chèn cạnh 𝑒 = (𝑢, 𝑣) vào 𝑇 , duyệt Cây Steiner 𝑇 theo climbing search với chiến lược tìm kiếm lân cận ngẫu chiều sâu bắt đầu từ 𝑢 , lưu vết trên đường đi bằng nhiên để hy vọng nâng cao chất lượng lời giải của mảng 𝑝 (đỉnh trước của một đỉnh trong phép duyệt).
- thuật toán.
- THUẬT TOÁN HILL CLIMBING SEARCH vết chính là các cạnh trong chu trình cần tìm.
- GIẢI BÀI TOÁN CÂY STEINER NHỎ NHẤT Thuật toán HCSMT ngoài việc lời giải ban đầu A.
- Ý tưởng thuật toán được khởi tạo ngẫu nhiên thì các Cây Steiner lân cận tìm được trong quá trình tìm kiếm là kiểu 1-lân cận Cho đồ thị vô hướng liên thông có trọng số 𝐺 .
- Hiệu quả của thuật toán HCSMT có thể được đầu từ Cây Steiner 𝑇 của 𝐺 được khởi tạo ngẫu nhiên, cải thiện khi ta thay đổi thứ tự các cạnh được duyệt chèn lần lượt từng cạnh 𝑒 ∈ 𝐸 (𝐺.
- 𝐶 (𝑇) thì thay Thuật toán HCSMT chủ yếu sử dụng tính tăng 𝑇 bằng 𝑇 0.
- Thuật toán dừng nếu trong một lần duyệt cường, thể hiện qua các chiến lược tìm kiếm Cây 4 Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông Thuật toán 1: Thuật toán HCSMT thời điểm sau: thứ nhất là khi khởi tạo lời giải ban Đầu vào: Đồ thị 𝐺 = (𝑉 (𝐺), 𝐸 (𝐺)) đầu, thứ hai là thay đổi thứ tự duyệt của các cạnh Đầu ra : Cây Steiner có chi phí nhỏ nhất tìm trong tập cạnh ứng viên (như đã đề cập ở đoạn trên), được thứ ba khi việc tìm kiếm lân cận không cải thiện qua 1 stop = false.
- thuật toán HCSMT do chúng tôi đề xuất.
- 13 for (với mỗi cạnh 𝑒 0 ∈ Cycle) Để thực nghiệm các thuật toán liên quan, 14 if (𝐶 (𝐹 − 𝑒 0.
- 17 } dùng cho bài toán Cây Steiner tại địa chỉ URL 18 if (𝑚𝑖𝑛 < 𝐶 (𝑇.
- Thuật toán HCSMT được chúng tôi cài đặt bằng 27 while (Thỏa điều kiện đa dạng hóa){ ngôn ngữ C++ sử dụng môi trường DEV C++ 5.9.2.
- Kết quả thực nghiệm và đánh giá thuộc 𝑇 mới được thêm vào để tránh trường hợp thêm vào quá nhiều lần Kết quả thực nghiệm của các thuật toán được ghi nhưng 𝑇 không liên thông trở lại).
- nhận giá trị chi phí Cây Steiner lần lượt ứng với hai 31 } thuật toán hueristic: Heu [26], PD [21].
- Hai thuật 32 } toán metahueristic: VNS [23], TS [5] và thuật toán 33 } 34 return 𝑇𝑏𝑒𝑠𝑡 .
- 5 Tập 2020, Số 1, Tháng 6 Bảng I Bảng II KẾT QUẢ THỰC NGHIỆM THUẬT KẾT QUẢ THỰC NGHIỆM THUẬT TOÁN TRÊN NHÓM ĐỒ THỊ STEINC TOÁN TRÊN NHÓM ĐỒ THỊ STEIND HC HC Test n m Heu PD VNS TS Test n m Heu PD VNS TS SMT SMT steinc1.txt steind1.txt steinc2.txt steind2.txt steinc3.txt steind3.txt steinc4.txt steind4.txt steinc5.txt steind5.txt steinc6.txt steind6.txt steinc7.txt steind7.txt steinc8.txt steind8.txt steinc9.txt steind9.txt steinc10.txt steind10.txt steinc11.txt steind11.txt steinc12.txt steind12.txt steinc13.txt steind13.txt steinc14.txt steind14.txt steinc15.txt steind15.txt steinc16.txt steind16.txt steinc17.txt steind17.txt steinc18.txt steind18.txt steinc19.txt steind19.txt steinc20.txt steind20.txt D.
- Mục này nhằm so sánh chất lượng lời giải của thuật Tương tự, kết quả so sánh thuật toán HCSMT với toán HCSMT với hai thuật toán heuristic: Heu [26], thuật toán PD [21] trên các nhóm dữ liệu steinc, PD [21] và hai thuật toán metaheuristic: VNS [23], steind, steine cũng đã được thể hiện chi tiết ở Bảng TS [5].
- tương ứng với số Kết quả so sánh thuật toán HCSMT với thuật toán lượng bộ dữ liệu cho chất lượng lời giải tốt hơn (ghi VNS [23] trên các nhóm dữ liệu steinc, steind, steine nhận bởi ký hiệu.
- khi toán HCSMT cho chất lượng lời giải (tốt hơn, bằng, so sánh thuật toán HCSMT với các thuật toán: Heu kém hơn) thuật toán Heu .
- Thuật toán HCSMT cho chất lượng lời giải (tốt hơn, Với 20 bộ dữ liệu nhóm steinc, thuật toán HCSMT bằng, kém hơn) thuật toán PD cho chất lượng lời giải (tốt hơn, bằng, kém hơn) thuật 0,0.
- Thuật toán HCSMT cho chất lượng lời giải (tốt toán Heu .
- Kết quả so sánh hơn, bằng, kém hơn) thuật toán VNS thuật toán HCSMT với thuật toán Heu [26] trên các 28,3.
- Thuật toán HCSMT cho chất lượng lời giải nhóm dữ liệu steind, steine cũng đã được thể hiện chi (tốt hơn, bằng, kém hơn) thuật toán TS Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông Bảng III Bảng IV KẾT QUẢ THỰC NGHIỆM THUẬT SO SÁNH CHẤT LƯỢNG LỜI GIẢI CỦA THUẬT TOÁN TRÊN NHÓM ĐỒ THỊ STEINE TOÁN HCSMT VỚI THUẬT TOÁN H EU HC Nhóm đồ HCSMTHeu Test n m Heu PD VNS TS SMT thị SL % SL % SL % steine1.txt steinc steine2.txt steind steine steine3.txt Tổng cộng steine4.txt steine5.txt Bảng V steine6.txt SO SÁNH CHẤT LƯỢNG LỜI GIẢI CỦA THUẬT TOÁN HCSMT VỚI THUẬT TOÁN PD steine7.txt steine8.txt Nhóm đồ HCSMTPD steine9.txt thị SL % SL % SL % steine10.txt steinc steine11.txt steind steine12.txt steine steine13.txt Tổng cộng steine14.txt steine15.txt cũng đã được thể hiện chi tiết ở Bảng VII.
- steine16.txt VI.
- KẾT LUẬN steine17.txt steine18.txt Bài báo này đề xuất thuật toán HCSMT dạng thuật toán Hill climbing search để giải bài toán Cây Steiner steine19.txt nhỏ nhất.
- Đóng góp của chúng tôi trong bài báo này steine20.txt là đã đề xuất cách thức tìm kiếm lân cận kết hợp với tìm kiếm lân cận ngẫu nhiên nâng cao chất lượng của thuật toán.
- Chúng tôi đã thực nghiệm thuật toán đề .
- xuất trên hệ thống gồm 60 bộ dữ liệu thực nghiệm Thời gian tính trung bình của thuật toán HCSMT chuẩn.
- Kết quả thực nghiệm cho thấy rằng thuật toán trên các đồ thị ứng với nhóm dữ liệu steinc là 2,54 này cho chất lượng lời giải tốt hơn hoặc bằng hai thuật giây.
- Thời gian chạy bằng, kém hơn hai thuật toán dạng metaheuristic tốt chương trình ngoài việc phụ thuộc vào độ phức tạp hiện biết trên một số bộ dữ liệu thực nghiệm chuẩn.
- và thông thường, rithms For Discrete Optimization Problems”, doctor thời gian chạy của thuật toán heuristic nhanh hơn thuật of philosophy, Industrial And Systems Engineering, toán metaheuristic.
- toán HCSMT như trên cũng cho chúng ta thông tin [2] Ankit Anand, Shruti, Kunwar Ambarish Singh, ”An tham khảo cần thiết về thuật toán này.
- efficient approach for Steiner tree problem by genetic algorithm”, International Journal of Computer Sci- Kết quả so sánh thuật toán HCSMT với thuật toán ence and Engineering (SSRG-IJCSE), vol.2, pp.233- TS [5] trên các nhóm dữ liệu steinc, steind, steine 237, 2015.
- Akyildiz, Luigi Paura, ”On TOÁN HCSMT VỚI THUẬT TOÁN VNS the solution of the Steiner tree np-hard problem via physarum bionetwork”, IEEE, pp .
- [16] Phan Tấn Quốc, ”Rút gọn đồ thị cho bài toán Cây Tổng Steiner nhỏ nhất”, Kỷ yếu Hội nghị Quốc gia lần thứ cộng: IX về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Trường Bảng VII Đại học Cần Thơ, ngày ISBN: 978- SO SÁNH CHẤT LƯỢNG LỜI GIẢI CỦA trang .
- THUẬT TOÁN HCSMT VỚI THUẬT TOÁN TS [17] Poompat Saengudomlert, ”Optimization for Commu- nications and Networks”, Taylor and Francis Group, Nhóm đồ HCSMTTS LLC, pp .
- ”Đề xuất một số thuật toán heuristic giải bài toán [4] Bang Ye Wu, Kun-Mao Chao, ”Spanning trees and Cây Steiner nhỏ nhất”, Kỷ yếu Hội nghị Quốc gia optimization problems”, Chapman&Hall/CRC, pp.13- lần thứ X về Nghiên cứu cơ bản và ứng dụng Công 139, 2004.
- [22] Trần Việt Chương, Phan Tấn Quốc, Hà Hải Nam, [6] Chi-Yeh Chen, ”An efficient approximation algorithm ”Thuật toán Bees giải bài toán Cây Steiner nhỏ nhất for the Steiner tree problem”, National Cheng Kung trong trường hợp đồ thị thưa”.
- Nhận bằng Thạc sỹ Khoa học [28] Vũ Đình Hòa, ”Bài toán Steiner”, http://math.ac.vn.
- Lĩnh vực [31] Xiuzhen Cheng, Ding-zhu Du, ”Steiner trees in indus- try”, Kluwer Academic Publishers, vol.5, pp.193-216, nghiên cứu: Thuật toán tiến hóa 2004.
- Lĩnh vực nghiên cứu: Thuật toán gần đúng