數(shù)學(xué)建模競賽中應(yīng)當(dāng)掌握十類算法：

1、蒙特卡羅算法（該算法又稱隨機(jī)性模擬算法，是通過計算機(jī)仿真來處理問題算法，同時能夠通過模擬來檢查自己模型正確性，是比賽時必用辦法）

2、數(shù)據(jù)擬合、參數(shù)預(yù)計、插值等數(shù)據(jù)處理算法（比賽中通常會碰到大量數(shù)據(jù)需要處理，而處理數(shù)據(jù)關(guān)鍵就在于這些算法，通常使用Matlab作為工具）

3、線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題（建模競賽大多數(shù)問題屬于最優(yōu)化問題，諸多時候這些問題能夠用數(shù)學(xué)規(guī)劃算法來描述，通常使用Lindo、Lingo軟件實(shí)現(xiàn)）

第1頁第1頁4、圖論算法（這類算法能夠分為很各種，涉及最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論問題能夠用這些辦法處理，需要認(rèn)真準(zhǔn)備）5、動態(tài)規(guī)劃、回溯搜索、分支定界等計算機(jī)算法（這些算法是算法設(shè)計中比較慣用辦法，諸多場合能夠用到競賽中）6、最優(yōu)化理論三大非典型算法：模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法（這些問題是用來處理一些較困難最優(yōu)化問題算法，對于有些問題非常有幫助，但是算法實(shí)現(xiàn)比較困難，需謹(jǐn)慎使用）7、網(wǎng)格算法和窮舉法（網(wǎng)格算法和窮舉法都是暴力搜索最長處算法，在諸多競賽題中有應(yīng)用，當(dāng)重點(diǎn)討論模型本身而輕視算法時候，能夠使用這種暴力方案，最好使用一些高級語言作為編程工具）

第2頁第2頁8、一些連續(xù)離散化辦法（諸多問題都是實(shí)際來，數(shù)據(jù)能夠是連續(xù)，而計算機(jī)只認(rèn)是離散數(shù)據(jù)，因此將其離散化后進(jìn)行差分代替微分、求和代替積分等思想是非常主要）9、數(shù)值分析算法（假如在比賽中采用高級語言進(jìn)行編程話，那一些數(shù)值分析中慣用算法比如方程組求解、矩陣運(yùn)算、函數(shù)積分等算法就需要額外編寫庫函數(shù)進(jìn)行調(diào)用）10、圖象處理算法（賽題中有一類問題與圖形相關(guān)，即使與圖形無關(guān)，論文中也應(yīng)當(dāng)要不乏圖片，這些圖形如何展示以及如何處理就是需要處理問題，通常使用Matlab進(jìn)行處理）第3頁第3頁十類算法詳細(xì)闡明1、蒙特卡羅辦法（MC）（MonteCarlo）：蒙特卡羅（MonteCarlo）辦法，或稱計算機(jī)隨機(jī)模擬辦法，是一個基于“隨機(jī)數(shù)”計算辦法。這一辦法源于美國在第二次世界大戰(zhàn)進(jìn)行研制原子彈“曼哈頓計劃”。該計劃主持人之一、數(shù)學(xué)家馮·諾伊曼用馳名世界賭城—摩納哥MonteCarlo—來命名這種辦法，為它蒙上了一層神秘色彩。

