9 e# c+ ?3 g! B1 M) m9 v " S6 G: K X, U% }, R( b(2)侯选集合 . i3 l8 T2 Z h1 }6 \0 C& U侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价 值最佳的邻居入选。8 u/ ?% H! ?$ S# q
9 Y& r8 C S: L; z8 o, z+ R
(3)禁忌对象和禁忌长度5 g& v) b$ c$ k, w
禁忌表中的两个主要指标是禁忌对象和禁忌长度。禁忌算法中,由于我们要避免 一些操作的重复进行,就要将一些元素放到禁忌表中以禁止对这些元素进行操作,这些元素就是我们指的禁忌对象。禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 x 一个数(禁忌长度) t ,要求对象 x 在 t 步迭代内被禁,在禁忌表中采用 tabu(x) = t 记忆,每迭代一步,该项指标做运算 tabu(x) = t −1,直到 tabu(x) = 0时 解禁。于是,我们可将所有元素分成两类,被禁元素和自由元素。禁忌长度t 的选取可以有多种方法,例如t = 常数,或t = [ ],其中 n 为邻域中邻居的个数;这种规则容易在算法中实现。* n. M1 W8 z S# t) h$ x
8 Q, }! ~9 `( b( r/ a+ A& Z(4)评价函数! ^. P/ U' ^+ @. T3 ?1 q. t
评价函数是侯选集合元素选取的一个评价公式,侯选集合的元素通过评价函数值 来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标, 但有时为了方便或易于计算,会采用其他函数来取代目标函数。$ w1 g* {! g. @* [9 Q8 J
+ @( e! A- d3 `, h3 B. s
(5)特赦规则; V4 S& X* O/ x
在禁忌搜索算法的迭代过程中,会出现侯选集中的全部对象都被禁忌,或有一对 象被禁,但若解禁则其目标值将有非常大的下降情况。在这样的情况下,为了达到全局 最优,我们会让一些禁忌对象重新可选。这种方法称为特赦,相应的规则称为特赦规则。$ u: t7 q/ \$ [1 @" s7 G. o
$ e' u! w$ F8 f; \2 模型及求解 ( n3 [% z ?' J4 ^我们用禁忌搜索算法研究如下的两个问题: y' i; K% s0 O N9 Y! H4 k* U ' `; h; n. A, w$ t, J. x(1)研究 1.2 中同样的问题。+ U* ?* e5 y! |4 m8 u. ?
% S! F' X2 U2 e, f1 i$ c & x+ g( {4 X# e' I/ {
C# f) F% o# o
0 [; R3 }- U( I0 Z, p7 M1 L' @5 K/ `. ?9 Y
( q9 G9 a8 e3 d# h7 U
我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目 标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。9 R1 _$ c& Z1 W, h2 ~2 @. |
5 _$ k. p8 y1 K8 |: @7 o; G F0 f 6 c2 ^8 a0 @; O( d' z$ d
' A/ s6 Q0 _6 G9 P' a" k5 i
(2)我方有三个基地,经度、纬度分别为(70,40),(72,45),(68,48)。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标, 怎样划分任务,才能使时间最短,且任务比较均衡。 ( a* R2 c# @9 W# r" g3 O; Y/ M+ m/ ^: a% x" c8 U7 F
2.1 问题(1)的求解; t( F6 L# W- T, E6 c% |
求解的禁忌搜索算法描述如下: (1)解空间, I/ |! W& O# E, D$ {, t
! d: p5 C8 Q% ]7 P7 f) o ; t* @1 A7 ~1 c H6 c% x4 }' j0 ] 7 c6 V* y5 Y9 A- {9 z l: l8 [1 e
(2)目标函数
目标函数为侦察所有目标的路径长度。我们要求
5 y1 o$ u2 k3 K, e7 w: ~0 o$ V
' y. X. J6 R1 _- W5 S/ k
(3)候选集合& j. L5 ]9 H0 x" G) ~) h7 F4 l7 k
; @- X$ r: C9 z6 D# m: f - J& v" l0 i$ ~5 m9 s* W* ]5 S* m! B! d
) Z F4 U7 g/ H: z) `/ }# d 6 ?& ~2 |* c% r5 m5 N- i % h/ e+ F B: `+ a ?' a; ]! J我们把禁忌表设计成一个循环队列,初始化禁忌表 H = Φ 。从候选集合C 中选出 一个向量 x ,如果 x ∉ H ,并且 H 不满,则把向量 x 添加到禁忌表中;如果 H 已满, 则最早进入禁忌表的向量出列,向量 x 进入到出列的位置。 ' f; A# O$ U( K- e . ?' ?' m4 a5 K" a(5)评价函数 7 Y% K' } d( l9 k W) N9 p6 X* p4 p e2 G
可以用目标函数作为评价函数,但是这样每选取一个新的路径都得去计算总时间, 计算量比较大。对于上述二邻域中的邻居作为侯选集合,每一个新路径中只有两条边发 生了变化,因此将目标函数的差值作为评价函数可以极大地提高算法的效率。评价函数 取为 . g; o# L, `& W, _/ n c# R6 M9 q1 x( g* h }" b 9 ?- c% Z, c: u) L; D: N
6 i Q9 U) O- g1 g. | 禁忌搜索算法的流程
: H+ I j7 M" N9 N7 j; X* k' T3 b # {( i. T# u: k& Z9 T/ j$ ?1 f- H2 n' A, J) R5 A8 ?. y, }
———————————————— & Y7 g7 z4 C# h6 m) W版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 + @2 X' O l8 n# M) F" m原文链接:https://blog.csdn.net/qq_29831163/article/details/89670768% N T$ L2 a, I& Z3 m8 U G: t N
8 A6 H2 X9 z/ A. b/ O( _
6 s' d5 u- ]3 Q