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

被引：11

作者：

郑明 ^{[1
,2
,3
]}

卓慕瑰 ^{[1
,2
]}

机构：

[1] 梧州学院广西高校行业软件技术重点实验室

[2] 梧州学院信息与电子工程学院

[3] 吉林大学计算机科学与技术学院

来源：

计算机工程与应用 | 2017年 / 53卷 / 14期

基金：

中国博士后科学基金;

关键词：

遗传算法; 旅行商问题; 两阶段策略; 四点三线;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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

引用

页码：148 / 154

页数：7

共 11 条

[1] A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks [J].

Urrutia, Sebastian ;

Milanes, Anolan ;

Lokketangen, Arne .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2015, 22 (01) :61-75

[2] Dynamic ng-Path Relaxation for the Delivery Man Problem [J].

Roberti, Roberto ;

Mingozzi, Aristide .

TRANSPORTATION SCIENCE, 2014, 48 (03) :413-424

[3]

A Hybrid Method to Search the Optimal Hamiltonian Circuit[J] . Guo Fu Tian,Shi Zhou Zhang,Shu Hui Sun.Advanced Materials Research . 2013 (605)

[4]

Simultaneous production and logistics operations planning in semicontinuous food industries[J] . Georgios M. Kopanos,Luis Puigjaner,Michael C. Georgiadis.Omega . 2011 (5)

[5]

An overall-regional competitive self-organizing map neural network for the Euclidean traveling salesman problem[J] . Junying Zhang,Xuerong Feng,Bin Zhou,Dechang Ren.Neurocomputing . 2012

[6]

GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem[J] . Mário Mestria,Luiz Satoru Ochi,Simone de Lima Martins.Computers and Operations Research . 2012

[7]

A genetic algorithm application using fuzzy processing times in non-identical parallel machine scheduling problem[J] . Advances in Engineering Software . 2011 (1)

[8]

Inferring gene regulatory networks using a hybrid GA–PSO approach with numerical constraints and network decomposition[J] . Wei-Po Lee,Yu-Ting Hsiao.Information Sciences . 2011

[9]

Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms[J] . Murat Albayrak,Novruz Allahverdi.Expert Systems With Applications . 2010 (3)

[10]

Multi-parent extension of partially mapped crossover for combinatorial optimization problems[J] . Chuan-Kang Ting,Chien-Hao Su,Chung-Nan Lee.Expert Systems With Applications . 2009 (3)

← 1 2 →