第4頁第4頁蒙特卡羅辦法基本原理及思想下列：當(dāng)所要求解問題是某種事件出現(xiàn)概率，或者是某個隨機(jī)變量盼望值時，它們能夠通過某種“試驗(yàn)”辦法，得到這種事件出現(xiàn)頻率，或者這個隨機(jī)變數(shù)平均值，并用它們作為問題解。這就是蒙特卡羅辦法基本思想。蒙特卡羅辦法通過抓住事物運(yùn)動幾何數(shù)量和幾何特性，利用數(shù)學(xué)辦法來加以模擬，即進(jìn)行一個數(shù)字模擬試驗(yàn)。它是以一個概率模型為基礎(chǔ)，按照這個模型所描繪過程，通過模擬試驗(yàn)結(jié)果，作為問題近似解。能夠把蒙特卡羅解題歸結(jié)為三個主要環(huán)節(jié)：結(jié)構(gòu)或描述概率過程；實(shí)現(xiàn)從已知概率分布抽樣；建立各種預(yù)計量。第5頁第5頁例.蒲豐氏問題為了求得圓周率π值，在十九世紀(jì)后期，有諸多人作了這樣試驗(yàn)：將長為2l一根針任意投到地面上，用針與一組相間距離為2a（l＜a）平行線相交頻率代替概率P，再利用準(zhǔn)確關(guān)系式：求出π值其中Ｎ為投計次數(shù)，n為針與平行線相交次數(shù)。這就是古典概率論中著名蒲豐氏問題。第6頁第6頁一些人進(jìn)行了試驗(yàn)，其結(jié)果列于下表：試驗(yàn)者年份投計次數(shù)π試驗(yàn)值沃爾弗(Wolf)185050003.1596斯密思(Smith)185532043.1553?？怂?Fox)189411203.1419拉查里尼(Lazzarini)190134083.1415929第7頁第7頁設(shè)針投到地面上位置能夠用一組參數(shù)（x,θ）來描述，x為針中心坐標(biāo)，θ為針與平行線夾角，如圖所表示。任意投針，就是意味著x與θ都是任意取，但x范圍限于［0，a］，夾角θ范圍限于［0，π］。在此情況下，針與平行線相交數(shù)學(xué)條件是針在平行線間位置

第8頁第8頁如何產(chǎn)生任意（x,θ）？x在［0，a］上任意取值，表示x在［0，a］上是均勻分布，其分布密度函數(shù)為：類似地，θ分布密度函數(shù)為：因此，產(chǎn)生任意（x,θ）過程就變成了由f1(x)抽樣x及由f2(θ)抽樣θ過程了。由此得到：

其中ξ1，ξ2均為（0,1）上均勻分布隨機(jī)變量。第9頁第9頁每次投針試驗(yàn)，事實(shí)上變成在計算機(jī)上從兩個均勻分布隨機(jī)變量中抽樣得到（x,θ），然后定義描述針與平行線相交情況隨機(jī)變量s(x,θ)，為假如投針Ｎ次，則是針與平行線相交概率Ｐ預(yù)計值。事實(shí)上，于是有第10頁第10頁因此，能夠通俗地說，蒙特卡羅辦法是用隨機(jī)試驗(yàn)辦法計算積分，即將所要計算積分看作服從某種分布密度函數(shù)f(r)隨機(jī)變量ｇ(r)數(shù)學(xué)盼望

通過某種試驗(yàn)，得到Ｎ個觀測值r1，r2，…，rN（用概率語言來說，從分布密度函數(shù)f(r)中抽取Ｎ個子樣r1，r2，…，rN，），將相應(yīng)Ｎ個隨機(jī)變量值g(r1)，g(r2)，…，g(rN)算術(shù)平均值作為積分預(yù)計值（近似值）。

第11頁第11頁用比較抽象概率語言描述蒙特卡羅辦法解題環(huán)節(jié)下列：結(jié)構(gòu)一個概率空間(W,A,P)，其中，W是一個事件集合，A是集合W子集，P是在A上建立某個概率測度；在這個概率空間中，選取一個隨機(jī)變量q(w),使得這個隨機(jī)變量盼望值正好是所要求解Q，然后用q(w)簡樸子樣算術(shù)平均值作為Q近似值。舉個例子就是97年A題，每個零件都有自己標(biāo)定值，也都有自己容差等級，而求解最優(yōu)組合方案將要面對著是一個極其復(fù)雜公式和108種容差選取方案，主線不也許去求解析解，那如何去找到最優(yōu)方案呢？隨機(jī)性模擬搜索最優(yōu)方案就是其中一個辦法，在每個零件可行區(qū)間中按照正態(tài)分布隨機(jī)選取一個標(biāo)定值和選取一個容差值作為一個方案，然后通過蒙特卡羅算法仿真出大量方案，從中選取一個最佳。第12頁第12頁另一個例子就是彩票問題第二問，要求設(shè)計一個更加好方案，首先方案優(yōu)劣取決于諸多復(fù)雜原因，同樣不也許刻畫出一個模型進(jìn)行求解，只能靠隨機(jī)仿真模擬。蒙特卡羅辦法計算程序：關(guān)于蒙特卡羅辦法計算程序已有諸多，如：EGS4、FLUKA、ETRAN、ITS、MCNP、GEANT等。這些程序大多通過了多年發(fā)展，花費(fèi)了巨大工作量。除歐洲核子研究中心（CERN）發(fā)行GEANT主要用于高能物理探測器響應(yīng)和粒子徑跡模擬外，其它程序都進(jìn)一步到低能領(lǐng)域，并被廣泛應(yīng)用。第13頁第13頁2、最優(yōu)化理論三大非典型算法

