禁忌搜索算法教学课件

1第三章 禁忌搜索1第三章 禁忌搜索2第三章禁忌搜索一.导言二.禁忌搜索三.TS举例四.TS中短、中、长期表的使用五.学习TS的几点体会2第三章禁忌搜索3问题描述一.导言目标函数约束条件定义域注：X为离散点的集合，TS排斥实优化3问题描述一.导言目标函数约束条件定义域注：X为离散点的集合4局域搜索邻域的概念函数优化问题：邻域(N(x))通常定义为在给定距离空间内，以一点(x)为中心的一个球体组合优化问题：

且

，称为一个邻域映射，其中表示X所有子集组成的集合。N(x)称为x的邻域，称为x的一个邻居。一.导言4局域搜索一.导言5局域搜索邻域的概念例：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)}

一.导言5局域搜索一.导言6局域搜索邻域的概念例：

解的邻域映射可由2-opt，推广到k-opt，即对k个元素按一定规则互换。一.导言邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。6局域搜索一.导言邻域的构造依赖于解的表示，邻域的结构在智能7练习定义邻域移动为：位值加1或减1对整数编码[22353]，下列编码是否在其邻域内：

[23353]

[23253]

[22355]

[22343]

[22253]

[22344]

是否否是是否7练习定义邻域移动为：位值加1或减1是否否是是否8练习定义邻域移动为：2-Opt对顺序编码[42351]，下列编码是否在其邻域内：

[43251]

[43512]

[43351]

[52341][12354][34251]

是否否是是否8练习定义邻域移动为：2-Opt是否否是是否9局域搜索局域搜索算法过程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。一.导言9局域搜索一.导言10局域搜索示例例：五个城市的对称TSP问题一.导言初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。10局域搜索一.导言初始解为xbest=(ABCDE)，f(11局域搜索示例方法：全邻域搜索

第1步

N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，对应目标函数为f(x)={45,43,45,60,60,59,44}

xbest:=xnow=(ACBDE)一.导言ABCDE11局域搜索一.导言ABCD12局域搜索示例方法：全邻域搜索

第2步

N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43,45,44,59,59,58,43}

xbest:=xnow=(ACBDE)一.导言12局域搜索一.导言13局域搜索优劣性通用易实现，易于理解搜索结果依赖于初始点和邻域结构，容易陷入局优一.导言13局域搜索一.导言14局域搜索优劣性通用易实现，易于理解搜索结果依赖于初始点和邻域结构，容易陷入局优一.导言为了得到好的解，可以采用的策略有(1)扩大邻域结构，(2)变邻域结构，(3)多初始点。14局域搜索一.导言为了得到好的解，可以采用的策略有(1)扩15TS的提出人类在选择过程中局优记忆功能，比如走迷宫时，当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性，这样就可以确定性的避开迂回搜索。借鉴人类的智能思考特性，采用禁忌策略尽量避免迂回搜索就构成了TS算法。Glover在1977年提出TS。相对于LS，TS的优点是能够通过接受劣解来逃离局优，在90年代初开始受到广泛的关注。二.禁忌搜索/~glover/15TS的提出二.禁忌搜索http://spot.color16构成要素解的表达编码方法：用数学的形式来表示问题的解。初始解的产生：随机产生或者采用启发式方法产生一个可行解。适值函数C(x)的构造：往往直接将目标函数f(x)作为适值函数。二.禁忌搜索16构成要素二.禁忌搜索17构成要素邻域及邻域移动定义邻域移动s，例如，在函数优化问题中邻域移动可以定义为给定步长和移动方向；在组合优化问题中邻域移动可以定义为某种排练序列置换。邻域是由当前解x及其通过定义的邻域移动能够达到的所有解构成的集合。二.禁忌搜索注意：移动的意义是灵活的，目的是便于搜索。17构成要素二.禁忌搜索注意：移动的意义是灵活的，目的是便于18构成要素禁忌表禁忌表(T表)的作用：防止搜索出现循环将移动、移动分量或适值作为禁忌对象表的长度称为Tabu-Size，可以用来控制局域搜索和广域搜索表是动态更新的——把最新的解记入，最老的解从表中释放(解禁)二.禁忌搜索18构成要素二.禁忌搜索19构成要素选择策略选择策略的作用：保证TS具有跳出局优的能力当前解x每一步总是移动到邻域N(x)中未被禁忌的最优解，即若则令，本次移动到邻域N(x)中未被禁忌的最优解二.禁忌搜索19构成要素二.禁忌搜索20构成要素渴望水平渴望水平A(s,x)是一个取决于s和x的值，若有成立，则s(x)不受T表限制。也就是说即使存在x仍然可以移动到s(x)。A(s,x)一般选取为历史上所能达到的最优适值。二.禁忌搜索禁忌策略和渴望水平共同构成了TS的两大核心移动规则20构成要素二.禁忌搜索禁忌策略和渴望水平共同构成了TS的两21构成要素停止准则设定最大迭代次数得到满意解设定某个对象的最大禁忌频率二.禁忌搜索21构成要素二.禁忌搜索22算法步骤Step1选一个初始点x()，令 ，，渴望水平，迭代指标k=0；Step2若，则停止；否则令k=k+1；若k>NG(其中NG为最大迭代数)，则停止；二.禁忌搜索注： 表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度<邻域大小)。Step2的作用是设置循环体出口。22算法步骤二.禁忌搜索注： 表示非正常终止，造23算法步骤Step3若，若，令，转Step5；Step4若，令；二.禁忌搜索注：Step3的作用破禁检查注：Step4的作用邻域选优23算法步骤二.禁忌搜索注：Step3的作用破禁检查注：S24算法步骤Step5若，令，，；Step6更新T表，转Step2；二.禁忌搜索注：Step5的作用选优并记录历史最好点，更新渴望水平注：x存入T表中的第一个位置24算法步骤二.禁忌搜索注：Step5的作用选优并记录历史25TS克服局优分析从邻域搜索的方法看移向N(x)\T中最好的解，而不于当前解比较，

