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

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

所有子集组成的集合所有子集组成的集合所有子集组成的集合N N( (x x) )称为称为称为称为x x的的的的邻域邻域邻域邻域，，，， 称为称为称为称为x x的一个的一个的一个的一个邻居邻居邻居邻居一一. .导言导言4 42.2.局域搜索局域搜索Ø邻域的概念邻域的概念邻域的概念邻域的概念 例：例：例：例：TSPTSP问题解的一种表示方法为问题解的一种表示方法为问题解的一种表示方法为问题解的一种表示方法为D D={={x x=(=(i i1 1, ,i i2 2,…,,…,i in n)| )| i i1 1, ,i i2 2,…,,…,i in n是是是是1,2,…,1,2,…,n n的排列的排列的排列的排列} }，定义它的邻域映射为，定义它的邻域映射为，定义它的邻域映射为，定义它的邻域映射为 2-opt2-opt，即，即，即，即x x中的两个元素进行对换，中的两个元素进行对换，中的两个元素进行对换，中的两个元素进行对换，N N( (x x) )中共包含中共包含中共包含中共包含x x的的的的C Cn n2 2= =n n( (n n-1)/2-1)/2个邻居和个邻居和个邻居和个邻居和x x本身。

本身 例如：例如：例如：例如：x x=(1,2,3,4)=(1,2,3,4)，，，， 则则则则C C4 42 2=6=6，，，，N N( (x x)={(1,2,3,4), (2,1,3,4), (3,2,1,4), )={(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)}(4,2,3,1), (1,3,2,4), (1,4,3,2), (1,2,4,3)} 一一. .导言导言5 52.2.局域搜索局域搜索Ø邻域的概念邻域的概念邻域的概念邻域的概念 例：例：例：例： 解的邻域映射可由解的邻域映射可由解的邻域映射可由解的邻域映射可由2 2-opt-opt，推广到，推广到，推广到，推广到k k-opt-opt，即对，即对，即对，即对k k个元个元个元个元素按一定规则互换素按一定规则互换素按一定规则互换素按一定规则互换 一一. .导言导言邻域的构造依赖于解的表示，邻域的结构邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。

在智能优化算法中起重要的作用6 6练练 习习定义邻域移动为：位值加1或减1对整数编码[ 2 2 3 5 3]，下列编码是否在其邻域内： [2 3 3 5 3] [2 3 2 5 3] [2 2 3 5 5] [2 2 3 4 3] [2 2 2 5 3] [2 2 3 4 4] 是是否否否否是是是是否否7 7练练 习习定义邻域移动为：2-Opt对顺序编码[ 4 2 3 5 1]，下列编码是否在其邻域内： [4 3 2 5 1] [4 3 5 1 2] [4 3 3 5 1] [5 2 3 4 1] [1 2 3 5 4] [3 4 2 5 1] 是是否否否否是是是是否否8 82.2.局域搜索局域搜索Ø局域搜索算法过程局域搜索算法过程一一. .导言导言ØSTEP 1 选定一个初始可行解选定一个初始可行解x0，记录当前最优解，记录当前最优解xbest:=x0, T=N(xbest)；；ØSTEP 2 当当T\{xbest}=Φ时，或满足其他停止运算准则时，输出时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从计算结果，停止运算；否则，从T中选一集合中选一集合S，得，得到到S中的最好解中的最好解xnow；若；若f (xnow)

