开发编程工具来处理货郎担问题的三个面向对象的语言

文摘

旅行商问题(TSP)是最著名的一个问题。许多应用程序和编程工具开发处理TSP。然而,它似乎是必要提供简单的编程工具根据先进的算法。因此,我们搜集了三个新的简单工具的面向对象编程语言。在本文中,我们目前的ADT(抽象数据类型)的开发工具;然后我们通过实验分析其性能。我们也设计一个混合遗传算法(近半年)开发工具。实验结果表明,该无形体病相当最近最先进的应用程序。

1。介绍

TSP的目的是找到一组引用之间的最短之旅。考虑到距离矩阵在哪里代表城市之间的距离和,这个问题被称为对称TSP (STSP),否则,它被命名为不对称TSP (ATSP)。

由于TSP是np完备性,没有准确的算法时间复杂度比一个指数。这意味着精确算法是不实际的大规模实例在合理的运行时间,所以我们必须使用近似算法来找到semioptimal解决方案可接受的运行时间。最近,已研制出许多近似算法来处理TSP实例(<一个href="#B1">1- - - - - -<一个href="#B4">4]。metaheuristics像遗传算法(GA)的类型(<一个href="#B5">5- - - - - -<一个href="#B7">7),模拟退火(<一个href="#B8">8],基于蜂群算法[<一个href="#B9">9),人工蜂群算法(<一个href="#B10">10[],蚁群算法<一个href="#B11">11,<一个href="#B12">12),结合这些算法已经应用于TSP (<一个href="#B13">13,<一个href="#B14">14]。然而,如果我们考虑这些引用的实验部分,我们注意到,几乎所有这些算法还没有被应用到实例的大小超过1000人。其中metaheuristics,暴躁,Lin-Kernighan(路)是一种局部搜索算法(lsa)(本文LS指向本地搜索)是最好的算法之一,它的扩展类型已经成功地应用于大规模实例85000多个节点的大小(<一个href="#B3">3,<一个href="#B15">15]。此外,在许多情况下,这些算法已用于其他metaheuristics和增加他们的表现<一个href="#B2">2,<一个href="#B11">11,<一个href="#B16">16]。

直燃型溴化锂包括2 -和3-opt Lin-Kernighan(路)算法都是基于边缘交换过程(<一个href="#B1">1,<一个href="#B3">3,<一个href="#B15">15,<一个href="#B17">17]。天然气以人群为基础的,其效率取决于他们的运营商<一个href="#B4">4]。轻松地使用这些算法,我们有客观工具由三个面向对象编程语言,包括c++, c#和Java。这些工具允许研究人员或开发人员能够很容易地利用这些metaheuristics和创建自己的混合算法(这些工具都可以通过电子邮件请求<一个href="mailto:esmkha@gmail.com" target="_blank">esmkha@gmail.com(主题:TSP_Tools))。

本文主要开发工具关注类型的遗传算子和直燃型溴化锂;然而,类型的蚁群优化(ACO)已经分别实现,可用。直燃型溴化锂的实现是基于LKH实现(<一个href="#B1">1,<一个href="#B15">15,<一个href="#B18">18]这是一个最著名的和有效的实现路。此外,一些著名的初始解构造函数Quick-Boruvka和最近邻(NN)策略已经包含在这些工具。遗传算子的选择从文学。这些操作符包括PMX [<一个href="#B19">19],EPMX [<一个href="#B20">20.],VGX [<一个href="#B21">21],IGX [<一个href="#B5">5),GX(这个操作符的描述及其版本可以在找到<一个href="#B5">5,<一个href="#B19">19,<一个href="#B21">21,<一个href="#B22">22)、GSX-0 GSX-1、GSX-2 DPX [<一个href="#B16">16),和牛<一个href="#B23">23]。这些算子的实现是有效的。实验结果表明,在几乎所有情况下,性能(在运行时间和准确性)的开发运营商甚至比报道结果的引用。

本文并不局限于开发工具。提出了一种混合遗传算法,本文并使用一个两层楼的策略是快速和准确。实验结果表明,提出的混合算法的性能优于最近最先进的算法之一。

通过这些描述,本文的组织结构如下:在本文的其余部分中,我们简要描述直燃型溴化锂和ADT的编程。我们审查GA,运营商,ADT的第三节课。节<一个href="#sec4">4路,我们结合到遗传算法和混合遗传算法设计。我们提出的这些算法实验结果部分<一个href="#sec5">5最后总结论文部分<一个href="#sec6">6。

2。直燃型溴化锂

多数的lsa对TSP基于边缘交换过程。2-opt, 3-opt,路有三个重要的lsa算法分类。我们编写这些启发式c++, c#和Java。在本节中,我们审查其算法简单,然后我们国家adt的编程工具。

2.1。的选择

2-opt的一个特例- opt。参观被命名为- opt,如果它是不可能减少旅游通过改变的成本边数。2-opt转换输入之旅可能2-opt情况。算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg1/" target="_blank">1显示了2-opt的一般算法。

想旅游与上所定义的边缘图G (V, E):
(1)假设方向。
(2)如果没有节点像,B, C和D下面条件然后去结束。
(我)AB, CD
在该方向上(a), B和D是正确的节点分别为a和C。
(2)成本(AB) +成本(CD) >成本(AC) +成本(BD)
(3)删除AB和CD表单并添加AC和BD (2-opt-move)。
(4)去(2)。
(5)结束。

