Abstract: As it is difficult to realize local optimization of the Multidimensional Multiple-choice Knapsack Problem (MMKP), the Estimation of Distribution Algorithms (EDA) is applied to optimize the MMKP. In order to improve the local optimization ability of EDA, value weight factors of items for selection are built to improve the EDA initial model and probabilistic model updating methods. The impact of the extreme effects on the algorithm optimization process is balanced to overcome the defect that the local optimization ability of the traditional EDA is weak. A new non-feasible solution repair mechanism is adopted to maintain the facilitation of machine learning methods for the probabilistic model and improve the global optimization ability of the improved algorithm. Experimental results show that this algorithm can effectively optimize the MMKP and its performance is much better than traditional optimization algorithms.

Key words: heuristics, multidimensional multiple-choice knapsack, value weight, estimation of distribution, optimality