第4章——禁忌搜索

1智能优化方法AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina20042第四章禁忌搜索3第四章禁忌搜索（TabuSearch）一.导言二.TS的基本原理及步骤三.TS的算法步骤四.TS可以克服局优的分析五.TS举例六.TS的中、长期表的使用七.TS表的应用举例八.学习TS的几点体会41.TS的提出1977年F.Glover提出TS，90年代初得到广泛重视一.导言（1）52.TS的基本思想——避免在搜索过程中的循环①只进不退的原则——用Tabu表锁住退路②不以局部最优作为停止准则③邻域选优的规则模拟了人类的记忆功能——找过的地方都记下来，不再找第二次一.导言（2）63.TS的要素构成①禁忌表(TabuList)②渴望水平函数(AspirationLevelFunction)③移动规则——邻域选优④选优规则——保持历史上的最优解⑤停止准则——与GA相似一.导言（3）71.问题的描述及邻域的概念TS仅用于离散优化，排斥实优化二.TS的基本原理及步骤（1）是离散值空间X..minXxtsxC8二.TS的基本原理及步骤（2）的集合。是邻域移动可达到的解邻域为方向，则：为单位步长，，的邻域移动为邻域的概念：xSXsudxSsxSudxxSx,du9邻域举例：X=[0,1,0,0,1,0,0]u=1,d=[0,0,1,0,0,0,0]注意：移动的意义是灵活的，目的是便于搜索。如：排序问题中一次换位可称为一次移动，还可以定义为选一个切点，两部分作交叉运算。二.TS的基本原理及步骤（3）0,0,1,0,1,1,0udxxS102.禁忌表的概念禁忌表的作用：防止搜索出现循环①记录前若干步走过的点、方向或目标值，禁止返回②表是动态更新的——把最新的解记入，最老的解从表中释放(解禁)。③表的长度称为Tabu-Size，一般取5、7、11，表长越大分散性越好。二.TS的基本原理及步骤（4）113.邻域搜索规则每一步移动到不在T表中的邻域中的最优解，即若，则令则本次移动到最优解邻域搜索规则的作用：保证TS的优良局部搜索功能二.TS的基本原理及步骤（5）xSkTxSxsxsOptxSk,xSXk124.渴望水平函数是一个取决于和的值，若有则是不受T表限制。即使，仍可取渴望水平，一般为历史上曾经达到的最好目标值。二.TS的基本原理及步骤（6）xsA,SXxsAxSC,xSTxSxSXxsA,131.步骤：①选一个初始点，，令，，迭代指标；②若停止，否则令，若(其中NG为最大迭代数)停止；注：表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度邻域大小)。步骤②的作用是设置循环体出口。三.TS的算法步骤（1）XxT0kxxxTxS1kkNGkTxS14③若，令更新(当前最优目标函数值)；注：步骤③的作用邻域选优④若，且，令，(更新渴望水平)；注：步骤④的作用破禁检查，修订渴望水平三.TS的算法步骤（2）TxSxsxsOptxSk,xSXkxcxcxsAxSCL,xSCxsAL,TxLSxSxLXCxSCL15⑤若，令，注：步骤⑤的作用选优并记录历史最好点⑥更新T表，转步2(存入T表中的第一个位置)三.TS的算法步骤（3）xCxCxxxCxCx16失败出口(避免)破禁检查初始开始更新T表停止YNXxT0kTxS1kkNGk停止YN若令TxSxsxsOptxSk,xSXkxsAxSCL,TxLSxSxL若xCxCxx输出终止出口xcx,step2step3step4step5step1邻域移动择优规则171.从邻域搜索的方法看移向中最好的解，但不与当前解比较是中的最优点，但可能劣于四.TS可以克服局优的分析（1）TxSxsxsOptxSk,TxSTxSxSkxSCkxC182.选优规则看始终保持历史上的最优解，不以当前解为最优3.从停止规则上看不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。四.TS可以克服局优的分析（2）191.问题的提出由7层不同的绝缘材料构成的一种绝缘体，应如何排列顺序，可获得最好的绝缘性能。五.TS举例（1）20编码方式：顺序编码初始编码：2-5-7-3-4-6-1目标值：极大化目标值。邻域定义：两两交换是一个邻域移动邻域大小：TabuSize：3NG：5五.TS举例（2）21①初始表初始编码：2-5-7-3-4-6-1结论：交换4和5五.TS举例（3）移动5，467，443，622，304，1-1…………10xcTT表123xSxc22②迭代1编码：2-4-7-3-5-6-1==16结论：交换1和3五.TS举例（4）移动3，122，313，4-17，1-26，1-4…………T表14，523xSxcxcxC23③迭代2编码：2-4-7-1-5-6-3==18结论：因交换1和3已在禁忌表中，故只能交换2和4五.TS举例（5）移动1，3-22，4-47，6-64，5-75，3-9…………T表11，324，53xSxcxcxc若选择这项=16，渴望水平不能发生作用xC24④迭代3编码：4-2-7-1-5-6-3=14，=18结论：因渴望水平发挥作用，交换在破禁表中的4,5五.TS举例（6）移动4，565，327，101，3-32，6-6…………T表12，421，334，5xSxcxc因=20大于渴望水平=18此时渴望水平发生作用，破禁。交换4和5。xcxsA,xC25⑤迭代4编码：5-2-7-1-4-6-3==20结论：交换7和1五.TS举例（7）移动7，104，3-36，3-55，4-62，6-8…………T表14，522，431，3xSxcxcxC26⑥迭代5编码：5-2-1-7-4-6-3==20结论：迭代已到5次，得到最优解5-2-7-1-4-6-3和5-2-1-7-4-6-3==20五.TS举例（8）xcxCxcxC271.引入中长期表的目的改善TS的广域搜索能力，TS的局域搜索能力很好，邻域选优快，但广域搜索能力较差。搜索能力是TS的关键，采用中长期表可改善TS的广域搜索能力。六.TS的中、长期表的使用（1）282.中期表——频数表①频数表的作用频数表是用来记忆不同方向的移动次数，从而加以惩罚(比如两两交换，记录每对交换的发生次数)以提高搜索方向的多样性。六.TS的中、长期表的使用（2）29在邻域选优公式中，令注：惩罚因子的取值一般应远小于目标值(1%目标值或1‰目标值)，越大分散性越好，广域搜索能力强，但会损坏邻域搜索。六.TS的中、长期表的使用（3）TxSxsxsNxsCTxSxsxsOpt,min,是惩罚因子的移动次数，是其中xsxsN30②频数表的记录方法I.建立n×n的数组，对上半部分每做一步搜索将所有0的数减1；II.对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size;III.T表的下半部分，用来记频数，每次(i,j)交换(ij)，对应的((j,i)+1)来记忆频数。六.TS的中、长期表的使用（4）31频数表的优点：同一数组作为T表和频数表共同使用，方便操作又节省了时间。六.TS的中、长期表的使用（5）32频数表：Tabu-Size=7六.TS的中、长期表的使用（6）T表11，221，53\347\2625\5,252\2447\33\2614115\17654321\N333.长期表的使用——多阶段TS算法①长期表的作用长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离。六.TS的中、长期表的使用（7）34②图示六.TS的中、长期表的使用（8）1x2x3x4x5x6x7x8x9x35③函数表达式长期表的TS有很好的性能。六.TS的中、长期表的使用（9）个点集是随机产生的分分散到可行域的不同部这种方法使初始解充分是已选初始解的集合其中，20,B2121KRKxxkDkDAugMaxKxxBLnilikiBLniliki361.问题的来源1994年Icmell发表的论文，C&ORV21,No.8ComputerandOperationsResearch问题：带有折扣资金流的约束网络计划问题(资源受限)2.例题见下页七.TS表的应用举例（1）37n个工作组成的项目,求极小化折扣资金流的计划七.TS表的应用举例（2）折扣：带有利息α：折扣率：工作i的工期d间：工作i的最迟完工时l间：工作i的最早开工时eD：项目的需求完工期可用量：t时刻第k种资源的tR资源k的需求：工作i每单位时间对r：工作i的资金需求q：j接在i后ji,Hiiikiki38H={(1,3),(1,4),(2,5),(2,6),(3,7),(5,7),(4,8),(6,8)}解：变量定义：七.TS表的应用举例（3）完成在时间工作其它titxi10SE1268734539问题模型：①式②式③式④式⑤式ti,10ji,T,1,2,t,,2,11..min1111或itletjtletjitnidttskisikletittntniletTDtittixHtxdtxtRxrnixtsPexDtxeqjjiiiiiii脱期罚项n是最后完成的工作脱期惩罚因子40数学模型的解释：①式折扣资金；②式每个工作只能完成1次;③式资源约束；④式工作i没做完不允许做工作j仔细思考，以上数学表达式的下标设计是非常精妙的尤其是③式资源约束。七.TS表的应用举例（5）41将以上模型简化七.TS表的应用举例（6）完成在时间工作其它ti10itx完工，在时间表示工作设titxi42ilxeHxdxmkTttRxtxifrtsPeDxeqiiijjikniiiikxninxini,ji,,,,2,1;,,2,1;1d-..min1i1模型变为：该式表示i在j之前这一项表示条件取和xx,0max注：对于条件取和、，常规的优化方法不能计算，但可用TS求解。xx,0max43编码方式：自然数编码状态：邻域定义：邻域大小：2n七.TS表的应用举例（8）nxxxX,,,21iiilex,144邻域搜索规则：中有可行解时，取可行解中目标值最小的邻域解；中无可行解时，取约束违反量最小的邻域解七.TS表的应用举例（9）TxSTxS451.TS的记忆功能——短、中、长期表要灵活使用2.TS相对于GA,SA是更快的算法，局域搜索能力强，但全局搜索能力较弱；3.改善TS的全局搜索能力，提高TS的分散性的方法①用长期表八.学习TS的几点体会（1）46②加大TabuSize③加大对频数的惩罚，即增大4.TS仍是一种启发式，不能保证最优性5.TS的理论工作较少八.学习TS的几点体会（2）