文摘

遗传算法(GA)是一种metaheuristic用于解决组合优化问题。受进化生物学的启发,GA采用选择、交叉和变异算子有效地遍历搜索空间的解决方案。提出了自然启发微调线粒体DNA的交叉算子使用尚未开发的思想(mtDNA)。mtDNA DNA是一个很小的子集。的完全继承其有别于竞争对手的女性,而其他的DNA是遗传同样来自父母。这个独特的特征mtDNA可以成为一个有效的机制来识别成员具有相似基因和限制它们之间的交叉。它可以降低稀释率的多样性和导致延迟收敛。此外,我们著名的岛规模模型,遗传算法的实例在哪里独立运行和人口成员定期交换,大陆模型。在这个模型中,多个web服务执行与每个web服务运行一个岛屿模型。我们应用mtDNA解决旅行商问题的概念和训练神经网络函数逼近。 Our implementation tests show that leveraging these new concepts of mtDNA and Continental Model results in relative improvement of the optimization quality of GA.

1。介绍

遗传算法是一种来自大自然的灵感metaheuristic用于解决优化和搜索问题,否则需要很长时间来解决使用蛮力的方法。GA提供我们遍历解搜索空间智能的方法,提出一个最优解附近显著短时间。遗传算法使用超出计算机科学、工程、数学、经济学等领域,生物信息学,生命科学和制造业。遗传算法非常适合组合优化问题。一个这样的问题,我们可以部署GA的旅行商问题(TSP)。

遗传算法的目标是尽可能接近最优的解决方案。自解搜索空间是如此巨大,达到这一目标的主要困难是收敛到局部最小值之前探索整个搜索空间的全局最小点。这是我们可以利用的概念mtDNA帮助添加一些顺序随机搜索最优解附近。

2。遗传算法

GA的概念提出了荷兰在他1975年的书《[1]。此后,GA一直是一个活跃的研究领域,已经有大量的出版物。TSP是其中的一个问题,遗传算法已成功使用。

如图1,有两个主要功能:人口选择和交叉。选择算法描述了方法选择为下一代创造孩子的父母。有四个策略所示图:精英,轮盘赌,排名,和旅游。精英策略给予优先选择最佳的成员从当前人口本身(2]。在轮盘赌选择,成员被映射到一个轮盘赌占据空间,正比于他们的健康和成员随机选择从它避免重复3]。排名选择方法类似于轮盘赌,而是基于健身比例代表制的馅饼,成员都是根据他们的健身(排名按升序2]。在比赛中选择,人口成员选择竞争和选择最好的父母从池中成员(2]。这个过程一直持续到所有成员已被确认。

交叉混合的过程是亲本种群的基因表示成员创造一个更好的健康的内涵产生的后代。有不同类型的跨运营商基于旅游表示。提出的部分映射交叉(PMX),戈德堡和林格尔4),是一个受欢迎的运营商。这一段一个父母的基因映射到其他父母和其他交换产生的后代(5]。

突变增加了附加价值GA通过引入随机变化可以帮助克服局部最小值在搜索探索。实现突变的一个方法是随机选择一小部分人口成员和交换单元与相邻的基因。

解决方案可以提高利用岛模型。这里的人口是破碎成更小的组或岛屿和GA上分别运行在单独的线程允许我们利用多个处理器甚至多个分布式服务器来解决一个大问题。这不仅加快了处理时间,而且提高解决方案的质量在大多数情况下,因为它消除了抽样偏差,如果任何出现在初始种群3]在一个线程中运行。此外,少数群体成员从不同的岛屿可以交换利用的多样性,防止过早收敛。

另一种方法来提高解决方案的质量进行更彻底的本地搜索。我们可以通过使用来实现这一点- opt算法,是一个数值,通常2或3。在2-Opt方法中,两条边从旅游中删除和重新连接的其他方法可以保留一个有效之旅(7]。2-Opt的优势在于它是快速和有效的。当与标准遗传算法结合使用运营商,2-Opt的的概率陷入局部最小值也减轻。每一个执行2-Opt需要操作,城市的数量和吗是成员的数量。因此,2-Opt不应该在每一个迭代而是运行(例如,100)迭代执行时间限制。

2.1。使用遗传算法解决TSP

在对称TSP问题,一个推销员拜访的城市数量,并返回到原来的(第一个)城市的最短路线(5]。TSP是一个典型的np难问题,最坏的情况下运行时增加superpolynomially或详尽地为解决这一问题的城市数量的增加呈指数级增长。

