[農(nóng)學(xué)]第一章__緒論ppt課件

1、課程定位課程定位 處理的問題：優(yōu)化問題處理的問題：優(yōu)化問題 處理的方法：智能方法處理的方法：智能方法 數(shù)學(xué)工具數(shù)學(xué)工具 適用方法適用方法考核方式考核方式 筆試筆試 優(yōu)化技術(shù)？優(yōu)化技術(shù)？ 以數(shù)學(xué)為根底，處理各種工程問題優(yōu)化解以數(shù)學(xué)為根底，處理各種工程問題優(yōu)化解優(yōu)化技術(shù)的用途優(yōu)化技術(shù)的用途 系統(tǒng)控制系統(tǒng)控制 人工智能人工智能 方式識(shí)別方式識(shí)別 消費(fèi)調(diào)度消費(fèi)調(diào)度 最優(yōu)化問題的描畫最優(yōu)化問題的描畫 最優(yōu)化問題的數(shù)學(xué)模型的普通描畫：最優(yōu)化問題的數(shù)學(xué)模型的普通描畫：Dxxgtsxf ,0)( .)( min即：討論求函數(shù)即：討論求函數(shù)f(x)的最小值問題，的最小值問題，即確定即確定xD,使使F(x*)=m

2、inF(x),g(x)=nxxFxxF)(.)(1g(x)是是F(x)的梯度的梯度待處理的問題待處理的問題 延續(xù)性問題，以微積分為根底，規(guī)模較小延續(xù)性問題，以微積分為根底，規(guī)模較小傳統(tǒng)的優(yōu)化方法傳統(tǒng)的優(yōu)化方法 實(shí)際上的準(zhǔn)確與完美，主要方法：線性與非線實(shí)際上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目的規(guī)劃、整數(shù)規(guī)劃等；排性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目的規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫存論、對策論、決策論等。隊(duì)論、庫存論、對策論、決策論等。 傳統(tǒng)的評價(jià)方法傳統(tǒng)的評價(jià)方法 算法收斂性、收斂速度算法收斂性、收斂速度待處理的問題待處理的問題 離散性、不確定性、大規(guī)模離散性、不確定性、大規(guī)?，F(xiàn)代的優(yōu)化方

3、法現(xiàn)代的優(yōu)化方法 啟發(fā)式算法啟發(fā)式算法heuristic algorithm 追求稱心近似解追求稱心近似解 適用性強(qiáng)處理實(shí)踐工程問題適用性強(qiáng)處理實(shí)踐工程問題 現(xiàn)代的評價(jià)方法現(xiàn)代的評價(jià)方法 算法復(fù)雜性算法復(fù)雜性數(shù)學(xué)表述數(shù)學(xué)表述難點(diǎn)難點(diǎn) 高維高維 多峰值多峰值 的定義域），上的有界子集（即變量為令nRS域上在維實(shí)值函數(shù)，所謂函數(shù)為SfnRSf:在使得全局最小化就是尋求點(diǎn))(minminXfSX。域上全局最小，即)()(:minXfXfSXS測試函數(shù)測試函數(shù)Benchmark問題問題 1Sphere Model 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為100| ,)(12iniixxXf0)0 ,

