Based on modified ant colony algorithm for researching the minimum weight spanning tree

Abstract

A Minimum Weight Spanning Tree (MWST) is a mathematical technique for connecting a set of points with the least amount of connecting lines. The MWST problem is among the most fundamental and intensely studied problems in network optimization, with a wide range of theoretical and practical applications. A common and well-known problem in combinatorial optimization is the MWST problem. The MWST visits all vertices in the same related portion as the starting node. In this study, several strategies are considered to solve the generalized MWST problem, and a novel approach is used to solve the MWST. MWST can be obtained using the well-known Prim and Kruskal algorithms. These algorithms can be divided into two groups according to the implementation. MWST is divided into two types: line-based MWST and node-based MWST. Prim's algorithm is node-based, whereas Kruskal's is a line-based algorithm. However, in this paper, we present a method for solving the MWST problem using a Modified Ant Colony Optimization (MACO) algorithm. Ant Colony Optimization (ACO) is a probabilistic method and a type of metaheuristic that has gained widespread use for solving combinatorial optimization problems, as well as a technique for determining the shortest path between two points. It is based on how ants behave as they travel from their nest (colony) to a food source in search of food. The algorithm has been improved in this unique way by modifying the ACO algorithm and including the transition rule and pheromone update rule. A comparable result can be obtained by applying Prim's and Kruskal's algorithms.