——禁忌搜索课件.ppt

智能优化方法AI-Based Optimization Methods
By Professor Dingwei Wang
Northeastern University
China 2004
第1页，共46页。
1
始终保持历史上的最优解，不以当前解为最优
从停止规则上看
不以最优判据为停止规则，而是指定最大迭代
步数为停止条件，这样不能保证最优性。
（2）
第18页，共46页。
18
问题的提出
由7层不同的绝缘材料构成的一种绝缘体，应如
何排列顺序，可获得最好的绝缘性能。
（1）
第19页，共46页。
19
编码方式：顺序编码
初始编码：2-5-7-3-4-6-1
目标值：极大化目标值。
邻域定义：两两交换是一个邻域移动
邻域大小：
Tabu Size：3 NG：5
（2）
第20页，共46页。
20
初始表
初始编码：2-5-7-3-4-6-1
结论：交换4和5
（3）
移动
5，4
6
7，4
4
3，6
2
2，3
0
4，1
-1
……
……
T表
1
2
3
第21页，共46页。
21
迭代1编码：2-4-7-3-5-6-1
= =16
结论：交换1和3
（4）
移动
3，1
2
2，3
1
3，4
-1
7，1
-2
6，1
-4
……
……
T表
1
4，5
2
3
第22页，共46页。
22
迭代2编码：2-4-7-1-5-6-3
= =18
结论：因交换1和3已在禁忌表中，故只能交换2和4
（5）
移动
1，3
-2
2，4
-4
7，6
-6
4，5
-7
5，3
-9
……
……
T表
1
1，3
2
4，5
3
若选择这项 =16，渴
望水平不能发生作用
第23页，共46页。
23
迭代3编码：4-2-7-1-5-6-3
=14， =18
结论：因渴望水平发挥作用，交换在破禁表中的4,5
（6）
移动
4，5
6
5，3
2
7，1
0
1，3
-3
2，6
-6
……
……
T表
1
2，4
2
1，3
3
4，5
因 =20大于渴望水平 =18
此时渴望水平发生作用，破禁。交换
4和5。
第24页，共46页。
24
迭代4编码：5-2-7-1-4-6-3
= =20
结论：交换7和1
（7）
移动
7，1
0
4，3
-3
6，3
-5
5，4
-6
2，6
-8
……
……
T表
1
4，5
2
2，4
3
1，3
第25页，共46页。
25
迭代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
（8）
第26页，共46页。
26
引入中长期表的目的
改善TS的广域搜索能力，TS的局域搜索能力很
好，邻域选优快，但广域搜索能力较差。搜索
能力是TS的关键，采用中长期表可改善TS的广
域搜索能力。
、长期表的使用（1）
第27页，共46页。
27
中期表——频数表
频数表的作用
频数表是用来记忆不同方向的移动次数，从而
加以惩罚(比如两两交换，记录每对交换的发生
次数)以提高搜索方向的多样性。
、长期表的使用（2）
第28页，共46页。
28
在邻域选优公式中，令
注：惩罚因子 的取值一般应远小于目标值
(1%目标值或1‰目标值)， 越大分散性越
好，广域搜索能力强，但会损坏邻域搜索。
、长期表的使用（3）
第29页，共46页。
29
频数表的记录方法
建立n×n的数组，对上半部分每做一步搜索将所有>0的数减1；
对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size;
T表的下半部分，用来记频数，每次(i,j)交换(i<j)，对应的((j,i)+1)来记忆频