Cheating Like The Neighbors: Logarithmic Complexity For Fitness Evaluation In Genetic Algorithms

While neighborhood-based algorithms can use incremental evaluation to obtain the fitness of a modified solution candidate, genetic crossover makes changes that are too big to easily allow reusing previous quality values. In this paper, we extend our previous work and evaluate the possibility of extending persistent data structures to carry residual fitness values that can be reused for later evaluation of derived solution candidates when applied to Multidimensional 0–1 Knapsack Problems. We show potential speedups especially on very large problem instances when compared to classic array-based implementations.