Combining Multiple Representations in a Genetic Algorithm for the Multiple Knapsack Problem

We propose a new evolutionary algorithm for the multiple knapsack problem (MKP) which uses multiple representations. Previous, successful approaches for the MKP have included a weight-coded, order-based representation, as well as a grouping representation enhanced by a dominance condition to restrict search. We propose a representation-switching genetic algorithm which periodically transforms the representation of individuals between these two representations. We show that this new hybrid algorithm outperforms the previous approaches.