摘要
交叉熵方法是近几年发展起来的一种优化方法,被应用到许多组合优化问题的求解中并显示出很好的性能。文中使用交叉熵方法来求解一种经典的组合优化问题—0-1背包问题。具体方法是:首先按Bernoulli分布生成变量的随机样本,并根据约束条件修正样本,求出目标函数值样本,然后按照交叉熵最小原理建立分布参数的更新规则。建立了基于交叉熵方法的背包问题求解算法。数值实验表明,与目前常用方法相比,该方法在收敛速度和稳定性上都有较大的优势。
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 opti- mization 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.
出处
《计算机仿真》
CSCD
2007年第7期183-186,271,共5页
Computer Simulation
基金
国家自然科学基金(50335040)
北京交通大学校科研基金(2004SM042)
关键词
背包问题
交叉熵方法
组合优化
Knapsack problem
Cross - entropy method
Combinatorial optimization
