QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2143|回复: 0
打印 上一主题 下一主题

组合优化算法-现代优化算法(三):禁忌搜索算法

[复制链接]
字体大小: 正常 放大
浅夏110 实名认证       

542

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2020-11-14 17:15
  • 签到天数: 74 天

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    跳转到指定楼层
    1#
    发表于 2020-5-22 15:25 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    1 禁忌搜索算法的相关概念
    : c. n+ A3 h- W5 J禁忌搜索算法是组合优化算法的一种,是局部搜索算法的扩展。禁忌搜索算法是人 工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所 谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点,在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点。 禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌 对象、评价函数、特赦规则、记忆频率信息等概念。5 v8 u6 ~0 y. ~( z; M. r5 r' @
    * C$ x' ?0 ^, J& V1 E
    (1)邻域
    3 R( V. o4 K1 G0 P5 X) g, T% t2 E在组合优化中,距离的概念通常不再适用,但是在一点附近搜索另一个下降的点仍 然是组合优化数值求解的基本思想。因此,需要重新定义邻域的概念。
    ) q7 C8 x' K6 z! p7 |
    4 b7 Z2 z) {" s% t; ~& t. Q* f4 I+ p0 \" ]4 k
    - e+ Y3 A* E# p8 ?, a4 F0 O, m
    2 G3 E$ g0 K7 D6 w- H/ r
    (2)侯选集合
    , P* [3 B/ F: L: [5 B, U' _; ]% G! s侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价 值最佳的邻居入选。
    & v7 j: G# D+ H
    5 S4 _: i8 i  G6 h(3)禁忌对象和禁忌长度2 F: D" }" ~2 o' T# m$ g
    禁忌表中的两个主要指标是禁忌对象和禁忌长度。禁忌算法中,由于我们要避免 一些操作的重复进行,就要将一些元素放到禁忌表中以禁止对这些元素进行操作,这些元素就是我们指的禁忌对象。禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 x 一个数(禁忌长度) t ,要求对象 x 在 t 步迭代内被禁,在禁忌表中采用 tabu(x) = t 记忆,每迭代一步,该项指标做运算 tabu(x) = t −1,直到 tabu(x) = 0时 解禁。于是,我们可将所有元素分成两类,被禁元素和自由元素。禁忌长度t 的选取可以有多种方法,例如t = 常数,或t = [  ],其中 n 为邻域中邻居的个数;这种规则容易在算法中实现。
      h, X2 B, C" _& l6 I( |  v$ y( o1 o/ _  n8 @6 t: b
    (4)评价函数
    0 Z# M: Z, L- F/ h! n- X8 ?评价函数是侯选集合元素选取的一个评价公式,侯选集合的元素通过评价函数值 来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标, 但有时为了方便或易于计算,会采用其他函数来取代目标函数。9 s- S6 ]& L) U4 k" Y9 L3 z

    / I% k( H  k/ d: Q(5)特赦规则3 I5 }" U1 V2 [0 M! k
    在禁忌搜索算法的迭代过程中,会出现侯选集中的全部对象都被禁忌,或有一对 象被禁,但若解禁则其目标值将有非常大的下降情况。在这样的情况下,为了达到全局 最优,我们会让一些禁忌对象重新可选。这种方法称为特赦,相应的规则称为特赦规则。2 \/ p7 I# T. F" p* J" _

    ; s5 i% I! d% E+ c5 Q! x( K. P(6)记忆频率信息) y2 k/ w/ i  A+ z+ W  }- g! y
    在计算的过程中,记忆一些信息对解决问题是有利的。如一个最好的目标值出现 的频率很高,这使我们有理由推测:现有参数的算法可能无法再得到更好的解。根据解 决问题的需要,我们可以记忆解集合、被禁对象组、目标值集合等的出现频率。 频率信息有助于进一步加强禁忌搜索的效率。我们可以根据频率信息动态控制禁 忌的长度。一个最佳的目标值出现的频率很高,有理由终止计算而将此值认为是最优值。  B7 }& D6 Q/ _6 h5 r
    8 X! U" G4 o9 I7 `7 F: U# O
    2 模型及求解
    8 z% e$ x+ M; Y( M1 R4 j# M我们用禁忌搜索算法研究如下的两个问题:5 M- J3 j( B% J" X$ p! G
    1 Q; F! k* Z( k) W4 d0 z
    (1)研究 1.2 中同样的问题。6 x2 j) b  B/ U8 @' C

    ! v' R  M4 a! _3 R, x" _8 i4 I) A2 e& Y$ v# b+ h! R
    & g& N* ~3 t6 j* L, {
    - Z- N5 w& u, A" k

    + \+ F( D4 S6 F
    % Q3 @% i6 N$ {我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目 标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。
    * g, g" M2 i! ], q% B% l
    ; e+ y) T& r/ x3 |4 Z; z5 F3 k5 h' G
    ! z$ w' n) J1 t% y
    * m3 p8 ]% A7 S% Z, k3 I(2)我方有三个基地,经度、纬度分别为(70,40),(72,45),(68,48)。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标, 怎样划分任务,才能使时间最短,且任务比较均衡。
    7 a6 H/ p6 R: q5 n- n( l$ ~. G% g' X9 v8 D# L" a8 W# X2 _
    2.1 问题(1)的求解
    7 m+ `1 p1 U% h( O1 U7 Y3 r3 {求解的禁忌搜索算法描述如下: (1)解空间
    9 [4 Q; i' V' _$ n+ a* d. a7 g2 f* b. p4 Y3 x

    8 N" {( `4 ^# n, Q2 C) S5 m3 D  g, F6 ^$ M7 [# P

    (2)目标函数

    目标函数为侦察所有目标的路径长度。我们要求


    . B1 K% F" P5 R- ]1 d6 ?5 R
    5 D5 {3 u# P+ g0 @% j9 ~% p( V(3)候选集合' F: T) p4 f) l" L1 y! s3 |
    . ^; [/ [( w7 z
    . S4 V4 b& {9 w! z8 L3 Q3 l/ C

    ( Z) L5 j# g. ]# r$ F, A. z

    如果要考虑当前解的全部二邻域(或三邻域)的邻居,将面临着太大的工作量。 因此我们用随机选取的方法每次选取50个邻居组成的集合作为侯选集合。而将省下的 时间作更多次搜索,这样做同样可以保证较高的精确度,同时可以大大提高算法的效率。

    (4)禁忌长度及禁忌对象


    . B" e9 T9 C3 _3 L+ ?/ G, x4 f; h( d  F9 j; Z" A/ C
    " f. N1 h1 K2 a& \7 i
    我们把禁忌表设计成一个循环队列,初始化禁忌表 H = Φ 。从候选集合C 中选出 一个向量 x ,如果 x ∉ H ,并且 H 不满,则把向量 x 添加到禁忌表中;如果 H 已满, 则最早进入禁忌表的向量出列,向量 x 进入到出列的位置。# X( G4 |+ h$ v3 o  [1 g

    / R' W( m% k7 U) I8 H(5)评价函数* A/ J* T4 ~- }7 \- ^7 Z8 }7 c) c

    : l  J/ ~6 C+ s  B6 I5 T. b! D可以用目标函数作为评价函数,但是这样每选取一个新的路径都得去计算总时间, 计算量比较大。对于上述二邻域中的邻居作为侯选集合,每一个新路径中只有两条边发 生了变化,因此将目标函数的差值作为评价函数可以极大地提高算法的效率。评价函数 取为6 Z' B9 {1 B5 d# @

    / \$ F/ d8 K7 w1 H: B
    6 T5 H2 Q  f4 S9 j3 G3 b/ U* T9 j! ^; s, o) D! l* s- C( X
    禁忌搜索算法的流程

    禁忌搜索算法的流程如下:

    - V7 d1 C4 a8 S! p) F

    ; ~8 k/ Z! p2 W; n; R0 C7 \6 Q+ x9 i# @) l& K9 a
    ! ]9 W/ ^6 ]1 j- F% d9 `

    / y" p$ i# _6 c. f! A9 D利用 Matlab 程序求得,我们的巡航时间大约在 41 小时左右,其中的一个巡航路径 如下图所示
    / X$ R+ o/ T/ s2 _. q& P5 o  m, a9 \( y. A3 C3 ^6 b: P2 U

    ! Y+ k" E2 \7 j; `( O$ h3 }% I
    , A% k# Z; `" q& s% U2 M2.2 问题(2)的求解

    对于这个问题,我们的基本想法是,先根据敌方基地的分布特点将敌方的基地大体 划分在三个区域之内,并使三架侦察机分别对这三个区域的敌军基地进行侦察,求取各 自的最短时间。然后对任务不均衡区域之中的点做适当调整。 我们解决问题的步骤如下:

    * r: `' k2 Z) l/ j( C' V) ~; b
    * @3 m  u( B# U
    : q9 ^. `% U! u; {6 q7 `( B, |4 q

    & d: D4 W0 h6 b# b  v& ~% b————————————————
    3 V. v) {2 U% l; F, ?% {- B6 [  Y版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。  Y* {/ O$ V8 l* }5 c+ D
    原文链接:https://blog.csdn.net/qq_29831163/article/details/89670768
    $ A) e7 x4 S/ y% y
    % W7 }7 w( u8 z8 `  f# {0 U' n$ y( {3 A2 L# @" F& \1 p
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-9-10 04:48 , Processed in 0.442604 second(s), 51 queries .

    回顶部