QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2880|回复: 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
    数学建模:优化算法
    ) c8 b0 `  L  K4 @优化算法
    * V( c8 Z4 p' C2 _# {
    5 ~1 j9 T! @  W数学建模问题总共分为四类: ' @- D' C9 A8 `+ A
    1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题4 U3 M8 `( ~4 C
    4 o2 ?: K- D) N0 I0 p
    一、粒子群算法(PSO)
    - ]/ E3 O8 w; N6 T9 X5 W% d9 x! p
    算法对于Hepper的模拟鸟群(鱼群)的模型进行修正,同遗传算法类似,也是一种基于群体叠代的,但并没有遗传算法用的交叉以及变异,而是粒子在解空间追随最优的粒子进行搜索。
    " G: |% O: Q" o! `  APSO的优势在于简单,容易实现,无需梯度信息,参数少,特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景,既适合科学研究,又特别适合工程应用。  P) X7 K7 O" s7 m/ Q9 @0 P
    4 p( i: i9 T0 ?; C* t& j2 r' n
    基本PSO算法+ k/ j1 B6 Z7 H

    8 c3 i* c" f0 U# w/ f7 P  [2 }9 v  C9 MD维空间中,有m个粒子;
    # \, G& ]4 j/ \1 t- l粒子i位置:xi=(xi1,xi2,…xiD)
    ! c( ~8 d( k8 N8 d$ l粒子i速度:vi=(vi1,vi2,…viD),1≤i≤m,1 ≤d ≤D
    . U6 q, ]" F1 {粒子i经历过的历史最好位置:pi=(pi1,pi2,…piD)
    8 g: j% F* v" L群体内(或领域内)所有粒子所经历过的最好位置: pg =(pg1,pg2,…pgD)
    ' I+ a# E- r9 r8 a
    * g" _6 u0 V/ ?6 Q4 V+ H0 J6 G0 \. u$ \/ P% u8 K9 E8 w
    二、模拟退火算法(SA)( Z; V$ f1 h/ l6 Y2 K& R
    " a$ p' i% }2 x# z  k, e$ I) [+ m
    模拟退火过程:
    * u* `: {$ P  |- y* j设定初始高温,相当于物理退火的加温过程。初始温度要足够高,在实际应用中,要根据以往的经验,通过反复实验来确定T0的值。
    % Y4 V5 E7 Z" K/ v, _; b& V3 X热平衡达到,相当于物理退火的等温过程。是指在一个给定温度下,SA用特殊的抽样策略进行随机搜索,最终达到平衡状态的过程。这是SA算法的内循环过程。 + g. q1 n8 u& ?: X3 P
    降温函数,相当于物理退火的冷却过程。用来控制温度的下降方式,这是SA算法的外循环过程。常用的降温函数有Tk+1=Tk-DT,Tk+1=Tk*r,其中r∈(0.95,0.99)。
    * _: J: M$ y9 C1 m3 i; r# ]; I) W, }
    ( Z' s3 [/ o/ j. [7 o  k三、遗传算法5 |) a' R0 \* Q  U; _# H

    8 k  S7 }; m& y' u产生一个初始种群 3 `- L: K. Q" U) P1 K* m; h
    根据问题的目标函数构造适值函数
    , S' U7 j# P  l5 r' r- e根据适应值的好坏不断选择和繁殖
    . v! }5 f( V4 ~( S# Y若干代后得到适应值最好的个体即为最优解
    & m( r7 @# v2 s* \. N: M. g6 z! A6 h4 r9 v2 B) X9 C0 W: S7 R
    四、算法步骤 . V& V- d5 Y4 y. C
    初始种群 2 G. s. q) Q& M3 V
    编码方法—二进制编码,可以对多个编码进行组合。 ) G; u) B7 X# T1 o& S% n6 l
    适值函数,往往就是目标函数,以值得大小为依据 / z& O1 m6 ^$ s
    遗传运算,交叉和变异
    . b( V6 [$ G' W1 L0 ?7 r选择策略,算出适应度,根据比例采用转盘模型 # ]- x: G7 j7 h4 ~, ~
    停止准则. J0 j3 X% b  L
    + v; p0 P. g! T: u9 j
    参考:https://blog.csdn.net/zuochao_2013/article/details/714351057 R  s$ ]( U) w

    9 o7 W/ E$ x; Z% e. i  l; s* ?四、神经网络算法) r, X9 |0 K4 _1 ~$ |+ ]9 a
    7 B, \7 I( A, t8 _9 h
    和机器学习模型中的神经网络一样,用来分类或预测
    " s1 Q$ p9 K; T- C: Z0 K
    8 b$ a+ R6 I7 F5 B" a3 s$ ^五、禁忌搜索算法 (Tabu Search)
    ; k6 G1 v1 `. X/ r% e8 |
    7 G# ~% ~3 [4 e+ N: O( h) M又称爬山启发式算法,从当前的节点开始,和周围的邻居节点的值进行比较。如果当前节点是最大的,那么返回当前节点,作为最大值(即山峰最高点);反之就用最高的邻居节点替换当前节点,从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础,TS算法是在其上改进而来。 ) z! E( h5 b* }9 e9 q% T2 B% K7 l) [
    优点: ! y2 K. ~0 D4 `8 w2 [$ l1 t
    1、容易理解,容易实现,具有较强的通用性; 4 ^! v0 l* O6 B6 @1 c  ?) H5 Y- k
    2、局部开发能力强,收敛速度很快。
    5 C! d$ c( I! E缺点: : l) M& c$ ^! ]6 N0 D3 S% q' s% }1 b
    1、全局开发能力弱,只能搜索到局部最优解;
    2 B  S2 @6 B' Y2、搜索结果完全依赖于初始解和邻域的映射关系。. `+ W  `. r3 q/ v

    6 F) U' P5 B0 h. N$ ^# v( [将不相同的n件物品分为m组,可以用的编码: 5 G1 Z8 I) }/ I3 ~8 s
    a、带分隔符的顺序编码,以自然数1~n分别代表n件物品如:1-3-4-0-2-6-7-5-0-8-9
    2 o3 L* @% ?; U$ F% Jb、自然数编码,每一位分别代表一件物品,而每一位的值代表该物品所在的分组。如:1-2-1-1-2-2-2-3-3 ) g, ?+ T8 f9 f% l1 ]
    (2)初始解的获取 4 x. h' M# \4 B/ k' L0 Y2 Y$ ~
    可以随机给出初始解,也可以事先使用其他启发式等算法给出一个较好的初始解。
    # k) m) ~. c0 g(3)移动邻域 4 K, i* ]4 d/ @* V
    移动是从当前解产生新解的途径,例如上述问题中用移动s产生新解s(x)。
    ; t( I/ D! l2 @/ r从当前解可以进行的所有移动构成邻域,也可以理解为从当前解经过“一步”可以到达的区域。
    , B: f3 ^0 S4 W. V(4)禁忌表
    ( v8 L9 Y; c7 o5 f( K- Y禁忌表的作用:防止搜索出现循环
    2 f( x! U# K, l7 a(5)渴望水平函数 . q9 T9 [+ R+ e8 p
    A(x,s)一般为历史上曾经达到的最好目标值,若有C(s(x))
    9 h1 \% C& ~3 i. w/ ?
    7 A' a; i2 ^: e! _六、蚁群算法(AS)$ L; b0 H- ~* B! i& V

    - [6 H: }  t/ f4 |- f( _: a
    ) m3 O1 P$ q8 C# r" [5 i
    8 }' s$ B0 J1 d( X/ {& T
    6 x! N/ @- P! t) V3 B/ _5 D+ Z6 |) P0 T. b$ T7 M- S( R
    8 v9 P( l. o( Q& g* u& d7 Y' N
    7 F' A) M1 j6 c6 R& Q2 w- a

    4 p* Y1 q2 g% d  ^* q, w
    , Q$ a( ?' \% e$ X# W& X) p0 C3 J$ d) X8 e) r0 ^
    & h0 I' `0 Q. c0 U% q: ]1 p

    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, 2026-6-15 01:43 , Processed in 0.965753 second(s), 54 queries .

    回顶部