An Spanning Tree based method for pruning non-dominated solutions in multi-objective optimization problems

Diversity maintenance of solutions is a crucial part in multi-objective optimization. However, most of existing studies show a good distribution with a large computational load or a comparative bad distribution quickly. In this paper, a method for pruning a set of non-dominated solutions using a Spanning Tree is proposed. This approach defines a density estimation metric — Spanning Tree Crowding Distance (STCD). Moreover, information of degree of solution combined with STCD is employed to truncate the population. From an extensive comparative study with three other methods on a number of 2, 3 and 4 objective test problems, the proposed method indicates a good balance among uniformity, spread and execution time.