回溯试探算法

回溯试探算法（共4篇）

回溯试探算法 篇1

0 引言

计算机基础课程是大学的必修课程,计算机基础考试逐渐由传统笔试向机试转变,这种转变既能考查学生基础知识的掌握程度,又能考查学生的实际操作能力,减轻了教师负担,保证考试的公平、公正。组卷技术是在线考试系统实现的核心,目前组卷算法很多,常见的类型主要有简单随机抽取算法、回溯试探算法、遗传算法。

(1)简单随机抽取算法是从题库中随机抽取一定数量的满足预先设定条件的试题组成试卷。这种方法实现简单、容易理解、组卷速度较快,但是抽取的试题重复率高,尤其是题库小的系统[1]。

(2)回溯试探法是随机抽取算法的改进,它采用随机抽取算法从题库中抽取试题,如果满足条件就将试题标记放入预先建立的栈中,如果抽取的试题不满足条件,就返回到上一个成功状态,继续随机搜索。它有效地解决了简单随机算法的试题重复抽取问题,实现简单,但只适用于小型题库系统。对于大型题库来说,需要占用很大的内存空间,且组卷时间长、效率低。

(3)遗传算法是模仿生物界中遗传、变异、交叉等过程,依照基因组合原理对染色体进行编码,按照优胜劣汰的原则得到最优解。这种算法具有全局寻优、智能搜索和收敛速度快等优点,但是实现困难[2]。

柳浪涛、谷林[3]提出了一种“卷内分块、组块分层”的组卷机制,按照题目类型分为若干块,按块分别抽题。按照题型分块,即为题库分类;块内分组,即为不同类型试题分组。分类算法是指按照题型设计将题库分类,解决知识点覆盖面的问题,而分段算法是将各类题型试题按照“知识点”、“难度系数”字段分组,从每组试题中按照试题数量比例抽取相应的试题,以解决试题重复抽取问题。题量越大,抽取效果越好。

综合考虑算法难易、组卷速度、知识点覆盖率、试题重复率等问题,本文采用分类分段回溯试探算法。分类分段算法结合回溯试探算法,综合利用了两者的优点,弥补了两者的不足。首先将题库按照不同题型分类,然后再对不同类别的试题按照知识点、难度系数字段分段,最后对每类题库根据预先设定条件随机抽取试题。回溯试探算法是对简单随机算法的改进,随机抽取一道题加入试卷,系统将记录下这道题的知识点、试题序号放入预先建立的栈中,再根据约束条件随机抽取下一道题,将这道题的知识点、试题编号与上一道题记录下的知识点、试题序号相比较,如果不同,则将试题加入试卷并释放上一个记录,并写入这道题的属性,如果相同则重新抽取试题,以此类推。回溯试探法结合分类分段抽取法,有效缩小了回溯搜索的范围,提高了组卷速度,解决了试题知识点覆盖面、试题重复抽取以及知识点覆盖面问题。

1 数据库设计

题库设计质量的好坏对组卷成败至关重要。本文采用分类分段回溯试探算法,在试题库中按“难度系数”排序,再按“知识点”排序。排序后,同一个知识点的同一难度系数试题放在一起,组卷就是从同一知识点同一难度系数的题目中随机抽取指定数量的题目[4]。

计算机基础在线考试一般分为选择题、填空题、Excel操作题、Word操作题、Windows操作题几类。为了提高组卷效率,需要预先确定试卷为百分制,然后确定题型题量、小题分值、知识点分布等属性,这些设置好的试卷属性字段都统一存放在PaperSet数据表中。按照试卷属性设置表中数据,每种题型分别从相应的题库中抽取。题库表分为选择题及操作题。

选择题题库表结构如表1所示,操作题题库表结构如表2所示。其中“questType”字段表示为题型设置编号,“1”代表选择题,“2”代表填空题,“3”代表Excel操作题,“4”代表Word操作题,“5”代表Windows操作题。表2中的“OperateType”字段指每种操作题的操作类型,用数字代表不同的操作类型,例如Word操作题中“1”、“2”、“3”数字分别代表“表格操作”、“文本替换”、“段落缩进”操作类型,Excel题型主要设计有“单元格样式”、“行列样式”、“工作表操作”、“生成图表”等操作类型,Windows操作题主要设计有“文件夹删除”、“文件夹创建”、“文件夹重命名”、“文件复制”等操作类型。此外,题库中的“Chapter”字段,用数字代表不同的知识点分布,用“Degree”难度系数划分“简单”、“中等”、“较难”、“困难”,分别用数字“1”、“2”、“3”、“4”来存储。

