New Genetic Algorithms For Minimum Spanning Tree

Combinatorial optimization is the important branch in the field of optimization. The problem of minimum spanning tree (MST) is a classical combinatorial optimization problem. It has wide applications in the real world, such as communication networks, circuit design, pipeline lying and so on. So, it's of practical significance for us to study the solution algorithms. In recent years, Genetic algorithms have been widely used to solve the minimum spanning tree problem.The main work is summarized as follows:The MST is studied, and a novel Genetic algorithm for the minimum spanning tree problem is proposed. Based on the characteristics of the tree, a simplified encoding scheme is presented, and an efficient decoding scheme is designed. Then based on this encoding scheme, the efficient crossover and mutation operators are proposed. It can always generate valid tour, enhance the ability of exploration and improve the diversity of the population effectively. Finally, the simulation results show the effectiveness of the proposed algorithm.Another Genetic algorithm for the minimum spanning tree problem is presented. In this algorithm, the idea of cycle-breaking method and a specific encoding scheme are use to design a new algorithm for producing feasible initial population. In order to enhance the ability of exploration and convergence speed, the uniform crossover and uniform mutation operators are participate in the evolution. The numerical experiments demonstrate the efficiency of the algorithm.