這十幾年來最優(yōu)化理論有了飛速發(fā)展，模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法這三類算法發(fā)展不久。近幾年賽題越來越復(fù)雜，諸多問題沒有什么較好模型能夠借鑒，于是這三類算法諸多時候能夠派上用場，比如：97年A題模擬退火算法，00年B題神經(jīng)網(wǎng)絡(luò)分類算法，象01年B題這種難題也能夠使用神經(jīng)網(wǎng)絡(luò)，尚有美國競賽89年A題也和BP算法相關(guān)系，當(dāng)初是86年剛提出BP算法，89年就考了，闡明賽題也許是當(dāng)今前沿科技抽象表達(dá)。當(dāng)前算法最佳是遺傳算法。第14頁第14頁遺傳算法簡介遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制隨機(jī)化搜索算法，由美國J.Holland專家提出，其主要特點(diǎn)是群體搜索策略和群體中個體之間信息互換，搜索不依賴于梯度信息。它尤其合用于老式搜索辦法難于解決復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計和人工生命等領(lǐng)域，是21世紀(jì)有關(guān)智能計算中關(guān)鍵技術(shù)之一。在人工智能領(lǐng)域中，有不少問題需要在復(fù)雜和龐大搜索空間中尋找最優(yōu)解或準(zhǔn)最優(yōu)解。象貨郎擔(dān)問題和規(guī)劃問題等組合優(yōu)化問題就是典型例子。在求解此類問題時，若不能利用問題固有知識來縮小搜索空間則會產(chǎn)生搜索組合爆炸。第15頁第15頁因此，研究能在搜索過程中自動獲取和積累相關(guān)搜索空間知識，并自適應(yīng)地控制搜索過程，從而得到最優(yōu)解地通用搜索辦法始終是令人矚目地課題。遺傳算法就是這種尤其有效地算法。生物進(jìn)化是一個奇妙優(yōu)化過程，它通過選擇淘汰，忽然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境改變優(yōu)良物種。遺傳算法是依據(jù)生物進(jìn)化思想而啟發(fā)得出一個全局優(yōu)化算法。盡管遺傳算法本身在理論和應(yīng)用辦法上仍有許多待進(jìn)一步研究地問題，但它已在諸多領(lǐng)域地應(yīng)用中呈現(xiàn)了其特色和魅力。第16頁第16頁遺傳算法基本概念遺傳算法基本思想是基于Darwin進(jìn)化論和Mendel遺傳學(xué)說。Darwin進(jìn)化論最主要是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境。物種每個個體基本特性由后代所繼承，但后代又會產(chǎn)生一些異于父代新改變。在環(huán)境改變時，只有那些能適應(yīng)環(huán)境個體特性方能保留下來。Mendel遺傳學(xué)說最主要是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包括在染色體內(nèi)。每個基因有特殊位置并控制某種特殊性質(zhì)；因此，每個基因產(chǎn)生個體對環(huán)境含有某種適應(yīng)性?；蛲蛔兒突螂s交可產(chǎn)生更適應(yīng)于環(huán)境后代。通過存優(yōu)去劣自然淘汰，適應(yīng)性高基因結(jié)構(gòu)得以保留下來。由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生直接搜索優(yōu)化辦法；故而在這個算法中要用到各種進(jìn)化和遺傳學(xué)概念。這些概念下列：第17頁第17頁一、串(String)它是個體(Individual)形式，在算法中為二進(jìn)制串，并且相應(yīng)于遺傳學(xué)中染色體(Chromosome)。二、群體(Population)個體集合稱為群體，串是群體元素三、群體大小(PopulationSize)在群體中個體數(shù)量稱為群體大小。四、基因(Gene)基因是串中元素，基因用于表示個體特性。比如有一個串S＝1011，則其中1，0，1，1這4個元素分別稱為基因。它們值稱為等位基因(Alletes)。五、基因位置(GenePosition)一個基因在串中位置稱為基因位置，有時也簡稱基因位?；蛭恢糜纱笙蛴矣嬎?，比如在串S＝1101中，0基因位置是3。基因位置相應(yīng)于遺傳學(xué)中地點(diǎn)(Locus)。第18頁第18頁六、基因特性值(GeneFeature)在用串表示整數(shù)時，基因特性值與二進(jìn)制數(shù)權(quán)一致；比如在串S=1011中，基因位置3中1，它基因特性值為2；基因位置1中1，它基因特性值為8。七、串結(jié)構(gòu)空間SS在串中，基因任意組合所構(gòu)成串集合?；虿僮魇窃诮Y(jié)構(gòu)空間中進(jìn)行。串結(jié)構(gòu)空間相應(yīng)于遺傳學(xué)中基因型(Genotype)集合。八、參數(shù)空間SP這是串空間在物理系統(tǒng)中映射，它相應(yīng)于遺傳學(xué)中表現(xiàn)型(Phenotype)集合。九、非線性它相應(yīng)遺傳學(xué)中異位顯性(Epistasis)十、適應(yīng)度(Fitness)表示某一個體對于環(huán)境適應(yīng)程度。第19頁第19頁遺傳算法原理

