数学建模：优化算法

杨利霞

数学建模：优化算法
数学建模问题总共分为四类：
+ {( P- h/ d3 @9 T5 h  p+ ?" q1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题
( ?8 v/ i. p" S+ w# @, o! V
  N: n8 }9 Y/ f- w一、粒子群算法（PSO）
% Z  h+ U/ Q5 R
+ T, {) z4 M* B7 m  l算法对于Hepper的模拟鸟群(鱼群)的模型进行修正，同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。
# w: d' m4 a& APSO的优势在于简单，容易实现，无需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。

基本PSO算法

D维空间中，有m个粒子；
粒子i位置：xi=(xi1,xi2,…xiD)
粒子i速度：vi=(vi1,vi2,…viD)，1≤i≤m,1 ≤d ≤D
% d! e( D3 S% ?粒子i经历过的历史最好位置：pi=(pi1,pi2,…piD)
& d7 c% ^5 H3 r. L  V/ p群体内（或领域内）所有粒子所经历过的最好位置： pg =(pg1,pg2,…pgD)


二、模拟退火算法（SA）

9 x' _$ l2 d' A$ W5 v% y8 N& O模拟退火过程：
  Y$ k" K* [& Y; g% C2 ^5 r设定初始高温，相当于物理退火的加温过程。初始温度要足够高，在实际应用中，要根据以往的经验，通过反复实验来确定T0的值。
热平衡达到，相当于物理退火的等温过程。是指在一个给定温度下，SA用特殊的抽样策略进行随机搜索，最终达到平衡状态的过程。这是SA算法的内循环过程。
9 x. n% G* J$ Y/ i. q6 N降温函数，相当于物理退火的冷却过程。用来控制温度的下降方式，这是SA算法的外循环过程。常用的降温函数有Tk+1=Tk-DT，Tk+1=Tk*r，其中r∈(0.95,0.99)。
/ b6 T4 Y' c3 I5 e/ v; r
" \  x7 _: D1 ?  K9 Y: s5 }( A9 d三、遗传算法

产生一个初始种群
0 L3 a2 n+ d! w1 _( |根据问题的目标函数构造适值函数
& j6 q9 Y) d- c( ?, q, H  a根据适应值的好坏不断选择和繁殖
若干代后得到适应值最好的个体即为最优解

四、算法步骤
2 r8 i2 n( [" b7 Y7 y( D8 c初始种群
6 `( n; e7 h  j编码方法—二进制编码，可以对多个编码进行组合。
适值函数，往往就是目标函数，以值得大小为依据
遗传运算，交叉和变异
$ E8 _; z( ^. g( G; J% X5 ]选择策略，算出适应度，根据比例采用转盘模型
停止准则
2 @% f% v' a) C- h
; Q( X$ Q7 e% B9 r1 v: _4 R9 p参考：https://blog.csdn.net/zuochao_2013/article/details/71435105

9 L, U& L4 Q, u四、神经网络算法

和机器学习模型中的神经网络一样，用来分类或预测
& |5 l- Z; Q8 i; O4 `# {4 ~
五、禁忌搜索算法 (Tabu Search)
( N( w0 c" g. W
3 G; H8 \2 x9 z. P% n4 p又称爬山启发式算法，从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础，TS算法是在其上改进而来。
优点：
1、容易理解，容易实现，具有较强的通用性；
2、局部开发能力强，收敛速度很快。
缺点：
) z3 {; ?' e4 D" o7 a1、全局开发能力弱，只能搜索到局部最优解；
/ D6 B7 g4 t5 C0 H6 }; R/ m+ H2、搜索结果完全依赖于初始解和邻域的映射关系。

将不相同的n件物品分为m组，可以用的编码：
a、带分隔符的顺序编码，以自然数1~n分别代表n件物品如：1-3-4-0-2-6-7-5-0-8-9
b、自然数编码，每一位分别代表一件物品，而每一位的值代表该物品所在的分组。如：1-2-1-1-2-2-2-3-3
, Y- o. Z& T' i  [, _+ `$ w(2)初始解的获取
可以随机给出初始解，也可以事先使用其他启发式等算法给出一个较好的初始解。
! @; f6 t  T; C(3)移动邻域
移动是从当前解产生新解的途径，例如上述问题中用移动s产生新解s(x)。
从当前解可以进行的所有移动构成邻域，也可以理解为从当前解经过“一步”可以到达的区域。
(4)禁忌表
& [0 d, I) U+ p$ I6 c# K* [禁忌表的作用：防止搜索出现循环
(5)渴望水平函数
A(x，s)一般为历史上曾经达到的最好目标值，若有C(s(x))
8 [0 |4 u! _* w: J$ q
; M1 w6 u9 b1 X& c六、蚁群算法（AS）
1 _6 e" b* x0 v6 p5 A
* E6 e! K6 p* H  K* A0 V& k
9 O" T7 |) R- V7 ^参考：http://www.cnblogs.com/asxinyu/p/Path_Optimization_Tsp_Problem_Ant_System_CSharp.html#_labelTop
8 x( E% p) r2 @# X# m2 K1 r8 ~9 d---------------------
作者：_朝闻道_
1 e7 x' |% Y0 U) |; D. E来源：CSDN
) g, N1 o" I3 w5 P- o
/ N2 c# L; {' l0 B1 `, }1 p. o& d

" L( E* I# k0 u; X9 T, b
3 l. h) q/ s3 ]; ~0 R& o/ G