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

数学建模竞赛中应该掌握的几种方法一、 模拟退火算法1、 定义及来源模拟退火算法(Simulated Annealing，SA)从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。2、原理模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。Metropolis准则：假设在状态时，系统受到某种扰动而使其状态变为。与此相对应，系统的能量也从变成，系统由状态变为状态的接受概率P：或3、流程1） 随机产生一个初始解，令，并计算目标函数值；2） 设置初始温度T(0)=T0，迭代次数i=1；3） Do while T(i)a、 for j=1-kb、 对于当前最优解按照某一邻域函数，产生一新的解。计算新的目标函数值，并计算目标函数值的增量。c、 如果，则d、 如果，则；如果c=random0,10, limP蒙特卡洛方法的收敛于平常所说的收敛不同，它是概率意义上的收敛。3、算法实例：（粒子运输）问题描述：在数值积分法中，利用求单位圆的1/4的面积来求得Pi/4从而得到Pi。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。怎样求出扇形面积在正方形面积中占的比例K呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。P落在扇形内的充要条件是x2+y2=1。程序描述：matlab 利用蒙特卡洛算法近似求圆周率PI function y = 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); % 对每一对数据进行检测 for i = 1:rows % 如果落在圆内，圆内的点数+1，落在正方形内的点数就为nums的数值 if (D(i,1)2 + D(i,2)2) metekaro(1000); pi的近似值为：3.088 metekaro(100000); pi的近似值为：3.1409 metekaro(10000000); pi的近似值为：3.1413 python 利用蒙特卡洛算法近似求圆周率PI import random import time random.seed() nums=100000 i=range(1,nums) s=0 print nums print time.strftime(Str:%Y-%m-%d %H:%M:%S,time.localtime(time.time() for x in i: a1=random.random() a2=random.random() if (a1*a1+a2*a2)1: s=s+1 print 1