遺傳算法GA把問題解表示成“染色體”，在算法中也即是以二進(jìn)制編碼串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問題“環(huán)境”中，并按適者生存原則，從中選擇出較適應(yīng)環(huán)境“染色體”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境一個“染色體”上，它就是問題最優(yōu)解。第20頁第20頁一、遺傳算法目的典型遺傳算法CGA(CanonicalGeneticAlgorithm)通慣用于處理下面這一類靜態(tài)最優(yōu)化問題：考慮對于一群長度為L二進(jìn)制編碼bi，i＝1，2，…，n；有bi∈{0,1}

給定目的函數(shù)f，有f(bi)，并且0<f(bi)<∞同時

f(bi)≠f(bi+1)求滿足下式max{f(bi)|bi∈{0,1}

bi。很明顯，遺傳算法是一個最優(yōu)化辦法，它通過進(jìn)化和遺傳機(jī)理，從給出原始解群中，不斷進(jìn)化產(chǎn)生新解，最后收斂到一個特定串bi處，即求出最優(yōu)解。第21頁第21頁二、遺傳算法基本原理長度為Ln個二進(jìn)制串bi(i＝1，2，…，n)組成了遺傳算法初解群，也稱為初始群體。在每個串中，每個二進(jìn)制位就是個體染色體基因。依據(jù)進(jìn)化術(shù)語，對群體執(zhí)行操作有三種：1．選擇(Selection)這是從群體中選擇出較適應(yīng)環(huán)境個體。這些選中個體用于繁殖下一代。故有時也稱這一操作為再生(Reproduction)。因?yàn)樵谶x擇用于繁殖下一代個體時，是依據(jù)個體對環(huán)境適應(yīng)度而決定其繁殖量，故而有時也稱為非均勻再生(differentialreproduction)。2．交叉(Crossover)這是在選中用于繁殖下一代個體中，對兩個不同個體相同位置基因進(jìn)行互換，從而產(chǎn)生新個體。3．變異(Mutation)這是在選中個體中，對個體中一些基因執(zhí)行異向轉(zhuǎn)化。在串bi中，假如某位基因?yàn)?，產(chǎn)生變異時就是把它變成0；反亦反之。第22頁第22頁三、遺傳算法環(huán)節(jié)1．初始化選擇一個群體，即選擇一個串或個體集合bi，i=1，2，...n。這個初始群體也就是問題假設(shè)解集合。普通取n＝30-160。通常以隨機(jī)辦法產(chǎn)生串或個體集合bi,i＝1，2，...n。問題最優(yōu)解將通過這些初始假設(shè)解進(jìn)化而求出。2．選擇依據(jù)適者生存原則選擇下一代個體。在選擇時，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則表達(dá)了適者生存，不適應(yīng)者淘汰自然法則。給出目的函數(shù)f，則f(bi)稱為個體bi適應(yīng)度。以為選中bi為下一代個體次數(shù)。

