Entropy-Based Substructural Local Search for the Bayesian Optimization Algorithm

摘要

A customary paradigm of designing a competent optimization algorithm is to combine an effective global searcher with an efficient local searcher. This paper presents and analyzes an entropy-based substructural local search method (eSLS) for the Bayesian Optimization Algorithm (BOA). The local searcher (the mutation operator) explores the substructural neighborhood areas denned by the probabilistic model encoded in the Bayesian network. The improvement of each local search step can be estimated by considering the variation this mutation causes to the entropy measurement of the population. Experiments show that incorporating BOA with eSLS results in a substantial reduction in the number of costly fitness evaluations until convergence. Moreover, this paper provides original insights into how the randomness of populations can be exploited to enhance the performance of optimization processes.