禁忌搜索算法教程

1第三章禁忌搜索2第三章禁忌搜索一.导言二.禁忌搜索三.TS举例四.TS中短、中、长期表的使用五.学习TS的几点体会31.问题描述一.导言min()fx..st()0gxxX目标函数约束条件定义域注：X为离散点的集合，TS排斥实优化42.局域搜索邻域的概念①函数优化问题：邻域(N(x))通常定义为在给定距离空间内，以一点(x)为中心的一个球体②组合优化问题：且，称为一个邻域映射，其中表示X所有子集组成的集合。N(x)称为x的邻域，称为x的一个邻居。一.导言:()2XNxXNx()xNx2X()yNx52.局域搜索邻域的概念例：TSP问题解的一种表示方法为D={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列}，定义它的邻域映射为2-opt，即x中的两个元素进行对换，N(x)中共包含x的Cn2=n(n-1)/2个邻居和x本身。例如：x=(1,2,3,4)，则C42=6，N(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)}一.导言62.局域搜索邻域的概念例：解的邻域映射可由2-opt，推广到k-opt，即对k个元素按一定规则互换。一.导言邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。7练习定义邻域移动为：位值加1或减1对整数编码[22353]，下列编码是否在其邻域内：[23353][23253][22355][22343][22253][22344]是否否是是否8练习定义邻域移动为：2-Opt对顺序编码[42351]，下列编码是否在其邻域内：[43251][43512][43351][52341][12354][34251]是否否是是否92.局域搜索局域搜索算法过程一.导言STEP1选定一个初始可行解x0，记录当前最优解xbest:=x0,T=N(xbest)；STEP2当T\{xbest}=Φ时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解xnow；若f(xnow)f(xbest)，则xbest:=xnow，T=N(xbest)；否则T:=T\S；重复STEP2。102.局域搜索示例例：五个城市的对称TSP问题一.导言初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。112.局域搜索示例方法：全邻域搜索第1步N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，对应目标函数为f(x)={45,43,45,60,60,59,44}xbest:=xnow=(ACBDE)一.导言ABCDE122.局域搜索示例方法：全邻域搜索第2步N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43,45,44,59,59,58,43}xbest:=xnow=(ACBDE)一.导言132.局域搜索优劣性①通用易实现，易于理解②搜索结果依赖于初始点和邻域结构，容易陷入局优一.导言0x0x142.局域搜索优劣性①通用易实现，易于理解②搜索结果依赖于初始点和邻域结构，容易陷入局优一.导言为了得到好的解，可以采用的策略有(1)扩大邻域结构，(2)变邻域结构，(3)多初始点。151.TS的提出人类在选择过程中局优记忆功能，比如走迷宫时，当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性，这样就可以确定性的避开迂回搜索。借鉴人类的智能思考特性，采用禁忌策略尽量避免迂回搜索就构成了TS算法。Glover在1977年提出TS。相对于LS，TS的优点是能够通过接受劣解来逃离局优，在90年代初开始受到广泛的关注。二.禁忌搜索~glover/162.构成要素解的表达①编码方法：用数学的形式来表示问题的解。②初始解的产生：随机产生或者采用启发式方法产生一个可行解。③适值函数C(x)的构造：往往直接将目标函数f(x)作为适值函数。二.禁忌搜索172.构成要素邻域及邻域移动①定义邻域移动s，例如，在函数优化问题中邻域移动可以定义为给定步长和移动方向；在组合优化问题中邻域移动可以定义为某种排练序列置换。②邻域是由当前解x及其通过定义的邻域移动能够达到的所有解构成的集合。二.禁忌搜索注意：移动的意义是灵活的，目的是便于搜索。182.构成要素禁忌表禁忌表(T表)的作用：防止搜索出现循环①将移动、移动分量或适值作为禁忌对象②表的长度称为Tabu-Size，可以用来控制局域搜索和广域搜索③表是动态更新的——把最新的解记入，最老的解从表中释放(解禁)二.禁忌搜索192.构成要素选择策略选择策略的作用：保证TS具有跳出局优的能力当前解x每一步总是移动到邻域N(x)中未被禁忌的最优解，即若则令，本次移动到邻域N(x)中未被禁忌的最优解二.禁忌搜索()(),\kCsxOptCsxsxNxT()kxsx()ksx202.构成要素渴望水平渴望水平A(s,x)是一个取决于s和x的值，若有成立，则s(x)不受T表限制。也就是说即使存在x仍然可以移动到s(x)。A(s,x)一般选取为历史上所能达到的最优适值。二.禁忌搜索,CsxAsx()sxT禁忌策略和渴望水平共同构成了TS的两大核心移动规则212.构成要素停止准则①设定最大迭代次数②得到满意解③设定某个对象的最大禁忌频率二.禁忌搜索223.算法步骤Step1选一个初始点x()，令，，渴望水平，迭代指标k=0；Step2若，则停止；否则令k=k+1；若kNG(其中NG为最大迭代数)，则停止；二.禁忌搜索xX:xxT*(,)()AsxCx\NxT注：表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度邻域大小)。Step2的作用是设置循环体出口。\NxT233.算法步骤Step3若若，令，转Step5；Step4若，令；二.禁忌搜索,LCsxOptCsxsxNx(,)LCsxAsx()Lxsx注：Step3的作用破禁检查,\KCsxOptCsxsxNxT()Kxsx注：Step4的作用邻域选优243.算法步骤Step5若，令，，；Step6更新T表，转Step2；二.禁忌搜索注：Step5的作用选优并记录历史最好点，更新渴望水平CxCxxxCxCx,AsxCx注：x存入T表中的第一个位置254.TS克服局优分析从邻域搜索的方法看移向N(x)\T中最好的解，而不于当前解比较，是N(x)\T中的最好点，但可能劣于二.禁忌搜索,\KsxOptsxsxNxTKsxKCsx*Cx264.TS克服局优分析从选优规则看始终保持历史上的最优解，不以当前解为最优从停止规则上看不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。二.禁忌搜索271.问题提出由7层不同的绝缘材料构成的一种绝缘体，应如何排列顺序，可获得最好的绝缘性能?三.TS举例282.算法设计编码方式：顺序编码初始解的产生：随机产生，如2-5-7-3-4-6-1适值函数：极大化目标值邻域移动方式：2-OPT，即两两交换其他参数：禁忌对象为邻域移动方式，T表长度设为3，NG设为5三.TS举例29①初始表初始编码：2-5-7-3-4-6-1结论：交换4和5三.TS举例移动5，467，443，622，304，1-1…………10CxTT表123xSCx*xx*(,)()10AsxCx30②迭代1编码：2-4-7-3-5-6-1结论：交换1和3三.TS举例移动3，122，313，4-17，1-26，1-4…………T表14，523xSCx16Cx*xx*(,)()16AsxCx31③迭代2编码：2-4-7-1-5-6-3结论：因交换1和3已在禁忌表中，故只能交换2和4三.TS举例移动1，3-22，4-47，6-64，5-75，3-9…………T表11，324，53xSCx若选择这项C(x)=16，渴望水平不能发生作用18Cx*xx*(,)()18AsxCx32④迭代3编码：4-2-7-1-5-6-3结论：因渴望水平发挥作用，交换4和5三.TS举例移动4，565，327，101，3-32，6-6…………T表12，421，334，5xSCx14Cx因C(x)=20A(s,x)=18，此时渴望水平发生作用，破禁。交换4和5。*(,)()18AsxCx33⑤迭代4编码：5-2-7-1-4-6-3结论：交换7和1三.TS举例移动7，104，3-36，3-55，4-62，6-8…………T表14，522，431，3xSCx20Cx*xx*(,)()20AsxCx34⑥迭代5编码：5-2-1-7-4-6-3结论：迭代已到5次，得到最优解5-2-7-1-4-6-3和5-2-1-7-4-6-3三.TS举例()20Cx*()20CxT表11，724，532，4351.短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用361.短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用变化因素解的变化解分量的变化函数值的变化371.短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用禁忌对象解移动函数值38练习初始解：(ABCDE)，邻域移动方式为2-OPT，T表长度为4，NG=5，分别以解、移动和函数值为禁忌对象进行求解，并分析各自的特点。391.短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用受禁范围：解的变化邻域移动函数值计算时间：函数值邻域移动解的变化摆脱局优：函数值邻域移动解的变化401.短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值①设为常数，易于实现②设为变化的数，在之间变化四.TS中短、中、长期表的使用minmax[,]tt禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。41练习初始解：(ABCDE)，邻域移动方式为2-OPT，以移动为禁忌对象，NG=5，T表长度分别设为2,4和6进行求解，并分析各自的特点。422.中期表-频数表频数表的作用：频数表是用来记忆不同方向的移动次数，从而加以惩罚（比如2-OPT，记录每对交换的发生次数）从而提高搜索方向的多样性在邻域选优公式中，令其中，E(s(x))表示移动s(x)的出现频数，α为惩罚因子四.TS中短、中、长期表的使用,\min,\OptCsxsxNxTCsxEsxsxNxT注：惩罚因子α的取值一般应远小于目标值（1%目标值或1‰目标值），α越大分散性越好，广域搜索能力强，但会损坏邻域搜索。432.中期表-频数表频数表的记录方法①建立n×n的数组，对上半部分每做一步搜索将所有0的数减1；②对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size；③下半部分用来记频数，每次(i