數(shù)學(xué)建模算法介紹

數(shù)學(xué)建模算法介紹第1頁，共70頁，2023年，2月20日，星期六進化算法算法基礎(chǔ)遺傳算法第2頁，共70頁，2023年，2月20日，星期六算法基礎(chǔ)算法的概念算法分類算法的評價第3頁，共70頁，2023年，2月20日，星期六算法的概念算法—計算方法把求解問題的方法程式化、規(guī)范化算法是程序的依據(jù)、程序是算法的計算機實現(xiàn)算法思想與依據(jù)—實現(xiàn)技術(shù)—算法步驟算法構(gòu)成第4頁，共70頁，2023年，2月20日，星期六算法組成初始條件—指定參數(shù)、初始解迭代方法—轉(zhuǎn)移規(guī)則、生成新可行解的方法終止條件—最優(yōu)性條件或可接受條件輸出結(jié)果—最優(yōu)解或可接受解第5頁，共70頁，2023年，2月20日，星期六算法的分類構(gòu)造算法搜索算法啟發(fā)式算法進化算法第6頁，共70頁，2023年，2月20日，星期六構(gòu)造算法明確知道最優(yōu)解的結(jié)構(gòu)特征直接構(gòu)建最優(yōu)解，中間過程得到的是最優(yōu)解的部分，不是可行解；最小支撐樹的算法第7頁，共70頁，2023年，2月20日，星期六最小支撐樹的算法算法思想算法構(gòu)成關(guān)鍵技術(shù)第8頁，共70頁，2023年，2月20日，星期六算法思想依據(jù)--加上支撐樹外的任一邊構(gòu)成唯一的圈，樹外邊是該圈中權(quán)最大的。從權(quán)重小的邊開始加邊，新拿的邊如果和已加入的邊構(gòu)成圈就不加，否則就加入。第9頁，共70頁，2023年，2月20日，星期六關(guān)鍵技術(shù)選擇圈中最小的邊按權(quán)重從小到大排序判斷是否構(gòu)成圈第10頁，共70頁，2023年，2月20日，星期六算法構(gòu)成初始條件：已加邊集為空集，未拿邊集為全體邊迭代規(guī)則：從未拿的邊中選一個權(quán)重最小的，如果該邊與已加入邊構(gòu)成權(quán)就舍去，否則就加入停止規(guī)則：已加邊的個數(shù)等于頂點數(shù)減1或者沒有未拿邊輸出結(jié)果：已加邊集或沒有支撐樹第11頁，共70頁，2023年，2月20日，星期六搜索算法知道最優(yōu)解滿足的條件，但不知道其結(jié)構(gòu)從一個可行解出發(fā)按某種規(guī)則生成新的可行解直到滿足最優(yōu)性條件單純形算法第12頁，共70頁，2023年，2月20日，星期六單純形算法算法思想關(guān)鍵技術(shù)算法構(gòu)成第13頁，共70頁，2023年，2月20日，星期六算法思想從基可行解中找最優(yōu)解，從一個基可行解開始，判斷是否滿足最優(yōu)性條件，如果滿足就停止，否則看是否沒有最優(yōu)解，如果沒有最優(yōu)解就停止，否則生成一個新的最優(yōu)解第14頁，共70頁，2023年，2月20日，星期六關(guān)鍵技術(shù)初始基可行解計算檢驗數(shù)和典式生成新基可行解第15頁，共70頁，2023年，2月20日，星期六算法構(gòu)成初始條件：初始基可行解迭代方法：計算典式和檢驗數(shù)，找初級變量和入基變量終止條件：檢驗數(shù)小于等于零或檢驗數(shù)大于零的分量對應(yīng)典式列小于等于零輸出結(jié)果：最優(yōu)基可行解或沒有最優(yōu)解第16頁，共70頁，2023年，2月20日，星期六啟發(fā)式算法不知道最優(yōu)解的結(jié)構(gòu)和最優(yōu)性條件模擬人們的思路或經(jīng)驗貪心算法第17頁，共70頁，2023年，2月20日，星期六最短路貪心算法算法思想關(guān)鍵技術(shù)算法組成第18頁，共70頁，2023年，2月20日，星期六算法思想從起點開始，每一步都選最短的邊，直到終點第19頁，共70頁，2023年，2月20日，星期六關(guān)鍵技術(shù)確定每個點關(guān)聯(lián)的未選的邊中權(quán)重最小的第20頁，共70頁，2023年，2月20日，星期六算法構(gòu)成初始條件：已選邊為空集，當(dāng)前點為發(fā)點迭代規(guī)則：從當(dāng)前點出發(fā)的邊中選擇一個權(quán)重最小的邊，其頭部點為新的當(dāng)前點。如果沒有出點則返回上一個點重新選擇。終止條件：當(dāng)前點為終點，或當(dāng)前點沒有出發(fā)點輸出結(jié)果：一條從起點到終點的路或沒有路第21頁，共70頁，2023年，2月20日，星期六1.3啟發(fā)式算法_定義啟發(fā)式算法（heuristicalgorithm）定義1.基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費（時間、空間）下，給出待解組合優(yōu)化問題的每個實例的一個可行解，該可行解與最優(yōu)解偏差事先不一定可以預(yù)計.定義2.啟發(fā)式算法是一種技術(shù)，在可接受的計算費用內(nèi)尋找最好解，但不保證該解的可行性與最優(yōu)性，無法描述該解與最優(yōu)解的近似程度。特點（與傳統(tǒng)優(yōu)化方法不同）：憑直觀和經(jīng)驗給出算法；不考慮所得解與最優(yōu)解的偏離程度.第22頁，共70頁，2023年，2月20日，星期六1.3啟發(fā)式算法_優(yōu)點