指令3算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg1/" target="_blank">1叫2-opt-move或2-change如图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig1/" target="_blank">1。在2-opt-move 2-opt算法时条件指令2感到满意。时间复杂度的精确2-opt很高,因此,提高速度2-opt算法,研究人员通常使用两个重要的规则已被提出的宾利。(1)为每个节点在第2行,我们只考虑它的候选节点。通常五个最近的邻居选择候选人的每个节点集。这些设置可以大约计算了k-d-tree [<一个href="#B24">25在( )。(2)在指令2中,只考虑活跃节点。的节点参与旅游成本降低在先前的迭代中被激活为下一次迭代。这种启发式方法被称为“不是位”(<一个href="#B25">26]。

2.2。选择

3-opt经营像2-opt但其条件交换边缘相当复杂(见[<一个href="#B26">27])。算法在每一步3-opt探针3条边交换,所以当三条边被删除,六个相当大的情况下出现,探索这些病例增加时间复杂度和算法实现变得更加复杂。

2.3。路

路的类型可能是最好的启发式方法,已经成功应用于TSP。此外,天然气等其他metaheuristics广泛使用变体版本的这种启发式方法来改善他们的解决方案。关于路的更多描述,我们建议读者参考(<一个href="#B15">15,<一个href="#B17">17该算法简单),但这里我们礼物。路可以引入的三个词:“休息”,“链接”和“条件测试”。路算法在一些迭代。在每个迭代中,交流一些边缘被另一个降低旅游成本。附录<一个href="#secA">一个显示了一个简单的路算法。

2.4。回顾ADT直燃型溴化锂的类

实现直燃型溴化锂,我们需要定义一些原始的数据结构如图和旅游,因为这些数据结构定义所需的其他部分程序和类。在本节的其余部分,我们首先定义类图和旅游;然后,我们现在类启发式方法。

2.4.1。图类

我们的图实现都装在图类。它可以阅读。tsp文件和计算节点之间的距离。它支持所有已知的TSP格式像地理,几何学,丙氨酸,EU-2D, CEIL-2D。算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg2/" target="_blank">2ADT展示图。图形类对象应该通过其构造函数读取TSP文件一旦被创建(4号线)。

//节点索引从0开始,去图维方位−1
(1)类图
(2){
(3)公众:
(4)图(字符路径);
(5)~图();
(6)node1 int D (int, int node2);
(7)int D (int x1, int y₁, int x2, y2 int);
(8)int维度();
(9)双X (int节点);
(10)双Y (int节点);
(11)};

2.4.2。旅游类

旅游ADT算法所示<一个href="//www.newsama.com/journals/acisc/2014/137928/alg3/" target="_blank">3。创建旅游对象属于图形对象。旅游对象完成后添加(=维度)节点,要么增加正确的(通过使用函数在第6行)或添加到左边(通过使用函数在第7行)。

(1)类之旅
2 {
3 公众:
4 旅游(图图);/ /旅游构造函数给出了一个黑gaph对象r为一个rgument
5 ~之旅();
6 int Add_Right (int节点);/ / exends uncomlete旅游从右
7 int Add_Left (int节点);/ / exends uncomlete旅游从左
8 int (int节点);/ /返回正确的邻居节点的完成旅行
9 int左(int节点);/ /返回左邻居节点完成旅行
10 无符号长长期成本();/ /计算并返回成本
11 空白InitiateRandomly ();/ /表单由序列之旅:0,1,…,维方位−1
12 之旅副本();
13 短赋予IsComplete(); / /如果完整之旅,这个函数返回1,否则为0。
14 空白重置();
15 };

2.4.3。启发式类

我们包装2-opt 3-opt路,Quick-Boruvka,双层桥到启发式类。操纵候选集,我们还添加了一些功能到启发式类。Quick-Boruvka有效旅游构造函数算法。双层桥通常用于变异。算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg4/" target="_blank">4显示类ADT启发式。启发式班上路方法基于最新版本的LKH,所谓LKH-2,及其在C语言源代码和免费的学术使用[<一个href="#B18">18]。

/ 我们根据LKH实现这个类函数(<一个href="#B18">18]免费供学术使用。 /
1 类启发式
2 {
3 公众:
/ 启发式对象计算候选集一旦创建,第二个参数
构造函数是候选人的数量每组。 /
4 启发式(图图,int NumberOfCandidates);
5 ~启发式();
/ 两行 6 和 7 显示的是2- - - - - -选择但功能 6 考虑到所有的节点
为活跃但功能 7 假设只在ActiveNodes节点数组是活跃的 /
6 空白TwoOpt(旅游旅游);
7 空白TwoOpt(旅游之旅,int ActiveNodes, int NumberOfActiveNodes);
/ 两行 8 和 9 显示了3-OPT但功能 8 考虑到所有的节点
为活跃但功能 9 假设只在ActiveNodes节点数组是活跃的 /
8 空白ThreeOpt(旅游旅游);
9 空白ThreeOpt(旅游之旅,int ActiveNodes, int NumberOfActiveNodes);
/ 两行 10 和 11 显示了路但功能 10 考虑到所有的节点
为活跃但功能 11 假设只在ActiveNodes节点数组是活跃的 /
10 空白LinKernighan(旅游旅游);
11 空白LinKernighan(之旅之旅,int ActiveNodes, int NumberOfActiveNodes);
12 空白DoubleBridge(之旅之旅);
13 之旅 Q_Boruvka ();
14 int SetCandidates (int节点,int, int指数);
15 int GetCandidates (int节点,int指数);
16 空白SetBestTour(旅游 best_tour);
17 };

3所示。遗传算法

遗传算法的搜索算法之一的灵感来源于自然界的进化过程。近年来,研究人员已经解决了许多np完全问题,遗传算法调度(<一个href="#B27">28,<一个href="#B28">29日,路由<一个href="#B29">30.),和作业<一个href="#B30">31日,<一个href="#B31">32和许多其他问题近年来已经被遗传算法有效地解决了。GA与人口的解决方案,在每个步骤中,新的解决方案是由交叉算子,或一个或多个解决方案改变了变异算子。交叉算子通常从人口得到两个解。这两个解决方案是所谓的父母(或父母)。交叉创建新的解决方案基于父母(s)。新解决方案叫做孩子或后代。有问题的解决方案适合提交突变或交叉算子。有一些论文回答这个问题(<一个href="#B32">33,<一个href="#B33">34]。遗传算法的交叉和变异是两个运营商扮演重要的角色在进化遗传算法的解决方案。一般来说,直燃型溴化锂包括路扩展,如迭代路(亲属)<一个href="#B3">3)和LKH版本(<一个href="#B1">1,<一个href="#B15">15处理TSP)是非常强大的。然而,也有一些有效的遗传算法或扩展经营的一个<一个href="#B4">4使用非常有效的交叉算子,所谓边缘组装交叉(EAX)。在本节中,我们回顾一些交叉运营商已包含在开发工具。

