数学建模社区-数学中国
标题:
数学建模：优化算法
[打印本页]
作者:
杨利霞
时间:
2019-4-18 15:54
标题:
数学建模：优化算法
数学建模：优化算法
: r5 H0 W, K( |/ P5 J! K+ [# T
数学建模问题总共分为四类：
# O9 z6 @. S9 n! ^
1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题
: Z( H# ^( d& @8 z1 c$ t
1 c0 t) M* y" Y1 q2 a$ `" S1 g
一、粒子群算法（PSO）
, C3 ~3 Z. W' o2 w( f
( d' O$ p ~+ ~, K9 l
算法对于Hepper的模拟鸟群(鱼群)的模型进行修正，同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。
0 M6 f( c; u' P d
PSO的优势在于简单，容易实现，无需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。
" P4 b) S% e4 E
+ h5 a$ W+ Y9 i# c+ X! Y( k
基本PSO算法
9 L& V% B9 C; e9 O$ m; W
1 e8 ` L' \. H7 D& b: m
D维空间中，有m个粒子；
$ `' r" R7 ~; U% Z- m4 A
粒子i位置：xi=(xi1,xi2,…xiD)
G& c$ `, W0 X% z1 [* o. C# P
粒子i速度：vi=(vi1,vi2,…viD)，1≤i≤m,1 ≤d ≤D
, p. d( T) ?) y+ v, e: h1 `6 F
粒子i经历过的历史最好位置：pi=(pi1,pi2,…piD)
+ x5 c' h9 a$ c0 u0 `6 |
群体内（或领域内）所有粒子所经历过的最好位置： pg =(pg1,pg2,…pgD)
8 h& T+ K5 e6 z. r3 R
* G! k% W; q3 s" S
6 o) S& S+ F# S4 D, c0 q: N
二、模拟退火算法（SA）
, P5 Q( o$ K* { F' i6 K3 N( `# k. J; a
2 _; w; T) ] d$ @" t
模拟退火过程：
/ j% ?$ ?9 a1 Y& {- K4 r+ D
设定初始高温，相当于物理退火的加温过程。初始温度要足够高，在实际应用中，要根据以往的经验，通过反复实验来确定T0的值。
" t$ p6 H8 g2 ?1 ?, U
热平衡达到，相当于物理退火的等温过程。是指在一个给定温度下，SA用特殊的抽样策略进行随机搜索，最终达到平衡状态的过程。这是SA算法的内循环过程。
: e9 @; I6 j' p: k9 a9 y& Y; L
降温函数，相当于物理退火的冷却过程。用来控制温度的下降方式，这是SA算法的外循环过程。常用的降温函数有Tk+1=Tk-DT，Tk+1=Tk*r，其中r∈(0.95,0.99)。
# k2 W" M& ?, y- m
& a7 d6 ~0 Y8 x8 B) Q
三、遗传算法
% |7 X G' {6 K# a- w
6 I& y6 c; {) a; Y, v. N( w# w
产生一个初始种群
2 _. V6 }0 [: P/ ]2 M% U, {" j) u
根据问题的目标函数构造适值函数
) i& N4 z5 ~; }4 s; Q( b8 H! ?
根据适应值的好坏不断选择和繁殖
- n/ ]* W4 d7 ^# n& G9 w$ F, u) `
若干代后得到适应值最好的个体即为最优解
( R5 M: n/ x: z$ F
2 E6 L8 `7 A$ |5 A& \6 m
四、算法步骤
( ]9 c! q* C# z, u' d& p; y& c
初始种群
7 z# G7 Q9 F' A: k
编码方法—二进制编码，可以对多个编码进行组合。
7 [0 P0 ~3 @# ~% X$ p6 G4 D
适值函数，往往就是目标函数，以值得大小为依据
3 b4 w- j. n8 p) N# A+ L1 N
遗传运算，交叉和变异
V* \; [$ t/ z2 a# ?& m* w9 m7 G
选择策略，算出适应度，根据比例采用转盘模型
5 g" v. e- q5 _, P2 o4 ^
停止准则
. h+ D3 ], {' Y/ r7 }
) q% {" a# \- L; c9 n t
参考：https://blog.csdn.net/zuochao_2013/article/details/71435105
2 N6 }; W8 J1 j* m, m) Y% j2 w
% I3 S0 q) c2 ]: k! `. v! Z
四、神经网络算法
+ K, \5 `" ^+ f( o, r) [6 r. D9 B8 z
9 y2 \1 W. ^$ p* t- J
和机器学习模型中的神经网络一样，用来分类或预测
/ [7 G0 c0 {6 [4 f' ~. @
& l9 O. c! ^* [$ d5 v! q8 A
五、禁忌搜索算法 (Tabu Search)
+ U9 k. v+ C: ~! h9 ~4 D5 p
6 u- U" W A" c" K# }* m
又称爬山启发式算法，从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础，TS算法是在其上改进而来。
4 {+ i* k: {# b. X3 m( {: @3 J
优点：
# o, l: T6 G. S$ s* s& b4 I
1、容易理解，容易实现，具有较强的通用性；
( a+ J& g. \: m& F1 `
2、局部开发能力强，收敛速度很快。
2 T5 v! o% k, Q. P* J1 {
缺点：
) s; b9 p1 [) a! M0 F
1、全局开发能力弱，只能搜索到局部最优解；
# ?8 M! N8 Z' ~ {
2、搜索结果完全依赖于初始解和邻域的映射关系。
3 I: c* P0 v; x% a
8 I l+ m' _3 J! n! w
将不相同的n件物品分为m组，可以用的编码：
# k$ G3 ?4 f& J! H5 x
a、带分隔符的顺序编码，以自然数1~n分别代表n件物品如：1-3-4-0-2-6-7-5-0-8-9
; l" ?$ O- j4 b0 ~5 s
b、自然数编码，每一位分别代表一件物品，而每一位的值代表该物品所在的分组。如：1-2-1-1-2-2-2-3-3
9 k n: W( g: @% D n
(2)初始解的获取
' u' C' T+ `% w7 T" X: \3 l
可以随机给出初始解，也可以事先使用其他启发式等算法给出一个较好的初始解。
6 y1 U, K& L1 R5 a1 p1 }3 K
(3)移动邻域
2 V( V8 T! @3 {7 p
移动是从当前解产生新解的途径，例如上述问题中用移动s产生新解s(x)。
, \) H+ t2 I! s) [ I8 d8 }
从当前解可以进行的所有移动构成邻域，也可以理解为从当前解经过“一步”可以到达的区域。
+ O* B# b9 e2 V. l
(4)禁忌表
6 [% H% R7 B1 f2 C* O
禁忌表的作用：防止搜索出现循环
+ l. Y) A+ d9 ^; K+ }: s
(5)渴望水平函数
' t6 g3 B& F. @/ F6 X; @) w
A(x，s)一般为历史上曾经达到的最好目标值，若有C(s(x))
2 `! u: J- C. d6 P# U. b+ _
7 u& H& L! Z6 W) l. |
六、蚁群算法（AS）
6 }0 }8 C; H3 z: M- H$ B# j
% H4 U- Q4 f4 |' U
+ N/ r7 b. K8 h; b, V2 B6 c( b e# K6 K
参考：http://www.cnblogs.com/asxinyu/p/Path_Optimization_Tsp_Problem_Ant_System_CSharp.html#_labelTop
/ [- `) O8 @) e5 J% O( x
---------------------
$ `1 X" w- R8 u, u8 }
4 A1 F$ u1 U- e/ g: D! E0 k6 `7 v
) K2 y b1 Q5 g0 s7 x) T. l7 z, V
7 m) v, b+ ^: ] G! B* o. b) F
8 \( L% w8 N3 ~$ b' m
数学建模解题思路与方法.pptx
2019-4-18 15:55 上传
点击文件名下载附件
下载积分: 体力 -2 点
117.69 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
