QQ登录

只需要一步,快速开始

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

[建模教程] 数学建模:优化算法

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2019-4-10 10:57 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    数学建模:优化算法7 p; M5 W+ ~. s4 E# ^" w/ w; F
    优化算法
    3 }! @# ?3 H6 T* A) p; A7 s/ e& n6 n3 X; _$ n2 I- B6 A+ V
    数学建模问题总共分为四类: / P$ X$ [7 \. x- D
    1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题
    7 M# _2 ^8 x# j' A# ^
    % x9 t9 p0 |/ n! }一、粒子群算法(PSO)
    5 V8 T4 F. p5 B7 P; B+ d; Z' H# q# X6 }1 D  L% q
    算法对于Hepper的模拟鸟群(鱼群)的模型进行修正,同遗传算法类似,也是一种基于群体叠代的,但并没有遗传算法用的交叉以及变异,而是粒子在解空间追随最优的粒子进行搜索。
    ! x, ?& ^5 }% o0 l$ n- ]: {8 OPSO的优势在于简单,容易实现,无需梯度信息,参数少,特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景,既适合科学研究,又特别适合工程应用。: i+ ]# d5 m7 [7 x) g

    & ~6 ]: r5 t$ Z! ?* u+ m基本PSO算法
    + ~! h# u8 Z0 m# w' J% S) f" j% x& [5 o2 z! z
    D维空间中,有m个粒子; $ h  e$ o6 N: t, C5 x
    粒子i位置:xi=(xi1,xi2,…xiD)
    5 n; k$ R+ k. W# a, K# O* O$ k粒子i速度:vi=(vi1,vi2,…viD),1≤i≤m,1 ≤d ≤D 8 }2 U" y+ x& u8 b
    粒子i经历过的历史最好位置:pi=(pi1,pi2,…piD)
    4 ~* P" D  m# z6 p4 p6 R- n$ }& p: E9 s群体内(或领域内)所有粒子所经历过的最好位置: pg =(pg1,pg2,…pgD)
      _: n; J* T5 m0 f" A& X: W2 Z
    ! I" D0 O  s, D
    ) d* r) v; w5 }# e8 y二、模拟退火算法(SA)$ z0 G' ~! {  _( P4 g7 V

      K2 T5 u- R/ V: [模拟退火过程:
    - L* K: M: s, n设定初始高温,相当于物理退火的加温过程。初始温度要足够高,在实际应用中,要根据以往的经验,通过反复实验来确定T0的值。
    ) h. W' S9 y3 e热平衡达到,相当于物理退火的等温过程。是指在一个给定温度下,SA用特殊的抽样策略进行随机搜索,最终达到平衡状态的过程。这是SA算法的内循环过程。
    , _( Q2 Q9 a6 m5 F降温函数,相当于物理退火的冷却过程。用来控制温度的下降方式,这是SA算法的外循环过程。常用的降温函数有Tk+1=Tk-DT,Tk+1=Tk*r,其中r∈(0.95,0.99)。
    1 P1 i4 s/ H5 m; q+ G. B3 t3 Q9 F5 \) g
    三、遗传算法+ E* B/ M, N* p3 b6 p; P7 e0 a

    2 I' X+ u) a$ D2 k2 l/ P产生一个初始种群 3 [; `6 \9 l; }2 }7 g4 c3 b
    根据问题的目标函数构造适值函数
    " |2 t* {+ C: d根据适应值的好坏不断选择和繁殖
    + b4 y$ @# V: _5 ?0 P6 a% A若干代后得到适应值最好的个体即为最优解
    0 v0 l+ C' N' E2 ~+ k9 I. R- ?% a" r/ w! `+ B1 x; v& z; F1 U. \; Y2 j: e
    四、算法步骤
    / z- z4 Z* i, u9 `/ `5 t: ?2 c: {初始种群 2 U* ^2 C6 d8 v8 X1 A2 o0 Z# u
    编码方法—二进制编码,可以对多个编码进行组合。 , z; F  B4 h2 }2 O6 ]
    适值函数,往往就是目标函数,以值得大小为依据
    ( c5 _8 _# U! H0 k& t& q遗传运算,交叉和变异
    ; U& }3 S4 y0 A$ a0 s, H8 V% g* A/ k选择策略,算出适应度,根据比例采用转盘模型 $ d. F( D* w4 a% B3 B( ]
    停止准则- W  C: C9 |" u7 l2 n3 ]
    ! Y) C% J" {9 ^7 S; ~
    参考:https://blog.csdn.net/zuochao_2013/article/details/71435105, \/ M6 W) F0 B$ ~( @
    $ m) [; s; g2 x" y/ W8 F( l
    四、神经网络算法8 T% c- i% S. q2 d# h) E

    * L1 E0 P1 p! `+ W. `和机器学习模型中的神经网络一样,用来分类或预测( X. Q& r' {  }, c
    5 \. k1 ^3 @) u7 r1 \0 p* e+ H
    五、禁忌搜索算法 (Tabu Search)
    * P/ l- z$ E& w7 \, `3 ^+ Q# b9 |: \  l8 w% h8 F5 P9 L
    又称爬山启发式算法,从当前的节点开始,和周围的邻居节点的值进行比较。如果当前节点是最大的,那么返回当前节点,作为最大值(即山峰最高点);反之就用最高的邻居节点替换当前节点,从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础,TS算法是在其上改进而来。 # H% b& r) L6 K# J0 `" M4 }
    优点: 9 L# w5 G* B7 E5 d9 D. Y
    1、容易理解,容易实现,具有较强的通用性; 6 L$ J. u9 P4 m4 d( f  n! Q
    2、局部开发能力强,收敛速度很快。
    0 R+ _1 J% U: S* n缺点: - n7 w7 B' k( f! @- q. D5 O% D
    1、全局开发能力弱,只能搜索到局部最优解;
    ) Q- h% }  y) v: L2、搜索结果完全依赖于初始解和邻域的映射关系。4 M) y  p$ Q, e5 \2 w: J. ?# |
      i2 W6 ]' z! j- N
    将不相同的n件物品分为m组,可以用的编码:
    $ U' [& P' F% Sa、带分隔符的顺序编码,以自然数1~n分别代表n件物品如:1-3-4-0-2-6-7-5-0-8-9 / L: ?3 {( q) o( E# S
    b、自然数编码,每一位分别代表一件物品,而每一位的值代表该物品所在的分组。如:1-2-1-1-2-2-2-3-3   h1 N0 Y! E+ q' l* D  ?; O
    (2)初始解的获取
    7 s+ d: f5 _% p3 N9 n可以随机给出初始解,也可以事先使用其他启发式等算法给出一个较好的初始解。 ; c& @+ p* Z. s2 _+ m4 |
    (3)移动邻域
    , n4 M( a+ G: V3 O移动是从当前解产生新解的途径,例如上述问题中用移动s产生新解s(x)。
    % D$ _3 p' J1 T从当前解可以进行的所有移动构成邻域,也可以理解为从当前解经过“一步”可以到达的区域。 $ ^! X0 _$ x& A$ g
    (4)禁忌表 * X6 V* w. b' Q2 i( y" V1 W: W
    禁忌表的作用:防止搜索出现循环
    " W! Q8 K; O3 x* T. ](5)渴望水平函数
    / f: I6 m3 v' t! B# ^4 B& xA(x,s)一般为历史上曾经达到的最好目标值,若有C(s(x))1 Y) v1 y/ o2 Q4 M. W3 p* [( ^7 K- V

    / z* S  p/ o, i+ \六、蚁群算法(AS)
    4 _& j' [. V3 A. y9 n/ m# {0 p3 F1 r8 i9 T8 q
    + G: g! i2 w& D! M' v5 S

    * G. _1 ^2 n5 O2 t$ U& {
    % i% i/ @5 {7 t# U1 y" V. o! @1 O& i# }7 ~( g- e; S

    3 }9 W" }$ \+ y) \' b4 Z4 h& q
    , W( }8 d% o0 J8 m( j& q; y/ `8 w' Z6 }: _
    . u2 j; ?" A  X. F! g+ |

    1 m- ~6 j# m) S* K; e& ~* f6 \4 z* f! b- H

    2018全国数学建模总结.docx

    17.26 KB, 下载次数: 2, 下载积分: 体力 -2 点

    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, 2025-7-28 03:12 , Processed in 0.420451 second(s), 53 queries .

    回顶部