3.1。遗传算子的审查

许多遗传算法交叉运营商一直因为遗传算法的性能取决于研究人员发明的这些操作符的能力。PMX [<一个href="#B19">19)是第一个提出的跨界车已Goldberg和林格尔在1985年。文献[<一个href="#B20">20.]PMX一些缺点,克服它们,建议延长PMX (EPMX)。DPX [<一个href="#B16">16)是另一个产生的交叉与贪婪的共同边缘的连接在两个孩子的父母。贪婪subtour跨界车(GSXs) [<一个href="#B35">24,<一个href="#B34">35,<一个href="#B36">36)家庭是另一组跨界车快速运作。GSX-2 [<一个href="#B36">36]GSX-0的改进版本<一个href="#B34">35]和GSX-1 [<一个href="#B35">24]。戴维斯提出的顺序交叉(牛)是另一个在它的扩展不仅应用于TSP (<一个href="#B23">23),但也解决了许多其他非完全多项式<一个href="#B31">32,<一个href="#B37">37]。

在本节中,我们代表最近的一些遗传算法交叉车型和介绍他们的例子。在这些示例中,我们使用这组与八节点图:、2、3、4、5、6、7,它的边缘重量是如表所示<一个href="//www.newsama.com/journals/acisc/2014/137928/tab1/" target="_blank">1。


	1	2	3	4	5	6	7	8

1	0	12	19	31日	22	17	23	12
2	12	0	15	37	21	28	35	22
3	19	15	0	50	36	35	35	21
4	31日	37	50	0	20.	21	37	38
5	22	21	36	20.	0	25	40	33
6	17	28	35	21	25	0	16	18
7	23	35	35	37	40	16	0	14
8	12	22	21	38	33	18	14	0

3.1.1。PMX交叉

部分映射交叉(PMX)是第一个遗传算子。它产生两个孩子据两位父母两个任意点之间通过交换节点。

PMX无法检测到相同的节点映射领域。在图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig2/" target="_blank">2,它可以很容易地看到PMX不能确定该节点7是常见的在这两个映射领域。PMX双点交叉和这些跨界车不适合解决TSP。这些缺陷可能会导致重复的孩子们在这个交叉生产(<一个href="#B20">20.]。

(一)父母

(b)任意点的选择

(c)的孩子

3.1.2。EPMX交叉

文献[<一个href="#B20">20.]试图克服PMX的缺点,提出了扩展PMX (EPMX)。它选择一个独特的节点在此之前任意点任意点与交流,产生两个孩子。EPMX为例,由于父亲= 1-2-3-4-5-6-7-8和母亲= 1-2-3-4-5-6-7-8,假设任意点= 4所以父亲= 1-2-3-4 | 1-2-3-4和母亲= 1-4-8-6 | 1-4-8-6分为两个子列表。节点2和3的第一子列表的父亲不重复母亲和节点的子表8和6从第一分表的母亲不重复第一个分表的父亲形式交流所以孩子们产生child1 = 1-4-8-6-5-3-7-2和child2 = 1-4-8-6-5-3-7-2。

3.1.3。贪婪的跨界车(gx)

GX的一些版本非常贪婪交叉(VGX) [<一个href="#B21">21)和改进的贪婪交叉(<一个href="#B5">5近年来被研究人员提出。回顾这些跨界车,读者可以参考<一个href="#B5">5]。

3.1.4。改进的贪婪Subtour交叉(GSX-2)

GSX-2 [<一个href="#B36">36]GSX-0的改进版本<一个href="#B34">35]和GSX-1 [<一个href="#B35">24]。GSX-0 GSX家族的第一个版本。算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg5/" target="_blank">5显示GSX-0算法。

1 节点X 选择随机节点;
2 X复制到孩子;
3 节点R X;
4 节点L X;
5 而(真)
6 {
7 R 对邻居的R父亲之旅;
8 l L左邻居的母亲之旅;
9 如果R是孩子然后打破while循环;
10 如果L是儿童然后打破while循环;
11 添加节点R孩子右侧;
12 添加节点L孩子左边;
13 }
14 剩余的节点(节点完成孩子的避风港”t被复制到孩子旅游)随机;
15 返回的孩子;

图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig3/" target="_blank">3(一个)显示了GSX-0示例。在这个例子中,在节点5已经包含在孩子见面,GSX-0随机节点来填充剩余的地方的,但一样的人物<一个href="//www.newsama.com/journals/acisc/2014/137928/fig3/" target="_blank">3 (b)显示GSX-1例子,它填补了剩余的节点之一的父母。

(一)GSX-0例子

(b) GSX-1例子