2 组卷

将在线考试系统设计的5种题型分为5个模块,在页面设置5个事件按钮,考生点击一个按钮将随机从相应题库抽取确定数量的试题,如图1所示。按照题型不同将题库分为5类,在这5大题库中又采用章节、难度系数的设定对每种题型进一步分组。题库中的每道题至少有如下4个属性,定义如下:

(1)分值:每道试题的分值,小题设置的分值与该题型的题量乘积即是该大题总分。设计试卷满分为100分,根据题型设置,单选题30分,15题,每题2分;填空题20分,10题,每题2分;Word题20分,5题,每题4分;Excel题20分,5题,每题4分,Window题10分,4题,每题2.5分。

(2)题型:试题的类型一般分为选择题、填空题、Excel操作题、Word操作题、Windows操作题等。给出试题类型,自动组卷将在给定的数据库表中搜索,缩小了搜索范围,加快了组卷速度。

(3)知识点:又称为考核点,它涉及具体考核内容,知识点按章节从前往后划分。每种题型预先设计一定数量的知识点,每道试题考查内容对应不同的知识点,每个考查的知识点录入一定数量的试题。

(4)难度系数:指测试试题的难易程度。它的定义是qi=1-Ri/n,qi表示第i题的难度系数,Ri表示此题平均得分值,n是该题的满分值[5]。试卷难度控制将容易、中等、困难试题所占比例进行设置。一般试卷的难度系数在中等才能使考试成绩成正态分布。题目区分度与它的难度相关,通常过高或过低题目的区分度都较小,中等难度的区分度最优[6]。

根据分类分段算法,按照题型设置,每种题型设置相应题库,分5次随机抽题。对于每类题库,再按照知识点、难度系数字段属性分配集合。根据回溯试探算法执行抽题,每种题型抽题的组卷事件触发按钮点击后,按照设定的难度系数、题型、题量等约束条件分别从相应的题库中随机抽取一道试题加入试卷中,将此试题的知识点、试题序号记录下来,再抽取下一道题,将这道题的知识点与上一题相比较,如果相同就放弃加入试卷并继续抽题,如果不一样即释放上一条记录,更新为当前记录。以此类推,直到完成组卷,算法描述如下:

