A hybrid genetic algorithm for the steiner tree problem in graphs towards optimizations for wireless sensor networks
Tóm tắt: 49
| 
PDF: 19 
##plugins.themes.academic_pro.article.main##
Author
Từ khóa:
Steiner tree problem
Genetic algorithm
Hybrid genetic algorithm
Node placement optimization in wireless sensor networks
Tóm tắt
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.
Tài liệu tham khảo
-
[1] M. Rehfeldt, “Faster algorithms for Steiner tree and related problems: From theory to practice”, Technische Universität Berlin, 2021.
[2] Gong, L. Fu, X. Fu, L. Zhao, K. Wang, and X. Wang, “Distributed Multicast Tree Construction in Wireless Sensor Networks”, IEEE Trans. Inf. Theory, vol. 63, no. 1, pp. 280–296, Jan. 2017, doi: 10.1109/TIT.2016.2623317.
[3] Y. Wu and K.-M. Chao, Spanning Trees and Optimization Problems. Chapman and Hall/CRC, 2004.
[4] N. Gilbert and H. O. Pollak, “Steiner Minimal Trees”, SIAM J. Appl. Math., vol. 16, no. 1, pp. 1–29, Jan. 1968, doi: 10.1137/0116001.
[5] Gröpl, S. Hougardy, T. Nierhoff, and H. J. Prömel, “Approximation Algorithms for the Steiner Tree Problem in Graphs”, Combinatorial Optimization, vol. 11, pp. 235–279, 2001, doi: 10.1007/978-1-4613-0255-1_7.
[6] Z. Zelikovsky, “An 11/6-approximation algorithm for the network steiner problem”, Algorithmica, vol. 9, no. 5, pp. 463–470, May 1993, doi: 10.1007/BF01187035.
[7] Karpinski and A. Zelikovsky, “New Approximation Algorithms for the Steiner Tree Problems”, J. Comb. Optim., vol. 1997, pp. 47–65, 1997, doi: https://doi.org/10.1023/A:1009758919736.
[8] Bahiense, F. Barahona, and O. Porto, “Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation”, J. Comb. Optim., vol. 103, no. 3, pp. 239–248, 2003, doi: 10.1023/A.
[9] -Y. Chen, “An Efficient Approximation Algorithm for the Steiner Tree Problem”, in Proceedings of the 2019 2nd International Conference on Information Science and Systems, 2019, pp. 179–184, doi: 10.1145/3322645.3322649.
[10] Kapsalis, V. J. Rayward-Smith, and G. D. Smith, “Solving the Graphical Steiner Tree Problem Using Genetic Algorithms”, J. Oper. Res. Soc., vol. 44, no. 4, p. 397, Apr. 1993, doi: 10.2307/2584417.
[11] Hesser, R. Männer, and O. Stucky, “On steiner trees and genetic algorithms”, Lecture Notes in Computer Science, vol. 565, pp. 509–525. 1991; doi: 10.1007/3-540-55027-5_30.
[12] V. Huy and N. D. Nghia, “Solving graphical Steiner tree problem using parallel genetic algorithm”, in 2008 IEEE International Conference on Research, Innovation and Vision for the Future in Computing and Communication Technologies, 2008, pp. 29–35, doi: 10.1109/RIVF.2008.4586329.
[13] Chen, W. Hou, and Y. Dong, “The Minimum Steiner Tree Problem Based on Genetic Algorithm”, DEStech Trans. Comput. Sci. Eng., 2018, doi: 10.12783/dtcse/mso2018/20491.
[14] Zhang, S. Yang, M. Liu, J. Liu, and L. Jiang, “A New Crossover Mechanism for Genetic Algorithms for Steiner Tree Optimization”, IEEE Trans. Cybern., vol. 52, no. 5, pp. 3147–3158, 2022, doi: 10.1109/TCYB.2020.3005047.
[15] Esbensen, “Computing near‐optimal solutions to the steiner problem in a graph using a genetic algorithm”, Networks, vol. 26, no. 4, pp. 173–185, 1995, doi: 10.1002/net.3230260403.
[16] B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proc. Am. Math. Soc., vol. 7, no. 1, p. 48, 1956, doi: 10.2307/2033241.
[17] E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, J. ACM, vol. 22, no. 2, pp. 215–225, 1975, doi: 10.1145/321879.321884.
[18] Chun-Wei and C. Ming-Chao, Handbook of Metaheuristic Algorithms. Elsevier, 2023.
[19] Leardi, “Genetic Algorithms”, in Comprehensive Chemometrics, Elsevier, 2009, pp. 631–653.
[20] Črepinšek, S.-H. Liu, and M. Mernik, “Exploration and exploitation in evolutionary algorithms”, ACM Comput. Surv., vol. 45, no. 3, pp. 1–33, 2013, doi: 10.1145/2480741.2480752.
[21] T. Dang, H. B. Truong, and N. T. Nguyen, “Hybrid Genetic Algorithms to Determine 2-Optimality Consensus for a Collective of Ordered Partitions”, in ecture Notes in Computer Science, vol 14162. Springer, Cham., 2023, pp. 3–15.
[22] T. Dang, N. T. Nguyen, and D. Hwang, “Hybrid genetic algorithms for the determination of DNA motifs to satisfy postulate 2-Optimality”, Appl. Intell., vol. 53, no. 8, pp. 8644–8653, 2023, doi: 10.1007/s10489-022-03491-7.
[23] N. T. Hanh, H. T. T. Binh, V. Q. Truong, N. P. Tan, and H. C. Phap, "Node placement optimization under Q-Coverage and Q-Connectivityconstraints in wireless sensor networks”, Journal of Network and Computer Applications, vol. 212, 2023, doi: 10.1016/j.jnca.2022.1035.
Xem thêm
##plugins.themes.academic_pro.article.sidebar##
Đã Xuất bản
Jun 30, 2024
Download
Cách trích dẫn
Le, T. P. Q., B. N. H. Sy, T. P. Q. Hoang, C. P. Huynh, và D. T. Dang. “A Hybrid Genetic Algorithm for the Steiner Tree Problem in Graphs towards Optimizations for Wireless Sensor Networks”. Tạp Chí Khoa học Và Công nghệ - Đại học Đà Nẵng, vol 22, số p.h 6B, Tháng Sáu 2024, tr 14-18, doi:10.31130/ud-jst.2024.195ICT.
