8 J. E; g( @" z3 Z ' g/ S% V& F# v(2)侯选集合 * k9 {5 H7 C; a4 ]- Q, i" h! Q2 k侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价 值最佳的邻居入选。1 Z: `9 ?- q" c# v. `5 ]) a
8 u4 J* p/ I; P(3)禁忌对象和禁忌长度, J0 q/ J, b1 S' r
禁忌表中的两个主要指标是禁忌对象和禁忌长度。禁忌算法中,由于我们要避免 一些操作的重复进行,就要将一些元素放到禁忌表中以禁止对这些元素进行操作,这些元素就是我们指的禁忌对象。禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 x 一个数(禁忌长度) t ,要求对象 x 在 t 步迭代内被禁,在禁忌表中采用 tabu(x) = t 记忆,每迭代一步,该项指标做运算 tabu(x) = t −1,直到 tabu(x) = 0时 解禁。于是,我们可将所有元素分成两类,被禁元素和自由元素。禁忌长度t 的选取可以有多种方法,例如t = 常数,或t = [ ],其中 n 为邻域中邻居的个数;这种规则容易在算法中实现。7 {- V2 m- H/ A) Z# e/ H' L# t
; i5 X7 C2 q- p. @! } 4 N8 J, J0 ?/ C! b: J% l. y* ^ : P2 X+ u/ J; j/ _, p1 k' y0 H我们把禁忌表设计成一个循环队列,初始化禁忌表 H = Φ 。从候选集合C 中选出 一个向量 x ,如果 x ∉ H ,并且 H 不满,则把向量 x 添加到禁忌表中;如果 H 已满, 则最早进入禁忌表的向量出列,向量 x 进入到出列的位置。: G0 h U% d- K* X0 k, A! E$ V6 D
7 o, j& P/ N1 |4 Q s(5)评价函数 . b) k" a. T& w$ {3 _5 s O6 m # C1 Y, H. X* G! ?( X' W可以用目标函数作为评价函数,但是这样每选取一个新的路径都得去计算总时间, 计算量比较大。对于上述二邻域中的邻居作为侯选集合,每一个新路径中只有两条边发 生了变化,因此将目标函数的差值作为评价函数可以极大地提高算法的效率。评价函数 取为 1 x' Z l5 @" p: @" v% V+ F' {2 Q0 Q" ~. v+ f K! `( U% }$ ~3 ~$ B 2 h4 X6 @8 U* g
9 A/ [4 |5 p! d9 @( Q7 V8 Y/ b4 n) o 禁忌搜索算法的流程
禁忌搜索算法的流程如下:
' _: B3 x6 }- P: R' Z2 H# e. G0 o6 y- O' H$ T$ R- k* X' ]
- G" n# g9 {5 r2 d1 I; a4 G0 A, @# d 8 Q4 N( C( ]) w