一般来说,GSX-1运作比GSX-1剩余节点的因为它可以维持秩序,但在某些情况下,它会产生重复的旅游;一样的图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig3/" target="_blank">3 (b),儿童旅游是一样的父亲旅游。文献[<一个href="#B36">36]国家GSX-0 GSX-1和的一些缺点,为了克服这些不足,提出GSX-2。

3.1.5。距离保护操作符(DPX)

DPX [<一个href="#B16">16操作如下:它检测常见的两个父母的子路径,然后重新连接时他们贪婪地产生孩子。图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig4/" target="_blank">4显示了DPX示例使用了边缘图在表的重量<一个href="//www.newsama.com/journals/acisc/2014/137928/tab1/" target="_blank">1。

(一)父母

(b)常见的子路径

(c)的孩子

3.2。ADT的跨界车类

我们有交叉运营商进入包装交叉类。算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg6/" target="_blank">6显示ADT的交叉类。5 - 14行显示的定义跨界车功能。功能在5 - 12行显示跨界车取两个旅游作为父亲和母亲和生产只有一个孩子,所以他们的功能需要三tour-pointers作为输入参数。前两个参数是指父旅游和第三个参数指向孩子之旅。行12、13和14显示牛,PMX, EPMX产生两个孩子所以他们需要4参数的函数。前两个参数指向父之旅第二两个参数指向两个孩子游。

1 类跨界车
2 {
3 公众:
4 CrossoversGraph(图 );
/ /原始贪婪的交叉”函数定义。
5 空白GX(旅游、旅游、旅游 );
/ /另一个版本的贪婪的交叉”s函数定义(<一个href="#B17">17,<一个href="#B21">21]。
6 空白GX_4(旅游、旅游、旅游 );
/ /函数定义GX的另一个版本(<一个href="#B17">17,<一个href="#B21">21]。
7 空白GX_4_Pool(旅游、旅游、旅游 );
/ 行 8 来 15 提出了函数定义提出的跨界车
(<一个href="#B3">3,<一个href="#B5">5,<一个href="#B16">16,<一个href="#B20">20.,<一个href="#B21">21,<一个href="#B23">23,<一个href="#B35">24]分别。 /
8 空白VGX(旅游、旅游、旅游 );
9 空白IGX(旅游、旅游、旅游 );
10 空白DPX(旅游、旅游、旅游 );
11 空白GSX(旅游、旅游、旅游 );
12 无效的牛(旅游、旅游、旅游、旅游 );
13 空白PMX(旅游、旅游、旅游、旅游 );
14 空白EPMX(旅游、旅游、旅游、旅游 );
15 };

这些跨界车的性能,基于速度和精度,分析了在<一个href="#B5">5]。结果在<一个href="#B5">5)表明,启发式交叉车型IGX和DPX比其他人有更多的准确性。这些结果还表明,跨界车像GSX家庭比别人有更多的多样性意味着这些跨界车可以产生各种不同的解决方案。

3.3。类型的遗传算法

有两个主要模型GA:代际和稳态。代际之间主要的顺从和稳态遗传算法,在代际遗传算法,新的解决方案添加到人口,一些步骤之后,人口规模是标准化通过消除糟糕的个人,但在稳态GA,新的解决方案是取代了旧的解决方案之一,人口。在这两种算法,变异操作可以应用在一个或多个解决方案定期的人口。

最近,研究人员添加解决方案改进2 -选择等功能,3-opt,路GA。这些函数通常应用于新的解决方案创建或更改后的交叉和变异操作。这些气体被称为迷因或混合GA(无)。迷因是一般概念,指出所有进化算法,结合本地搜索来改善他们的解决方案。

4所示。发展中国家近半年的发达客观的工具

显示的适用性提出了客观的工具,我们开发新的模型近半年的不同在两种情况下与另一个版本(见附件)。(1)两层遗传算法提出了近半年。这意味着该近半年一直由两层遗传算法。GA的第一层使用启发式遗传算子如GX版本。这层提高人口素质,所以LSA可以迅速在第二层楼。应该会,直燃型溴化锂可以快速高质量的解决方案。因此,这层影响第二个层路在哪里利用。路运营很快当它应用于高质量的旅游。(2)第二个层近半年也无形体病本身。像其他近半年的算法结合LSA提高旅游质量,提出了近半年也和利用路为LSA但(我)定期更新路是候选人的集,这些层的指令执行;(2)为了培养出各种各样的解决方案应该使用快速交叉算子高多样性一样古典PMX, GSX-1或EPMX代替启发式交叉通常是缓慢的。注意到路保证解决方案的质量所以不合理使用时间消费者启发式的跨界车。

5。实验

在本节中,我们将展示客观工具性能。我们把这部分三个部分。在第一小节中,我们关注直燃型溴化锂工具,在第二节,我们提出了跨界车的实验结果,实验结果,最后,我们展览近半年的开发目标指定的工具。

5.1。开发工具的性能

测试开发LS工具包括2-opt 3-opt,路,我们将它们应用在15 TSPLIB实例20次。用户可能需要了解LS工具的准确性和速度,我们报告最好,最坏的情况下,平均和标准偏差记录成本和运行时的LS工具/每个实例的20分。表<一个href="//www.newsama.com/journals/acisc/2014/137928/tab2/" target="_blank">2显示平均,最好的,最糟糕的情况下,和标准偏差二十解决方案的成本为每个实例通过每一个启发式。而且,这个表显示错误的最佳百分比,平均和糟糕的解决方案成本计算。usa115475请考虑,优化成本是未知的,所以我们使用了最好的解决方案成本(6283142)所获得的路的工具。

(一)


	最优成本	最好的		平均		最糟糕的		方差
	最优成本	成本	误差(%)	成本	误差(%)	成本	误差(%)	方差

