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

被引：23

作者：

王凌

王圣尧

方晨

机构：

[1] 清华大学清华信息科学与技术国家实验室自动化系

来源：

控制与决策 | 2011年 / 08期

基金：

高等学校博士学科点专项科研基金;

关键词：

多维背包问题; 分布估计算法; 概率模型; 混合算法;

D O I：

10.13195/j.cd.2011.08.4.wangl.009

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

针对多维背包问题(MKP),提出一种基于分布估计算法的混合求解算法.该算法基于优势种群构建概率模型,并基于概率模型采样产生新个体;同时,提出一种基于MKP问题信息的修复机制,有效修复采样后种群中的不可行解,另外,设计了一种自适应的局部搜索操作,以增强算法的局部搜索能力.基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性.

引用

页码：1121 / 1125

页数：5

共 6 条

[1] 松驰互补的分布估计算法求解多维背包问题 [J].

杨广益 ;

欧阳智敏 ;

全惠云 .

计算机工程与应用, 2007, (12) :77-80

[2] 分布估计算法综述 [J].

周树德 ;

孙增圻 .

自动化学报, 2007, (02) :113-124

[3]

Scatter Search for the 0–1 Multidimensional Knapsack Problem[J] . Said Hanafi,Christophe Wilbaut.Journal of Mathematical Modelling and Algorithms . 2008 (2)

[4] A genetic algorithm for the multidimensional knapsack problem [J].

Chu, PC ;

Beasley, JE .

JOURNAL OF HEURISTICS, 1998, 4 (01) :63-86

[5] DYNAMIC-PROGRAMMING ALGORITHMS FOR THE ZERO-ONE KNAPSACK-PROBLEM [J].

TOTH, P .

COMPUTING, 1980, 25 (01) :29-45

[6]

Engineering Design and Manufacturing .2 Springer-Verlag . 1999

← 1 →