一种求解多维多选择背包问题的分布估计算法

Distributed Estimation Algorithm for Multi-dimensional Multi-choice Knapsack Problem

针对多维多选择背包问题(MMKP)局部难以优化的特点,提出将分布估计算法(EDA)应用于优化MMKP问题。为了提升EDA优化局部的能力,以构建待选物品价值权重因子的方式来改进EDA的初始模型和概率模型更新方法;并平衡了极值效应对算法寻优过程的影响,克服了传统EDA局部优化能力不强的缺陷.同时采用新的非可行解的修复机制,维护了机器学习法对概率模型的促进作用,提高了改进算法的全局优化能力。实验结果表明,该算法能够有效地优化MMKP问题,其性能高于传统的优化算法。

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.