Balancing the Diversification-Intensification Trade-off Using Mixtures of Probability Models
Joan Alza, Josu Ceberio, Borja Calvo · 2018
The trade-off between diversification and intensification has been investigated recurrently in the field of evolutionary computation. Proof of this is the numerous approaches that have been devoted to finding a balance in the diversification-intensification behavior of algorithms. Despite the large amount of work on this topic, dynamically adjusting such behavior is still difficult and depends on the algorithm at hand. In this paper, we focus on estimation of distribution algorithms (EDAs). Usually, research on EDAs mainly focuses on the design of probability models that either represent as best as possible the characteristics of the problem, or accurately fit the domain of the solutions. In this work, we propose implementing mixtures of probability models that permit the dynamic adjustment of the scope of the EDA. Particularly, we design a mixture model that combines two unimodal Thurstone family probability models: the Plackett-Luce model and the Bradley-Terry model. The first model tends to concentrate the probability around the mode, while the second spreads the probability more. Using a homogeneity measure on the population of solutions, we dynamically decide the ratio of solutions to sample from each model. Performed experiments on the linear ordering problem demonstrate that this research line is definitively promising.