《數(shù)學(xué)建模算法介紹》PPT課件.ppt

《《數(shù)學(xué)建模算法介紹》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)學(xué)建模算法介紹》PPT課件.ppt（70頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

優(yōu)化算法基礎(chǔ),馬建華2011年7月,進(jìn)化算法,算法基礎(chǔ)遺傳算法,算法基礎(chǔ),算法的概念算法分類算法的評(píng)價(jià),算法的概念,算法—計(jì)算方法把求解問(wèn)題的方法程式化、規(guī)范化算法是程序的依據(jù)、程序是算法的計(jì)算機(jī)實(shí)現(xiàn)算法思想與依據(jù)—實(shí)現(xiàn)技術(shù)—算法步驟算法構(gòu)成,算法組成,初始條件—指定參數(shù)、初始解迭代方法—轉(zhuǎn)移規(guī)則、生成新可行解的方法終止條件—最優(yōu)性條件或可接受條件輸出結(jié)果—最優(yōu)解或可接受解,,算法的分類,構(gòu)造算法搜索算法啟發(fā)式算法進(jìn)化算法,,構(gòu)造算法,明確知道最優(yōu)解的結(jié)構(gòu)特征直接構(gòu)建最優(yōu)解，中間過(guò)程得到的是最優(yōu)解的部分，不是可行解；最小支撐樹(shù)的算法,,最小支撐樹(shù)的算法,算法思想算法構(gòu)成關(guān)鍵技術(shù),,算法思想,依據(jù)--加上支撐樹(shù)外的任一邊構(gòu)成唯一的圈，樹(shù)外邊是該圈中權(quán)最大的。從權(quán)重小的邊開(kāi)始加邊，新拿的邊如果和已加入的邊構(gòu)成圈就不加，否則就加入。,,關(guān)鍵技術(shù),選擇圈中最小的邊按權(quán)重從小到大排序判斷是否構(gòu)成圈,,算法構(gòu)成,初始條件：已加邊集為空集，未拿邊集為全體邊迭代規(guī)則：從未拿的邊中選一個(gè)權(quán)重最小的，如果該邊與已加入邊構(gòu)成權(quán)就舍去，否則就加入停止規(guī)則：已加邊的個(gè)數(shù)等于頂點(diǎn)數(shù)減1或者沒(méi)有未拿邊輸出結(jié)果：已加邊集或沒(méi)有支撐樹(shù),,搜索算法,知道最優(yōu)解滿足的條件，但不知道其結(jié)構(gòu)從一個(gè)可行解出發(fā)按某種規(guī)則生成新的可行解直到滿足最優(yōu)性條件單純形算法,,,,,,,,,,,,單純形算法,算法思想關(guān)鍵技術(shù)算法構(gòu)成,,算法思想,從基可行解中找最優(yōu)解，從一個(gè)基可行解開(kāi)始，判斷是否滿足最優(yōu)性條件，如果滿足就停止，否則看是否沒(méi)有最優(yōu)解，如果沒(méi)有最優(yōu)解就停止，否則生成一個(gè)新的最優(yōu)解,,關(guān)鍵技術(shù),初始基可行解計(jì)算檢驗(yàn)數(shù)和典式生成新基可行解,,算法構(gòu)成,初始條件：初始基可行解迭代方法：計(jì)算典式和檢驗(yàn)數(shù)，找初級(jí)變量和入基變量終止條件：檢驗(yàn)數(shù)小于等于零或檢驗(yàn)數(shù)大于零的分量對(duì)應(yīng)典式列小于等于零輸出結(jié)果：最優(yōu)基可行解或沒(méi)有最優(yōu)解,啟發(fā)式算法,不知道最優(yōu)解的結(jié)構(gòu)和最優(yōu)性條件模擬人們的思路或經(jīng)驗(yàn)貪心算法,,最短路貪心算法,算法思想關(guān)鍵技術(shù)算法組成,,算法思想,從起點(diǎn)開(kāi)始，每一步都選最短的邊，直到終點(diǎn),,關(guān)鍵技術(shù),確定每個(gè)點(diǎn)關(guān)聯(lián)的未選的邊中權(quán)重最小的,,算法構(gòu)成,初始條件：已選邊為空集，當(dāng)前點(diǎn)為發(fā)點(diǎn)迭代規(guī)則：從當(dāng)前點(diǎn)出發(fā)的邊中選擇一個(gè)權(quán)重最小的邊，其頭部點(diǎn)為新的當(dāng)前點(diǎn)。如果沒(méi)有出點(diǎn)則返回上一個(gè)點(diǎn)重新選擇。終止條件：當(dāng)前點(diǎn)為終點(diǎn)，或當(dāng)前點(diǎn)沒(méi)有出發(fā)點(diǎn)輸出結(jié)果：一條從起點(diǎn)到終點(diǎn)的路或沒(méi)有路,,1.3啟發(fā)式算法_定義,啟發(fā)式算法（heuristicalgorithm）定義1.基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（時(shí)間、空間）下，給出待解組合優(yōu)化問(wèn)題的每個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解偏差事先不一定可以預(yù)計(jì).定義2.啟發(fā)式算法是一種技術(shù)，在可接受的計(jì)算費(fèi)用內(nèi)尋找最好解，但不保證該解的可行性與最優(yōu)性，無(wú)法描述該解與最優(yōu)解的近似程度。特點(diǎn)（與傳統(tǒng)優(yōu)化方法不同）：憑直觀和經(jīng)驗(yàn)給出算法；不考慮所得解與最優(yōu)解的偏離程度.,1.3啟發(fā)式算法_優(yōu)點(diǎn),優(yōu)點(diǎn)：（1）有可能比簡(jiǎn)化數(shù)學(xué)模型解的誤差小；（2）對(duì)有些難題，計(jì)算時(shí)間可接受；（3）可用于某些最優(yōu)化算法（如分支定界算法）之中的估界；（4）直觀易行；（5）速度較快；（6）程序簡(jiǎn)單，易修改。,1.3啟發(fā)式算法_不足,不足：（1）不能保證求得全局最優(yōu)解；（2）解的精度不穩(wěn)定，有時(shí)好有時(shí)壞；（3）算法設(shè)計(jì)與問(wèn)題、設(shè)計(jì)者經(jīng)驗(yàn)、技術(shù)有關(guān)，缺乏規(guī)律性；（4）不同算法之間難以比較。,1.3啟發(fā)式算法_分類,（1）一步算法（2）改進(jìn)算法（迭代算法）（3）數(shù)學(xué)規(guī)劃算法（4）解空間松弛法,1.3啟發(fā)式算法_分類,（5）現(xiàn)代優(yōu)化算法：80年代初興起禁忌搜索（tabusearch）模擬退火（simulatedannealing）遺傳算法（geneticalgorithms）神經(jīng)網(wǎng)絡(luò)（neuralnetworks）螞蟻算法（AntAlgorithm，群體（群集）智能，SwarmIntelligence）（6）其他算法：多種啟發(fā)式算法的集成.,1.3啟發(fā)式算法_性能分析,（1）最壞情形分析（worstcaseanalysis）利用最壞實(shí)例分析計(jì)算復(fù)雜性、解的效果。(2）概率分析（probabilityanalysis）用最壞情況分析，會(huì)因一個(gè)最壞實(shí)例影響總體評(píng)價(jià).在實(shí)例數(shù)據(jù)服從一定概率分布情形下，研究算法復(fù)雜性和解的效果.(3)大規(guī)模計(jì)算分析通過(guò)大量實(shí)例計(jì)算，評(píng)價(jià)算法效果.注意數(shù)據(jù)的隨機(jī)性和代表性.,進(jìn)化算法,不知道最優(yōu)解的結(jié)構(gòu)和最優(yōu)性條件模擬生物尋優(yōu)行為，大規(guī)模群體優(yōu)化群體搜索算法遺傳算法,,,,,,,,,,,,,,,,,算法的評(píng)價(jià),結(jié)果評(píng)價(jià)復(fù)雜性評(píng)價(jià),,結(jié)果評(píng)價(jià),全局最優(yōu)算法局部最優(yōu)算法近似算法有效算法,,全局最優(yōu)算法,全局收斂算法得到全局最優(yōu)解或收斂到全局最優(yōu)解分支定界算法,,局部最優(yōu)解,得到局部最優(yōu)解結(jié)果的好壞依賴初始解的選取非線性規(guī)劃搜索算法,,近似算法,得到一個(gè)與最優(yōu)解的差距不超過(guò)一定比例的解需要說(shuō)明與最優(yōu)解的差距復(fù)雜問(wèn)題的多項(xiàng)時(shí)間算法,,可接受算法,得到一個(gè)比較好的解無(wú)法說(shuō)明與最優(yōu)解的差距貪心算法不需要太多的理論知識(shí),,復(fù)雜性評(píng)價(jià),算法復(fù)雜性多項(xiàng)式時(shí)間算法非多項(xiàng)式時(shí)間算法,,1.2計(jì)算復(fù)雜性的概念,評(píng)價(jià)算法的好壞——計(jì)算時(shí)間的多少、解的偏離程度例非對(duì)稱距離TSP問(wèn)題的算法實(shí)現(xiàn)：所有路徑枚舉。計(jì)算時(shí)間：n個(gè)城市，固定1個(gè)為起終點(diǎn)需要(n-1)!個(gè)枚舉，設(shè)計(jì)算機(jī)1秒能完成24個(gè)城市的枚舉，則城市數(shù)與計(jì)算時(shí)間的關(guān)系如下表：,1.2計(jì)算復(fù)雜性的概念,隨城市增多，計(jì)算時(shí)間增加很快。到31個(gè)城市時(shí)，要計(jì)算325年。,描述算法的好壞——計(jì)算復(fù)雜性——討論計(jì)算時(shí)間與問(wèn)題規(guī)模之間的關(guān)系。以目前二進(jìn)制計(jì)算機(jī)中的存儲(chǔ)和計(jì)算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評(píng)估算法性能的基礎(chǔ)。,1.2計(jì)算復(fù)雜性的概念,問(wèn)題（problem）：要回答的一般性提問(wèn)，通常含有若干個(gè)滿足一定條件的參數(shù)（或自由變量）?？梢詮膬煞矫婷枋觯海?）對(duì)所有參數(shù)的一般性描述；（2）答案（或解）必須滿足的性質(zhì)。實(shí)例（instance）:給問(wèn)題的所有參數(shù)指定具體值，得到問(wèn)題的一個(gè)實(shí)例。這些具體值稱為數(shù)據(jù)；這些數(shù)據(jù)輸入計(jì)算機(jī)所占的空間稱為實(shí)例的長(zhǎng)度（size）.,1.2計(jì)算復(fù)雜性的概念,一類最優(yōu)化問(wèn)題是由一些類似的具體問(wèn)題（實(shí)例）組成的，每一個(gè)具體問(wèn)題可表達(dá)成二元組（F,C）.F為可行解集合;C是費(fèi)用函數(shù)，是由F到R（實(shí)數(shù)集）的映像。問(wèn)題是在F中找到一個(gè)點(diǎn)f*，使對(duì)F中任意的f，有C(f*)C(f),稱f*為這一具體問(wèn)題的最優(yōu)解（或全局最優(yōu)解）.,1.2計(jì)算復(fù)雜性的概念,算法計(jì)算量的度量：加、減、乘、除、比較的總運(yùn)算次數(shù)與實(shí)例的計(jì)算機(jī)計(jì)算時(shí)的二進(jìn)制輸入數(shù)據(jù)的大小關(guān)系。正整數(shù)x的二進(jìn)制位數(shù)是:(整數(shù)到二進(jìn)制的轉(zhuǎn)換),1.2計(jì)算復(fù)雜性的概念,算法計(jì)算量的度量之例——TSP枚舉法,計(jì)算量的統(tǒng)計(jì)：,1.2計(jì)算復(fù)雜性的概念,實(shí)例的輸入長(zhǎng)度：,實(shí)例的輸入長(zhǎng)度是n的多項(xiàng)式函數(shù)枚舉法的基本計(jì)算量是n的階乘函數(shù)，隨n的增加，比指數(shù)函數(shù)增加得還快.,1.2計(jì)算復(fù)雜性的概念,1.2計(jì)算復(fù)雜性的概念,定義多項(xiàng)式算法給定問(wèn)題P，算法A，對(duì)一個(gè)實(shí)例I，存在多項(xiàng)式函數(shù)g(x)，使（XX）成立，稱算法A對(duì)實(shí)例I是多項(xiàng)式算法；若存在多項(xiàng)式函數(shù)g(x)，使（XX）對(duì)問(wèn)題P的任意實(shí)例I都成立，稱算法A為解決該問(wèn)題P的多項(xiàng)式算法.當(dāng)g(x)為指數(shù)函數(shù)時(shí)，稱A為P的指數(shù)時(shí)間算法。,1.2計(jì)算復(fù)雜性的概念,利用復(fù)雜性分析對(duì)組合優(yōu)化問(wèn)題歸類。定義多項(xiàng)式問(wèn)題給定一個(gè)組合優(yōu)化問(wèn)題，若存在一個(gè)多項(xiàng)式算法，稱該問(wèn)題為多項(xiàng)式時(shí)間可解問(wèn)題，或簡(jiǎn)稱多項(xiàng)式問(wèn)題(或P問(wèn)題).所有多項(xiàng)式問(wèn)題的集合記為P.例：線性規(guī)劃是否為多項(xiàng)式問(wèn)題？,1.2計(jì)算復(fù)雜性參考書(shū),計(jì)算復(fù)雜性,作者：Christos，Papadimitriou清華大學(xué)出版社，2004年9月第1版計(jì)算復(fù)雜性導(dǎo)論，作者：堵丁柱等，高等教育出版社，2002年8月第1版,遺傳算法,基本思想關(guān)鍵技術(shù)算法步驟實(shí)例,,遺傳算法起源,遺傳算法是由美國(guó)的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。,遺傳算法基本思想,生物進(jìn)化過(guò)程模擬技術(shù),生物進(jìn)化過(guò)程,遺傳信息決定個(gè)體性能子代信息來(lái)自父代個(gè)體會(huì)發(fā)生變異通過(guò)自然選擇、適者生存具有整體尋優(yōu)性能,種群,父代群,,子群,單親、雙親繁殖,,優(yōu)勝劣汰,,,,,進(jìn)化過(guò)程,遺傳算法的搜索機(jī)制,遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。,模擬技術(shù),表示可行解初始子集合選擇標(biāo)準(zhǔn)生成新的子集合（選擇、交叉、變異）,編碼方式產(chǎn)生初始種群適應(yīng)度函數(shù)遺傳算子（選擇、交叉、變異）,編碼,GA是通過(guò)某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。,函數(shù)優(yōu)化示例,求下列一元函數(shù)的最大值：,x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。,GA對(duì)于本例的編碼,由于區(qū)間長(zhǎng)度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3106等份。又因?yàn)?21<3106<222，所以本例的二進(jìn)制編碼長(zhǎng)度至少需要22位，本例的編碼過(guò)程實(shí)質(zhì)上是將區(qū)間[-1，2]內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20…b0）。,幾個(gè)術(shù)語(yǔ),基因型：1000101110110101000111,表現(xiàn)型：0.637197,,,編碼,解碼,,個(gè)體（染色體）,,基因,初始種群,SGA采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為初始種群。初始種群中個(gè)體的數(shù)量稱為種群規(guī)模。,適應(yīng)度函數(shù),遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來(lái)評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過(guò)程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問(wèn)題本身的要求而定。,選擇算子,遺傳算法使用選擇運(yùn)算來(lái)實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。SGA中選擇算子采用輪盤(pán)賭選擇方法。,輪盤(pán)賭選擇方法,輪盤(pán)賭選擇又稱比例選擇算子，它的基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個(gè)體i的適應(yīng)度為Fi，則個(gè)體i被選中遺傳到下一代群體的概率為：,輪盤(pán)賭選擇方法的實(shí)現(xiàn)步驟,（1）計(jì)算群體中所有個(gè)體的適應(yīng)度函數(shù)值（需要解碼）；（2）利用比例選擇算子的公式，計(jì)算每個(gè)個(gè)體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤(pán)操作（即生成0到1之間的隨機(jī)數(shù)與每個(gè)個(gè)體遺傳到下一代群體的概率進(jìn)行匹配）來(lái)確定各個(gè)個(gè)體是否遺傳到下一代群體中。,交叉算子,所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。SGA中交叉算子采用單點(diǎn)交叉算子。,單點(diǎn)交叉運(yùn)算,交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000,交叉點(diǎn),變異算子,所謂變異運(yùn)算，是指依據(jù)變異概率Pm將個(gè)體編碼串中的某些基因值用其它基因值來(lái)替換，從而形成一個(gè)新的個(gè)體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。SGA中變異算子采用基本位變異算子。,基本位變異算子,基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。,基本位變異算子的執(zhí)行過(guò)程,變異前：000001110000000010000變異后：000001110001000010000,變異點(diǎn),運(yùn)行參數(shù),（1）M：種群規(guī)模（2）T：遺傳運(yùn)算的終止進(jìn)化代數(shù)（3）Pc：交叉概率（4）Pm：變異概率,算法步驟,3、遺傳算法的特點(diǎn),（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。,