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

• 作者: 张灵先 徐玉静 李洁 牟乃夏
• 来源期刊: 河南理工大学学报（自然科学版）
• 学科: 地球科学
• 关键词: 遗传算法 禁忌搜索算法 收敛性 时间复杂度 马尔科夫链模型
• 年，卷（期）: 2018,（4）
• 所属期刊栏目: 机电与计算机工程
• 页码范围: 118-122
• 页数: 5页
• 分类号: P208
• 字数: 3502字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张灵先	山东科技大学测绘科学与工程学院	11	104	5.0	10.0
2	牟乃夏	山东科技大学测绘科学与工程学院	25	242	8.0	15.0
6	徐玉静	山东科技大学测绘科学与工程学院	6	21	2.0	4.0
7	李洁	山东科技大学测绘科学与工程学院	9	16	3.0	3.0