第23頁第23頁顯然：(1)適應(yīng)度較高個體，繁殖下一代數(shù)目較多。(2)適應(yīng)度較小個體，繁殖下一代數(shù)目較少；甚至被淘汰。這樣，就產(chǎn)生了對環(huán)境適應(yīng)能力較強(qiáng)后代。對于問題求解角度來講，就是選擇出和最優(yōu)解較靠近中間解。選擇辦法有：適應(yīng)度百分比法盼望值法排位次法精髓保留法第24頁第24頁3．交叉

對于選中用于繁殖下一代個體，隨機(jī)地選擇兩個個體相同位置，按交叉概率P。在選中位置實(shí)行互換。這個過程反應(yīng)了隨機(jī)信息互換；目的在于產(chǎn)生新基因組合，也即產(chǎn)生新個體。交叉時，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。比如有個體S1=100101S2=010111選擇它們左邊3位進(jìn)行交叉操作，則有S1=010101S2=100111普通而言，交叉概率P，取值為0.25—0.75。第25頁第25頁4．變異依據(jù)生物遺傳中基因變異原理，以變異概率Pm對一些個體一些位執(zhí)行變異。在變異時，對執(zhí)行變異串相應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小情況一致，因此，Pm取值較小，普通取0.01-0.2。比如有個體S＝101011。對其第1，4位置基因進(jìn)行變異，則有S'=001111單靠變異不能在求解中得到好處。但是，它能確保算法過程不會產(chǎn)生無法進(jìn)化單一群體。由于在所有個體同樣時，交叉是無法產(chǎn)生新個體，這時只能靠變異產(chǎn)生新個體。也就是說，變異增長了全局優(yōu)化特質(zhì)。第26頁第26頁5．全局最優(yōu)收斂(Convergencetotheglobaloptimum)當(dāng)最優(yōu)個體適應(yīng)度達(dá)到給定閥值，或者最優(yōu)個體適應(yīng)度和群體適應(yīng)度不再上升時，則算法迭代過程收斂、算法結(jié)束。不然，用通過選擇、交叉、變異所得到新一代群體取代上一代群體，并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。遺傳算法基本處理流程圖下列：第27頁第27頁二、遺傳算法應(yīng)用關(guān)鍵遺傳算法在應(yīng)用中最關(guān)鍵問題有下列3個1．串編碼方式這本質(zhì)是問題編碼。普通把問題各種參數(shù)用二進(jìn)制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。串長度及編碼形式對算法收斂影響極大。2．適應(yīng)函數(shù)確實(shí)定適應(yīng)函數(shù)(fitnessfunction)也稱對象函數(shù)(objectfunction)，這是問題求解品質(zhì)測量函數(shù)；往往也稱為問題“環(huán)境”。普通能夠把問題模型函數(shù)作為對象函數(shù)；但有時需要另行結(jié)構(gòu)。3．遺傳算法本身參數(shù)設(shè)定遺傳算法本身參數(shù)有3個，即群體大小n、交叉概率Pc和變異概率Pm。群體大小n太小時難以求出最優(yōu)解，太大則增長收斂時間。普通n＝30-160。交叉概率Pc太小時難以向前搜索，太大則容易破壞高適應(yīng)值結(jié)構(gòu)。普通取Pc=0.25-0.75。變異概率Pm太小時難以產(chǎn)生新基因結(jié)構(gòu)，太大使遺傳算法成了單純隨機(jī)搜索。普通取Pm＝0．01—0．2。第28頁第28頁matlab遺傳算法工具箱函數(shù)及實(shí)例解說