att532	27686年	28004年	1.149	28271年	2.113	28466年	2.817	135.82961
rat783	8806年	9001年	2.214	9030.35	2.548	9079年	3.1	24.598406
pr1002	259045年	263489年	1.716	265864.85	2.633	267891年	3.415	1053.8556
rl1889	316536年	362397年	14.488	366151.5	15.675	370419年	17.023	2649.2821
pr2392	378032年	388057年	2.652	390727.5	3.358	393472年	4.084	1552.5029
pcb3038	137694年	140534年	2.063	141086.6	2.464	141533年	2.788	269.47071
fnl4461	182566年	186205年	1.993	186608.85	2.214	187116年	2.492	250.18104
rl5915	565530年	612142年	8.242	628403.15	11.118	642120年	13.543	7820.3035
pla7397	23260728	24613322	5.815	24926239	7.16	25373211	9.082	192676.28
brd14051	469385年	480038年	2.27	485242.3	3.378	491392年	4.688	3402.7965
d15112	1573084	1607543	2.191	1611675.8	2.453	1627080	3.432	4269.2295
d18512	645238年	659009年	2.134	660992.65	2.442	666349年	3.272	1859.8221
pla33810	66048945	69456797	5.16	69879698	5。8	70333800	6.487	281635.59
pla85900	142382641	148589968	4.36	148751673	4.473	148868721	4.555	68119.888
usa115475	6283142	6424750	2.254	6469988.7	2.974	6504607	3.525	18159.159

(b)


	最优成本	最好的		平均		最糟糕的		方差
	最优成本	成本	误差(%)	成本	误差(%)	成本	误差(%)	方差

att532	27686年	27809年	0.444	27869.35	0.662	27984年	1.076	46.671613
rat783	8806年	8826年	0.227	8860.3	0.617	8901年	1.079	21.555559
pr1002	259045年	261013年	0.76	261966.95	1.128	263477年	1.711	676.60316
rl1889	316536年	353866年	11.793	362309.1	14.461	369220年	16.644	3502.7353
pr2392	378032年	382036年	1.059	385028.6	1.851	390991年	3.428	2673.4602
pcb3038	137694年	138687年	0.721	138978.65	0.933	139684年	1.445	239.93624
fnl4461	182566年	183351年	0.43	183628.35	0.582	183918年	0.741	163.06514
rl5915	565530年	614092年	8.587	625596.05	10.621	640140年	13.193	7676.6391
pla7397	23260728	24153629	3.839	24466610	5.184	24899249	7.044	212019.08
brd14051	469385年	474243年	1.035	477311.15	1.689	482885年	2.876	2821.3266
d15112	1573084	1581463	0.533	1584579	0.731	1589468	1.042	2568.7097
d18512	645238年	649143年	0.605	650639.05	0.837	655523年	1.594	1533.274
pla33810	66048945	66980982	1.411	68025924	2.993	68519773	3.741	411992.49
pla85900	142382641	144593580	1.553	144680542	1.614	144750832	1.663	45980.685
usa115475	6283142	6334053	0.81	6359277.6	1.212	6395483	1.788	19890.006

(c)


	最优成本	最好的		平均		最糟糕的		方差
	最优成本	成本	误差(%)	成本	误差(%)	成本	误差(%)	方差

att532	27686年	27712年	0.094	27765.2	0.286	27897年	0.762	49.990104
rat783	8806年	8806年	0	8818.95	0.147	8833年	0.307	8.9117014
pr1002	259045年	260359年	0.507	261630.45	0.998	265127年	2.348	1434.3942
rl1889	316536年	338432年	6.917	352930.7	11.498	366537年	15.796	6490.877
pr2392	378032年	378870年	0.222	381562.35	0.934	385833年	2.064	1432.2577
pcb3038	137694年	138010年	0.229	138346.35	0.474	138604年	0.661	162.46466
fnl4461	182566年	182872年	0.168	183035年	0.257	183134年	0.311	77.290974
rl5915	565530年	597425年	5.64	616541.85	9.02	629056年	11.233	7045.3808
pla7397	23260728	24090910	3.569	24308120	4.503	24588866	5.71	140266.08
brd14051	469385年	471566年	0.465	474418.05	1.072	479274年	2.107	1767.5788
d15112	1573084	1576636	0.226	1577681.8	0.292	1579279	0.394	669.32031
d18512	645238年	646770年	0.237	647091.95	0.287	648439年	0.496	373.13882
pla33810	66048945	67107824	1.603	67841467	2.714	68576654	3.827	361018.43
pla85900	142382641	144296674	1.344	144528830	1.507	144944342	1.799	220016.09
usa115475	6283142	6283142	0	6325336.4	0.672	6350265	1.068	23558.074

表<一个href="//www.newsama.com/journals/acisc/2014/137928/tab3/" target="_blank">3提出了启发式申请每个实例的运行时信息20分。最低、平均、最大、所需的运行时和标准偏差表中列出。

(一)


	分钟时间	平均时间	最大时间	方差

att532	0.015	0.02185	0.032	0.0077817
rat783	0.015	0.0187	0.031	0.0063254
pr1002	0.031	0.05075	0.078	0.0122039
rl1889	0.062	0.0803	0.109	0.0136617
pr2392	0.094	0.14515	0.203	0.0291047
pcb3038	0.093	0.12325	0.234	0.03034
fnl4461	0.109	0.18565	0.234	0.0349801
rl5915	0.234	0.3494	0.452	0.0488439
pla7397	0.218	0.2965	0.39	0.0448371
brd14051	0.578	0.93515	1.435	0.2534248
d15112	0.748	1.152	1.81	0.2831689
d18512	0.936	1.2106	1.904	0.2183212
pla33810	6.271	8.16745	12.543	2.2148945
pla85900	7.16	8.84205	10.343	0.8042973
usa115475	9.984	13.1663	20.951	2.6126377

