Modeling and replicating higher-order dependencies in genetic algorithms

Problems exhibiting a building-block structure but lacking pairwise dependencies are hard for linkage learning mechanisms and consequently can be very hard to optimize. The current methods capable of building-block wise crossover begin the search for their models by exploiting dependencies between pairs of variables, thus fail to capture higher-order interactions that can not be easily decomposed into lower ones. This paper introduces an exclusive or (XOR) based higher-order dependency detection algorithm. The method searches for groups of variables where repeatedly applying XOR does not lead to entropy distillation. We experiment with a Genetic Algorithm (GA) that uses a building-block wise crossover according to the linkage model derived with the proposed method. Results show that the GA develops a correct linkage model for allelic-pairwise independent, k-bounded, additively separable test functions, solving them efficiently.