9 92.2.局域搜索局域搜索Ø示例示例示例示例例：例：例：例：五个城市的对称五个城市的对称五个城市的对称五个城市的对称TSPTSP问题问题问题问题一一. .导言导言初始解为初始解为xbest=(ABCDE)，，f(xbest)=45，定义邻域映射，定义邻域映射为对换两个城市位置的为对换两个城市位置的2-opt，选定，选定A城市为起点城市为起点10102.2.局域搜索局域搜索Ø示例示例示例示例方法：方法：方法：方法：全邻域搜索全邻域搜索全邻域搜索全邻域搜索 第第第第1 1步步步步 N N( (x xbestbest)={()={(ABCDEABCDE) )，，( (ACBDEACBDE) )，，( (ADCBEADCBE) )，，( (AECDBAECDB) )，，( (ABDCEABDCE) )，，( (ABEDCABEDC) )，，( (ABCEDABCED)})}，，，， 对应目标函数为对应目标函数为对应目标函数为对应目标函数为f f( (x x)={45, 43, 45, 60, 60, 59, 44})={45, 43, 45, 60, 60, 59, 44} x xbestbest:=:=x xnownow=(=(ACBDEACBDE) )一一. .导言导言A B C D E11112.2.局域搜索局域搜索Ø示例示例示例示例方法：方法：方法：方法：全邻域搜索全邻域搜索全邻域搜索全邻域搜索 第第第第2 2步步步步 N N( (x xbestbest)={()={(ACBDEACBDE) )，，( (ABCDEABCDE) )，，( (ADBCEADBCE) )，，( (AEBDCAEBDC) )，，( (ACDBEACDBE) )，，( (ACEDBACEDB) )，，( (ACBEDACBED)})}，， 对应目标函数为对应目标函数为对应目标函数为对应目标函数为f f( (x x)={43, 45, 44, 59, 59, 58, 43})={43, 45, 44, 59, 59, 58, 43} x xbestbest:=:=x xnownow=(=(ACBDEACBDE) )一一. .导言导言12122.2.局域搜索局域搜索Ø优劣性优劣性优劣性优劣性①①通用易实现，易于理解通用易实现，易于理解通用易实现，易于理解通用易实现，易于理解②②搜索结果依赖于初始点和邻域结构，容易陷搜索结果依赖于初始点和邻域结构，容易陷搜索结果依赖于初始点和邻域结构，容易陷搜索结果依赖于初始点和邻域结构，容易陷入局优入局优入局优入局优一一. .导言导言13132.2.局域搜索局域搜索Ø优劣性优劣性优劣性优劣性①①通用易实现，易于理解通用易实现，易于理解通用易实现，易于理解通用易实现，易于理解②②搜索结果依赖于初始点和邻域结构，容易陷搜索结果依赖于初始点和邻域结构，容易陷搜索结果依赖于初始点和邻域结构，容易陷搜索结果依赖于初始点和邻域结构，容易陷入局优入局优入局优入局优一一. .导言导言为了得到好的解，可以采用的策略为了得到好的解，可以采用的策略有有(1)扩大扩大邻域结构，邻域结构，(2)变邻域结构，变邻域结构，(3)多初始点多初始点。

14141.1.TSTS的提出的提出Ø人类在选择过程中局优记忆功能，比如走迷宫人类在选择过程中局优记忆功能，比如走迷宫人类在选择过程中局优记忆功能，比如走迷宫人类在选择过程中局优记忆功能，比如走迷宫时，当发现有可能又回到某个地点的时候总会时，当发现有可能又回到某个地点的时候总会时，当发现有可能又回到某个地点的时候总会时，当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可有意识地避开先前选择的方向而选择其他的可有意识地避开先前选择的方向而选择其他的可有意识地避开先前选择的方向而选择其他的可能性，这样就可以确定性的避开能性，这样就可以确定性的避开能性，这样就可以确定性的避开能性，这样就可以确定性的避开迂回搜索迂回搜索迂回搜索迂回搜索Ø借鉴人类的智能思考特性，采用禁忌策略尽量借鉴人类的智能思考特性，采用禁忌策略尽量借鉴人类的智能思考特性，采用禁忌策略尽量借鉴人类的智能思考特性，采用禁忌策略尽量避免迂回搜索就构成了避免迂回搜索就构成了避免迂回搜索就构成了避免迂回搜索就构成了TSTSTSTS算法ØGloverGlover在在在在19771977年提出年提出年提出年提出TSTS。

