Learning Variable Importance and Interaction in Genetic Algorithms for Pseudo-Boolean Optimization

Abstract Understanding variable importance and interactions is relevant to the analysis of optimization problem instances and can provide insights into the behavior of evolutionary algorithms. We study the estimation of variable importance and interaction in the context of pseudo-Boolean optimization performed by genetic algorithms. We propose a method to infer such information as a side-effect of the optimization process, without requiring additional fitness evaluations. The estimated variable importance and interaction information can be exploited to design more efficient reproduction operators. We explore this idea by proposing mutation and recombination operators that generate offspring from local optima. We evaluate the proposed approach on NK landscapes and on feature selection problems formulated as pseudo-Boolean optimization tasks. The results show that the proposed genetic algorithm can recover meaningful variable importance and interaction patterns and that leveraging this information can improve the efficiency and effectiveness of the search.