A Multi-Objective Evolutionary Algorithm Based on Minimum Spanning Tree

Fitness assignment and external population maintenance are the two critical parts of multi-objective evolutionary algorithms (MOEA). They affect the two basic objectives (convergence and distribution) of MOEA design to a great extent. It is difficult for many existing MOEAs to obtain satisfying results. In this paper, a multi-objective evolutionary algorithm based on minimum spanning tree (MST_MOEA) is proposed. In the algorithm, a density estimation metric, tree crowding density, is defined. And on the basis of Pareto dominance relationship, the algorithm assigns fitness using two factors, the distance between the current individual and non-dominated solutions set and the tree crowding density of different rank individual. Moreover, if the size of non-dominated solutions set exceeds that of population, the degree information of solution combined with tree crowding density is employed to truncate population. Particularly, the solutions which have higher degree will be eliminated, for the degree in minimum spanning tree represents not only the density of solution, but the situation in population to a certain extent. Finally, the proposed algorithm is applied to nine test functions on different dimensions and has an extensively comparative study with NSGA-II and SPEA2. Experimental results demonstrate that the proposed algorithm indicates good performance in convergence and distribution.