A non-revisiting genetic algorithm based on a novel binary space partition tree

Abstract

Abstract As one of the most popular evolutionary algorithms for solving complex optimization problems, genetic algorithm has been extensively studied in the last three decades. Since genetic algorithm is a stochastic algorithm that may revisit duplicated solutions, it could suffer from low convergence speed on some real-world problems making algorithms likely to get trapped into local optimums. To address this issue, this paper proposes a non-revisiting genetic algorithm with a novel binary space partition (BSP) tree. The proposed BSP tree records all the generated solutions, which enables the algorithm to quickly determine whether a newly generated solution is duplicated or not. Moreover, the proposed algorithm fine-tunes the solutions according to the topology of the BSP tree in each generation, and thus can improve the population diversity and convergence speed. In comparison to six representative evolutionary algorithms, the proposed non-revisiting genetic algorithm exhibits better overall performance on eight benchmark problems, the power system fault diagnosis problem, and the molecular signatures selection problem.