現(xiàn)代優(yōu)化算法簡介PPT課件

1、v最優(yōu)化問題模型優(yōu)化問題概述min( )f x.( ) 0( ) 00iistg xh x或v全局最優(yōu)與局部最優(yōu) DxSRv實(shí)際生活中的優(yōu)化問題第1頁/共29頁組合優(yōu)化問題優(yōu)化模型 組合優(yōu)化（combinatorial optimization）:解決離散問題的優(yōu)化問題運(yùn)籌學(xué)分支。通過數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸和通信網(wǎng)絡(luò)等許多方面。 數(shù)學(xué)模型：決策變量有限點(diǎn)集約束函數(shù)目標(biāo)函數(shù), . , 0)(. . )( minDxxgtsxf第2頁/共29頁組合優(yōu)化問題 組合優(yōu)化問題的三參數(shù)表示： .| )(min)(,:,0)

2、(,|:),(FxxfxfFxxFxfxgDxxFDfFD最優(yōu)解，如果可行解（點(diǎn)）目標(biāo)函數(shù)有限點(diǎn)集可行域決策變量定義域第3頁/共29頁經(jīng)典的計(jì)算方法v17世紀(jì)Newtown 微積分v1847年 Cauchy 最速下降法v1947年 Dantzig 單純形方法v1939年 Kantorovich下料問題和運(yùn)輸問題 問題求解第4頁/共29頁傳統(tǒng)運(yùn)籌學(xué)面臨新挑戰(zhàn) 現(xiàn)代問題的特點(diǎn) 離散性問題主要以組合優(yōu)化（針對離散問題，定義見后）理論為基礎(chǔ) 不確定性問題隨機(jī)性數(shù)學(xué)模型 半結(jié)構(gòu)或非結(jié)構(gòu)化的問題計(jì)算機(jī)模擬、決 策支持系統(tǒng) 大規(guī)模問題并行計(jì)算、大型分解理論、近似理論 現(xiàn)代優(yōu)化方法 追求滿意近似解 實(shí)用性強(qiáng)解

3、決實(shí)際問題 現(xiàn)代優(yōu)化算法的評價方法 算法復(fù)雜性第5頁/共29頁1、蒙特卡羅算法（該算法又稱隨機(jī)性模擬算法，是通過計(jì)算機(jī)仿真來解決問題的算法，同時可以通過模擬可以來檢驗(yàn)自己模型的正確性，是比賽時必用的方法）2、數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(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)）4、圖論算法（這類算法可以分為很多種，包括最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論

4、的問題可以用這些方法解決，需要認(rèn)真準(zhǔn)備）計(jì)算機(jī)上的常用算法：第6頁/共29頁5、動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計(jì)算機(jī)算法（這些算法是算法設(shè)計(jì)中比較常用的方法，很多場合可以用到競賽中） 6、最優(yōu)化理論的三大非經(jīng)典算法：模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法（這些問題是用來解決一些較困難的最優(yōu)化問題的算法，對于有些問題非常有幫助，但是算法的實(shí)現(xiàn)比較困難，需慎重使用）7、數(shù)值分析算法（如果在比賽中采用高級語言進(jìn)行編程的話，那一些數(shù)值分析中常用的算法比如方程組求解、矩陣運(yùn)算、函數(shù)積分等算法就需要額外編寫庫函數(shù)進(jìn)行調(diào)用） 8、一些連續(xù)離散化方法（很多問題都是實(shí)際來的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只認(rèn)的是

5、離散的數(shù)據(jù)，因此將其離散化后進(jìn)行差分代替微分、求和代替積分等思想是非常重要的）第7頁/共29頁9、網(wǎng)格算法和窮舉法（網(wǎng)格算法和窮舉法都是暴力搜索最優(yōu)點(diǎn)的算法，在很多競賽題中有應(yīng)用，當(dāng)重點(diǎn)討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具）10、圖象處理算法（賽題中有一類問題與圖形有關(guān)，即使與圖形無關(guān)，論文中也應(yīng)該要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進(jìn)行處理）第8頁/共29頁背 景 傳統(tǒng)實(shí)際問題的特點(diǎn) 連續(xù)性問題主要以微積分為基礎(chǔ)，且問題規(guī)模較小 傳統(tǒng)的優(yōu)化方法 追求準(zhǔn)確精確解 理論的完美結(jié)果漂亮 主要方法：線性與非

6、線性規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫存論、對策論、決策論等。 傳統(tǒng)的評價方法 算法收斂性（從極限角度考慮） 收斂速度（線性、超線性、二次收斂等）第9頁/共29頁啟發(fā)式計(jì)算方法【定義1-1】 啟發(fā)式算法是一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的耗費(fèi)（指計(jì)算時間、占用空間等）下給出待解決優(yōu)化問題每一實(shí)例的一個可行解，該可行解與最優(yōu)解的偏離程度未必可事先估計(jì)?！径x1-2】 啟發(fā)式算法是一種技術(shù)，該技術(shù)使得能在可接受的計(jì)算費(fèi)用內(nèi)去尋找盡可能好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法描述所得解與最優(yōu)解的近似程度。經(jīng)典的啟發(fā)式方法基本原理:根據(jù)問題的部分已知信

7、息來啟發(fā)式地探索該問題的解決方案，在探索解決方案的過程中將發(fā)現(xiàn)的有關(guān)信息記錄下來，不斷積累和分析，并根據(jù)越來越豐富的已知信息來指導(dǎo)下一步的動作并修正以前的步驟，從而獲得在整體上較好的解決方案。第10頁/共29頁啟發(fā)式算法_ _優(yōu)點(diǎn) 優(yōu)點(diǎn)： （1）有可能比簡化數(shù)學(xué)模型解的誤差??； （2）對有些難題，計(jì)算時間可接受； （3）可用于某些最優(yōu)化算法（如分支定界算 法）之中的估界； （4）直觀易行； （5）速度較快； （6）程序簡單，易修改。第11頁/共29頁啟發(fā)式算法_ _不足 不足： （1）不能保證求得全局最優(yōu)解； （2）解的精度不穩(wěn)定，有時好有時壞； （3）算法設(shè)計(jì)與問題、設(shè)計(jì)者經(jīng)驗(yàn)、技術(shù) 有關(guān)，

8、缺乏規(guī)律性； （4）不同算法之間難以比較。第12頁/共29頁可應(yīng)用那些問題 可應(yīng)用那些問題 NP問題 不存在多項(xiàng)式算法的問題,典型問題如背包問題,周游問題,選址問題等 某些高階多項(xiàng)式算法問題 .如對應(yīng)算法時間復(fù)雜度超過4階以上,此時利用普通算法在有效時間內(nèi)可能不能得到結(jié)果 那些問題不適合使用 .求解為精確解 .不是優(yōu)化模型問題 .有低階多項(xiàng)式算法第13頁/共29頁當(dāng)前進(jìn)化算法新進(jìn)展 多目標(biāo)優(yōu)化 動態(tài)環(huán)境下優(yōu)化 大規(guī)模超大規(guī)模優(yōu)化 不確定環(huán)境下優(yōu)化 .第14頁/共29頁生物啟發(fā)式優(yōu)化方法v遺傳算法v神經(jīng)網(wǎng)絡(luò)v模糊邏輯v。生物啟發(fā)式計(jì)算是指以生物界的各種自然現(xiàn)象或過程為靈感，而提出的一系列啟發(fā)式智

9、能計(jì)算方法。第15頁/共29頁遺傳算法進(jìn)化過程優(yōu)化過程生物進(jìn)化過程是一個自然，并行，穩(wěn)健的優(yōu)化過程，這一優(yōu)化過程的目的在于使生命體達(dá)到適應(yīng)環(huán)境的最佳結(jié)構(gòu)與效果，而生物種群通過” “優(yōu)勝劣汰”及遺傳變異來達(dá)到進(jìn)化（優(yōu)化）目的的。第16頁/共29頁遺傳算法+=生物的進(jìn)化機(jī)制u自然選擇 適應(yīng)環(huán)境的個體具有更高的生存能力，同時染色體特征被保留下來u雜交 隨機(jī)組合來自父代的染色體上的遺傳物質(zhì)，產(chǎn)生不同于它們父代的染色體u突變 隨機(jī)改變父代的染色體基因結(jié)構(gòu)，產(chǎn)生新染色體第17頁/共29頁神經(jīng)計(jì)算樹突 突觸 軸突 細(xì)胞體人工神經(jīng)網(wǎng)絡(luò)是由 具有適應(yīng)性的簡單單元組成的廣泛并行互連的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)

