多选择多维度背包问题的多尺度量子谐振求解算法

摘要

本发明公开了一种运筹学领域中经典的组合优化问题，即多选择多维度背包问题的多尺度量子谐振求解算法，首先针对原问题模型建立了拉格朗日松弛对偶模型，大大减少了约束条件，并利用拉格朗日价值来评价组内物品价值，在此基础上引入MMKP近似核问题，对寻找最优解具有启发作用，并且减少了问题规模。此外基于近似核问题构建了混合高斯采样模型，引导算法在可信区域强化搜索，在不可信区域均匀搜索，提高了求解精度和收敛速度。