4、0 , 0()(min(*fXf測試函數(shù)測試函數(shù) 2Schwefels Problem 2.22 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為0)0 , 0 , 0()(min(*fXf10| , |)(11ininiiixxxXf測試函數(shù)測試函數(shù) 3Schwefels Problem 1.2 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為0)0 , 0 , 0()(min(*fXf100| ,)()(211 iniijjxxXf測試函數(shù)測試函數(shù) 4Schwefels Problem 2.21 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為0)0 , 0 , 0()(min(*fXf100| |,|max)(

5、1iinixxXf測試函數(shù)測試函數(shù) 5Generalized Rosenbrocks Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為30| , )1 ()(100)(112221iniiiixxxxXf0) 1 , 1 , 1 ()(min(*fXf測試函數(shù)測試函數(shù) 6Step Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為100| ,)5 . 0()(12iniixxXf0)0 , 0 , 0()(min(*fXf測試函數(shù)測試函數(shù) 6Step Function 測試函數(shù)測試函數(shù) 7Quartic Function i.e. Niose 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和

6、最優(yōu)值為28. 1| , ) 1 , 0)(14iniixrandomixXf0)0 , 0 , 0()(min(*fXf測試函數(shù)測試函數(shù) 8Generalized Schwefels Problem 2.26 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為500| ,)sin()(1iniiixxxXfnfXf9829.418 )9687.420,9687.420,9687.420()(min(*測試函數(shù)測試函數(shù) 8Generalized Schwefels Problem 2.26 測試函數(shù)測試函數(shù) 9Generalized Rastrigins Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀

7、和最優(yōu)值為12. 5| , 10)2cos(10)(12iniiixxxXf0)0 , 0 , 0()(min(*fXf測試函數(shù)測試函數(shù) 10Ackleys Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為32| ,20)/ )2cos(exp()/2 . 0exp(20)(112iniiniixenxnxXf0)0 , 0 , 0()(min(*fXf測試函數(shù)測試函數(shù) 10Ackleys Function 測試函數(shù)測試函數(shù) 11Generalized Griewank Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為600| , 1cos40001)(112iininii

8、xixxXf0)0 , 0 , 0()(min(*fXf測試函數(shù)測試函數(shù) 11Generalized Griewank Function 測試函數(shù)測試函數(shù) 12Generalized Penalized Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為50| , )4 ,100,10,( ) 1()(sin101 ) 1()(sin10)(111212212iniininiixxuyyyynXf0) 1 , 1 , 1 ()(min(*fXf測試函數(shù)測試函數(shù) 其中，其中，axaxkaxaaxaxkmkaxuxyimiiimiiii ,)( , 0 ,)(),(4/ ) 1(1測試函數(shù)

9、測試函數(shù) 13Generalized Penalized Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為同上)(,50| , )4 ,100, 5 ,( ) 1()3(sin1 ) 1()3(sin1 . 0)(111212212uxxuxxxxXfiniininii0) 1 , 1 , 1 ()(min(*fXf測試函數(shù)測試函數(shù) 14Shekels Foxholes Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為56.65| ,)(15001)(1251216ijiijixaxjXf1)32,32()(min(* fXf測試函數(shù)測試函數(shù) 其中，其中，3232,32,1

10、6,32, 0,32,16,32,32,16,32,16,16,16, 0,16,16,16,32, 0,32, 0,16, 0, 0, 0,16, 0,32 ,16,32,16,16,16, 0,16,16,16,32,32,32,32,16,32, 0,32,16,32,32)(ija測試函數(shù)測試函數(shù) 15Kowaliks Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為5| ,)()(1112432221iiiiiiixxxbbxbbxaXf0003075. 0)1358. 0 ,1231. 0 ,1928. 0 ,1928. 0()(min(* fXf測試函數(shù)測試函數(shù) 其中，

11、其中，)16,14,12,10, 8 , 6 , 4 , 2 , 1 , 5 . 0 ,25. 0()/1 ()0246. 0 ,0235. 0 ,0323. 0 ,0342. 0 ,0456. 0 ,0627. 0 ,0844. 0 ,16. 0 ,1735. 0 ,1947. 0 ,1957. 0()(iiba測試函數(shù)測試函數(shù) 16Six-Hump Camel-Back Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為5| ,443/1 . 24)(422221614121ixxxxxxxxXf0316285. 1 )7126. 0 ,08983. 0( )7126. 0,089

12、83. 0()(min(*ffXf測試函數(shù)測試函數(shù) 17Branin Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為150 ,105 ,10cos811106541 . 5)(211212122xxxxxxXf398. 0)425. 2 ,425. 9( )275. 2 ,142. 3()275. 2 ,142. 3()(min(*fffXf測試函數(shù)測試函數(shù) 18Goldstein-Price Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為2 ),273648123218()32(30 )361431419() 1(1 )(2221221122122212211221i

13、xxxxxxxxxxxxxxxxxXf3) 1, 0()(min(* fXf測試函數(shù)測試函數(shù) 19Hartmans Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為10 ,)(exp)(41312jijijjijixpxacXf86. 3)852. 0 ,556. 0 ,114. 0()(min(* fXf測試函數(shù)測試函數(shù) 其中，其中，8828. 05547. 07470. 02673. 0,5743. 0,8732. 0,4387. 0,1170. 0,03815. 0,1090. 0,4699. 0,3689. 0)(),2 . 3 , 3 , 2 . 1 , 1 ()( ,35

14、303530,10,10,10,10, 1 . 0, 3, 1 . 0, 3)(ijiijpca測試函數(shù)測試函數(shù) 20Hartmans Function 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為10 ,)(exp)(41612jijijjijixpxacXf32. 3)657. 0 ,311. 0 ,275. 0 ,477. 0 ,15. 0 ,201. 0()(min(* fXf測試函數(shù)測試函數(shù) 其中，其中，0381. 06650. 09991. 05886. 0,1091. 0,3047. 0,1004. 0,8283. 0,5743. 0,2883. 0,3736. 0,0124. 0,

15、8732. 0,3522. 0,8307. 0,5569. 0,8828. 0,1415. 0,4135. 0,1696. 0,4047. 0,2348. 0,2329. 0,1312. 0)(),2 . 3 , 3 , 2 . 1 , 1 ()( ,148148, 1 . 0,17, 8, 7 . 1,10,10, 1 . 0, 5 . 3,05. 0, 7 . 1,17,17, 8, 5 . 3,10, 3,17, 3,05. 0,10)(ijiijpca測試函數(shù)測試函數(shù) 21Shekels Family m分別取分別取5，7和和10，其最優(yōu)形狀和最優(yōu)，其最優(yōu)形狀和最優(yōu)值為值為100 ,)

16、()(11xcaxaxXfmiiTiimicafXfii1 ,/1)()(min(*測試函數(shù)測試函數(shù) 其中，其中，iaijcij=1234144440.1211110.2388880.2466660.4537370.4629290.6755330.3881810.7962620.51073.673.60.5測試函數(shù)測試函數(shù) 22J. D. Schaffer 其最優(yōu)形狀和最優(yōu)值為其最優(yōu)形狀和最優(yōu)值為 100| , 5 . 0)(001. 01 5 . 0sin)(2222122212ixxxxxXf1)0 , 0()(min(* fXf測試函數(shù)測試函數(shù) 22J. D. Schaffer 此函數(shù)在

17、距全局最優(yōu)點(diǎn)大約此函數(shù)在距全局最優(yōu)點(diǎn)大約3.14范圍內(nèi)存范圍內(nèi)存在無窮多個(gè)部分極小將其包圍，并且函數(shù)劇烈振蕩。在無窮多個(gè)部分極小將其包圍，并且函數(shù)劇烈振蕩。有約束的函數(shù)優(yōu)化有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)；常用受約束測試函數(shù)； 影響要素：影響要素： 1曲面拓?fù)湫再|(zhì)，線性或凸函數(shù)比無規(guī)律的曲面拓?fù)湫再|(zhì)，線性或凸函數(shù)比無規(guī)律的函數(shù)更容易求解；函數(shù)更容易求解； 2可行區(qū)域的疏密程度，通常以可行區(qū)域占可行區(qū)域的疏密程度，通常以可行區(qū)域占整個(gè)搜索空間的比值來度量；整個(gè)搜索空間的比值來度量； 有約束的函數(shù)優(yōu)化有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)；常用受約束測試函數(shù)； 影響要素：影響要素： 3整體最優(yōu)解

18、與可行區(qū)域最優(yōu)解之比；整體最優(yōu)解與可行區(qū)域最優(yōu)解之比； 4在最優(yōu)解處活潑約束的數(shù)目，活潑約束數(shù)在最優(yōu)解處活潑約束的數(shù)目，活潑約束數(shù)目越多那么最優(yōu)解離可行區(qū)域的邊境越近。目越多那么最優(yōu)解離可行區(qū)域的邊境越近。 數(shù)學(xué)表述數(shù)學(xué)表述所屬范疇所屬范疇 涉及離散事件的最優(yōu)編排、分類、次序挑選等涉及離散事件的最優(yōu)編排、分類、次序挑選等問題，是運(yùn)籌學(xué)的一個(gè)重要分支。問題，是運(yùn)籌學(xué)的一個(gè)重要分支。 ，構(gòu)成,21的解空間為所有狀態(tài)令ns,ss要求尋找最對應(yīng)的目標(biāo)函數(shù)值為狀態(tài),)(iissC。使得優(yōu)解)(min)(,*iisCsCss典型問題典型問題游覽商問題游覽商問題Traveling salesman prob

19、lem, TSP 給定給定n個(gè)城市和兩兩個(gè)城市和兩兩 城市之間的間隔，要城市之間的間隔，要 求確定一條經(jīng)過各城求確定一條經(jīng)過各城 市當(dāng)且僅當(dāng)一次的最市當(dāng)且僅當(dāng)一次的最 短道路。短道路。123412181032典型問題典型問題游覽商問題游覽商問題Traveling salesman problem, TSP 計(jì)算復(fù)雜度：指數(shù)災(zāi)難計(jì)算復(fù)雜度：指數(shù)災(zāi)難城市數(shù)2425262728293031計(jì)算時(shí)間1sec24sec10min4.3hour4.9day136.5day10.8year325year典型問題典型問題加工調(diào)度問題加工調(diào)度問題Scheduling problem,如如Flow-shop, J

20、ob-shop Job-shop：n個(gè)工件在個(gè)工件在m臺(tái)機(jī)器上加工，臺(tái)機(jī)器上加工，Oij：第第i個(gè)工件在第個(gè)工件在第j臺(tái)機(jī)器上的操作，臺(tái)機(jī)器上的操作， Tij：相應(yīng)的操作：相應(yīng)的操作時(shí)間，知。事先給定各工件在各機(jī)器上的加工次序時(shí)間，知。事先給定各工件在各機(jī)器上的加工次序技術(shù)約束條件，要求確定與技術(shù)約束條件相容技術(shù)約束條件，要求確定與技術(shù)約束條件相容的各機(jī)器上一切工件的加工順序，使得加工性能目的各機(jī)器上一切工件的加工順序，使得加工性能目的到達(dá)最優(yōu)。的到達(dá)最優(yōu)。 假設(shè)各工件技術(shù)約束條件一樣，轉(zhuǎn)化為假設(shè)各工件技術(shù)約束條件一樣，轉(zhuǎn)化為Flow-shop。典型問題典型問題加工調(diào)度問題加工調(diào)度問題Sche

21、duling problem,如如Flow-shop, Job-shop 計(jì)算復(fù)雜性：能夠的陳列方式有計(jì)算復(fù)雜性：能夠的陳列方式有n！m 多目的優(yōu)化多目的優(yōu)化 動(dòng)態(tài)性動(dòng)態(tài)性 形狀相依形狀相依典型問題典型問題01背包問題背包問題Knapsack problem 對于對于n個(gè)體積為個(gè)體積為ai、價(jià)值分別為、價(jià)值分別為ci的物品，如何的物品，如何將它們裝入總體積為將它們裝入總體積為b的背包中，使得所選物品的的背包中，使得所選物品的總價(jià)值最大?？們r(jià)值最大。背包問題的貪婪算法背包問題的貪婪算法典型問題典型問題裝箱問題裝箱問題Bin packing problem 有有n個(gè)尺寸不超越個(gè)尺寸不超越1的物品，

22、有數(shù)個(gè)尺寸為的物品，有數(shù)個(gè)尺寸為1的箱的箱子，如何將這些物品裝入箱子，使得所需箱子的個(gè)子，如何將這些物品裝入箱子，使得所需箱子的個(gè)數(shù)最少。數(shù)最少。典型問題典型問題圖著色問題圖著色問題Graph coloring problem 對于對于n個(gè)頂點(diǎn)的無環(huán)圖個(gè)頂點(diǎn)的無環(huán)圖G，要求對其各個(gè)頂點(diǎn)進(jìn)，要求對其各個(gè)頂點(diǎn)進(jìn)展著色，使得恣意兩個(gè)相鄰的頂點(diǎn)都有不同的顏色，展著色，使得恣意兩個(gè)相鄰的頂點(diǎn)都有不同的顏色，且所用顏色種類最少。且所用顏色種類最少。C1：第一種顏色：第一種顏色C2：第二種顏色：第二種顏色C3：第三種顏色：第三種顏色C1C1C2C3C2ABDCE典型問題典型問題聚類問題聚類問題Cluster

23、ing problem m維空間上的維空間上的n個(gè)方式個(gè)方式Xi|i=1,2,n，要求聚成，要求聚成k類，使得各類本身內(nèi)的點(diǎn)最相近，如要求類，使得各類本身內(nèi)的點(diǎn)最相近，如要求 其中其中Rp為第為第p類的中心，即類的中心，即 其中，其中，p=1,2,k，np為第為第p類中的點(diǎn)數(shù)。類中的點(diǎn)數(shù)。最小 1)(2nippiRXpnippipnXR1)(/Benchmark問題問題 n城市城市TSP問題問題n=30，50，75 Hopfield-10城市城市TSP問題問題 Grotschel-442城市城市TSP問題問題 Car n Flow-shop問題問題n=1,2,8 Rec n Flow-shop

24、問題問題n=1,3,5,39,41 FT n or MT n Job-shop問題問題n=6,10,20 LA n Job-shop問題問題n=1,6,11,16,21,26,31,3630城市城市TSP問題問題d*=423.741 by D B Fogel 41 94; 37 84; 54 67; 25 62; 7 64; 2 99; 68 58; 71 44; 54 62; 83 69; 64 60; 18 54; 22 60; 83 46; 91 38; 25 38; 24 42; 58 69; 71 71; 74 78; 87 76; 18 40; 13 40; 82 7; 62 32

25、; 58 35; 45 21; 41 26; 44 35; 4 50最優(yōu)算法最優(yōu)算法 一個(gè)問題的最優(yōu)算法求得該問題每個(gè)實(shí)例的最一個(gè)問題的最優(yōu)算法求得該問題每個(gè)實(shí)例的最優(yōu)解；優(yōu)解；啟發(fā)式算法啟發(fā)式算法 一個(gè)基于直觀或閱歷構(gòu)造的算法，在可接受的一個(gè)基于直觀或閱歷構(gòu)造的算法，在可接受的破費(fèi)計(jì)算時(shí)間、占用空間等下給出待處理優(yōu)化破費(fèi)計(jì)算時(shí)間、占用空間等下給出待處理優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解問題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以估計(jì)。的偏離程度不一定事先可以估計(jì)。啟發(fā)式算法的特點(diǎn)啟發(fā)式算法的特點(diǎn) 是一種技術(shù)；是一種技術(shù)； 不能保證所得解的最優(yōu)性；不能保證

26、所得解的最優(yōu)性；啟發(fā)式算法的開展歷史啟發(fā)式算法的開展歷史 20世紀(jì)世紀(jì)40年代年代起步起步 20世紀(jì)世紀(jì)6070年代年代被輕視被輕視 20世紀(jì)世紀(jì)70年代年代觀念轉(zhuǎn)變觀念轉(zhuǎn)變 20世紀(jì)世紀(jì)80年代至今年代至今研討熱潮研討熱潮例子例子背包問題的貪婪算法背包問題的貪婪算法Greedy algorithm 貪婪算法：采用逐漸構(gòu)造最優(yōu)解的方法。貪婪算法：采用逐漸構(gòu)造最優(yōu)解的方法。 在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策在一定的規(guī)范下。決策一旦作出，就不可再策在一定的規(guī)范下。決策一旦作出，就不可再更改。作出貪婪決策的根據(jù)稱為貪婪準(zhǔn)那么更改。作出貪婪決策的根據(jù)稱為貪婪準(zhǔn)

27、那么greedy criterion。例子例子背包問題的貪婪算法背包問題的貪婪算法Greedy algorithmSTEP 1 STEP 2; 1:, 2 , 1knacii記成排列從大到小排列，不妨把對物品以。時(shí)，停止；否則，重復(fù)；當(dāng)，；否則則，若STEP211:01 11nkkkxxbaxakkkikii啟發(fā)式算法的優(yōu)點(diǎn)啟發(fā)式算法的優(yōu)點(diǎn) 1. 模型誤差、數(shù)據(jù)不準(zhǔn)確性、參數(shù)估計(jì)誤差等能模型誤差、數(shù)據(jù)不準(zhǔn)確性、參數(shù)估計(jì)誤差等能夠呵斥最優(yōu)算法的解比啟發(fā)式算法的解更差；夠呵斥最優(yōu)算法的解比啟發(fā)式算法的解更差； 2. 復(fù)雜問題無法求得最優(yōu)算法或最優(yōu)算法太復(fù)雜；復(fù)雜問題無法求得最優(yōu)算法或最優(yōu)算法太復(fù)雜

28、； 3. 簡單易行，直觀，程序簡單。簡單易行，直觀，程序簡單。 啟發(fā)式算法的缺陷啟發(fā)式算法的缺陷 1. 不能保證最優(yōu)；不能保證最優(yōu)； 2. 不穩(wěn)定；不穩(wěn)定； 3. 依賴于實(shí)踐問題、設(shè)計(jì)者閱歷。依賴于實(shí)踐問題、設(shè)計(jì)者閱歷。 簡單直觀的算法簡單直觀的算法 一步算法：不在兩個(gè)可行解之間比較，在未終一步算法：不在兩個(gè)可行解之間比較，在未終止的迭代過程中，得到的中間解有能夠不是可行解；止的迭代過程中，得到的中間解有能夠不是可行解； 例：背包問題的貪婪算法例：背包問題的貪婪算法 改良算法：迭代過程是從一個(gè)可行解到另一個(gè)改良算法：迭代過程是從一個(gè)可行解到另一個(gè)可行解變換，經(jīng)過兩個(gè)解的比較而選擇好的解，直可行

29、解變換，經(jīng)過兩個(gè)解的比較而選擇好的解，直到滿足一定的要求為止；到滿足一定的要求為止； 例：例：TSP問題的問題的2opt方法方法數(shù)學(xué)規(guī)劃算法數(shù)學(xué)規(guī)劃算法 用延續(xù)優(yōu)化如線性規(guī)劃的方法求解組合優(yōu)用延續(xù)優(yōu)化如線性規(guī)劃的方法求解組合優(yōu)化問題如整數(shù)線性規(guī)劃模型，其中包括一些啟化問題如整數(shù)線性規(guī)劃模型，其中包括一些啟發(fā)式規(guī)那么。發(fā)式規(guī)那么。 基于數(shù)學(xué)規(guī)劃的實(shí)際?；跀?shù)學(xué)規(guī)劃的實(shí)際。 現(xiàn)代優(yōu)化算法現(xiàn)代優(yōu)化算法 忌諱搜索算法忌諱搜索算法 模擬退火算法模擬退火算法 遺傳算法遺傳算法 人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò) 蟻群算法蟻群算法 粒子群算法粒子群算法 混合算法混合算法 特點(diǎn)：特點(diǎn)：基于客觀世界中的一些自基于客觀世界

30、中的一些自然景象；然景象；建立在計(jì)算機(jī)迭代計(jì)算的建立在計(jì)算機(jī)迭代計(jì)算的根底上；根底上；具有普適性，可處理實(shí)踐具有普適性，可處理實(shí)踐運(yùn)用問題。運(yùn)用問題。評價(jià)算法優(yōu)劣的目的評價(jià)算法優(yōu)劣的目的 算法的復(fù)雜性計(jì)算效率算法的復(fù)雜性計(jì)算效率 解的偏離程度計(jì)算效果解的偏離程度計(jì)算效果 算法的穩(wěn)健性不同實(shí)例、不同時(shí)間、不同起算法的穩(wěn)健性不同實(shí)例、不同時(shí)間、不同起點(diǎn)的差別點(diǎn)的差別評價(jià)算法優(yōu)劣的手段評價(jià)算法優(yōu)劣的手段 最壞情況分析純實(shí)際最壞情況分析純實(shí)際 概率分析實(shí)際分析概率分析實(shí)際分析 計(jì)算模擬分析統(tǒng)計(jì)特性計(jì)算模擬分析統(tǒng)計(jì)特性時(shí)間復(fù)雜性和空間復(fù)雜性概念時(shí)間復(fù)雜性和空間復(fù)雜性概念 算法的時(shí)間復(fù)雜性：算法對時(shí)間的需

31、求量加、算法的時(shí)間復(fù)雜性：算法對時(shí)間的需求量加、減、乘、除、比較、讀、寫等操作的總次數(shù)；減、乘、除、比較、讀、寫等操作的總次數(shù)； 算法的空間復(fù)雜性：算法對空間的需求量存算法的空間復(fù)雜性：算法對空間的需求量存儲(chǔ)空間的大小，二進(jìn)制位數(shù)；儲(chǔ)空間的大小，二進(jìn)制位數(shù)； 問題的時(shí)間復(fù)雜性：一切算法中時(shí)間復(fù)雜性最問題的時(shí)間復(fù)雜性：一切算法中時(shí)間復(fù)雜性最小的算法時(shí)間復(fù)雜性；小的算法時(shí)間復(fù)雜性； 問題的空間復(fù)雜性：一切算法中空間復(fù)雜性最問題的空間復(fù)雜性：一切算法中空間復(fù)雜性最小的算法空間復(fù)雜性；小的算法空間復(fù)雜性；復(fù)雜性問題分類復(fù)雜性問題分類 P類、類、NP類、類、NP完全類完全類復(fù)雜性表示方法復(fù)雜性表示方法

32、復(fù)雜性表示為問題規(guī)模復(fù)雜性表示為問題規(guī)模n如如TSP的的n的函數(shù)，的函數(shù)， 時(shí)間復(fù)雜性時(shí)間復(fù)雜性T(n)，關(guān)鍵操作的次數(shù)；，關(guān)鍵操作的次數(shù)； 空間復(fù)雜性空間復(fù)雜性S(n)，占用的存儲(chǔ)單元數(shù)量；，占用的存儲(chǔ)單元數(shù)量； 復(fù)雜性表示方法復(fù)雜性表示方法 假設(shè)算法假設(shè)算法A的時(shí)間復(fù)雜性為的時(shí)間復(fù)雜性為TA(n)=O(p(n)，O(p(n)為復(fù)雜性函數(shù)為復(fù)雜性函數(shù)p(n)主要項(xiàng)的階，且主要項(xiàng)的階，且p(n)為為n的多項(xiàng)式函數(shù)，那么稱算法的多項(xiàng)式函數(shù)，那么稱算法A為多項(xiàng)式算法。為多項(xiàng)式算法。 當(dāng)不存在多項(xiàng)式函數(shù)當(dāng)不存在多項(xiàng)式函數(shù)p(n)時(shí)，稱相應(yīng)的算法為非時(shí)，稱相應(yīng)的算法為非多項(xiàng)式時(shí)間算法或指數(shù)時(shí)間算法；多

33、項(xiàng)式時(shí)間算法或指數(shù)時(shí)間算法； 隨著變量的添加，多項(xiàng)式函數(shù)增長的速度比指隨著變量的添加，多項(xiàng)式函數(shù)增長的速度比指數(shù)函數(shù)和非多項(xiàng)式函數(shù)增長的速度要慢得多。數(shù)函數(shù)和非多項(xiàng)式函數(shù)增長的速度要慢得多。P類問題類問題 deterministic polynomial 具有多項(xiàng)式時(shí)間求解算法的問題類具有多項(xiàng)式時(shí)間求解算法的問題類 迄今為止，許多組合優(yōu)化問題都沒有找到求最迄今為止，許多組合優(yōu)化問題都沒有找到求最優(yōu)解的多項(xiàng)式時(shí)間算法。優(yōu)解的多項(xiàng)式時(shí)間算法。NP類問題類問題(Nondeterministic polynomial) 定義定義1 實(shí)例是問題的特殊表現(xiàn)，所謂實(shí)例就是實(shí)例是問題的特殊表現(xiàn)，所謂實(shí)例就是確

34、定了描畫問題特性的一切參數(shù)的問題，其中參數(shù)確定了描畫問題特性的一切參數(shù)的問題，其中參數(shù)值稱為數(shù)據(jù)，這些數(shù)據(jù)占有計(jì)算機(jī)的空間稱為實(shí)例值稱為數(shù)據(jù)，這些數(shù)據(jù)占有計(jì)算機(jī)的空間稱為實(shí)例的輸入長度。的輸入長度。NP類問題類問題(Nondeterministic polynomial) 定義定義2 假設(shè)一個(gè)問題的每個(gè)實(shí)例只需假設(shè)一個(gè)問題的每個(gè)實(shí)例只需“是或是或“否兩種回答，那么稱該問題為斷定問題。否兩種回答，那么稱該問題為斷定問題。 例，例，TSP的斷定問題：給定的斷定問題：給定z，能否存在，能否存在n個(gè)城個(gè)城市的一個(gè)陳列市的一個(gè)陳列W，使得，使得f(W)z。滿足。滿足f(W)z的一個(gè)的一個(gè)陳列陳列W稱為斷定問題的稱為斷定問題的“是答案可行解。是答案可行解。NP類問題類問題(Nondeterministic polynomial) 假設(shè)存在一個(gè)多項(xiàng)式假設(shè)存在一個(gè)多項(xiàng)式 g(x