数学建模社区-数学中国
标题:
数学建模：优化算法
[打印本页]
作者:
杨利霞
时间:
2019-3-19 17:41
标题:
数学建模：优化算法
数学建模：优化算法
$ S, }( @# t4 ~+ K4 y' N
数学建模问题总共分为四类：
* ]: T: N. `/ o- E: y5 j! E
1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题
- c( ?" y, u( k6 y/ A
6 |+ i3 U; L Q, V i
一、粒子群算法（PSO）
) x4 _$ @& y0 Q! b8 K0 l* q
* R4 e: p- F F, y1 |; f
算法对于Hepper的模拟鸟群(鱼群)的模型进行修正，同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。
4 }+ U3 F( o3 [- x
PSO的优势在于简单，容易实现，无需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。
8 T A2 k/ U+ [- V
. G" ^' f- k- `" b- Y1 e# X
基本PSO算法
3 n/ p0 O& ], b' `* v$ I5 u
6 O5 t6 u. C3 ` a6 e
D维空间中，有m个粒子；
0 m8 P# C9 |9 |$ [5 Z2 v, }) O
粒子i位置：xi=(xi1,xi2,…xiD)
7 j2 C; n% z8 {5 \- t
粒子i速度：vi=(vi1,vi2,…viD)，1≤i≤m,1 ≤d ≤D
$ R# }' i5 K. y: l
粒子i经历过的历史最好位置：pi=(pi1,pi2,…piD)
& J2 E3 y; k: r. ~1 X/ T
群体内（或领域内）所有粒子所经历过的最好位置： pg =(pg1,pg2,…pgD)
) N* M4 l+ j$ r+ N- T
5 v, ^9 V9 o2 O$ X( y; [5 D! N, T
' Y% q, ~. q; |) `. u J
二、模拟退火算法（SA）
+ N# A1 `8 @3 f* X) s1 i; T2 i
2 j) j" L) T2 ~5 d! i+ O
模拟退火过程：
0 E$ m1 g1 b: `, |0 M" R# v: R
设定初始高温，相当于物理退火的加温过程。初始温度要足够高，在实际应用中，要根据以往的经验，通过反复实验来确定T0的值。
1 J, w: t" P1 D; s4 l* b
热平衡达到，相当于物理退火的等温过程。是指在一个给定温度下，SA用特殊的抽样策略进行随机搜索，最终达到平衡状态的过程。这是SA算法的内循环过程。
& `- e8 y1 i4 c
降温函数，相当于物理退火的冷却过程。用来控制温度的下降方式，这是SA算法的外循环过程。常用的降温函数有Tk+1=Tk-DT，Tk+1=Tk*r，其中r∈(0.95,0.99)。
; u1 g& |7 p0 |5 e6 E
8 {( Q7 ]) g8 h& [
三、遗传算法
% O; _$ F# u. _0 M- q
' u( o' F. p& A- {, A
产生一个初始种群
# j9 j+ p, P4 m: z* r9 u2 v8 a+ Z
根据问题的目标函数构造适值函数
$ {; v, l6 ^# R6 L
根据适应值的好坏不断选择和繁殖
% y. e: ]" s7 p5 o$ n( l& {
若干代后得到适应值最好的个体即为最优解
. A K5 Q$ C1 H" G& e x4 ~. O8 o
3 F& C/ w) w( ?5 Z/ w
四、算法步骤
- {' n$ e& y$ L: P |# L
初始种群
0 `8 [9 b+ K5 I& S5 _! c* }
编码方法—二进制编码，可以对多个编码进行组合。
7 N4 I8 y/ A, Y. c m2 K6 R
适值函数，往往就是目标函数，以值得大小为依据
" U8 ]& X; H ~- g
遗传运算，交叉和变异
: Y0 ?8 K4 h# y% y- P
选择策略，算出适应度，根据比例采用转盘模型
. n+ F- S+ I0 p1 c; a& u% n8 t
停止准则
5 }9 x7 s+ Z: \
$ v! H& s, w! V# k& B+ i
参考：https://blog.csdn.net/zuochao_2013/article/details/71435105
9 z+ a! a" D1 Y( [* f
7 k& x( ]9 w& ?# {
四、神经网络算法
: a% y/ T% A6 I
; ?$ {# X& @; {0 b7 ~2 K
和机器学习模型中的神经网络一样，用来分类或预测
0 g+ K5 N) u) z' u7 c' _+ o
' D' s" U, e5 ~& L& G' U
五、禁忌搜索算法 (Tabu Search)
- g$ d( k2 p( ?. s. h
! e; k9 l3 Y. t, N4 O' U
又称爬山启发式算法，从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础，TS算法是在其上改进而来。
/ Y: Y4 x8 T/ @6 X( C6 ]
优点：
$ f6 \! B2 Y D
1、容易理解，容易实现，具有较强的通用性；
/ z+ W7 o) O2 s0 I$ R0 G. f2 C! y
2、局部开发能力强，收敛速度很快。
1 P9 l$ ~6 B7 N i
缺点：
8 _5 S% n( w7 S
1、全局开发能力弱，只能搜索到局部最优解；
& I0 j) Y+ J6 ^4 Z
2、搜索结果完全依赖于初始解和邻域的映射关系。
. z! s* f& [8 g6 c' R, ^
' {4 h8 Z: R3 T
将不相同的n件物品分为m组，可以用的编码：
7 x6 x r r: S9 x- W$ |
a、带分隔符的顺序编码，以自然数1~n分别代表n件物品如：1-3-4-0-2-6-7-5-0-8-9
3 X% m5 P( R6 R" ~4 m
b、自然数编码，每一位分别代表一件物品，而每一位的值代表该物品所在的分组。如：1-2-1-1-2-2-2-3-3
- j3 |) V" i, J. }- {
(2)初始解的获取
! K. i# C+ d# Y# d+ p g" h
可以随机给出初始解，也可以事先使用其他启发式等算法给出一个较好的初始解。
0 j! F. A% {3 Z
(3)移动邻域
. p. U3 g J, ~5 y3 N
移动是从当前解产生新解的途径，例如上述问题中用移动s产生新解s(x)。
* v& l& j* ~" {
从当前解可以进行的所有移动构成邻域，也可以理解为从当前解经过“一步”可以到达的区域。
) L, W+ P& P5 H2 o
(4)禁忌表
T& U, j. D$ b) [5 }. L
禁忌表的作用：防止搜索出现循环
5 Q+ t! ~! g0 C3 o, q* w
(5)渴望水平函数
7 a* x. l6 x! t
A(x，s)一般为历史上曾经达到的最好目标值，若有C(s(x))
8 @- b) q! J$ d; b7 z
" g+ Q$ U! w/ y. S5 v9 T/ t
六、蚁群算法（AS）
r5 c$ Z$ i3 G8 Q
% U3 e$ x8 V% ]7 u- N; h+ @
# ]' u# H* {; ]' M- ]* k2 I
参考：http://www.cnblogs.com/asxinyu/p/Path_Optimization_Tsp_Problem_Ant_System_CSharp.html#_labelTop
3 g0 K0 u) q. ~( V* x6 C1 A
---------------------
( Z: ]/ L. W8 i( m+ ~1 Z
作者：_朝闻道_
: N D5 |1 T9 U
来源：CSDN
) m8 A% Q; V2 G
4 N7 k6 ?. q( O, |0 B9 i
( Y' V% q' Q. C
3 N# P1 W# e2 i' u1 ]& W& S( J
; S: w2 W% ~$ i9 i* C$ Q9 L
16种常用的数据分析方法汇总.docx
2019-3-25 17:34 上传
点击文件名下载附件
下载积分: 体力 -2 点
20.53 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
