Abstract：The hybrid of genetic algorithm and tabu search algorithm has greatly improved performances relative to one single algorithm. It has been widely used in vehicle route optimization and travel planning, etc. In this paper, a hybrid strategy of genetic tabu search algorithm was introduced and its convergence was theoretical proved. The time complexity of the algorithm was analyzed as well. By using Markov chain model, the algorithm of genetic tabu search was proved to have the global optimal solution with converge of probability 1. Meanwhile, its time complexity was calculated by a stochastic algorithm. Based on the above methods, the time complexity of the algorithm was obtained, which was proved to be highly related to the diversity of the solution, the problem scale and the population of the genetic algorithm.

Keyword：genetic algorithm;tabu search algorithm;convergence;time complexity;Markov chain model;