资源搜索算法（精选9篇）
资源搜索算法 篇1
0 引言
近年来,社会上各种突发事件( 火灾、地震、海啸、空难等)频出,应对此类突发事件的关键是如何对所需的应急资源进行及时调度,将损失降到最小。目前国内外对应急资源调度问题的研究发展较快,刘春林、何建敏等在应急时间最早、出救点数目最少的前提下,提出了基于单目标、多目标、两层目标且有资源数量约束条件下的应急资源调度模型[1,2,3]。高淑萍和刘三阳针对出救点到受灾点的时间不确定性,给出了基于联系数的多资源连续消耗应急系统的应急时间最早的模型和算法[4]。李敏霞和车海涛针对应急系统多点出救的特点,研究了消耗速率为函数的连续型单资源应急调度模型[5]。李进等考虑了灾害链情形下的多资源调度问题,建立了灾害链中多受灾点多资源调度模型,设计了基于图论中网络优化和线性规划优化思想的启发式算法[6]。Fiedrich等针对地震受灾的特点,提出了地震后向多个受灾点进行资源调度的动态优化模型[7]。zdamar和Ekinci探讨了在限定时间内的应急资源调度问题,建立了多资源应急系统下的最短应急时间模型[8]。Ranganathan、Gupta等建立了一种基于纳什均衡的非合作博弈模型,探讨了对多受灾点进行公平合理的资源调度方案[9]。
综上所述,目前对于应急资源调度问题的研究大多是以应急时间最早、出救点数目最少作为目标,建立调度模型时极少考虑到资源调度的成本问题。在求解模型时,大多数学者运用遗传算法、差分进化算法、粒子群算法等智能优化算法进行求解,这类算法对于离散的优化问题处理不佳且容易陷入局部最优。因此本文以应急资源调度的时间成本和运输成本最小化为目标,建立在多种应急资源需求约束、供应量约束、时间约束等多约束条件下的应急资源调度模型。针对该模型的特点,对一种具有强全局搜索性的新智能算法———回溯搜索优化算法进行改进,并利用改进的回溯搜索优化算法对模型进行求解,实现应急资源的高效合理调度。
1 多资源多供应点的应急调度模型
假设有n个应急资源供应点,需要m类应急资源,对模型的符号说明如下:
A : 应急需求点;
Ai: 第i个应急资源供应点,i = 1,2,…,n ;
tij: 从Ai处运输第j类应急资源到A处所需的时间,tij> 0,j = 1,2,…,m,不妨设t( k+1) j≥ tij,k = 1,2,…,n - 1 ;
xij: Ai处对第j类应急资源的供应量;
x'ij:Ai处对第j类应急资源的最大可供应量,其中x'ij≥xij≥0;
Rj: A处对第j类应急资源的需求量,其中Rj≤ ∑x'ij;
Tj: 第j类应急资源的供应量满足一定应急系数w( 资源供应量相对于需求量的百分比) 的时限,即在Tj时间内,第j类资源的供应量达到wRj;
Cij:第j类应急资源从Ai到A的单位运输成本;
Cij(t):Ai处第j类应急资源的时间成本系数。
问题要求确定一个应急调度方案,在满足应急资源需求量和时间约束的基础上,使总的调度成本最低。建立多资源多供应点的应急调度模型如下[10]:
该模型是以时间成本和运输成本最小化为目标的多目标应急资源调度模型,其中,f1( X) 为应急资源调度的时间成本,f2( X) 为运输成本。
对于应急需求点所需的第j类应急资源,应优先选择运输时间最短的供应点进行调度。因此,应急资源调度的时间成本可以以运输时间最短的供应点作为参照对象,将时间成本转换为运输成本。设第j类应急资源的最短运输时间为t0( j) ,对应的单位运输成本为C0( j) ,则从供应点i供应该类应急资源,所增加的单位时间单位成本为| Cij/ tij- C0( j) /t0( j) | ,增加的运输时间为tij- t0( j) 。因此,时间成本系数Cij( t) 可以转化为单位运输成本,Cij( t) =| Cij/ tij- C0( j) /t0( j)| ·( tij- t0( j) ) 。由此,该调度模型的多目标函数可以表示为单目标函数:
2 回溯搜索优化算法基本原理
回溯搜索优化算法是一种解决实值优化问题的新的进化算法,由Pinar Civicioglu于2013 年提出[11]。与其他搜索算法不同,回溯搜索优化算法只有一个单一的控制参数,且问题的解决不过分依赖于初始解的选取。简单的结构使回溯搜索优化算法能够快速适应不同的数值优化问题,因而能够有效且快速地解决多目标问题。
对于一个最小化问题,回溯搜索优化算法的求解过程主要包括: 初始化种群、选择操作Ⅰ、变异操作、交叉操作和选择操作Ⅱ。
1) 初始化种群: 根据式( 8) 对种群中的个体进行初始化。
其中,i = 1,2,…,N; j = 1,2,…,D。N是种群规模,D是问题维数,upj、lowj分别表示第j维分量的上限和下限,rand( 1) 产生0~ 1 之间的随机数,round对产生的数值进行取整。
2) 选择操作Ⅰ: 在之前产生的种群中随机选择一个种群P作为历史种群Old P ,按照式( 9) 进行选择操作。
其中,a、b在区间( 0,1) 上服从均匀分布。
3) 变异操作: 对Old P中的个体进行随机排序,并重新赋予Old P ,利用式( 10) 进行变异操作。
其中,F是变异尺度系数,F = 3·randn,随机数randn服从标准正态分布。
4) 交叉操作: 将历史种群Old P中个体的元素与变异种群Mutant中相同位置个体的同维元素进行互换,生成新的个体。其实质是确定每个个体交换的维数v,交换维数v的选取方式有两种,即有两种不同的交叉策略,如式( 11) 所示。
其中,mixrate是交叉概率。两种交叉策略等概率随机调用,构成回溯搜索优化算法的交叉策略,交叉操作后的种群为T 。
5) 选择操作Ⅱ: 采用式( 12) 的贪婪策略进行选择操作。
其中,fitness代表适应度函数。
3 回溯搜索优化算法的改进
3. 1 变异尺度系数设计
根据式( 10) 可知,当变异尺度系数F较大时,( Old P-P) 对变异个体Mutant的影响较大,有利于保持种群的多样性,但是收敛速度将变慢,求得的全局最优解精度低; 反之,F较小时,能起到局部精细搜索的作用,但是容易陷入局部最优而出现早熟收敛[12]。因此,本文设计新的变异尺度系数如下:
其中,t为迭代次数; β 为缩放比例; a为初始衰减率,调整a的值可以调整变异尺度系数F的下降速度。
式( 13) 表明,在算法初期,F值较大,易于找到全局最优值,且F值下降的速度较快,能够加快最优解的收敛速度; 在算法后期,F值下降的速度减慢,有利于进行局部精细搜索。
3. 2 自适应交叉概率设计
在标准回溯搜索优化算法中,交叉概率mixrate是一个固定值。为了能够利用其他种群搜索到的优良信息,提高算法的搜索性能,本文提出了一种交叉概率的自适应调节策略,如式( 14) 所示[13]。
其中,mixrate( i) 是第i个个体的交叉概率,i = 1,2,…,N; fi是第i个个体的适应度函数值; f1best和fworst分别表示当前子群中适应度最优和最劣的函数值; fgbest表示当前所有群体中适应度最优的函数值。
3. 3 改进回溯搜索优化算法求解步骤
Step 1
设定种群规模、最大进化代数、缩放比例 β 和初始衰减率a ;
Step 2
按照式( 8) 初始化种群P( t) ,t = 0 ;
Step 3
计算种群中每个个体的适应度fitness( Pi) ,若满足终止条件,则输出结果并结束计算; 否则,转下一步;
Step 4
按照式( 9) 对种群P( t) 进行选择操作 Ⅰ,确定历史种群Old P( t) ;
Step 5
按照式( 13) 和式( 14) 分别计算变异尺度系数F和交叉概率mixrate ;
Step 6
按照式( 10) 进行变异操作,生成变异个体;
Step 7
按照式( 11) 对变异个体进行交叉操作,生成新个体Ti;
Step 8
计算fitness(Ti),按照式(12)进行选择操作Ⅱ;
Step 9
重复Step 3-Step 8。
4 算例分析
4. 1 算例描述
为了验证改进回溯搜索优化算法的调度效果,采用文献[10]中的实验数据,对改进回溯搜索优化算法( IBSA) 与回溯搜索优化算法( BSA) 、差分进化算法( DE) 以及改进粒子群算法( IPSO) 进行了对比实验。实验数据描述如下:
某地A发生严重突发事件,急需3 类应急物资,需要从A1、A2、A3、A4、A5五个供应点进行紧急调度。其中,应急系数w =0. 6,A处对第j类应急资源的需求量Rj= [15,30,50],时限Tj=[10,15,8]。Ai处对第j类应急资源的最大可供应量x'ij,从Ai处运输第j类应急资源到A处所需的时间tij,第j类应急资源从Ai到A的单位运输成本Cij如表1 所示。
运用改进回溯搜索优化算法,进行Matlab编程求解。种群规模N=20,最大进化代数为2500,缩放比例β=0.5,初始衰减率a在区间[e-3,e3]上按对数均匀分布取值。得到一组最优解,即最优方案为:物资1从供应点A1、A2、A5进行调度,调度量分别为4、5、6;物资2从供应点A3、A4、A5进行调度,调度量分别为3、13、14;物资3从供应点A1、A4、A5进行调度,调度量分别为8、18、24。总的调度成本为61.58万元。
4. 2 结果分析
运用回溯搜索优化算法(BSA)、差分进化算法(DE)和改进粒子群算法(IPSO)进行模型求解,与本文的改进回溯搜索优化算法(IBSA)进行比较。BSA的种群规模N=20,最大进化代数为2500;DE的交叉因子CR∈[0,1],缩放因子F是[0,1]之间的随机数,采用一对一的淘汰机制来更新种群。IPSO的学习因子c1=c2=1.4962,惯性权重w随着进化代数的改变而动态变化,。所有算法均采用Matlab编程,得到的最优调度方案及最小调度成本如表2所示。
上述算法均能在十几秒内得到模型的最优解,但在算法性能方面,IBSA明显优于其他算法,得到的结果更好,调度成本更低。四种算法的成本进化曲线如图1 所示。
观察图1 可以看出,IPSO的成本进化曲线迅速下降,在第71 代便收敛得到最优调度成本为67. 67 万元; DE在第203 代得到最优调度成本为66. 69 万元; BSA的收敛速度较慢,最终得到最优调度成本为63. 19 万元。IBSA的成本进化曲线在前200代急剧下降,然后趋于平缓,在480 代继续下降,最终收敛得到最优调度成本为61. 58 万元。对四种算法的最优成本进化曲线进行比较,如图2 所示。
从图2 可以看出,IPSO的收敛速度最快,但是在迭代后期,由于全局搜索能力变弱,出现早熟收敛而陷入了局部极值; DE由于变异个体在后期趋于同一,也陷入了局部最优;BSA的全局收敛性强,但是收敛速度较慢; IBSA相比于BSA的收敛速度明显提升,且全局寻优能力强,求解精度高,具有良好的执行性能。
5 结语
建立了以时间成本和运输成本最小化为目标的应急资源调度模型。针对该模型特点,对回溯搜索优化算法进行了改进,设计了变异操作中的变异尺度系数和交叉操作中的交叉概率,提高了算法的收敛速度和求解精度。通过仿真实例,对IBSA与BSA、DE、IPSO进行了求解比较,IBSA在全局搜索能力和求解精度方面均优于其他三种算法,有效解决了其他算法易陷入局部最优且出现早熟收敛的问题。在下一步的工作中,将考虑更加复杂的应急资源调度模型,并运用改进回溯搜索优化算法进行求解。
摘要：以连续性消耗应急系统为背景,建立以时间成本和运输成本最小化为目标的多资源多供应点调度模型。针对该模型的特点,对一种具有强全局搜索性的新智能算法——回溯搜索优化算法进行改进,设计变异操作中的变异尺度系数和交叉操作中的交叉概率策略,提高算法的收敛速度和求解精度。运用改进回溯搜索算法进行模型求解,仿真实例表明,改进回溯搜索优化算法在解决应急资源调度问题时拥有良好的性能,全局收敛性与求解精度均优于比较的回溯搜索优化算法、差分进化算法和粒子群算法,能够有效且合理地进行应急资源调度。
关键词：调度成本,应急资源调度,改进回溯搜索优化算法,变异尺度系数
资源搜索算法 篇2
关键词：车辆路径问题；不确定决策；禁忌搜索算法
中图分类号：F224文献标识码：A
文章编号：1002-3100(2007)12-0026-04
Abstract: A vehicle routing problem in war is discussed, in which some routes may be destroyed uncertainly by competitor. A two-stage integer program model is constructed. The value of a route in a uncertain situation is analyzed. In the method, only the maximum value and the minimum value are countered into the object value, simpling the computation of the object value of the model. A two-stage tabu search algorithm is designed. In the end, an example is given.
Key words: vehicle routing problem; uncertain decision; tabu search algorithm
0引言
战争环境下，交通线路中的一些关键性的桥梁、隧道和线路枢纽随时可能被敌方破坏。利用这些关键性的桥梁（隧道）运输时间将会缩短，但如果这些桥梁被毁坏，运输车可能要绕道运输甚至原路返回，反而延误了运输时间。这一类问题同样也存在于自然灾害的救援活动中。在人类的发展历史上，地震、洪水、台风和雪崩等自然灾害也是破坏交通线的重要因素。1995年日本的神户地震、美国近期的飓风“丽塔”、我国1998年的特大洪水等都破坏了许多交通设施，同时这些自然灾害还随时威胁物资救援的运输线路。由于这类运输直接关系到整个军事（救援）活动的成功与否和人员的生命安全，因此研究这一类不确定的运输决策问题无论对于战争还是人类战胜自然灾害都具有重要的意义。目前关于车辆线路优化的研究很多，但涉及战争环境下（或自然灾害环境）的研究很少，正式的研究文献几乎没有看到。本文探讨了一个个别关键路段（桥梁、隧道等）可能被毁坏情况下的多车辆路径决策问题，提出了相应的数学模型并给出了求解模型的禁忌启发式算法。
1问题描述及复杂性分析
1.1问题的提出
2数学模型
调整上述模型的一些参数，即可建立不协作的两阶段规划模型，这里不再详述。
3线路方案的评价值
4禁忌搜索算法
禁忌搜索算法主要内容如下：
（1）随机产生一个路径序列为初始解。为n个需求点编序列号，仓库为0。路径解的首尾各为0，中间是n个需求点加上M-1个0的随机排列。相邻两个0之间为一个车辆的服务路径。以6个需求点，两辆车为例，一个路径解为0-1-2-3-0-4-5-6-0。
（2）邻域的产生。分别采用任意两个需求点交换位置、任意一个需求点插入到线路任意位置的方法产生新的解。
（3）车辆容量限制的处理。当一个车辆线路中的需求点的总需求量超过车辆最大载货量时，该线路方案被淘汰。
（4）禁忌对象为两个相邻的需求点。禁忌表的长度随进化代数的增加而加长。当前值优于历史最优值时，禁忌解除。
（6）线路的方向。在乐观准则下，毁坏后线路的调整变化没有被计算到评价值中，为了弥补这一缺陷，可选出乐观准则下的最优方案和多个次优方案，并计算出最坏情况下的结果，以供决策参考。即使是最优化方案，相同的线路次序但不同的线路方向也被认为是不同的方案。如线路0-1-2-3-4-0和0-4-3-2-1-0是不同的方案。
5示例
表1是一个路网的距离数据。其中路段2-4经过一个难以修复的桥梁，被敌方破坏的可能性非常大。0表示仓库，其它10个序号表示需求点，每个需求点需求为5，每辆车的最大载货量为35，用两辆车送货，要求规划不同期望值准则下的里程最短的线路。
由于车辆载货量的限制，完成任务必须两辆车。采用文中的禁忌搜索算法得到不同准则下的最优方案。
6结束语
战时或各种抢险救灾时的物流运输保障具有重大意义。但这类运输线路优化问题至今研究很少。本文把不确定决策技术和车辆路径优化技术结合起来，建立了不确定环境下的运输线路优化模型，研究结果可以为不确定环境下的物流配送决策提供参考。
参考文献：
[1] 李军，郭耀煌. 车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001:7-10.
[2] 甘应爱，田丰,等. 运筹学[M]. 北京：清华大学出版社，1990.
[3] 柳春光，焦双健. 城市震后救灾系统救灾决策研究[J]. 自然灾害学报，2000,9(3):21-24.
[4] 吴育华，杜纲. 管理科学基础[M]. 天津：天津大学出版社，2001.
[5] 张凤林，武小悦，郭波,等. 物流网络可用性研究[J]. 系统工程理论方法应用，2002,12(1):16-19.
基于P2P的资源搜索算法探讨 篇3
P2P中文称为对等网络, 是指分布式系统中的各个节点是逻辑对等的, 与目前互连网上比较流行的C/S计算模型不同的是:P2P计算模型中不再区别服务器以及客户端, 系统中的各个节点之间可以直接进行数据通信而不需要通过中间的服务器。也就是说, 对等网络中每个IP点的地位是对等的, 既可充当服务器为其它节点服务, 也可充当客户机消费其它IP点提供的服务。依据文件的检索模型和机制, 现有的P2P实现方式大致可以分为3种类型。它们分别是基于目录服务器P2P, 非结构化P2P和结构化P2P。
2 基于根服务器的P2P搜索算法设计
2.1 数据结构
(a) 根服务器上保存所有搜索树根的列表:
(b) 物理节点 (PN) 所保存的本地逻辑节点列表:
(c) 逻辑节点 (LN) 的路由表:
2.2 搜索树根发现机制
所有LN维护一个仅存储自己的父节点、所有子节点的位置信息的邻居表, 所有根节点的子节点均设置父节点为根节点的标识符当一个LN需要获得根节点的位置时, 将发送一个根节点发现消息给自己的父节点, 并逐级向上转发, 直到父节点为根节点时, 返回响应消息。如图1所示。
2.3 空余度路由更新算法
子LN节点的空余度Vin或者空余度距离Lin发生改变时, 将二者的值发给父LN, 通知父节点执行空余度路由更新。父节点更新自己存储的该子节点的Vln和Lin, 并根据新的子节点空余度路由状况, 重新设置自己的空余度路由出口。
如图2, Vin为空余度, Lin为空余度距离, Ext为空余度路由出口。LN6下接4个节点之后, LN6的空余度路由发生改变, 同时通知其父节点LN2, LN2将选择Lin最小的子节点, 而LN7.LN8.LN9的Lin均为0, 因此LN6选择这3个子节点中Vin最大者, 即LN9作为自己的空余度路由出口。而LNl及其它兄弟节点并为受此拓扑变化的影响。
伪码如下:
2.4 搜索树创建算法
当一个物理节点上存储的文件加入P2P网络时, 将执行一下步骤:
(a) 计算出该文件各个关键字对应的哈希键值
(b) 检查本节点上是否己经存在包含该哈希键值的LN, 如果没有, 则创建该LNnew.
(c) 检查该物理节点上是否已存在的其它LN, 如果不存在, 则向根服务器发送新LN消息:如果存在则利用该LN的根LN发现消息找到其所对应的根LN, 即对应另一哈希数值区间的搜索树根, 并由此确定LNnew本身所属的哈希数值区间的搜索树是否存在 (步骤d确保每个搜索树根LN均保有所有搜索树根LN的信息) , 若存在, 则转向LN加入算法:若不存在, 则向根服务器发送新LN消息。
(d) 根服务器接收到新LN消息, 在LNnew所对应的哈希数值区间上新建一棵搜索树, 即将该物理节点上的这个新创建的LN, 定义为该搜索树的根添加到本地搜索树根表中的对应行, 随即将这张搜索树根表发给所有根LN进行更新。
如图3所示, 新加入的逻辑节点LNnew仅在本地不存在其它LN的时候才向根服务器发起查询请求, 而根服务器也仅需返回对应于LNnew所在哈希值区段的搜索树树根地址即可。伪码如下:
建立搜索树的目的即是将同在一个关键字哈希值区间内的文件逻辑上聚合在一起, 当产生搜索请求时, 搜索消息即可在某个搜索树内部进行, 消除了盲目性, 而搜索树的结构也保证了不会有消息循环和冗余。每个节点仅需负责简单的转发消息和查找自己的文件列表, 负载分布合理, 具有很高的效率。
2.5 逻辑节点加入算法
当一个新的LN:LNnew加入网络.并且由算法A中的 (c) 步骤转向LN加入算法时:
(a) LNnew通过同一PN的其他搜索树节点获得自己所在搜索树的根LN节点。若该PN没有其他的LN时, 则向根服务器查询根LN。
(b) LNnew向根节点LN发送新LN消息。
(c) 从根节点开始, 依照空余度路由转发LN加入消息, 直到到达路由出口指向自身的节点LNi, 即完成搜索。
(d) LN将LNi作为LNnew的父节点, 并通知该当前节点和LNnew, 二者随后更新自己的空余度路由表。
如图4 (a) 所示, LNnew向其所属的搜索树的根节点LN1发出加入请求, 根节点沿着空余度路由进行搜索, 直到找出u指向自己的逻辑节点LN9。
如图4 (b) 所示, LNnew接入搜索树, 成为LN9的子节点, 则LN9更新其空余度路由, 并向父节点LN2发出更新消息, 以此类推, LN2和根节点LNI均更新空余度路由, LNnew加入过程完毕。
伪码如下:
采用空余度路由的理由是尽可能将新加入的节点往靠近根LN的地方放置, 并且尽可能将各LN的子节点排满, 避免在搜索树的各个LN间广播空余度查询消息, 造成对搜索树的大面积遍历, 浪费网络资源。
参考文献
[1]詹春华, 陈晓苏.对等网络搜索方法比较与分析[J].湖北工学院学报, 2004 (5) .
[2]陈志琦, 苏德富.基于P2P技术的Gnutella网络搜索路由机制的改进[J].计算机工程与设计, 2005 (2) .
[3]周晋, 路海明, 卢增祥, 等.基于部分匹配方式的可扩展P2P搜索算法[J].清华大学学报 (自然科学版) , 2004 (10) .
[4]李运娣, 冯勇.基于DHT的P2P搜索定位技术研究[J].计算机应用研究, 2006 (10) .
[5]邱彤庆, 陈贵海.一种令P2P覆盖网络拓扑相关的通用方法[J].软件学报, 2007 (2) .
资源搜索算法 篇4
关键词 BOC 捕获 频谱 仿真搜索 正交
1 引言
由于GPS卫星发射的导航信号比较微弱，而且以固定的频率发射，因此很容易受到敌方的干扰。为了改善这种局面，1977年美国正式提出了“GPS导航战”（Navigation warfare）的概念[1-3]。但由于现行的军用和民用GPS信号的频谱是混叠使用的，所以美方对C/A码施放干扰信号也必然导致军用信号频谱的中央部分不能使用。为了改善GPS这种频谱结构的缺陷，美方经过大量的研究后，确定了最终方案：在现有L1和L2两个频段上附加新的军用信号，即M码。M码采用一种裂谱调制法，它把其大部分功率放在靠近分配给它的频带的边缘外，抗干扰能力主要来自不干涉C/A码或Y码接收机的强大的发射功率，而且M码信号的保密设计基于下一代密码技术和新的密钥结构，具有很高的保密性。实现M码分裂频谱调制方法有很多种，经过大量比较，确定了选用二进制偏移载波（BOC）调制技术，这是因为它不仅使M码信号的频谱能与现有信号的频谱很好的隔离，而且还有更好的性能。本文在介绍BOC调制技术的原理和分析其频谱结构的基础上，提出了基于并行码相位搜索的改进捕获算法，设计了正交IQ捕获算法，对两路并行捕获，捕获性能优于传统的捕获方法，仿真结果显示算法的正确性。
2 BOC调制信号的频谱与自相关特性
二进制偏置载波（BOC）调制，该调制提供两个相互独立的设计参数：
（1）副载波频率fs，单位MHz；
（2）扩频码速率fc，单位Mchip/s。
通过这两个参数，可以自由地将信号能量集中在所分配带宽的指定部分，以减少接收其他信号的干扰。
BOC调制信号通常被记作为BOC（fs，fc）或BOC（a，b），其中fs=af0，fc=bf0（a，b通常为正整数），基准频率f0=1.023MHz。
2.1 BOC调制信号的频谱特性
BOC（fs，fc）信号的归一化基带功率谱4-7：当n=2fs/fc为偶数时[4-7]，
（1）
当n=2fs/fc为奇数时，
（2）
采用BPSK调制方式，扩频码码率为fc的GPS C/A码信号的归一化基带功率谱为：
（3）
图1所示为 BOC（1，1）信号和GPS C/A码信号的归一化基带功率谱，可以看出BOC（1，1）相对于 GPS C/A码信号，最大的一个特点就是具有中心分裂的功率谱，这将有助于降低它与GPS C/A码信号的干扰，并且由于它在高频段具有更多的能量，它比GPS C/A码信号拥有更大的Gabor带宽， 这也意味着它具有更佳的捕获性能。
2.2 BOC调制信号的自相关特性
BOC调制信号的自相关函数，可以通过对BOC调制信号的功率谱做逆傅立叶变换得到。理想情况下（接收机前端带宽无限宽）BOC（pn，n）信号的自相关函数为[8]：
（4）
其中，p=1，2，3，…，k=■。
在（4）中令p=1，可得BOC（1，1）自相关函数RBOC （1，1）（τ）为：
（5）
采用BPSK调制方式的GPS C/A码信号的自相关函数RCA（τ）为：
其中k=2τ/Tc，Tc=1/fc。图2所示为BOC（1，1）信号和GPS C/A码信号的自相关函数，可以看到BOC（1，1）的自相关函数相对于GPS C/A码信号而言，具有多个峰值，这也对接收机提出了更高的要求。通常将自相关函数正中间的峰值称为主峰，而其它的峰称为旁峰。
3 捕获算法的设计
经典的并行码相位搜索框图如图3所示[9-10]：
本地产生的副载波与本地产生的伪码相乘之后变换到频域取共轭，输入信号经过傅立叶变换后与经过傅立叶变换的BOC码相乘，输出结果经过傅立叶逆变换 转换为时域信号，傅立叶逆变换输出的模值表示输入信号与本地伪码的相关结果。改进后的并行码相位算法框图如图4所示：
改进捕获算法如下：
（1）将接收到的中频信号取1ms的数据长度，记为x（n）；
（2）本地载波取中频信号IF±10KHz范围，步长取500Hz，生成41个本地中频载波，并对生成的本地载波进行采样，记为li（n）（i=1，2，…，21）；
（3）将x（n）和li（n）的转置点对点相乘，结果取FFT，记为Fi（k）；
（4）产生本地副载波，相位分别为0°和90°，两路信号分别进行FFT变换到频域中，并取共轭。记为f1*（k）和f2*（k）；
（5）Fi（k）分别与f1*（k）和f2*（k）点对点相乘，结果记为G1（k）和G2（k）；
（6）产生本地的C/A码，并对其进行采样，记为Cs（n）（s为卫星编号）；
（7）对Cs（n）进行FFT，变换到频域中，并取共轭，记为Cs（k）*；
（8）将G1（k）和G2（k）分别与Cs（k）*点对点相乘，结果为Rs1（k）和Rs2（k）；
（9）对Rs1（k）和Rs2（k）进行IFFT，变换到时域中，得到rs1（n）和rs2（n），得到其模平方rs1（n）2和rs2（n）2；
（10）比较rs1（n）2和rs2（n）2的最大值，选择判决那个大就选择哪个，记为rsi（n）2，最大值对应的坐标即为C/A码的起始点和载波粗频。
4 仿真结果及分析
高斯信道信噪比为0dB时的捕获结果如图5所示，局部放大图如图6所示。由图可以看到有1个主峰和2个次峰，这和BOC（1，1）信号的自相关函数有三个峰值是相符的，由图BOC（14，2）捕获图可以看出，峰值位于码相位45094和频率25.542MHz处，图7为BOC（14，2）信道加高斯干扰0dB-34dB的仿真结果。
由图仿真结果可知，当干扰为-36dB时，捕获算法完全失效，主峰与副峰比值基本相同，捕获结果完全被信号淹没，在干扰为-35dB到-27dB时，捕获算法仍然有效，但效果较差，此算法在大于-27dB高斯信道干扰下完全可以捕获到信号的初始码相位和载波频率，为进一步跟踪提供了粗略值。
5 结束语
改进的捕获算法基于并行码相位搜索算法，针对收发端载波不同的问题，在产生本地副载波时分别产生I路和Q路两路信号，分别基于捕获算法，最后对捕获到的峰值进行比较，这样可以选择最优的捕获结果。
参 考 文 献
[1] 杨东凯，樊江滨，张波，张敏译. GNSS应用与方法. 电子工业出版社. 2011.09 p.16-22
[2] 杨力，基于BOC调制的导航信号同步接收关键技术研究. 南京理工大学.2009.12
[3] 楚横林，李春霞. BOC调制导航信号关键技术研究. 2010 Radio Engineering Vol.40 No.6
[4] 王智，耿相铭. Galileo卫星导航系统中的BOC调制与接收技术.上海航天.2007年第6期
[5] Peter Rinder， Nicolaj Betelsen， Design of a single frequency GPS software receiver. Aalborg University 2004.
[6] D Akopian.Fast FFT based GPS satellite acquisition methods.IEE Proceedings Radar， Sonar and Navigation，2005，1 52（4）：277—286.
[7] 杨俊，武奇生. GPS基本原理及其Matlab仿真. 西安：西安电子科技大学出版社. 2006：126-181页
[8] Julien O，Cannon M E，Lachapelle G，et al.A New Unambiguous BOC（n，n） Signal Tracking Technique [A].In：Europe Navigation Conference GNSS 2004[C].2004：17-19P
[9] 刑兆栋. BOC 导航信号处理方法及卫星导航数据的传输. 北京航空航天大学. 2006：58-73页
[10] Kai Borre，Dennis M.AKos，Nicolaj Bertelsen Peter Rinder Soren Holdt Jensen，杨东凯，张飞舟，张波译. 软件定义的GPS和伽利略接收机. 国防工业出版社.2009.3
Based on Parallel Code Phase Search of BOC Signal Acquisition Algorithm of Design and Implementation
Xin Fuguo1，Li Rongfang2
（1. Shaanxi Post and Telecommunication College department of communication，Xianyang 712000，China）
（2. Shaanxi Post and Telecommunication College department of computer，Xianyang 712000，China）
Abstract BOC modulation，as a navigation signal system ，has such better performances as multipath-resistant and anti-jamming ，it can realize spectrum separation under the condition of carrier frequency being shared .This paper first analyzes the characteristic of the frequency spectrum of BOC signal and the autocorrelation function ， put forward based on the concurrent code phase search of the algorithm， the design of orthogonal orthogonal IQ acquisition algorithm， the two road parallel acquisition， the simulation results show the correctness of the algorithm and the superiority.
资源搜索算法 篇5
1.1 移动P2P网络的定义及特征
移动P2P至今没有统一的学术定义, 它是近年来新兴的研究领域。移动P2P (MP2P) 网络[2]也称为移动点对点网络, 它利用已有的底层资源共享技术进行移动节点之间的数据发送和接收操作, 以达实现节点间数据资源共享的目的。
受无线网络环境限制, MP2P网络有如下特性:
(1) 高度动态性:由于网络终端节点是无线设备, MP2P网络的一显著特点就是网络的不稳定性, 拓扑结构时刻处在不断变化中, 且变化频繁。
(2) 节点自身有限资源:MP2P网络中的终端节点大多为移动手机、平板电脑、手提电脑等设备, 其性能限制了节点的服务质量、数据传输和共享等操作, 导致整体系统性能受到影响。
(3) 传输时长较大:由于MP2P所处无线网络环境, 节点之间的资源传输只能在一定范围内进行, 当距离超过范围时, 需要加入中间节点来进行转发, 从而造成了网络的时延。
1.2 MP2P资源搜索算法
MP2P系统的重要作用就是实现系统中节点之间的数据共享, 而实现数据共享的前提条件是找到节点需要的资源, 这需要MP2P系统进行资源搜索操作, 因此, 资源搜索成为MP2P重点研究方向。当前对MP2P资源搜索算法的研究总体概括为:一是将现有的适用于有线网络的P2P协议进行修改, 用在无线网络中;二是重新设计专门的无线P2P资源搜索协议, 但受无线网络环境限制, 这方面还有大量工作要做。当前研究较多的方法是改进传统P2P协议, 并将其应用在移动环境中。
对传统P2P协议改进后应用于移动网络主要有三类:集中式拓扑结构搜索算法、基于泛洪式信息广播搜索算法以及基于DHT结构化搜索算法。
1.2.1 集中式拓扑结构搜索算法
基于中央索引节点的传统P2P协议中最经典之一是e Donkey[2]协议。MP2P网络资源搜索策略对e Donkey协议做了改进, 加入三种节点:代理节点、缓存节点和爬虫节点。这种算法设计的主要目的是将网络中性能较好的单个运用商资源充分利用, 使网络中的资源控制在本地库中。这种设计的缺点是:索引服务器必须和移动终端保持实时联系, 以便及时了解移动终端在线情况。移动终端要保持实时在线, 就必然导致网络带宽消耗严重以及终端电源耗损较快, 反而缩短了移动终端在线的时间。
1.2.2 基于泛洪式/广播式资源搜索算法
Gnutella协议是传统广播式资源搜索算法的典型应用。基于泛洪式/广播式MP2P资源搜索算法的原理是:在已有的P2P泛洪式协议基础上加入代理节点, 当移动终端需要查询某个资源时, 首先将资源查询请求传输到代理节点处, 代理节点再继续发送。整个过程通过Gnutella协议实现文件共享和资源查询。
1.2.3 基于DHT结构化资源搜索算法
基于DHT结构化的资源搜索算法是:将传统DHT协议改进使之适应于移动网络环境。基于该方面的研究算法比较多, 文献[3]至[5]都是将传统DHT算法进行改进, 使之适用于MP2P网络。
MP2P资源搜索算法是MP2P网络研究热点之一, 做了大量的工作。将泛洪式算法与DHT算法相结合, 使之适应于移动网络环境特点, 是未来资源搜索策略重要研究方向。
2 基于分组的MP2P资源搜索算法
移动网络的一大特点就是高不确定性及高动态性。由于该特点, 传统P2P协议并不能直接在MP2P环境下发挥良好作用。笔者提出了一个基于分组的MP2P资源搜索算法, 主要原理是:无线终端使用者以往查询的数据内容都有缓存记录, 这些记录可认为是节点“兴趣”, 根据查询的“兴趣”, 终端节点自组织成“组”, 整个网络因此形成多种包含各类“兴趣”的组, 组和组之间的数据共享通过Chord协议实现, 一个组内的节点之间的数据分发资源共享通过非结构化拓扑方式完成。整个网络因此形成一个层次化的拓扑结构。
2.1 算法核心思想
本算法中, 节点根据“兴趣”自组织成组, 组内采用非结构化拓扑, 组和组之间通过超级节点连接, 超级节点之间采用Chord结构化拓扑。除“超级节点”外, 移动网络中的其他节点是“普通节点”。该算法核心思想结构图如如图一所示。
网络中的组都有唯一的由哈希函数计算而得的组标识符 (Group ID) , 每个组在网络中所处的位置就是由组ID决定的。组和组之间通过Chord环组成多条通信路径。组内拓扑结构如图二所示。
2.2 系统创建机制
2.2.1 系统初始化
本算法中, 系统初始化的过程其实就是网络中的节点通过“兴趣”自组织成组 (Group) 的过程。初始化过程图如图三所示。
图三 (a) 中, 终端节点P1向网络中的所有节点广播资源搜索请求消息。
图三 (b) 中, 系统中的终端节点P3收到节点P1发送来的消息, 并向P1节点发送一应答消息, 表示本地资源中包含P1需要的资源。
图三 (c) 中, P1收到P3发送过来的应答消息后, 更新朋友列表, 将P3作为自己的朋友节点。
以上步骤不断循环重复执行, 网络中不断增加节点, 节点又各自组成不同的组, 当系统中组的数量超过两个或以上时, 系统完成初始化。
2.2.2 节点加入网络
系统通过自组织方式完成初始化后, 其他节点开始不断加入网络。节点分两种情况加入组:一是超级节点加入, 二是普通节点加入。当网络中不存在该节点相同或相类似的“兴趣”组时, 该节点是作为超级节点加入网络, 并根据该节点的“兴趣”新建一个组。当网络中存在与该节点相同或相类似的“兴趣”组时, 节点是作为普通节点加入该“兴趣”组。
2.2.3 节点离开网络
节点离开网络时有两种状况:一是普通节点离开网络;二是超级节点离开网络。
(1) 当普通节点离开网络时, 因长时间不与其他节点进行数据分享, 组内其他朋友节点会自适应更改朋友列表, 普通节点离开对网络不影响。
(2) 当超级节点离开网络时, 情况稍微复杂一些。首先它会向组内所有节点发送一条广播信息, 通知组内节点要更新本地超级节点列表;同时, 其他组中的超级节点也会收到一条广播消息, 告知需要更新其邻居节点列表。超级节点离开后, 系统会重新启动超级节点选择机制。
3 结束语
MP2P近年来发展迅速, 关于MP2P研究的文章也相继出现。本文提出了一种基于分组的MP2P网络资源搜索算法, 该算法克服了无线网络高度动态性及终端性能的限制, 节省了网络带宽和相应时间, 提高了网络内资源搜索效率。
摘要：移动P2P (Mobile P2P) 技术是随着近年来无线网络的兴起而发展起来的新兴研究领域, 主要集中在系统结构、资源搜索以及数据共享等技术方面。本文提出了基于分组的移动P2P资源搜索算法 (RSBG) , 由该算法得出的仿真结果可知:RSGB资源搜索算法提高了文件查找的效率, 缩短了查找时长, 增大了搜索的成功率。
关键词：MP2P,资源搜索算法,分组算法
参考文献
[1]张春红, 裘晓峰, 弭伟, 等.P2P技术全面解析[M].北京:人民邮电出版社, 2010.
[2]Andersen F, de Meer H, Dedinski I.An architecture concept for mobile P2P file sharing services.In:Proc.of the Workshop at Informatik 2004-Algorithms and Protocols for Efficient Peer-to-Peer Applications[C].Bonner Kllen Verlag, 2004.
[3]R.Winter, T.Zahn, J.Schiler, Dynamo.A topology-aware P2P overlay network for dynamic, mobile ad-hoc environments[J].Telecommunication Systems, 2004, 27 (02) :321.
[4]Gang Peng, Shanping Li, Hairong Jin, et al.M-CAN:a Lookup protocol for Mobile Peer-to-Peer Environment[Z].International Symposium on Parallel Architecture, Algorithms, and Networks (I-SPAN2004) , 2004.
资源搜索算法 篇6
近几年来,基于点对点P2P(1)的网络逐渐成为互联网中最流行的网络之一。对等网络打破了传统的C/S模式,每个节点既是服务器,为别的节点提供服务,同时又可以向其他节点请求服务。P2P的概念并不局限于文件的共享,它在对等节点之间共享资源和服务,可以共享的计算机资源包括处理器的计算能力、存储器和磁盘等。
目前,根据拓扑结构的关系可以将P2P分为4种形式:中心化拓扑;非结构化拓扑;结构化拓扑(2)和混合拓扑。中心化拓扑最大的优点是维护简单发现效率高,最大的问题是与传统C/S结构类似,容易造成单点故障,经典案例就是Napster。目前主流的结构化拓扑采用哈希表DHT技术,最大问题是维护机制比较复杂,节点的增加与减少都会产生维护代价。和结构化P2P网络相比,非结构化P2P网络在网络拓扑上没有严格的控制,节点可以随意地加入或离开网络,并不会给网络结构的调整带来太大负担,因此大部分P2P应用系统都是基于非结构化的。
P2P搜索技术评价标准
在对目前主流的非结构化P2P搜索算法进行探究之前,我们先从用户角度和网络的角度给出P2P搜索技术的评价标准。
从用户角度出发,我们最关心的是每次查询能否立即定位成功,每次能查询到多少内容,其中有多少是用户想得到的信息。因此用户一般从返回的结果数、满意度以及响应时间来进行评价。从网络角度出发,一个好的搜索算法搜索效率要高,系统资源利用率要高,要能保证搜索质量,用最少的代价获取最高的质量。
非结构化P2P网络搜索算法的分类
1洪泛算法(3)
Gnutella的Flooding方法,是一种典型的盲目搜索算法。该算法又叫宽度优先搜索方法(BFS)。该算法每次要搜索资源的时候就向它的所有邻居节点发布查询信息。而邻居节点收到该节点的查询信息时,先检查自己是否有该资源信息,如果有,就将满足要求的结果返回给该节点;如果没有,则邻居节点继续以同样的方式向它自己的所有邻居节点发布查询信息,如此反复。这种搜索过程在一开始设定了消息生命周期TTL,来防止无休止的洪泛。
这种算法里每个节点都在TTL周期里不停地洪泛,即使已经查询到正确资源。因此容易造成大量的查询冗余信息,给网络造成负载,在节点规模增大的时候容易造成网络堵塞。因此在实际网络中,需要更合理的搜索方法。
2 Iterative Deeping(4)搜索方法
迭代加深算法是洪泛算法的一种改进,它在查询开始的时候先给TTL设定一个较小的值,当查询进行到TTL为0的时候,检测查询结果,如果满足则停止搜索;如果仍未得到查询结果,就重新开始搜索,并且给TTL一个较大的值。等到TTL再次为0的时候再检测查询结果,如此反复,一直到最后得到满足的查询结果。这个过程中很有可能在比最大深度小很多的时候就搜索到资源,因此和直接以最大深度进行洪泛搜索比起来,可以节省大量的资源。
在好的情况下,这种策略可以很快得到搜索结果,但是因为P2P网络的状况的未知的,最差的时候可能要进行最大规模的查询,这时迭代算法由于多次反复迭代,其查询冗余开销就比直接洪泛更多,占用了更多的网络资源。
3 Random Walk搜索方法
随机漫步算法中,每次查询都是同时发出K个查询消息,而这K个查询消息节点都随机地将查询消息转发给自己的一个邻居节点。每个节点收到查询消息时,先检测该消息标志是否为0,如果不是,则随机选择一个邻居节点转发;如果为0,则直接联系请求者,看查询结果是否满足请求:如果满足,则查询结束;如果不满足,则重新设置消息标志,继续随机漫步。
这种方法只记录成功的搜索,一旦所以来的资源发生变化,中途经过的节点频繁退出,将无法得到反馈调整,节点的偏好准确度就会大为降低,可能导致大的查询延时。
4 Gnutella2(5)
Gnutella2不是Gnutella的继承,它没有在整个P2P网络中使用洪泛算法,它把网络中的节点划分成两种:超级节点和叶子节点。超级节点只存储离它最近的叶子节点的信息,而这些超级节点又共同连接起来形成一个覆盖网络。当某个叶子节点需要搜索资源时,它先从它所连接的超级节点的索引中搜。如果搜索成功,则根据资源所存储的机器IP地址建立连接;如果搜索失败,该超级节点就把这个查询请求转发给它所连接的其它超级节点,如此反复,直至搜索结束。
Gnutella2只是在超级节点向其相连接的超级节点转发信息时才使用洪泛,有效地减少了冗余消息,提高了搜索效率。但超级节点向其邻居超级节点转发查询消息时仍使用洪泛机制,在目前P2P网络规模大、节点数多的情况下,仍存在较多的带宽浪费。
5基于移动Agent(6)的搜索
移动Agent天生就具有分布式的特点,一个基于移动Agent的应用由一组移动Agent构成,每一个Agent根据自身的目标和环境的状况移动到拥有计算机所需资源的节点上进行计算。在进行计算时可能需要与其他Agent进行通信协作,而整个计算机过程则可能会分成多个步骤进行,每一步完成之后,移动Agent都将自主地决定下一步的动作,直至其任务全部完成后才自动消亡。
移动Agent的出现使得计算机之间的通信不再是一台主机调用位于另一台主机上的服务,而是向其它计算机提供可执行的计算过程,通过网络传送的消息也不再仅仅局限于数据,而是包含计算机过程及其所处状态的计算实体,能够较大地减轻网络负载。
结束语
文中对非结构化P2P网络中的搜索方法进行了比较和分析,发现其自身仍存在许多问题,例如:用户需要在P2P网络中获取资源时,预先并不知道这些资源存储在哪个节点,这就使得搜索具有一定的盲目性。而搜索算法本身未提供有效查询TTL,不能及时停止查询,就带来了大量查询冗余消耗。因此,如何选择一个处理能力强、负载轻、带宽高的节点是需要用户考虑的。
总之,非结构化P2P网络电视额搜索算法应有效地改进资源搜索的有效性,减少网络带宽的消耗,降低对网络节点的依赖性,提高搜索精度。为适应实际网络应用,仍需要在优化搜索效率与质量上进行更深入的研究。
摘要：P2P(Peer-to-Peer)网络是分布式网络的最新热点应用,目前流行的大多数P2P网络大都基于非结构化拓扑,这种拓扑利用洪泛方法传播查询信息,但是由于搜索的盲目性,其检索效率又普遍低下。本文分析了各种搜索算法的优势以及存在的缺陷,为高性能的资源搜索算法提出奠定理论基础。
注释
1符飞雄;基于数据转发树的P2P网络搜索研究;重庆大学;2006.
2罗杰文;Peer to Peer(P2P)综述;中科院计算技术研究所;2005-11-3.
3Napster website,http://www.napster.com/.
4Gnutella website,http://www.gnutella.com/.
5基于非结构化P2P网络的资源搜索算法研究.http://wenku.baidu.com/view/4679642ced630b1c59eeb591.heml;2012.
资源搜索算法 篇7
在现代社会中,火灾、爆炸、坍塌事故常有发生,救援过程中因建筑情况不清,意外坍塌事故等导致救援人员遇难的惨剧时有发生。为避免此类事故,应用机器人及时探知险情和受困人员的情况和位置有着极大的应用意义。论文中将机器人所面临的搜救环境抽象为一个迷宫,而搜救就是要在迷宫中先搜索到目标物并带着目标物返回到出发点处。
迷宫的种类[1]有很多,而用的比较普遍的是Perfect迷宫,所谓的Perfect迷宫是一种没有任何环路且没有任何不能到达的区域。本次实验中,所选择的迷宫环境都为Perfect迷宫。目前,经典的搜索路径算法有D*算法和A*算法,而在迷宫中运用最为普遍的搜索算法是泛洪算法,而泛洪算法是一种基于改进的深度优先搜索算法[2]。泛洪算法在搜索过程中多次遇到目标点,但它的目的是要从这些路径中找到最快到达目标点的一条路径,原始的泛洪算法不适合本次实验中的搜救应用,于是,我们在实验中是用深度优先搜索算法进行比较研究。Takayuki Goto,Takeshi Kosaka研究了A*以及D*算法在ITS(智能运输系统)和机器人路径规划中的应用,确定了A*算法以及D*算法的优势[3]。而对于A*算法中启发式函数的选取,已有多种选择。在启发式函数的选取上,有对A*算法估价函数所出现的问题,将距离和角度进行归一化处理[4];也有对当前节点进行评估的思想上,增加了最短路径中当前节点的父节点,并对当前节点与终节点的距离进行了评估,这使得A*算法的搜索方向更加趋向终点,从而提高了搜索速度[5];还有一般情况下对启发式函数的设定选择为两点间的欧几里得距离[6];
本次实验中,将分别对含有三种不同启发式函数的A*算法与深度优先搜索算法用于迷宫中进行比较仿真研究。
1 实验研究
1.1 实验研究方法
实验研究目的是将算法用于现实搜救中,既然是为了搜救,那么时间是关键,搜索迷宫所用时间的长短就成为评价算法优劣的主要因素。对于机器人来说,所处的迷宫环境是未知的,它只能通过传感器感测到目标点所在的大致位置,然后根据算法一步一步的搜索到目标物。从出发点处找到目标物时所耗的时间我们记录为搜索迷宫所用的时间,当然,搜救的目的不仅仅是为了找到目标物,同时是需要在找到目标物后将目标物带回至出发点处。从目标点返回到出发点时,如果沿之前的原路返回,那就会浪费很多没必要的时间,使搜救时间变长,所以我们要做的工作是要将之前的走过的路径进行优化,使机器人带着目标物返回出发点时不用走“冤枉路”,从而节省搜救时间。
真实环境中,目标物在目标点处通过敲打墙壁或地面等发出声音,模拟“呼救”,从而让机器人通过传感器感知到目标物。但由于外界因素(例如:传感器的精度,迷宫环境中障碍物对声音的阻碍作用等)的干扰会导致机器人只能判断出目标物的大致位置,这个大致位置是随着机器人离目标物越来越近而会越来越精确,直至找到目标物。
而在本次仿真实验中,为了能够比较真实的模拟真实环境,我们人为的让目标点坐标产生了一定的偏差,并且让这个偏差值随着机器人越来越靠近目标点而变得越来越小。
1.2 深度优先搜索算法
所谓“深度优先”,即:状态树的生长或展开,首先沿状态树的深度方向进行。深度优先搜索算法需要记录下状态树的生长过程,深度优先搜索算法是一种盲目的搜索算法,搜索中可能很多次的搜索到目标点,深度搜索算法通过不断剪枝,寻找出一条从起始点到目标点最近且最省时的路径,即深度优先搜索算法也是一种全局的搜索算法,这样的深度优先搜索算法运用到未知迷宫搜救中是没有意义的。而本次实验中,深度优先搜索算法是以找到目标物为目的,没有剪枝的步骤,只要搜索到目标物,迷宫的搜索过程就成功退出。
1.3 A*算法
A*算法是人工智能中的一种搜索算法,是一种启发式搜索算法,它不需遍历所有节点,只是利用包含问题启发式信息的评价函数对节点进行排序(Node Ordering),使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价节点处于最短路线上的可能性的度量。A*算法中引入了评估函数,评估函数如下:
其中:n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。仿真实验中,我们为A*实现了三种启发式函数,如引言中所述,一种启发式函数为当前点到目标点的欧几里得距离评估,我们定义为A*(1);
即A*(1)算法的评估函数为:
其中启发式函数h1(i)为当前节点i到偏移目标点的欧几里得距离。
另一种启发式函数在第一种的启发式函数中增加了当前节点的父节点到目标点的欧几里得距离评估,我们定义为A*(2);
A*(2)算法的评估函数为:
j为当前节点的父节点,h2(i)为已评估出的当前节点i的父节点到偏移目标点的距离。
最后一种启发式函数是在第一种启发式函数的评估上加入了当前点到目标点的角度评估,我们定义为A*(3)。
A*(3)算法的评估函数为:
其中,为权重值,取ω1=0.55,ω2=0.45;θ为当前点到偏移目标点的直线与水平线的夹角,α为起始点到实际目标点的直线与水平线的夹角,角度如图2中标示;l为当前点坐标到实际目标点坐标的欧几里得距离,L为起始点到实际目标点坐标的欧几里得距离。
2 仿真实验分析
实验的迷宫环境设置如下图所示,将环境划分为一个一个的栅格,红色栅格为障碍物,白色栅格为通道,生成的10个迷宫均为Pefect迷宫,保证了整个迷宫中至少有一条从起点到目标点的通道并不会产生环路。起点坐标设为(0,0),目标点坐标设为(24,24)。
由于机器人在检测呼救信号时存在不准确因素(例如:传感器的精度,迷宫环境障碍物对声音的阻碍作用等),都会导致机器人在搜索时存在或多或少的误差,所以仿真实验中,为了比较真实的模拟现实搜救环境,我们对目标点做了偏差处理,处理方式如图2中所示。
其中,(xs,ys)为起始点坐标,(x,y)为机器人当前所在位置坐标,(xt',yt')为偏移目标点的坐标,(xt,yt)为实际目标点坐标:
为目标点产生的偏移误差:
其中,k为权重值,通过实验,取得k=40,l为当前点坐标到实际目标点坐标的欧几里得距离,L为起始点到实际目标点坐标的欧几里得距离,rand(-1,1)为随机数,随机数的取值范围为(-1,1)。
实验中,我们将三种A*算法分别在10个不同的Perfect迷宫中运行,统计结果如表1所示。
通过上表的结果分析可知,正如文献3中所述,加入了父节点评估的A*算法(即A*(2))在搜索时,提高了搜索速度;而在文献2中所述的提高搜索速度的优势在本次实验中没有很好的体现出来,这是因为,在本次实验中,我们加入了偏差值,对于A*(3)中的估价函数,不仅在距离上加入了偏差,同时在角度上也加入了偏差,从而使得A*(3)算法在本次搜索中没有优势。从表中我们还可以得出,带有启发式函数的A*算法要优于深度优先搜索算法。
仿真实验中,对于返回路径的优化,我们通过算法设定,让机器人每走过一个栅格都将该栅格的状态标记为“已访问”,被标记为“已访问”的栅格,机器人在搜索时就不会再走,除非遇到是死路的栅格。那么在算法中我们定义两个状态,一个状态是通过栅格的次数(count),另一个状态是栅格是否为分支。当机器人搜索到目标点后,返回时只需要走count为1或者栅格为分支(is Branch=true)的路线就是返回的最优路线,且不会走“冤枉路”。
3 结论
本文通过仿真实验比较了A*算法与深度优先搜索算法在未知迷宫中的搜索应用,仿真实验中还同时比较了三种带有不同启发式函数的A*算法的应用,通过仿真实验比较得出的结果是:总体来说,未知迷宫中,在仅知道目标点的大概位置的情况下,进行搜索时,A*算法要优于深度优先搜索算法,而A*算法在启发式函数不同的情况下,搜索产生的结果也是不同的,从上述仿真实验结果的比较中可以得出,A*(2)算法搜索路径的时间是最优的,其次是A*(1)和A*(3)算法。同时,从实物实验比较结果也可以得出,带有启发式函数的A*算法要优于深度优先搜索算法。深度优先搜索算法在未知迷宫中进行搜索时是盲目的,而A*算法在搜索过程中通过引入启发式信息来实现向目标节点移动的判别,无需遍历地图,使得计算复杂度相对较小,实现了快速、高效。但是,这也导致搜索的过程中排除了大量节点,而由于经验及实际问题的复杂性,引入启发信息的代价函数无法做到完全正确,这些被排除的节点可能就是最优路径的节点之一。
摘要：本文通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在标准迷宫中的应用,在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度。机器人搜索的目的是为了进行搜救,因此机器人应该要在尽量短的时间内搜索到目标物并将目标物带回。通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法。
关键词：迷宫搜索,深度优先搜索算法,A*算法
参考文献
[1]http://www.astrolog.org/labyrnth.htm.
[2]A.Francy Golda,S.Aridha,and D.Elakkiya,"AlgorithmicAgent for Effective Mobile Robot Navigation in anUnknown Environment."Intelligent Agent&Multi-AgentSystems,2009,IAMA 2009.
[3]Takayuki Goto,Takeshi Kosaka,and Hiroshi Noborio,"Onthe Heuristics of A*or A Algorithm in ITS and Robot Path-Planning,"Proceedings of the 2003 IEEE/RSJ InternationalConference on Intelligent Robots and Systems,pp.1159-1166,Oct,2003.
[4]史辉,曹闻,朱述龙,"A*算法的改进及其在路径规划中的应用"[J].测绘与空间地理信息,2009,32,6:208-211.
[5]张仁平,周庆忠,熊伟,"A*算法改进算法及其应用"[J].计算机系统应用,2009,98-100.
三分搜索算法 篇8
众所周知,在没有更多的关于元素组次序的信息时,要找出是否在元素组中的元素,搜索元素组中的所有元素是不可避免的。但当知道元素组按升(降)序排列时,人们往往采用分治法解决。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。根据分治法的分割原则,应把原问题分为多少个子问题才较适宜?每个子问题是否规模相同或怎样才为适当?这些问题一般很难予以肯定的回答。但人们从大量的实践中发现,在用分治法设计算法时,最好使问题的规模大致相同。即将一个问题分成大小相等的k个子问题来处理是行之有效的。许多问题可以取k=2。这种使问题规模大致相等的做法是出自一种平衡子问题的思想,它常常比子问题规模不等的做法要好。
给定已排序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。
二分搜索算法解决这一类问题的基本思想是将这n个元素分成大致相同的两部分,取a[(n-1)/2]与x比较。如果x=a[(n-1)/2],则找到x,算法终止。如果x<a[(n-1)/2],则只须在数组a的左半部继续搜索x。如果x>a[(n-1)/2],则只须在数组a的右半部继续搜索x。具体算法可描述如下[1]。
输入:n个元素的升序数组a[0:n-1]和元素x
输出: 如果x=a[j],1≤j≤n-1,则输出j,否则输出-1。
low←0; high←n-1;j←-1
while(low≤high)and(j=-1)
mid←[(low+high)/2]
if x=a[mid] then j←mid
else if x<a[mid] then high←mid-1
else low←mid+1
end while
return j
容易看出,每执行一次算法的while循环,待搜索数组的大小减少一半。 但在寻找的x大于或等于数组的最大元素时,算法总执行最大次数的比较,即算法并未充分利用最大数(或最小数)。因此,在最坏的情况下,while循环执行了O(log n),循环体内运算需要O(1)时间,整个算法在最坏情况下的计算时间复杂性为O(log n)。由此可见,对搜索元素大于或等于待搜索数组的最大元素时,二分搜索法的效率不如其他情况的效率。要解决这样问题的搜索效率,又兼顾搜索元素在靠近待搜索数组中间位置的搜索效率问题,可采用将待搜索数组大致三等分的搜索方法——三分搜索法来解决。
三分搜索法的基本思想与二分搜索法基本思想类似,将这n个元素分成大致相同的的三部分,取a[(n-1)/3]与x比较。如果x=a[(n-1)/3],则找到x,算法终止。如果x<a[(n-1)/3],则只须在数组a的左三分之一部分中继续搜索x。如果x>a[2(n-1)/3],则只须在数组a的右三分之一部分中继续搜索x。上述两种情况都不成立时,则在数组中间的三分之一部分中继续搜索x。具体算法可描述如下:
输入:n个元素的升序数组a[0:n-1]和元素x
输出:如果x=a[j],1≤j≤n-1,则输出j,否则输出-1。
low←0;high←n-1;j←-1
while(low≤high)and(j=-1)
mid1←[(low+(high-low)/3]
mid2←[(high-(high-low)/3]
if x=a[mid1] then j←mid1
else if x<a[mid1] then high←mid1-1
else if x=a[mid2] then j←mid2
else if x>a[mid2] then low←mid2+1
else low←mid1+1;high←mid2-1
end while
return j
这是从小到大方向上的搜索。容易看出,每执行一次算法的while循环,待搜索数组的大小减少三分之二。在寻找的x等于数组的中间元素时,算法总执行最大次数的比较。因此,在最坏的情况下,while循环执行了O(lg3n),循环体内运算需要O(2)时间,整个算法在最坏情况下的计算时间复杂性为O(lg3n)。对具体n值的数组进行搜索时,虽然三分搜索法在数据搜索时,循环次数减少了,但在一次循环中最坏情况下需要进行数据的两次比较,数据减少量在同等数据的比较量下不如二分搜索法,由于充分利用了待搜索数组的最大数和最小数,在搜索方向的选择上灵活性更强。这是因为对上述算法稍加变化可得从大到小方向上的三分法的搜索算法。
low←0;high←n-1;j←-1
while(low≤high)and(j=-1)
mid1←[low+(high-low)/3]
mid2←[high-(high-low)/3]
if x=a[mid2] then j←mid2
else if x>a[mid2] then low←mid2+1
else if x=a[mid1] then j←mid1
else if x<a[mid1] then high←mid1+1
else low←mid1+1;high←mid2-1
end while
return j
由此当对待搜索数组的结构有所了解,就可以根据搜索数的大体位置选择搜索方向,从而更快捷的搜索出该数在数组中的位置。该算法对某些数据库关于某些已排序字段进行搜索记录给出了一种新的启示。
上面的问题也可利用递归思路解决,其算法可描述如下。
int ternarysearch(int a[],int low,int high,int x)
if (high<low)
j=-1;
else
int mid1=low+(high-low)/3;
int mid2=high-(high-low)/3;
if(x=a[mid1])
j=mid1;
else if(x<a[mid1])
j=ternarysearch(a,low,mid1-1,x);
else if(x=mid2)
j=mid2;
else if(x>a[mid2])
j=ternarysearch(a,mid2+1,high,x);
else
j=ternarysearch(a,mid1+1,mid2-1,x);
return j
这是按数组元素从小到大方向上的三分搜索法的递归算法,同样也可给出从大到小方向上的三分搜索法的递归算法,不再赘述。
摘要：给出了利用最大数(或最小数)的排序元素组的三分搜索法,该方法具有编程简单且易于计算机实现等特点,也可看成是对二分搜索法的补充。
关键词：排序元素,搜索,三分搜索
参考文献
禁忌搜索算法评述 篇9
工程领域内存在大量的优化问题, 对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识, 属于局部优化算法。智能随机算法不依赖问题的性质, 按一定规则搜索解空间, 直到搜索到近似优解或最优解, 属于全局优化算法, 其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法 (Tabu Search, TS) 最早是由Glover在1986年提出, 它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制, 采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦 (破禁) 准则来释放一些被禁忌的优良状态, 以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法, 可以克服搜索过程易于早熟收敛的缺陷而达到全局优化[1]。
迄今为止, TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域, 并显示出极好的研究前景[2,3,4,5,6,7,8,9,11,12,13,14,15]。目前关于TS的研究主要分为对TS算法过程和关键步骤的改进, 用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。
禁忌搜索提出了一种基于智能记忆的框架, 在实际实现过程中可以根据问题的性质做有针对性的设计, 本文在给出禁忌搜索基本流程的基础上, 对如何设计算法中的关键步骤进行了有益的总结和分析。
2 禁忌搜索算法的基本流程
TS算法一般流程描述[1]:
(1) 设定算法参数, 产生初始解x, 置空禁忌表。
(2) 判断是否满足终止条件?若是, 则结束, 并输出结果;否则, 继续以下步骤。
(3) 利用当前解x的邻域结构产生邻域解, 并从中确定若干候选解。
(4) 对候选解判断是否满足藐视准则?若成立, 则用满足藐视准则的最佳状态y替代x成为新的当前解, 并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象, 同时用y替换“best so far”状态, 然后转步骤 (6) ;否则, 继续以下步骤。
(5) 判断候选解对应的各对象的禁忌情况, 选择候选解集中非禁忌对象对应的最佳状态为新的当前解, 同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。
(6) 转步骤 (2) 。
算法可用图1所示的流程图更为直观的描述。
3 禁忌搜索算法中的关键设计
3.1 编码及初始解的构造
禁忌搜索算法首先要对待求解的问题进行抽象, 分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略, 主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示[2], 十进制编码将问题的解用一个十进制串来表示[3], 实数编码将问题的解用一个实数来表示[4], 在某些组合优化问题中, 还经常使用混合编码[5]、0-1矩阵编码等。
禁忌搜索对初始解的依赖较大, 好的初始解往往会提高最终的优化效果。初始解的构造可以随机产生, 但效果往往不够理想, 通常是基于问题特征信息, 借助一些启发式方法产生, 以保证初始解的性能。
3.2 邻域移动、邻域解及邻域解规模
邻域移动, 相关文献也称作邻域操作、邻域结构、邻域变换等。禁忌搜索要想不断进行就要依赖邻域移动来不断拓展搜索空间, 邻域移动是在当前解的基础上, 按照特定的移动策略产生一定数目的新解, 这些新解被称为邻域解, 新解的数目称为邻域解规模。邻域移动的设计通常与问题有关, 如排列置换类组合优化问题, 常用的邻域移动方法是交换、插入、逆序等[3,6,7,8]。不同的移动将导致邻域解个数及其变化情况的不同, 进而影响搜索的质量和效率。在一些应用中为了取得好的搜索效果, 会根据搜索的进展情况动态改变邻域移动策略, 即变邻域移动[9]。邻域移动的设计策略既要保证变化的有效性还要保证变化的平滑性, 即产生的邻域解和当前解既有不同, 又不能差异太大。不同使搜索过程向前进行, 不能差异太大保证搜索是有序而非随机的搜索。邻域解的规模, 也并不总是取可产生邻域解个数的上限, 可以根据需要和经验设定成小于上限的值, 以提高搜索的运行效率。
3.3 解的评价函数
解的评价函数, 相关文献又称其为适应值函数、适配值函数或适应度函数。对于禁忌搜索空间中的解, 通过评价函数来计算其对应的评价函数值, 评价函数值的大小代表了解的优劣程度。根据问题的特性, 可能评价函数值越大越好, 反之也可能越小越好。依据数学方法, 两种目标可以等价转换。直接把优化目标作为评价函数是一种简单、直观的方法, 同时任何与优化目标等价的变换函数也可以作为评价函数。有时, 目标函数的计算困难或是耗时较多, 则可以取体现问题目标的特征值来替代计算, 但必须要保证特征值与问题目标有一致的最优性。
与遗传算法的评价函数类似, 在求解带有约束的优化问题时, 可以将解违反约束的情况作为惩罚因子加入评价函数, 从而规避传统启发式方法中对于约束的复杂处理。基本形式如公式 (1) 。
其中, P (Rj, x) 为第j个约束的惩罚值, 当解满足约束时, 惩罚值为0。关于评价函数的设计详见文献[10]。
3.4 禁忌表、禁忌对象、禁忌长度、候选解及禁忌频率
禁忌表是用来存放禁忌对象的一个容器, 被放入禁忌表中的禁忌对象在解禁之前不能被再次搜索, 可见禁忌表模拟了人的记忆机制, 防止搜索陷入局部最优, 进而探索更多的搜索空间。禁忌表可以使用数组、队列、栈、链表等顺序结构实现, 每个顺序结构的元素定义根据具体问题确定。
禁忌对象就是放入禁忌表中的元素, 归纳而言, 禁忌对象通常可选取状态 (解的编码) 本身或状态分量或适配值的变化等, 禁忌范围依次扩大[1]。其中选取状态本身易于理解, 也最为常用, 禁忌范围最小。
禁忌长度就是每个禁忌对象在禁忌表中的生存时间, 也称为禁忌对象的任期。当一个禁忌对象加入禁忌表时, 设置其任期为禁忌长度值, 搜索过程每迭代一次, 禁忌表中的各禁忌对象的任期自动减1, 当某一禁忌对象任期为0时, 将其从禁忌表中删除。任期不为0的禁忌对象处于禁忌状态, 不能被搜索过程选为新解。
候选解是当前解邻域解集的一个子集。搜索中为了减少搜索的代价 (包括空间和时间) , 要求禁忌长度和候选解集尽量小, 但禁忌长度过小将使搜索无法跳出局部最小, 候选解集过小将使搜索早熟收敛。候选解集的大小常根据问题特性和对算法的要求确定, 禁忌长度的选取则主要有静态和动态两种方法。静态方法是指在搜索过程中, 禁忌长度是一个固定值, 比如, 其中n为问题维数或规模。动态方法是指在搜索过程中, 禁忌长度也是动态变化的, 当算法搜索能力较强时, 可以增大禁忌长度从而延续当前的搜索能力, 并避免搜索陷入局部优解, 反之亦然。
禁忌频率记录每个禁忌对象出现在禁忌表中的次数, 以此作为搜索过程的重要参考, 如若某个对象出现频繁, 则可以增加禁忌长度来避免循环。此外可以把某对象的禁忌频率作为评价解的因素加入评价函数来指导搜索过程。
3.5 特赦准则
特赦准则, 相关文献也称为藐视准则、破禁准则[11]、释放准则等。特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解 (或状态) 被禁时, 能够释放特定解 (或状态) , 从而实现高效的全局优化搜索。
3.6 终止准则
终止准则也称停止准则, 即算法在何条件下停止搜索过程。实际应用中无法使用在禁忌长度充分大的条件下实现状态空间的遍历这一理论收敛条件, 往往使用如下近似终止 (收敛) 准则。
(1) 算法迭代次数达到指定最大次数停止[8,11]。
(2) 最优解的目标函数值小于指定误差。
(3) 最优解的禁忌频率达到指定值。
4 总结和展望
本文简述了禁忌搜索算法的发展、特点及应用, 给出了基本禁忌搜索算法实现的流程, 对禁忌搜索设计过程中的关键步骤进行了分析和总结, 为推广禁忌搜索算法在优化领域的应用有一定意义。
今后关于禁忌搜索算法的研究热点主要有以下几个方面。
(1) 与其他优化算法结合, 如与传统启发式算法、遗传算法、模拟退火算法、粒子群算法、神经网络算法、蚁群算法、混沌算法等结合, 构成更新型的混合优化算法[2,4,5,12,13,14,15]。
(2) 为推广禁忌搜索算法在超大规模优化领域中的应用, 突破禁忌搜索的串行性限制, 研究并行禁忌搜索算法。包括基于问题空间分解的并行策略和基于多禁忌搜索任务的并行策略[1]。
(3) 对禁忌搜索算法本身的关键步骤进行改良设计。如根据禁忌频率信息在算法中增加集中搜索和分散搜索, 分别实现优良区域的重点搜索和搜索范围的扩展。
(4) 探索禁忌搜索算法适于应用的新的优化领域。