關(guān)鍵函數(shù)：

(1)function[pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始種群生成函數(shù)

【輸出參數(shù)】

pop--生成初始種群

【輸入?yún)?shù)】

num--種群中個體數(shù)目

bounds--代表變量上下界矩陣

eevalFN--適應(yīng)度函數(shù)

eevalOps--傳遞給適應(yīng)度函數(shù)參數(shù)

options--選擇編碼形式(浮點(diǎn)編碼或是二進(jìn)制編碼)[precisionF_or_B],如

precision--變量進(jìn)行二進(jìn)制編碼時指定精度

F_or_B--為1時選擇浮點(diǎn)編碼，不然為二進(jìn)制編碼,由precision指定精度)

第29頁第29頁2)function[x,endPop,bPop,traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,...

termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)--遺傳算法函數(shù)

【輸出參數(shù)】

x--求得最優(yōu)解

endPop--最后得到種群

bPop--最優(yōu)種群一個搜索軌跡

【輸入?yún)?shù)】

bounds--代表變量上下界矩陣

evalFN--適應(yīng)度函數(shù)

evalOps--傳遞給適應(yīng)度函數(shù)參數(shù)

startPop-初始種群

opts[epsilonprob_opsdisplay]--opts(1:2)等同于initializegaoptions參數(shù)，第三個參數(shù)控制是否輸出，普通為0。如[1e-610]

termFN--終止函數(shù)名稱,如[‘maxGenTerm’]

termOps--傳遞給終止函數(shù)參數(shù),如[100]

selectFN--選擇函數(shù)名稱,如[‘normGeomSelect’]

selectOps--傳遞給選擇函數(shù)參數(shù),如[0.08]

xOverFNs--交叉函數(shù)名稱表，以空格分開，如['arithXoverheuristicXoversimpleXover']

xOverOps--傳遞給交叉函數(shù)參數(shù)表，如[20;23;20]

mutFNs--變異函數(shù)表，如['boundaryMutationmultiNonUnifMutationnonUnifMutationunifMutation']

mutOps--傳遞給交叉函數(shù)參數(shù)表,如[400;61003;41003;400]

第30頁第30頁【問題】求f(x)=x+10*sin(5x)+7*cos(4x)最大值，其中0<=x<=9【分析】選擇二進(jìn)制編碼，種群中個體數(shù)目為10，二進(jìn)制編碼長度為20，交叉概率為0.95,變異概率為0.08

【程序清單】

%編寫目的函數(shù)

function[sol,eval]=fitness(sol,options)

x=sol(1);

eval=x+10*sin(5*x)+7*cos(4*x);

%把上述函數(shù)存儲為fitness.m文獻(xiàn)并放在工作目錄下

initPop=initializega(10,[09],'fitness');%生成初始種群，大小為10

[xendPop,bPop,trace]=ga([09],'fitness',[],initPop,[1e-611],'maxGenTerm',25,'normGeomSelect',...

[0.08],['arithXover'],[2],'nonUnifMutation',[2253])%25次遺傳迭代

第31頁第31頁運(yùn)算結(jié)果為：x=

7.856224.8553(當(dāng)x為7.8562時，f（x）取最大值24.8553)

注：1、遺傳算法普通用來取得近似最優(yōu)解，而不是最優(yōu)解。

2、matlab工具箱函數(shù)必須放在工作目錄下第32頁第32頁一、模型建立設(shè)購買Si金額為Xi，所需交易費(fèi)ci(xi)為：設(shè)存銀行金額為x0,顯然c0(x0)=0對si投資凈收益為Ri(xi)=rixi-ci(xi)投資組合x=(x0,x1,…xn)凈收益為由題意，投資風(fēng)險為Q(x)=max(qixi)

