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

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