文化的基本路径篇1

关键字:无线传感器网络,蚁群优化,信息素,路由算法

中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)01-34-03

ANovelRoutingAlgorithmBasedonAntColonyoptimizationforWirelessSensorNetworks

HAOXiao-qing

(SchoolofComputerScience,ChengduUniversityofElectronicScienceandTechnology,Chengdu610054,China)

Abstract:Inthispaper,weintroduceanovelroutingalgorithmwhichisbasedonAntColonySystem.Theaimofthisnovelalgorithmistosolvetheproblemofenergyandcongestioncontrolonwirelesssensornetworkroutingprocess.Thisalgorithmisabletoachievebetterloadbalanceandprolongthenetworklifetime.Inthisnewalgorithmwecombinethepheromonereleasedbymulti-antcoloniesandresidualenergy.Wealsointroducethecompetitionmechanismamongmulti-antcoloniestoavoidthesimplexconvergence.Thenewalgorithmcontrolsthenetworktrafficcongestioneffectivelyandbalancestheenergyconsumptionforsensornetworks.Simulationresultsdemonstratethatthisalgorithmhasbetterperformanceonloadbalancecomparingwithfundamentalantcolonyalgorithm.

Keywords:wirelesssensornetworks;antcolonysystem;pheromone;routingalgorithm

无线传感器网络[1]是近几年新兴的信息获取平台,具有快速展开、抗毁性强等特点,有着广阔的应用前景。路由算法的作用是初始化并维护包含路径信息的路由表。路由算法可分为单播、多播以及广播路由算法,它应该具有简单性、可扩展性、节能性和鲁棒性。另外,针对节点故障和网络拓扑变化还应该具有自重构性。

蚁群算法是一种群体智能算法,最初用于解决组合优化问题中的旅行商问题、二次分配等问题,并取得了较好的效果。蚁群算法具有分布式并行计算、自组织、正反馈的特点,且有较强的鲁棒性。由于无线传感器网络自身的特点,传统网络的路由协议不能很好地适用于无线传感器网络。许多学者都在集中研究开发基于蚁群算法的无线传感器网络路由算法[2-4]。我们在本文中提出一种改进的基于蚁群优化的路由算法,该算法避免了基本蚁群算法中的单一收敛,在控制网络拥塞和平衡能量消耗上也达到了很好的效果,延长了网络生命周期,实现无线传感器网络的路由优化目标。

1基于蚁群优化的路由原理

1.1蚁群算法原理

蚁群算法[5]是一种启发式算法,蚂蚁借助他们在通过了的路径上留下的信息素彼此通信。每个蚂蚁可以嗅到其它蚂蚁留下的信息素并通过信息素引导自己的移动方向,但信息素会随著时间的流逝而挥发。因此,路径的长度和经过这条道路径的蚂蚁个数会影响信息素的浓度。另一方面,信息素的浓度将引导蚁群中其他蚂蚁的移动方向,如果有很多蚂蚁经过这条道路径,那么其它的蚂蚁选择这条路径的概率将会很高。这在蚁群系统中构成了一种信息素正向反馈机制。

近几年,生物启发算法已被广泛地应用到网络路由问题上,基于蚁群优化的路由算法对最大化网络生命周期有显著贡献。基于蚁群算法的路由算法一般分为两大类。一是Ant-Net算法,即通过正向蚂蚁和逆向蚂蚁的协作来取得最优路由,正向蚂蚁收集节点信息而由逆向蚂蚁根据这些信息来更新路由表。另外一种是蚁群控制算法,它以特殊的概率选择和更新路径。该算法只有一种蚂蚁,从源点出发到终点。当蚂蚁抵达终点时更新路由表。两种算法在网络变化中都具有较强的自适应性,并能迅速的建立最优路径。但是当他们更新路由表时有两个缺点:一个是节点瘫痪,这是由于网络延迟,节点能量消耗过快引起的。另一个是因广播通信中更多的蚂蚁需要协同工作而消耗过多的能量。

为了达到结果最优和适应无线传感网络,在文献[6]中,提出了均衡节点的能量消耗的蚁群算法路由协议,他们利用蚂蚁算法建立最优路由路径。文献[7]中作者提出了基于蚁群系统的网络能量平衡路由算法。文献[8]实现了多蚁群路由算法。

1.2基本蚁群路由算法

我们将无线传感器网络的拓扑结构模拟成一个无向图G(N,A),N是节点集,A是路径集。在初始化过程中,图中所有的路径都被给定一个信息素值。当搜索活动开始,蚂蚁会随机的在候选的节点集中选择一个并开始搜寻过程中。在这个搜寻过程中,蚂蚁倾向于选择具有较高浓度的信息素路径的下一个节点。当所有的蚂蚁都完成了他们的搜寻过程,更新全局信息素。这意味着所有路径上信息素会蒸发掉一部分,每一个蚂蚁根据能量消耗参数更新它通过的路径上的信息素。如果能量消耗参数低,这条路径上的信息素减少的就会很少。随后蚂蚁会选择一个新的节点重新开始搜索过程。

我们假设一些蚂蚁在节点n,蚂蚁k根据概率Pk(n,d)访问下一个节点d。Pk(n,d)公式如下:

在公式(1)中,Ω代表信息素大小,Γ代表从源点到目的地的距离的倒数,Xk(n)表示蚂蚁还没有访问过的节点集,ε是调整能量消耗和信息素之间关系的一个常数。全局信息素的更新根据公式(2):

ΔΩk(n,d)由公式(3)表示:

这里,Ek是蚂蚁k完成路由路径搜索的能量消耗。

从上面的描述我们可以知道,所有的蚂蚁通过具有最高信息素的路径到达目的地。因此,如果一条路径可以引导蚂蚁到达目的地,这条路会涌现大量的蚂蚁,最后我们会把这个路径作为热路径。在无线传感器网络中,这种热路径并不一定是一个用来转发数据包的最佳选择。因为在这个路径上数据包可能会拥塞、甚至导致部分网络崩溃的结果。而且热路径会缩短网络的生命周期。

2基于蚁群优化的无线传感网络路由算法

为了达到平衡负载这个目的,我们不得不改进基本的蚁群算法。新算法能让数据包通过不同的路由路径来转发,收敛速度更快,避免了单一收敛。在新方法中,我们将标记不同的数据包流使他们通过不同的通道转发。为此我们引进多蚁群之间的竞争机制,结合节点能量的变化来达到负载均衡的目标。因为每一个蚁群都有他们自己的信息素,我们将每个蚁群标记不同的信息素以作为他们的蚁群划分。一旦不同的信息素出现在同一转发路径上时,所有的信息素会被迅速蒸发掉。这意味着,不同的蚁群的信息素相互抑制。因此,这就导致了这个转发路径上蚂蚁的数量将会越来越少。

我们定义m个蚂蚁的蚁群为A1,A2,…,Am-1,Am,每个蚂蚁的信息素为Ω1,Ω2,…,Ωm-1,Ωm。蚂蚁Ai停留在节点n,根据概率Pik(n,d),蚂蚁Ai将访问下一个节点d。

这里Ω代表每条路径上信息素的量,Γ代表从源点到目的地的距离的倒数,Xik(n)表示蚂群Ai中蚂蚁k没有访问过的节点集,ε是调整能量消耗和信息素之间关系的一个常数,值设置为2。φi,d是蚁群Ai中蚂蚁k的信息素能量操作因子:

Ed表示蚁群Ai中蚂蚁k将要访问的下一个节点的能量消耗,Uk(n)表示蚁群Ai中蚂蚁k将要访问的下一个节点集合。

公式(4)中,?谆j是当蚁群Ai和其他蚁群有相同推进方向时候的抑制概率因子:

公式(6)表明在搜索传输路径过程中,如果两个蚁群Ai和Aj在同一路径上,这两个蚁群会相互抑制,最后导致这个路径上的两种蚁群的蚂蚁数目都减少。然而,这种数据流平衡不能使网络快速的稳定。在任何一个蚁群系统中,当选择一个路径的概率发生了变化,选择另一个相关路径作为下一个路径的概率也将更新。所以更新概率应该要满足下式:

在公式(7)中,我们以节点n作为源节点,并且所有的候选转发节点都有他们自己的转发概率,概率和为1。因此,在调整一个转发节点概率后,所有转发节点的概率都需要重新计算,也就是要动态的调整概率。

从公式(4)中可以看到,当所有的蚁群相互竞争最优路径时,他们都服从来自于转发节点的能量消耗最小的约束条件。也就是为了达到当蚁群算法收敛于最优解的同时平衡节点间的能量消耗的目标。与此同时,我们的算法将避免所有的蚁群收敛于同一个全局最优解,更避免了通信拥塞并延长了网络生命周期。全局信息素的更新公式(8):

