Genetic Algorithms for the Balanced Spanning Tree Problem
This technical research work investigates the Balanced Spanning Tree Problem, an optimisation problem that seeks to construct a spanning tree capable of balancing two competing network objectives: the low overall cost associated with a Minimum Spanning Tree and the short source-to-destination distances provided by a Shortest Path Tree. For an undirected, weighted and connected graph with a designated root vertex, a balanced spanning tree is defined using two parameters, α and β. The first limits the distance between the root and each vertex relative to the corresponding shortest path in the original graph, while the second limits the total tree weight relative to the Minimum Spanning Tree. Finding an optimal balanced spanning tree is computationally challenging because determining whether a graph contains an (α, β)-balanced spanning tree is an NP-complete problem. The research therefore proposes genetic algorithms as heuristic optimisation techniques for two variants of the problem: minimising β while α is fixed, and minimising α while β is fixed. The proposed genetic algorithm represents individual spanning trees as chromosomes composed of graph edges. An initial population of valid spanning trees is generated before evolutionary operations are repeatedly applied. The approach incorporates chromosome selection, crossover, mutation, fitness evaluation and stopping criteria. Four selection strategies are examined: Random Selection, Roulette Wheel Selection, Stochastic Universal Sampling and Tournament Selection. The fitness function is based on the relationship between the Minimum Spanning Tree weight and the total weight of the candidate chromosome. Experimental evaluation is performed using randomly generated weighted graphs containing 6, 10, 15 and 20 vertices. The experiments investigate different values of the balancing parameters, selection mechanisms and population sizes. The implementation uses a population size of 30, a maximum of 300 generations, crossover probability of 0.9 and mutation probability of 0.01 in the principal experiments. The reported results show that the genetic approach can generate high-quality balanced spanning trees and, for the tested instances, produced solutions matching the corresponding optimal balanced spanning trees. The study also examines how balancing parameters and population size influence execution time and convergence, demonstrating the practical use of evolutionary computation for complex graph-optimisation problems.
Read Model Answer →