A Novel Multi-Population Genetic Algorithm for Multiple-Choice Multidimensional Knapsack Problems

摘要

In this paper, a novel Multi-Population Genetic Algorithm (MPGA) is proposed to solve the Multiple-choice Multidimensional Knapsack Problem (MMKP), a kind of classical combinatorial optimization problems. The proposed MPGA has two evolutionary populations and one archive population, and can effectively balance the search biases between the feasible space and the in-feasible space. The experiment results demonstrate that the proposed MPGA is better than the existing algorithms, especially when the strength of constraints is relatively strong.