A Genetic Algorithm for Minimum Spanning Tree

In this paper a novel approach for minimum spanning tree based on genetic algorithm is proposed. In this method, new representation of chromosome and more suitable fitness function have been defined. At first, a vector in length of complete graph edges as initial chromosome is created. For presence or absence of an edge, the corresponding value in chromosome is set to 1 or 0, respectively. Fitness function is defined based on graph weights and number of connected components. Fitness should be low as possible in each iteration. Results of experiments shows proposed method can converge with large number of nodes.

Keywords:

Genetic Algorithm , Minimum Spanning Tree , Graph.