Analyses of convergence and time complexity of genetic tabu search algorithm
MOU Naixia
XU Yujing
LI Jie
ZHANG Lingxian
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.Mean-while,its time complexity was calculated by a stochastic algorithm.Based on the above methods,the time com-plexity 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.
Keywords：genetic algorithmtabu search algorithmconvergencetime complexityMarkov chain model
Publication Date：2018-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：5( 118-122 )