禁忌搜索算法教学课件.ppt

1、min()f x.st()0g x xX目标函数目标函数约束条件约束条件定义域定义域注：注：X为为离散点的集合，离散点的集合，TS排斥实优化排斥实优化N xxXN xxx:()2XN xXN x()xN x2X()yN xD=x=(i1,i2,in)|i1,i2,in1,2,nN(x)xCn2=n(n-1)/2xx=(1,2,3,4)C42=6N(x)=(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)k邻域的构造依赖于解的表示，邻域的结构邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。在

2、智能优化算法中起重要的作用。是是否否否否是是是是否否是是否否否否是是是是否否x0 xbest:=x0T=N(xbest)TSSxnowf(xnow)NGNGxX:xxT*(,)()A s xC x N xT注：注：表示非正常终止，造成的原因：表示非正常终止，造成的原因：邻域小，邻域小，T T表长。正常设置为表长。正常设置为(T表长度表长度 邻域大小邻域大小)。Step 2的作用是设置循环体出口。的作用是设置循环体出口。N xT ,LC sxOpt C s xs xN x(,)LC sxA s x()Lxsx注：注：Step 3的作用破禁检查的作用破禁检查 ,KC sxOpt C s xs xN

3、 xT()Kxsx注：注：Step 4的作用邻域选优的作用邻域选优注：注：Step 5的作用选优并记录历史最好点，更新渴望水平 C xC xxx C xC x,A s xC x注：注：x存入存入T T表中的第一个位置表中的第一个位置N(x)TN(x)T ,KsxOpt s xs xN xT Ksx KC sx*C x 10C x T xS C x*xx*(,)()10A s xC x xS C x 16C x*xx*(,)()16A s xC x xS C x 18C x*xx*(,)()18A s xC x xS C x 14C x*(,)()18A s xC x xS C x 20C x*

4、xx*(,)()20A s xC x()20C x*()20C x变化因素变化因素解的变化解的变化解分量的变化解分量的变化函数值的变化函数值的变化禁忌对象禁忌对象解解移动移动函数值函数值受禁范围：解的变化受禁范围：解的变化 邻域移动邻域移动 函数值函数值 计算时间：函数值计算时间：函数值 邻域移动邻域移动 解的变化解的变化摆脱局优：函数值摆脱局优：函数值 邻域移动邻域移动 解的变化解的变化minmax,tt禁忌长度过短，一旦陷入局部最优点，出现循禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；环无法跳出；禁忌长度过长，造成计算时间较大，也可能造禁忌长度过长，造成计算时间较大，也可能造成计算

5、无法继续下去。成计算无法继续下去。E(s(x)s(x),min,Opt C s xs xN xTC s xE s xs xN xT注：惩罚因子注：惩罚因子的取值一般应远小于目标值（的取值一般应远小于目标值（1%1%目标值目标值或或11目标值），目标值），越大分散性越好，广域搜索能力强，越大分散性越好，广域搜索能力强，但会损坏邻域搜索。但会损坏邻域搜索。nni,j(ij)(j,i)+1)1x2x3x4x5x6x7x8x9x 2121 BnkliiL B inkliiL B ixxKArgMax D k D kxx其中，是已选初始解的集合这种方法使初始解充分分散到可行域的不同部分wTSP Benchmark 问题问题 41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50