这里的Eik表示当蚂蚁k完成路由路径搜寻后的能量消耗。在公式(8)中,λi表示改进后的信息素挥发因子,这个因子能由公式(10)计算:

εij是信息素抑制参数。在我们的算法中,我们使用信息素抑制参数来计算在两个蚁群竞争过程中的信息素的挥发程度和在竞争中蚂蚁减少的数量。

3实验与分析

我们把改进的算法和基本蚁群算法做了实验比较。实验结果统计图如下:

图1基本蚁群算法中蚂蚁的多样性图2改进的蚁群算法中蚂蚁的多样性图3节点D的能量消耗情况

图1是模拟基本蚁群算法的实验结果,显示随着时间的推移不同路径上的蚂蚁的数目。结论:在路径BD上,蚂蚁的数量急剧增加。然而,路径BC和BE上的蚂蚁数目的远低于BD上的。图2显示的是改进算法的实验结果,可以看到在最优路径BD上,蚂蚁的数量得到了控制并相对于基本蚁群算法有明显的减少。另一方面,在路径BC和BE上,蚂蚁的数量也显著增加,这可以达到平衡网络负载这个目标。我们还对节点D在改进的算法和基本蚁群算法关于能源消耗上做了比较。从图3中可以看到采用基本蚁群算法时,节点D的能量消耗显著;相反,改进的算法在负载平衡上很有效,节点D则保留了更多的能量。

新算法结合了多蚁群的信息素释放机制和节能策略,还引进多蚁群之间的竞争机制以避免算法的单一收敛,解决了无线传感器网络路由过程中节点能量消耗和拥塞控制问题,能够达到更好的负载平衡能力,并延长了网络生命周期。

4结束语

WSN具有广阔的应用前景,但是由于节点能量,处理能力,储存空间以及带宽等的限制,它的大规模应用还是存在许多需要克服的问题,设计一个满足需要的高效的路由算法是目前面临的一个主要问题。在本文中,我们提出一种新的基于蚁群优化的无线传网络的路由算法。新算法对基本蚁群算法进行了改进。引入多蚁群之间的竞争机制来解决局部最优解的问题和避免早熟现象。同时,结合节点的能量消耗问题,实现负载平衡。算法对延长网络的生命周期具有很明显的效果。

参考文献:

[1]李晓维,徐勇军,任丰原,等.无线传感器网络技术[M].北京:北京理工大学出版社,2007.

[2]M.DorigoandL.Gambardella,“Antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem,”IEEETrans.OnEvolutionaryComputation,Vol.1,pp.53-66,Apr.1997.

[3]G.Chen,T.D.Guo,W.G.YangandT.Zhao,“Animprovedantbasedroutingprotocolinwirelesssensornetworks,”Proc.ofInternationalConferenceonCollaborativeComputing:Networking.ApplicationsandWorksharing,pp.1-7.Nov.2006.

[4]L.Juan.S.ChenandZ.Chao,“AntsystembasedanycastRoutinginwirelesssensornetworks,”Proc.oftheInternationalConferenceonWirelessCommunications,NetworkingandMobileComputing(WiCom2007),pp.2420-2423,Sept2007.

[5]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.

[6]杨靖,熊伟丽,徐保国.无线传感器网络中基于蚁群算法的路由算法[J].计算机工程,2009,35(6):4-6.

文化的基本路径篇2

关键词:动态二进制翻译;动态优化;热路径;隐马尔可夫模型

algorithmforhotpathspredictionusinghiddenmarkovmodel

liukui?1,lishi-ying?1,lirui??1,2,liren-fa?1

(1.schoolofcomputer&communication,hunanuniversity,changsha410082,china;2.schoolofcomputer,nationaluniversityofdefensetechnology,changsha410073,china)

abstract:methodofhotpaths-baseddynamicoptimizationiseffectiveforimprovingtheoperationalefficiencyofthesoftwareindynamicbinarytranslator.thisstudyfocusedonhowtoidentifythehotpathsbyusingtheexistinglimitedamountof?previousoperationalinformationofbasicblocks,andtoenhancethehitrateoftheprediction,withnoincreaseofcomputationalcostatthesametime.therehadbeenfewmethodsbasedonmodelsamongexsitinghotpathspredictionalgorithms,whichneedcomplicatedimplementation.thispaperproposedanimprovedhotpathspredictionalgorithmbasedonhiddenmarkovmodel.sincethesequenceofstatetransitionwasunique,thisalgorithmwaseasytoimplement,andcouldimprovethehitrateofhotpathsaswellastheperformanceofthedynamicbinarytranslator.theexperimentalresultsverifiedtheefficiencyofouralgorithm.

keywords:dynamicbinarytranslation;dynamicoptimization;hotpath;hiddenmarkovmodel(hmm)

0引言

动态二进制翻译技术是一种即时编译技术,它在程序的运行过程中将针对源体系结构编译生成的二进制代码(源机器码)动态翻译为可以在目的体系结构上运行的代码(目标码),此过程对用户来说是透明的。整个动态翻译过程分为两个阶段,即产生本地代码的翻译阶段和执行阶段。在代码的执行阶段,动态优化器会进行一定的优化。大多数的程序将大部分的时间花费在很小的一部分代码段上,识别并优化这一部分代码将从本质上改善软件的整体性能。

频繁执行的代码块称之为热块。代码块就是一个控制转移(如一个分支、调用或跳转指令)结束的指令序列,代码块也称为基本块[1]。当一个代码块变热时,其周围的一些代码块也将变热,由这些热块组成的执行序列称之为热路径。一个热路径就是一个指令序列。热路径是研究人员在设计dynamo[2]系统时提出来的概念,热路径的优化技术是目前动态二进制翻译器主要采用的技术。常见的热路径识别方法主要有分别基于基本块、边和路径的识别方法。这三种方法的预测准确度递增,但是复杂度也随之增加,尤其是基于路径的预测,随着程序的运行,负载急剧增长反而会降低软件的运行效率[3,4]。

热路径的产生一定与循环执行有关,因此预测主要针对循环进行,只有热路径优化带来的收益大于开销时才能从整体上提高系统的效率。因此,在热路径的优化过程中既要尽量提高热路径的预测准确率,同时又要控制预测过程的开销,并且优化越早启动越好。已有的热路径预测算法出于计算复杂度的考虑都没有基于模型进行预测,如spanningtree算法[5]、bittracing算法[3]、net算法[3]、编码算法[6],大多只是计算路径的执行次数,并取执行次数最多的作为热路径,研究的重点是如何更方便、更高效地记录热路径以及更新路径计数器的方法,尤其是当候选热路径的执行次数近似或者执行均衡时,更是很难作出合理的选择。本文基于隐马尔可夫模型(hmm),提出了改进的热路径预测算法,该算法实现简单,在预测延迟不明显增加的情况下,提高了热路径的命中率,从而减少了热路径在cache中的替入替出消耗,一定程度上提升了软件在动态二进制翻译器上的运行效率。

1总体思路

本文的总体思想是以程序的基本块为单位,将程序的流程构造成一个满足隐马尔可夫模型(hmm)[7]的有向图,并以图中自上至下的每层为一个状态,每层中的一个代码块可视为一个观察值,热路径即为模型的一个观察序列,程序的流转变为状态的转移,同时,任何时刻每个状态的转移只与前一个状态相关,而与时间以及其他状态无关。很显然,此时基于块的热路径预测过程满足马尔可夫性,是一个马尔可夫过程,即马尔可夫链;而且一个状态中有多个观察值,通过扩展后(详见1.2节),一个观察序列不能直接确定状态的转移序列,因此该过程又是一个隐马尔可夫过程。依据hmm的估算方法,一旦循环程序段的入口代码块的计数器counter达到阈值trigger时,就启动基于该模型的热路径预测,并选取候选热路径candihp中估算概率最大的路径作为热路径。总体思路如图1所示。

1.1隐马可夫模型介绍

如果一个过程的“将来”仅依赖于“现在”而不依赖“过去”,则此过程具有马尔可夫性,或称此过程为马尔可夫过程。设s是一个由有限个状态组成的集合s={1,2,3,…,n-1,n},随机序列x在t和s时刻所在的状态分别为q?t、q?s(q?t,q?s∈s)。若有p(q?t=j|qt-1=i,qt-2=k,…)=p(q?t=j|qt-1=i),或者p(q?t=j|qt-1=i)=p(q?s=j|qs-1=i),则随机序列x构成一个一阶马尔可夫链。令aij=p(q?t=j|qt-1=i)(1≤i,j≤n),则对于所有的i,j有下面的关系成立:?nj=1aij=1(aij≥0)。

