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...
详细信息
ISBN:
(纸本)9781450349390
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 laSer, to determine which samples are retained for updating the model. In contrast, other evolution-inspired algorithms (such as rHN-G and MACRO) use selection 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 not from any difficulty 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.
暂无评论