  The 0-1 Multidimensional Knapsack Problem (MKP) is a classical NP-hard
combinatorial optimization problem with many engineering applications. In this
paper, we propose a novel algorithm combining evolutionary computation with the
exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and
utilizes the information from the population to extract good partial
assignments. To find high-quality solutions, an exact algorithm is applied to
explore the promising search space specified by the good partial assignments.
The new solutions are used to update the population. Thus, the good partial
assignments evolve towards a better direction with the improvement of the
population. Extensive experimentation with commonly used benchmark sets shows
that our algorithm outperforms the state-of-the-art heuristic algorithms, TPTEA
and DQPSO, as well as the commercial solver CPlex. It finds better solutions
than the existing algorithms and provides new lower bounds for 10 large and
hard instances.
