Detecting General Problem Structures with Inductive Linkage Identification

Abstract

Genetic algorithms and the descendant methods have been deemed robust, effective, and practical for the past decades. In order to enhance the features and capabilities of genetic algorithms, tremendous effort has been invested within the research community. One of the major development trends to improve genetic algorithms is trying to extract and exploit the relationship among decision variables, such as estimation of distribution algorithms and perturbation-based methods. In this study, we make an attempt to enable a perturbation-based method, inductive linkage identification (ILI), to detect general problem structures, in which one decision variable can link to an arbitrary number of other variables. Experiments on circular problem structures composed of order-4 and order-5 trap functions are conducted. The results indicate that the proposed technique requires a population size growing logarithmically with the problem size as the original ILI does on non-overlapping building blocks as well as that the population requirement is insensitive to the problem structure consisting of similar substructures as long as the overall problem size is identical.