98年全國大學(xué)生數(shù)學(xué)建模競賽A題

投資收益和風(fēng)險

第33頁第33頁因此，問題數(shù)學(xué)模型是一個雙目的優(yōu)化：minz1=Q(x)minz2=-R(x)s.t第34頁第34頁二、模型求解對于上述雙目的優(yōu)化模型這類問題大多用某種方式化為單目的問題來求解，主要有下列三種：（1）固定風(fēng)險水平，優(yōu)化收益；（2）固定贏利水平，極小化風(fēng)險；（3）擬定投資者對風(fēng)辦法險—收益相對偏好系數(shù)。前（1）、（2）兩種辦法分別是以犧牲某一目的來達(dá)到另一目的優(yōu)化，而對第三種則由于決議者很難知道偏好系數(shù)詳細(xì)值。故這三種辦法都不太抱負(fù)，下面我們考慮用遺傳算法來處理這個問題。由于在雙目的情況下，兩目的通常本質(zhì)上是互相矛盾，最優(yōu)解需要替換為非劣解，即對于任何目的函數(shù)在不犧牲其它目的情況下就不能改進(jìn)解。第35頁第35頁三個定義定義1：非劣解：可行解定義2：正抱負(fù)解：正抱負(fù)解由所有可達(dá)到最好目的值構(gòu)成定義3：負(fù)抱負(fù)解：負(fù)抱負(fù)解由所有可達(dá)到最壞目的值構(gòu)成我們考慮用遺傳算法產(chǎn)生整個非劣解集合，或近似集合，然后讓決議者自己來選擇最好地表示他對各個目的權(quán)衡取舍非劣解。對于這個雙目的規(guī)劃問題可采用自適應(yīng)移動線技術(shù)建立一個求加權(quán)和辦法，這種辦法可迫使遺傳搜索去摸索目的空間中非劣解集合。第36頁第36頁總環(huán)節(jié)：環(huán)節(jié)1：結(jié)構(gòu)染色體，產(chǎn)生初始種群：選取二進(jìn)制編碼，隨機(jī)產(chǎn)生一組染色體xk放入集合E中環(huán)節(jié)2：染色體交叉，對上面產(chǎn)生種群按交叉概率pc選擇“個體對”進(jìn)行單點(diǎn)交叉。普通取pc從0.25到1.00之間。環(huán)節(jié)3：染色體變異：為使群體保持多樣性，可按變異率pm進(jìn)行變異（可隨機(jī)選擇變異點(diǎn)）環(huán)節(jié)4：更新集合E：1）對雙親和后代每個染色體計算兩個目的值；（2）將新非劣解加入E，從而更新E并從E刪去劣點(diǎn)；（3）擬定集合E中新特殊點(diǎn)環(huán)節(jié)5：評估：按公式計算雙親和后代每個染色體適值。第37頁第37頁環(huán)節(jié)6：選擇：（1）刪去所有重復(fù)染色體；（2）按降序排列余下染色體；（3）選擇前pop_size個染色體構(gòu)成新種群.環(huán)節(jié)7:檢查終止條件：若運(yùn)營次數(shù)已達(dá)預(yù)先擬定代數(shù)目則停止，不然轉(zhuǎn)環(huán)節(jié)2故利用該算法若干次后最后能得到一個非劣解集，供決議者參考.遺傳算法從多個初始點(diǎn)開始尋優(yōu)，沿多路徑搜索，可獲全局或準(zhǔn)全局最優(yōu)解.我們可類似地用上述算法取得多目的規(guī)劃模型非劣解集合.第38頁第38頁3、數(shù)據(jù)擬合、參數(shù)預(yù)計、插值等算法

數(shù)據(jù)擬合在諸多賽題中有應(yīng)用，與圖形處理相關(guān)問題諸多與擬合相關(guān)系，一個例子就是98年美國賽A題，生物組織切