| 一种求解多维背包问题的混合分布估计算法 |
| |
| 引用本文： | 王凌,王圣尧,方晨.一种求解多维背包问题的混合分布估计算法[J].控制与决策,2011,26(8):1121-1125. |
| |
| 作者姓名： | 王凌 王圣尧 方晨 |
| |
| 作者单位： | 1. 清华大学清华信息科学与技术国家实验室／自动化系,北京,100084
2. 清华大学清华信息科学与技术国家实验室 |
| |
| 基金项目： | 国家自然科学基金项目(70871065,60834004); 教育部新世纪优秀人才支持计划项目(NCET-10-0505); 高等学校博士学科点专项科研基金项目(20100002110014) |
| |
| 摘 要： | 针对多维背包问题（MKP），提出一种基于分布估计算法的混合求解算法,该算法基于优势种群构建概率模型，并基于概率模型采样产生新个体；同时，提出一种基于MKP问题信息的修复机制，有效修复采样后种群中的不可行解．另外，设计了一种自适应的局部搜索操作，以增强算法的局部搜索能力,基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性．
|
| 关 键 词： | 多维背包问题 分布估计算法 概率模型 混合算法 |
| 收稿时间： | 2010/5/5 0:00:00 |
| 修稿时间： | 2010/6/11 0:00:00 |
A hybrid distribution estimation algorithm for solving multidimensional knapsack problem |
| |
| WANG Ling,WANG Sheng-yao,FANG Chen.A hybrid distribution estimation algorithm for solving multidimensional knapsack problem[J].Control and Decision,2011,26(8):1121-1125. |
| |
| Authors: | WANG Ling WANG Sheng-yao FANG Chen |
| |
| Affiliation: | WANG Ling,WANG Sheng-yao,FANG Chen (a.Tsinghua National Laboratory for Information Science and Technology,b.Department of Automation,Tsinghua University,Beijing 100084,China. |
| |
| Abstract: | A hybrid algorithm based on estimation of distribution algorithm is proposed to solve multidimensional knapsack problem(MKP).In the algorithm,the probabilistic model is built with the superior population and new individuals are generated based on probability model.Meanwhile,a repair operator based on MKP specific knowledge is proposed to effectively repair infeasible solutions generated by sampling.In addition,an adaptive local search is designed to enhance the exploitation ability.Simulation results based ... |
| |
| Keywords: | multidimensional knapsack problem estimation of distribution algorithm probabilistic model hybrid algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《控制与决策》浏览原始摘要信息 |
|
点击此处可从《控制与决策》下载全文 |