这样的设计解决了试题知识覆盖面、试题重复率等问题。部分抽取试题代码如下(采用C#语言结合SQL语言的代码):

对于不同的题型调用不同的抽题函数随机抽取试题。

3 实验结果

分类分段回溯试探组卷算法相较于随机抽取算法而言,解决了试题重复率高、知识点覆盖率小的问题,相较于回溯试探法而言解决了搜索速度慢、组卷效率低等问题。本文算法综合利用了分类分段随机算法以及回溯试探算法的优点,摒弃了它们的不足,代码实现较为简单,能够生成需要的试卷。

4 结语

本文采用的分类分段回溯试探算法,结合了简单随机抽取算法和回溯试探算法的优点,实现简单,大大缩小了搜索范围,组卷速度快且避免了试题重复率问题。在线考试组卷系统兼顾了题型、题量、分值、知识点分布、难度系数等试卷参数,能快速得到一份满意的计算机基础在线考试试卷。

参考文献

[1]王琦.智能组卷算法研究比较[J].科技信息,2008(29):403-418.

[2]高兴媛,古辉.在线考试系统自动组卷技术的研究与实现[J].计算机与现代化,2011(3):155-157.

[3]柳浪涛,谷林.自动组卷系统试题难度和知识点覆盖控制算法[J].西安工程大学学报,2015,29(3):321-324.

[4]雷勇.分类分段算法在组卷中的应用研究[J].实践与经验,2014(19):41-44.

[5]桂阳,王修信,农京辉,等.大学物理试题库智能组卷随机抽取法的改进[J].广西物理,2008,29(2):23-25.

[6]严思静,常红春.蚁群算法在组卷中的应用[J].职大学报,2014(6):83-87.

一种改进的快速网络回溯算法 篇2

1 快速网络回溯算法

快速网络回溯算法使用IPv4报头中16bit的ID域作为标记域，ID域共分为三部分，第一部分是1bit距离域;第二部分为bfnum位段号域;第三部分为bfrag位Hash值域。路由器计算自身IP地址的hash值并将其分为n个片段(n为固定值)，每段为bfrag位，bfrag的长度为15-bfrum。当路由器准备标记一个数据包时，随机选择一个段号写入段号域，然后将相应的Hash片段值写入hash值域，从而完成标记，表1是FIT算法符号表示。

当路由器要以一定概率标记数据包时，将数据包的TTL值(Pkt.TTL)的低位数起第六位1bit的数存储在1bit的距离域中，常量c值(实验证明22是最优的)赋予Pkt.TTL[4..0]，数据包传输距离的计算方法为：

即数据包被最后一个路由器标记时的M.dist_bit|c值与当前的TTL差的模64。FIT算法描述如下：

2 改进的快速网络回溯算法

改进的FIT算法利用生存时间域(Time-To-Live,TTL)来计算每个数据包的最大剩余传输距离。以最大剩余传输距离的反函数作为标记概率p对数据包进行标记。

选取标记概率p的理论依据基于以下两点：一是当标记概率P=1/Length_eva(length_eva是数据包最大剩余传输估计距离)时，距离受害者远的数据包被标记的概率大，距离受害者近的数据包被标记的概率小，这样使得到达受害端的数据包被标记的概率有显著增加，为了获得数据包最大剩余传输估计距离。根据文献[5]中提到的99%的数据包所传输路径长度小于32跳，而90%的数据包所传输的路径长度小于25跳。因此算法设置TTL域的上界值Max.TTL=32。二是DPPM算法[6]研究发现距离攻击者最近的路由器中所传输的数据包最少也最难收集，要能够完整收集到整个攻击路径的标记数据包，前提是收集到的所有数据包中，首个路由器(离攻击者最近)标记的数据包数必须大于等于1。因此在数据包距离大于32跳时，路由器对其标记概率p全部设定为1。

标记概率p选取算法

3 重构攻击路径所需数据包数

利用尽可能少的数据包来重构攻击路径是提高追踪性能的重要内容。下面来分析改进的FIT算法重构攻击路径时所需要的数据包数，定义Ppath为受害者在收到x个数据包后能重构出s个路由器IP地址的概率，即重构概率。定义Pip为受害者在收到x个数据包后重构出距离为其i跳位置的路由器IP地址的概率，假设重构过程相互独立，则可得。定义npath为受害者重构一个路由器IP地址至少需要得到的不同Hash值的片段数。由概率论可知，从所有k个Hash片段中随机选择y个片段后，其中有j个不同Hash片段的概率为[7]：

对于FIT算法，由文献[8]可知，给定标记概率p，则受害者收到距离i跳处的路由器IP地址Hash值片段的概率pm为：

对于受害者收到的x个数据包，其中有x·Pm个数据包来自于距离i处的一个路由器。由此可以用Pf和Pm来表示当受害者收到x个数据包后重构出距离i跳处一个路由器IP地址的概率为：

k和npath值由预期的误报率来确定[8]，表2是重构概率Ppath分别为0.5和0.95的情况下，根据k和npath值以及公式(1)、公式(2)和公式(3)计算出的不同距离情况下重构攻击图所需的数据包数量。(计算过程见文献[8])。

改进的FIT算法与FIT算法的不同之处在于使用不同的标记概率对数据包进行标记,则对于改进的FIT算法,一个数据包(TTL值为t)携带距离受害者为i跳的路由器IP地址Hash值片段的概率为:

公式(4)中,(1/(32-t))对应的是路由器标记一个数据包的概率,是在数据包传输路径中其他路由器都没有标记该数据包的概率。

如果攻击者进行标记欺诈，必须考虑以下一些情况：

1)如果攻击者伪造的TTL值等于距离受害者的跳数i(t=i)，则Pm=1/32。

2)如果攻击者伪造的TTL值小于i(t

3)如果攻击者伪造的TTL值大于i(t>i)，由于此时Pm>1/32，路由器的IP地址Hash值片段会传送到受害者。

可以看出在攻击者没有伪造TTL字段并且t=32时，改进的FIT算法重构攻击路径所需数据包最少，处于最佳情况。在攻击者伪造TTL字段且t=i时，改进的IT算法重构攻击路径所需数据包最多，达到最坏情况。由表2比较可得，即使在最坏的情况下，改进的FIT算法重构攻击路径所需要的数据包还不到FIT算法所需要的一半。在最好的情况下，改进的FIT算法重构攻击路径所需要的数据包约是FIT算法的三分之一。

