A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem |
| |
Authors: | Ali Eshragh Jerzy A Filar Michael Haythorpe |
| |
Institution: | 1.School of Mathematics and Statistics,The University of South Australia,Mawson Lakes,Australia |
| |
Abstract: | In this paper, we propose a new hybrid algorithm for the Hamiltonian cycle problem by synthesizing the Cross Entropy method
and Markov decision processes. In particular, this new algorithm assigns a random length to each arc and alters the Hamiltonian
cycle problem to the travelling salesman problem. Thus, there is now a probability corresponding to each arc that denotes
the probability of the event “this arc is located on the shortest tour.” Those probabilities are then updated as in cross
entropy method and used to set a suitable linear programming model. If the solution of the latter yields any tour, the graph
is Hamiltonian. Numerical results reveal that when the size of graph is small, say less than 50 nodes, there is a high chance
the algorithm will be terminated in its cross entropy component by simply generating a Hamiltonian cycle, randomly. However,
for larger graphs, in most of the tests the algorithm terminated in its optimization component (by solving the proposed linear
program). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|