A nonrevisiting genetic algorithm based on multi-region guided search strategy

Abstract

Abstract Recently, nonrevisiting genetic algorithms have demonstrated superior capabilities compared with classic genetic algorithms and other single-objective evolutionary algorithms. However, the search efficiency of nonrevisiting genetic algorithms is currently low for some complex optimisation problems. This study proposes a nonrevisiting genetic algorithm with a multi-region guided search to improve the search efficiency. The search history is stored in a binary space partition (BSP) tree, where each searched solution is assigned to a leaf node and corresponds to a search region in the search space. To fully exploit the search history, several optimal solutions in the BSP tree are archived to represent the most potential search regions and estimate the fitness landscape in the search space. Except for the conventional genetic operations, the offspring can also be generated through multi-region guided search strategy, where the current solution is first navigated to one of the candidate search regions and is further updated towards the direction of the optimal solution in the search history to speedup convergence. Thus, multi-region guided search can reduce the possibility of getting trapped in local optima when solving problems with complex landscapes. The experimental results on different types of test suites reveal the competitiveness of the proposed algorithm in comparison with several state-of-the-art methods.

Keywords

• Genetic algorithm
• Binary space partition tree
• Search history
• Nonrevisiting
• Multi-region guided search