数学建模：优化算法

杨利霞

数学建模：优化算法
数学建模问题总共分为四类：
1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题
6 E. E0 v8 x. E9 R1 {- u% C
4 t$ ]- l0 k) u+ U% C) j一、粒子群算法（PSO）

算法对于Hepper的模拟鸟群(鱼群)的模型进行修正，同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。
/ f: e: }" K! G2 zPSO的优势在于简单，容易实现，无需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。

) U* `3 r* F3 c1 o4 e8 z2 V基本PSO算法
7 h5 {$ @* x6 V3 {( T, i) f
D维空间中，有m个粒子；
粒子i位置：xi=(xi1,xi2,…xiD)
粒子i速度：vi=(vi1,vi2,…viD)，1≤i≤m,1 ≤d ≤D
粒子i经历过的历史最好位置：pi=(pi1,pi2,…piD)
: h, A2 d' D; [3 g8 A群体内（或领域内）所有粒子所经历过的最好位置： pg =(pg1,pg2,…pgD)
9 O- b9 C2 @& H
# a4 ^5 w; c! O. Y
+ r+ }: m% P& k$ ?二、模拟退火算法（SA）
% ^2 e1 f( l! I, X4 a# s
模拟退火过程：
1 M# O4 ^% b) ^: O* I  \# v4 a; d/ z设定初始高温，相当于物理退火的加温过程。初始温度要足够高，在实际应用中，要根据以往的经验，通过反复实验来确定T0的值。
热平衡达到，相当于物理退火的等温过程。是指在一个给定温度下，SA用特殊的抽样策略进行随机搜索，最终达到平衡状态的过程。这是SA算法的内循环过程。
5 r. M4 G$ }: q- ~% E降温函数，相当于物理退火的冷却过程。用来控制温度的下降方式，这是SA算法的外循环过程。常用的降温函数有Tk+1=Tk-DT，Tk+1=Tk*r，其中r∈(0.95,0.99)。

5 A% P7 K0 d7 E- r三、遗传算法

产生一个初始种群
根据问题的目标函数构造适值函数
根据适应值的好坏不断选择和繁殖
0 p5 _3 S2 M4 L1 ~7 S0 u若干代后得到适应值最好的个体即为最优解
; z1 z, B$ v0 d7 @' v. F$ j, A7 w
四、算法步骤
: s. j# l# [9 M3 E) s! A* x3 ?初始种群
编码方法—二进制编码，可以对多个编码进行组合。
7 H' a; c4 d1 E. |5 E1 _适值函数，往往就是目标函数，以值得大小为依据
遗传运算，交叉和变异
  F" g7 i, q  j选择策略，算出适应度，根据比例采用转盘模型
: D" R; D6 L1 ~4 _停止准则

. b/ _/ Z- Y; ^1 p. h8 Z6 Z参考：https://blog.csdn.net/zuochao_2013/article/details/71435105

四、神经网络算法

/ q, ^* h3 n- [3 v) B& g和机器学习模型中的神经网络一样，用来分类或预测

( l- l0 W; M, X5 I- l+ u6 k五、禁忌搜索算法 (Tabu Search)
9 N/ L' p9 y- \& `6 `2 f0 x
又称爬山启发式算法，从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础，TS算法是在其上改进而来。
7 m" y! i# x6 z* m3 ^0 ]* t优点：
1、容易理解，容易实现，具有较强的通用性；
2、局部开发能力强，收敛速度很快。
缺点：
1、全局开发能力弱，只能搜索到局部最优解；
7 Q" \, i9 |& L! I. J2、搜索结果完全依赖于初始解和邻域的映射关系。
. w7 B. U; J6 X0 M! x4 C
" Y3 ?5 h) q  |3 A/ I将不相同的n件物品分为m组，可以用的编码：
; Q+ f# M; \* o9 i( ?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
(2)初始解的获取
可以随机给出初始解，也可以事先使用其他启发式等算法给出一个较好的初始解。
(3)移动邻域
! {$ [0 L& q) r' I; z4 N移动是从当前解产生新解的途径，例如上述问题中用移动s产生新解s(x)。
. r; @7 X6 e4 L# z, \# p2 B从当前解可以进行的所有移动构成邻域，也可以理解为从当前解经过“一步”可以到达的区域。
(4)禁忌表
' N& P! N$ |) v  V7 }禁忌表的作用：防止搜索出现循环
(5)渴望水平函数
A(x，s)一般为历史上曾经达到的最好目标值，若有C(s(x))

0 d6 ^( I2 q/ Y; W六、蚁群算法（AS）
6 A* O% a. d* ^! ~5 ~
' R1 o% R8 M1 h; g% ?; e0 ~( I
- R/ T: s' O* ?$ Y! h/ @参考：http://www.cnblogs.com/asxinyu/p/Path_Optimization_Tsp_Problem_Ant_System_CSharp.html#_labelTop
4 u( }  T) n; A2 a---------------------
# w( c7 v* @" u
9 J( c+ X% b' E
- \( N. T6 O- I, w' ^
8 Y' s0 L2 r$ X2 r; o, W