A Comparative Study of Metaheuristics Solutions to Weighted Minimum Spanning Tree Problem

This paper presents a comparative sturdy of different metaheuristic solutions for Minimum Spanning Tree (MST) problem, which is an undirected graph connecting all vertices without any encirclement while ensuring minimum cost. Smell Agent Optimization (SAO) which is a new metaheuristic algorithm is used and compared with Particle Swarm Optimization (PSO) and Smell Detection Agent (SDA) algorithm. An undirected graph containing thirty nodes was used to formulate a three-scenario based MST network. The three algorithms were applied independently to each scenario and results were compared. Results showed that, the SAO and PSO obtained the same cost in the first scenario and 3.03% improvement over SDA. In the second scenario, the SAO obtained a better cost with 15.97% and 20.67% improvement over PSO and SDA respectively. In the third scenario, the SAO obtained a better cost with 8.94% and 14.14% improvement over PSO and SDA respectively. Convergence analysis also showed that the SAO converges faster by requiring a smaller number of iterations to obtain its optimum solution. These results showed the competitive behaviors of SAO against established algorithms.