On A Particularity In Model-based Search
Christian Blum, Michaël Sampels, Mark Zlochin · 2002
Giving positive feedback to good solutions is a common base technique in model-based search algorithms, such as Ant Colony Optimization, Estimation of Distribution Algorithms, or Neural Networks. In particular, the reinforcement of components of good solutions by positive feedback is known as a successful technique in tackling hard combinatorial optimization problems. We show by a simple model-based search algorithm for the node-weighted k-cardinality tree problem that this strategy doesn't guarantee steadily increasing performance of the algorithm in general. It is rather possible that for some "problem"-"probabilistic model" combinations the average performance of the system is decreasing and even the average probability of sampling good solutions is decreasing over time. The result is proven analytically and the consequences are studied in some empirical case studies.