APPLYING GENETICS ALGORITHM AND STATISTICAL PROBABILITY RESULTS TO SOLVE HAMILTON CYCLE PROBLEM

Abstract

Finding Hamilton cycle is one of the most important NP-complete problems. Several studies, used in real problems, have been conducted to solve it, especially in heuristic solutions. In this paper, we propose a new approach that combines Genetics algorithm and appearance probabilities of edges in the optimal cycle. The final solution will be selected from results of generations gained in the whole population evolution. Our proposal is evaluated in various practical problems and compared with previous works. The experiment results prove that our approach is more efficient than those using either Genetics algorithm or statistical probability results. Hence, it proposes a new approach to solve heuristically problems of finding optimal Hamilton cycle.