当使用遗传算法解决TSP,每个城市都用一个独特的号码。每个解决方案都是随机序列(或群体成员的GA)独特的nonrepeating数字,代表一个可能的路线或旅游。每个人口成员与一个独特的基因组成代表解决遗传算法。同样每个路线代表了TSP的解决方案。遗传算法开始时随机产生一组初始的人口成员,经过若干次迭代的选择和交叉功能,希望在后续迭代中提高解决方案或一代。TSP,我们生成随机集的路线,每一个由向量序列的城市。选择方法选择对线路或人口成员被允许成为输入转换函数。交叉函数然后交流独特的数字(城市)每一对路线生成的两个孩子(新的人口成员)为每一对父母人口。孩子们,自己代表解决方案(路线)TSP,然后取代父母的新路线(人口成员)。这种选择和交叉迭代过程可以继续,直到我们不得到任何下一代更好的结果。

提供额外增强突变和岛模型。模仿突变GA,一小部分路线解决方案是随机挑选的顺序交换,交换两个相邻的城市。突变有助于保持多样性(9]。在岛的模型中,独立运营的多个气体和少量的人口成员(TSP)路线后这些岛屿之间交换特定数量的迭代(代)。岛模型还允许我们利用所有可用的计算资源(丰富)并行运行多个气体(3]。这两种机制已被证明解决方案的积极影响的结果。

2.2。使用遗传算法训练人工神经网络

人工神经网络(ann)是受生物神经系统的学习系统。人工神经网络模拟大脑的解剖和功能。人工神经网络是由相互连接的节点处理单元/(类似于神经元)中组织层,如图2。每个节点的传入连接权重分配给他们和输入信号的求和的权重通过节点和处理结果满足后续节点下一层[s]。

在图2输入层中,每个节点连接中的所有节点随后隐藏层和隐层中的所有节点连接到输出层节点。每个传入连接的节点是由(例如,th输入节点)和每个连接也有重量,,与之相关的10]。

以下方程给出的数学表示、处理的输出节点是偏见,是一个非线性函数,如乙状结肠函数(10]。

安节点功能。考虑 (见[10])。

安图2是一个前馈神经网络,节点之间的连接并没有形成一个反馈循环。有不同的方法来训练神经网络。在训练阶段的价值权重和偏见进行了优化来解决一个特定问题。通常使用梯度下降法调整权重基于所需的输出之间的差异和当前11]。遗传算法还可以用来训练神经网络。可以恰当地选择和健身的标准应用于训练神经网络。函数近似的领域之一是神经网络可以有效地使用。

3所示。相关工作

已经有大量的研究来提高遗传算法解决TSP运营商。前面提到的几个选择策略的发展,也就是说,精英,轮盘赌,排名,和比赛,是这一努力的见证。这些策略已经实现和运行对TSPLIB基准(8由不同的人员)。每一个选择运营商都有自己的特点,好处和缺点。Razali和格拉提神6]本文得出结论,基于秩选择策略取得了更好的结果,但需要更多的计算时间,而旅游方法更快的为小尺寸的问题(6]。选择方法仅代表TSP问题的一个方面。另一个主要方面是交叉功能,导致算法的成功的重要原因。大约有11个交叉运营商审核通过的票数et al。5在他们的论文中。其中大部分是基于特定模式的混合和父母之间交换的信息,例如,顺序交叉(OXI),介绍了几种均匀长度减少点父母和后代产生的路径和几个家长完整和同化的子路径的孩子(12]。另一个交叉算子,即遗传边重组交叉,增加了更有意义的逻辑在其运作通过假设旅游很重要的边缘和试图保护他们的后代13]。

有文献发表的限制性的交叉。加兰等。14)提出了一个交配策略,探索之间的平衡(选择标准)和剥削(健康标准)通过开发一个参数交配指数控制的勘探程度(或多样性)的父母基于问题的硬度。策略等乱伦的预防(15防止类似的个体之间的交配。选型交配是另一种策略用于改善遗传算法的结果。奥乔亚et al。16]演示变异率和选型交配选择的关系;即较高的突变率工作与选型交配而变异率低和dissortative交配带来更好的健康。这些策略背后的理念是基于相似的后代个体的原则不会导致更高的适应性。基于相似的基因引入控制交配并产生更好的结果,但他们也计算成本高昂,漫长的染色体相比。

本文提出了进一步优化的想法限制交配补充标准的交叉算子。这种想法是基于这样一个前提:它不会有利于选择相同的后代父母(或关闭血统),新父母互相交叉。事实上,它可能是不利于保持多样性和探索更大的搜索空间。作为另一个详尽的比较确定的基因遗传多样性之间的父母,我们提出一个算法计算倾斜。我们利用mtDNA提高遗传算法的概念。

4所示。提出想法和它的实现

4.1。线粒体DNA (mtDNA)

