数学数学建模竞赛算法讲座课件

数学建模竞赛数学建模竞赛常用方法常用方法哈尔滨工业大学数学系哈尔滨工业大学数学系王希连王希连 前言前言 在数学建模竞赛的评卷过程中在数学建模竞赛的评卷过程中,首重摘要首重摘要,其次是所建立的数学模型的创新性和正确其次是所建立的数学模型的创新性和正确性性,第三要看求解计算结果的应用结果第三要看求解计算结果的应用结果(是否是否能够完全回答题目的问题能够完全回答题目的问题)及强健性及强健性(结果的结果的主要优缺点和结果的敏感性分析等主要优缺点和结果的敏感性分析等),第四看第四看文章的整体结构和格式表述的规范性文章的整体结构和格式表述的规范性,简洁简洁性性,最后再考评算法的实用性和正确性最后再考评算法的实用性和正确性(只有只有竞争力较强的文章算法才可能被评委审评竞争力较强的文章算法才可能被评委审评),因此一定不要本末倒置因此一定不要本末倒置.一篇一篇mcm官方正式出版的对一份官方正式出版的对一份Outstanding论文评审文章中节录的关于评审过程的一段论文评审文章中节录的关于评审过程的一段:广义来看广义来看,算法是指求解一个问题的高效方法算法是指求解一个问题的高效方法,如等比数如等比数列的求和方法列的求和方法,一元二次方程的求解方法一元二次方程的求解方法,求一元函数零求一元函数零点的牛顿迭代法点的牛顿迭代法,信号频谱分析中的快速傅立叶变换法信号频谱分析中的快速傅立叶变换法,常微分方程求解的龙格常微分方程求解的龙格-库塔法等等库塔法等等,目前特指所有利用目前特指所有利用计算机程序求解问题的各种有效算法计算机程序求解问题的各种有效算法 在数学建模中在数学建模中,针对各种各样的问题针对各种各样的问题,人们已经建立了各人们已经建立了各种算法种算法,特别是很多问题的优秀算法都已经商业化了成熟特别是很多问题的优秀算法都已经商业化了成熟的软件包的软件包,使用者只要根据相应软件的语法要求正确地描使用者只要根据相应软件的语法要求正确地描述问题述问题,然后运行程序即可得到结果然后运行程序即可得到结果,而不需要关心算法的而不需要关心算法的具体原理和数据结构的组织安排和计算精度及收敛性的具体原理和数据结构的组织安排和计算精度及收敛性的控制等控制等,如数据的统计分析、相关分析、回归分析、聚类如数据的统计分析、相关分析、回归分析、聚类分析、数据简化、生存分析、时间序列分析、多重响应分析、数据简化、生存分析、时间序列分析、多重响应等数据处理和挖掘工作可以用等数据处理和挖掘工作可以用SAS或或SPSS软件进行求软件进行求解分析解分析;曲线拟合与插值曲线拟合与插值,常微分方程和偏微分方程的求常微分方程和偏微分方程的求解等数值求解问题可以使用解等数值求解问题可以使用Matlab完成完成,线性规划、非线性规划、非线性规划、整数规划问题可以用线性规划、整数规划问题可以用lingo软件求解等软件求解等 算法概述算法概述蒙特卡洛蒙特卡洛(Monte-Carlo)(Monte-Carlo)算法算法 蒙特卡罗方法又称随机抽样技巧或统蒙特卡罗方法又称随机抽样技巧或统计试验方法，与一般数值计算方法有计试验方法，与一般数值计算方法有很大区别。它是以概率统计理论为基很大区别。它是以概率统计理论为基础的一种方法。础的一种方法。当所求问题的解是某个事件的概率，当所求问题的解是某个事件的概率，或者是某个随机变量的数或者是某个随机变量的数学期望，或学期望，或者是与之有关的量时，通过某种试验者是与之有关的量时，通过某种试验的方法，得出该事件发生的频率，再的方法，得出该事件发生的频率，再通过它得到问题的解。这就是蒙特卡通过它得到问题的解。这就是蒙特卡罗方法的基本思想。罗方法的基本思想。基本示例基本示例:圆周率圆周率的计算的计算 蒙特卡罗投点法蒙特卡罗投点法(蒲丰投针实验蒲丰投针实验的推广的推广)：在一个边长为在一个边长为a的正方形内随机投点，的正方形内随机投点，该点落在此正方形的内切圆中的概率该点落在此正方形的内切圆中的概率应为该内切圆与正方形的面积比值，应为该内切圆与正方形的面积比值，即即n=10000;a=2;m=0;for i=1:n x=rand(1)*a;y=rand(1)*a;if(x-a/2)2+(y-a/2)2=(a/2)2)m=m+1;endenddisp(投点法近似计算的投点法近似计算的为为:,num2str(4*m/n);o(a/2,a/2)蒙特卡罗方法的关键步骤在于随机数的产生，计算机产蒙特卡罗方法的关键步骤在于随机数的产生，计算机产生的随机数都不是真正的随机数生的随机数都不是真正的随机数(由算法确定的缘故由算法确定的缘故)，如果伪随机数能够通过一系列统计检验，我们也可以将如果伪随机数能够通过一系列统计检验，我们也可以将其当作真正的随机数使用。其当作真正的随机数使用。rand(state,sum(100*clock)*rand);rand(1)%重新启动重新启动matlab时，输出的随机数不一样时，输出的随机数不一样 常用常用Matlab随机数生成方法随机数生成方法:1rand()生成（生成（0,1）区间上均匀分布的随机变量。基本语法：）区间上均匀分布的随机变量。基本语法：rand(M,N,P.)生成排列成生成排列成M*N*P.多维向量的随机数。如果只写多维向量的随机数。如果只写M，则生成则生成M*M矩阵；如果参数为矩阵；如果参数为M,N可以省略掉方括号可以省略掉方括号 2randn()生成服从标准正态分布（均值为生成服从标准正态分布（均值为0，方差为，方差为1）的随机数。）的随机数。基本语法和基本语法和rand()类似。类似。randn(M,N,P.)生成排列成生成排列成M*N*P.多维向量的随机数。如果只写多维向量的随机数。如果只写M，则生成则生成M*M矩阵；如果参数为矩阵；如果参数为M,N可以省略掉方括号可以省略掉方括号 3unifrnd()和和rand()类似，这个函数生成某个区间内均匀分布的随类似，这个函数生成某个区间内均匀分布的随机数。基本语法机数。基本语法 unifrnd(a,b,M,N,P,.)4normrnd()和和randn()类似，此函数生成指定均值、标准差的正态类似，此函数生成指定均值、标准差的正态分布的随机数。基本语法分布的随机数。基本语法normrnd(mu,sigma,M,N,P,.)生成的随机数服从均值为生成的随机数服从均值为mu，标准差为，标准差为sigma（注意（注意标准差是正数）正态分布，标准差是正数）正态分布，5chi2rnd()此函数生成服从卡方（此函数生成服从卡方（Chi-square)分布的随机数。卡分布的随机数。卡方分布只有一个参数：自由度方分布只有一个参数：自由度v。基本语法。基本语法chi2rnd(v,M,N,P,.)生成的随机数服从自由度为生成的随机数服从自由度为v的卡方分布，这些随机数的卡方分布，这些随机数排列成排列成M*N*P.多维向量多维向量6frnd()此函数生成服从此函数生成服从F分布的随机数。分布的随机数。F分布有分布有2个参数：个参数：v1,v2。基本语法。基本语法 frnd(v1,v2,M,N,P,.)生成的随机数服从参数为生成的随机数服从参数为(v1,v2)的卡方分布的卡方分布7trnd()此函数生成服从此函数生成服从t(Students t Distribution，这里是，这里是Cosset.W.S.的笔名的笔名)分布的随机数。分布的随机数。t分布有分布有1个参数：个参数：自由度自由度v。基本语法。基本语法trnd(v,M,N,P,.)生成的随机数服从参数为生成的随机数服从参数为v的的t分布分布8betarnd()此函数生成服从此函数生成服从Beta分布的随机数。分布的随机数。Beta分布有两个分布有两个参数分别是参数分别是A和和B。生成。生成beta分布随机数的语法是：分布随机数的语法是：betarnd(A,B,M,N,P,.)9exprnd()此函数生成服从指数分布的随机数。指数分布只有一此函数生成服从指数分布的随机数。指数分布只有一个参数个参数:mu,生成指数分布随机数的语法是：生成指数分布随机数的语法是：betarnd(mu,M,N,P,.)10gamrnd()生成服从生成服从Gamma分布的随机数。分布的随机数。Gamma分布有两个分布有两个参数：参数：A和和B。生成生成Gamma分布随机数的语法是：分布随机数的语法是：gamrnd(A,B,M,N,P,.)11lognrnd()生成服从对数正态分布的随机数。其有两个参数：生成服从对数正态分布的随机数。其有两个参数：mu和和sigma，服从这个这样的随机数取对数后就，服从这个这样的随机数取对数后就服从均值为服从均值为mu，标准差为，标准差为sigma的正态分布。的正态分布。lognrnd(mu,sigma,M,N,P,.)12raylrnd()生成服从瑞利（生成服从瑞利（Rayleigh）分布的随机数。其分）分布的随机数。其分布有布有1个参数：个参数：B。raylrnd(B,M,N,P,.)13wblrnd()生成服从威布尔（生成服从威布尔（Weibull）分布的随机数。其分）分布的随机数。其分布有布有2个参数：个参数：scale 参数参数 A和和shape 参数参数 B。wblrnd(A,B,M,N,P,.)14unidrnd()生成服从离散均匀分布的随机数。生成服从离散均匀分布的随机数。Unifrnd是在某个区是在某个区间内均匀选取实数（可为小数或整数），间内均匀选取实数（可为小数或整数），Unidrnd是是均匀选取整数随机数。离散均匀分布随机数有均匀选取整数随机数。离散均匀分布随机数有1个参数：个参数：n,表示从表示从1,2,3,.N这这n个整数中以相同的概率抽样。个整数中以相同的概率抽样。基本语法：基本语法：unidrnd(n,M,N,P,.)15.binornd()生成服从二项分布的随机数。二项分布有生成服从二项分布的随机数。二项分布有2个参数：个参数：n,p。考虑一个打靶的例子，每枪命中率为。考虑一个打靶的例子，每枪命中率为p，共射击，共射击N枪，那么一共击中的次数就服从参数为（枪，那么一共击中的次数就服从参数为（N,p）的二）的二项分布。注意项分布。注意p要小于等于要小于等于1且非负，且非负，N要为整数。基要为整数。基本语法：本语法：binornd(n,p,M,N,P,.)16.geornd()生成服从几何分布的随机数。几何分布的参数只有生成服从几何分布的随机数。几何分布的参数只有一个：一个：p。几何分布的现实意义可以解释为，打靶命。几何分布的现实意义可以解释为，打靶命中率为中率为p，不断地打靶，直到第一次命中目标时没有，不断地打靶，直到第一次命中目标时没有击中次数之和。注意击中次数之和。注意p是概率，所以要小于等于是概率，所以要小于等于1且且非负。非负。基本语法：基本语法：geornd(p,M,N,P,.)17poissrnd()生成服从泊松生成服从泊松(Poisson)分布的随机数。泊松分布的分布的随机数。泊松分布的参数只有一个：参数只有一个：lambda。此参数要大于零。此参数要大于零。基本语法：基本语法：poissrnd(lambda,M,N,P,.)附附:概率分布函数概率分布函数(Probability Distribution Function)直方图绘制语句直方图绘制语句:hist例例1 1 掷掷两两枚枚不不均均匀匀硬硬币币，每每枚枚正正面面出出现现概概率率为为批批p p，记记录录前前mmmm次次掷掷硬硬币币试试验验中中两两枚枚都都为为正正面面频率的波动情况，并画图。频率的波动情况，并画图。function test1(p,mm)pro=zeros(1,mm);randnum=binornd(1,p,2,mm)；a=0;for i=1:mm a=a+randnum(1,i)*randnum(2,i);pro(i)=a/i;end num=1:mm;plot(num,pro)例例2 2 两两盒盒火火柴柴，每每盒盒n根根。每每次次随随机机在在任任一一盒盒中中取取出出一一根根火火柴柴。问问其其中中一一盒盒中中火火柴柴被被取取完完而而另另一一盒盒中中至至少少还还有有k根火柴的概率有多大？（用频率估计概率）根火柴的概率有多大？（用频率估计概率）function proguji=test2(n,k,mm)frq=0;randnum=binornd(1,0.5,mm,2*n);proguji=0;for i=1:mm a1=0;a2=0;j=1;while(a1n)&(a2=k ,frq=frq+1;endend;proguji=frq/mm例例3 3在我方某前沿防守地域，敌人以一个炮排（含两在我方某前沿防守地域，敌人以一个炮排（含两门火炮）为单位对我方进行干扰和破坏为躲避我方门火炮）为单位对我方进行干扰和破坏为躲避我方打击，敌方对其阵地进行了伪装并经常变换射击地点打击，敌方对其阵地进行了伪装并经常变换射击地点经过长期观察发现，我方指挥所对敌方目标的指示经过长期观察发现，我方指挥所对敌方目标的指示有有5050是准确的，而我方火力单位，在指示正确时，是准确的，而我方火力单位，在指示正确时，有有1/31/3的概率能毁伤敌人一门火炮，有的概率能毁伤敌人一门火炮，有1/61/6的概率能全的概率能全部消灭敌人现在希望能用某种方式把我方将要对敌部消灭敌人现在希望能用某种方式把我方将要对敌人实施的人实施的1 1次打击结果显现出来，利用频率稳定性，次打击结果显现出来，利用频率稳定性，确定有效射击确定有效射击(毁伤一门炮或全部消灭毁伤一门炮或全部消灭)的概率的概率.分析：分析：这是一个复杂概率问题，可以通过理论计算得这是一个复杂概率问题，可以通过理论计算得到相应的概率到相应的概率.为了直观地显示我方射击的过程，现为了直观地显示我方射击的过程，现采用模拟的方式。采用模拟的方式。需要模拟出以下两件事：需要模拟出以下两件事：1 1 观察所对目标的指示正确与否观察所对目标的指示正确与否 模拟试验有两种结果，每一种结果出现的概率都是模拟试验有两种结果，每一种结果出现的概率都是1/21/2因此，因此，可用投掷一枚硬币的方式予以确定可用投掷一枚硬币的方式予以确定,当硬币出当硬币出现正面时为指示正确，反之为不正确现正面时为指示正确，反之为不正确2 2 当指示正确时，我方火力单位的射击结果情况当指示正确时，我方火力单位的射击结果情况 模拟试验有三种结果：毁伤一门火炮的可能性为模拟试验有三种结果：毁伤一门火炮的可能性为1/3(1/3(即即2/6)2/6)，毁伤两门的可能性为，毁伤两门的可能性为1/61/6，没能毁伤敌火炮的可，没能毁伤敌火炮的可能性为能性为1/2(1/2(即即3/6)3/6)这时这时可用投掷骰子的方法来确定可用投掷骰子的方法来确定：如果出现的是、三个点：则认为没能击中敌人；如果出现的是、三个点：则认为没能击中敌人；如果出现的是、点：则认为毁伤敌人一门火炮；如果出现的是、点：则认为毁伤敌人一门火炮；若出现的是点：则认为毁伤敌人两门火炮若出现的是点：则认为毁伤敌人两门火炮 i i：要模拟的打击次数；：要模拟的打击次数；k k1 1：没击中敌人火炮的射击总数；：没击中敌人火炮的射击总数；k k2 2：击中敌人一门火炮的射击总数；：击中敌人一门火炮的射击总数；k k3 3：击中敌人两门火炮的射击总数：击中敌人两门火炮的射击总数E E：有效射击：有效射击(毁伤一门炮或两门炮毁伤一门炮或两门炮)的概率的概率符号假设符号假设模拟框图模拟框图function test(p,mm)efreq=zeros(1,mm);randnum1=binornd(1,p,1,mm);randnum2=unidrnd(6,1,mm);k1=0;k2=0;k3=0;for i=1:mm if randnum1(i)=0 k1=k1+1;else if randnum2(i)=3 k1=k1+1;elseif randnum2(i)=6 k3=k3+1;else k2=k2+1;end end efreq(i)=(k2+k3)/i;end num=1:mm;plot(num,efreq)蒙特卡洛方法的特点蒙特卡洛方法的特点1.Monte Carlo方法及其程序结构简单方法及其程序结构简单 产生随机数，计算相应的值。即通过大量的简单重产生随机数，计算相应的值。即通过大量的简单重复抽样和简单计算实现该方法。复抽样和简单计算实现该方法。2.收敛速度与问题维数无关收敛速度与问题维数无关 Monte Carlo方法的收敛速度为方法的收敛速度为O(n-1/2)，与一般数，与一般数值方法相比很慢。因此，用值方法相比很慢。因此，用Monte Carlo方法不能方法不能解决精确度要求很高的问题解决精确度要求很高的问题 Monte Carlo方法的误差方法的误差 只与标准差只与标准差 和样本容量和样本容量n有关，而与样本所在空间无关，即有关，而与样本所在空间无关，即Monte Carlo方方法的收敛速度与问题维数无关。而其他数值方法则法的收敛速度与问题维数无关。而其他数值方法则不然。因此，这就决定了不然。因此，这就决定了Monte Carlo方法对多维方法对多维问题的适用性。问题的适用性。3.Monte Carlo方法的适用性强方法的适用性强 在解题时受问题条线限制的影响较小，例如要计算在解题时受问题条线限制的影响较小，例如要计算s维空间中的任一区域维空间中的任一区域Ds上的积分上的积分 时，无论区域时，无论区域Ds的形状多么特殊，只要能给出描述的形状多么特殊，只要能给出描述 Ds的几何特征的条件，就可以从的几何特征的条件，就可以从Ds中均匀产生中均匀产生n个个 点点 ,得到积分的近似值得到积分的近似值 其中其中Ds为区域为区域Ds的体积。这是数值方法难以作到的的体积。这是数值方法难以作到的数据处理方法数据处理方法 数据拟合方法数据拟合方法 给出一系列的点，要求得到反映点列变化规律的给出一系列的点，要求得到反映点列变化规律的函数，不要求曲线或曲面通过所有数据点，而是函数，不要求曲线或曲面通过所有数据点，而是要求它反映对象的整体变化趋势。注意在进行数要求它反映对象的整体变化趋势。注意在进行数据拟合时，难点在反映数据规律的大致函数类型，据拟合时，难点在反映数据规律的大致函数类型，拟合只是对函数类型中含有的参数利用最小二乘拟合只是对函数类型中含有的参数利用最小二乘法在误差最小的条件下进行优化。在进行拟合时，法在误差最小的条件下进行优化。在进行拟合时，如有固定规律函数，必须使用该函数，如果没有，如有固定规律函数，必须使用该函数，如果没有，则以常用函数如多项式函数、指数函数、对数函则以常用函数如多项式函数、指数函数、对数函数、三角函数等进行拟合比较，并选择误差最小数、三角函数等进行拟合比较，并选择误差最小的函数作为结果的函数作为结果.Matlab曲线拟合工具箱曲线拟合工具箱cftool数据插值方法数据插值方法 给出一系列点，要求按照已知点的函数值得到未知给出一系列点，要求按照已知点的函数值得到未知点的函数值，也可以理解为得到函数表达式，但点的函数值，也可以理解为得到函数表达式，但是与数据拟合不同的是插值要求所得到的函数曲是与数据拟合不同的是插值要求所得到的函数曲线经过所有的已知点，在进行插值时一般使用三线经过所有的已知点，在进行插值时一般使用三次样条插值，注意在实际建模时要根据具体的问次样条插值，注意在实际建模时要根据具体的问题区分拟合和插值题区分拟合和插值附附:常用的常用的matlab插值函数有插值函数有interp1q,interpft,spline,pchip,interp2,interp3,interpn,ppval，csape,spapi,csapi等等,样条插值的实现可以使样条插值的实现可以使用用matlab的样条工具箱（的样条工具箱（Spline toolbox），运），运行命令是行命令是splinetool，得到如下的用户交互式界面，得到如下的用户交互式界面回归分析方法：回归分析与数据拟合大致相同，也回归分析方法：回归分析与数据拟合大致相同，也是按照已知数据通过最小二乘法得到反映涉及到的是按照已知数据通过最小二乘法得到反映涉及到的量的关系。由于回归分析给出了具体的接受回归结量的关系。由于回归分析给出了具体的接受回归结果的统计判断条件，因此要按照统计条件决定是否果的统计判断条件，因此要按照统计条件决定是否接受回归结果，回归过程中也要进行回归函数的选接受回归结果，回归过程中也要进行回归函数的选择，一般情况下选择线性回归，进而考虑多项式回择，一般情况下选择线性回归，进而考虑多项式回归，非线性回归等归，非线性回归等统计分析方法：按照问题的要求选择适当的统计分统计分析方法：按照问题的要求选择适当的统计分析方法，如回归分析，判别分析，聚类分析，相关析方法，如回归分析，判别分析，聚类分析，相关分析，方差分析等分析，方差分析等参数分析方法参数分析方法:根据问题所提供的数据根据问题所提供的数据,在确定分布在确定分布类型的情况下给出常用概率分布的参数估计类型的情况下给出常用概率分布的参数估计附附:根据自己的适用经验根据自己的适用经验,可以使用可以使用matlab的统计工具的统计工具箱或箱或SAS或或SPSS软件实现相应的功能软件实现相应的功能优化方法优化方法线性规划模型：目标函数和约束条件都是线性规划模型：目标函数和约束条件都是线性函数的优化问题线性函数的优化问题非线性规划模型：目标函数或约束条件至非线性规划模型：目标函数或约束条件至少有一个是非线性函数的优化问题少有一个是非线性函数的优化问题整数规划模型：决策变量是整数值的优化整数规划模型：决策变量是整数值的优化问题问题附附:列举出规划后用列举出规划后用Lindo、Lingo 等软件来等软件来进行解决比较方便进行解决比较方便遗传算法遗传算法 遗传算法模拟自然选择和自然遗传过程中发生的遗传算法模拟自然选择和自然遗传过程中发生的繁繁殖、交叉和基因突变殖、交叉和基因突变现象，在每次迭代中都保留一现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，组候选解，并按某种指标从解群中选取较优的个体，利用利用遗传算子遗传算子(选择、交叉和变异选择、交叉和变异)对这些个体进行对这些个体进行组合，产生新一代的候选解群，重复此过程，直到组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。满足某种收敛指标为止。遗传算法作为一种有效的工具，已广泛地应用于遗传算法作为一种有效的工具，已广泛地应用于 最最优化问题求解之中。优化问题求解之中。遗传算法提供了一种求解复杂系统优化问题的通用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。有很强的鲁棒性，所以广泛应用于很多学科。生物进化与遗传算法对应关系生物进化与遗传算法对应关系生物进化生物进化遗传算法遗传算法适者生存适者生存适应函数值最大的解被保留的概率最大适应函数值最大的解被保留的概率最大个体个体问题的一个解问题的一个解染色体染色体解的编码解的编码基因基因编码的元素编码的元素群体群体被选定的一组解被选定的一组解种群种群根据适应函数选择的一组解根据适应函数选择的一组解交叉交叉以一定的方式由双亲产生后代的过程以一定的方式由双亲产生后代的过程变异变异编码的某些分量发生变化的过程编码的某些分量发生变化的过程环境环境适应函数适应函数 函数优化函数优化 函数优化是遗传算法的经典应用领域，函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。较好的结果。组合优化组合优化 遗传算法是寻求组合优化问题满意解的最遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题佳工具之一，实践证明，遗传算法对于组合优化问题中的中的NPNP完全问题非常有效。例如，遗传算法已经在求完全问题非常有效。例如，遗传算法已经在求解旅行商问题解旅行商问题(Traveling Salesman Problem,TSP)(Traveling Salesman Problem,TSP)、背包问题背包问题(Knapsack Problem)(Knapsack Problem)、装箱问题、装箱问题(Bin(Bin Packing Problem)Packing Problem)等方面得到成功的应用。等方面得到成功的应用。生产调度问题生产调度问题 生产调度问题在很多情况下所建立起生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。的有效工具。自动控制自动控制 遗传算法已经在自动控制领域中得到了很好的遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。值学习等。机器人智能控制机器人智能控制 机器人是一类复杂的难以精确建模的人机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要研究，所以机器人智能控制自然成为遗传算法的一个重要应用领域。应用领域。图象处理和模式识别图象处理和模式识别 图像处理和模式识别是计算机视觉图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。的优化计算方面得到了很好的应用。Matlab 7.0版本首次增加了遗传算法工具箱版本首次增加了遗传算法工具箱（Genetic Algorithm and Direct Search Toolbox Genetic Algorithm and Direct Search Toolbox(GA&DS)(GA&DS)），运行命令是），运行命令是gatool，Matlab 2009及后续版本将该产品集成到优化工具箱及后续版本将该产品集成到优化工具箱（Optimization Toolbox）中，运行命令是）中，运行命令是Optimtool，然后在左侧的下拉菜单中选择，然后在左侧的下拉菜单中选择“ga-Genetic Algorithm”选项，然后在右选项，然后在右侧的选项卡组中定义所要求解问题描述的侧的选项卡组中定义所要求解问题描述的“种种群群”，“选择选择”，“适应函数适应函数”，“复制复制”，“交叉交叉”，“变异变异”，“迁移迁移”等特性，即可等特性，即可开始计算求解，该工具的界面如图所示开始计算求解，该工具的界面如图所示06A 出版社的资源配置出版社的资源配置整数规划、数据整数规划、数据处理、优化处理、优化 06B 艾滋病疗法的评价及疗效的预测艾滋病疗法的评价及疗效的预测线线性规划、回归分析性规划、回归分析 07A 中国人口增长预测中国人口增长预测微分方程、数据微分方程、数据处理、优化处理、优化07B 乘公交，看奥运乘公交，看奥运 多目标规划、图论、多目标规划、图论、动态规划、整数规划动态规划、整数规划08A 数码相机定位数码相机定位非线性方程组、优化非线性方程组、优化 08B 高等教育学费标准探讨高等教育学费标准探讨数据收集和数据收集和处理、统计分析处理、统计分析、回归分析、回归分析图论方法图论方法最短路问题：给出一个连接若干城镇的铁最短路问题：给出一个连接若干城镇的铁路网络，在这个网络的两个指定城镇间，路网络，在这个网络的两个指定城镇间，找一条最短的铁路线（找一条最短的铁路线（Dijkstra算法）或每算法）或每对指定顶点间的最短路径（对指定顶点间的最短路径（Dijkstra算法，算法，Floyd算法）算法）最大流问题：运输问题最大流问题：运输问题最小费用最大流问题：在完成运输任务的最小费用最大流问题：在完成运输任务的同时，寻求一个使总的运输费用最小的运同时，寻求一个使总的运输费用最小的运输方案输方案最小生成树问题（连线问题）：欲修筑连最小生成树问题（连线问题）：欲修筑连接多个城镇的铁路，设计一个连线图，使接多个城镇的铁路，设计一个连线图，使得总造价最低（得总造价最低（prim算法，算法，Kruskal算法）算法）图的匹配问题（人员安排问题）：图的匹配问题（人员安排问题）：n个人员个人员安排安排n份工作，每人适合做其中一件或若干份工作，每人适合做其中一件或若干件工作，问能否每人有一件合适工作？如件工作，问能否每人有一件合适工作？如果不能，最多几人可以有合适的工作？果不能，最多几人可以有合适的工作？（匈牙利算法）（匈牙利算法）遍历性问题（中国邮递员问题）：邮递员遍历性问题（中国邮递员问题）：邮递员从邮局出发，经过投递范围内每条街道最从邮局出发，经过投递范围内每条街道最少一次，再回到邮局，选择一条行程最短少一次，再回到邮局，选择一条行程最短的路线的路线预测方法预测方法拟合预测：按照已知数据得到反映规律的拟合预测：按照已知数据得到反映规律的函数，再代入需要预测的变量，将函数值函数，再代入需要预测的变量，将函数值作为预测值作为预测值回归预测：与拟合预测基本类似回归预测：与拟合预测基本类似微分方程预测：首先得到预测变化规律的微分方程预测：首先得到预测变化规律的微分方程，求解方程得到通解，利用已知微分方程，求解方程得到通解，利用已知数据进行拟合，由方程得解进行预测数据进行拟合，由方程得解进行预测时间序列分析：按照数据变化的基本规律，时间序列分析：按照数据变化的基本规律，用统计方法进行预测用统计方法进行预测灰色预测：根据灰色系统的行为特征，充灰色预测：根据灰色系统的行为特征，充分利用数量不多的数据和信息寻求数学关分利用数量不多的数据和信息寻求数学关系，建立相应的数学模型进行预测系，建立相应的数学模型进行预测其它预测方法：拓扑预测，线性网络预测，其它预测方法：拓扑预测，线性网络预测，BP网络预测，网络预测，Hopfield网络预测，模糊神网络预测，模糊神经网络，全域法，一阶局域法，加权零阶经网络，全域法，一阶局域法，加权零阶局域法，加权一阶局域法，局域法，加权一阶局域法，Lyapunov指数指数预测，权重综合，区域综合，最优加权模预测，权重综合，区域综合，最优加权模型，正权组合方法，方差倒数加权法，马型，正权组合方法，方差倒数加权法，马尔科夫预测，遗传预测，分形预测等等尔科夫预测，遗传预测，分形预测等等决策方法决策方法规划模型规划模型层次分析法层次分析法综合评判方法综合评判方法模糊数学方法模糊数学方法多属性决策方法多属性决策方法多目标决策方法多目标决策方法灰色决策方法灰色决策方法对策论方法对策论方法