是N(x)\T中的最好点，但可能劣于二.禁忌搜索25TS克服局优分析二.禁忌搜索26TS克服局优分析从选优规则看始终保持历史上的最优解，不以当前解为最优从停止规则上看不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。二.禁忌搜索26TS克服局优分析二.禁忌搜索27问题提出由7层不同的绝缘材料构成的一种绝缘体，应如何排列顺序，可获得最好的绝缘性能?三.TS举例27问题提出三.TS举例28算法设计编码方式：顺序编码初始解的产生：随机产生，如2-5-7-3-4-6-1适值函数：极大化目标值邻域移动方式：2-OPT，即两两交换其他参数：禁忌对象为邻域移动方式，T表长度设为3，NG设为5三.TS举例28算法设计三.TS举例29初始表初始编码：2-5-7-3-4-6-1结论：交换4和5三.TS举例移动5，467，443，622，304，1-1…………T表12329初始表三.TS举例移动5，467，443，622，30430迭代1

编码：2-4-7-3-5-6-1

结论：交换1和3三.TS举例移动3，122，313，4-17，1-26，1-4…………T表14，52330迭代1

编码：2-4-7-3-5-6-1三.TS举例移动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若选择这项C(x) =16，渴望水平不能发生作用31迭代2

编码：2-4-7-1-5-6-3三.TS举例移动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因C(x)=20>A(s,x)=18，此时渴望水平发生作用，破禁。交换4和5。 32迭代3

编码：4-2-7-1-5-6-3三.TS举例移动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，333迭代4

编码：5-2-7-1-4-6-3三.TS举例移动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举例T表11，724，532，434迭代5

