Một thuật toán di truyền lai cho bài toán cây Steiner trong đồ thị hướng tới tối ưu hóa cho mạng cảm biến không dây=A hybrid genetic algorithm for the steiner tree problem in graphs towards optimizations for wireless sensor networks

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Nhan Ho Sy Bao, Phap Huynh Cong, Dai Tho Dang, Phu Quoc Hoang Tan, Phu Quy Le Tang

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ - Đại học Đà Nẵng, 2024

Mô tả vật lý: tr.14-18

Bộ sưu tập: Metadata

ID: 477850

Thêm vào giỏ

Bài toán cây Steiner trong đồ thị (SPG) là một trong những bài toán được nghiên cứu nhiều nhất trong tối ưu hóa tổ hợp vì các lý thuyết và ứng dụng của nó. Đây là một trong những nền tảng để phát triển Mạng cảm biến không dây (WSN), chẳng hạn như thiết kế đa hướng và cấu trúc mạng. SPG là một bài toán NP-Hard và nhiều thuật toán tìm kiếm và xấp xỉ đã được đề xuất. Do đó, nghiên cứu này đề xuất một thuật toán di truyền lai (HGA) để giải SPG. Nghiên cứu này là biểu diễn chuỗi nhị phân cho một tập các cạnh đã chọn. Để tăng tính đa dạng của quần thể và tránh rơi vào tối ưu hóa cục bộ, chúng tôi sử dụng chiến lược Khoảng cách dài nhất thứ 2, tỷ lệ giao thoa động và các giải pháp được chọn phải khác nhau ít nhất 5%. Kết quả thực nghiệm cho thấy thời gian chạy của thuật toán HGA bằng 153,83% so với thuật toán GA, độ lệch do HGA tìm thấy và khoảng cách tối ưu chỉ bằng 65% khoảng cách của GA.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 the foundations to develop a Wireless Sensor Network (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.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR