A LIGHTWEIGHT BENCHMARK OF SWARM INTELLIGENCE ALGORITHMS FOR GRAPH-BASED OPTIMIZATION

Abstract

The Minimum Spanning Tree (MST) is a fundamental problem in graph optimization widely applied in networking and routing systems. However, modern network environments often experience dynamic structural changes, making traditional deterministic algorithms less flexible for adaptive scenarios. This study addresses the limited comparative evaluation of swarm intelligence algorithms for solving the MST problem using consistent datasets and performance metrics. The objective of this research is to compare the performance of three swarm intelligence algorithms Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), and Artificial Bee Colony (ABC) in generating MST solutions. Kruskal’s algorithm is used as an exact baseline for measuring solution accuracy and computational efficiency. The experiments were conducted on four graph configurations with different node sizes and change frequencies. Performance evaluation focuses on two indicators: optimality gap and computational time. The results show that Kruskal consistently produces the optimal MST with the shortest runtime. Among the swarm-based methods, PSO achieves the smallest optimality gap and the fastest computation time, followed by ACO and ABC. As graph size increases, all swarm algorithms show higher deviation from the optimal solution and longer execution times. These findings indicate that swarm intelligence methods can generate acceptable MST approximations, although deterministic algorithms remain superior for static graph conditions.