![](/image/LogoVKU.png)
Please use this identifier to cite or link to this item:
https://elib.vku.udn.vn/handle/123456789/3823
Title: | A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks |
Other Titles: | Nghiên cứu phát triển thuật toán metaheuristic giải bài toán cây Steiner nhỏ nhất định hướng ứng dụng trong mạng truyền thông |
Authors: | Dang, Dai Tho Le, Tang Phu Quy Ho, Sy Bao Nhan Hoang, Tan Phu Quoc |
Keywords: | Steiner tree problem Metaheuristic algorithm Genetic algorithm Hybrid genetic algorithm Wireless sensor networks |
Issue Date: | Jun-2024 |
Publisher: | Vietnam-Korea University of Information and Communication Technology |
Series/Report no.: | NCKHSV; |
Abstract: | The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization because of its theories and applications. It is one of th foundations to develop Wireless Sensor Networks (WSNs), such as multicast and topology design. SPG is an NP-Hard problem, and many heuristic and approximation algorithms have been proposed. Thus, this study proposes a Hybrid Genetic algorithm (HGA) to solve SPG. This study is the binary string representation for a set of chosen edges. To increase the diversity of the population and avoid falling into local optimization, we use a 2-longest Distance strategy, dynamic crossover rate, and chosen solutions must differ by at least 5%. The experiment results show that the HGA algorithm's running time equals 153,83% of the GA algorithm's, the deviation found by HGA, and the optimal distance only equals 65% that of GA. A graph visualization software for SPG toward optimizations for WSNs is developed. |
Description: | Kỷ yếu Nghiên cứu khoa học của sinh viên Trường Đại học Công nghệ Thông tin và Truyền thông Việt - Hàn năm học 2023-2024; trang 2-9. |
URI: | https://elib.vku.udn.vn/handle/123456789/3823 |
Appears in Collections: | SV NCKH Năm học 2023-2024 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.