编码：5-2-1-7-4-6-3三.TS举例T表35短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用35短期表-T表四.TS中短、中、长期表的使用36短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用变化因素解的变化解分量的变化函数值的变化36短期表-T表四.TS中短、中、长期表的使用变化因素解的变37短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用禁忌对象解移动函数值37短期表-T表四.TS中短、中、长期表的使用禁忌对象解移动38练习初始解：(ABCDE)，邻域移动方式为2-OPT，T表长度为4，NG=5，分别以解、移动和函数值为禁忌对象进行求解，并分析各自的特点。38练习初始解：(ABCDE)，邻域移动方式为2-OPT39短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用受禁范围：解的变化邻域移动函数值计算时间：函数值邻域移动解的变化摆脱局优：函数值邻域移动解的变化39短期表-T表四.TS中短、中、长期表的使用受禁范围：解的40短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值设为常数，易于实现设为变化的数，在之间变化四.TS中短、中、长期表的使用禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。40短期表-T表四.TS中短、中、长期表的使用禁忌长度过短，41练习初始解：(ABCDE)，邻域移动方式为2-OPT，以移动为禁忌对象，NG=5，T表长度分别设为2,4和6进行求解，并分析各自的特点。41练习初始解：(ABCDE)，邻域移动方式为2-OPT42中期表-频数表频数表的作用：频数表是用来记忆不同方向的移动次数，从而加以惩罚（比如2-OPT，记录每对交换的发生次数）从而提高搜索方向的多样性在邻域选优公式中，令其中，E(s(x))表示移动s(x)的出现频数，α为惩罚因子四.TS中短、中、长期表的使用注：惩罚因子α的取值一般应远小于目标值（1%目标值或1‰目标值），α越大分散性越好，广域搜索能力强，但会损坏邻域搜索。42中期表-频数表四.TS中短、中、长期表的使用注：惩罚因子43中期表-频数表频数表的记录方法建立n×n的数组，对上半部分每做一步搜索将所有>0的数减1；对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size；下半部分用来记频数，每次(i,j)(i<j)交换，对应的((j,i)+1)来记忆频数四.TS中短、中、长期表的使用频数表的优点：同一数组作为T表和频数表共同使用，方便操作又节了时间。43中期表-频数表四.TS中短、中、长期表的使用频数表的优点44频数表：Tabu-Size=7四.TS中短、中、长期表的使用T表13，421，735，643，752，664，571，3\12345671\162\331\7441\251\5611\711\44频数表：Tabu-Size=7四.TS中短、中、长期表的45频数表：Tabu-Size=7四.TS中短、中、长期表的使用T表11，323，431，745，653，762，674，5\12345671\752\232\6341\151\4611\711\45频数表：Tabu-Size=7四.TS中短、中、长期表的46长期表-多阶段TS长期表的作用：长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离四.TS中短、中、长期表的使用46长期表-多阶段TS四.TS中短、中、长期表的使用47长期表-多阶段TS函数表达式四.TS中短、中、长期表的使用47长期表-多阶段TS四.TS中短、中、长期表的使用48TS的记忆功能——短、中、长期表要灵活使用TS相对于GA是更快的算法，局域搜索能力强，但全局搜索能力较弱；改善TS的全局搜索能力，提高TS的分散性的方法用长期表加大TabuSize加大对频数的惩罚，即增大αTS仍是一种启发式，不能保证最优性TS的理论工作较少五.学习TS的几点体会48TS的记忆功能——短、中、长期表要灵活使用五.学习TS的49作业30城市TSP问题（d*=423.741byDBFogel）TSPBenchmark问题

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;45049作业30城市TSP问题（d*=423.741by50第三章 禁忌搜索1第三章 禁忌搜索51第三章禁忌搜索一.导言二.禁忌搜索三.TS举例四.TS中短、中、长期表的使用五.学习TS的几点体会2第三章禁忌搜索52问题描述一.导言目标函数约束条件定义域注：X为离散点的集合，TS排斥实优化3问题描述一.导言目标函数约束条件定义域注：X为离散点的集合53局域搜索邻域的概念函数优化问题：邻域(N(x))通常定义为在给定距离空间内，以一点(x)为中心的一个球体组合优化问题：

且

，称为一个邻域映射，其中表示X所有子集组成的集合。N(x)称为x的邻域，称为x的一个邻居。一.导言4局域搜索一.导言54局域搜索邻域的概念例：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)}

一.导言5局域搜索一.导言55局域搜索邻域的概念例：

解的邻域映射可由2-opt，推广到k-opt，即对k个元素按一定规则互换。一.导言邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。6局域搜索一.导言邻域的构造依赖于解的表示，邻域的结构在智能56练习定义邻域移动为：位值加1或减1对整数编码[22353]，下列编码是否在其邻域内：

