A hierarchical knowledge guided backtracking search algorithm with self-learning strategy. (June 2021)

• Record Type: Journal Article
• Authors: Zhao, Fuqing; Zhao, Jinlong; Wang, Ling; Cao, Jie; Tang, Jianxin
• Is Part Of: Engineering applications of artificial intelligence. Volume 102(2021)
• Publication Date: 2021-06
• Subjects: Backtracking search algorithm -- Hierarchical knowledge -- Multi-strategy mutation -- Probability vector -- Self-learning strategy; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2021.104268
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: To improve the performance of the backtracking search optimization algorithm (BSA), a multi-population cooperative evolution strategy guided BSA with hierarchical knowledge (HKBSA) is proposed in this paper. According to the domain knowledge of the candidates in objective space, the population is divided into the dominant population, the ordinary population and the inferior population. The information between the sub-populations has interacted with the evolution processes of the three sub-populations. The individuals in the dominant population are maintained as the optimal solutions and are utilized to guide the evolution of the other two sub-populations. A multi-strategy mutation mechanism is applied to solve non-separable problems. The distribution vector of inferior individuals is constructed by sampling, and a mechanism of the individual generation with feedback is proposed by combining self-learning strategy and elite learning strategy. The convergence of HKBSA is analyzed with the Markov model. Compared with the state-of-the-art BSA variants, HKBSA outperforms other algorithms in terms of the speed of convergence, solution accuracy and stability. Highlights: A Hierarchical Knowledge Guided Backtracking Search Algorithm (HKBSA) is proposed. The population of HKBSA is divided into the dominant, ordinary and inferior population. A multi-strategy mutation mechanism is applied to solve non-separable problems. The self-learning and elite learning strategy are introduced to individual generation. The convergence of HKBSA is analyzed with the Markov model.