A crossover operator for objective functions defined over graph neighborhoods with interdependent and related variables

Abstract

Abstract This article presents a new crossover operator for problems with an underlying graph structure where edges point to prospective interdependence relationships between decision variables and neighborhoods shape the definition of the global objective function via a sum of different expressions, one for each neighborhood. The main goal of this work is to propose a crossover operator that is broadly applicable, adaptable, and effective across a wide range of problem settings characterized by objective functions that are expressed in terms of graph neighbourhoods with interdependent and related variables. Extensive experimentation has been conducted to compare and evaluate the proposed crossover operator with both classic and specialized crossover operators. More specifically, the crossover operators have been tested under a variety of graph types, which model how variables are involved in interdependencies, different types of expressions in which interdependent variables are combined, and different numbers of decision variables. The results suggest that the new crossover operator is statistically better or at least as good as the best-performing crossover in 75% of the families of problems tested.

Keywords

• Genetic algorithms
• Optimization
• Artificial intelligence
• Metaheuristics