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 [2] 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 [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 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 [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 simulation-optimization algorithm for the Hamiltonian cycle problem.” Annals of Operations Research, 189(1):103-125, 2011. SpringerLink