優(yōu)點：（1）有可能比簡化數(shù)學(xué)模型解的誤差小；（2）對有些難題，計算時間可接受；（3）可用于某些最優(yōu)化算法（如分支定界算法）之中的估界；（4）直觀易行；（5）速度較快；（6）程序簡單，易修改。第23頁，共70頁，2023年，2月20日，星期六1.3啟發(fā)式算法_不足不足：（1）不能保證求得全局最優(yōu)解；（2）解的精度不穩(wěn)定，有時好有時壞；（3）算法設(shè)計與問題、設(shè)計者經(jīng)驗、技術(shù)有關(guān)，缺乏規(guī)律性；（4）不同算法之間難以比較。第24頁，共70頁，2023年，2月20日，星期六1.3啟發(fā)式算法_分類（1）一步算法（2）改進算法（迭代算法）（3）數(shù)學(xué)規(guī)劃算法（4）解空間松弛法

第25頁，共70頁，2023年，2月20日，星期六1.3啟發(fā)式算法_分類（5）現(xiàn)代優(yōu)化算法：80年代初興起禁忌搜索（tabusearch）模擬退火（simulatedannealing）遺傳算法（geneticalgorithms）神經(jīng)網(wǎng)絡(luò)（neuralnetworks）螞蟻算法（AntAlgorithm，群體（群集）智能，SwarmIntelligence）（6）其他算法：多種啟發(fā)式算法的集成.第26頁，共70頁，2023年，2月20日，星期六1.3啟發(fā)式算法_性能分析（1）最壞情形分析（worstcaseanalysis）利用最壞實例分析計算復(fù)雜性、解的效果。(2）概率分析（probabilityanalysis）

用最壞情況分析，會因一個最壞實例影響總體評價.在實例數(shù)據(jù)服從一定概率分布情形下，研究算法復(fù)雜性和解的效果.

(3)大規(guī)模計算分析通過大量實例計算，評價算法效果.注意數(shù)據(jù)的隨機性和代表性.第27頁，共70頁，2023年，2月20日，星期六進化算法不知道最優(yōu)解的結(jié)構(gòu)和最優(yōu)性條件模擬生物尋優(yōu)行為，大規(guī)模群體優(yōu)化群體搜索算法遺傳算法第28頁，共70頁，2023年，2月20日，星期六算法的評價結(jié)果評價復(fù)雜性評價第29頁，共70頁，2023年，2月20日，星期六結(jié)果評價全局最優(yōu)算法局部最優(yōu)算法近似算法有效算法第30頁，共70頁，2023年，2月20日，星期六全局最優(yōu)算法全局收斂算法得到全局最優(yōu)解或收斂到全局最優(yōu)解分支定界算法第31頁，共70頁，2023年，2月20日，星期六局部最優(yōu)解得到局部最優(yōu)解結(jié)果的好壞依賴初始解的選取非線性規(guī)劃搜索算法第32頁，共70頁，2023年，2月20日，星期六近似算法得到一個與最優(yōu)解的差距不超過一定比例的解需要說明與最優(yōu)解的差距復(fù)雜問題的多項時間算法第33頁，共70頁，2023年，2月20日，星期六可接受算法得到一個比較好的解無法說明與最優(yōu)解的差距貪心算法不需要太多的理論知識第34頁，共70頁，2023年，2月20日，星期六復(fù)雜性評價算法復(fù)雜性多項式時間算法非多項式時間算法第35頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念評價算法的好壞——計算時間的多少、解的偏離程度例非對稱距離TSP問題的算法實現(xiàn)：所有路徑枚舉。計算時間：n個城市，固定1個為起終點需要(n-1)!個枚舉，設(shè)計算機1秒能完成24個城市的枚舉，則城市數(shù)與計算時間的關(guān)系如下表：第36頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念城市數(shù)2425262728293031計算時間1sec24sec10min4.3hour4.9day136.5day10.8year325year隨城市增多，計算時間增加很快。到31個城市時，要計算325年。描述算法的好壞——計算復(fù)雜性——討論計算時間與問題規(guī)模之間的關(guān)系。以目前二進制計算機中的存儲和計算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評估算法性能的基礎(chǔ)。第37頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念問題（problem）：要回答的一般性提問，通常含有若干個滿足一定條件的參數(shù)（或自由變量）。可以從兩方面描述：（1）對所有參數(shù)的一般性描述；（2）答案（或解）必須滿足的性質(zhì)。實例（instance）:給問題的所有參數(shù)指定具體值，得到問題的一個實例。這些具體值稱為數(shù)據(jù)；這些數(shù)據(jù)輸入計算機所占的空間稱為實例的長度（size）.第38頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念一類最優(yōu)化問題是由一些類似的具體問題（實例）組成的，每一個具體問題可表達(dá)成二元組（F,C）.F為可行解集合;C是費用函數(shù)，是由F到R（實數(shù)集）的映像。問題是在F中找到一個點f*，使對F中任意的f，有C(f*)C(f),稱f*為這一具體問題的最優(yōu)解（或全局最優(yōu)解）.第39頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念算法計算量的度量：加、減、乘、除、比較的總運算次數(shù)與實例的計算機計算時的二進制輸入數(shù)據(jù)的大小關(guān)系。正整數(shù)x的二進制位數(shù)是:(整數(shù)到二進制的轉(zhuǎn)換)

第40頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念算法計算量的度量之例——TSP枚舉法計算量的統(tǒng)計：第41頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念實例的輸入長度：實例的輸入長度是n的多項式函數(shù)枚舉法的基本計算量是n的階乘函數(shù)，隨n的增加，比指數(shù)函數(shù)增加得還快.第42頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念第43頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念定義多項式算法給定問題P，算法A，對一個實例I，存在多項式函數(shù)g(x)，使（XX）成立，稱算法A對實例I是多項式算法；若存在多項式函數(shù)g(x)，使（XX）對問題P的任意實例I都成立，稱算法A為解決該問題P的多項式算法.當(dāng)g(x)為指數(shù)函數(shù)時，稱A為P的指數(shù)時間算法。第44頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性的概念利用復(fù)雜性分析對組合優(yōu)化問題歸類。定義多項式問題給定一個組合優(yōu)化問題，若存在一個多項式算法，稱該問題為多項式時間可解問題，或簡稱多項式問題(或P問題).所有多項式問題的集合記為P.例：線性規(guī)劃是否為多項式問題？第45頁，共70頁，2023年，2月20日，星期六1.2計算復(fù)雜性參考書計算復(fù)雜性,

作者：Christos，Papadimitriou

清華大學(xué)出版社，2004年9月第1版計算復(fù)雜性導(dǎo)論，作者：堵丁柱等，高等教育出版社，2002年8月第1版

第46頁，共70頁，2023年，2月20日，星期六遺傳算法基本思想關(guān)鍵技術(shù)算法步驟實例第47頁，共70頁，2023年，2月20日，星期六遺傳算法起源遺傳算法是由美國的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。第48頁，共70頁，2023年，2月20日，星期六遺傳算法基本思想生物進化過程模擬技術(shù)第49頁，共70頁，2023年，2月20日，星期六生物進化過程遺傳信息決定個體性能子代信息來自父代個體會發(fā)生變異通過自然選擇、適者生存具有整體尋優(yōu)性能種群父代群子群單親、雙親繁殖優(yōu)勝劣汰第50頁，共70頁，2023年，2月20日，星期六進化過程種群選擇父群子群交叉變異可行解子集合可行解子集合新解子集合選擇交叉、變異第51頁，共70頁，2023年，2月20日，星期六遺傳算法的搜索機制遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。

第52頁，共70頁，2023年，2月20日，星期六模擬技術(shù)表示可行解初始子集合選擇標(biāo)準(zhǔn)生成新的子集合（選擇、交叉、變異）編碼方式產(chǎn)生初始種群適應(yīng)度函數(shù)遺傳算子（選擇、交叉、變異）第53頁，共70頁，2023年，2月20日，星期六編碼GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進制串進行編碼。第54頁，共70頁，2023年，2月20日，星期六函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：

x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。第55頁，共70頁，2023年，2月20日，星期六GA對于本例的編碼由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222，所以本例的二進制編碼長度至少需要22位，本例的編碼過程實質(zhì)上是將區(qū)間[-1，2]內(nèi)對應(yīng)的實數(shù)值轉(zhuǎn)化為一個二進制串（b21b20…b0）。第56頁，共70頁，2023年，2月20日，星期六幾個術(shù)語基因型：1000101110110101000111表現(xiàn)型：0.637197編碼解碼個體（染色體）基因第57頁，共70頁，2023年，2月20日，星期六初始種群SGA采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。第58頁，共70頁，2023年，2月20日，星期六適應(yīng)度函數(shù)

遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。第59頁，共70頁，2023年，2月20日，星期六選擇算子遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。第60頁，共70頁，2023年，2月20日，星期六輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個體i的適應(yīng)度為Fi，則個體i被選中遺傳到下一代群體的概率為：第61頁，共70頁，2023年，2月20日，星期六輪盤賭選擇方法的實現(xiàn)步驟（1）計算群體中所有個體的適應(yīng)度函數(shù)值（需要解碼）；（2）利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機數(shù)與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。第62頁，共70頁，2023年，2月20日，星期六交叉算子所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。SGA中交叉算子采用單點交叉算子。第63頁，共70頁，2023年，2月20日，星期六單點交叉運算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點第64頁，共70頁，2023年，2月20日，星期六變異算子