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

被引：11

作者：

王永贵 ^{[1
]}

曲海成 ^{[1
]}

赵婉彤 ^{[2
]}

机构：

[1] 辽宁工程技术大学软件学院

[2] 中共鞍山市委党校

来源：

辽宁工程技术大学学报(自然科学版) | 2011年 / 30卷 / 02期

关键词：

NP完全问题; 遗传算法; 排列法; 顺序交换算子; 合法交叉算子; 灾难算子;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：263 / 267

页数：5

共 9 条

[1]

遗传算法的研究与应用.[D].王银年.江南大学.2009, 05

[2]

一种改进的遗传算法及其在TSP求解中的应用.[D].于兴涛.山东大学.2006, 12

[3]

遗传算法.[M].王小平;曹立明著;.西安交通大学出版社.2002,

[4]

演化程序.[M].(美)Z.米凯利维茨(ZbigniewMichalewicz)著;周家驹;何险峰译;.科学出版社.2000,