- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36312 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13854
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 12
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
|---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1 禁忌搜索算法的相关概念
, I7 c# a( w( F禁忌搜索算法是组合优化算法的一种,是局部搜索算法的扩展。禁忌搜索算法是人 工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所 谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点,在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点。 禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌 对象、评价函数、特赦规则、记忆频率信息等概念。# |. r0 i. ]( t& Z# U# q
1 L+ i7 j6 n0 W+ L; h' H; t(1)邻域' I1 m9 p; F3 j9 u6 W( {
在组合优化中,距离的概念通常不再适用,但是在一点附近搜索另一个下降的点仍 然是组合优化数值求解的基本思想。因此,需要重新定义邻域的概念。/ U5 h9 S" a [7 o ~) Q8 v7 C4 E
( N% {/ G0 o5 o7 }* [ 7 d$ w! c/ X# G H
8 Y D" |9 V5 D3 h
0 u8 {2 W& `( ~3 o
(2)侯选集合
1 g1 O+ [ T& N! b* A1 z4 h侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价 值最佳的邻居入选。3 j h. O) r( Z( t. \; m
K' w5 d' j6 b) q( K. S9 p# J
(3)禁忌对象和禁忌长度' W, V8 I" {; z& @$ Z) Z2 f
禁忌表中的两个主要指标是禁忌对象和禁忌长度。禁忌算法中,由于我们要避免 一些操作的重复进行,就要将一些元素放到禁忌表中以禁止对这些元素进行操作,这些元素就是我们指的禁忌对象。禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 x 一个数(禁忌长度) t ,要求对象 x 在 t 步迭代内被禁,在禁忌表中采用 tabu(x) = t 记忆,每迭代一步,该项指标做运算 tabu(x) = t −1,直到 tabu(x) = 0时 解禁。于是,我们可将所有元素分成两类,被禁元素和自由元素。禁忌长度t 的选取可以有多种方法,例如t = 常数,或t = [ ],其中 n 为邻域中邻居的个数;这种规则容易在算法中实现。* C7 e7 P* r4 E: w7 ]& c5 a8 B% g
) E5 E. T. v5 v k0 D, r(4)评价函数
% ]# p0 V! R4 q: e1 @评价函数是侯选集合元素选取的一个评价公式,侯选集合的元素通过评价函数值 来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标, 但有时为了方便或易于计算,会采用其他函数来取代目标函数。
$ ?9 ^! A5 \# q* q- e4 Q# J `8 i0 }$ Q V2 y7 \# u
(5)特赦规则- S% ]6 F$ m, Q: {
在禁忌搜索算法的迭代过程中,会出现侯选集中的全部对象都被禁忌,或有一对 象被禁,但若解禁则其目标值将有非常大的下降情况。在这样的情况下,为了达到全局 最优,我们会让一些禁忌对象重新可选。这种方法称为特赦,相应的规则称为特赦规则。
- R; k5 a3 w) i z* E! g
, D4 Y* r* i% @# F9 f! j+ W(6)记忆频率信息! I. X1 o6 q3 n$ @/ B
在计算的过程中,记忆一些信息对解决问题是有利的。如一个最好的目标值出现 的频率很高,这使我们有理由推测:现有参数的算法可能无法再得到更好的解。根据解 决问题的需要,我们可以记忆解集合、被禁对象组、目标值集合等的出现频率。 频率信息有助于进一步加强禁忌搜索的效率。我们可以根据频率信息动态控制禁 忌的长度。一个最佳的目标值出现的频率很高,有理由终止计算而将此值认为是最优值。+ h* c4 y# W F: r6 M3 j
& }# C6 f! c- @: T% b. c) Z+ \
2 模型及求解
2 k5 Y1 r# W1 K" i, w/ }我们用禁忌搜索算法研究如下的两个问题:
3 |* u7 n |9 `: g0 K, E
, N( V0 D. D; E4 [7 X! g0 S* ~(1)研究 1.2 中同样的问题。
$ ^+ W$ L6 Z3 `# d& {% V, a9 L% J i; Y' ~4 a1 ?) V0 K
![]()
0 ^9 @0 p. B0 |2 q. `+ H# |
( Y5 J4 B7 Z2 H: _; t
6 `5 B, i9 s7 J3 S5 u, }: _: y![]()
5 e4 Z7 e7 e) p+ d6 t( ~) F$ q/ E; o2 [4 [( V% X. _# I& F( E
我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目 标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。( c- ]. l7 R) F1 v
& y3 i* Y; y+ m; i. d# y% O6 B4 @ " m) ]" R% b [7 u
3 \2 @) }' ~5 X4 d5 S& o9 b9 q(2)我方有三个基地,经度、纬度分别为(70,40),(72,45),(68,48)。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标, 怎样划分任务,才能使时间最短,且任务比较均衡。- B F5 N/ _. S! [1 q# A
7 l# `3 L8 R7 @8 a2.1 问题(1)的求解
) j6 y6 V4 k( J5 W; o* s3 r, i6 w( y求解的禁忌搜索算法描述如下: (1)解空间" q" ~4 _& ?* y/ A
( m+ Q8 B$ C) l1 o" u! }- U 9 ~8 }( k7 M( Y* [. @# l
! w" U6 ]: Z. \; T# g4 @
(2)目标函数 目标函数为侦察所有目标的路径长度。我们要求 6 A! X+ K, k6 D# W; |; }# p
5 g% U' L5 o$ z9 T) x" ]2 [4 H* E: y1 u
(3)候选集合
8 w/ ^) C+ p1 Q6 \8 u- Y S; G) F% n! ~% ?
![]()
u2 k, S/ c# V+ @6 s4 G* y) B- y( m( H7 t' w4 l1 n' ]) H
如果要考虑当前解的全部二邻域(或三邻域)的邻居,将面临着太大的工作量。 因此我们用随机选取的方法每次选取50个邻居组成的集合作为侯选集合。而将省下的 时间作更多次搜索,这样做同样可以保证较高的精确度,同时可以大大提高算法的效率。 (4)禁忌长度及禁忌对象
) \ s: ?1 [) T ! o/ q' I5 g G5 J. \, [7 d2 J$ N. |
- o' e' l; c( X4 |! E C
我们把禁忌表设计成一个循环队列,初始化禁忌表 H = Φ 。从候选集合C 中选出 一个向量 x ,如果 x ∉ H ,并且 H 不满,则把向量 x 添加到禁忌表中;如果 H 已满, 则最早进入禁忌表的向量出列,向量 x 进入到出列的位置。1 f( }' B/ t A6 W( g8 C+ Z( y
+ V6 z- O$ |, L3 S9 J& q
(5)评价函数' D k" l& T2 q3 D& i
1 ^: _3 ]# z: [ l- H
可以用目标函数作为评价函数,但是这样每选取一个新的路径都得去计算总时间, 计算量比较大。对于上述二邻域中的邻居作为侯选集合,每一个新路径中只有两条边发 生了变化,因此将目标函数的差值作为评价函数可以极大地提高算法的效率。评价函数 取为
* B# s% P: B# @" P" r) E1 o
3 C/ M) V6 O2 k4 O8 K![]()
' F% a% [4 |$ _( _: ?7 G' o" u% W3 h6 a
禁忌搜索算法的流程禁忌搜索算法的流程如下: ' [2 T1 e% V! S$ p' c5 T0 k. @3 x
$ L3 Y R g r, ?0 m% W' C
7 l% A7 v4 o! R" k- a
4 ?3 f% r$ M @3 Y. s2 a- X
[* Q! {$ G3 l" \' b9 |
利用 Matlab 程序求得,我们的巡航时间大约在 41 小时左右,其中的一个巡航路径 如下图所示9 h, ^% `7 D# ^+ F9 j2 }& B6 t
6 [7 p/ g+ e# |1 w5 s* o \
' y4 ?/ d: W) K) U
$ P) z6 c$ K) |8 @
2.2 问题(2)的求解对于这个问题,我们的基本想法是,先根据敌方基地的分布特点将敌方的基地大体 划分在三个区域之内,并使三架侦察机分别对这三个区域的敌军基地进行侦察,求取各 自的最短时间。然后对任务不均衡区域之中的点做适当调整。 我们解决问题的步骤如下: ![]()
% R: U, C2 \. F3 |0 y
: ?2 x7 e+ r4 D- B$ Z, l/ s( g![]()
- q4 g. h/ X% c+ _0 R% N# [
, C5 Z) F0 c$ X, R$ G————————————————
$ C% Q" d6 W S. p版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
3 |9 |/ S* X* Z, X& F原文链接:https://blog.csdn.net/qq_29831163/article/details/89670768
3 J: v* x% ^8 c. w2 Z- H/ z
. }8 q- [2 M) e: |) ^, t0 {: T/ o) \6 d5 u5 @% b( ^
|
zan
|