(b)


	分钟时间	平均时间	最大时间	方差

att532	0.015	0.0281	0.047	0.0096185
rat783	0.015	0.0234	0.047	0.0095499
pr1002	0.031	0.04525	0.063	0.0101508
rl1889	0.047	0.07495	0.125	0.0156994
pr2392	0.093	0.1171	0.171	0.0227917
pcb3038	0.093	0.1303	0.156	0.0163453
fnl4461	0.156	0.20675	0.266	0.0258739
rl5915	0.188	0.2404	0.344	0.0380808
pla7397	0.172	0.2434	0.281	0.0255021
brd14051	0.733	0.9384	1.56	0.1754526
d15112	0.967	1.1318	1.248	0.0875338
d18512	0.983	1.1941	1.435	0.1246983
pla33810	1.248	1.65835	2.012	0.2394011
pla85900	3.182	3.66755	4.384	0.3271961
usa115475	9.313	11.47305	15.21	1.6807505

(c)


	分钟时间	平均时间	最大时间	方差

att532	0.109	0.1812	0.296	0.0440438
rat783	0.032	0.0687	0.156	0.0293493
pr1002	0.265	0.3553	0.515	0.0719716
rl1889	0.406	0.5171	0.734	0.0887841
pr2392	0.562	0.954	1.669	0.2803806
pcb3038	0.592	0.86495	1.217	0.1730511
fnl4461	0.671	1.0308	1.622	0.2252083
rl5915	0.921	1.2207	1.544	0.1467128
pla7397	1.295	1.94995	2.839	0.3957677
brd14051	3.666	5.322	6.646	0.7302357
d15112	3.541	4.3859	5.335	0.5414395
d18512	4.68	5.70405	7.909	0.711076
pla33810	12.371	16.43415	23.946	2.7950968
pla85900	23.4	28.04495	34.991	3.1503448
usa115475	37.815	46.1041	54.506	3.7665248

在启发式的工具中比较容易,我们引入了平均误差百分比表的列<一个href="//www.newsama.com/journals/acisc/2014/137928/tab2/" target="_blank">2和平均时间列的表<一个href="//www.newsama.com/journals/acisc/2014/137928/tab3/" target="_blank">3由图在图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig5/" target="_blank">5。

(一)

(b)

5.2。性能开发跨界车的工具

呈现交叉性能,我们应该显示交叉的遗传算法精度的影响,收敛速度和能力的交叉产生广泛的各种解决方案。为了实现这些目标,我们必须使用分代GA,因为在稳态遗传算法,生成的大小不变,但在代际遗传算法,生成的总解决方案取决于交叉生成各种解决方案的能力;如果交叉可以生成不同的解决方案,所以延误世代GA收敛;然后总代增加。另一方面,当生成解决方案数高,这表明交叉多样性很高,它可以产生广泛的各种解决方案。我们使用的每一个陈述的代际遗传算法来解决某些情况下跨界车TSPLIB 20倍和表<一个href="//www.newsama.com/journals/acisc/2014/137928/tab4/" target="_blank">4显示了这个实验的结果。


	最优成本	交叉的名字	最好的		平均		最糟糕的		方差
	最优成本	交叉的名字	成本	误差(%)	成本	误差(%)	成本	误差(%)	方差

kroA100	21282年	GSX	21282年	0	21282年	0	21282年	0	0
		PMX	21282年	0	21282年	0	21282年	0	0
		EPMX	21282年	0	21282年	0	21282年	0	0
		牛	21282年	0	21282年	0	21282年	0	0
		VGX	21282年	0	21282年	0	21282年	0	0
		DPX	21282年	0	21282年	0	21282年	0	0
		IGX	21282年	0	21282年	0	21282年	0	0

a280	2579年	GSX	2579年	0	2579年	0	2579年	0	0
		PMX	2579年	0	2579年	0	2579年	0	0
		EPMX	2579年	0	2579年	0	2579年	0	0
		牛	2579年	0	2579年	0	2579年	0	0
		VGX	2579年	0	2579年	0	2579年	0	0
		DPX	2579年	0	2579年	0	2579年	0	0
		IGX	2579年	0	2579年	0	2579年	0	0

lin318	42029年	GSX	42029年	0	42029年	0	42029年	0	0
		PMX	42029年	0	42029年	0	42029年	0	0
		EPMX	42029年	0	42029年	0	42029年	0	0
		牛	42029年	0	42031.7	0.006	42083年	0.128	12.075
		VGX	42029年	0	42029年	0	42029年	0	0
		DPX	42029年	0	42032.1	0.007	42091年	0.148	13.864
		IGX	42029年	0	42029年	0	42029年	0	0

att532	27686年	GSX	27686年	0	27696.55	0.038	27704年	0.065	6.716
		PMX	27686年	0	27699年	0.047	27705年	0.069	7.773
		EPMX	27686年	0	27693.35	0.027	27706年	0.072	8.4
		牛	27686年	0	27696.85	0.039	27706年	0.072	7.638
		VGX	27693年	0.025	27702.1	0.058	27706年	0.072	3.432
		DPX	27686年	0	27697.5	0.042	27847年	0.582	35.881
		IGX	27686年	0	27694.1	0.029	27706年	0.072	8.896

rat783	8806年	GSX	8807年	0.011	8811.7	0.065	8822年	0.182	4.342
		PMX	8806年	0	8810.5	0.051	8826年	0.227	4.763
		EPMX	8807年	0.011	8815.15	0.104	8828年	0.25	5.274
		牛	8806年	0	8810.9	0.056	8818年	0.136	3.626
		VGX	8808年	0.023	8813.8	0.089	8824年	0.204	4.324
		DPX	8806年	0	8810.3	0.049	8815年	0.102	2.867
		IGX	8807年	0.011	8809.25	0.037	8815年	0.102	1.997

