第3章 禁忌搜索.ppt

1 1第三章第三章禁忌搜索禁忌搜索2 2第三章第三章 禁忌搜索禁忌搜索一一.导言导言二二.禁忌搜索禁忌搜索三三.TS.TS举例举例四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用五五.学习学习TSTS的几点体会的几点体会3 31.1.问题描述问题描述一一.导言导言目标函数目标函数约束条件约束条件定义域定义域注：注：X为为离散点的集合，离散点的集合，TS排斥实优化排斥实优化4 42.2.局域搜索局域搜索邻域的概念邻域的概念邻域的概念邻域的概念函数优化问题：函数优化问题：函数优化问题：函数优化问题：邻域邻域邻域邻域(N(x)通常定义为在给定距离空间内，以一点通常定义为在给定距离空间内，以一点通常定义为在给定距离空间内，以一点通常定义为在给定距离空间内，以一点(x)为中心的一个球体为中心的一个球体为中心的一个球体为中心的一个球体组合优化问题：组合优化问题：组合优化问题：组合优化问题：且且且且 ，称为一个，称为一个，称为一个，称为一个邻域映射邻域映射邻域映射邻域映射，其中，其中，其中，其中 表示表示表示表示X所有子集组成的集合。所有子集组成的集合。所有子集组成的集合。所有子集组成的集合。N(x)称为称为称为称为x的的的的邻域邻域邻域邻域，称为称为称为称为x的一个的一个的一个的一个邻居邻居邻居邻居。一一.导言导言5 52.2.局域搜索局域搜索邻域的概念邻域的概念邻域的概念邻域的概念 例：例：例：例：TSPTSP问题解的一种表示方法为问题解的一种表示方法为问题解的一种表示方法为问题解的一种表示方法为D=x=(i1,i2,in)|i1,i2,in是是是是1,2,n的排列的排列的排列的排列，定义它的邻域映射为，定义它的邻域映射为，定义它的邻域映射为，定义它的邻域映射为 2-opt2-opt，即，即，即，即x 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)一一.导言导言6 62.2.局域搜索局域搜索邻域的概念邻域的概念邻域的概念邻域的概念 例：例：例：例：解的邻域映射可由解的邻域映射可由解的邻域映射可由解的邻域映射可由2 2-opt-opt，推广到，推广到，推广到，推广到k k-opt-opt，即对，即对，即对，即对k个元个元个元个元素按一定规则互换。素按一定规则互换。素按一定规则互换。素按一定规则互换。一一.导言导言邻域的构造依赖于解的表示，邻域的结构邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。在智能优化算法中起重要的作用。7 7练练 习习定义邻域移动为：位值加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 是是否否否否是是是是否否8 8练练 习习定义邻域移动为：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 是是否否否否是是是是否否9 92.2.局域搜索局域搜索局域搜索算法过程局域搜索算法过程局域搜索算法过程局域搜索算法过程Step 1Step 1选定一个初始可行解选定一个初始可行解选定一个初始可行解选定一个初始可行解x0，记录当前最优解，记录当前最优解，记录当前最优解，记录当前最优解xbest:=x0,T=N(xbest)；Step 2Step 2当当当当T T x xbestbest=时，或满足其他停止运算准则时，时，或满足其他停止运算准则时，时，或满足其他停止运算准则时，时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从输出计算结果，停止运算；否则，从输出计算结果，停止运算；否则，从输出计算结果，停止运算；否则，从T中选一中选一中选一中选一集合集合集合集合S，得到，得到，得到，得到S中的最好解中的最好解中的最好解中的最好解xnow；若；若；若；若 f(xnow)NG(其中其中其中其中NG为最大迭代数为最大迭代数为最大迭代数为最大迭代数)，则停止；，则停止；，则停止；，则停止；二二.禁忌搜索禁忌搜索注：注：表示非正常终止，造成的原因：表示非正常终止，造成的原因：邻域小，邻域小，T T表长。正常设置为表长。正常设置为(T表长度表长度 A A(s s,x x)=18)=18，此时渴望水平此时渴望水平此时渴望水平此时渴望水平发生作用，破禁。交换发生作用，破禁。交换发生作用，破禁。交换发生作用，破禁。交换4 4和和和和5 5。3333迭代迭代迭代迭代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-8T T表表表表1 14 4，5 52 22 2，4 43 31 1，3 33434迭代迭代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 435351.1.短期表短期表-T表表T T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用36361.1.短期表短期表-T表表T T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些变化元素变化元素变化元素变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用变化因素变化因素解解的的变变化化解解分分量量的的变变化化函函数数值值的的变变化化37371.1.短期表短期表-T表表T T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象禁忌对象禁忌对象禁忌对象：T T表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些表中被禁忌的那些变化元素变化元素变化元素变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用禁忌对象禁忌对象解解移移动动函函数数值值3838练练 习习初始解：(ABCDE)，邻域移动方式为2-OPT，T表长度为4，NG=5，分别以解、移动和函数值为禁忌对象进行求解，并分析各自的特点。39391.1.短期表短期表-T表表T T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用受禁范围：解的变化受禁范围：解的变化 邻域移动邻域移动 函数值函数值 计算时间：函数值计算时间：函数值 邻域移动邻域移动 解的变化解的变化摆脱局优：函数值摆脱局优：函数值 邻域移动邻域移动 解的变化解的变化40401.1.短期表短期表-T表表T T表的主要指标：表的主要指标：表的主要指标：表的主要指标：禁忌对象：禁忌对象：禁忌对象：禁忌对象：T T表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素表中被禁忌的那些变化元素禁忌长度：禁忌长度：禁忌长度：禁忌长度：T T表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值表的长度，禁忌对象的最大值设为常数，易于实现设为常数，易于实现设为常数，易于实现设为常数，易于实现设为变化的数，在设为变化的数，在设为变化的数，在设为变化的数，在 之间变化之间变化之间变化之间变化四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用禁忌长度过短，一旦陷入局部最优点，出现循禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；环无法跳出；禁忌长度过长，造成计算时间较大，也可能造禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。成计算无法继续下去。4141练练 习习初始解：(ABCDE)，邻域移动方式为2-OPT，以移动为禁忌对象，NG=5，T表长度分别设为2,4和6进行求解，并分析各自的特点。42422.2.中期表中期表-频数频数表表频数表的作用：频数表的作用：频数表的作用：频数表的作用：频数表是用来记忆不同方向的频数表是用来记忆不同方向的频数表是用来记忆不同方向的频数表是用来记忆不同方向的移动次数，从而加以惩罚（比如移动次数，从而加以惩罚（比如移动次数，从而加以惩罚（比如移动次数，从而加以惩罚（比如2-OPT2-OPT，记录每，记录每，记录每，记录每对交换的发生次数）从而提高搜索方向的多样对交换的发生次数）从而提高搜索方向的多样对交换的发生次数）从而提高搜索方向的多样对交换的发生次数）从而提高搜索方向的多样性性性性 在邻域选优公式中，令在邻域选优公式中，令在邻域选优公式中，令在邻域选优公式中，令其中，其中，其中，其中，E(s(x)表示移动表示移动表示移动表示移动s(x)的出现频数，的出现频数，的出现频数，的出现频数，为惩罚因子为惩罚因子为惩罚因子为惩罚因子四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用注：惩罚因子注：惩罚因子的取值一般应远小于目标值（的取值一般应远小于目标值（1%1%目标值目标值或或11目标值），目标值），越大分散性越好，广域搜索能力强，越大分散性越好，广域搜索能力强，但会损坏邻域搜索。但会损坏邻域搜索。43432.2.中期表中期表-频数频数表表频数表的记录方法频数表的记录方法频数表的记录方法频数表的记录方法建立建立建立建立nn的数组，对上半部分每做一步搜索将的数组，对上半部分每做一步搜索将的数组，对上半部分每做一步搜索将的数组，对上半部分每做一步搜索将所有所有所有所有00的数减的数减的数减的数减1 1；对数组上半部分，给新发生的移动所对应的对数组上半部分，给新发生的移动所对应的对数组上半部分，给新发生的移动所对应的对数组上半部分，给新发生的移动所对应的数组元加上数组元加上数组元加上数组元加上Tabu-SizeTabu-Size；下半部分用来记频数，每次下半部分用来记频数，每次下半部分用来记频数，每次下半部分用来记频数，每次(i,j)(ij)交换，对交换，对交换，对交换，对应的应的应的应的(j,i)+1)来记忆频数来记忆频数来记忆频数来记忆频数四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用频数表的优点：同一数组作为频数表的优点：同一数组作为频数表的优点：同一数组作为频数表的优点：同一数组作为T T T T表和频数表表和频数表表和频数表表和频数表共同使用，方便操作又共同使用，方便操作又共同使用，方便操作又共同使用，方便操作又节了节了节了节了时间。时间。时间。时间。4444频数表：频数表：频数表：频数表：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 4545频数表：频数表：频数表：频数表：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 46462.2.长期表长期表-多阶段多阶段TS长期表的作用：长期表的作用：长期表的作用：长期表的作用：长期表用来记录每个阶段的初长期表用来记录每个阶段的初长期表用来记录每个阶段的初长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能始解，在下一阶段产生初始解时，使之尽可能始解，在下一阶段产生初始解时，使之尽可能始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离与已有的初始解有较大的距离与已有的初始解有较大的距离与已有的初始解有较大的距离四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用47472.2.长期表长期表-多阶段多阶段TS函数表达式函数表达式函数表达式函数表达式四四.TS.TS中短、中、长期表的使用中短、中、长期表的使用48481.1.TSTS的记忆功能的记忆功能短、中、长期表要灵活使短、中、长期表要灵活使用用2.2.TSTS相对于相对于GAGA是更快的算法，局域搜索能力强，是更快的算法，局域搜索能力强，但全局搜索能力较弱；但全局搜索能力较弱；3.3.改善改善TSTS的全局搜索能力，提高的全局搜索能力，提高TSTS的分散性的的分散性的方法方法用长期表用长期表用长期表用长期表加大加大加大加大Tabu SizeTabu SizeTabu SizeTabu Size加大对频数的惩罚，即增大加大对频数的惩罚，即增大加大对频数的惩罚，即增大加大对频数的惩罚，即增大4.4.TSTS仍是一种启发式，不能保证最优性仍是一种启发式，不能保证最优性5.5.TSTS的理论工作较少的理论工作较少五五.学习学习TSTS的几点体会的几点体会4949作作 业业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 50