遗传禁忌搜索算法收敛性和时间复杂度分析
牟乃夏1
徐玉静2
李洁2
张灵先2
1.山东科技大学 测绘科学与工程学院,山东 青岛266590;中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室,北京1001012.山东科技大学 测绘科学与工程学院,山东 青岛,266590
摘要：遗传禁忌搜索算法多用于车辆路径优化、旅行商问题等,试验证明:融合遗传算法与禁忌搜索算法的混合算法相比单一算法的性能有较大提升,但缺少理论证明.本文阐述了遗传禁忌搜索算法的混合策略,从理论上对该算法的收敛性进行了证明,对时间复杂度进行了分析.应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、问题规模以及遗传算法的种群数量有关.
关键词：遗传算法禁忌搜索算法收敛性时间复杂度马尔科夫链模型
分类号：P208(一般性问题)
资助基金：国家自然科学基金(41771476)山东省自然科学基金(ZR2016DM02)
论文发表日期：2018-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：5( 118-122 )
英文信息