文档介绍：问题提出
由7层不同的绝缘材料构成的一种绝缘体，应如何排
列顺序，可获得最好的绝缘性能?
31
算法设计
编码方式：顺序编码
初始解的产生：随机产生，如2-5-7-3-4-6-1
适值函数代已到5次，得到最优解
T表
1
1，7
2
4，5
3
2，4
38
作 业
小规模TSP问题
算法设置如下：
初始解为1-2-3-4-5；
评价函数为极小化巡回路程；
邻域移动方式为2-opt;
禁忌对象为邻域移动方式；
T表长度设为3，NG设为5。
要求：给出完整的TS迭代过程。
39
短期表-T表
T表的主要指标：
禁忌对象：T表中被禁忌的那些变化元素
禁忌长度：T表的长度，禁忌对象的最大值
、中、长期表的使用
40
短期表-T表
T表的主要指标：
禁忌对象：T表中被禁忌的那些变化元素
禁忌长度：T表的长度，禁忌对象的最大值
、中、长期表的使用
变化因素
解的变化
解分量的变化
函数值的变化
41
短期表-T表
T表的主要指标：
禁忌对象：T表中被禁忌的那些变化元素
禁忌长度：T表的长度，禁忌对象的最大值
、中、长期表的使用
禁忌对象
解
移动
函数值
42
短期表-T表
T表的主要指标：
禁忌对象：T表中被禁忌的那些变化元素
禁忌长度：T表的长度，禁忌对象的最大值
、中、长期表的使用
受禁范围：解的变化 邻域移动 函数值
计算时间：函数值 邻域移动 解的变化
摆脱局优：函数值 邻域移动 解的变化
43
短期表-T表
T表的主要指标：
禁忌对象：T表中被禁忌的那些变化元素
禁忌长度：T表的长度，禁忌对象的最大值
设为常数，易于实现
设为变化的数，在 之间变化
、中、长期表的使用
禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；
禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。
44
中期表-频数表
频数表的作用：频数表是用来记忆不同方向的移动次数，从而加以惩罚（比如2-Opt，记录每对交换的发生次数），从而提高搜索方向的多样性
在邻域选优公式中，令
其中，E(s(x))表示移动s(x)的出现频数，α为惩罚因子
、中、长期表的使用
注：惩罚因子α的取值一般应远小于目标值（1%目标值或1‰目标值），α越大分散性越好，广域搜索能力强，但会损坏邻域搜索。
45
中期表-频数表
频数表的记录方法
建立n×n的数组，对上半部分每做一步搜索将所有>0的数减1；
对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size；
下半部分用来记频数，每次(i,j) (i<j)交换，对应的((j,i)+1)来记忆频数。
、中、长期表的使用
频数表的优点：同一数组作为T表和频数表共同使用，方便操作又节省时间。
46
频数表：Tabu-Size=7
、中、长期表的使用
T表
1
3，4
2
1，7
3
5，6
4
3，7
5
2，6
6
4，5
7
1，3
\
1
2
3
4
5
6
7
1
\
1
6
2
\
3
3
1
\
7
4
4
1
\
2
5
1
\
5
6
1
1
\
7
1
1
\
47
频数表：Tabu-Size=7
、中、长期表的使用
T表
1
1，3
2
3，4
3
1，7
4
5，6
5
3，7
6
2，6
7
4，5
\
1
2
3
4
5
6
7
1
\
7
5
2
\
2
3
2
\
6
3
4
1
\
1
5
1
\
4
6
1
1
\
7
1
1
\
48
长期表- 多阶段TS
长期表的作用：长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离
、中、长期表的使用
49
长期表- 多阶段TS
公式
其中B是已选初始解的集合，这种方法的目的是使
初始解充分分散到可行域的不同部分。
、中、长期表的使用
50
TS的记忆功能—短、中、长期表要灵活使用
TS局域搜索能力强，但全局搜索能力较弱；
改善TS的