四点三线遗传算法求解旅行商问题

• 作者: 卓慕瑰 郑明
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 遗传算法 旅行商问题 两阶段策略 四点三线
• 年，卷（期）: 2017,（14）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 148-154
• 页数: 7页
• 分类号: TP18
• 字数: 6032字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1701-0249

摘要

为解决NP完全的旅行商问题,提出一种四点三线遗传算法.该算法特色在两阶段策略,第一阶段是变异算子优化,将汉密尔顿环中所有大于两点的内部路径倒置,并用新极值代替原极值.第二阶段是四点三线优化,将汉密尔顿环分为n个四点三线局部路径并将每个局部路径转化为最优局部路径,将所有局部路径长度求和除以1/3.交叉算子结束后,如子代含有重复位点,将未交叉部分重复位点与交叉部分重复位点对应的父代等位点交换.通过将该算法与传统遗传算法及只进行第一步优化的遗传算法进行比较,采用TSPLIB数据库实例数据,证明该算法有更高的执行效率,有更强的收敛性,适合寻找最短TSP路径.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑明	梧州学院广西高校行业软件技术重点实验室	19	80	5.0	8.0
10	卓慕瑰	梧州学院广西高校行业软件技术重点实验室	4	13	2.0	3.0