求解最大割问题的交叉熵算法

摘要：

交叉熵方法(Cross Entropy)是近几年发展而来的一种启发式方法,在求解组合优化问题中显示出其简单有效的特点,将运用交叉熵方法(CE)寻求图论中一个典型的NP困难问题一最大割问题的最优解.为了解决最大割问题,CE方法借助Bernoulli分布的思想,将一个确定性的网络转换成一个具有一定随机性的关联网络,接下来首先按照一个多维的Bernoulli概率分布生成样本,同时计算出随机割;其次,基于前一步的数据,更新Bernoulli概率分布P参数,使得分布参数逐步逼近最优值产生最大割的稳定估计值.数值实验表明,CE方法具有很好的稳定性和收敛性,最终也获得了比较好的近似解.

关键词：最大割问题、交叉熵、重要抽样、组合优化

所属期刊栏目：45

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

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

页数：共4页

页码：53-56