相对于相对于LSLS，，，，TSTS的优点的优点的优点的优点是能够通过接受劣解来逃离局优，在是能够通过接受劣解来逃离局优，在是能够通过接受劣解来逃离局优，在是能够通过接受劣解来逃离局优，在9090年代初年代初年代初年代初开始受到广泛的关注开始受到广泛的关注开始受到广泛的关注开始受到广泛的关注二二. .禁忌搜索禁忌搜索15152.2.构成要素构成要素Ø解的表达解的表达解的表达解的表达①①编码方法：用数学的形式来表示问题的解编码方法：用数学的形式来表示问题的解编码方法：用数学的形式来表示问题的解编码方法：用数学的形式来表示问题的解②②初始解的产生：随机产生或者采用启发式方初始解的产生：随机产生或者采用启发式方初始解的产生：随机产生或者采用启发式方初始解的产生：随机产生或者采用启发式方法产生一个可行解法产生一个可行解法产生一个可行解法产生一个可行解③③适值函数适值函数适值函数适值函数C C( (x x) )的构造：往往直接将目标函数的构造：往往直接将目标函数的构造：往往直接将目标函数的构造：往往直接将目标函数f f( (x x) )作为适值函数作为适值函数作为适值函数作为适值函数二二. .禁忌搜索禁忌搜索16162.2.构成要素构成要素Ø邻域及邻域移动邻域及邻域移动邻域及邻域移动邻域及邻域移动①①定义邻域移动定义邻域移动定义邻域移动定义邻域移动s s，例如，在函数优化问题中邻，例如，在函数优化问题中邻，例如，在函数优化问题中邻，例如，在函数优化问题中邻域移动可以定义为给定步长和移动方向；在域移动可以定义为给定步长和移动方向；在域移动可以定义为给定步长和移动方向；在域移动可以定义为给定步长和移动方向；在组合优化问题中邻域移动可以定义为某种排组合优化问题中邻域移动可以定义为某种排组合优化问题中邻域移动可以定义为某种排组合优化问题中邻域移动可以定义为某种排练序列置换。

练序列置换练序列置换练序列置换②②邻域是由当前解邻域是由当前解邻域是由当前解邻域是由当前解x x及其通过定义的邻域移动能及其通过定义的邻域移动能及其通过定义的邻域移动能及其通过定义的邻域移动能够达到的所有解构成的集合够达到的所有解构成的集合够达到的所有解构成的集合够达到的所有解构成的集合二二. .禁忌搜索禁忌搜索注意：移动的意义是灵活的，目的是便于搜索注意：移动的意义是灵活的，目的是便于搜索17172.2.构成要素构成要素Ø禁忌表禁忌表禁忌表禁忌表禁忌表禁忌表禁忌表禁忌表( ( ( (T T表表表表) ) ) )的作用：防止搜索出现循环的作用：防止搜索出现循环的作用：防止搜索出现循环的作用：防止搜索出现循环①①将移动、移动分量或适值作为禁忌对象将移动、移动分量或适值作为禁忌对象将移动、移动分量或适值作为禁忌对象将移动、移动分量或适值作为禁忌对象②②表的长度称为表的长度称为表的长度称为表的长度称为Tabu-SizeTabu-Size，可以用来控制局域，可以用来控制局域，可以用来控制局域，可以用来控制局域搜索和广域搜索搜索和广域搜索搜索和广域搜索搜索和广域搜索③③表是动态更新的表是动态更新的表是动态更新的表是动态更新的————————把最新的解记入，最老把最新的解记入，最老把最新的解记入，最老把最新的解记入，最老的解从表中释放的解从表中释放的解从表中释放的解从表中释放( ( ( (解禁解禁解禁解禁) ) ) )二二. .禁忌搜索禁忌搜索18182.2.构成要素构成要素Ø选择策略选择策略选择策略选择策略选择策略的作用：保证选择策略的作用：保证选择策略的作用：保证选择策略的作用：保证TSTS具有跳出局优的能力具有跳出局优的能力具有跳出局优的能力具有跳出局优的能力当前解当前解当前解当前解x x每一步总是移动到邻域每一步总是移动到邻域每一步总是移动到邻域每一步总是移动到邻域N N( (x x) )中未被禁忌的最中未被禁忌的最中未被禁忌的最中未被禁忌的最优解，即若优解，即若优解，即若优解，即若则令则令则令则令 ，本次移动到邻域，本次移动到邻域，本次移动到邻域，本次移动到邻域N N( (x x) )中未被禁忌的中未被禁忌的中未被禁忌的中未被禁忌的最优解最优解最优解最优解二二. .禁忌搜索禁忌搜索19192.2.构成要素构成要素Ø渴望水平渴望水平渴望水平渴望水平渴望水平渴望水平渴望水平渴望水平A A( (s s, ,x x) )是一个取决于是一个取决于是一个取决于是一个取决于s s和和和和x x的值，若有的值，若有的值，若有的值，若有成立，则成立，则成立，则成立，则s s( (x x) )不受不受不受不受T T T T表限制。

