一种改进的遗传算法在TSP问题中的应用

• 作者: 曲海成 王永贵 赵婉彤
• 来源期刊: 辽宁工程技术大学学报（自然科学版）
• 学科: 工学
• 关键词: NP完全问题 遗传算法 排列法 顺序交换算子 合法交叉算子 灾难算子
• 年，卷（期）: 2011,（2）
• 所属期刊栏目: 电气工程与计算机技术
• 页码范围: 263-267
• 分类号: TP301
• 字数: 4571字
• 语种: 中文
• DOI: 10.3969/j.issn.1008-0562.2011.02.028

摘要

为了解决旅行商(TSP)不能够在多项式时间内求得最优解的问题,从仿生学的角度入手,重新设计了从问题域到算法域的编码和解码方法,应用"排列法"来初始化种群:并设计了两种染色体操作算子:顺序交换算子和合法交叉算子,保证了种群在进化过程中染色体的合法性:在种群进化选择方面,设计了一个新的更加仿生的选择算子--"灾难算子",并与经典算法的"轮盘赌"选择法相结合,作为改进算法的选择算子,进一步提高了算法的收敛速度.实验表明,改进后的遗传算法能更准确地找到最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王永贵	辽宁工程技术大学软件学院	47	293	10.0	15.0
2	曲海成	辽宁工程技术大学软件学院	52	387	11.0	18.0