数学建模竞赛中应该掌握的几种方法

《数学建模竞赛中应该掌握的几种方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学建模竞赛中应该掌握的几种方法一、模拟退火算法1、定义及来源模拟退火算法(SimulatedAnnealing，SA)从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。2、原理模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐

2、趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由

3、冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。Metropolis准则：假设在状态时，系统受到某种扰动而使其状态变为。与此相对应，系统的能量也从变成，系统由状态变为状态的接受概率P：或3、流程1）随机产生一个初始解，令，并计算目标函数值；2）设置初始温度T(0)=T0，迭代次数i=1；3）DowhileT(i)>a、forj=1-kb、对于当前最优解按照某一邻域函数，产生一新的解。计算新的目标函数值，并计算目标函数值的增量。c、如果，则d、如果，则；如果c=

4、random[0,1]

5、更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法搜索是通过选择与染色体之间的交叉和变异来完成的。遗传算法主要使用选择算子、交叉算子与变异算子来模拟生物进化，从而产生一代又一代的种群X(t)。（1）选择算子：是模拟自然选择的操作，反映“优胜劣汰”原理。它根据每一个个体的适应度，按照一定规则或方法，从t代种群X(t)中选择出一些优良的个体（或作为母体，或让其遗传到下一代种群X(t+1)）。（2）交叉算子：是模拟有性繁殖的基因重组操作，它将从种群X(t)所选择的每一对

6、母体，以一定的交叉概率交换它们之间的部分基因。（3）变异算子：是模拟基因突变的遗传操作，它对种群X(t)中的每一个个体，以一定的变异概率改变某一个或某一些基因座上的基因值为其他的等位基因。交叉算子与变异算子的作用都在于重组染色体基因，以生成新的个体。1、基本原理遗传算法把问题的解表示成“染色体”，在算法中也即是以二进制编码的串（string）。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环

7、境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。具体来说就是：长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种： 1．选择(Selection) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为

8、非均匀再生(differentialreproduction)。 2．交叉(Crossover) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。 3．变异(Mutation