也就是说即使存在表限制也就是说即使存在表限制也就是说即使存在表限制也就是说即使存在x x仍然可以移动到仍然可以移动到仍然可以移动到仍然可以移动到s s( (x x) )A A( (s s, ,x x) )一般选取为历史上所能达到的最优适值一般选取为历史上所能达到的最优适值一般选取为历史上所能达到的最优适值一般选取为历史上所能达到的最优适值二二. .禁忌搜索禁忌搜索禁忌策略和渴望水平共同构禁忌策略和渴望水平共同构成了成了TS的两大核心移动规则的两大核心移动规则20202.2.构成要素构成要素Ø停止准则停止准则停止准则停止准则①①设定最大迭代次数设定最大迭代次数设定最大迭代次数设定最大迭代次数②②得到满意解得到满意解得到满意解得到满意解③③设定某个对象的最大禁忌频率设定某个对象的最大禁忌频率设定某个对象的最大禁忌频率设定某个对象的最大禁忌频率二二. .禁忌搜索禁忌搜索21213.3.算法步骤算法步骤Step 1Step 1选一个初始点选一个初始点选一个初始点选一个初始点 x x( ( ) )，令，令，令，令 ，，，， ，，，，渴望水平渴望水平渴望水平渴望水平 ，迭代指标，迭代指标，迭代指标，迭代指标 k k=0=0；；；；Step 2Step 2若若若若 ，则停止；否则令，则停止；否则令，则停止；否则令，则停止；否则令k k= =k k+1+1；若；若；若；若k k> >NGNG( (其中其中其中其中NGNG为最大迭代数为最大迭代数为最大迭代数为最大迭代数) )，则停止；，则停止；，则停止；，则停止；二二. .禁忌搜索禁忌搜索注：注： 表示非正常终止，造成的原因：表示非正常终止，造成的原因：邻域小，邻域小，T T表长。

正常设置为表长正常设置为( (T表长度表长度< <邻域大小邻域大小) )Step 2的作用是设置循环体出口的作用是设置循环体出口22223.3.算法步骤算法步骤Step 3Step 3 若若若若 若若若若 ，令，令，令，令 ，，，，转转转转Step 5Step 5；；；；Step 4Step 4若若若若 ，令，令，令，令 ；；；；二二. .禁忌搜索禁忌搜索注：注：Step 3的作用破禁检查的作用破禁检查注：注：Step 4的作用邻域选优的作用邻域选优23233.3.算法步骤算法步骤Step 5Step 5若若若若 ，令，令，令，令 ，，，， ，，，， ；；；；Step 6Step 6更新更新更新更新T T表，转表，转表，转表，转Step 2 Step 2 ；；；；二二. .禁忌搜索禁忌搜索注：注：Step 5的作用选优并记录历史最好点，更新渴望水平注：注：x存入存入T T表中的第一个位置表中的第一个位置24244.4.TSTS克服局优分析克服局优分析Ø从邻域搜索的方法看从邻域搜索的方法看从邻域搜索的方法看从邻域搜索的方法看移向移向移向移向N N( (x x)\ )\T T中最好的解，而不于当前解比较，中最好的解，而不于当前解比较，中最好的解，而不于当前解比较，中最好的解，而不于当前解比较， 是是是是 N N( (x x)\ )\T T中的最好点，但中的最好点，但中的最好点，但中的最好点，但可能劣于可能劣于可能劣于可能劣于二二. .禁忌搜索禁忌搜索25254.4.TSTS克服局优分析克服局优分析Ø从选优规则看从选优规则看从选优规则看从选优规则看始终保持历史上的最优解，不以当前解为最优始终保持历史上的最优解，不以当前解为最优始终保持历史上的最优解，不以当前解为最优始终保持历史上的最优解，不以当前解为最优Ø从停止规则上看从停止规则上看从停止规则上看从停止规则上看不以最优判据为停止规则，而是指定最大迭代步数不以最优判据为停止规则，而是指定最大迭代步数不以最优判据为停止规则，而是指定最大迭代步数不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。

