Crossentropy/optimisation hybrid approach
The CrossEntropy method when applied to the Travelling salesman problem relies on generating random samples of tours and then constructing a sequence of transition probability matrices whose entries will, ultimately, be concentrated on the edges of an optimal tour. Of course, the Hamiltonian cycle problem can be regarded as a special case of the Travelling salesman problem and is thus, in principle, solvable by this method. On the other hand, the various MDPbased methods (see Variance of first hitting times and Branchandfix method) also search for a probability transition matrix, entries of which are concentrated on the edges of a Hamiltonian cycle; however, they do so by solving a global optimisation problem, for instance, in the associated subspace of discounted occupational measures.
The crossentropy/optimisation hybrid approach was first proposed by Eshragh et al [2] and consists of two parts:

MDPpart – a static optimisation problem derived from the above mentioned embedding of a graph in a Markov decision process,

CEpart – extracting information from a random sample in a manner consistent with the CrossEntropy method. This part may be used either separately from or in conjunction with an appropriate optimisation algorithm.
The CEpart is slightly modified from the standard crossentropy implementation, in that we seek to generate reverse Hamiltonian cycles in addition to standard Hamiltonian cycles. Used alone, the CEpart should be enough to converge to an optimal solution (ie a Hamiltonian cycle), however, for moderately large graphs, the numerical performance suffers. This is the movitation for adding the MDPpart. While it does not influence the CEpart, it uses the information gained from the CEpart at each iteration to execute a heuristic aimed at finding a Hamiltonian cycle. Then, a Hamiltonian cycle may be found either by the CEpart or the MDPpart, and either allows the algorithm to terminate.
In Eshragh et al [2] experimental results are given that demonstrate which part of the algorithm is ultimately successful in finding Hamiltonian cycles in progressively larger graphs, and although the CEpart is usually successful in small graphs, for larger graphs the MDPpart allows the early termination of the algorithm. The algorithm is demonstrated to be capable of solving problems with hundreds of vertices.
The crossentropy/optimisation hybrid algorithm is discussed in greater detail in Eshragh [1].
PUBLICATIONS
[1] Eshragh, A. “Hamiltonian cycles and the space of discounted occupational measures.” PhD Thesis, University of South Australia, 2011. Trove
[2] Eshragh, A., Filar, J.A. and Haythorpe, M. “A hybrid simulationoptimization algorithm for the Hamiltonian cycle problem.” Annals of Operations Research, 189(1):103125, 2011. SpringerLink