| 求解0-1背包问题的交叉熵方法 |
| |
| 引用本文： | 卢长先,陆一平,查建中.求解0-1背包问题的交叉熵方法[J].计算机仿真,2007,24(7):183-186,271. |
| |
| 作者姓名： | 卢长先 陆一平 查建中 |
| |
| 作者单位： | 北京交通大学机械与电子控制工程学院,北京,100044 |
| |
| 基金项目： | 国家自然科学基金
,
北京交通大学校科研和教改项目 |
| |
| 摘 要： | 交叉熵方法是近几年发展起来的一种优化方法,被应用到许多组合优化问题的求解中并显示出很好的性能.文中使用交叉熵方法来求解一种经典的组合优化问题-0-1背包问题.具体方法是:首先按Bernoulli分布生成变量的随机样本,并根据约束条件修正样本,求出目标函数值样本,然后按照交叉熵最小原理建立分布参数的更新规则.建立了基于交叉熵方法的背包问题求解算法.数值实验表明,与目前常用方法相比,该方法在收敛速度和稳定性上都有较大的优势.
|
| 关 键 词： | 背包问题 交叉熵方法 组合优化 求解算法 背包问题 熵方法 Knapsack Problem 优势 稳定性 收敛速度 数值实验 规则 分布参数 最小原理 交叉熵 函数值 目标 随机样本 修正 条件 约束 变量 Bernoulli |
| 文章编号： | 1006-9348（2007）07-0183-04 |
| 修稿时间： | 2006-06-242006-06-28 |
A Cross-Entropy Method for Solving 0-1 Knapsack Problem |
| |
| LU Chang-xian,LU Yi-ping,CHA Jian-zhong.A Cross-Entropy Method for Solving 0-1 Knapsack Problem[J].Computer Simulation,2007,24(7):183-186,271. |
| |
| Authors: | LU Chang-xian LU Yi-ping CHA Jian-zhong |
| |
| Affiliation: | School of Mechanical and Electronic Control Engineering, Beijing Jiaotong University , Beijing 100044, China |
| |
| Abstract: | Cross-Entropy method is an optimization method developed in recent years,and it shows good performance when applied in many combinatorial optimization problems.This paper solves a classical combinatorial optimization problem-0-1-knapsack problem using Cross-Entropy method.Main strategy is: generating samples of variables by Bernoulli-distribution,revising the samples according to constraints,evaluating the samples of object value and establishing parameter-updating rule of distribution parameters based on cross entropy theory.The corresponding algorithm for knapsack problem is also given.Numerical experiments show that this algorithm has much better performance in convergence speed and stability compared with existing algorithms. |
| |
| Keywords: | Knapsack problem Cross - entropy method Combinatorial optimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