[23353]

[23253]

[22355]

[22343]

[22253]

[22344]

是否否是是否7练习定义邻域移动为：位值加1或减1是否否是是否57练习定义邻域移动为：2-Opt对顺序编码[42351]，下列编码是否在其邻域内：

[43251]

[43512]

[43351]

[52341][12354][34251]

是否否是是否8练习定义邻域移动为：2-Opt是否否是是否58局域搜索局域搜索算法过程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。一.导言9局域搜索一.导言59局域搜索示例例：五个城市的对称TSP问题一.导言初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。10局域搜索一.导言初始解为xbest=(ABCDE)，f(60局域搜索示例方法：全邻域搜索

第1步

N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，对应目标函数为f(x)={45,43,45,60,60,59,44}

xbest:=xnow=(ACBDE)一.导言ABCDE11局域搜索一.导言ABCD61局域搜索示例方法：全邻域搜索

第2步

N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43,45,44,59,59,58,43}

xbest:=xnow=(ACBDE)一.导言12局域搜索一.导言62局域搜索优劣性通用易实现，易于理解搜索结果依赖于初始点和邻域结构，容易陷入局优一.导言13局域搜索一.导言63局域搜索优劣性通用易实现，易于理解搜索结果依赖于初始点和邻域结构，容易陷入局优一.导言为了得到好的解，可以采用的策略有(1)扩大邻域结构，(2)变邻域结构，(3)多初始点。14局域搜索一.导言为了得到好的解，可以采用的策略有(1)扩64TS的提出人类在选择过程中局优记忆功能，比如走迷宫时，当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性，这样就可以确定性的避开迂回搜索。借鉴人类的智能思考特性，采用禁忌策略尽量避免迂回搜索就构成了TS算法。Glover在1977年提出TS。相对于LS，TS的优点是能够通过接受劣解来逃离局优，在90年代初开始受到广泛的关注。二.禁忌搜索/~glover/15TS的提出二.禁忌搜索http://spot.color65构成要素解的表达编码方法：用数学的形式来表示问题的解。初始解的产生：随机产生或者采用启发式方法产生一个可行解。适值函数C(x)的构造：往往直接将目标函数f(x)作为适值函数。二.禁忌搜索16构成要素二.禁忌搜索66构成要素邻域及邻域移动定义邻域移动s，例如，在函数优化问题中邻域移动可以定义为给定步长和移动方向；在组合优化问题中邻域移动可以定义为某种排练序列置换。邻域是由当前解x及其通过定义的邻域移动能够达到的所有解构成的集合。二.禁忌搜索注意：移动的意义是灵活的，目的是便于搜索。17构成要素二.禁忌搜索注意：移动的意义是灵活的，目的是便于67构成要素禁忌表禁忌表(T表)的作用：防止搜索出现循环将移动、移动分量或适值作为禁忌对象表的长度称为Tabu-Size，可以用来控制局域搜索和广域搜索表是动态更新的——把最新的解记入，最老的解从表中释放(解禁)二.禁忌搜索18构成要素二.禁忌搜索68构成要素选择策略选择策略的作用：保证TS具有跳出局优的能力当前解x每一步总是移动到邻域N(x)中未被禁忌的最优解，即若则令，本次移动到邻域N(x)中未被禁忌的最优解二.禁忌搜索19构成要素二.禁忌搜索69构成要素渴望水平渴望水平A(s,x)是一个取决于s和x的值，若有成立，则s(x)不受T表限制。也就是说即使存在x仍然可以移动到s(x)。A(s,x)一般选取为历史上所能达到的最优适值。二.禁忌搜索禁忌策略和渴望水平共同构成了TS的两大核心移动规则20构成要素二.禁忌搜索禁忌策略和渴望水平共同构成了TS的两70构成要素停止准则设定最大迭代次数得到满意解设定某个对象的最大禁忌频率二.禁忌搜索21构成要素二.禁忌搜索71算法步骤Step1选一个初始点x()，令 ，，渴望水平，迭代指标k=0；Step2若，则停止；否则令k=k+1；若k>NG(其中NG为最大迭代数)，则停止；二.禁忌搜索注： 表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度<邻域大小)。Step2的作用是设置循环体出口。22算法步骤二.禁忌搜索注： 表示非正常终止，造72算法步骤Step3若，若，令，转Step5；Step4若，令；二.禁忌搜索注：Step3的作用破禁检查注：Step4的作用邻域选优23算法步骤二.禁忌搜索注：Step3的作用破禁检查注：S73算法步骤Step5若，令，，；Step6更新T表，转Step2；二.禁忌搜索注：Step5的作用选优并记录历史最好点，更新渴望水平注：x存入T表中的第一个位置24算法步骤二.禁忌搜索注：Step5的作用选优并记录历史74TS克服局优分析从邻域搜索的方法看移向N(x)\T中最好的解，而不于当前解比较，

