A non-dominated genetic algorithm for constructing balanced spanning tree

Hajizadeh Tahan, Marzieh; Ghasemzadeh, Mohammad; Latif, Ali Mohammad

A non-dominated genetic algorithm for constructing balanced spanning tree

Document Type : Persian Original Article

Authors

Computer Engineering Department, Yazd University, Yazd, Iran.

Abstract

This research shows how we can find Balanced Spanning Trees, without the need to determine the relevant parameters, by using an evolutionary multi-objective algorithm. This problem belongs to the complexity class NP-complete; therefore, for big graphs, we cannot use exact algorithms, which often rely on exhaustive search. The existing approximate algorithms are all limited to obtaining the related parameter(s) and considering them separately during their computations; this usually leads to finding solution with lower quality than desired. On the other hand, the existing methods solve the problem of the balanced spanning tree as a single objective; which loss search space information and finding only one solution, while in real-world problems, decision-makers often need several solutions to make a better decision. Overcoming the above-mentioned shortcomings leads to finding a balanced spanning tree with better characteristics; which in turn, yields more benefits in relevant applications, such as communication networks and high-performance computing projects. In this research, in order to overcome the above challenge, the use of evolutionary multi-objective optimization via Non-dominated Sorting Genetic Algorithm - NSGA is recommended. The proposed solution uses two objective functions to simultaneously optimize the weight of the spanning tree and the shortest path. The first objective function attempts to minimize the distance between each vertex and the root of the tree. The second objective function is selected to minimize the weight of the obtained spanning tree. The proposed method was implemented and run in a Python environment by specialized functions, on a seven-core microcomputer. In order to evaluate the performance of the proposed algorithm, a set of random graphs by Erdos and Renyi approaches were used. The proposed algorithm was compared with the state of the art methods in the problem of finding the balanced spanning tree. Experimental results show that the proposed algorithm is often able to find better responses than the other algorithms compared. The experimental results show that the proposed algorithm was always able to find highly ranked Balanced Spanning Trees. Meanwhile, often the optimal solutions, which can only be obtained through exact and very costly algorithms, were found, with teeny computations.

Keywords

References

[1] S. M. Ejabati, "Adaptive Increasing/Decreasing PSO for Solving Dynamic Optimization Problems," Journal of Soft Computing and Information Technology, vol. 7, no. 2, pp. 58-70, 2018.

[2] A. Mohammadi, S.-H. Zahiri, and S.-M. Razavi, "Performance of Intelligent Optimization Methods in IIR System Identification Problems," Journal of Soft Computing and Information Technology, vol. 6, no. 2, pp. 25-39, 2017.

[3] R. Campos and M. Ricardo, "A fast algorithm for computing minimum routing cost spanning trees," Computer Networks, vol. 52, no. 17, pp. 3229-3247, 2008.

[4] C. Li, H. Zhang, B. Hao, and J. Li, "A survey on routing protocols for large-scale wireless sensor networks," Sensors, vol. 11, no. 4, pp. 3498-3526, 2011.

[5] R. Moharam and E. Morsy, "Geneticalgorithms to balanced tree structures in graphs," Swarm and Evolutionary Computation, vol. 32, pp. 132-139, 2017.

[6] C. A. C. Coello, G. B. Lamont, and D. A. Van Veldhuizen, Evolutionary algorithms for solving multi-objective problems. Springer, 2007.

[7] P. Ngatchou, A. Zarei, and A. El-Sharkawi, "Pareto multi objective optimization," in Proceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems, 2005, pp. 84-91: IEEE.

[8] W. Gao, M. Pourhassan, V. Roostapour, and F. Neumann, "Runtime Analysis of Evolutionary Multi-objective Algorithms Optimising the Degree and Diameter of Spanning Trees," in International Conference on Evolutionary Multi-Criterion Optimization, 2019, pp. 504-515: Springer.

[9] S. Ronoud and S. Asadi, "An evolutionary deep belief network extreme learning-based for breast cancer diagnosis," Soft Computing, vol. 23, no. 24, pp. 13139-13159, 2019.

[10] K. Deb, "A robust evolutionary framework for multi-objective optimization," in Proceedings of the 10th annual conference on Genetic and evolutionary computation, 2008, pp. 633-640.

[11] P. ERDdS and A. wi, "On random graphs I," Publ. Math. Debrecen, vol. 6, pp. 290-297, 1959.

