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

• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 最大割问题 交叉熵 重要抽样 组合优化
• 年，卷（期）: 2009,（30）
• 所属期刊栏目: 研究、探讨
• 页码范围: 53-56
• 页数: 4页
• 分类号: TP301.6
• 字数: 5318字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.30.017

摘要

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