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

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