A new genetic algorithm for the optimal communication spanning tree problem

This paper proposes a new genetic algorithm to solve the Optimal Communication Spanning Tree problem. The proposed algorithm works on a tree chromosome without intermediate encoding and decoding, and uses crossovers and mutations which manipulate directly trees, while a traditional genetic algorithm generally works on linear chromosomes. Usually, an initial population is constructed by the standard uniform sampling procedure. But, our algorithm employs a simple heuristic based on Prim's algorithm to randomly generate an initial population. Experimental results on known data sets show that our genetic algorithm is simple and efficient to get an optimal or near-optimal solution to the OCST problem.