- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 557466 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 172613
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
数学建模:优化算法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
|
zan
|