求解0-1背包问题的交叉熵方法

摘要：

交叉熵方法是近几年发展起来的一种优化方法,被应用到许多组合优化问题的求解中并显示出很好的性能.文中使用交叉熵方法来求解一种经典的组合优化问题-0-1背包问题.具体方法是:首先按Bernoulli分布生成变量的随机样本,并根据约束条件修正样本,求出目标函数值样本,然后按照交叉熵最小原理建立分布参数的更新规则.建立了基于交叉熵方法的背包问题求解算法.数值实验表明,与目前常用方法相比,该方法在收敛速度和稳定性上都有较大的优势.

关键词：背包问题、交叉熵方法、组合优化

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金50335040;北京交通大学校科研和教改项目2004SM042

在线出版日期：2007-09-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：183-186,271