一阶马尔可夫模型可以描述为一个二元组λ(s,a)。s是状态的集合,而a是所有状态转移概率aij组成的一个n行n列的矩阵,其中每一个元素aij表示从状态i转移到j的概率,可表示为a=[aij],aij=p(qt+1=j|q?t=i)(1≤i,j≤n)。一阶马尔可夫模型的状态与观察序列一一对应,因此根据观察序列能直接推断出状态转移序列。隐马尔可夫模型是对马尔可夫模型的一种扩展,观察序列不能确定状态的转移。隐马尔可夫模型λ可以表示为一个五元组λ=(s,v,a,b,π)。s和a与一阶马尔可夫模型一样分别表示一组状态的集合和状态转移矩阵;v是一组输出符号组成的集合,v={v?1,v?2,v?3,…,v?m};b是输出符号的概率分布,b={b?j(v?k)},其中b?j(v?k)表示在状态j时输出符号v?k的概率,b?j(k)=p(v?k|j)(1≤k≤m,1≤j≤n);π是初始状态概率分布,π={π?i},π?i=p(q?1=i)(1≤i≤n),表示初始时刻选择某个状态i时的概率。

hmm的状态是不确定或不可见的,只有通过观察序列的随机过程才能表现出来。观察到的观察序列与状态不是一一对应的,而是通过一组概率分布相联系。hmm是一个双重随机过程(图2),有两个组成部分:马尔可夫链和一般随机过程。前者描述状态的转移,用转移概率描述;后者描述状态与观察序列间的关系,用观察值概率描述。

基于模型λ,若给定状态转移序列q={q?1,q?2,q?3,…,q?t},则产生观察序列o={o?1,o?2,o?3,…,o?t}的概率p(o|λ)为[7]

p(o|λ)=?qp(o,q|λ)=

?q??1,q??2,…,q??tπq??1bq??1(o?1)aq??1q??2bq??2(o?2),…,aq??t-1q??tbq??t(o?t)

1.2基于程序的图解及扩展

动态二进制翻译器的热路径优化针对的是频繁执行的代码块序列,主要是程序中循环执行的代码段。图3是一种典型的循环代码段,其中包括结构化程序中常见的顺序、选择和循环三种结构。图4为该程序段基于基本块的图解。由图4可以发现,程序中任何时刻基本块的转移仅与前一基本块有关,而与其他基本块以及时间无关。图中基本块旁边的数字表示在启动热路径预测时代码块的执行次数,由程序运行时的profile获取。?

通过对图4的扩展,可使其满足隐马尔可夫性。首先将循环中的内循环合并成一个块,本文以代码块较少、循环次数较少的常见内循环为例进行介绍,当然,当内循环较复杂时可多次调用本算法。将图中的每个块视为hmm中一个输出或者是观察值,也即模型λ中集合v的元素,v={a,b,c,d,e,f,g,h,i,j,k}。并使得自顶向下处于同一层次的代码块属于一个状态,如图5所示,也即模型λ中的状态集合s,其中s={q?1,q?2,q?3,q?4,q?5}。通过对图5的再次扩展,可使其转换成以代码块为单位的图6,也就是使得程序段的每条执行路径在每个状态q?i(1≤i≤5)都有输出。

基于模型λ的概率估算只在循环入口代码块a的执行次数达到优化触发器的值trigger时才启动预测,本例为了方便计算设trigger=100。候选热块candibb是基本块的计数器count大于阈值basecount的块,一般basecount=trigger×40%[8],可表示为candibb={x|x∈bbset•count(x)>basecount}。bbset指循环内的所有基本块,此处即为集合v。由候选热块组成的执行路径称为候选热路径,candihp={a,x,y|x,y∈candibb•ax∧xy∧ya}。

至此,热路径的预测即可通过模型λ进行,图6中的路径adhjk表示hmm的一个输出,也即观察序列o?i(1≤i≤m),m为循环内路径总数,并且是一条候选热路径。热路径的预测就是基于模型λ预测其中输出序列o?i出现概率p(o?i|λ)最大的序列过程。

2基于hmm的建模

经过分析,此时热路径的预测变成如下问题的求解过程。

已知:a)模型λ=(s,v,a,b,π);b)候选热路径为o?i=(o?1,o?2,…,o?i,…,o?5)。其中o?i∈v。

求解:候选热路径中p(o?i|λ)值最大的路径,也即求解o?i中出现概率最大的观察序列。

其中:状态集合s={1,2,3,4,5},q?i(1≤i≤5)表示某一个状态;观察值集合为v={a,b,c,d,e,f,g,h,i,j,k}。状态转移矩阵a如下所示,经过扩展后,程序的执行可视为自上至下的执行过程,因此只存在(q?1,q?2,q?3,q?4,q?5)的状态转移序列,其他出现的概率均为0。

a=01000

00100

00010

00001

10000

b表示各代码块的执行概率分布,b={b?j(v?k)}。其中:?b?j(v?k)=count/trigger,如bq??2(b)=40/100,即为q?2状态下出现b的概率;π是初始状态概率分布,π={π?i}且π?i=p(q?1=i),本处很显然π?1=1,π?1=0(2≤i≤5)。

3算法及复杂度分析

1)给定λ以及状态转移序列q=(q?1,q?2,q?3,…,q?t),则观察序列o?i=(o?1,o?2,o?3,…,o?t)的出现概率为p(o?i|q,q,λ)=bq??1(o?1)bq??2(o?2)bq??3(o?3),…,bq??t(o?t);给定λ,则状态转移序列?q=(q?1,q?2,q?3,…,q?t)的出现概率为p(q|λ)=πq??1aq??1q??2aq??2q??3,…,aq?t-1q??t。因此o?i和q的联合概率p(o?i,q|λ)=p(o?i|q,λ)[7]。

2)给定λ,若考虑所有的状态转移序列,则p(o?i|λ)=?qp(o,q|λ)=?qp(o|q,λ)p(q|λ)。

展开后得到

p(o?i|λ)=?q?1,q?2,…,q??tπq??1

bq??1(o?1)aq??1q??2bq??2(o?2)aq??2q??3,aq?t-1q??tbq??t(o?t)

由于只存在q=(q?1,q?2,q?3,…,q?t)转移序列,其他情况的状态转移计算结果为0,无须纳入计算,即π?1=1,π?i=0(2≤?i≤5)。此时计算变成:

p(o?i|λ)=bq??1(o?1)aq??1q??2bq??2(o?2)aq??2q??3…aq?t-1q??tbq??t(o?t)

整理后即为

p(o?i|λ)=bq??1(o?1)bq??2(o?2)…bq??t(o?t)aq??1q??2aq??2q??3…aq?t-1q??t

则计算p(o?i|λ)共需要进行2(t-1)次乘法,整个算法需要计算n×2(t-1)次乘法(n为候选热路径数)。

本例对于每条候选热路径只需计算8次乘法运算,候选热路径数3条,则总的计算次数为24次。通过计算获得候选热路径的最大可能执行概率,选取该候选热路径作为热路径。

在本例中

p(o?i|λ)=bq??1(o?1)aq??1q??2bq??2(o?2)aq??2q??3bq??3(o?3)aq??3q??4bq??4(o?4)a?q??4q??5bq??5(o??5)

候选热路径有{abeii,abejk,adhjk}。

通过计算可以得到p(abeii|λ)=100/100×50/100×50/100×20/100×20/100=0.01;同理可计算得p(abejk|λ)=0.06;p(adhjk|λ)=0.0448(由于b?j(v?k)的基数都是trigger,计算时可直接使用基本块的执行次数count进行计算,本处为了更直观,仍使用比值计算)。

p(abejk|λ)>p(adhjk|λ)>p(abeii|λ),那么最热的热路径为abejk。

若采用传统的热路径执行次数判断法,则c{abeii}=20;c{abejk}=30;c{adhjk}=35。

c{adhjk}>c{abejk}>c{abeii},因为路径adhjk的执行次数最多,所以最热的路径为adhjk。

由以上复杂度分析可知,尽管思路完全不同,基于隐马尔可夫模型的计算,其计算过程并不复杂,而且实现非常简单。

4实验结果与分析

为了评价热路径预测算法的有效性,下面分别给出了预测命中率、噪声比、预测延迟的定义。假设启动预测后,候选热路径p?i的执行次数为f(p?i)(1≤i≤n),则所有候选热路径的执行次数约为?ni=1f(p?i)+n×trigger,热路径的预测命中率为

hitrate(p)=f(p)/(?ni=1f(p?i)+n×trigger)

