# Cross-entropy/optimisation hybrid approach

The Cross-Entropy 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 MDP-based methods (see Variance of first hitting times and Branch-and-fix 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 cross-entropy/optimisation hybrid approach was first proposed by Eshragh et al  and consists of two parts:

• MDP-part – a static optimisation problem derived from the above mentioned embedding of a graph in a Markov decision process,
• CE-part – extracting information from a random sample in a manner consistent with the Cross-Entropy method. This part may be used either separately from or in conjunction with an appropriate optimisation algorithm.

The CE-part is slightly modified from the standard cross-entropy implementation, in that we seek to generate reverse Hamiltonian cycles in addition to standard Hamiltonian cycles. Used alone, the CE-part 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 MDP-part. While it does not influence the CE-part, it uses the information gained from the CE-part at each iteration to execute a heuristic aimed at finding a Hamiltonian cycle. Then, a Hamiltonian cycle may be found either by the CE-part or the MDP-part, and either allows the algorithm to terminate.

In Eshragh et al  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 CE-part is usually successful in small graphs, for larger graphs the MDP-part allows the early termination of the algorithm. The algorithm is demonstrated to be capable of solving problems with hundreds of vertices.

The cross-entropy/optimisation hybrid algorithm is discussed in greater detail in Eshragh .

### PUBLICATIONS

 Eshragh, A. “Hamiltonian cycles and the space of discounted occupational measures.” PhD Thesis, University of South Australia, 2011. Trove

 Eshragh, A., Filar, J.A. and Haythorpe, M. “A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem.” Annals of Operations Research, 189(1):103-125, 2011. SpringerLink