Availability of Perfect Decomposition in Statistical Linkage Learning for Unitation-based Function Concatenations
This work addresses a specific bottleneck in optimization algorithms for practitioners, but it is incremental as it builds on existing SLL methods.
The authors tackled the problem of understanding when Statistical Linkage Learning (SLL) can achieve perfect decomposition for concatenations of unitation-based functions, by analytically estimating the population size needed and confirming it experimentally, identifying hard problem types for SLL-using optimizers.
Statistical Linkage Learning (SLL) is a part of many state-of-the-art optimizers. The purpose of SLL is to discover variable interdependencies. It has been shown that the effectiveness of SLL-using optimizers is highly dependent on the quality of SLL-based problem decomposition. Thus, understanding what kind of problems are hard or easy to decompose by SLL is important for practice. In this work, we analytically estimate the size of a population sufficient for obtaining a perfect decomposition in case of concatenations of certain unitation-based functions. The experimental study confirms the accuracy of the proposed estimate. Finally, using the proposed estimate, we identify those problem types that may be considered hard for SLL-using optimizers.