其中:p表示预测出的热路径。

噪声比是指将非热路径作为热路径的概率,可表示为

noise=(?ni=1f(p?i)-f(p))/(?ni=1f(p?i)+n×trigger)

其中:n为候选热路径数。

预测延迟predelay是指启动热路径预测前所有路径执行的次数与程序段总的执行次数的比值,可表示为

perdelay=?mi=1f(p?i(t))/t

其中:f(p?i(t))表示t时刻启动预测前路径i的执行次数;m表示路径总数;t是程序段总的执行次数。预测延迟越大,则热路径的丢失机会成本[3]越高,同时运行时的负载也将越高。

预测的重点就是如何提高命中率hitrate(p),并保持低的预测延迟和噪声比noise。本算法的实现在skyeye[9]上进行。skyeye是国内一款开源的虚拟机,目标是模拟常见的嵌入式计算机系统,可在skyeye上运行linux、μclinux等多种嵌入式操作系统和各种系统软件。skyeye的动态二进制翻译模块(dbct)对运行在其上的操作系统进行加速,该模块的实现基于qemu。

下面是在skyeye的linux系统上运行系统性能测试工具nbenchbenchmarksuite的结果,并针对上面介绍的三个指标进行分析。表1给出了benchmark程序中的绝对热路径数?(a-hotpaths)与相对热路径数(r-hotpaths)占路径总数比例的情况。其中绝对热路径是指在循环内执行次数远远多于其他分支的路径;相对热路径是指循环内平均执行的路径。大多数情况下循环内绝对热路径要比相对热路径多,可以发现其中assignment和huffman程序中相对热路径的数目较多。同时,从表1可以了解到huffman程序绝对路径与相对路径数相似,assignment程序的相对热路径比绝对热路径稍多,idea程序两者相差较大。这三个程序具有一定的代表性,因此下面就采用这三个程序对本文所提出的算法性能进行分析。

表1路径情况

benchmarkpathsa-hotpaths/%r-hotpaths/%

numericsort7002.4291.571

stringsort7502.8001.600

bitfield7132.1041.543

fpemulation8271.6930.967

fourier6972.2961.578

assignment7622.8873.281

idea7632.7521.180

huffman7392.0301.894

图7给出了所提出算法下huffman、idea和assignment程序的预测延迟与命中率的关系图。由图可以看出,由于huffman的路径数较少,在盲测时的命中率稍高;同时由于idea的绝对热路径与相对热路径占用比例相差较大,idea的命中率总体呈上升趋势。

图8给出了上述三个程序的噪声比与预测延迟的关系图。由图可以看出,与图7相对应,idea的噪声比明显要小;同时由于assignment的相对路径较多,整体噪声比较大。结合图7和8可以发现,若在预测延迟的20%处启动预测,将在?hitrate与noise之间达到一个较好的平衡。

预测命中率的计算相对比较复杂,并且预测的目的是通过提高命中率来减少热路径重复翻译产生的开销,从而提高程序的运行效率,减少程序的运行时间,因此本文直接针对程序的运行时间进行分析,运行时间越少自然命中率越高,算法更优越。图9给出了所提出的算法与基于路径数预测方法以及本地的运行时间比较。从图中可以发现,利用基于hmm模型的热路径算法程序运行时间有不同程度的减少,其中相对热路径较多的assignment等程序减少明显。由于显示的需要,本文以代码块较少的简单程序作为实例进行分析。如果程序更加复杂,如大型系统程序,该算法的效果将更加显著。当然,如果直接在本地运行,速度差别仍然较大。以上实验结果和分析表明,本算法在保持预测延迟不明显增加的情况下可以提高热路径的命中率,从而提升软件的总体运行效率。

5结束语

热路径是程序在某一个时间频繁执行的代码块的集合,识别并优化热路径能显著改善程序在动态二进制翻译器上的运行性能。热路径预测的目标是如何利用有限的已有运行信息预测出未来将要频繁执行的路径,预测算法要尽量简单,容易实现,并且只有预测带来的效益大于开销时,预测才有意义。本文运用隐马尔可夫模型提出了改进的基于块的热路径预测算法,该算法的优越性主要体现在热路径的预测基于预测模型,尤其当候选热路径执行次数近似时,热路径的选择更具有效性。该算法实现简单,提高了热路径的命中率,降低了热路径在cache中替入替出的消耗,从而能够提高软件在虚拟机中的运行速率。下一步工作将针对热路径的阶段变化情况进行研究。

参考文献:

[1]

scottk,kumarn.overheadreductiontechniquesforsoftwaredynamictranslation[c]//procofthe18thinternationalparallelanddistributedprocessingsymposium.2004.

[2]ebciogluk.dynamicbinarytranslationandoptimization[j].ieeetransoncomputers,2001,50(6):529-548.