为停止条件，这样不能保证最优性为停止条件，这样不能保证最优性为停止条件，这样不能保证最优性二二. .禁忌搜索禁忌搜索26261.1.问题提出问题提出由由由由7 7 7 7层不同的绝缘材料构成的一种绝缘体，应如何排层不同的绝缘材料构成的一种绝缘体，应如何排层不同的绝缘材料构成的一种绝缘体，应如何排层不同的绝缘材料构成的一种绝缘体，应如何排列顺序，可获得最好的绝缘性能列顺序，可获得最好的绝缘性能列顺序，可获得最好的绝缘性能列顺序，可获得最好的绝缘性能? ? ? ?三三.TS.TS举例举例27272.2.算法设计算法设计Ø编码方式：顺序编码编码方式：顺序编码编码方式：顺序编码编码方式：顺序编码Ø初始解的产生：随机产生，如初始解的产生：随机产生，如初始解的产生：随机产生，如初始解的产生：随机产生，如2-5-7-3-4-6-12-5-7-3-4-6-1Ø适值函数：极大化目标值适值函数：极大化目标值适值函数：极大化目标值适值函数：极大化目标值Ø邻域移动方式：邻域移动方式：邻域移动方式：邻域移动方式：2-OPT2-OPT，即两两交换，即两两交换，即两两交换，即两两交换Ø其他参数：禁忌对象为邻域移动方式，其他参数：禁忌对象为邻域移动方式，其他参数：禁忌对象为邻域移动方式，其他参数：禁忌对象为邻域移动方式，T T表长度表长度表长度表长度设为设为设为设为3 3，，，，NGNG设为设为设为设为5 5三三.TS.TS举例举例2828①①①①初始表初始表初始表初始表初始编码：初始编码：初始编码：初始编码：2-5-7-3-4-6-12-5-7-3-4-6-1结论：交换结论：交换结论：交换结论：交换4 4和和和和5 5三三.TS.TS举例举例移动移动移动移动5 5，，4 46 67 7，，4 44 43 3，，6 62 22 2，，3 30 04 4，，1 1-1-1……………………T T表表表表1 12 23 32929②②②②迭代迭代迭代迭代1 1编码：编码：编码：编码：2-4-7-3-5-6-12-4-7-3-5-6-1结论：交换结论：交换结论：交换结论：交换1 1和和和和3 3三三.TS.TS举例举例移动移动移动移动3 3，，1 12 22 2，，3 31 13 3，，4 4-1-17 7，，1 1-2-26 6，，1 1-4-4……………………T T表表表表1 14 4，，5 52 23 33030③③③③迭代迭代迭代迭代2 2编码：编码：编码：编码：2-4-7-1-5-6-32-4-7-1-5-6-3结论：因交换结论：因交换结论：因交换结论：因交换1 1和和和和3 3已在禁忌表中，故只能交换已在禁忌表中，故只能交换已在禁忌表中，故只能交换已在禁忌表中，故只能交换2 2和和和和4 4三三.TS.TS举例举例移动移动移动移动1 1，，3 3-2-22 2，，4 4-4-47 7，，6 6-6-64 4，，5 5-7-75 5，，3 3-9-9……………………T T表表表表1 11 1，，3 32 24 4，，5 53 3若选择这项若选择这项若选择这项若选择这项 C C( (x x) )=16=16，渴望水平，渴望水平，渴望水平，渴望水平不能发生作用不能发生作用不能发生作用不能发生作用3131④④④④迭代迭代迭代迭代3 3编码：编码：编码：编码：4-2-7-1-5-6-34-2-7-1-5-6-3结论：因渴望水平发挥作用，交换结论：因渴望水平发挥作用，交换结论：因渴望水平发挥作用，交换结论：因渴望水平发挥作用，交换4 4和和和和5 5三三.TS.TS举例举例移动移动移动移动4 4，，5 56 65 5，，3 32 27 7，，1 10 01 1，，3 3-3-32 2，，6 6-6-6……………………T T表表表表1 12 2，，4 42 21 1，，3 33 34 4，，5 5因因因因C C( (x x)=20)=20> >A A( (s s, ,x x)=18)=18，，，，此时渴望水平此时渴望水平此时渴望水平此时渴望水平发生作用，破禁。

