数学建模社区-数学中国
标题:
数学建模：优化算法
[打印本页]
作者:
杨利霞
时间:
2019-4-10 10:57
标题:
数学建模：优化算法
数学建模：优化算法
8 o5 v& E$ {3 a* {+ u' t
优化算法
% { L5 o. H9 \
! a* h- X4 B" k9 p: C
数学建模问题总共分为四类：
; y5 _! N9 H. W, F+ s5 Q4 H i9 `; ]
1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题
/ R; ~0 r8 ~' w o& w/ U% | p
1 s3 K% G; [& h( P
一、粒子群算法（PSO）
" q, W( F$ g' ^: z
, b9 p4 `' }, u% `! Q3 u
算法对于Hepper的模拟鸟群(鱼群)的模型进行修正，同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。
2 W4 p, ]2 D5 G
PSO的优势在于简单，容易实现，无需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。
2 J1 `8 d9 @) c* T+ P
9 H9 h; ^2 _! p0 M# S; a1 ?$ t
基本PSO算法
9 L, L1 ^' t9 i
' C: o0 t$ \* n. S3 z4 e3 Y
D维空间中，有m个粒子；
0 s7 S9 l$ U: l3 N
粒子i位置：xi=(xi1,xi2,…xiD)
8 C i. s# U8 ~; I: L4 F
粒子i速度：vi=(vi1,vi2,…viD)，1≤i≤m,1 ≤d ≤D
$ a# \5 i# w* y* e( ~! s
粒子i经历过的历史最好位置：pi=(pi1,pi2,…piD)
5 {4 B+ b5 B' `& C+ m
群体内（或领域内）所有粒子所经历过的最好位置： pg =(pg1,pg2,…pgD)
* D) ~4 J$ j, H3 B. P, o" L; p
1 m; ^1 h z. W+ o! w( v
7 R2 G, R' E7 d! E- C
二、模拟退火算法（SA）
1 d2 }$ i: ]$ J, v: Z5 A( U
% i o: c& I, p8 {5 _% n
模拟退火过程：
, @% P+ q( v9 e" y2 _
设定初始高温，相当于物理退火的加温过程。初始温度要足够高，在实际应用中，要根据以往的经验，通过反复实验来确定T0的值。
$ y& J; n5 C& [" O3 f. d
热平衡达到，相当于物理退火的等温过程。是指在一个给定温度下，SA用特殊的抽样策略进行随机搜索，最终达到平衡状态的过程。这是SA算法的内循环过程。
/ p2 c6 J2 N' V. M8 R; e8 `4 v0 [+ X
降温函数，相当于物理退火的冷却过程。用来控制温度的下降方式，这是SA算法的外循环过程。常用的降温函数有Tk+1=Tk-DT，Tk+1=Tk*r，其中r∈(0.95,0.99)。
' b8 r& k$ \. F6 p
0 g6 }; W8 z+ K1 \, J
三、遗传算法
; A: h0 t+ X3 D7 s3 b8 t+ O
- l$ U2 W. A. `5 k2 ?
产生一个初始种群
9 ~6 ?% V/ D- y7 Y; u. P: @: x2 D
根据问题的目标函数构造适值函数
- j1 P/ Z% p6 [) ^
根据适应值的好坏不断选择和繁殖
( D7 y3 r+ R8 T3 @% h
若干代后得到适应值最好的个体即为最优解
3 I8 B% j' T0 a9 I9 z3 ?
7 }/ w s$ | b& G( ~; i
四、算法步骤
2 M& G7 P) r; ?4 H4 b
初始种群
- {9 ]5 L# a g1 s+ T c5 H* A
编码方法—二进制编码，可以对多个编码进行组合。
, V+ m3 t$ A1 \% B! A* j2 F
适值函数，往往就是目标函数，以值得大小为依据
* p5 _ T6 E, p) g6 L2 b4 {
遗传运算，交叉和变异
; i6 x0 W M- Z: x2 q# t
选择策略，算出适应度，根据比例采用转盘模型
8 {' D$ E: F" k2 z- p$ @1 [1 N7 J
停止准则
; }5 k# B" }( G7 @' L3 }- P
1 E `/ T& ?" G! h
参考：https://blog.csdn.net/zuochao_2013/article/details/71435105
+ k0 ?( d! f9 {6 c
' E3 k, d9 f$ W5 M4 |! L
四、神经网络算法
9 \6 k$ C' m+ [) \2 ^
3 r# P; n& ~: q1 h
和机器学习模型中的神经网络一样，用来分类或预测
; Y, r! A* e, z' A, R
# U/ A# D3 j. ]. B% W
五、禁忌搜索算法 (Tabu Search)
+ w" ^) w' T, \4 a) Q
& n1 N( S9 B1 K
又称爬山启发式算法，从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础，TS算法是在其上改进而来。
' j( A t# i6 ?9 A' s& o2 D
优点：
5 K0 A( {6 G7 }# h& P" _9 N8 ]) u
1、容易理解，容易实现，具有较强的通用性；
6 A7 m( k/ E5 a
2、局部开发能力强，收敛速度很快。
8 b. F9 E% y+ o
缺点：
+ R4 A7 [8 h! a! R# [% f6 B3 B: ?3 K- K
1、全局开发能力弱，只能搜索到局部最优解；
% w+ y: B6 A; [+ s) l( F
2、搜索结果完全依赖于初始解和邻域的映射关系。
$ g1 ]. [7 Z% S! f3 v, s
+ \# [& ?) `0 j6 m Z6 B
将不相同的n件物品分为m组，可以用的编码：
1 R# O" j4 R6 I+ `4 ]
a、带分隔符的顺序编码，以自然数1~n分别代表n件物品如：1-3-4-0-2-6-7-5-0-8-9
& p7 J* x" |5 S" t( f3 ?
b、自然数编码，每一位分别代表一件物品，而每一位的值代表该物品所在的分组。如：1-2-1-1-2-2-2-3-3
' ^ z3 D& T; a+ r6 o
(2)初始解的获取
( S& V0 [0 @! W. \# @
可以随机给出初始解，也可以事先使用其他启发式等算法给出一个较好的初始解。
( z# J) {; }* [% W
(3)移动邻域
& Y& a% H3 e3 ?) _+ k
移动是从当前解产生新解的途径，例如上述问题中用移动s产生新解s(x)。
! V( n6 k$ z3 J; x
从当前解可以进行的所有移动构成邻域，也可以理解为从当前解经过“一步”可以到达的区域。
; J$ F3 Y1 @) Y3 U# [
(4)禁忌表
; H Z$ y% q6 q$ e6 N8 Y* E
禁忌表的作用：防止搜索出现循环
7 U' c5 }' V3 A7 v/ v
(5)渴望水平函数
5 w" N7 c# |" ~/ D- x! X$ P! E
A(x，s)一般为历史上曾经达到的最好目标值，若有C(s(x))
: h5 Q4 y9 ]- R- {
0 u% g& d/ S5 O& Y/ D5 R
六、蚁群算法（AS）
& C C9 ]- G: Z
* s5 b" Q9 W+ a+ r
$ u+ m! J' P$ `; b$ F9 P
6 N+ x7 h- v5 P0 `: V+ d
P. t& d( {. r3 }7 a( m) Y
' N7 o6 D: w. \+ \7 ^+ a
/ p2 c' R: B* a( d* w: w
; B+ v$ [0 M6 _
9 _" m* u+ @( _# u
" }; a# Z2 k. m% }
5 v& R5 l. T2 {
$ Y( o9 @/ k1 V0 a
2018全国数学建模总结.docx
2019-4-10 11:37 上传
点击文件名下载附件
下载积分: 体力 -2 点
17.26 KB, 下载次数: 2, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
