Effects of discrete hill climbing on model building forestimation of distribution algorithms
Wei-Ming Chen, Chu-Yu Hsu, Tian–Li Yu, Wei-Che Chien · 2013
Hybridization of global and local searches is a well-known technique for optimization algorithms. Hill climbing is one of the local search methods. On estimation of distribution algorithms (EDAs), hill climbing strengthens the signals of dependencies on correlated variables and improves the quality of model building, which reduces the required population size and convergence time. However, hill climbing also consumes extra computational time. In this paper, analytical models are developed to investigate the effects of combining two different hill climbers with the extended compact genetic algorithm and the dependency structure matrix genetic algorithm. By using the one-max problem and the 5-bit non-overlapping trap problem as the test problems, the performances of different hill climbers are compared. Both analytical models and experiments reveal that the greedy hill climber reduces the number of function evaluations for EDAs to find the global optimum.