交换发生作用，破禁交换发生作用，破禁交换发生作用，破禁交换4 4和和和和5 53232⑤⑤⑤⑤迭代迭代迭代迭代4 4编码：编码：编码：编码：5-2-7-1-4-6-35-2-7-1-4-6-3结论：交换结论：交换结论：交换结论：交换7 7和和和和1 1三三.TS.TS举例举例移动移动移动移动7 7，，1 10 04 4，，3 3-3-36 6，，3 3-5-55 5，，4 4-6-62 2，，6 6-8-8……………………T T表表表表1 14 4，，5 52 22 2，，4 43 31 1，，3 33333⑥⑥⑥⑥迭代迭代5编码：编码：5-2-1-7-4-6-3 结论：迭代已到结论：迭代已到5次，得到最优解次，得到最优解5-2-7-1-4-6-3和和5-2-1-7-4-6-3三三.TS.TS举例举例T T表表表表1 11 1，，7 72 24 4，，5 53 32 2，，4 434341.1.短期表短期表- -T表表ØT T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用35351.1.短期表短期表- -T表表ØT T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些变化元素变化元素变化元素变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用变化因素变化因素解解的的变变化化解解分分量量的的变变化化函函数数值值的的变变化化36361.1.短期表短期表- -T表表ØT T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象禁忌对象禁忌对象禁忌对象：：：：T T表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些变化元素变化元素变化元素变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用禁忌对象禁忌对象解解移移动动函函数数值值3737练练 习习初始解：(ABCDE)，邻域移动方式为2-OPT，T表长度为4，NG=5，分别以解、移动和函数值为禁忌对象进行求解，并分析各自的特点。

38381.1.短期表短期表- -T表表ØT T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用受禁范围：解的变化受禁范围：解的变化 邻域移动邻域移动 函数值函数值 计算时间：函数值计算时间：函数值 邻域移动邻域移动 解的变化解的变化摆脱局优：函数值摆脱局优：函数值 邻域移动邻域移动 解的变化解的变化39391.1.短期表短期表- -T表表ØT T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值①①设为常数，易于实现设为常数，易于实现设为常数，易于实现设为常数，易于实现②②设为变化的数，在设为变化的数，在设为变化的数，在设为变化的数，在 之间变化之间变化之间变化之间变化四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用禁忌长度过短，一旦陷入局部最优点，出现循禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；环无法跳出；禁忌长度过长，造成计算时间较大，也可能造禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。

成计算无法继续下去4040练练 习习初始解：(ABCDE)，邻域移动方式为2-OPT，以移动为禁忌对象，NG=5，T表长度分别设为2,4和6进行求解，并分析各自的特点41412.2.中期表中期表- -频数频数表表Ø频数表的作用：频数表的作用：频数表的作用：频数表的作用：频数表是用来记忆不同方向的频数表是用来记忆不同方向的频数表是用来记忆不同方向的频数表是用来记忆不同方向的移动次数，从而加以惩罚（比如移动次数，从而加以惩罚（比如移动次数，从而加以惩罚（比如移动次数，从而加以惩罚（比如2-OPT2-OPT，记录每，记录每，记录每，记录每对交换的发生次数）从而提高搜索方向的多样对交换的发生次数）从而提高搜索方向的多样对交换的发生次数）从而提高搜索方向的多样对交换的发生次数）从而提高搜索方向的多样性性性性 在邻域选优公式中，令在邻域选优公式中，令在邻域选优公式中，令在邻域选优公式中，令其中，其中，其中，其中，E E( (s s( (x x)) ))表示移动表示移动表示移动表示移动s s( (x x) )的出现频数，的出现频数，的出现频数，的出现频数，α α为惩罚因为惩罚因为惩罚因为惩罚因子子子子四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用注：惩罚因子注：惩罚因子α的取值一般应远小于目标值（的取值一般应远小于目标值（1%1%目标值目标值或或1‰1‰目标值），目标值），α越大分散性越好，广域搜索能力强，越大分散性越好，广域搜索能力强，但会损坏邻域搜索。

