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.

保存先:

書誌詳細
主要な著者:	Le, Tang Phu Quy, Ho, Sy Bao Nhan, Hoang, Tan Phu Quoc
その他の著者:	Dang, Dai Tho
フォーマット:	Bài viết
言語:	English
出版事項:	Vietnam-Korea University of Information and Communication Technology 2024
主題:	Steiner tree problem Metaheuristic algorithm Genetic algorithm Hybrid genetic algorithm Wireless sensor networks
オンライン･アクセス:	https://elib.vku.udn.vn/handle/123456789/3823
タグ:	タグ追加タグなし, このレコードへの初めてのタグを付けませんか!

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

A Metaheuristic Algorithm for the Steiner Tree Problem in Graphs toward Optimizations for Wireless Sensor Networks

類似資料