高等运筹学(第6章)

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第章 禁忌搜索算法,禁忌搜索（,Tabu,Search,TS,）,的思想是由,Glover,于,1986,年提出的，并逐步形成了一套完整的算法,算法思想源于对,人类智力过程,的一种模拟.所以,TS,也是一种人工智能,算法,模拟退火,(,SA)：,模拟固体物质退火过程.,禁忌搜索,(,TS)：,模拟人类智力过程.,遗传算法,(,GA)：,模拟生物进化过程.,与,SA、GA,等通用启发式算法一样，,TS,也,是对局部搜索算法的一种扩展，是一种全局逐步寻优算法,所谓,禁忌,就是禁止重复前面的工作算法,引入一个,禁忌表,记录下已经搜索过的点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点,1,主要内容,6.1 禁忌搜索算法示例,6.2 禁忌搜索算法的基本思想和步骤,6.3 禁忌搜索算法的关键参数和操作设计,2,6.1 禁忌搜索算法示例,以,TSP,为例说明禁忌搜索的主要思想,问题规模,n,=7,邻域结构：定义为“互换(,swap,)”,操作，即随机交换两个城市在,当前解,中的排列位置，则每个解的邻域解有,=,n,(,n,-1)/2,=7(7-1)/2=21,个每次迭代用其中最好的5次变换作为,候选解,每次变换将导致目标函数节约值（即目标函数差）的变化,每个被采纳的变换在禁忌表中将滞留3步（称为禁忌长度）,但若禁忌对象对应的目标函数节约值优于到目前为止所搜索到的,最好解,（“,best-so-far”）,，,则无视其禁忌属性而仍接受该解藐视准则,3,归纳起来,TS,有如下主要特征：,(1)邻域结构的设计很关键，它决定了当前解的邻域解的产生形式和数目,(2)候选解集仅取其中的少量最佳状态组成,(3)禁忌长度直接影响整个算法的搜索进程和行为,(4)藐视准则的设置是算法避免遗失优良状态,(5)对于非禁忌的候选解，算法无视它与当前解的目标函数值的优劣关系（即可能比当前解差），仅考虑从中取出最佳的一个作为下一步的当前解，以此来实现跳出局部最优（是一种确定性策略）,(6)新解不是在当前解的邻域中随机产生，而是非禁忌的最佳候选解，或者是优于“最好解”的候选解,(7)必须设置一个合理的终止准则,4,6.2,TS,的基本思想和步骤,算法的基本思想,：给定一个当前解（初始解）和候选解产生函数（邻域结构），然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于到目前为止搜索到的“最好解”（,best-so-far），,则忽视其禁忌特性，用其替代当前解和“最好解”；若不存在上述候选解，则在候选解集中选择非禁忌的最佳候选解为新的当前解，而无视它与当前解的优劣；两种情况下都将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直到满足停止准则,5,禁忌搜索算法主要步骤流程图,由当前解产生候选解集,将该解作为新的当前解,和到目前为止的最好解,有满足藐视准则的候选解否？,算法终止准则满足否？,输出结果,更新禁忌表中各对象的任期,给定算法参数,产生初始解,置禁忌表为空,N,Y,N,Y,选择非禁忌的最佳,候选解为新的当前解,6,6.3,TS,的关键参数和操作设计,1.初始解,可以随机产生，也可以借助一些经典启发式方法产生以保证一定的初始解性能,2.邻域结构,即候选解产生函数，用于从当前解的邻域中产生一个新解对算法搜索质量和效率有重要影响,通常选择当前解经过简单地变换即可产生新解的方法如上例中的“互换(,swap,)”,操作,为了使算法渐近收敛于全局最优解，所构造的邻域结构应能使解空间中的任何两个状态通过有限步邻域搜索后互达,7,3.候选解的选择,候选解数量的确定：确定性或随机性地在当前解的邻域解集中选取一个子集作为候选解集，其大小一般为50500个,最佳候选解的选取：选择候选解集中满足藐视准则或非禁忌的最佳候选解,4.解评价函数,用于对搜索到的候选解进行评价,方法：,直接用目标函数作为解评价函数；,用反映问题目标的某些特征值来作为解评介函数，但要保证特征值的最佳性与目标函数的最优性一致如上例中用“节约值”,8,5.禁忌对象,被置入禁忌表中的那些变化元素禁忌的目的是为了尽量避免迂回搜索,(1)以整个解的变化为禁忌对象当解状态由,x,变化到解状态,y,时，将解,y,（,或,xy,的变化）视为禁忌对象,(2)以解分量的变化为禁忌对象如示例中的情形,(3)以目标值的变化作为禁忌对象,6.禁忌表和禁忌长度,禁忌表,（,tabu,list）,是针对禁忌对象所设计的一种结构，可以是一维或二维的,禁忌长度,t,（,tabu,length）,是禁忌对象的禁忌期，即不允许再次被选取的迭代次数每迭代一步，,t,减少1，当,t,=0,时解禁,9,禁忌长度,t,的选取：,(1),t,是一个固定的数如,t,=7,，,或者固定为与问题规模相关的一个量，如,t=,，,或,t=,/2,(2),t,是动态变化的即设定禁忌长度的变化区间,t,min,t,max,，,如,5,10,等,7.藐视准则,若某个禁忌候选解的目标值优于到目前为止搜索到的“最好解”（,best so far,），,则解禁此,候选解,为,当前解,和新的“,最好解,”,若候选解均被禁忌，且不存在优于“最好解”的候选解，则对候选解中的最佳者进行解禁，以便搜索过程继续进行下去,10,8.终止条件,(1)给定最大迭代步数，如,N,=10000,优点是易于操作和控制计算时间，但无法保证解的质量,(2)给定当前的最好解保持不变的最大连续迭代次数如,2500,次,(3)设定目标值的偏离幅度若,Z,LB,为问题的下界，,为给定的偏离幅度，则当,f,(,x,),Z,LB,时，终止计算,(4),设定禁忌对象的最大禁忌频率若某个禁忌对象的禁忌频率超过给定的值，则终止计算,11,TS,求解过程演示（,示例1,，,示例2,）,参考文献,1,符卓.带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究.,系统工程理论与实践,2004,24(3):123-128,2,Z Fu,(,符卓,),R,Eglese,and LYO Li.A new,tabu,search heuristic for the open vehicle routing problem.,Journal of the Operational Research Society,2005,56(3):267-274.,显示,总迭代,次数,最好解保持不变的连续迭代次数,当前解,最好解,(,best-so-far),特点,累加,波动,波动,逐步减小,12,13,14,