How to get more from your model: the role of constructive selection in estimation of distribution algorithms

Model-building optimisation methods aim to learn the structure underlying a problem and exploit this to direct the exploration of solutions. This generally interleaves two processes: Generating samples (from the model), and updating the model (using selected samples). In most estimation of distribution algorithms (EDAs),e.g. BOA, selection is used only in the latter, to determine which samples are retained for updating the model. In contrast, other evolution-inspired algorithms (such as rHN-G and MACRO) useselection differently - within the process that generates samples from the model. It has been hypothesised that this ’constructive selection’ process can facilitate optimisation that other EDAs cannot but this has not been previously shown. Here we investigate these distinctions using constraint optimisation problems with a very simple modular structure. We find that a simple constructive selection method (rHN-g) can solve these problems in time polynomial in the problem size whereas other methods, such as BOA, require exponential time. We confirm that this result arises notfrom any diffculty in acquiring an accurate model but because of how samples are generated given the model. This suggests that by using constructive selection other EDAs could exploit the models they learn more efficiently to solve otherwise unsolvable problems