10、系統(tǒng)對真實(shí)世界物體所作出的交互反應(yīng)。細(xì)胞體突觸軸突樹突圖12.2 生物神經(jīng)元功能模型輸入輸出信息處理電脈沖形成傳輸?shù)?8頁/共29頁神經(jīng)計(jì)算 人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Networks, ANN），一種模范動物神經(jīng)網(wǎng)絡(luò)行為特征，進(jìn)行分布式并行信息處理的算法數(shù)學(xué)模型。這種網(wǎng)絡(luò)依靠系統(tǒng)的復(fù)雜程度，通過調(diào)整內(nèi)部大量節(jié)點(diǎn)之間相互連接的關(guān)系，從而達(dá)到處理信息的目的。人工神經(jīng)網(wǎng)絡(luò)具有自學(xué)習(xí)和自適應(yīng)的能力。IN1NjjjxwIxT？1w2w3w4wI1I2I3S第19頁/共29頁模糊邏輯x集結(jié)器去模糊化y規(guī)則1xxx規(guī)則2規(guī)則r 模糊推理系統(tǒng)是建立在模糊集合理論、模糊if-then規(guī)

11、則和模糊推理等概念基礎(chǔ)上的先進(jìn)的計(jì)算框架。 模糊推理系統(tǒng)的基本結(jié)構(gòu)由三個重要部件組成：一個規(guī)則庫，包含一系列模糊規(guī)則；一個數(shù)據(jù)庫，定義模糊規(guī)則中用到的隸屬度函數(shù)（Membership Functions, MF）；以及一個推理機(jī)制，按照規(guī)則和所給事實(shí)執(zhí)行推理過程求得合理的輸出或結(jié)論 。第20頁/共29頁其它生物啟發(fā)式計(jì)算技術(shù)v進(jìn)化規(guī)劃算法v進(jìn)化編程v人工免疫系統(tǒng)vDNA計(jì)算v膜計(jì)算等第21頁/共29頁群體智能（Swarm Intelligence）生物學(xué)家研究表明：在這些群居生物中雖然每個個體的智能不高，行為簡單，也不存在集中的指揮，但由這些單個個體組成的群體，似乎在某種內(nèi)在規(guī)律的作用下，卻表現(xiàn)出異常復(fù)雜而有序的群體行為。第22頁/共29頁AC第23頁/共29頁otherwise 0allowed if )(allowed)()(jtpjijijijijttkij),()()(ijntttntijij軌跡更新:Visibility: ij = 1/dij螞蟻算法表示軌跡的相對重要性表示能見度的相對重要性軌跡的持久性ij表示第K只螞蟻在本次循環(huán)中留在路徑ij上的信息量第24頁/共29頁生物社會學(xué)家E.O.Wilson指出：“至少從理論上，在搜索食物過程中群體中個體成員可以得益于所有其他成員的發(fā)