人类有23对染色体,一份每一对分别继承了从每个父6]。这些染色体的DNA被称为核DNA (17]。此外,人类也有mtDNA [17),包括只有1%的总DNA (18),从而为更少的基因编码。虽然微不足道的数量级的核DNA的贡献相比,遗传性状(基因),mtDNA独特的特点在继承可以发挥重要作用在指导寻找最优解。23对染色体中的DNA序列是继承了同样来自父母在繁殖的后代,而序列mtDNA只继承了从孕产妇(18]。这使我们能够跟踪人口成员具有类似通过母系血统遗传性状和共同继承。多样性是防止过早收敛的关键和实现最优解附近。跨界车与DNA相近相似的人口成员之间不会产生结果比前一代在大多数情况下。本文的想法是创建一个数据结构来标记和追踪mtDNA在每个人口成员之间的交叉和限制人口成员mtDNA相似。mtDNA广泛用于进化遗传学和人口研究[19),它的概念可能是有益的GA搜索探索。

4.2。使用mtDNA遗传算法解决TSP和扩展架构

遗传算法的主要目标是帮助我们更好的解决方案在每次迭代和防止解决方案探索过早收敛到局部最小值。解决后目标的主要方式是引入适量的多样性的父母。

大部分的交叉运营商往往是非常完善和颗粒在城市或节点信息水平,似乎忽略了大局。交叉的GA进行若干次迭代,收敛的风险增加,在某些情况下,跨界车之间相同的人口成员的后代不会产生结果,比上一代更好,因为他们的父母会有相似的遗传信息。用更少的遗传方差的父母,我们不能指望后代更好的或不同的结果。不言而喻,母猪种子遗传变异进化和新后代(20.]。追踪遗传相似性的一个方法是通过跟踪家庭血统。和最有效的方法来跟踪继承在现实世界中是通过mtDNA [21]。

mtDNA的概念(线粒体DNA)在本文中实现控制交叉函数来阻止人口成员同mtDNA繁殖一代又一代。避免这种情况的过度延伸的后果,这要求是只在跨界车的比例决定。mtDNA被定义为一个单独的类属性的人口成员。由于mtDNA继承仅仅来自母本,它不改变,因为它是传递给后代。这个属性是用来指导和控制跨界车。这是一个高水平的概述mtDNA算法和伪代码。

所有的四个选择方法(旅游,精英,轮盘赌,排名)时使用前面描述的实现。在交叉基因转移到孩子,1/4与3/4旅游减少了父母传给孩子。其余被循环顺序从第二个父母,跳过任何城市,已经由第一个家长,从而确保每个城市的孩子表示没有重复。在实现中,除了利用mtDNA各种选择方法,岛模型,2-Opt,使用多个服务器和分布式处理的(大陆模型),也被利用。

图3提供了一个高层次的遗传算法实现的工作流。定制的GA版本运行在每个服务器上的四个线程。

岛模型实现了多核处理器的服务器并行运行多个线程。每个线程跑自己的GA版本。定期每迭代次数/代的每个线程运行遗传算法,随机选择人口的少数成员之间交换的线程。这个过程不仅增加了更多的计算资源和改进遗传算法的执行时间,还增加了多样性和减少了初始抽样偏差。

2-Opt实施通过选择人口成员迄今为止最好的健身GA特定线程的执行每一个迭代/代。所选的成员然后进行局部优化。两个链接/边最好的成员也被替换详尽检查如果它提高了解决方案。

岛与分布式处理模型进一步扩展,在几个服务器上执行上述实现使用Web服务(面向服务的体系结构(SOA))。我们恰当地将其命名为大陆模型。人口成员被随机之间交换这些独立岛模型GA实现在不同的服务器上运行后固定数量的迭代实现多样性和减少过早收敛的可能性。