4 小结

针对FIT算法标记数据包使用固定概率，导致数据包容易被重复标记，重构路径需要大量数据包的问题，对FIT算法进行了改进，以路由器到受害端距离为参数，利用网络中数据包最大传输距离小于32跳原理，使用数据包最大剩余传输距离的反函数作为标记概率，使得传输距离长的数据包标记概率高，传输距离近的数据包标记概率低，分析表明，该算法与FIT算法相比，减少了重构路径所需数据包数。

参考文献

[1]Yaar A,Perrig A,Song D.FIT:Fast Internet Traceback,in Proceedings IEEE INFOCOM,2005.

[2]University of Oregon Route Views Project.,http://www.routeviews.org/.

[3]Rizvi B,Fernandez E.Analysis of Adjusted Probabilistic Packet Marking.In Proc of IEEE IP Operations and Management'03.

[4]Paruchuri V,A.Durresi,R.Jain,On the(in)effectiveness of Probabilistic Packet marking for IP traeeback under DDoS attack.IEEE GLOBECOM2007.

[5]Theilmann W,Rothermel K.Dynamic Distance Maps of the Internet.2000IEEE INFOCOM Conference,2000.

[6]Liu J,Lee Z J,Chung Y C,Efficient dynamic probabilistic packet marking,in:Proceedings of the11th IEEEInternational Conference on Network,2003:475-480.

[7]Feller W.An Introduction to Probability Theory and Its Applications.New York:Wiley,1996.

基于回溯法的排课算法 篇3

1 排课基本原则

要排出科学、合理和实用的课程表,必须满足下列排课原则[6]:

1)同一教师不能同时给两门或两门以上的不同课程授课;

2)同一教室不能同时安排两门或两门以上的不同课程;

3)教室的座位数要大于等于上课的人数;

4)教室的类型要与课程的类型一致(如实验课等);

5)尽量将课堂教学安排在上午,而将试验课、体育课和电化教育课程安排在下午进行;

6)尽量保证每个教师的工作时间要错开,即在上课的时间上,不能让一个教师连续完成多个教学工作;

7)一般在某个特定的时间段不要安排教学任务,以便教师和学生都能够利用这个时间进行一些教学工作以外的活动;

8)尽量为特殊教师(如领导等)安排特定的教学时间;

9)同一个班级的同一门课在一个星期里尽量使其上课的时间错开,即均匀排课。

这里把1)、2)、3)、4)称为显约束,其余称为隐约束,显约束必须满足,而隐约束要似情况而定。

2 主要数据结构

排课的基本要素包括:课程、教师、班级、教室和时间。

课程信息表(课程编号,课程名称,课程性质,上课学时,周学时,上课班级,教师代码,教师姓名,是否已排,优先级);

教师信息表(教师编号,教师姓名,性别,年龄);

班级信息表(班级名称,人数);

教室信息表(教室代码,房间号,教室类型,可容纳人数,是否已排);

时间信息表(时间代码,节次,时间段)。

3 优先级原则

1)专业课的调度优先于非专业课;

2)参与班级较多的课程优先调度;

3)合班课优先调度;

4)多头课优先单头课调度;

5)对时间有特殊要求的课程先调度;

6)对教室有特殊要求的课程先调度。

根据以上原则,设计了一个优先级函数为:

其中F(x)表示优先级函数;J(x)表示课程的级别(专业课设置为3,基础课设置为2,非专业公共课1);W(x)表示该课程的周学时数;S(x)表示该课程的参与班级数;T(x)表示教师承担课程的任务量(承担一门课为0,两门课为1,三门课为2,依次类推);C1,C2,C3,C4为可调整的参数,由F(x)可知,课程级别越高、周学时数越多、参与班越多、教师任务越重的课程的优先级超高。这样按优先级进行降序排序,优先级高的优先处理。

4 优化原则

因为排课问题是NP完全问题,必须根据排课的基本原则对课程表进行优化,让其满足约束条件,从而达到最终目标,优化的基本原则是:

1)学习效率原则

不同类型的课程在不同的时间段学习的效率不同,排课时要尽量使学习效果最佳。

根据学习心理学,将课程划分为以下四大类:

(1)逻辑性强的课程:如数学、电路、数据结构等;

(2)记忆性强的课程:如语文、外语等;

