数学建模：优化算法

数学建模：优化算法

优化算法

数学建模问题总共分为四类：1.分类问题2.优化问题3.评价问题4.预测问题⼀、粒⼦群算法（PSO）

算法对于Hepper的模拟鸟群(鱼群)的模型进⾏修正，同遗传算法类似，也是⼀种基于群体叠代的，但并没有遗传算法⽤的交叉以及变异，⽽是粒⼦在解空间追随最优的粒⼦进⾏搜索。PSO的优势在于简单，容易实现，⽆需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时⼜有深刻的智能背景，既适合科学研究，⼜特别适合⼯程应⽤。

基本PSO算法

D维空间中，有m个粒⼦；粒⼦i位置：xi=(xi1,xi2,…xiD)粒⼦i速度：vi=(vi1,vi2,…viD)，1≤i≤m,1≤d≤D粒⼦i经历过的历史最好位置：pi=(pi1,pi2,…piD)群体内（或领域内）所有粒⼦所经历过的最好位置：pg=(pg1,pg2,…pgD)

⼆、模拟退⽕算法（SA）

模拟退⽕过程：设定初始⾼温，相当于物理退⽕的加温过程。初始温度要⾜够⾼，在实际应⽤中，要根据以往的经验，通过反复实验来确定T0的值。热平衡达到，相当于物理退⽕的等温过程。是指在⼀个给定温度下，SA⽤特殊的抽样策略进⾏随机搜索，最终达到平衡状态的过程。这是SA算法的内循环过程。降温函数，相当于物理退⽕的冷却过程。⽤来控制温度的下降⽅式，这是SA算法的外循环过程。常⽤的降温函数有Tk+1=Tk-DT，Tk+1=Tk*r，其中r∈(0.95,0.99)。三、遗传算法

产⽣⼀个初始种群根据问题的⽬标函数构造适值函数根据适应值的好坏不断选择和繁殖若⼲代后得到适应值最好的个体即为最优解

四、算法步骤初始种群编码⽅法—⼆进制编码，可以对多个编码进⾏组合。适值函数，往往就是⽬标函数，以值得⼤⼩为依据遗传运算，交叉和变异选择策略，算出适应度，根据⽐例采⽤转盘模型停⽌准则

参考：四、神经⽹络算法

和机器学习模型中的神经⽹络⼀样，⽤来分类或预测五、禁忌搜索算(TabuSearch)

⼜称爬⼭启发式算法，从当前的节点开始，和周围的邻居节点的值进⾏⽐较。如果当前节点是最⼤的，那么返回当前节点，作为最⼤值(即⼭峰最⾼点)；反之就⽤最⾼的邻居节点替换当前节点，从⽽实现向⼭峰的⾼处攀爬的⽬的。它是禁忌搜索的基础，TS算法是在其上改进⽽来。优点：1、容易理解，容易实现，具有较强的通⽤性；2、局部开发能⼒强，收敛速度很快。缺点：1、全局开发能⼒弱，只能搜索到局部最优解；2、搜索结果完全依赖于初始解和邻域的映射关系。

将不相同的n件物品分为m组，可以⽤的编码：a、带分隔符的顺序编码，以⾃然数1~n分别代表n件物品如：1-3-4-0-2-6-7-5-0-8-9b、⾃然数编码，每⼀位分别代表⼀件物品，⽽每⼀位的值代表该物品所在的分组。如：1-2-1-1-2-2-2-3-3(2)初始解的获取可以随机给出初始解，也可以事先使⽤其他启发式等算法给出⼀个较好的初始解。(3)移动邻域移动是从当前解产⽣新解的途径，例如上述问题中⽤移动s产⽣新解s(x)。从当前解可以进⾏的所有移动构成邻域，也可以理解为从当前解经过“⼀步”可以到达的区域。(4)禁忌表禁忌表