第三章禁忌搜索

第三章禁忌搜索内容摘要：

TS的两大核心移动规则 24 2. 构成要素  停止准则 ① 设定最大迭代次数 ② 得到满意解 ③ 设定某个对象的最大禁忌频率 二 .禁忌搜索 25 3. 算法流程 Step 1 选一个初始点 x( )，令 ， ，渴望水平 ，迭代指标 k=0； Step 2 若 ，则停止；否则令 k=k+1；若kNG(其中 NG为最大迭代次数 )，则停止； 二 .禁忌搜索 xX xx  T *( , ) ( )A s x C x  \N x T 注： 表示非正常终止，造成的原因：邻域小， T表长。 正常设置为 T表长度 邻域大小。 Step 2的作用是设置循环体出口。   \N x T 26 3. 算法流程 Step 3 若 且 ，令 ，转 Step 5； Step 4 若 ，令 ； 二 .禁忌搜索           ,LC s x O p t C s x s x N x   ( , )LC s x A s x ()Lx s x注： Step 3的作用破禁检查           ,\KC s x O p t C s x s x N x T()Kx s x注： Step 4的作用邻域选优 27 3. 算法流程 Step 5 若 ，令 ， ， ； Step 6 更新 T表，转 Step 2 ； 二 .禁忌搜索 注： Step 5的作用更新历史最好解及渴望水平    C x C x  xx     C x C x    ,A s x C x 注： x存入 T表中的第一个位置 28 4. TS克服局优分析  从邻域搜索的方法看 移向 N(x)\T中最好的解，而不与当前解比较， 是 N(x)\T中的最好点，但 可能劣于 二 .禁忌搜索         ,\Ks x O pt s x s x N x T Ksx   KC s x *Cx29 4. TS克服局优分析  从选优规则看 始终保持历史最优解，不以当前解为最优  从停止规则上看 不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。 二 .禁忌搜索 30 1. 问题提出 由 7层不同的绝缘材料构成的一种绝缘体，应如何排 列顺序，可获得最好的绝缘性能 ? 三 .算法举例 31 2. 算法设计  编码方式：顺序编码  初始解的产生：随机产生，如 2573461  适值函数：极大化目标值  邻域移动方式： 2opt，即两两交换  其他参数：禁忌对象为邻域移动方式， T表长度设为 3， NG设为 5 三 .算法举例 32 ① 初始表 初始编码： 2573461 结论：交换 4和 5 三 .算法举例 移动 5， 4 6 7， 4 4 3， 6 2 2， 3 0 4， 1 1 …… ……   10Cx TT表 1 2 3  xS  Cx *xx *( , ) ( ) 10A s x C x33 ② 迭代。