pr1002	259045年	GSX	259045年	0	259264.3	0.085	260066年	0.394	281.477
		PMX	259045年	0	259115.8	0.027	260046年	0.386	237.75
		EPMX	259045年	0	259093.5	0.019	259600年	0.214	150.998
		牛	259045年	0	259136.75	0.035	259908年	0.333	233.981
		VGX	259045年	0	259119.35	0.029	259949年	0.349	216.241
		DPX	259045年	0	259134.6	0.035	259588年	0.21	134.744
		IGX	259045年	0	259050.9	0.002	259099年	0.021	15.758

表<一个href="//www.newsama.com/journals/acisc/2014/137928/tab4/" target="_blank">4显示信息最好,最坏的情况下,平均和标准偏差的解决方案成本为每个20每个交叉运行时解决每个实例。图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig6/" target="_blank">6总结了平均误差百分比和STDV列的表<一个href="//www.newsama.com/journals/acisc/2014/137928/tab4/" target="_blank">4。

(一)

(b)

在图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig6/" target="_blank">6它可以很容易地看到IGX有更好的性能在平均误差百分比和标准差。a280,平均误差百分比和kroA100 lin318, rat783,和pr1002 IGX第一最好的排名,只有在att532,第二最小误差百分比。标准差,也IGX最低处理kroA100 a280, lin318 rat783, pr1002。在解决att532, IGX第二最小方差。

表<一个href="//www.newsama.com/journals/acisc/2014/137928/tab5/" target="_blank">5和<一个href="//www.newsama.com/journals/acisc/2014/137928/tab6/" target="_blank">6显示实验结果信息所需的运行时和代总数的20分。这些表列表最好,平均水平,最坏的情况下,所需的运行时和和标准偏差最小值,平均值,最大值,代总数的标准偏差。介绍了平均值和方差两个表的列在图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig7/" target="_blank">7。


		最好的	平均	最糟糕的	方差

kroA100	GSX	1.762	2.065	2.839	0.296
	PMX	1.623	2.586	3.619	0.531
	EPMX	2.137	2.666	3.354	0.368
	牛	1.888	2.406	3.042	0.419
	VGX	2.464	2.992	4.587	0.589
	DPX	1.264	1.755	2.169	0.324
	IGX	2.106	2.665	3.916	0.467

a280	GSX	3.229	3.502	4.118	0.301
	PMX	3.9	4.289	5.038	0.467
	EPMX	3.635	3.928	4.789	0.392
	牛	2.621	3.429	4.056	0.314
	VGX	4.898	5.242	6.349	0.463
	DPX	3.76	4.063	4.82	0.355
	IGX	3.635	3.895	4.773	0.292

lin318	GSX	14.18	18.257	23.338	2.206
	PMX	16.832	23.554	28.922	3.171
	EPMX	15.818	21.304	27.301	3.186
	牛	13.588	18.713	26.894	3.262
	VGX	18.798	22.938	30.031	2.813
	DPX	13.026	17.735	23.743	2.702
	IGX	24.351	28.89	34.617	3.172

att532	GSX	32.962	44.434	60.84	7.568
	PMX	46.301	63.016	95.753	12.268
	EPMX	42.354	56.373	83.382	10.394
	牛	33.056	45.853	69.763	7.809
	VGX	64.786	79.721	101.447	9.776
	DPX	38.891	46.856	64.693	6.75
	IGX	50.731	69.304	99.185	13.961

rat783	GSX	37.456	46.628	56.301	4.659
	PMX	57.97	75.219	100.823	10.811
	EPMX	48.704	64.15	92.259	10.477
	牛	36.457	45.407	58.406	5.957
	VGX	101.26	130.538	173.285	23.599
	DPX	51.355	64.816	81.713	8.804
	IGX	50.84	61.569	92.618	9.933

pr1002	GSX	74.443	108.473	148.091	16.73
	PMX	137.483	164.007	210.804	20.737
	EPMX	121.586	142.91	176.171	16.68
	牛	83.429	120.811	180.774	22.516
	VGX	247.057	316.199	403.245	40.551
	DPX	106.158	127.228	146.437	10.286
	IGX	174.814	238.014	279.912	26.608


		最小值	平均	马克斯	方差

kroA100	GSX	1500年	1725年	2500年	302.403
	PMX	500年	862.5	1250年	206.394
	EPMX	750年	975年	1250年	160.181
	牛	750年	975年	1250年	197.017
	VGX	1500年	1850年	3000年	432.252
	DPX	1000年	1525年	2000年	379.577
	IGX	1500年	1950年	3000年	394.034

a280	GSX	1500年	1625年	2000年	222.131
	PMX	750年	825年	1000年	117.541
	EPMX	750年	800年	1000年	102.598
	牛	500年	775年	1000年	111.803
	VGX	1500年	1575年	2000年	183.174
	DPX	1500年	1600年	2000年	205.196
	IGX	1500年	1550年	2000年	153.897

lin318	GSX	3000年	4025年	5500年	617.188
	PMX	1250年	1887.5	2500年	319.076
	EPMX	1250年	1862.5	2500年	339.068
	牛	1250年	1912.5	3000年	415.767
	VGX	2500年	3250年	4500年	550.12
	DPX	2500年	3575年	5500年	693.485
	IGX	4000年	4875年	6000年	646.346

