An Estimation of Distribution Algorithm With Cheap and Expensive Local Search Methods

In an estimation of distribution algorithm (EDA), global population distribution is modeled by a probabilistic model, from which new trial solutions are sampled, whereas individual location information is not directly and fully exploited. In this paper, we suggest to combine an EDA with cheap and expensive local search (LS) methods for making use of both global statistical information and individual location information. In our approach, part of a new solution is sampled from a modified univariate histogram probabilistic model and the rest is generated by refining a parent solution through a cheap LS method that does not need any function evaluation. When the population has converged, an expensive LS method is applied to improve a promising solution found so far. Controlled experiments have been carried out to investigate the effects of the algorithm components and the control parameters, the scalability on the number of variables, and the running time. The proposed algorithm has been compared with two state-of-the-art algorithms on two test suites of 27 test instances. Experimental results have shown that, for simple test instances, our algorithm can produce better or similar solutions but with faster convergence speed than the compared methods and for some complicated test instances it can find better solutions.