但会损坏邻域搜索42422.2.中期表中期表- -频数频数表表Ø频数表的记录方法频数表的记录方法频数表的记录方法频数表的记录方法①①建立建立建立建立n n× ×n n的数组，对上半部分每做一步搜索将的数组，对上半部分每做一步搜索将的数组，对上半部分每做一步搜索将的数组，对上半部分每做一步搜索将所有所有所有所有>0>0的数减的数减的数减的数减1 1；；；；②②对数组上半部分，给新发生的移动所对应的对数组上半部分，给新发生的移动所对应的对数组上半部分，给新发生的移动所对应的对数组上半部分，给新发生的移动所对应的数组元加上数组元加上数组元加上数组元加上Tabu-SizeTabu-Size；；；；③③下半部分用来记频数，每次下半部分用来记频数，每次下半部分用来记频数，每次下半部分用来记频数，每次( (i i, ,j j) ) ( (i i<

共同使用，方便操作又节了时间共同使用，方便操作又节了时间共同使用，方便操作又节了时间4343频数表：频数表：频数表：频数表：Tabu-Size=7Tabu-Size=7四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用T T表表表表1 13 3，，4 42 21 1，，7 73 35 5，，6 64 43 3，，7 75 52 2，，6 66 64 4，，5 57 71 1，，3 3\ \1 12 23 34 45 56 67 71 1\ \1 16 62 2\ \3 33 31 1\ \7 74 44 41 1\ \2 25 51 1\ \5 56 61 11 1\ \7 71 11 1\ \4444频数表：频数表：频数表：频数表：Tabu-Size=7Tabu-Size=7四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用T T表表表表1 11 1，，3 32 23 3，，4 43 31 1，，7 74 45 5，，6 65 53 3，，7 76 62 2，，6 67 74 4，，5 5\ \1 12 23 34 45 56 67 71 1\ \7 75 52 2\ \2 23 32 2\ \6 63 34 41 1\ \1 15 51 1\ \4 46 61 11 1\ \7 71 11 1\ \45452.2.长期表长期表- - 多阶段多阶段TSØ长期表的作用：长期表的作用：长期表的作用：长期表的作用：长期表用来记录每个阶段的初长期表用来记录每个阶段的初长期表用来记录每个阶段的初长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能始解，在下一阶段产生初始解时，使之尽可能始解，在下一阶段产生初始解时，使之尽可能始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离与已有的初始解有较大的距离与已有的初始解有较大的距离与已有的初始解有较大的距离四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用46462.2.长期表长期表- - 多阶段多阶段TSØ函数表达式函数表达式函数表达式函数表达式四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用47471.1.TSTS的记忆功能的记忆功能————短、中、长期表要灵活使短、中、长期表要灵活使用用2.2.TSTS相对于相对于GAGA是更快的算法，局域搜索能力强，是更快的算法，局域搜索能力强，但全局搜索能力较弱；但全局搜索能力较弱；3.3.改善改善TSTS的全局搜索能力，提高的全局搜索能力，提高TSTS的分散性的的分散性的方法方法Ø用长期表用长期表用长期表用长期表Ø加大加大加大加大Tabu SizeTabu SizeTabu SizeTabu SizeØ加大对频数的惩罚，即增大加大对频数的惩罚，即增大加大对频数的惩罚，即增大加大对频数的惩罚，即增大αααα4.4.TSTS仍是一种启发式，不能保证最优性仍是一种启发式，不能保证最优性5.5.TSTS的理论工作较少的理论工作较少五五. .学习学习TSTS的几点体会的几点体会4848作作 业业30城市TSP问题（d*=423.741 by D B Fogel） 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 504949。