数学建模比赛，尤其是像国赛和美赛这类国家级数模比赛无论是对本科生还是研究生来说都是现阶段非常重要的。在这些比赛中取得好成绩，不仅有助于保研、有助于找工作，更重要的是形成科学的思维模式。今天老哥专门给同学们准备了数模比赛最优化理论的三大经典算法，希望对同学们有所帮助。
1
模拟退火算法
模拟退火算法包含两个部分即Metropolis算法和退火过程,，分别对应内循环和外循环。外循环就是退火过程，将固体达到较高的温度（初始温度T（0）），然后按照降温系数alpha使温度按照一定的比例下降，当达到终止温度Tf时，冷却结束，即退火过程结束。
Metropolis算法是内循环，即在每次温度下，迭代L次，寻找在该温度下能量的最小值（即最优解）。下图中所示即为在一次温度下，跌代L次，固体能量发生的变化。在该温度下，整个迭代过程中温度不发生变化，能量发生变化，当前一个状态x(n)的能量大于后一个状态x(n+1)的能量时，状态x(n)的解没有状态x(n+1)的解好，所以接受状态x(n+1)。但是如果下一状态的能量比前一个状态的能量高时，该不该接受下一状态呢？在这里设置一个接受概率P,即如果下一状态的能量比前一个状态的能量高，则接受下一状态的概率为P。
Metropolis算法就是如何在局部最优解的情况下让其跳出来（如图中B、C、E为局部最优），是退火的基础。1953年Metropolis提出重要性采样方法，即以概率来接受新状态，而不是使用完全确定的规则，称为Metropolis准则，计算量较低。
假设开始状态在A，多次迭代之后更新到B的局部最优解，这时发现更新到B时，能力比A要低，则说明接近最优解了，因此百分百转移，状态到达B后，发现下一步能量上升了，如果是梯度下降则是不允许继续向前的，而这里会以一定的概率跳出这个坑，这各概率和当前的状态、能量等都有关系。所以说这个概率的设计是很重要的，下面从数学方面进行解释。
假设前一个状态为x(n),系统根据某一指标（梯度下降，上节的能量），状态变为x(n+1),相应的，系统的能量由E(n)变为E(n+1),定义系统由x(n)变为x(n+1)的接受概率P为：
从上式我们可以看到，如果能量减小了，那么这种转移就被接受（概率为1），如果能量增大了，就说明系统偏离全局最优值位置更远了，此时算法不会立刻将其抛弃，而是进行概率操作：首先在区间【0,1】产生一个均匀分布的随机数ϵ \epsilonϵ，如果ϵ \epsilonϵ，则此种转移接受，否则拒绝转移，进入下一步，往复循环。其中p以能量的变化量和t进行决定概率p的大小，所以这个值是动态的。
用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件Tf。而温度的作用就是来计算转移概率P的。当温度每次下降后，转移概率也发生变化，因此在所有温度下迭代L次的结果也都是不相同的。在每个温度下迭代L次来寻找当前温度下的最优解，然后降低温度继续寻找，直到到达终止温度，即转移概率P接近于0.
2
神经网络
人工神经网络是具有适应性的简单神经元组成的广泛并互连的网络，它的组织能够模拟生物神经系统对真实世界物体作出的交互式反应。人工神经网络具有自学习、自组织、较好的容错性和优良的非线性逼近能力。
人工神经网络能干什么？
1、拟合数据——>预测
2、分类——>聚类分析
那么我们学习人工神经网络需要知道哪些呢？
1、神经元模型
2、激活函数
3、网络结构
4、工作状态
5、学习方式
人工神经元模型
作为神经网络的基本元素，神经元的模型如下：
是从其他神经元上传来的信号，表示从神经元 到神经元的连接权值，表示一个阈值，或者称为偏置。神经元输入与输出的关系为：
激活函数
激活函数是对净激活量与输出进行映射的函数。一些常用的激活函数，由于输入数据与期望之间可能并不是量级一样，所以需要激活，激活函数：
一些常用的激活函数有：
线性函数：
S型函数：
阈值函数：
双极S型函数：
网络结构
根据网络中神经元的互连方式，可以分为3种神经网络:
1、前馈神经网络：在训练的过程中会有反馈信号，而在分类的过程中只能向前传递数据，直到到达输出层，层间没有向后反馈信号
2、反馈神经网络：从输入到输出具有反馈连接的神经元
3、自组织网络：通过自动寻找样本中的内在规律和本质属性，自组织、自适应地改变网络参数与结构
工作状态
1、学习：利用学习算法来调整神经元之间的连接权值，使得网络输出更符合实际
2、工作：神经元的连接权值不变，可作为分类器或者预测数据时使用
学习方式
1、有导师学习：将一组训练集送入网络，根据网络的实际输出与期望输出间的差别来调整连接权，如BP算法（本文的代码实现也为BP神经网络的算法实现）
2、无导师学习：抽取样本集合中蕴含的统计特性，并以神经元之间的连接权的形式存在于网络中，如（Hebb学习率）
3
遗传算法
遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。
基本遗传算法的框图：
所以，遗传算法基本步骤是：
1） 初始化 t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体 P（t）；
2） 个体评价 计算P（t）中各个个体的适应度值；
3） 选择运算 将选择算子作用于群体；
4） 交叉运算 将交叉算子作用于群体；
5） 变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体P（t + 1）;
6） 终止条件判断 t≦T：t← t+1 转到步骤2；
t>T：终止 输出解。
基本遗传算法的组成
（1）编码（产生初始种群）
（2）适应度函数
（3）遗传算子（选择、交叉、变异）
（4）运行参数
转自：科研交流
如有侵权，请联系本站删除！
