Linkage identification by perturbation and decision tree induction

Abstract

The purpose of linkage identification in genetic and evolutionary algorithms is to detect the strongly related variables of the fitness function. If such linkage information can be acquired, the crossover or recombination operator can accordingly mix the discovered sub-solutions effectively without disrupting them. In this paper, we propose a new linkage identification technique, called inductive linkage identification (ILI), employing perturbation with decision tree induction. With the proposed scheme, the linkage information can be obtained by first constructing an ID3 decision tree to learn the mapping from the population of solutions to their corresponding fitness differences caused by perturbations and then inspecting the constructed decision tree for variables exhibiting strong interdependencies with one another. The numerical results show that the proposed technique can accomplish the identical linkage identification task with a lower number of function evaluations compared to similar methods proposed in the literature. Moreover, the proposed technique is also shown being able to handle both uniformly scaled and exponentially scaled problems.