[3]duesterwalde,balav.softwareprofilingforhotpathprediction:lessismore[c|//procofthe9thinternationalconferenceonarchitecturalsupportforprogramminglanguagesandoperatingsystems.newyork:acmpress,2000:202-211.

[4]ballt,matagap,sagiym.edgeprofilingversuspathprofiling:theshowdown[c]//procofthe25thacmsigplan-sigactsymposiumonprinciplesofprogramminglanguages.newyork:acmpress,1998:134-148.

[5]ballt,larusjr.efficientpathprofiling[c]//procofthe29thannualacm/ieeeinternationalsymposiumonmicroarchitecture.washingtondc:ieeecomputersociety,1996:46-57.

[6]史辉辉,管海兵,梁阿磊.动态二进制翻译中热路径优化的软件实现[j].计算机工程,2007,33(23):78-83.

[7]rabinerlr.atutorialonhiddenmarkovmodelsandselectedapplicationsinspeechrecognition[j].proceedingsofieee,1989,77(2):257-286.

文化的基本路径篇3

关键词：车辆路径问题；启发式算法；优化

中图分类号：U116.2文献标识码：A

Abstract：Vehicleroutingproblemisthecoreprobleminlogisticsmanagementandintheorganizationandoptimizationoftransportation，andisaclassiccombinatorialoptimizationprobleminoperationsresearch.ThisarticlesystematicallysummarizedthecommonclassificationsandthebasicmodelofVRPproblems.Andthroughreferringtoscholars'researchsituation，summarizedthecommonlyusedandefficientheuristicalgorithmsofsolvingVRPproblemsandthepresentsituationofthecorrespondingresearch.Finally，summarizedtheproblemsintheresearchofVRPproblemsanddiscussedthefutureresearchandthesolvingmethodsforVRPproblems.

Keywords：vehicleroutingproblem；heuristicalgorithm；optimization

0引言

随着科技的进步和电子商务的飞速发展，作为国民经济中一个重要行业的物流产业已成为拉动国家经济发展与提高居民生活水平的重要动力源泉，而物流行业中的车辆路径问题（VehicleRoutingProblem，VRP）是制约物流行业发展的一个关键要素，其研究也受到人们的广泛关注。车辆路径问题是物流管理与运输组织优化中的核心问题之一，是指在满足一定的约束条件（如时间限制、车载容量限制、交通限制等）下，通过对一系列收货点与发货点客户合理安排行车路线，在客户的需求得到满足的前提下，达到配送车辆最少、配送时间最短、配送成本最低、配送路程最短等目标。该问题由Dantzig和Ramser[1]于1959年在优化亚特兰大炼油厂的运输路径问题时首次提出，现已成为运筹学中一类经典的组合优化问题，是典型的NP-难题。

企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效减少车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。VRP作为物流系统优化环节中关键的一环，其研究成果已经应用到快递和报纸配送连锁商店线路优化以及城市绿化车线路优化等社会实际问题中，因而车辆路径问题的优化研究具有很好的现实意义。

1车辆路径问题的分类与基本模型

VRP的构成要素通常包括车辆、客户点、货物、配送中心（车场）、道路网络、目标函数和约束条件等，根据侧重点的不同，VRP可以分为不同的类型。根据运输车辆载货状况分类可分为非满载车辆路径问题和满载车辆路径问题；根据任务特征可分为仅装货、仅卸货和装卸混合的车辆路径问题；根据优化目标的数量可分为单目标车辆路径问题和多目标车辆路径问题；根据配送车辆是否相同可分为同型车辆路径问题和异型车辆路径问题；根据客户对货物接收与发送有无时间窗约束可分为不带时间窗的车辆路径问题和带时间窗的车辆路径问题；根据客户需求是否可拆分可分为需求可拆分车辆路径问题和需求不可拆分车辆路径问题；根据客户是否优先可分为优先约束车辆路径问题和无优先约束车辆路径问题；根据配送与取货完成后车辆是否需要返回出发点可分为开放式车辆路径问题和闭合式车辆路径问题；还可以将上述两个或更多约束条件结合起来，构成一些更复杂的车辆路径问题。

由于VRP的约束条件不同引起了其分类多种多样，而不同类型的VRP其模型构造及求解算法有很大差别。VRP的一般数学模型为：

在上述模型中，式（1）表示目标函数，式（2）表示约束条件。其他VRP模型大致都是在此模型的基础上根据约束条件完善形成的。

2VRP的求解算法与研究现状

VRP的求解方法，基本上可分为精确算法和启发式算法两大类。由于精确算法的计算难度与计算量随着客户点的增多呈指数级增加，在实际中应用范围有限，而启发式算法则具有全局搜索能力强、求解效率高的特点，求出的解也具有较好的参考性，因此，目前大部分研究者们主要把精力集中在如何构造高质量的启发式算法上，本文也主要讨论一些近年来研究比较多的启发式优化算法。针对VRP问题目前已提出了大量的启发式算法，其中研究较多的主要包括以下算法：

2.1遗传算法（GeneticAlgorithm，GA）

GA是一种通过模拟生物进化过程来搜索最优解的方法，该方法通过对群体进行选择、交叉和变异等操作，产生代表新的解集的种群，根据个体适应度大小选择个体，通过迭代逐步使群体进化到近似最优解状态。但是该算法具有搜索速度慢、易早熟、总体可行解质量不高等缺点。

采用遗传算法研究VRP问题的研究现状包括：蒋波[2]设计了遗传算法求解以配送总成本最小为目标函数和带有惩罚函数的VRPTW模型；赵辰[3]基于遗传算法求解了从生产中心到仓库之间的路径优化问题，设计了配送路径优化决策；张群和颜瑞[4]建立了多配送中心、多车型车辆路径问题混合模型，并采用一种新的模糊遗传算法求解该问题。

2.2模拟退火算法（SimulatedAnnealing，SA）

SA同禁忌搜索算法一样，也属于局部搜素算法，但是模拟退火算法是模仿金属加工中退火的过程，通过一个温度函数作为目标函数，使其趋于最小值，是一种基于概率的算法。

采用模拟退火算法研究VRP问题的研究现状包括：郎茂祥[5]研究了装卸混合车辆路径问题，并构造了模拟退火算法求解该问题；穆东等[6]提出了一种并行模拟退火算法，并将该算法的应用领域扩展到其他车辆路径问题和组合优化问题；魏江宁和夏唐斌[7]以模拟退火算法为基础，研究了单个集散点与多个客户之间的运输问题；Mirabi和FatemiGhomi等[8]提出了一种基于模拟退火思想的三步启发式算法求解最小化配送时间的多配送中心VRP模型。

2.3蚁群算法（AntColonyOptimization，ACO）

蚁群算法是人们受蚂蚁可以快速找到食物的自然现象启发提出的。蚁群算法所建立的机制，主要包括蚂蚁的记忆、蚂蚁利用信息素进行交互通信及蚂蚁的集群活动三个方面。单个蚂蚁缺乏智能，但整个蚁群则表现为一种有效的智能行为。通过这种群体智能行为建立的路径选择机制可使蚁群算法的搜索向最优解靠近。

采用蚁群算法研究VRP问题的研究现状包括：马建华等[9]研究了基于动态规划方法的多车场最快完成车辆路径问题的变异蚁群算法；辛颖[10]通过对MMAS蚁群算法进行了三种策略的改造，指出蚁群算法可以找到相对较好的解和很强的鲁棒性；陈迎欣[11]针对蚁群算法的缺点，分别对信息素更新策略、启发因子进行改进，引入搜索热区机制，有效解决车辆路径优化问题；段征宇等[12]通过最小成本的最邻近法生成蚁群算法和局部搜索操作设计了一种求解TDVRP问题的改进蚁群算法。

2.4粒子群算法（ParticleSwarmOptimization，PSO）

PSO算法是通过对鸟群觅食行为的研究而得出的一种群体并行优化算法，它从随机解出发，通过迭代寻找最优解。蚁群算法具有容易实现、收敛速度快、精度高等优点，在多种优化问题上均取得了较好的效果。但是由于PSO算法是通过粒子之间的相互作用来寻找最优解，缺乏像遗传算法那样的变异机制，因而PSO算法容易陷入局部最优。

采用粒子群算法研究VRP问题的研究现状包括：马炫等[13]提出了一种基于粒子交换原理的整数粒子更新方法求解有时间窗约束的车辆路径问题；吴耀华和张念志[14]以处理集货或送货非满载带时间窗车辆路径优化问题为背景，提出了带自调节机制的局部近邻粒子群算法解决VRP问题。

2.5蝙蝠算法（BatAlgorithm，BA）

蝙蝠算法是剑桥大学学者Yang[15]于2010年提出的一种新型群智能进化算法，模拟自然界中蝙蝠通过超声波搜索、捕食猎物的生物学特性，是一种基于种群的随机寻优算法。截至目前，蝙蝠算法主要用于求解连续域的函数优化问题，只有少数学者将其用来求解离散型问题，具有很好的研究前景。

采用蝙蝠算法研究VRP问题的研究现状包括：马祥丽等[16]将蝙蝠算法应用于求解VRP问题，在蝙蝠速度更新公式中引入了惯性权重，对基本蝙蝠算法进行了改进，克服了基本蝙蝠算法的不足之处；马祥丽等[16]针对VRPTW问题的具体特性重新定义了蝙蝠算法的操作算子，设计了求解VRPTW问题的蝙蝠算法，并采用罚函数的方式对目标函数进行了简化求解。

3总结与展望

车辆路径问题由于约束条件的不同其分类多种多样，数学模型与求解算法也层出不穷。本文总结了近几年一些相关学者对VRP问题的研究和求解算法，通过较为系统地总结VRP问题，本文总结出以下当前研究存在的问题和今后可能的研究方向：

（1）研究目标太过理想化。目前学者研究VRP的研究过于注重成本最小和路径最短，大部分是单目标优化，而在实际应用中，配送的驾驶员也可能会因许多原因耽误计划的行程，顾客的需求各异甚至冲突，顾客满意度与企业成本最小化目标之间存在效益悖反的矛盾。今后的研究可以将成本、路程、驾驶员休息、顾客满意度等多个目标联合起来进行研究，并可以通过线性加权的方式进行综合求解。

（2）单个约束的VRP问题由于研究时间较长，现在已经研究的较为成熟，而且其应用局限也比较大，应该考虑将多个约束条件结合起来，建立符合实际的多约束条件的车辆路径问题，更好地解决企业的配送优化。

（3）虽然启发式算法具有全局搜索能力强，运算方便等优点，但是也存在着局部搜索能力差、收敛时间过长、易陷于局部最优等问题。使用单一的群智能算法不是求解VRP的最有效算法，将两种和多种群智能算法结合起来研究车辆路径问题，取长补短，是今后应该考虑的问题；同时，应考虑寻求更多的智能优化算法来求解VRP问题。

参考文献：

[1]GB.Dantzig，JK.Ramser.Thetruckdispatchingproblem[J].ManagementScience，1959，6（1）：80-91.

[2]蒋波.基于遗传算法的带时间窗车辆路径优化问题研究[D].北京：北京交通大学（硕士学位论文），2010.

[3]赵辰.基于遗传算法的车辆路径优化问题研究[D].天津：天津大学（硕士学位论文），2012.

[4]张群，颜瑞.基于改进遗传算法的混合车辆路径问题[J].中国管理科学，2012，20（2）：121-128.

[5]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报，2005，20（5）：485-491.

[6]穆东，王超，王胜春，等.基于并行模拟退火算法求解时间依懒型车辆路径问题[J].计算机集成制造系统，2015，21（6）：1626

-1636.

[7]魏江宁，夏唐斌.基于混合模拟退火算法的多阶段库存路径问题研究[J].工业工程与管理，2015，20（3）：1-8.

[8]MMirabi，SMTFGhomi，FJolai.Efficentstochastichybridheuristicsforthemulti-depotvehicleroutingproblem[J].RoboticsandComputer-IntegratedManufacturing，2010，26（6）：564-569.

[9]马建华，房勇，袁杰.多车场多车型最快完成车辆路径问题的变异蚁群算法[J].系统工程理论与实践，2011，31（8）：1508

-1516.

[10]辛颖.基于蚁群算法的车辆路径规划问题求解研究[D].长春：吉林大学（硕士学位论文），2015.

[11]陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究，2012，29（6）：2031-2034.

[12]段征宇，杨东援，王上.时间依赖型车辆路径问题的一种改进蚁群算法[J].控制理论与应用，2010，27（11）：1557-1563.

[13]马炫，彭M，刘庆.求解带时间窗车辆路径问题的改进粒子群算法[J].计算机工程与应用，2009，45（27）：200-204.

[14]吴耀华，张念志.带时间窗车辆路径问题的改进粒子群算法研究[J].计算机工程与应用，2010，46（15）：230-235.

[15]YangXS.Anewmetaheuristicbat-inspiredalgorithm[C]//Nature-InspiredCoopreativeStrategiesforOptimization，2010：65

文化的基本路径篇4

1基本概念

1.1xml数据模型和xml数据模式

一个xml文档树是一个有序标签树(如果考虑元素之间的应用关系则以xml文档的基本结构为图)，每个节点与一个元素或值(文本)相对应，边表示元素和子元素(或值)之间的嵌套关系。xml文档的数据模式是一个有向图，它为xml数据提供完整性约束。

1.2xml数据的编码方法

到目前为止处理路径表达式查询有两种方法：一种是基于树遍历的方法，另一种不遍历文档树就可以快速决定节点之间结构关系的方法，元素之间结构关系的确定主要依赖于有效的xml节点编码方法。

1.2.1基于区域的编码方案

目前，最常用的编码方法是区域编码方法，最先使用区域编码确定树节点之间的结构关系的是dietz。它给每个节点赋予一个(pre,post)编码，其中，pre是节点的前序遍历值，post是节点的后序遍历值，对于任意两个不同的节点x和y，x是y的一个祖先当且仅当x.pre

文献。给每个节点赋予一个(start,end)编码，一个节点的start和end值是该元素的开始和结尾的绝对物理或逻辑位移，如果一个节点的编码所覆盖的区域被另一个节点的编码所覆盖的区域完全包含，则这个节点是另一个节点的后代节点。为适用于多个文档查询和父子关系的确定，还可以将元素的编码扩展为(d，cid,start,end,levd)，docid是文档的标识符，level是节点在文档树中的层数。文献提出一种类似于区域编码方案——扩展的前序和后代范围编码，其目是的为了支持数据的动态插入和删除，每个节点被赋予一个(order，size)，order是节点的前序遍历序号。size表示节点所覆盖的范围，它可以是任意一个大于该节点后代节点总数的整数值。

除了区域编码以外还有另外一种相对区域编码方，每个节点被赋予一个到其父节点的相对位移。这种编码可以转换成区域编码，其主要缺点是为了确定节点的绝对位置查询代价沿着查询路径从祖先节点到被查询节点逐步增加。

1.2.2基于前缀的编码方法

不同于区域编码方法，基于前缀的编码方式保存路径信息。在这种编码方法中祖先后代关系和前缀子串的包含关系相对应。文献提出了k-ary编码，该方法通过增加虚节点把文档看成一个完全k分树，根据树的层次遍历顺序给树中的节点编码，在这种编码方法中节点的编码带有文档的结构信息。类似于k-ary编码，文献提出了一种特殊的pbitree编码，这种编码方案是通过增加虚拟节点将文档树嵌入到一个完全二叉树中。这种编码的优点是可以利用完全二叉树的优良特性来计算节点间的结构关系。pbitree中的虚拟节点起着—个占位符的作用，这样有利于数据的动态更新，同时它们对查询性能也有一定的影响。

1.3xml数据索引

为了提高查询的性能，许多专家和学者都致力于索引的研究与开发。目前提出的索引有两种：一种是基于结构连接的索引；另一种是基于路径的索引。基于结构连接的索引m首先将文档树中的所有节点以的形式进行分解后存储在多张表中。这样，当处理查询//e1/e2/……/en时，对包含ei(i=-1，…，m)的表按次序要进行多次连接操作得到查询结果。基于路径的索引则是以文档树为基本数据结构，按照路径将树中的节点进行拆分、合并等操作，索引结构仍然是一个树，使用这种索引处理查询//el/e2/……/en时，基本上要遍历整个索引树才能得到结果。文献提出了一种自适应的路径索引结构，这种索引利用频繁使用的路径来改善查询性能，并且这种索引可以随着查询工作量的不同而动态改变，从而有效地缩小了索引文件。

2路径表达式的查询处理方式

2.1树遍历方法

最朴素的路径访问方法是树遍历的方法：一般采用自顶向下的方式遍历文档树，使用该方法进行查询时需要遍历某元素通往叶子节点的所有可能路径。为了减少树遍历的代价引入自底向上的方法，首先查找符合谓词条件的所有原子节点，然后再寻找它们的父节点。这种方法一般情况下比较简单、耗时较少。但对于符合谓词条件的节点数目很大而符合路径表达式的路径很少时，这种遍历方式的代价可能会高于自顶向下方式。一种折中的方法是同时按自顶向下和自底向上两种方法进行遍历，最后在路径的某个中间位置汇合，从而得到查询结果。当路径上某节点的扇人度(在文档中的)很大而符合谓词条件的原子节点很少时，该方法可以达到最优。在这种方法中优化路径表达式查询的一个中心思想是设法缩小查询范围。使得不需要遍历整个树就可以获得符合条件的查询结果。

2.2路径分解法

这一种方法是目前用的比较多的，它的基本思路是将复杂的查询路径分解成简单路径，简单路径可以是由一个元素、一个谓词条件或一个元素加一个谓词条件，还可以是由两个元素组成的路径。首先计算这些简单路径表达式，再将每个简单路径表达式的计算结果连接起来。其本质确定节点间的结构关系(祖先后代或父子关系)，因此这种操作叫结构连接。像关系数据库中的连接运算一样，结构连接操作的代价非常昂贵，结构连接又是查询处理的核心操作，因此在这种查询处理模式中查询优化的关键开发高效的结构连接算法，同时结构连接的顺序也极大地影响着结构连接运算的性能。

3路径表达查询优化的一般方法

3.1路径表达式的重写优化

路径表达式重写优化的基本思想将复杂的、高代价的查询路径表达式转换为简单的、低代价的等价路径表达式。查询重写技术的一般特征可以概括如下：①重写优化发生在查询解析之后查询计划生成之前；②重写优化是将一个查询转换为一个等价的查询；③要使用启发式方法选择查询转换方法，被选择的查询转换方法能改善大多数查询的执行性能；④查询重写的依据通常是查询本身获得信息、完整性约束或数据模式，而不考虑数据以及数据的存储方式和数据的统计信息。

3.1.1根据结构约束删除冗余

最先研究路径表达式最小化问题是和，文献中只对不包括祖先后代边“//”的简单路径表达式进行最小化，而文献研究了不包含*的路径表达式的最小化问题。其基本思想是将查询中的路径表示为查询模式树，根据给定的结构约束，逐步查询模式树中冗余路径节点或冗余谓词。

文献对包含全部操作符{/,//[],*}的路径表达式的最小化进行了研究，算法的基本思想是递归地从原模式树中查找最小子模式并连接它们，证明了这是一个np完全问题，同时，它还指出：在对路径表达式分支个数和形状加以一定限制的情况下。表达式最小化算法的复杂度可以达到多项式级。很显然，在实际查询中用户不可能将查询限制成一种特定形式的路径表达式。

3.1.2删除路径表达式中的固有冗余

文献中提出了两种优化策略：缩短路径策略和补路径策略。缩短路径法是试图用等价相对路径取代绝对路径，缩短路径表达式本身，从而降低查询的代价。这种方法利用元素的唯一访问路径、唯一父元素、关键祖先等几个概念把绝对路径表达式转换为相对路径表达式，这样路径表达式的查询匹配就不再从根元素开始，从而缩短了路径表达式查询时间。如假定某查询的绝对路径表达式eicle2c2e3…cnen，如果uap(e2)=c1e2，则可以用c2e3…cnen代替eicle2c2e3…cnen。这里的关键问题确定唯一访问路径、唯一父元素和关键祖先。

在补路径法中定义了互补路径，相对于某元素的互补路径是等价的，这样就可以用补路径替换原查询。其基本思想是把用户书写的复杂的、代价高的查询路径表达式用一些简单的、查询代价低的互补路径表达式来替代。这种策略的目的是减少连接次数和连接结果集的大小，因此怎样确定查询路径的互补路径并进行代价估算成为其关键问题。

3.1.3删除非冗余的通配符步

当在某条路径中一个元素名未知或无关紧要时通常采用通配符。进行路径匹配时，通配符需要和当前节点的所有子节点(或后代节点)匹配，由此可见，通配符的计算代价相当高。文献中提出消除路径表达式中的非冗余的通配符步，从而降低路径表达式的计算代价。为了消除路径中的通配符步，引入一个layer∞ds重写有通配符的路径表达式查询，在形如child：：*/…/child*/ehild1：的查询中，layeraxis可以用来替代所有路径通配步，从而把查询等价地表示为li::t1。这样一方面缩短了路径表达式，另一方面使得系统仅仅加载与查询相关的xml数据，从而大大的优化了查询。

3.2基于树遍历的路径查询优化

基于树遍历的查询优化要使用路径索引缩小搜索范围，这种优化方法的关键问题是要设计出有效合理的便于维护的路径索引。dataguides算得上是最早的路径索引，也是路径索引中最有影响力的代表。它采用了一种标签路径合并策略对文档结构进行缩减，dmguides中的每个节点都有一个目标集。这个目标集记录了通过这个标签路径可访问到的数据节点，这样执行一个路径查询时只需要在dataguides中查找该路径，获得的目标集即为满足条件的查询结果。当文档的数据结构比较规则时dataguides能很好地缩减文档的结构，从而极大地改善查询的性能。

文献中提出了一种使用图模式(graphschemas)缩小查询范围的方法。这里的图模式也起着dataguides的作用，但是它采用了合并同类边的策略。图模式中的节点叫状态，每个状态都对应一个状态扩展，集即该状态在文档中所对应的节点集。在此基础上文档提出了两种查询优化策略：剪切查询和使用状态扩展集重写查询。剪切查询是将查询的搜索限制在仅与查询结果有关的子树上，后者则是将原查询改写为在图模式上的查询，两种方法都使用非确定自动机为剪切工具。

不同于以上两种方式，文献提出了一种新的路径查询方法，该方法将xml文档中的文本数据抽取出来单独存储，这样文档树仅由带标签的元素或属性组成，这样的结构被叫做文档的骨架(skeleton)。为了使大的文档的骨架尽可能地放入内存中。这个树骨架进一步通过共享的公共子树被压缩，被压缩的树骨架的每个节点与未压缩树的一组节点相对应，他们之间的对应关系用双向相似关系表示。

3.3基于路径分解的查询优化

结构连接是基于节点在nml文档中的位置表示确定xml节点间的包含关系。给定一个祖先(或父)节点集合a和一个后代(或子)节点集合d，结构连接操作的任务就是要用高效的方法找到所有的节点对(ai,di)，其中ai是di的祖先(或父亲)，ai、di分别是a、d中的元素。a、d可能来自索引扫描也可能是某个计算的中间结果。结构连接运算的代价非常昂贵，因此结构连接算法的好坏直接影响着查询的效率，同时结构连接的顺序也极大地影响着结构连接运算的性能。

3.3.1结构连接算法

目前，已经提出的结构连接算法有两种：排序合并[2，3,7,19]和划分方法。排序合并法的主要特点是：①节点采用区域编码确定节点间的结构关系；②要求输入的数据集有序或在数据集上建立索引；③为了快速定位某类节点，可以利用元素索引、路径索引或值索引。文献中提出了一种多谓词合并连接算法(mp-mgjn)，该算法需要多次扫描数据集；文献中提出的ε－jion、εa－lion和κe-iion算法存在同样的缺点。文献提出了两类算法：树合并(tree-merge)算法和堆栈合并(stack-tree)算法，前者是传统数据库合并连接的推广，后者是一种基于堆栈的结构连接的算法，通过内存中保留一个栈结构来达到对输入数据的一次扫描的目标。文献对stack-tree算法做了改进，利用附加的索引跳过不需要参加连接的节点。堆栈合并算法(stack-tree)既可以应用在xml的关系存储系统中，也可以应用在原生xml系统中。

除了基于区域编码的结构连接算法，文献目中还针对它提出的pbitree编码提出了基于划分的结构连接算法，其划分策略有两种：水平划分和垂直划分，分别按节点在树中的高度和所在分支对数据集合的划分，这种算法不要求输入的数据有序或建立索引。结构连接算法在一定程度上依赖于节点的编码方法，目前普遍使用的编码方法是区域编码。由于使用区域编码可以快速确定节点间的包含关系，开发高效基于区域编码的结构连接算法仍然是一个值得研究的课题。

3.3.2结构连接的顺序选择

在结构连接中，无论采用什么样的结构连接算法，结构连接的顺序极大地影响着结构连接运算的性能，文献使用简单的代价估算模型提出了5种结构连接的顺序选择算法。其基本思想是使用动态规划算法在整个解空间中搜索代价最小的连接计划，当连接节点过多时解空间会发生组合爆炸，使用动态规划算法进行搜索将会变得非常缓慢。为了加速搜索速度，在动态规划算法中引入了各种不同的启发式规则，这虽然极大地提高了搜索速度却冒着一些可能丢失最优解的风险。结构连接顺序选择的目标是用较小的代价获得最优的连接计划，要实现这个目标还有待于新的结构连接顺序选择算法的提出。

文化的基本路径篇5

针对当前移动机器人的一些路径规划算法存在的局限性，提出了一种基于改进蚁群优化和遗传优化的融合算法。利用改进的信息素更新技术和路径节点选择技术使算法尽快找到优化路径，来形成融合算法的初始种群，机器人每前进一步，蚂蚁就对局部路径重新搜索，并处理随机出现的障碍物；然后利用遗传算法（GA）对种群个体进行全局优化，从而能使机器人沿一条全局优化的路径到达终点。仿真结果表明了该融合算法的可行性和有效性。

关键词：

蚁群优化；遗传算法；移动机器人；路径规划；信息素

0引言

移动机器人的路径规划问题是移动机器人研究领域的热点问题。移动机器人路径规划技术的研究起始于20世纪70年代，斯坦福研究院的NilsNilssen和CharlesRosen等，在1966年至1972年研制出了取名Shakey的自主移动机器人[1-6]，在20世纪80年代中期，设计和制造机器人的浪潮席卷全世界[5-7]。根据以往的研究，从机器人对环境感知的角度，将移动机器人路径规划方法分为三类[7-10]：基于环境模型的全局路径规划方法、基于传感器信息的局部路径规划方法和基于行为的路径规划方法。目前，已有的局部路径规划算法有人工势场法、模糊逻辑法等[2，5]，已有的全局路径规划算法有A*方法、可视图法、遗传算法、蚁群算法等[11-17]。本文提出了一种基于蚁群优化算法（AntColonyOptimization，ACO）和遗传算法（GeneticAlgorithm，GA）的移动机器人路径规划融合算法（ACO+GA），该算法克服了遗传算法在初始可行解的有效构造以及针对复杂环境设计相应的遗传算子等方面的困难，特别是

在遇到非规则障碍物的复杂环境下使用蚁群采用最近邻居搜索策略完成机器人局部最优路径的搜索。

在遇到非规则障碍物的复杂环境下使用蚁群算法采用最近邻搜索策略完成机器人局部最优路径的搜索。

仿真结果表明，该算法能够快速、高效地规划出优化路径，特别适合复杂地形环境下的机器人路径规划。

1蚁群算法原理及改进的相关技术

1.1蚁群算法原理

蚁群优化算法是MarcoDorigo等学者在20世纪90年代提出的一种基于真实蚂蚁觅食行为的、具有高度创新性的元启发式算法[11-13]。Goss等此处的人名与文献13中的人名不一致，请作相应调整。在1990年用双桥试验验证了蚂蚁这种自身催化或者正反馈的特征[13]。

1.2改进的相关技术

为了方便操作将问题进行简化，首先说明以下几个问题[11-13]：

1）该蚁群算法应用在栅格模型的路径优化上；

2）在蚂蚁数量为m的蚁群中，每个蚂蚁在访问过的单位栅格上释放的信息素为常量；

3）蚁群释放的信息素与它们发现的路径长度成反比，即：

2基于蚁群优化和遗传优化的算法融合

2.1个体编码与种群初始化

如图1所示，机器人由其起始位置B沿图中带箭头的折线所示路径运动到终点位置E，即为一个个体。取路径点的标识序列数作为路径编码，规定每条路径中不能出现重复的标识序列号。在图1情况下，一条路径表示为：p={0，10，20，31，42，53，…，99}。从起始点出发，利用环境信息和局部搜索技术，随机选取与起始点相邻的一个非障碍物点作为下一路径点，如此反复，直到找到终点为止。如图1所示，在机器人运动的起点B到终点E之间，用一系列随机选择、自由、不一定连续的栅格序号连接B和E。因此，初始种群如式（10）所示：

2.2适应性函数

一条优化路径是无碰的、不间断的可执行路径，然后要求该条路径是最短的。因此，路径个体适应性函数要包含路径长度信息、无碰撞信息和路径不间断信息[15-17]，所以，适应性函数定义如下：

2.3遗传算子

复制算子初始种群作为优化过程的开始，由算法本身随机产生，N为群体规模，即随机生成路径pj（j=1，2，…，N），同传统复制算子一样，采用与适配值成正比例的概率来选择个体。具体做法是：

1）计算选择复制的概率：

Pcopy=fj（p）/∑fj（p）（15

2）计算期望的复制数：

Dcopy=fj+1（p）/fj（p）（16

3）实际得到的复制数：按四舍五入原则对期望的复制数取整。

交叉算子第1步是将复制产生的个体随机两两配对；第2步是随机地选择交叉点，对匹配的个体按一定的交叉概率Pc（一般在0.7左右）进行交叉繁殖，产生一对新的个体。

随机突变变异是对群体中的元素（基因）加入随机扰动，使其发生变异。变异概率为Pm的取值很小（一般在0.001～0.1），变异有节制地和交叉一起使用，是一种防止过度成熟而丢失一些重要遗传信息的保险策略，但变异多保持低概率，以避免损坏下一代个体的结构。

2.4融合算法流程

根据以上的原理和相关技术，融合算法的具体执行步骤如下：

第1步利用栅格法对机器人的工作环境建模，确定起始点gbegin和终点gend，将m只蚂蚁放置在出发点gbegin，并设置禁忌表tabuk（k=1，2，…，m），设τij（0）=τ0，τ0为一常数，设置计数器s=0。

第2步以当前节点（或起始点gbegin）为中心，按照路径节点转移概率式（9）的值选择下一个节点，将无效节点加入禁忌表tabuk，直到终点gend，将有效解路径形成初始种群。

第3步利用适应性函数式（11）对种群路径个体计算适应值。

第4步利用复制算子中的式（15）和（16）对期望值高的个体进行复制，利用交叉概率Pc、变异概率Pm进行交叉和变异操作。

第5步判断是否有符合条件的路径个体出现，若有转向第7步算法结束；否则进行下一步。

第6步根据式（7）更新信息素，s=s+1，转向第2步，进入下一次循环。

第7步算法结束。

3仿真实验与分析

为了验证本文算法的有效性，在VC环境下进行了大量的仿真实验，结果令人十分满意。在实验中，通过不同数量的栅格数、随机设置障碍物、多次改变起始点和目标点等方法进行环境建模，来实现路径规划。

实验一该实验仿真了蚁群寻食过程中的情形。图2（a）给出了蚁群在寻食过程中没有遇到障碍物的情况；图2（b）给出了在蚂蚁寻食的路径上出现了障碍物的情形，此时的蚂蚁基本以相等的概率从障碍物的两侧通过，但此时蚂蚁在绕过障碍物的较短路径上稍多一些，因此沉积的信息素也相对多一些，这样就会引导更多的蚂蚁经过此路径；图2（c）给出了蚁群最终选择的路径。

文化的基本路径篇6

关键词：蚁群算法；智能算法；路径优化；应用

DOI：10.16640/ki.37-1222/t.2017.08.209

1蚁群算法

蚂蚁是一种生物个体，觅食过程中可以在其经过的路径上留下一种物质，称为信息素，并在觅食过程中能够感知信息素的强度，以此指导自己的行动方向。蚁群总是朝着信息素浓度高的方向移动，以较高的概率搜索出一条信息素浓度较高的路径，从而得到一条最佳的路径。

根据蚂蚁“寻找食物”的群体行为，意大利学者DorigoM等最早提出蚁群算法的基本模型，并阐述了蚁群算法的核心思想。该算法中蚂蚁需要具备三种智能行为，分别是蚂蚁互相通信是通过信息素，蚂蚁会在经过的路径上释放信息素，其他蚂蚁根据信息素浓度选择路径；蚂蚁具有一定记忆能力，其选择过一次的路径不会被再次选择，可由禁忌表模拟；蚁群活动，在某一路径上行走的蚂蚁越多，留下的信息素浓度越大，该路径被选择的概率也就越大，越利于选择出最优路径。

蚁群算法的最优路径搜索过程是：初始化，将若干只蚂蚁随机放置到若干个地点，并为每条路径设定相等的信息素初始值；更新禁忌表，每当蚂蚁走过一个地点，将该地点编号添加至禁忌表中，以防止蚂蚁走重复的路径；确定行走方向，根据转移概率公式，计算转移概率，从而选择出蚂蚁下一个要访问的地点；计算信息素增量，每只蚂蚁完成一次周游之后，计算每只蚂蚁走过的路径长度，保存最短路径，并且根据每只蚂蚁在经过边的信息素释放量，更新每条边上的信息素，则路径长度最短的路径各边信息素浓度更大，从而该路径在之后迭代中被选择的概率也就越大；判断终止准则，蚂蚁完成一次循环后，会将禁忌表清空，重新回到初始地点，进行下一次周游，以此循环，直到蚂蚁的周游次数满足停止准则，得到最优路径。

2蚁群算法在路径优化问题的应用

蚁群算法是一种自组织、正反馈、鲁棒性较强的算法，通过人工蚂蚁释放信息素相互通信，信息素越多的路径被选择的概率越大，从而使得蚁群自发地不断接近于最优解，从而寻找到最优路径，具有全局搜索能力，因此被广泛应用在各种路径优化问题。从大量文献看出，学者将蚁群算法不断改进，使蚁群算法在路径优化问题上的应用涉及社会各个方面，包括物流配送、居民出行、避灾逃生、农业应用、智能机器人等领域。

在物流配送方面，涉及到应急物流、医疗器械运送、快递配送、粮食输送、矿山运输等。其中，文献[1]提出了基于主次种群蚁群算法的物流配送车辆的路径优化方法，针对主次种群蚁群算法前期信息素积累较慢的缺点，分别使用路径去交叉算法和节约策略进行改进，以陕西省西安市某快递公司物流配送为例，仿真证明改进的主次种群蚁群算法在解决该快递物流问题上有明显优势。文献[2]采用了一种改进的蚁群算法进行医疗器械物流配送的路径优化，将免疫算法与传统蚁群算法相结合，具有更快的收敛速度、更短的搜索时间，实验仿真证明免疫蚁群算法的路径优化结果优于传统蚁群算法。在应急运输车辆路径优化问题中，一种改进的蚁群算法针对地震、泥石流、洪水等应急条件下的路况不稳定，加入动态路况因子，仿真使用21个真实城市作为应急情况下的货物供应点和需求点，证明了该算法可有效解决应急物流分配问题。

在居民出行方面，文献[3]研究了一种基于蚁群优化的居民公交出行路径选择算法，根据城市公交系统，设计基于蚁群算法的居民出行的公交最优路径选择模型，当乘客设定起点终点后，自动为乘客配置出最优的公交路径方案，并验证了该算法的准确性和有效性。

在避灾逃生方面，学者将蚁群算法应用到了大型公共建筑火灾的智能逃生路径规划研究中，在此加入蚂蚁体力值，使蚂蚁寻找最优路径同时也考虑到火灾发生时各种复杂的风险因素，以降低人员伤亡率，仿真表明改进后的蚁群算法不仅可以适应危险环境，而且满足实r计算的收敛性需求。

在农业应用方面，一种节水灌溉路径优化方案提出了采用信息素优化的改进蚁群算法进行灌溉路径优化设计，该方案以田间地块坐标作为数据源，采用改进的蚁群算法对田间地块布线路径进行设计，最终可以在相同的迭代次数内找到路径更短、代价更小的节水灌溉管线路径[4]。

在智能机器人方面，一种动态搜索策略的蚁群算法应用在了机器人路径规划中，其通过新的动态搜索诱导算子来改进蚁群算法性能，为增加种群的多样性，在初期设定较大阈值；进化过程中为加快收敛速度，动态调整较小阈值，实验结果表明该改进蚁群算法的收敛速度高，且解的质量得到优化，将其应用在复杂环境下的机器人路径规划问题，验证出较好的实际应用效果。

3结束语

蚁群算法是一种集群智能算法，模拟蚁群觅食原理，某路径上人工蚂蚁释放的信息素越多，被蚂蚁选择的概率会越大，由此不断接近并找到最优路径。本文总结了蚁群算法针对路径优化问题在社会各个领域中已有的应用研究，该算法可以结合其它智能算法与技术，实现更加复杂的多因素路径优化问题。

参考文献

[1]康燕妮.基于主次种群蚁群算法的物流配送车辆路径优化研究[D].西安建筑科技大学，2015（06）.

[2]费腾，张立毅，韩应征，张锦.免疫蚁群算法在常规医疗器械配送路径优化中的应用[J].天津商业大学学报，2010（03）.