A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks
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.
Na minha lista:
| Principais autores: | , , |
|---|---|
| Outros Autores: | |
| Formato: | Bài viết |
| Idioma: | English |
| Publicado em: |
Vietnam-Korea University of Information and Communication Technology
2024
|
| Assuntos: | |
| Acesso em linha: | https://elib.vku.udn.vn/handle/123456789/3823 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| Thư viện lưu trữ: | Trường Đại học Công nghệ Thông tin và Truyền thông Việt Hàn - Đại học Đà Nẵng |
|---|
| id |
oai:elib.vku.udn.vn:123456789-3823 |
|---|---|
| record_format |
dspace |
| spelling |
oai:elib.vku.udn.vn:123456789-38232024-06-17T03:46:16Z A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks 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 Le, Tang Phu Quy Ho, Sy Bao Nhan Hoang, Tan Phu Quoc Dang, Dai Tho Steiner tree problem Metaheuristic algorithm Genetic algorithm Hybrid genetic algorithm Wireless sensor networks 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. 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. 2024-06-17T03:46:10Z 2024-06-17T03:46:10Z 2024-06 Working Paper https://elib.vku.udn.vn/handle/123456789/3823 en NCKHSV; application/pdf Vietnam-Korea University of Information and Communication Technology |
| institution |
Trường Đại học Công nghệ Thông tin và Truyền thông Việt Hàn - Đại học Đà Nẵng |
| collection |
DSpace |
| language |
English |
| topic |
Steiner tree problem Metaheuristic algorithm Genetic algorithm Hybrid genetic algorithm Wireless sensor networks |
| spellingShingle |
Steiner tree problem Metaheuristic algorithm Genetic algorithm Hybrid genetic algorithm Wireless sensor networks Le, Tang Phu Quy Ho, Sy Bao Nhan Hoang, Tan Phu Quoc A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks |
| 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. |
| author2 |
Dang, Dai Tho |
| author_facet |
Dang, Dai Tho Le, Tang Phu Quy Ho, Sy Bao Nhan Hoang, Tan Phu Quoc |
| format |
Working Paper |
| author |
Le, Tang Phu Quy Ho, Sy Bao Nhan Hoang, Tan Phu Quoc |
| author_sort |
Le, Tang Phu Quy |
| title |
A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks |
| title_short |
A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks |
| title_full |
A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks |
| title_fullStr |
A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks |
| title_full_unstemmed |
A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks |
| title_sort |
metaheuristic algorithm for the steiner tree problem in graphs toward optimizations for wireless sensor networks |
| publisher |
Vietnam-Korea University of Information and Communication Technology |
| publishDate |
2024 |
| url |
https://elib.vku.udn.vn/handle/123456789/3823 |
| _version_ |
1849203258648690688 |