Pareto Tree Searching Genetic Algorithm: Approaching Pareto Optimal Front by Searching Pareto Optimal Tree


A new multi-objective evolutionary algorithm, Pareto Tree Searching GA (PTSGA), is introduced in this paper. The algorithm is based on a recursive binary division of the objective space, which is represented by a hyper binary tree (Pareto Tree) structure. Only non-dominated population is kept in the tree, and Pareto comparison is carried out directly on the binary location codes of tree nodes, with comparison granularity ranging from the coarsest of the root level to the finest of the leaf level; thus the algorithm is efficient. On the other hand, population diversity is achieved readily because the tree depth will become deeper, and correspondingly the comparison precision finer, only in the later stage of the evolution. Finally, tree size (non-dominated population size) reducing, niching and fitness assigning are all performed based on the resident count of sub-trees; this ensures a good distribution and spread of the resulting non-dominated front. Preliminary experimental comparisons indicate that the new algorithm is the best or close to the best among all the successful MOEAs today.