[12] S. Khuller, B. Raghavachari, and N. Young, "Balancing minimum spanning trees and shortest-path trees," Algorithmica, vol. 14, no. 4, pp. 305-321, 1995.

[13] M. Souier, M. Dahane, and F. Maliki, "An NSGA-II-based multiobjective approach for real-time routing selection in a flexible manufacturing system under uncertainty and reliability constraints," The International Journal of Advanced Manufacturing Technology, vol. 100, no. 9-12, pp. 2813-2829, 2019.

[14] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEEtransactions on evolutionary computation, vol. 6, no. 2, pp. 182-197, 2002.

[15] K. Singh and S. Sundar, "Artifical bee colony algorithm using problem-specific neighborhood strategies for the tree t-spanner problem," Applied Soft Computing, vol. 62, pp. 110-118, 2018.

[16] S. Sundar, "A Steady-State Genetic Algorithm for the Tree t-Spanner Problem," in Soft Computing: Theories and Applications: Springer, 2019, pp. 387-398.

[17] Y. Ran, Z. Chen, S. Tang, and Z. Zhang, "Primal dual based algorithm for degree-balanced spanning tree problem," Applied Mathematics and Computation, vol. 316, pp. 167-173, 2018.

[18] M. H. Tahan and S. Asadi, "MEMOD: a novel multivariate evolutionary multi-objective discretization," Soft Computing, vol. 22, no. 1, pp. 301-323, 2018.

[19] M. H. Tahan and S. Asadi, "EMDID: Evolutionary multi-objective discretization for imbalanced datasets," Information Sciences, vol. 432, pp. 442-461, 2018.

[20] K. Bharath-Kumar and J. Jaffe, "Routing to multiple destinations in computer networks," IEEE Transactions on communications, vol. 31, no. 3, pp. 343-351, 1983.

[21] J. Cong, A. Kahng, G. Robins, M. Sarrafzadeh, and C. Wong, "Performance-driven global routing for cell based ics," in [1991 Proceedings] IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1991, pp. 170-173: IEEE.

[22] J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C.-K. Wong, "Provably good performance-driven global routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 11, no. 6, pp. 739-752, 1992.

[23] B. Awerbuch, A. Baratz, and D. Peleg, "Cost-sensitive analysis of communication protocols," Massachusetts Inst of Tech Cambridg Lab for Computer Science,1991.

[24] A. Avokh and G. Mirjalily, "Dynamicbalanced spanning tree (DBST) for data aggregation in wireless sensor networks," in 2010 5th international symposium on telecommunications, 2010, pp. 391-396: IEEE.

[25] R. Moharam, E. Morsy, and I. A. Ismail, "Genetic algorithms for balanced spanning tree problem," in 2015 Federated Conference on Computer Science and Information Systems (FedCSIS), 2015, pp. 537-545: IEEE.

[26] C. J. Alpert et al., "Prim-Dijkstra Revisited: Achieving Superior Timing-driven Routing Trees," in Proceedings of the 2018 International Symposium on Physical Design, 2018, pp. 10-17: ACM.

[27] L. Davis, D. Orvosh, A. Cox, and Y. Qiu, "A genetic algorithm for survivable network design," in Proceedings of the 5th International Conference on Genetic Algorithms, 1993, pp. 408-415: Morgan Kaufmann Publishers Inc.

[28] P. Piggott and F. Suraweera, "Encoding graphs for genetic algorithms: An investigation using the minimum spanning tree problem," in Progress in Evolutionary Computation: Springer, 1993, pp. 305-314.

[29] R. Mathur, I. Khan, and V. Choudhary, "Genetic algorithm for dynamic capacitated minimum spanning tree," International Journal of Computer Technology and Applications, vol. 4, no. 3, p. 404, 2013.

[30] Q. P. Tan, "A genetic approach for solving minimum routing cost spanning tree problem," International Journal of Machine Learning and Computing, vol. 2, no. 4, p. 410, 2012.

[31] S. Balaji, V. Swaminathan, and K. Kannan, "Approximating maximum weighted independent set using vertex Support," International Journal of Computational and Mathemtical Sciences1, vol. 3, no. 8, pp. 406-411, 2009.

[32] A. Cayley, "A theorem on trees," The Quarterly Journal of Mathematics, vol. 23, pp. 376-378, 1889.

[33] D. B. Johnson, "Finding all the elementary circuits of a directed graph," SIAMJournal on Computing, vol. 4, no. 1, pp. 77-84, 1975.