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

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

作　　者：谭阳[1,2] 刘章[2] 周虹[2] Tan Yang;Liu Zhang;Zhou Hong(College of Computer Science, Human Normal University, Changsha 410081, China;Human Radio and Television University, Changsha 410004, China.)

机构地区：[1]湖南师范大学计算机科学学院,长沙410081 [2]湖南广播电视大学,长沙410004

出　　处：《系统仿真学报》2017年第12期3123-3131,共9页Journal of System Simulation

基　　金：国家自然科学基金(10971060);湖南省教育厅重点项目(10A074);湖南省高校科研项目(14C0781;15C0928)

摘　　要：针对多维多选择背包问题(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.

关 键 词：启发式 多维多选择背包 价值权重 分布估计 优化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]