A non-dominated genetic algorithm for constructing balanced spanning tree

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.