(3)综合类课程:即既有理解记忆的部分,又有逻辑推理,如会计类课程等;

(4)体育类课程。

根所以上划分,可把学习效率用不同的系数表示如表1所示。

2)均匀排课原则

一周内上两次或两次以上的课程(一般为两次或三次),两次间隔均匀。现对可能出现的的情况作出统计并对其进行评分,如表2、表3所示。

3)资源利用原则

资源利用率,这里主要指教室资源的利用率,考虑上课人数与教室资源的比值,即人数/教室座位数,比值越大越好,最大值为1。

这里称上述原则为排课三原则。首先处理均匀排课,其次是学习效率,最后是资源利用率。根据排课三原则,可得到目标函数值的计算公式:

其中r1,r2,r3为原则1,2,3的得分值,w1,w2,w3为权重分别为3,2,1,由此可知目标函数值越大则课表越优化,目标函数值最大时对应的课表为最理想的课表。

5 回溯排课算法描述

回溯算法是求解多约束条件问题的最佳解时常采用的首选方法,希望一个问题的解能表示成一个n元式(x1,x2,…,xn)的形式,有时也称其为问题的解向量,对于具体的问题通常要求使解向量满足某些约束条件或者是使问题的目标函数最大化(或最小化)[8]。通过上述对排课问题的具体分析后,得出了回溯算法的目标函数值的计算方法,现将算法描述如下:

1)处理特殊情况,如固定时间的课程,领导的课程等;

2)排课;

(1)根据优先级函数F(x)计算调度优先级,并对优先进行降序排序;

(2)取排课信息;

若周学时为偶数;

判断该位置是否可排,可排则剩余周学时=周学时-2;

若周学时为奇数;

当周学时或剩余周学时为1时,必须分单双周处理;

当周学时或剩余周学时为3时,若不分单双周,则处理三节连排;

对上述两步若找不到合适的位置则回溯。

(3)若所有课程均排完,则计算目标函数值并保存;

(4)重复(2)(3)步并比较目标函数值,直到目标函数值最大时停止。

6 结束语

该算法已在我校排课中得到具体应用,结果表明,使用该算法编排的课表是成功的,各种约束条件都得到了满足,课表科学合理,编码简单,容易软件实现。

参考文献

[1]Even S,Itai A,Shamir A.on the The Complexity of Timetable and multicommodify flow problems SLAM[J].Journal on Computing,1976(5):691-703.

[2]Cooper T B,Kingston J H.The Complexity of Timetable Construction Problems[C].Proc.ICPTAT'95,1995:183-295.

[3]张健.基于图论的高校排课系统实现[J].重庆师范大学学报,2005(1).

[4]蒲保兴.基于遗传算法的排课算法[J].中央民族大学:自然科学版,2006,15(1):83-87.

[5]杜敏.基于知识的排课系统研究与实现[J].小型微型计算机系统,1989(8).

[6]杨兴旺.贪婪算法在排课算法中的应用[J].中央电大学科研究,2007(1).

[7]李志娟,王冠.高校自动排课算法的研究与设计[J].计算机与数字工程,2008(5).

回溯试探算法 篇4

近年来,社会上各种突发事件( 火灾、地震、海啸、空难等)频出,应对此类突发事件的关键是如何对所需的应急资源进行及时调度,将损失降到最小。目前国内外对应急资源调度问题的研究发展较快,刘春林、何建敏等在应急时间最早、出救点数目最少的前提下,提出了基于单目标、多目标、两层目标且有资源数量约束条件下的应急资源调度模型[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在全局搜索能力和求解精度方面均优于其他三种算法,有效解决了其他算法易陷入局部最优且出现早熟收敛的问题。在下一步的工作中,将考虑更加复杂的应急资源调度模型,并运用改进回溯搜索优化算法进行求解。

摘要：以连续性消耗应急系统为背景,建立以时间成本和运输成本最小化为目标的多资源多供应点调度模型。针对该模型的特点,对一种具有强全局搜索性的新智能算法——回溯搜索优化算法进行改进,设计变异操作中的变异尺度系数和交叉操作中的交叉概率策略,提高算法的收敛速度和求解精度。运用改进回溯搜索算法进行模型求解,仿真实例表明,改进回溯搜索优化算法在解决应急资源调度问题时拥有良好的性能,全局收敛性与求解精度均优于比较的回溯搜索优化算法、差分进化算法和粒子群算法,能够有效且合理地进行应急资源调度。