《數(shù)學(xué)建模競(jìng)賽算法講座.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《數(shù)學(xué)建模競(jìng)賽算法講座.ppt（41頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、數(shù)學(xué)建模競(jìng)賽 常用方法 哈爾濱工業(yè)大學(xué)數(shù)學(xué)系 王希連 前言 在數(shù)學(xué)建模競(jìng)賽的評(píng)卷過(guò)程中 , 首重摘要 , 其次是所建立的數(shù)學(xué)模型的創(chuàng)新性和正確 性 , 第三要看求解計(jì)算結(jié)果的應(yīng)用結(jié)果 (是 否能夠完全回答題目的問(wèn)題 )及強(qiáng)健性 (結(jié)果 的主要優(yōu)缺點(diǎn)和結(jié)果的敏感性分析等 ), 第 四看文章的整體結(jié)構(gòu)和格式表述的規(guī)范性 , 簡(jiǎn)潔性 , 最后再考評(píng)算法的實(shí)用性和正確性 (只有競(jìng)爭(zhēng)力較強(qiáng)的文章算法才可能被評(píng)委 審評(píng) ), 因此一定不要本末倒置 . 一篇 mcm官方正式出版的對(duì)一份 Outstanding 論文評(píng)審文章中節(jié)錄的關(guān)于評(píng)審過(guò)程的一段 : 廣義來(lái)看 , 算法是指求解一個(gè)問(wèn)題的高效方法 , 如等
2、比數(shù) 列的求和方法 , 一元二次方程的求解方法 , 求一元函數(shù)零 點(diǎn)的牛頓迭代法 , 信號(hào)頻譜分析中的快速傅立葉變換法 , 常微分方程求解的龍格 -庫(kù)塔法等等 , 目前特指所有利用 計(jì)算機(jī)程序求解問(wèn)題的各種有效算法 在數(shù)學(xué)建模中 , 針對(duì)各種各樣的問(wèn)題 , 人們已經(jīng)建立了各 種算法 ,特別是很多問(wèn)題的優(yōu)秀算法都已經(jīng)商業(yè)化了成熟 的軟件包 , 使用者只要根據(jù)相應(yīng)軟件的語(yǔ)法要求正確地描 述問(wèn)題 ,然后運(yùn)行程序即可得到結(jié)果 ,而不需要關(guān)心算法的 具體原理和數(shù)據(jù)結(jié)構(gòu)的組織安排和計(jì)算精度及收斂性的 控制等 , 如數(shù)據(jù)的統(tǒng)計(jì)分析、相關(guān)分析、回歸分析、聚類(lèi) 分析、數(shù)據(jù)簡(jiǎn)化、生存分析、時(shí)間序列分析、多重響應(yīng)
3、等數(shù)據(jù)處理和挖掘工作可以用 SAS或 SPSS軟件進(jìn)行求 解分析 ; 曲線(xiàn)擬合與插值 ,常微分方程和偏微分方程的求 解等數(shù)值求解問(wèn)題可以使用 Matlab完成 , 線(xiàn)性規(guī)劃、非 線(xiàn)性規(guī)劃、整數(shù)規(guī)劃問(wèn)題可以用 lingo軟件求解等 算法概述 蒙特卡洛 (Monte-Carlo)算法 蒙特卡羅方法又稱(chēng)隨機(jī)抽樣技巧或統(tǒng) 計(jì)試驗(yàn)方法，與一般數(shù)值計(jì)算方法有 很大區(qū)別。它是以概率統(tǒng)計(jì)理論為基 礎(chǔ)的一種方法。 當(dāng)所求問(wèn)題的解是某個(gè)事件的概率， 或者是某個(gè)隨機(jī)變量的數(shù)學(xué)期望，或 者是與之有關(guān)的量時(shí)，通過(guò)某種試驗(yàn) 的方法，得出該事件發(fā)生的頻率，再 通過(guò)它得到問(wèn)題的解。這就是蒙特卡 羅方法的基本思想。 基本示例
4、: 圓周率 的計(jì)算 蒙特卡羅投點(diǎn)法 (蒲豐投針實(shí)驗(yàn) 的推廣 )： 在一個(gè)邊長(zhǎng)為 a的正方形內(nèi)隨機(jī)投點(diǎn)， 該點(diǎn)落在此正方形的內(nèi)切圓中的概率 應(yīng)為該內(nèi)切圓與正方形的面積比值， 即 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; end end disp(投點(diǎn)法近似計(jì)算的 為 : ,num2str(4*m/n); o (a/2,a/2) /4a:a/2 22 蒙特卡羅方法的關(guān)鍵步驟在于隨機(jī)數(shù)的產(chǎn)生，計(jì)算機(jī)產(chǎn) 生的隨機(jī)數(shù)都不是真正的隨機(jī)數(shù) (由算法確定的緣故
5、)， 如果偽隨機(jī)數(shù)能夠通過(guò)一系列統(tǒng)計(jì)檢驗(yàn)，我們也可以將 其當(dāng)作真正的隨機(jī)數(shù)使用。 rand(state,sum(100*clock)*rand); rand(1) %重新啟動(dòng) matlab時(shí)，輸出的隨機(jī)數(shù)不一樣 常用 Matlab隨機(jī)數(shù)生成方法 : 1 rand() 生成（ 0,1）區(qū)間上均勻分布的隨機(jī)變量?；菊Z(yǔ)法： rand(M,N,P .) 生成排列成 M*N*P. 多維向量的隨機(jī)數(shù)。如果只寫(xiě) M， 則生成 M*M矩陣；如果參數(shù)為 M,N可以省略掉方括號(hào) 2 randn() 生成服從標(biāo)準(zhǔn)正態(tài)分布（均值為 0，方差為 1）的隨機(jī)數(shù) ?；菊Z(yǔ)法和 rand()類(lèi)似。 randn(M,N,P
6、.) 生成排列成 M*N*P. 多維向量的隨機(jī)數(shù)。如果只寫(xiě) M， 則生成 M*M矩陣；如果參數(shù)為 M,N可以省略掉方括號(hào) 3 unifrnd() 和 rand()類(lèi)似，這個(gè)函數(shù)生成某個(gè)區(qū)間內(nèi)均勻分布的隨 機(jī)數(shù)。基本語(yǔ)法 unifrnd(a,b,M,N,P,.) 4 normrnd() 和 randn()類(lèi)似，此函數(shù)生成指定均值、標(biāo)準(zhǔn)差的正態(tài) 分布的隨機(jī)數(shù)。基本語(yǔ)法 normrnd(mu,sigma,M,N,P,.) 生成的隨機(jī)數(shù)服從均值為 mu，標(biāo)準(zhǔn)差為 sigma（注意 標(biāo)準(zhǔn)差是正數(shù)）正態(tài)分布， 5 chi2rnd() 此函數(shù)生成服從卡方（ Chi-square)分布的隨機(jī)數(shù)?？?方分布只有
7、一個(gè)參數(shù)：自由度 v?；菊Z(yǔ)法 chi2rnd(v,M,N,P,.) 生成的隨機(jī)數(shù)服從自由度為 v的卡方分布，這些隨機(jī)數(shù) 排列成 M*N*P. 多維向量 6 frnd() 此函數(shù)生成服從 F分布的隨機(jī)數(shù)。 F分布有 2個(gè)參數(shù)： v1, v2?；菊Z(yǔ)法 frnd(v1,v2,M,N,P,.) 生成的隨機(jī)數(shù)服從參數(shù)為 (v1,v2)的卡方分布 7 trnd() 此函數(shù)生成服從 t(Students t Distribution，這里是 Cosset.W.S.的筆名 )分布的隨機(jī)數(shù)。 t分布有 1個(gè)參數(shù)： 自由度 v?；菊Z(yǔ)法 trnd(v,M,N,P,.) 生成的隨機(jī)數(shù)服從參數(shù)為 v的 t分布 8
8、 betarnd() 此函數(shù)生成服從 Beta分布的隨機(jī)數(shù)。 Beta分布有兩個(gè) 參數(shù)分別是 A和 B。生成 beta分布隨機(jī)數(shù)的語(yǔ)法是： betarnd(A,B,M,N,P,.) 9 exprnd() 此函數(shù)生成服從指數(shù)分布的隨機(jī)數(shù)。指數(shù)分布只有一 個(gè)參數(shù) : mu, 生成指數(shù)分布隨機(jī)數(shù)的語(yǔ)法是： betarnd(mu,M,N,P,.) 10 gamrnd() 生成服從 Gamma分布的隨機(jī)數(shù)。 Gamma分布有兩個(gè) 參數(shù)： A和 B。 生成 Gamma分布隨機(jī)數(shù)的語(yǔ)法是： gamrnd(A,B,M,N,P,.) 11 lognrnd() 生成服從對(duì)數(shù)正態(tài)分布的隨機(jī)數(shù)。其有兩個(gè)參數(shù)： mu和
9、 sigma，服從這個(gè)這樣的隨機(jī)數(shù)取對(duì)數(shù)后就 服從均值為 mu，標(biāo)準(zhǔn)差為 sigma的正態(tài)分布。 lognrnd(mu,sigma,M,N,P,.) 12 raylrnd() 生成服從瑞利（ Rayleigh）分布的隨機(jī)數(shù)。其分 布有 1個(gè)參數(shù)： B。 raylrnd(B,M,N,P,.) 13 wblrnd() 生成服從威布爾（ Weibull）分布的隨機(jī)數(shù)。其分 布有 2個(gè)參數(shù)： scale 參數(shù) A和 shape 參數(shù) B。 wblrnd(A,B,M,N,P,.) 14 unidrnd() 生成服從離散均勻分布的隨機(jī)數(shù)。 Unifrnd是在某個(gè)區(qū) 間內(nèi)均勻選取實(shí)數(shù)（可為小數(shù)或整數(shù)）， U
10、nidrnd是 均勻選取整數(shù)隨機(jī)數(shù)。離散均勻分布隨機(jī)數(shù)有 1個(gè)參數(shù) ： n, 表示從 1, 2, 3, . N這 n個(gè)整數(shù)中以相同的概率抽 樣?；菊Z(yǔ)法： unidrnd(n,M,N,P,.) 15. binornd() 生成服從二項(xiàng)分布的隨機(jī)數(shù)。二項(xiàng)分布有 2個(gè)參數(shù)： n,p?？紤]一個(gè)打靶的例子，每槍命中率為 p，共射擊 N槍?zhuān)敲匆还矒糁械拇螖?shù)就服從參數(shù)為（ N,p）的二 項(xiàng)分布。注意 p要小于等于 1且非負(fù)， N要為整數(shù)?；?本語(yǔ)法： binornd(n,p,M,N,P,.) 16. geornd() 生成服從幾何分布的隨機(jī)數(shù)。幾何分布的參數(shù)只有 一個(gè)： p。幾何分布的現(xiàn)實(shí)意義可以解釋為
11、，打靶命 中率為 p，不斷地打靶，直到第一次命中目標(biāo)時(shí)沒(méi)有 擊中次數(shù)之和。注意 p是概率，所以要小于等于 1且 非負(fù)。 基本語(yǔ)法： geornd(p,M,N,P,.) 17 poissrnd() 生成服從泊松 (Poisson)分布的隨機(jī)數(shù)。泊松分布的 參數(shù)只有一個(gè)： lambda。此參數(shù)要大于零。 基本語(yǔ)法： poissrnd (lambda,M,N,P,.) 附 : 概率分布函數(shù) (Probability Distribution Function) 直方圖繪制語(yǔ)句 : hist 例 1 擲 兩枚不均勻硬幣 ， 每枚正面出現(xiàn)概率為 批 p， 記錄前 mm次擲硬幣試驗(yàn)中兩枚都為正面 頻率的波
12、動(dòng)情況 ， 并畫(huà)圖 。 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 兩盒火柴 ， 每盒 n根 。 每次隨機(jī)在任一盒中取出一 根火柴 。 問(wèn)其中一盒中火柴被取完而另一盒中至少還 有 k根火柴的概率有多大 ？ （ 用頻率估計(jì)概率 ） function proguji=test2(n,k,mm) frq=0; randnum=bino
13、rnd(1,0.5,mm,2*n);proguji=0; for i=1:mm a1=0;a2=0;j=1; while (a1n) end end; proguji=frq/mm 例 3 在我方某前沿防守地域，敵人以一個(gè)炮排（含兩 門(mén)火炮）為單位對(duì)我方進(jìn)行干擾和破壞為躲避我方 打擊，敵方對(duì)其陣地進(jìn)行了偽裝并經(jīng)常變換射擊地點(diǎn) 經(jīng)過(guò)長(zhǎng)期觀(guān)察發(fā)現(xiàn)，我方指揮所對(duì)敵方目標(biāo)的指示 有 50是準(zhǔn)確的，而我方火力單位，在指示正確時(shí)， 有 1/3的概率能毀傷敵人一門(mén)火炮，有 1/6的概率能全 部消滅敵人現(xiàn)在希望能用某種方式把我方將要對(duì)敵 人實(shí)施的 1次打擊結(jié)果顯現(xiàn)出來(lái)，利用頻率穩(wěn)定性， 確定有效射擊 (毀傷一
14、門(mén)炮或全部消滅 )的概率 . 分析： 這是一個(gè)復(fù)雜概率問(wèn)題，可以通過(guò)理論計(jì)算得 到相應(yīng)的概率 .為了直觀(guān)地顯示我方射擊的過(guò)程，現(xiàn) 采用模擬的方式。 需要模擬出以下兩件事： 1 觀(guān)察所對(duì)目標(biāo)的指示正確與否 模擬試驗(yàn)有兩種結(jié)果，每一種結(jié)果出現(xiàn)的概率都是 1/2因此， 可用投擲一枚硬幣的方式予以確定 ,當(dāng)硬幣 出現(xiàn)正面時(shí)為指示正確，反之為不正確 2 當(dāng)指示正確時(shí)，我方火力單位的射擊結(jié)果情況 模擬試驗(yàn)有三種結(jié)果：毀傷一門(mén)火炮的可能性為 1/3(即 2/6)，毀傷兩門(mén)的可能性為 1/6，沒(méi)能毀傷敵火炮的可 能性為 1/2(即 3/6) 這時(shí) 可用投擲骰子的方法來(lái)確定 ： 如果出現(xiàn)的是、三個(gè)點(diǎn)：則認(rèn)為沒(méi)能
15、擊中敵人； 如果出現(xiàn)的是、點(diǎn)：則認(rèn)為毀傷敵人一門(mén)火炮； 若出現(xiàn)的是點(diǎn)：則認(rèn)為毀傷敵人兩門(mén)火炮 i：要模擬的打擊次數(shù)； k1：沒(méi)擊中敵人火炮的射擊總數(shù)； k2：擊中敵人一門(mén)火炮的射擊總數(shù)； k3：擊中敵人兩門(mén)火炮的射擊總數(shù) E：有效射擊 (毀傷一門(mén)炮或兩門(mén)炮 )的概率 符號(hào)假設(shè) 模擬框圖 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 i
16、f 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) 蒙特卡洛方法的特點(diǎn) 1. Monte Carlo方法及其程序結(jié)構(gòu)簡(jiǎn)單 產(chǎn)生隨機(jī)數(shù)，計(jì)算相應(yīng)的值。即通過(guò)大量的簡(jiǎn)單重 復(fù)抽樣和簡(jiǎn)單計(jì)算實(shí)現(xiàn)該方法。 2. 收斂速度與問(wèn)題維數(shù)無(wú)關(guān) Monte Carlo方法的收斂速度為 O(n -1/2)，與一般數(shù) 值方法相比很慢。因此，用 Monte Carlo方法不能 解決精確度要求很高的問(wèn)題 Monte Car
17、lo方法的誤差 只與標(biāo)準(zhǔn)差 和樣本容量 n 有關(guān)，而與樣本所在空間無(wú)關(guān)，即 Monte Carlo方 法的收斂速度與問(wèn)題維數(shù)無(wú)關(guān)。而其他數(shù)值方法則 不然。因此，這就決定了 Monte Carlo方法對(duì)多維 問(wèn)題的適用性。 3. Monte Carlo方法的適用性強(qiáng) 在解題時(shí)受問(wèn)題條線(xiàn)限制的影響較小，例如要計(jì)算 s 維空間中的任一區(qū)域 Ds上的積分 時(shí)，無(wú)論區(qū)域 Ds的形狀多么特殊，只要能給出描述 Ds的幾何特征的條件，就可以從 Ds中均勻產(chǎn)生 n個(gè) 點(diǎn) , 得到積分的近似值 其中 Ds為區(qū)域 Ds的體積。這是數(shù)值方法難以作到的 ssD dxdxdxxxxgg s 2121 ),( N i i
18、s iis N xxxgN Dg 1 )()( 2 )( 1 ),( ),( )()(2)(1 isii xxx 數(shù)據(jù)處理方法 數(shù)據(jù)擬合方法 給出一系列的點(diǎn)，要求得到反映點(diǎn)列變化規(guī)律的 函數(shù)，不要求曲線(xiàn)或曲面通過(guò)所有數(shù)據(jù)點(diǎn)，而是 要求它反映對(duì)象的整體變化趨勢(shì)。注意在進(jìn)行數(shù) 據(jù)擬合時(shí)，難點(diǎn)在反映數(shù)據(jù)規(guī)律的大致函數(shù)類(lèi)型， 擬合只是對(duì)函數(shù)類(lèi)型中含有的參數(shù)利用最小二乘 法在誤差最小的條件下進(jìn)行優(yōu)化。在進(jìn)行擬合時(shí)， 如有固定規(guī)律函數(shù)，必須使用該函數(shù)，如果沒(méi)有， 則以常用函數(shù)如多項(xiàng)式函數(shù)、指數(shù)函數(shù)、對(duì)數(shù)函 數(shù)、三角函數(shù)等進(jìn)行擬合比較，并選擇誤差最小 的函數(shù)作為結(jié)果 . Matlab曲線(xiàn)擬合工具箱 cfto
19、ol 數(shù)據(jù)插值方法 給出一系列點(diǎn)，要求按照已知點(diǎn)的函數(shù)值得到未 知點(diǎn)的函數(shù)值，也可以理解為得到函數(shù)表達(dá)式， 但是與數(shù)據(jù)擬合不同的是插值要求所得到的函數(shù) 曲線(xiàn)經(jīng)過(guò)所有的已知點(diǎn)，在進(jìn)行插值時(shí)一般使用 三次樣條插值，注意在實(shí)際建模時(shí)要根據(jù)具體的 問(wèn)題區(qū)分?jǐn)M合和插值 附 : 常用的 matlab插值函數(shù)有 interp1q, interpft, spline, pchip, interp2, interp3, interpn, ppval， csape, spapi, csapi等 , 樣條插值的實(shí)現(xiàn)可以使用 matlab的樣條工具箱（ Spline toolbox），運(yùn)行 命令是 splinetoo
20、l，得到如下的用戶(hù)交互式界面 回歸分析方法：回歸分析與數(shù)據(jù)擬合大致相同，也 是按照已知數(shù)據(jù)通過(guò)最小二乘法得到反映涉及到的 量的關(guān)系。由于回歸分析給出了具體的接受回歸結(jié) 果的統(tǒng)計(jì)判斷條件，因此要按照統(tǒng)計(jì)條件決定是否 接受回歸結(jié)果，回歸過(guò)程中也要進(jìn)行回歸函數(shù)的選 擇，一般情況下選擇線(xiàn)性回歸，進(jìn)而考慮多項(xiàng)式回 歸，非線(xiàn)性回歸等 統(tǒng)計(jì)分析方法：按照問(wèn)題的要求選擇適當(dāng)?shù)慕y(tǒng)計(jì)分 析方法，如回歸分析，判別分析，聚類(lèi)分析，相關(guān) 分析，方差分析等 參數(shù)分析方法 : 根據(jù)問(wèn)題所提供的數(shù)據(jù) , 在確定分布 類(lèi)型的情況下給出常用概率分布的參數(shù)估計(jì) 附 : 根據(jù)自己的適用經(jīng)驗(yàn) , 可以使用 matlab的統(tǒng)計(jì)工具 箱或
21、 SAS或 SPSS軟件實(shí)現(xiàn)相應(yīng)的功能 優(yōu)化方法 線(xiàn)性規(guī)劃模型：目標(biāo)函數(shù)和約束條件都是 線(xiàn)性函數(shù)的優(yōu)化問(wèn)題 非線(xiàn)性規(guī)劃模型：目標(biāo)函數(shù)或約束條件至 少有一個(gè)是非線(xiàn)性函數(shù)的優(yōu)化問(wèn)題 整數(shù)規(guī)劃模型：決策變量是整數(shù)值的優(yōu)化 問(wèn)題 附 :列舉出規(guī)劃后用 Lindo、 Lingo 等軟件來(lái) 進(jìn)行解決比較方便 遺傳算法 遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的 繁 殖、交叉和基因突變 現(xiàn)象，在每次迭代中都保留一 組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體， 利用 遺傳算子 (選擇、交叉和變異 )對(duì)這些個(gè)體進(jìn)行 組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到 滿(mǎn)足某種收斂指標(biāo)為止。 遺傳算法作為一種有效的工
22、具，已廣泛地應(yīng)用于 最 優(yōu)化問(wèn)題求解之中。 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用 框架，它不依賴(lài)于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類(lèi) 有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。 生物進(jìn)化與遺傳算法對(duì)應(yīng)關(guān)系 生物進(jìn)化 遺傳算法 適者生存 適應(yīng)函數(shù)值最大的解被保留的概率最大 個(gè)體 問(wèn)題的一個(gè)解 染色體 解的編碼 基因 編碼的元素 群體 被選定的一組解 種群 根據(jù)適應(yīng)函數(shù)選擇的一組解 交叉 以一定的方式由雙親產(chǎn)生后代的過(guò)程 變異 編碼的某些分量發(fā)生變化的過(guò)程 環(huán)境 適應(yīng)函數(shù) 函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域， 也是對(duì)遺傳算法進(jìn)行性能測(cè)試評(píng)價(jià)的常用算例。對(duì)于 一些非線(xiàn)性、多模型、多目標(biāo)的函數(shù)
23、優(yōu)化問(wèn)題，用其 他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到 較好的結(jié)果。 組合優(yōu)化 遺傳算法是尋求組合優(yōu)化問(wèn)題滿(mǎn)意解的 最佳工具之一，實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化問(wèn) 題中的 NP完全問(wèn)題非常有效。例如，遺傳算法已經(jīng)在 求解旅行商問(wèn)題 (Traveling Salesman Problem , TSP)、背包問(wèn)題 (Knapsack Problem)、裝箱問(wèn)題 (Bin Packing Problem) 等方面得到成功的應(yīng)用。 生產(chǎn)調(diào)度問(wèn)題 生產(chǎn)調(diào)度問(wèn)題在很多情況下所建立起 來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后 可以進(jìn)行求解也會(huì)因簡(jiǎn)化得太多而使求解結(jié)果與實(shí)際 相差太遠(yuǎn)?，F(xiàn)在遺傳算
24、法已經(jīng)成為解決復(fù)雜調(diào)度問(wèn)題 的有效工具。 自動(dòng)控制 遺傳算法已經(jīng)在自動(dòng)控制領(lǐng)域中得到了很好 的應(yīng)用，例如基于遺傳算法的模糊控制器的優(yōu)化設(shè)計(jì)、基 于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的模糊控制規(guī)則的 學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和 權(quán)值學(xué)習(xí)等。 機(jī)器人智能控制 機(jī)器人是一類(lèi)復(fù)雜的難以精確建模的人 工系統(tǒng)，而遺傳算法的起源就來(lái)自于對(duì)人工自適應(yīng)系統(tǒng)的 研究，所以機(jī)器人智能控制自然成為遺傳算法的一個(gè)重要 應(yīng)用領(lǐng)域。 圖象處理和模式識(shí)別 圖像處理和模式識(shí)別是計(jì)算機(jī)視覺(jué) 中的一個(gè)重要研究領(lǐng)域。在圖像處理過(guò)程中，如掃描、特 征提取、圖像分割等不可避免地存在一些誤差，這些誤差 會(huì)影響圖像處理
25、的效果。如何使這些誤差最小是使計(jì)算機(jī) 視覺(jué)達(dá)到實(shí)用化的重要要求，遺傳算法在這些圖像處理中 的優(yōu)化計(jì)算方面得到了很好的應(yīng)用。 Matlab 7.0版本首次增加了遺傳算法工具箱 （ Genetic Algorithm and Direct Search Toolbox (GA&DS)），運(yùn)行命令是 gatool， Matlab 2009及后續(xù)版本將該產(chǎn)品集成到優(yōu)化工具箱 （ Optimization Toolbox）中，運(yùn)行命令是 Optimtool，然后在左側(cè)的下拉菜單中選擇 “ ga- Genetic Algorithm ”選項(xiàng)，然后在右 側(cè)的選項(xiàng)卡組中定義所要求解問(wèn)題描述的“種 群”，“選擇
26、”，“適應(yīng)函數(shù)”，“復(fù)制”， “交叉”，“變異”，“遷移”等特性，即可 開(kāi)始計(jì)算求解，該工具的界面如圖所示 06A 出版社的資源配置 整數(shù)規(guī)劃、數(shù)據(jù) 處理、優(yōu)化 06B 艾滋病療法的評(píng)價(jià)及療效的預(yù)測(cè) 線(xiàn) 性規(guī)劃、回歸分析 07A 中國(guó)人口增長(zhǎng)預(yù)測(cè) 微分方程、數(shù)據(jù) 處理、優(yōu)化 07B 乘公交，看奧運(yùn) 多目標(biāo)規(guī)劃、圖 論、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃 08A 數(shù)碼相機(jī)定位 非線(xiàn)性方程組、優(yōu)化 08B 高等教育學(xué)費(fèi)標(biāo)準(zhǔn)探討 數(shù)據(jù)收集和 處理、統(tǒng)計(jì)分析 、回歸分析 圖論方法 最短路問(wèn)題：給出一個(gè)連接若干城鎮(zhèn)的鐵 路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間， 找一條最短的鐵路線(xiàn)（ Dijkstra算法）或每 對(duì)指定頂點(diǎn)間
27、的最短路徑（ Dijkstra算法， Floyd算法） 最大流問(wèn)題：運(yùn)輸問(wèn)題 最小費(fèi)用最大流問(wèn)題：在完成運(yùn)輸任務(wù)的 同時(shí)，尋求一個(gè)使總的運(yùn)輸費(fèi)用最小的運(yùn) 輸方案 最小生成樹(shù)問(wèn)題（連線(xiàn)問(wèn)題）：欲修筑連 接多個(gè)城鎮(zhèn)的鐵路，設(shè)計(jì)一個(gè)連線(xiàn)圖，使 得總造價(jià)最低（ prim算法， Kruskal算法） 圖的匹配問(wèn)題（人員安排問(wèn)題）： n個(gè)人員 安排 n份工作，每人適合做其中一件或若干 件工作，問(wèn)能否每人有一件合適工作？如 果不能，最多幾人可以有合適的工作？ （匈牙利算法） 遍歷性問(wèn)題（中國(guó)郵遞員問(wèn)題）：郵遞員 從郵局出發(fā)，經(jīng)過(guò)投遞范圍內(nèi)每條街道最 少一次，再回到郵局，選擇一條行程最短 的路線(xiàn) 預(yù)測(cè)方法 擬
28、合預(yù)測(cè)：按照已知數(shù)據(jù)得到反映規(guī)律的 函數(shù)，再代入需要預(yù)測(cè)的變量，將函數(shù)值 作為預(yù)測(cè)值 回歸預(yù)測(cè)：與擬合預(yù)測(cè)基本類(lèi)似 微分方程預(yù)測(cè)：首先得到預(yù)測(cè)變化規(guī)律的 微分方程，求解方程得到通解，利用已知 數(shù)據(jù)進(jìn)行擬合，由方程得解進(jìn)行預(yù)測(cè) 時(shí)間序列分析：按照數(shù)據(jù)變化的基本規(guī)律， 用統(tǒng)計(jì)方法進(jìn)行預(yù)測(cè) 灰色預(yù)測(cè)：根據(jù)灰色系統(tǒng)的行為特征，充 分利用數(shù)量不多的數(shù)據(jù)和信息尋求數(shù)學(xué)關(guān) 系，建立相應(yīng)的數(shù)學(xué)模型進(jìn)行預(yù)測(cè) 其它預(yù)測(cè)方法：拓?fù)漕A(yù)測(cè)，線(xiàn)性網(wǎng)絡(luò)預(yù)測(cè)， BP網(wǎng)絡(luò)預(yù)測(cè)， Hopfield網(wǎng)絡(luò)預(yù)測(cè)，模糊神 經(jīng)網(wǎng)絡(luò)，全域法，一階局域法，加權(quán)零階 局域法，加權(quán)一階局域法， Lyapunov指數(shù) 預(yù)測(cè)，權(quán)重綜合，區(qū)域綜合，最優(yōu)加權(quán)模 型，正權(quán)組合方法，方差倒數(shù)加權(quán)法，馬 爾科夫預(yù)測(cè)，遺傳預(yù)測(cè)，分形預(yù)測(cè)等等 決策方法 規(guī)劃模型 層次分析法 綜合評(píng)判方法 模糊數(shù)學(xué)方法 多屬性決策方法 多目標(biāo)決策方法 灰色決策方法 對(duì)策論方法
數(shù)學(xué)建模競(jìng)賽算法講座.ppt
