数学建模社区-数学中国
标题: 组合优化算法-现代优化算法(三）：禁忌搜索算法 [打印本页]
作者: 浅夏110 时间: 2020-5-22 15:25
标题: 组合优化算法-现代优化算法(三）：禁忌搜索算法
1 禁忌搜索算法的相关概念4 |! A( N% G+ o
禁忌搜索算法是组合优化算法的一种，是局部搜索算法的扩展。禁忌搜索算法是人 工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所 谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点。 禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌 对象、评价函数、特赦规则、记忆频率信息等概念。
0 M1 w9 M& `- r p% V( r
) w4 C9 V# r6 c5 Q; Z（1）邻域
, J3 t* t" F q3 {, E9 H- N在组合优化中，距离的概念通常不再适用，但是在一点附近搜索另一个下降的点仍 然是组合优化数值求解的基本思想。因此，需要重新定义邻域的概念。1 P2 X- a# L& k1 o
# |# J0 z# g# p! V. Z
# p1 p) j. M, v7 z0 ~/ ~# k1 w( t/ G
N1 c1 V M! P2 Y9 Q" H' H3 W3 y6 G# v* w" W. N
（2）侯选集合5 c' P$ y7 H6 Y4 E& }
侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价 值最佳的邻居入选。
0 u$ b! k; r5 R Y
7 y7 F$ H" M9 u, @7 E9 I' a3 ?3 y7 X（3）禁忌对象和禁忌长度% d4 }3 i% O! `0 @. w
禁忌表中的两个主要指标是禁忌对象和禁忌长度。禁忌算法中，由于我们要避免 一些操作的重复进行，就要将一些元素放到禁忌表中以禁止对这些元素进行操作，这些元素就是我们指的禁忌对象。禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 x 一个数（禁忌长度） t ，要求对象 x 在 t 步迭代内被禁，在禁忌表中采用 tabu(x) = t 记忆，每迭代一步，该项指标做运算 tabu(x) = t −1，直到 tabu(x) = 0时 解禁。于是，我们可将所有元素分成两类，被禁元素和自由元素。禁忌长度t 的选取可以有多种方法，例如t = 常数，或t = [
]，其中 n 为邻域中邻居的个数；这种规则容易在算法中实现。
2 k. h* s. B7 o+ o' t
7 r$ C: @6 y& ~$ `/ L（4）评价函数
* e/ W- H9 R/ Z+ H/ O- d评价函数是侯选集合元素选取的一个评价公式，侯选集合的元素通过评价函数值 来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标， 但有时为了方便或易于计算，会采用其他函数来取代目标函数。# @+ l8 H0 `3 ?; w2 J# ?
' ?3 s9 k' F) V( ^( R
（5）特赦规则( v6 r# C+ f# W, O; p
在禁忌搜索算法的迭代过程中，会出现侯选集中的全部对象都被禁忌，或有一对 象被禁，但若解禁则其目标值将有非常大的下降情况。在这样的情况下，为了达到全局 最优，我们会让一些禁忌对象重新可选。这种方法称为特赦，相应的规则称为特赦规则。( B9 Q) S' g8 `. j8 |' M
- ?6 ~7 V1 R I9 |$ j; a. j
（6）记忆频率信息
0 U- }6 Y# ^ v6 O% s* a在计算的过程中，记忆一些信息对解决问题是有利的。如一个最好的目标值出现 的频率很高，这使我们有理由推测：现有参数的算法可能无法再得到更好的解。根据解 决问题的需要，我们可以记忆解集合、被禁对象组、目标值集合等的出现频率。 频率信息有助于进一步加强禁忌搜索的效率。我们可以根据频率信息动态控制禁 忌的长度。一个最佳的目标值出现的频率很高，有理由终止计算而将此值认为是最优值。2 v- S/ @% L$ r4 o0 M& {5 V
* _% Z$ e8 F/ s# F0 e# }2 模型及求解; q1 f. G% K& [) f0 k
我们用禁忌搜索算法研究如下的两个问题：
) Q/ R8 Q2 Y/ }- c! V. h; s4 z3 o+ u/ O" |2 l
（1）研究 1.2 中同样的问题。
8 F/ ~& p6 ~( q- H/ G# Q9 z; {
+ f# ~. \! ~' c* g
1 @) q8 H/ H2 z, n( I
' o g- @# K# h: s% B1 h
: Y* K* g( h3 c
0 E0 f1 p- A: G( ` _6 k. L+ o/ X
我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目 标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。7 B' B" ]2 a8 }) m8 S
- V) Z# H7 P7 }2 i# n4 ~1 J0 j
& J. e: D1 T& t" k5 X8 J0 V" R5 ?% ~, O
（2）我方有三个基地，经度、纬度分别为（70,40），（72,45），（68,48）。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标， 怎样划分任务，才能使时间最短，且任务比较均衡。
3 o" l5 f3 W- b1 f
" [8 I' M2 T" O2.1 问题（1）的求解
4 N" [+ \) K2 @! e3 R求解的禁忌搜索算法描述如下： （1）解空间9 m( M7 d5 Q% b; B" B6 w( I
( C, P' D6 o8 S6 w: ?0 `; A
/ z( y6 v2 m9 S' V; B2 _& y0 z
D: q+ j; p" \. c5 I
（2）目标函数
目标函数为侦察所有目标的路径长度。我们要求
: V" y2 n* r/ T# a6 r4 _
# w2 \0 @2 a2 d1 [9 K5 `
（3）候选集合 v( ^6 O5 D8 L6 h, G: ~' y
0 z- e8 j4 b$ o' U0 c
- z7 Q# Y/ P T: E9 ?
' K/ z* | _- j5 y2 J4 T( K W
如果要考虑当前解的全部二邻域（或三邻域）的邻居，将面临着太大的工作量。 因此我们用随机选取的方法每次选取50个邻居组成的集合作为侯选集合。而将省下的 时间作更多次搜索，这样做同样可以保证较高的精确度，同时可以大大提高算法的效率。
（4）禁忌长度及禁忌对象
) r' `9 X( }% z1 r# X$ J' L4 }
3 w s% }# Y2 }9 c: e( t* V7 J5 p0 F, `" T/ u
我们把禁忌表设计成一个循环队列，初始化禁忌表 H = Φ 。从候选集合C 中选出 一个向量 x ，如果 x ∉ H ，并且 H 不满，则把向量 x 添加到禁忌表中；如果 H 已满， 则最早进入禁忌表的向量出列，向量 x 进入到出列的位置。
. ~' L& e0 h, S0 v
. `! i* c/ ~/ o+ V: b' [% {0 {. J（5）评价函数
3 s$ V7 |" V8 q* H- `
/ G% X. |0 c M2 R1 P可以用目标函数作为评价函数，但是这样每选取一个新的路径都得去计算总时间， 计算量比较大。对于上述二邻域中的邻居作为侯选集合，每一个新路径中只有两条边发 生了变化，因此将目标函数的差值作为评价函数可以极大地提高算法的效率。评价函数 取为
9 g' Y# E8 K/ P% [/ o+ h
! b3 |9 Y3 J5 D0 p' L
J1 H, M% k) r- F0 O
" `0 Q- t' c, q4 }* C4 x1 e8 [& V禁忌搜索算法的流程禁忌搜索算法的流程如下：
# g% J8 c6 p; v* J6 U% \+ |8 {2 Q0 Z
# }, g: h/ a* p! t0 l
' l% t6 `: X, c# b3 R, A
! R# x& e# Q. m4 G5 z9 @; X
6 k( s0 a: ^* O9 I7 ~$ L V* W' K利用 Matlab 程序求得，我们的巡航时间大约在 41 小时左右，其中的一个巡航路径 如下图所示
/ Q, S3 r5 }. t5 j
n6 |4 @) S2 T8 |; q) C+ ~8 s) u
, J3 x/ V. E5 U1 P# L: \' l/ B7 m2 H2 E+ i! F
2.2 问题（2）的求解对于这个问题，我们的基本想法是，先根据敌方基地的分布特点将敌方的基地大体 划分在三个区域之内，并使三架侦察机分别对这三个区域的敌军基地进行侦察，求取各 自的最短时间。然后对任务不均衡区域之中的点做适当调整。 我们解决问题的步骤如下：
+ K& W* E- E' V2 K' T' c, D
8 X' G! ?) j5 [5 w! E y( \0 r
/ S. U3 N O0 o# C% n$ A. w
6 j2 S! h- c$ N/ v% K. p1 l2 s9 d————————————————& C. p1 G) ~0 U8 o$ h7 E/ c
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 M; }- C' D" n' F, w$ e s原文链接：https://blog.csdn.net/qq_29831163/article/details/896707680 Z/ }) ]* @. @$ `0 q8 A- O
' f( q+ P, b/ X( [+ z; U/ G. C, H2 I# o% J$ {" [
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |