Abstract: Cross Entropy method has recently been proposed as a heuristic method.It shows some simple performance in the process of solving combinatorial optimization problems.This paper makes full use of Cross Entropy method to obtain the best estimator for the max-cut problem which is a standard NP-hard problem in graph graphic theory.The proposed algorithm employs an auxiliary Bernoulli distribution，which transforms the original deterministic network into an associated stochastic one.Random samples can be generated by using a multidimensional Ber（p） distribution.Meanwhile，some random cuts can be gotten.The next step is to update the parameter vector p on the basis of the data collected in the first phase.The exact estimator of the maximal cut can be obtained.Numerical studies suggest that for the maximal cut the proposed algorithm has much better performance in convergence speed and stability.Moreover，the good solutions are found.

Key words: max-cut problem, cross entropy, importance sampling, combinatorial optimization

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

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