是N(x)\T中的最好点，但可能劣于二.禁忌搜索25TS克服局优分析二.禁忌搜索75TS克服局优分析从选优规则看始终保持历史上的最优解，不以当前解为最优从停止规则上看不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。二.禁忌搜索26TS克服局优分析二.禁忌搜索76问题提出由7层不同的绝缘材料构成的一种绝缘体，应如何排列顺序，可获得最好的绝缘性能?三.TS举例27问题提出三.TS举例77算法设计编码方式：顺序编码初始解的产生：随机产生，如2-5-7-3-4-6-1适值函数：极大化目标值邻域移动方式：2-OPT，即两两交换其他参数：禁忌对象为邻域移动方式，T表长度设为3，NG设为5三.TS举例28算法设计三.TS举例78初始表初始编码：2-5-7-3-4-6-1结论：交换4和5三.TS举例移动5，467，443，622，304，1-1…………T表12329初始表三.TS举例移动5，467，443，622，30479迭代1

编码：2-4-7-3-5-6-1

结论：交换1和3三.TS举例移动3，122，313，4-17，1-26，1-4…………T表14，52330迭代1

编码：2-4-7-3-5-6-1三.TS举例移动80迭代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若选择这项C(x) =16，渴望水平不能发生作用31迭代2

编码：2-4-7-1-5-6-3三.TS举例移动81迭代3

编码：4-2-7-1-5-6-3

结论：因渴望水平发挥作用，交换4和5三.TS举例移动4，565，327，101，3-32，6-6…………T表12，421，334，5因C(x)=20>A(s,x)=18，此时渴望水平发生作用，破禁。交换4和5。 32迭代3

编码：4-2-7-1-5-6-3三.TS举例移动82迭代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，333迭代4

编码：5-2-7-1-4-6-3三.TS举例移动83迭代5

编码：5-2-1-7-4-6-3

结论：迭代已到5次，得到最优解 5-2-7-1-4-6-3和5-2-1-7-4-6-3 三.TS举例T表11，724，532，434迭代5

编码：5-2-1-7-4-6-3三.TS举例T表84短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用35短期表-T表四.TS中短、中、长期表的使用85短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用变化因素解的变化解分量的变化函数值的变化36短期表-T表四.TS中短、中、长期表的使用变化因素解的变86短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用禁忌对象解移动函数值37短期表-T表四.TS中短、中、长期表的使用禁忌对象解移动87练习初始解：(ABCDE)，邻域移动方式为2-OPT，T表长度为4，NG=5，分别以解、移动和函数值为禁忌对象进行求解，并分析各自的特点。38练习初始解：(ABCDE)，邻域移动方式为2-OPT88短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值四.TS中短、中、长期表的使用受禁范围：解的变化邻域移动函数值计算时间：函数值邻域移动解的变化摆脱局优：函数值邻域移动解的变化39短期表-T表四.TS中短、中、长期表的使用受禁范围：解的89短期表-T表T表的主要指标：禁忌对象：T表中被禁忌的那些变化元素禁忌长度：T表的长度，禁忌对象的最大值设为常数，易于实现设为变化的数，在之间变化四.TS中短、中、长期表的使用禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。40短期表-T表四.TS中短、中、长期表的使用禁忌长度过短，90练习初始解：(ABCDE