实现对已知的TSP实例运行(dantzig42, eil51, rd100 ch150, kroB200)从TSPLIB8]。数值的名义基准表示城市的数量;例如,eil51 51个城市。mtDNA实现遗传算法的结果比较反对的结果实现Razali和Geraghty [6和已知的最佳解决方案。

4.3。在人工神经网络mtDNA GA

我们用遗传算法来训练神经网络函数逼近。1个节点的多层前馈神经网络,输入层,26日在第一隐层节点,26第二隐层节点和1个节点到输出层,被选中。神经网络的遗传算法实现类似于GA实现茶匙。在城市的数量(TSP)权重的值是随机初始化在解集和跨越另一组神经网络的初始权值。但与TSP,权重的值不需要独特的解集内。

mtDNA介绍了GA在这里就像在TSP。由此产生的跨界车的孩子被母亲的标记mtDNA相同的属性中定义的迭代算法1和那些同样mtDNA之间跨界车了。mtDNA后重置价值迭代,以确保跨界车并不太受限制。我们使用mtDNA实现遗传算法训练神经网络的函数逼近。

下面是实现的细节:(1)人口规模= 200。(2)选择率= 20。(3)变异率= 4。(4)mtDNA重置每迭代,。(5)输入层节点如下:1(),26日(隐层1),26日(隐层2),和1(输出层)。遗传算法被用来训练安以下功能有无mtDNA逻辑(图4):功能一:。函数B:。Schewefel函数的函数C: 1 d版。函数D:。

5。结果

5.1。遗传算法在旅行商问题

TSPLIB列在表1表明基准的名字。第二和第三列代表了从已知的最佳解决方案和健身Razali et al。6纸,分别。最后一列列出了GA的健身价值实现与mtDNA一起2-Opt和大陆模型。TSP,适应度函数是距离推销员通过所有的城市,回到第一个。解决方案是基于健身价值评估;也就是说,价值越低越好。

图5展示了本文的mtDNA GA实现之间的比较和已知的解决方案(8TSP的基准。mtDNA GA实现了更好的基准上相对较少数量的城市,也就是说,dantzig42(42个城市),eil51(51个城市),和eil76(76个城市)。

数据6,7,8提供TSPLIB mtDNA GA的结果实现较高的基准(100、150和200年)的城市。虽然mtDNA GA的结果在这些基准背后略高于已知的最佳解决方案,他们明显比结果当mtDNA逻辑和比例(多节点)架构是不习惯。因此,这两个概念引入增值解决TSP的持续降低健身解决方案,即使在TSPLIB基准与超过99个城市。

表2提供最好的路线/旅游,结果收到的GA与mtDNA运行各自的基准。结果从表1表明mtDNA收益率结果比Razali和格拉提神6)和出版解决方案发布在TSPLIB (8]dantzig42和eil51基准。当mtDNA和大陆模型被用来与其他已知的运营商和算法,它导致解决方案是比出版解决方案eil76 rd100非常接近已知的最佳解决方案,ch150, kroB200基准。

5.2。在人工神经网络遗传算法

安训练分别使用mtDNA实现遗传算法和遗传算法本身。权重设置后,安被用来近似(图四个功能4)和方差计算。GA的mtDNA实现的结果列在表中3比结果GA单独使用时在所有四个功能。表3显示的结果几个(100、200、300、500、1000和5000年)迭代/执行使用的训练方法。数据9- - - - - -12代表的数据表3以图形的形式。

mtDNA结合遗传算法训练的结果安始终优于GA-only安给定训练四个函数近似。

6。结论

我们提出了两个重要的想法mtDNA和大陆模型在改进遗传算法的优化质量。mtDNA逻辑介绍了新奇的想法,灵感来自自然就像很多优化的算法,例如遗传算法,群体智慧,蚁群优化和神经网络。这样自然启发算法和系统的概念mtDNA不是很复杂,但可以有助于提高metaheuristics的质量。保持多样性的关键是防止过早收敛到局部最小值。可以利用mtDNA跟踪多样性的特点和限制之间的交叉的父母同样的遗传性状,从而提供更好的健身价值的后代。mtDNA概念表达和实现本文模拟的自然秩序是一个既定事实,生物多样性有利于进化和生产更具有适应能力的后代。由于更快的硬件、并行/分布式处理和算法,TSP基准与较少的城市已经解决了最优运行时的不足。更大的基准/问题仍然提供机会来改善算法。mtDNA的实现中小型TSP基准本文支持的贡献相对提高解决方案的质量。这个实现的目标不仅是一定要战胜基准算法的运行记录,已经最优解决,而且还旨在提供一个概念证明的技术,可以利用,从而获得更好的结果。 Likewise with大陆模型,我们提高我们的结果与更大的探索一个额外的随机性层提供的搜索空间和独立的实现交流岛天然气。大陆模型繁殖岛的好处模型通过注入更多的多样性,减少负面影响的最初固有偏见的个别竖井的GA实现不同的系统。此外,我们能够使用的概念mtDNA GA超出TSP提高神经网络学习的结果。因此,它可以从本文的结果得出结论,大陆模型和整合mtDNA控制交叉建设性修改有助于进一步优化遗传算法的收益率相对更好的结果。

7所示。未来的工作

在GA扩展mtDNA的有效性普遍接受的技术,它可以实现和测试在其他组合优化问题(人口)更大的数据集。其他新方法的分布式和并行计算的算法也可以用于接近最优解。mtDNA指导交叉功能的概念可以进一步细化和根深蒂固的GA算法来实现更好的结果。mtDNA的价值可以相对于核DNA序列之间的方差(市路线序列)的人口成员和成员之间我们可以限制跨界车mtDNA相近除了成员mtDNA相同。我们可以把mtDNA的概念与其他交叉算子和进一步探索优化策略。此外,而不是彻底预防人口成员之间的跨界车mtDNA相同,我们可以使用特殊的运营商等跨界车最大化多样性。进一步验证mtDNA概念的使用,我们可以用更多的实验扩展测试范围和其他优化问题。

相互竞争的利益

作者宣称没有利益冲突。