att532	GSX	3000年	4425年	6500年	892.586
	PMX	1750年	2487.5	3750年	509.612
	EPMX	1750年	2512.5	4250年	620.245
	牛	1500年	2337.5	3750年	501.806
	VGX	4000年	5150年	7000年	812.728
	DPX	3500年	4375年	7500年	1024.374
	IGX	3500年	5250年	8000年	1208.522

rat783	GSX	3500年	4300年	5500年	571.241
	PMX	2000年	2925年	4250年	544.711
	EPMX	2000年	2687.5	4000年	479年
	牛	1750年	2287.5	3000年	337.122
	VGX	5500年	7400年	10000年	1391.705
	DPX	3500年	4825年	6500年	892.586
	IGX	3500年	4500年	7000年	842.927

pr1002	GSX	5000年	8950年	14500年	2199.88
	PMX	3750年	4650年	6000年	640.723
	EPMX	3750年	4575年	6000年	702.907
	牛	3500年	4887.5	7750年	1119.431
	VGX	11000年	13750年	19000年	1956.77
	DPX	5500年	7175年	9000年	831.533
	IGX	10000年	14400年	17500年	1923.538

(一)

(b)

5.3。近半年的性能分析

比较发达无形体病和其他先进的方法不是我们的目的,但我们想展示,可以设计和开发新的迷因算法通过我们的目标的工具。因此,为了实现这一目标我们比较无形体病和最新的windows版本的LKH在100000秒内解决pla85900 TSPLIB中最大的问题。图<一个href="//www.newsama.com/journals/acisc/2014/137928/fig8/" target="_blank">8显示了这种竞争的结果。这个图表表明,近半年产生旅游比LKH 100000 (s)及其突出明显。

6。结论

在本文中,我们目前的突出我们的TSP编程工具,基于LKH实现。事实上,这些工具在三个面向对象语言源代码:c++, c#和JAVA。这些工具可以帮助工程师、研究人员和那些处理TSP更容易编写和开发他们的TSP应用程序的任意编程语言。在这里,我们试图展示我们的工具的性能实验。为了显示他们的适用性,我们设计了一种混合算法是有效和击败LKH-2软件在处理最大TSPLIB实例。

附录

一个。

看算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg7/" target="_blank">7。

1 <节点列表> ActiveNodes; / /来实现”不”t-look比特”
2 空白路(巡演之旅)
3 {
4 为每个节点X
5 加上X ActiveNodes列表;
6 虽然(活跃节点存在)
7 {
8 节点N = ActiveNodes删除并返回第一个节点;
9 如果(inner-LK(旅游,X) < = 0)
10 不活跃的X;
11 }
12 }
1 int inner-LK(旅游参观,节点x)
2 {
3 Y 邻居(X);
4 int partial-gain = \| XY \|;
5 打破XY旅游;
6 添加Y ActiveNodes列表;
7 为每个Z 候选人的X
8 {
9 添加YZ参观;
10 添加Z ActiveNodes列表;
11 partial-gain = partial-gain + \| YZ \|;
12 如果旅行是可行的(旅游结束由一个优势是可能的)
13 {
14 如果(partial-gain−最后添加边缘成本> 0然后)
15 {
16 近距离旅行;
17 返回partial-gain−最后添加边缘成本;
18 }
19 其他的
20. {
21 int g = inner-LK(旅游,x);
22 如果(g < 0)
23 {
24 打破YZ;/ /测试另一个。
25 }
26 其他的
27 {
28 返回g;
29日 }
30. }
31日 }
32 }
33 添加XY参观;/ /打破XY是不成功的。
(34)删除Y从ActiveNodes列表;
(35)返回0;
(36)}

B。

看算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg8/" target="_blank">8和<一个href="//www.newsama.com/journals/acisc/2014/137928/alg9/" target="_blank">9。

1 而(满足一些条件)
2 {
3 (我= 0;我<创- - - - - -大小;我+ +)
4 {
5 父亲和母亲来自人口;
6 孩子(s)<- - - - - -交叉(父亲,母亲);
7 LS可能应用在儿童之旅(s);
8 增加孩子的人口;
9 }
10 归一化人口规模通过删除一些解决方案;
11 }

1 f或(i = 0;我< gen-size;我+ +)
2 {
3 父亲和母亲来自人口;
4 孩子(s)<- - - - - -交叉(父亲、母亲);
5 LS可能应用在儿童之旅(s);
6 指数<- - - - - -get_inddex ();
7 人口(指数)<- - - - - -孩子;
9 }

C。

看算法<一个href="//www.newsama.com/journals/acisc/2014/137928/alg10/" target="_blank">10。

1 创建随机旅游人口;
/ /第一层是GA和增加旅游”质量。它使用IGX交叉(<一个href="#B5">5]。
2 使用稳态GA通过启发式交叉提高人口;
3 这种人口根据订购成本上升;
4 之旅到目前为止最人口 0 ;
/ /第二个层是近半年,并使用GSX交叉,双电桥作为其突变和路
LS。
5 (i = 1;我< = gen-size;我+ +)
6 {
7 之旅孩子;
8 int指数;
9 如果(rand_01() <交换率)
10 {
11 从人口线性选择指数=;
12 父亲人口(指数);
13 从人口线性选择指数=;
14 妈妈。人口(指数);
15 交叉(父亲、母亲、孩子);
16 提高儿童的路;
17 }
18 其他的
19 {
20. 孩子从人口线性选择;
21 通过双桥变异的孩子;
22 提高儿童的路;
23 }
24 这种人口根据订购成本上升;
25 如果(我% = = 0)
26 更新候选人组根据边缘人口密度;
(27)如果(迄今最佳成本>人口 0 成本)
(28)到目前为止最成本人口 0 ;
(29日)}
(30.)报告迄今最佳;