遗传禁忌搜索算法收敛性和时间复杂度分析 |
| |
引用本文: | 牟乃夏,徐玉静,李洁,张灵先.遗传禁忌搜索算法收敛性和时间复杂度分析[J].河南理工大学学报(自然科学版),2018(4). |
| |
作者姓名: | 牟乃夏 徐玉静 李洁 张灵先 |
| |
作者单位: | 山东科技大学测绘科学与工程学院;中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室 |
| |
摘 要: | 遗传禁忌搜索算法多用于车辆路径优化、旅行商问题等,试验证明:融合遗传算法与禁忌搜索算法的混合算法相比单一算法的性能有较大提升,但缺少理论证明。本文阐述了遗传禁忌搜索算法的混合策略,从理论上对该算法的收敛性进行了证明,对时间复杂度进行了分析。应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、问题规模以及遗传算法的种群数量有关。
|
本文献已被 CNKI 等数据库收录! |
|