动态二进制搜索算法（共5篇）
动态二进制搜索算法 篇1
1. 引言
RFID系统在客观应用时,读写器范围内出现多个标签同时识读的现象是很普遍的。这就会导致多个标签同时向读写器传输数据而产生碰撞,进而致使读写器接收数据失败。因此,多标签碰撞问题[1]是RFID系统进行广泛应用的难点和瓶颈所在,应当给予重点研究。
2. RFI D系统防碰撞算法分析
2.1 算法分类
目前,解决多标签碰撞问题的方法有多种。在无线电技术中,通常有四种:时分多址(TDMA)法、码分多址(CDMA)法、空分多址(SDMA)法、频分多路(FDMA)法。而对RFID系统来说,时分多址法是目前应用最为广泛的方法。时分多址[2]法从形式上又分为标签控制法和读写器控制法两类。这两类方法又包含多种防碰撞算法,如表1所示。
2.2 典型读写器控制法分析
从应用的角度考虑,对于存在大量待读标签的情况,二进制搜索算法比Aloha算法识别的准确性和效率要高。下面对读写器控制法中的各类二进制算法加以分析比较。
(1)二进制搜索算法
二进制防碰撞算法[3]的基本思想是将发生碰撞的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集01分成00和01两个子集,依次类推,直到识别出子集0中的所有标签,再按此步骤查询子集1。
该算法实现的关键在于:(1)要RFID系统同步,对于每个标签,都需要一个附加机制以产生随机数。(2)须有合适的位编码法(如曼彻斯特编码),以能识别出读写器中数据碰撞的比特的准确位置。(3)用标签序列号(EPC ID)唯一的特性[4]。(4)计一组有效的指令规则,高效、迅速地达到选择标签的目的[4]。
(2)动态二进制搜索算法
该算法是在二进制搜索算法基础上对数据传送时间进行缩短改进以提高效率的一种算法。其算法原理[5]是把数据分成两部分,收发双方各自传送其中一部分数据,当标签ID与查询前缀相符时,标签响应只发送其余的比特位,把传输的数据量减小到一半,达到缩短数据传送时间的目的来提高读取效率。
(3)跳跃式动态树形防碰撞算法
该算法在性能上均优于二进制搜索算法与动态二进制搜索算法。根据碰撞时的特点,跳跃式前后搜寻。识别N个标签,共需要问询2N-1次[6]。与二进制搜索算法主要有三点区别:
(1)在一个标签的EPC被识别后,跳跃式反碰撞算法的过程不是二进制搜索算法的重复[4]。阅读器发送的下一个代码所识别标签所在节点的父节点代码。
(2)在阅读器开始发送问询命令时,只发送代码“1”而不是发送与标签EPC等长的全1代码[4]。
(3)在下一个问询命令中,阅读器只发送若干位,而不像二进制搜索算法那样发送全位EPC值。
2.3 文献[4]算法分析
文献[4]中,提出了一种反碰撞改进算法。该算法在基于二进制搜索算法与跳跃式动态树形反碰撞算法约定的基础上,增添了两点不同的约定。其中一点约定是:由于二进制位上的取值具有相互排斥特性(非1即0),所以假如只有一位二进制位发生碰撞,则阅读器不需要发送请求命令而能够自动识别出这两个标签。但是,从技术实现的角度来讲,识别时还是需要对这两个标签进行一次辨别。否则,读写器本身是无法识读的。为此,该算法对文献中8个标签识读重复搜索的次数应当是9次。不过,该算法较其它典型的二进制算法性能优越很多。其最大优越性在于,由0与1的反复置换中,增大了与问询标签序列号相吻合的几率,从而大大缩短了查询的时间,减少了查询的次数,提高了检测效率。但由于该改进算法的目标是当碰撞连续发生时提高标签的识别速度,故其局限性在于,只适合标签碰撞位连续的情况。
3. 基于跳跃式动态树的二进制搜索改进算法
改进算法是受文献[4]中算法约定思维的启迪,在融合二进制搜索算法、跳跃式动态树形反碰撞算法、轮询法三种算法的思想和原理的前提下,提出的一种算法。与动态二进制搜索算法分两部分传输数据的原理不同。较文献[4]中算法在碰撞位状态上有所扩展。
3.1 算法提出
与二进制搜索算法和跳跃式动态树形防碰撞算法相同。需存在以下约定:(1)使用曼彻斯特编码。目的使读写器能够准确发现碰撞的比特位置。(2)要求所有标签能够在同一时刻响应阅读器的问询,以便标签能够同步发送它们的EPC值给读写器。(3)引入以下四个命令:第一个是请求命令。读写器发送一序列号(EPC值)作为请求命令进行询问。当标签序列号小于或等于请求命令序列号时,则回送其序列号给读写器。第二个是选择命令。读写器收到标签的EPC值后,若无碰撞发生,读写器就会选择这个标签,进行数据的传送。第三个是读写命令。根据读写命令来处理存储在标签内部的数据信息[4]。第四个是屏蔽命令。将已经读取到的标签进行屏蔽,使标签不在回应读写器的请求命令。
算法原理:首先,读写器发送问询代码“1”进行询问,让所有标签响应以确定所有碰撞位。而后,将所有碰撞位置0,将此EPC值作为下一步请求命令。无碰撞读标签并将其屏蔽。若存在碰撞,按照比特位由低到高的顺序,对碰撞位进行X个“1”(这里,X值由1-N,N为发生碰撞的位数)的全排列轮询,每一个排列序列号(EPC值)就是下一次的请求命令。在执行置0或置1全排列轮询的过程中,无碰撞读标签并将其屏蔽。若发生一位碰撞,在保持该排列序列号不变的基础上,将碰撞为置1,作为下一次的请求命令,即可读取标签并将其屏蔽。随后,继续执行碰撞位置1的全排列轮询,直至读取识读范围内的所有标签为止。
3.2 算法工作流程
(1)标签进入读写器的识读范围后,读写器发出发送问询代码“1”进行询问,让所有标签响应以确定所有碰撞位。将所有碰撞位置0,将此序列号作为下一个请求命令。(2)置0后,执行请求命令,无碰撞,依次执行选择命令、读写命令、屏蔽命令。(3)有一位碰撞,碰撞位置1,将此序列号作为请求命令。而后对标签依次执行选择命令、读写命令、屏蔽命令。(4)对碰撞位按照比特位由低到高的顺序,执行置1全排列。首先,将一位“1”在碰撞为做全排列轮询。无碰撞,读取标签。发生一位碰撞,碰撞位置1读取标签。一位置1全排列完成后,将“11”在碰撞位进行全排列。如此循环,一直完成N位(N为发生碰撞的位数)置1全排列,直至读取读写器范围内的所有待读标签为止。
4. 性能比较
防碰撞算法的最终目的是为了提高识读标签的速度与准确性,以完成读写器与标签之间数据的传送。下面通过具体的示例来进行算法性能的比较分析。
示例一:碰撞位连续的情况
有8张标签卡[4],序列号分别是:卡1:10000010;卡2:10001010;卡3:10010010;卡4:10011010;卡5:10100010;卡6:10101010;卡7:10110010;卡8:10111010。
改进算法识读过程:
第1次,读写器发出发送问询代码“1”进行询问,标签响应后读写器收到碰撞序列号为:10★★★010,可知第3、4、5位发生连续碰撞。将其均置为0,并将序列号(10000010)作为下一次请求命令。
第2次,读写器发出发送问询代码“10000010”进行询问。这时只有卡1响应,读写器对卡1完成选择、读写、屏蔽的过程。而后,对碰撞位按照比特位由低到高的顺序进行一位置1全排列轮询。首先得序列号(10001010),将其作为下一次请求命令。
第3次,读写器发出发送问询代码“10001010”进行询问。这时只有卡2响应,读写器对卡2完成选择、读写、屏蔽的过程。这时,继续执行一位置1全排列轮询。得序列号(10010010),将其作为下一次请求命令。
第4次,读写器发出发送问询代码“10010010”进行询问。这时只有卡3响应,读写器对卡3完成选择、读写、屏蔽的过程。这时,继续执行一位置1全排列轮询。得序列号(10100010),将其作为下一次请求命令。
第5次,读写器发出发送问询代码“10100010”进行询问。这时只有卡5响应,读写器对卡5完成选择、读写、屏蔽的过程。至此,一位置1全排列结束,读写器将按照比特位由低到高的顺序进行二位置1全排列轮询。得到序列号(10011010),将其作为下一次请求命令。
第6次,读写器发出发送问询代码“10011010”进行询问。这时只有卡4响应,读写器对卡4完成选择、读写、屏蔽的过程。这时,继续执行二位置1全排列轮询。得序列号(10110010),将其作为下一次请求命令。
第7次,读写器发出发送问询代码“10110010”进行询问。这时只有卡7响应,读写器对卡7完成选择、读写、屏蔽的过程。这时,继续执行二位置1全排列轮询。得序列号(10101010),将其作为下一次请求命令。
第8次,读写器发出发送问询代码“10101010”进行询问。这时只有卡6响应,读写器对卡6完成选择、读写、屏蔽的过程。至此,二位置1全排列结束,读写器将按照比特位由低到高的顺序进行三位置1全排列轮询。得到序列号(10111010),将其作为下一次请求命令。
第9次,读写器发出发送问询代码“10111010”进行询问。这时只有卡8响应,读写器对卡8完成选择、读写、屏蔽的过程。至此,所有标签识读完毕。
其它算法识读:跳跃式动态树形防碰撞算法根据其算法规律可知识读次数为15次。动态二进制搜索算法识读次数为28次。二进制搜索算法将会更多。文献[4]改进算法识读次数为9次。
示例二:碰撞位不连续的情况
有3张标签卡,序列号分别是:卡1:11010111;卡2:11010101;卡3:11111101。
改进算法识读过程详见表2所示。
其它算法识读:跳跃式动态树形防碰撞算法根据其算法规律可知识读次数为5次。动态二进制搜索算法与二进制搜索算法识读次数分别为7次和9次。
由上述示例可知,不同标签数各种算法对两个示例的识读次数比较见表3所示。
由表中显示的数据可以看出:对于相同数量的标签在识读时,改进算法的识读性能比上述四种算法均优越。当标签数量增大时,改进算法的识读次数增加幅度不大,而其它算法的增加幅度都比较大。并且改进算法识读次数相对于标签数量的增加幅度也是最少的。同时,改进算法对于标签碰撞位连续和不连续的情况都适合。
5. 结束语
本文提出的改进算法是基于二进制搜索、跳跃式动态数形防碰撞算法基础上改进的一种多标签识别防碰撞算法。它是将二进制的分群(0和1)、跳跃式的初始碰撞位检测及序列号轮询进行融合,并渗入数学中的全排列方法原理,提出的一种算法实现。
该算法的最大优越性在于:一次性检测碰撞,以后一直进行序列号置1的全排列轮询,不用重复进行碰撞位检测,从而大大缩减了防碰撞检测的时间;对标签碰撞位连续与不连续情况均适用,实际应用性强;更适宜对大量的标签进行读取识别,并能够有效的缩短识读时间;不仅可应用于多标签防碰撞的识别上,而且由于其识读次数与与标签数相差不大,识别速度快,还有望应用于检测标签(物体)的数量上。这些对提高RFID系统的防碰撞性能显得尤为重要。
参考文献
[1]Klaus Finkenzeller,RFID-Handbook Fundamentals and Applications in Contactless Smart Cards Identification[M](2nd Edition),2003.
[2]L.Burdet,RFID multiple access methods[A],Technical Report ETH Zurich,2004.
[3]Vogt H,Mutiple Objet Identification with Passive RFID Tags Systems,Man and Cybernetics[A].2002IEE International Conference,2002:6-9.
[4]王亚奇,一种改进的RFI D系统反碰撞算法[J].单片机与嵌入式系统应用,2007,(9):16—17.
[5]李兴鹤,胡咏梅,王华莲等,基于动态二进制的二叉树搜索结构RFI D反碰撞算法[J].山东科学,2006,19(2):51—55.
[6]余松森,詹宜巨,王志平等,跳跃式动态树形反碰撞算法及其分析[J].计算机工程,2005,31(9):19—20,26.
动态二进制搜索算法 篇2
RFID是一种非接触式的自动识别技术,它通过无线电射频信号识别目标并获取目标信息。根据标签能量和调制方式的不同,可以将R F I D系统分成两类:有源RFID系统和无源RFID系统。有源RFID系统由标签中的电池为标签提供能量,无源RFID标签从阅读器通过天线发送的无线电波接收能量。有源系统可以支持更远距离的通信和更高的通信速率,其通信范围可以达到100米,传输速率可达2Mbps。使其在很多应用领域都很有优势。有源RFID系统设计的关键技术就是防碰撞算法的设计。本文提出了一种后退式二进制搜索算法,并将其与现存的算法做了对比。解决了现阶段有源有源R F I D系统的多标签防碰撞和低功耗问题。
目前,有源R F I D由于各方面原因还没有标准的防碰撞算法,常用的防碰撞算法有以下2种:ALOHA算法和CSMA/CA算法[1]。其中最常用的是基于ALOHA算法,ALOHA算法采用标签随机发送,因此算法随机性较大。C S M A/C A算法是相对于A L O H A算法增加了射频信号检测功能。A L O H A和C S M A/C A算法都属于非确定性防碰撞算法,当标签数量较多时,A L O H A和CSMA/CA算法都会产生帧冲突严重,信道利用率很低等问题。将会导致功耗高、识别率低和标签饥饿等问题。实际应用可行性较低。A L O H A和C S M A/C A算法只能适用于标签较少、且可靠性要求不高的应用场合。不适合大规模标签读取。
本文提出了一种基于后退式二进制搜索算法的有源RFID系统防碰撞算法。后退式二进制搜索算法是一种确定性搜索算法。可以从根本上解决A L O H A和C S M A/C A算法所固有的缺点。算法识别准确度高,速度快,效率高,适合于大规模标签读取[2]。
2防碰撞算法的几点约定
2.1有源RFID碰撞检测方法
由于有源RFID硬件无法检测碰撞是否产生,因此采用软件方法判断碰撞。碰撞检测方法:当读卡器检测到射频信号且没有接收到标签信息时,说明此时有碰撞产生。
2.2算法中的报文类型
为了便于描述算法,引入了3种报文类型
1、Broadcast广播报文:由读卡器发送给标签,当标签收到广播报文时,标签进入接收碰撞报文模式。
2、Collision碰撞报文:由读卡器发送给标签,报文包含掩码值D和掩码长度L。(匹配原则:收到碰撞报文的标签将自己的ID号的最低L位与掩码值D比较,当相等时,标签响应,发送自己的ID)。
3、ID信息报文:由标签发出,当标签收到的碰撞报文与自己的ID号匹配时,应答ID报文,报文包含自己的ID号[3]。
4、Quiet休眠命令报文:由读卡器发送给指定ID的标签,对应ID的标签进入低功耗模式,等待下一个唤醒周期。
2.3标签工作模式设置:
1、设置标签唤醒周期为1秒,时间为500微秒,即标签每隔1秒被唤醒,唤醒后待机时间为500微秒,没有接收到广播报文后立即休眠。
2、设置标签ID号长度为1个字节。
3后退式二进制搜索算法
3.1算法实现
标签ID号长度为32位(4个字节),假设阅读器作用区域内有8个标签(ID号分别为00 00 00 01-00 00 0008,下面以1-8代替)。开始时,读卡器对区域内标签数量为未知状态。具体算法实现过程如下
首先当读卡器串口接收到扫描标签命令时,读卡器发送广播报文,连续发送1秒的广播报文,唤醒区域类所有标签。
1、读卡器发送碰撞报文(D=0,L=1)。标签2、4、6、8应答,读卡器检测到碰撞发生。
2、读卡器发送碰撞报文(D=00,L=2)。标签4、8应答,读卡器检测到碰撞发生。
3、读卡器发送碰撞报文(D=000,L=3)。标签8应答,识别标签8。
4、读卡器发送休眠命令报文,指定标签8休眠,标签8收到报文后休眠。
5、读卡器发送碰撞报文(D=100,L=3)。标签4应答,识别标签4。
6、读卡器发送休眠命令报文,指定标签4休眠,标签4收到报文后休眠。
7、读卡器发送碰撞报文(D=10,L=2)。标签2、6应答,读卡器检测到碰撞发生。
8、读卡器发送碰撞报文(D=010,L=3)。标签2应答,识别标签2。
9、卡器发送休眠命令报文,指定标签2休眠,标签2收到报文后休眠。
10、器发送碰撞报文(D=110,L=3)。标签6应答,识别标签6。
11、卡器发送休眠命令报文,指定标签6休眠,标签6收到报文后休眠。
12、卡器发送碰撞报文(D=1,L=1)。标签1、3、5、7应答,读卡器检测到碰撞发生。
13、卡器发送碰撞报文(D=01,L=2)。标签1、5应答,读卡器检测到碰撞发生。
14、卡器发送碰撞报文(D=001,L=3)。标签1应答,识别标签1。
15、卡器发送休眠命令报文,指定标签1休眠,标签1收到报文后休眠。
16、卡器发送碰撞报文(D=101,L=3)。标签5应答,识别标签5。
17、卡器发送休眠命令报文,指定标签5休眠,标签5收到报文后休眠。
18、卡器发送碰撞报文(D=11,L=2)。标签3、7应答,读卡器检测到碰撞发生。
19、卡器发送碰撞报文(D=011,L=3)。标签3应答,识别标签3。
20、卡器发送休眠命令报文,指定标签3休眠,标签3收到报文后休眠。
21、卡器发送碰撞报文(D=111,L=3)。标签7应答,识别标签7。
22、卡器发送休眠命令报文,指定标签7休眠,标签7收到报文后休眠。
标签搜索完毕,所有标签1-8被准确识别。由于采用了二级制树搜索算法,搜索过程中不会产生标签冲突的情况,同时能准确的搜索出范围内的所有标签,当标签数量规模较大时,传统A L O H A算法将会出现大量冲突,识别准确度很低。而采用本算法则不会出现标签冲突的情况。因此能体现出此算法搜索准确度高的优势。
3.2算法性能分析
后退式二进制搜索算法识别N个标签所需查询次数为S(N)=2N-1。在最不理想的情况下,可以保证N个标签的最大查询次数为2N-1。从上述有源RFID后退式二级制搜索算法实例过程和图1所示,当区域内存在8个有源RFID标签时,查询次数为14次,读卡器和标签之间的交互次数为22次(包括查询次数14次和休眠报文次数8次)。具有后退式二进制搜索算法搜索速度快、识别精度高的特点[4]。
本有源R F I D系统标签采用被动工作模式,标签定时唤醒。为了提高响应速度,标签唤醒周期为1秒,唤醒后待机时间为500us,待机电流以12m A为例,300m Ah的电池可用5.5年[5]。在不影响系统响应速度和识别精度的前提下,标签有较低的功耗。
此算法彻底解决了A L O H A等非确定性防碰撞算法功耗高、识别率低和标签饥饿的问题。因此,后退式二进制搜索有源R F I D防碰撞算法相对于现有A L O H A算法具有识别速度快、精度高、功耗低、可靠性好的优势。
4算法在2.45G有源RFID系统环境的实现
为了验证算法的有效性,我们在基于Nordic公司的最新低功耗2.45G无线收发芯片n RF24LE1基础上开发了一套2.45G有源RFID系统,包括标签和读卡器。2.45G有源RFID标签硬件框图如图3所示。
在以上硬件平台上,我们在M D K软件平台上采用C开发了读写器和标签软件系统,n RF24LE1 2.4g收发模块初始化程序如下:
实际测试中在读卡器区域放置了8个标签(标签ID号分别为00 00 00 01-00 00 00 08)。标签ID为4个字节。测试结果如下图所示,从串口终端中搜索到的标签信息可以看出,按照本搜索算法依次搜索出标签00 0000 08、00 00 00 04、00 00 00 02、00 00 00 06、00 0000 01、00 00 00 05、00 00 00 03、00 00 00 07[6]。实际标签搜索过程和算法理论分析完全一致,验证了后退式二进制搜索防碰撞算法在有源RFID系统应用中具有识别速度快、精度高、功耗低、可靠性好的优点。
5结束语
本文介绍了一种新颖的基于后退式二进制搜索的有源RFID系统防碰撞算法。此算法是在二进制搜索算法的基础上,结合有源RFID系统改进的一种新型算法。通过算法理论分析和实际2.45G有源RFID硬件平台测试。采用此算法后的有源R F I D系统相对于ALOHA等非确定性防碰撞算法具有识别速度快、识别精度高、功耗低、稳定性好、可靠性高的特点。特别是在标签数量较多的情况下,此算法的优势极为明显。
参考文献
[1]谢振华,赖声礼,陈鹏.标签防冲撞算法设计[J].计算机工程,2008,6.
[2]宁焕生,张彦.RFID产品研发及生产关键技术[M].电子工业出版社,2007,3.
[3]余松森,詹宜巨,王志平,唐忠平.跳跃式动态树形反碰撞算法及其分析[J].计算机工程,2005,9.
[4]陈博.一种类二进制搜索的RFID系统反碰撞算法及其实现[J].电子器件,2006,3(29).
[5]KALINWSKI R,LATTEUX M,SIMPWT D.Anadaptive anti-collision protocol for smart labels[J].2001.
动态二进制搜索算法 篇3
大部分动态车间调度研究都专注于问题规模、算法收敛速度而忽略了工件本身的数据结构和它们之间可能存在的关系。于是, Mohammad提出了一种改进的变邻域搜索算法 (Modified Variable Neighborhood Search, MVNS) , 即搜索前采用K-means聚类后, 利用工件之间的距离来得到更好的结果。但是, 变邻域搜索较为简单, 对所得结果准确度的提升有限。而GA等算法在迭代时因群组过大会出现耗时太长的问题, 因此, 本文采用将分散搜索与改进的变邻域搜索相结合的方式来完成全局搜索。在大规模的车间调度下, 采用这种全新的混合分散搜索算法 (Hybrid Scatter Search, HSS) 来解决动态车间调度问题对实时性有较高的要求。实验结果显示, 与现有的几种动态车间调度算法相比, 这种新的算法得到了更好的结果, 凸显了其实时性和高效性。
1 混合分散搜索算法 (HSS)
与静态车间调度问题相比, 动态车间调度问题中所有的工件并不是在调度一开始就到达的, 而是随着调度的进行而逐渐到达工厂。除此之外, 在动态车间调度问题中, 我们还需要考虑机器的损坏。动态车间调度算法就是解决如何在这种情况下找到一种优化的工件调度序列。
分散搜索算法 (Scatter Search, SS) 是一种已经被成功应用到很多领域来解决优化问题的算法。由于分散搜索的每个步骤都是独立的, 可以分别改进, 因此具有很高的可调整性。除了五个标准的部分外, 我们还在分散搜索中引入了精英策略, 以确保最好的调度个体不会在进化过程中遗失。图1所示为混合分散搜索算法流程。
动态环境中, 机器故障和新工件的增加使得原来的调度已不再适应新的局面。因此, 在发生这些事件时, 需要重新调度。图2所示为实时动态系统。在初始状态下, 有3 个工件, 每个工件有3个工序, 其加工时间都为1.图2 (a) 为整个系统的初始态;图2 (b) 为在正常运行条件下且时间等于1 时, 工件1, 2, 3 的第一个工序均已完成;图2 (c) 中的机器3 发生了故障, 维修时间为1, 系统重新调度, 将工件2 的第二个工序的加工时间延迟了1;图2 (d) 为新工件到来, 可以看到工件4 被置于整个调度中。
本文研究的是10 台机器 (6 台机器以上为复杂的车间调度问题) 处理300 个工件, 每个工件有10 个工序, 每个工序的处理时间均平均分布, 工件到达车间的时间按照泊松分布。在计算平均流程时间时, 由于工件会无休止地到来, 因此采用从稳定态到某一个时间点的算法计算。这种计算方法避免了初始态不稳定的情况对结果造成影响。
1.1 编码方法和适应度函数
在车间调度算法中, 一个关键问题是如何将一个调度计划编码成一种合适的形式。不同的编码架构有不同的优缺点。在研究中, 我们采用了一种基于工序的表示方式。采用这种编码方式可将一种调度计划编码成一个工件编号的序列。假设每一个工件都必须在m个机器上加工一次, 在这种编码方式下, 每个工件编号都将出现m次。通过从左到右依次对编码序列扫描, 我们得到的第k次出现的某个工件编号代表了这个工件的第k个工序。比如, [2 1 3 2 3 3 1 1 2]这串序列就代表了以下这些工序的排序:[O21, O11, O31, O22, O32, O33, O12, O13, O23], 其工件的加工顺序如图3 所示。
适应度函数是车间调度问题中的另一个关键性问题。我们用适应度函数来评价所得到的不同调度计划的表现优劣。在静态车间调度问题中, 我们的优化目标是最小化调度计划的总制造时长 (makespan) 。然而, 在动态车间调度问题中, 通常, 我们的优化目标是最小化所有工件的平均制造时间。在本文中, 一个调度计划S的目标函数被定义为:
式 (1) 中:n为当前已经完成的工件个数;tck为第k个工件的完成时间;trk为第k个工件的到达时间。
1.2 多样性生产方法
基于给定的初始解, 多样性生成方法将产生一组多样性的调度计划作为整个分散搜索算法的第一代解。“多样性”这个词的含义可以理解为, 产生的这些第一代调度计划和初始解具有很大的不同, 并且每个解之间也具有很大的差异。生成的方法可用以下公式表示:
S (h∶t) ={[t], [t+h], [t+2h], …, [t+rh]}. (2) 式 (2) 中:h待定;t=1, 2, …, h, t+rh<l, l为初始解长度。
比如, 给定初始解p= (1, 2, 3, 4, 5, 6, 7, 8) , 如果我们选择h=4 作为多样性生成方法的参数, 那么将得到
p (4∶4) = (4, 8) , p (4∶3) = (4, 8) , p (4∶2) = (2, 6) , p (4∶1) = (1, 5) 。合并这4 个集合, 我们将得到一个新解p (4) = (4, 8, 3, 7, 2, 6, 1, 5) 。类似地, h取n个不同的值, 就可以得到n个不同的解。
1.3 改进部分:结合聚类的变邻域搜索
在用于解决静态车间调度问题的分散搜索中, 这个步骤则为简单的局部搜索。本文采用了结合MVNS的搜索方法:在工件进入车间后, 我们会根据工件本身的特性, 即在各个机器上所需的加工时间用K-means对其聚类。聚类的依据为加工时间的相似度, 相似度越高, 越可能被分为一类。这个分类信息在接下来的交换和插入中会被用到。简单来说, 相距越远的两个类中的工件, 越容易被选中并进行变换, 距离计算公式可参考公式 (2) 。由于距离越远, 意味着两个工件的加工时间差异越大, 交换或者插入这两个工件越容易使整个调度产生更大的变化, 从而使整个搜索变快, 更快地取得更出色的解。
总体的思路如下:
初始化:选择一组用于搜索的邻域Ni (i=1, 2, …, imax) , 产生一个初始解, 设置终止条件 (迭代次数为N) 、设置聚类数。用K-means完成聚类, 计算各类中心之间的距离。
重复以下步骤直至满足终止条件: (1) 设置i←1. (2) 重复以上步骤, 直到i=imax. (3) 随机搜索。根据聚类中心的距离, 随机在第i层产生解x´ (x´∈Ni (x) ) 。 (4) 局部搜索。将上一步得到的x´作为初始解进行局部搜索, 得到局部最优解x´´. (5) 更新。如果x´´比x´好, 则用x´´代替x´, 并在N1 (i←1) 中继续搜索;否则, i←i+1.
VNS算法非常简单、有效, 已经被广泛运用于很多这类问题的优化中。简单来说, VNS的中心思想是在初始解的附近搜索, 如果没有找到比初始解更好的解, 则跳到下一层, 直至k层;如果有比初始解更好的解, 则替换初始解再搜索, 原理如图4 所示。VNS算法优于一般局部搜索之处在于, 它的搜索范围在不断变动, 更加灵活, 所以收敛速度也快得多。
对于VNS算法中“邻域”的定义, 本文采用的是交换和插入, 其中, 交换是指两个工序交换位置, 互相替代;插入是指一个工序插到另一个工序之前。这里要变换的两个工序并不是完全随机挑选的, 而是要结合K-means算法的结果。在这个调度算法中, K-means算法的分类依据为最小方差和, 具体计算公式如下:
式 (3) (4) 中:k为分类的数量;Xij表示第j个工件被分在第i类;Ci为第i类的中心;ni为第i类工件的个数。
1.4 精英策略和引用集
在改良方法、优化步骤之后, 我们对组内所有的调度计划进行了精英策略操作。迭代时, 保留这一代中最好的解, 用来替换下一代中最差的解。原来的分散搜索中没有这个操作, 所以会在迭代过程中丢失暂时取得的最优解。
分散搜索中的引用集是一个兼具多样性和强化性这两个关键特性的解集。根据引用集, 我们可以得到子集。子集的形式为 (x, y) , 其中, (x, y) 均来自引用集。根据不同的方法, 我们将得到3 个子集: (1) 根据引用集A中的解, 两两组合得到; (2) 根据引用集B中的解, 两两组合得到; (3) 第一个解来自引用集A, 第二个解来自引用集B, 其中, 来自B的解为与第一个解距离最远的那个解。我们可以将这三个子集理解为对引用集中的多样性和强化性这两个特性的进一步深化, 可使搜索更加快速、有效。最后一步是对这三个子集中的元素内部交叉变异产生两个新的解。
2 实验结果
为了更直观地看到结果, 我们在编程中加入了显示部分, 用于甘特图的实时输出。每次重新调度时, 系统会自动截取这一刻生成的最优调度方案。图5 所示为混合分散搜索算法下系统产生的甘特图。图5 中, 5 号机器发生故障, 62 号工件为最新加入的工件, 这次的重新调度是因为机器故障, 原本在5 号机器上的60 号工件的最早开始时间由原来的“当前时刻”变成了机器故障被修复后的时刻。
为了更为公平地进行比较, 我们建立了一个与Adibi M A和Shahrabi所写论文中相同的动态实验环境。为了在初始时可以调度, 本文设置的是在刚开始时已经有10 个工件可供调度。两个工件之间的平均到达时间差符合平均值为100~300 的泊松分布, 共5 组实验。之所以这样设置, 是因为间隔超过300时, 工件的到来太过稀疏, 机器上常常只有两三个工件, 调度意义不大。而如果间隔小于100, 则太过密集, 绝大部分工件在等待, 与实际生产不符。机器的平均损耗时间为5 700, 平均修复时间为300.工件的各工序在各机器上的处理时间为平均值为300 的正太分布。工件的加工顺序为随机产生。
在计算时, 为了减少开头静态10 个工件带来的影响, 我们在计算平均流程时间时, 不是计算所有工件的平均流程时间, 而是计算当第150 个工件到达时, 最近完成的100 个工件的流程时间的平均值 (一般说来, 当第150 个工件到达车间时, 已经完成了100 个以上的工件) 。
为了更好地比较本文算法的有效性, 我们在相同的动态环境下, 对以下四种算法, 即混合分散搜索、分散搜索、改进遍邻域搜索和先入先出 (FIFO) 进行了仿真。在参考文献[13]中, 分散搜索用于解决静态车间调度问题, 本文的算法是分散搜索首次用于解决动态车间调度问题;而FIFO和MVNS已经有研究用于动态调度中, FIFO的思想非常简单, 即先到的工件先被安排到调度中, 在参考文献[12]中用于跟MVNS作比较。
图6 所示为各算法运行时间的比较。从图6 可以看出, 我们设置的是工件平均到来的间隔在150~300 之间, 这符合一般实际生产中的情况, 即工件来得不是特别频繁, 但机器总是保持忙碌, HSS与SS和MVNS所花费的时间比较接近。图7 所示为各算法平均流程时间比较。从图7 可以看出, 混合分散搜索在各种工件间隔条件下, 始终比其他算法表现得出色。图8所示为HSS与MVNS比较。从图8 可以看出, 与目前比较有效的MVNS相比, 混合分散搜索所用的时间增加了24%左右。
从以上3 个图不难看出, 我们提出的HSS在动态车间调度问题的解决上有很强的应用性。混合分散搜索之所以能有这样出色的表现, 我们认为主要有以下三个原因: (1) 在引用子集中, A集为最优解, 而B集为与之距离最远的解。将这两个子集用于后续的交叉操作, 既保证了接下去可以强化结果, 又保证了多样性。能兼顾这两点的算法非常少, 而这两点是启发类算法中至关重要的两点。 (2) 融合了MVNS中K-means和VNS后, 相比于简单的局部搜索, 能结合工件本身的特性, 整个搜索变得更加有效、快速。 (3) 引入精英策略使得每代中最好的解被保留下来, 与原来的分散搜索相比, 最优解不会在迭代过程中丢失。
3 结束语
在本文中, 我们设计了一个事件驱动的实时动态系统, 并提出了一种全新的混合分散搜索方法来解决动态车间调度问题。这是分散搜索首次应用于动态车间, 并用改进遍邻域搜索代替了原来分散搜索算法中的局部搜索, 在迭代次数相近、搜索时间相近的情况下, 使得工件的平均流程时间大大缩短。在大规模的条件下, 实验结果表明混合分散搜索算法可以有效解决动态车间调度问题, 对于自动化程度较高的产业具有一定的指导意义。
摘要：车间调度问题是最为人熟知的生产自动化调度问题之一, 而在实际生产中, 动态车间调度问题更为常见。动态车间调度问题包括机器故障和新工件的到来, 这对调度算法的实时性和效率提出了更高的要求。为提高调度算法的实时性和效率, 设计了实时动态系统, 并提出了一种全新的混合分散搜索算法:用改进的变邻域搜索代替分散搜索中简单的邻域搜索, 使得搜索更快;同时, 引入精英策略, 使得搜索结果更好。大规模的实验证明, 提出的混合分散搜索算法在解决动态车间调度问题上表现出色, 应用效果非常好, 且实时性强。
动态二进制搜索算法 篇4
背包问题是算法学习中非常经典的一个问题,背包问题有多种形式,如0-1背包、完全背包、部分背包、混合背包问题等。其中0-1背包问题是最基本、最重要的问题,它的算法思想经过转换后就可以得出其它几类背包问题的算法,因此深入理解0-1背包问题的算法很有必要。本文探讨用穷举、搜索、动态规划三种算法来解决0-1背包问题,这三种算法的难度逐步增加,算法效率也逐步提高。我们在给出这三种算法基本思想的同时,也讨论对算法的时间和空间复杂度进行优化。
0-1背包问题的描述:一个旅行者有一个最多能装M公斤重量的背包,现在有N种物品,每件的重量分别是W1,W2,…,Wn,每件的价值分别为C1,C2,…,Cn。求能装进旅行者背包的物品的最大总价值。0-1背包特点是:每种物品都仅有一件,可以选择放入或不放。
2 穷举算法解决0-1背包问题
解决0-1背包问题最容易理解的算法应该是穷举算法。算法分析:为了得到能放进背包物品的最大总价值。我们可以在n种物品中,取其中的任意几件,因为每一件都可以取或不取,所以共有2n种取法,求出这2n种取法各自的总重量和总价值,比较这些总重量和总价值,在满足总重量
则放入背包中的物品总重量s=a[1]*w[1]+a[2]*w[2]...+a[n]*w[n]
而放入背包中的物品总价值t=a[1]*c[1]+a[2]*c[2]...+a[n]*c[n]
参考程序:
上面的程序,当物品种类的值n比较大时,计算耗时较多,运行效率不是很高。我们可以在简单穷举的基础上,进行一些优化,将物品按重量从小到大排序,一旦发现放入某个物品后发现总重量已超出背包容量,则可以不再向下列举。如在第k种状态,当放入第i件物品后出现超载情况,则再加入a[i+1]~a[n]的物品已没有意义,直接把a[i+1]-a[n]全部置为1,这样跳过这些无意义的列举,直接进入剩余情况的穷举运算,这个优化可以较大的提高运行效率。
3 用搜索算法解决0-1背包问题
算法分析:用搜索算法递归求解,设当前n个物品,容量为m;因为这些物品要么选,要么不选,我们假设选的第一个物品编号为i(1~i-1号物品不选),问题又可以转化为有n-i个物品(即第i+1~n号物品),容量为m-w[i]的子问题……如此反复下去,然后在所有可行解中选一个放入总价值最大的即可。为了优化程序,我们定义一个函数如下:
f[i]表示选第i-n个物品能得到的总价值。不难推出f[n]=c[n],
假设当前已选到第i号物品,如果当前搜索得到的价值+f[i+1]的值仍然比当前的最优值小,则没有必要继续搜索下去。
参考程序:
4 动态规划解决0-1背包问题
当物品种类增多时,用穷举和搜索算法就不能很好解决问题,往往要超时限。要比较完美地解决问题,我们要考虑更高效的算法。动态规划可以很好地提高0-1背包问题的算法效率。我们建立一张二维表f[0..n,0..m],f[i,j]表示前i个物品装到容量为j背包可以获得的最大总价值,则可得状态转移方程为:f[i,j]=max{f[i-1,j],f[i-1,j-w[i]]+c[i]}
含义为:“将前i件物品放入容量为j的背包中”这个子问题,考虑第i件物品的策略(放或不放),当第i件物品放入背包时,则背包中物品的总价值等于把前面i-1个物品装入容量为j-w[i]背包所得到的价值,再加上第i个物品的价值c[i]。如果第i件物品没有装入背包,则背包中物品的总价值就等于把前面i-1件物品装入容量为j的背包所取得的价值。显然这两种装入方法,在背包中所取得的总价值不一定相同,因此就取这两者中的最大者,作为把前面i件物品装入容量为j的背包所取得的最优价值。
参考程序:
解决0-1背包问题算法很多,处理方法也很灵活,在时间和空间复杂度上可进行很多优化。各种算法有各自的优缺点:穷举算法简单容易理解,但效率不高;搜索算法比较灵活,但递归搜索中有时会占用较多的空间;动态规划因减少重叠子问题的计算,速度有较大提高。三种算法之间也有本质联系,都是通过列举各种状态,从中找到符合条件的最优解,这些算法需要我们深入思考,融会贯通。
参考文献
[1]郑宗汉,郑晓明.算法设计与分析[M].北京:清华大学出版社,2005.
[2]吴文虎,李立新.全国信息学奥林匹克联赛试题精解[M].北京:清华大学出版社,2004.
动态二进制搜索算法 篇5
水库优化调度需要考虑到众多约束条件和实际情况, 本文引进了动态规划算法, 构成了DP-TS算法, 以锦屏一级二滩水库群调度实例模拟算法。
1 水库群优化调度模型
1.1 目标函数
根据发电效益最大的原则, 得到目标函数如下式所示:
注:E为总时间段的发电量;Et为第t个时间段水库群的发电量;Ai是第i个电站的出力系数;Qit是第i个电站在第t个时段的平均发电流量;Hit是第i电站在第t时段的平均发电水头;△t是所计算的时间长度。
1.2 约束条件
(1) 库容约束条件
(2) 流量约束条件
(3) 电站出力约束条件
(4) 水量平衡约束条件
1.3 目标函数处理
考虑到保证率的要求, 我们加入惩罚项, 最终目标函数如下:
注:A为惩罚系数;E保为保证电量;σk为模型参数, 取值规则为:当Et≥E保时, σk=0;否则σk=1。
2 动态-禁忌搜索算法
2.1 TS算法
TS算法是组合优化算法的一种, 以下为TS算法的主要步骤。
Step1:赋予一组初始值集合X0n (X0n={X01, X02, …, X0n}) , 计算当下X0n的目标函数值;
Step2:令当前解集合Xnnow和最优解集合Xnbest等于X0n, 禁忌表长度l为0;
Step3:构造当前解集合Xnnow的邻域, 将其作为候选集, 在候选集中选一个最佳解X1n;
Step4:若X1n比最优解集Xnbest更优, 令Xnbest=X1n, Xnnow=X1n;
Step5:若X1n比最优解集Xnbest差, 且X0n到X1n的变化不在禁忌表中, 则令Xnnow=X1n;若在禁忌表中, 则在候选解中寻找次优解X2n, 并令X1n=X2n, 返回Step5;
Step6:将X0n到X1n的变化记录到禁忌表末尾, 若禁忌表长度达到最大值, 去掉最头的一个记录;否则禁忌表长度l=l+1;
Step7:满足迭代收敛条件转Step8, 否则转Step3;
Step8:满足精度要求, 退出。
2.2 DP-TS算法
TS算法的初值较为主观, 故我们利用DP算法来获取TS算法的初值。我们利用DP算法得出一个优化解XnDP, 将此解作为TS算法的初值X0n, 这样便可利用TS算法以利于求解全局最优解的优点, 又避开其初始值选取敏感的缺点, 得到组合DP-TS算法。
3 实例应用
3.1 锦屏一级二滩水库群概况
锦屏一级水电站位于四川省, 装机容量3600MW, 保证出力1086MW, 多年平均174.1×108kwh, 水库正常蓄水位1880m, 死水位1800m, 正常蓄水位以下库容77.6×108m3, 调节库容49.1×108m3, 属年调节水库。二滩水电站水库正常蓄水位1200m, 发电最低运行水位1155m, 总库容58×108m3, 调节库容33.7×108m3, 死水位库容24.2×108m3, 属季调节水库。电站装机容量3300MW, 多年平均发电量168.8×108kwh, 保证出力1050MW
3.2 算法设计
DP算法求初始值:
根据上述给出的约束条件, 通过获取某典型年的逐月径流情况以及库水位与库容的关系, 可以得到用DP算法求出的一个解集串。在这里我们取水位离散点数为50和500, 保证率惩罚系数A=5, DP算法主要相关变量设计如下:
(1) 阶段变量和状态变量:阶段变量取1月, 整个调度期共12个时段, 即阶段变量k=1, 2, ..., 12。状态变量取各时段初系统的水位, 水库水位在死水位与各时段状态允许最高水位之间连续变化, 取水库水位变化△z为一个间隔, 相应于该水位的一个状态。状态变量Zkij= (zk1i, zk2j) , 表示第k状态初, 锦屏一级水库水位处于i状态, 二滩水库水位处于j状态。
(2) 决策变量和状态转移方程:各阶段, 若初状态为Zkij, 末状态为Zk+1, g, h, 则决策变量出库流量为qkijgh= (q0k1ig, q0k2ig) 。状态转移方程用水量平衡方程, 第k阶段, 入流为Qk= (Qk1, Qk2) , 状态变量为Zkij, 决策变量为qkijgh, 状态转移方程为:
其中:Vk+1, g, h、Vkij为初状态Zkij, 末状态Zk+1, g, h所对应的库容;Sk为整个系统的入库流量;Qk1为锦屏一级的入库流量;Qk2为锦屏一级与二滩之间的区间流量;q0k1ig为第k阶段, 此始末状态下, 锦屏一级水库的出库流量;q0k2ig为第k阶段, 此始末状态下, 二滩水库的出库流量。
(3) 根据上述变量选取可得到该法下最优解所对应的发电流量解集XnDP={Q1DP, Q2DP, …, QnDP}。
3.3 DP-TS算法求全局最优解
根据表1中利用DP算法得出的发电流量解集XnDP={Q1DP, Q2DP, …, QnDP}作为TS算法的初始值X0n, 然后利用上述所介绍的TS算法求出最后最优解, 见表1。
3.4 结果分析
在基于DP算法基础上的TS算法由于初值选取较好, 因而迭代的次数明显减少, 可迅速趋于全局最优解, 为便于比较, 我们再利用DP算法在水位离散点数分别为500的情况下求解两个水库发电效益, 并与在DP算法离散点为50的基础上的DP-TS算法的结果进行比较, 结果见表2。
从上表可以看出DP算法随着离散点所取数量增多, 发电量有着提升, 但耗时多, 而DP-TS算法只需在DP算法取50离散点的情况下便可与取500离散点时具有获得几乎相当的调度解, 且时间消耗与离散点为500的DP算法相比较少。进一步, 容易知道当水库群的数量进一步增多时, DP算法会陷入“时间灾”, 而组合算法的优点则会突出。
4 结论