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

数学建模竞赛中应该掌握的几种方法一、模拟退火算法1、定义及来源模拟退火算法(SimulatedAnnealing，SA)从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。2、原理模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。Metropolis准则：假设在状态oldx时，系统受到某种扰动而使其状态变为newx。与此相对应，系统的能量也从)(xoldE变成)(xnewE，系统由状态oldx变为状态newx的接受概率P：或3、流程1）随机产生一个初始解0x，令0xxbest，并计算目标函数值)(x0E；2）设置初始温度T(0)=T0，迭代次数i=1；3）DowhileT(i)minTa、forj=1-kb、对于当前最优解bestx按照某一邻域函数，产生一新的解newx。计算新的目标函数值）（newxE，并计算目标函数值的增量)(x-)(bestExEEnew。c、如果0E，则newbestxxd、如果0E，则E/T(i))(-expp；如果c=random[0,1]p,newbestxx，否则bestbestxxe、Endfori=i+1;Enddo输出当前最有点，计算结果。4、应用97年A题的模拟退火算法。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。二、遗传算法1、概念及来源遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法搜索是通过选择与染色体之间的交叉和变异来完成的。遗传算法主要使用选择算子、交叉算子与变异算子来模拟生物进化，从而产生一代又一代的种群X(t)。（1）选择算子：是模拟自然选择的操作，反映“优胜劣汰”原理。它根据每一个个体的适应度，按照一定规则或方法，从t代种群X(t)中选择出一些优良的个体（或作为母体，或让其遗传到下一代种群X(t+1)）。（2）交叉算子：是模拟有性繁殖的基因重组操作，它将从种群X(t)所选择的每一对母体，以一定的交叉概率交换它们之间的部分基因。（3）变异算子：是模拟基因突变的遗传操作，它对种群X(t)中的每一个个体，以一定的变异概率改变某一个或某一些基因座上的基因值为其他的等位基因。交叉算子与变异算子的作用都在于重组染色体基因，以生成新的个体。2、基本原理遗传算法把问题的解表示成“染色体”，在算法中也即是以二进制编码的串（string）。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。具体来说就是：长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：1．选择(Selection)这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differentialreproduction)。2．交叉(Crossover)这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。3．变异(Mutation)这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。3、运算过程步1（初始化）确定种群规模N，交叉概率Pc，变异概率Pm和终止进化准则；随机生成N个个体作为初始种群）（0X；置0t。步2（个体评价）计算评估）（0X中各个体的适应度。步3（种群进化）3.1.选择（母体）从）（0X中运用选择算子选择出M/2对母体(NM）。3.2.交叉对所选择的M/2对母体，以概率Pc执行交叉，形成M个中间个体。3.3.变异对M个中间个体分别独立以概率Pm执行变异，形成M个候选个体。3.4.选择（子代）从上述所形成的M个候选个体中依据适应度选择出N个个体组成新一代种群)1t(X。步4（终止检验）如已满足终止准则，则输出)1t(X中具有最大适应度的个体作为最优解，终止计算，否则置1tt并转步2。以上运算过程只是遗传算法的多种实现方式中的一种，根据实际问题的不同，遗传算法的实现也是多种多样的。4、例子求sin(x)在0到3.14之间的最大值.Step1：编写目标函数sin1.mfunction[sol,val]=sin1(sol,options)x=sol(1);val=sin(x);step2:生成初始种群，大小为10initPop=initializega(10,[0,3.14],'sin1',[],[1e-6,1]);step3:25次遗传迭代[x,endPop,bpop,trace]=ga([03.14],'sin1',[],initPop,...[1e-611],'maxGenTerm',25,...'normGeomSelect',[0.08],...['arithXover'],[2],...'nonUnifMutation',[2,25,3])三、蒙特卡洛算法1、概念及来源蒙特卡洛算法是一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。即概率是他的基础。蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。可以把蒙特卡罗解题归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。2、原理设x1,x2,x3,…,xN是独立同分布的随机变量序列，且有有限的数据期望E（x）和方差2，设x为x1,x2,…,xN的算术平方根，当N时x按概率为1收敛于E（x）,用数学公式可表示为：对于任意0,limP1|(x)-xN1|N1iiE蒙特卡洛方法的收敛于平常所说的收敛不同，它是概率意义上的收敛。3、算法实例：（粒子运输）问题描述：在数值积分法中，利用求单位圆的1/4的面积来求得Pi/4从而得到Pi。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。怎样求出扇形面积在正方形面积中占的比例K呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。P落在扇形内的充要条件是x^2+y^2=1。程序描述：matlab利用蒙特卡洛算法近似求圆周率PIfunctiony=metekaro(nums)%蒙特卡罗算法的简单模拟，输入nums对绝对值x,y都小于1的数(x,y)，通过落在圆内的点数来求pi%产生nums对坐标数据(x,y)D=unifrnd(-1,1,nums,2);%落在圆中的点数inCircle=0;%获取行数,也即nums的值rows=size(D,1);%对每一对数据进行检测fori=1:rows%如果落在圆内，圆内的点数+1，落在正方形内的点数就为nums的数值if(D(i,1)^2+D(i,2)^2)1inCircle=inCircle+1;endend%圆的面积/正方形的面积=圆内的点数/正方形内的点数y=4*inCircle/rows;%输出pi值disp(['pi的近似值为：'num2str(y)])计算结果：metekaro(1000);pi的近似值为：3.088metekaro(100000);pi的近似值为：3.1409metekaro(10000000);pi的近似值为：3.1413python利用蒙特卡洛算法近似求圆周率PIimportrandomimporttimerandom.seed()nums=100000i=range(1,nums)s=0printnumsprinttime.strftime('Str:%Y-%m-%d%H:%M:%S',time.localtime(time.time()))forxini:a1=random.random()a2=random.random()if(a1*a1+a2*a2)1:s=s+1print1.0*s/nums*4printtime.strftime('End:%Y-%m-%d%H:%M:%S',time.localtime(time.time()))运行结果：3.14248