遗传禁忌搜索算法收敛性和时间复杂度分析

Analyses of convergence and time complexity of genetic tabu search algorithm

遗传禁忌搜索算法多用于车辆路径优化、旅行商问题等,试验证明:融合遗传算法与禁忌搜索算法的混合算法相比单一算法的性能有较大提升,但缺少理论证明。本文阐述了遗传禁忌搜索算法的混合策略,从理论上对该算法的收敛性进行了证明,对时间复杂度进行了分析。应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、问题规模以及遗传算法的种群数量有关。

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.