智能優(yōu)化計(jì)算.ppt

1、智 能 優(yōu) 化 計(jì) 算,湖北民族學(xué)院理學(xué)院 向長城,課程名稱 智能優(yōu)化計(jì)算 教師聯(lián)系方式 辦公地點(diǎn)：TelEmail： 上課時(shí)間地點(diǎn):辦公室：理學(xué)院二樓 創(chuàng)新中心一樓辦公室 本周及補(bǔ)課時(shí)間 17-18,智能優(yōu)化計(jì)算,湖北民族學(xué)院,課程定位 解決的問題：優(yōu)化問題 解決的方法：智能方法 數(shù)學(xué)工具 實(shí)用方法 考核方式 課程論文，一人一篇 作業(yè)（編程，2次）,智能優(yōu)化計(jì)算,湖北民族學(xué)院,內(nèi)容安排 最優(yōu)化問題概述 禁忌搜索算法(Tabu search) 模擬退火算法(Simulated Annealing) 遺傳算法(Genetic Algorithm) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法(Ne

2、ural Network) 群智能算法，包括蟻群算法(Ant Colony Optimization)、粒子群算法(Particle Swarm Optimization) 廣義領(lǐng)域搜索算法及其統(tǒng)一結(jié)構(gòu) 課堂討論及作業(yè),智能優(yōu)化計(jì)算,湖北民族學(xué)院,參考書 1 邢文訓(xùn), 謝金星. 現(xiàn)代優(yōu)化計(jì)算方法. 北京: 清華大學(xué)出版社, 2005. 2 王凌. 智能優(yōu)化算法及其應(yīng)用. 北京: 清華大學(xué)出版社, 2001. 3 閻平凡, 張長水. 人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算. 北京: 清華大學(xué)出版社, 2005.,智能優(yōu)化計(jì)算,湖北民族學(xué)院,參考書 4王小平, 曹立明. 遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn). 西安:

3、 西安交通大學(xué)出版社, 2002. 5黃席樾等. 現(xiàn)代智能算法理論及應(yīng)用. 北京：科學(xué)出版社, 2005. 6高尚, 楊靜宇. 群智能算法及其應(yīng)用. 北京: 中國水利水電出版社, 2006.,智能優(yōu)化計(jì)算,湖北民族學(xué)院,第一章 緒論,智能優(yōu)化計(jì)算,湖北民族學(xué)院,1.1 引言 1.1.1 優(yōu)化問題 1.1.2 傳統(tǒng)優(yōu)化方法 1.1.3 現(xiàn)代優(yōu)化方法 1.2 最優(yōu)化問題及其分類 1.2.1 函數(shù)優(yōu)化問題 1.2.2 組合優(yōu)化問題 1.3 啟發(fā)式算法 1.3.1 啟發(fā)式算法的定義 1.3.2 啟發(fā)式算法的分類 1.3.3 啟發(fā)式算法的性能分析 1.4 計(jì)算復(fù)雜性與NP完全問題 1.4.1 計(jì)算復(fù)雜性

4、的基本概念 1.4.2 P,NP,NP-C和NP-hard,智能優(yōu)化計(jì)算,湖北民族學(xué)院,1.1 引言,智能優(yōu)化計(jì)算,湖北民族學(xué)院,優(yōu)化技術(shù)？ 以數(shù)學(xué)為基礎(chǔ)，解決各種工程問題優(yōu)化解 優(yōu)化技術(shù)的用途 系統(tǒng)控制 人工智能 模式識別 生產(chǎn)調(diào)度 ,1.1.1 優(yōu)化問題,1.1 引言,智能優(yōu)化計(jì)算,湖北民族學(xué)院,最優(yōu)化問題的描述 最優(yōu)化問題的數(shù)學(xué)模型的一般描述：,1.1.1 優(yōu)化問題,1.1 引言,智能優(yōu)化計(jì)算,湖北民族學(xué)院,待解決的問題 連續(xù)性問題，以微積分為基礎(chǔ)，規(guī)模較小 傳統(tǒng)的優(yōu)化方法 理論上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫存論、對策論、決策論等

5、。 傳統(tǒng)的評價(jià)方法 算法收斂性、收斂速度,1.1.2 傳統(tǒng)優(yōu)化方法,1.1 引言,智能優(yōu)化計(jì)算,湖北民族學(xué)院,待解決的問題 離散性、不確定性、大規(guī)模 現(xiàn)代的優(yōu)化方法 啟發(fā)式算法（heuristic algorithm） 追求滿意（近似解） 實(shí)用性強(qiáng)（解決實(shí)際工程問題） 現(xiàn)代的評價(jià)方法 算法復(fù)雜性,1.1.3 現(xiàn)代優(yōu)化方法,1.2 最優(yōu)化問題及其分類（函數(shù)優(yōu)化和組合優(yōu)化）,智能優(yōu)化計(jì)算,湖北民族學(xué)院,數(shù)學(xué)表述 難點(diǎn) 高維 多峰值,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù)（Benchmark問題） （1）Sphere Model 其最優(yōu)狀態(tài)和最優(yōu)值

6、為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （2）Schwefels Problem 2.22 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （3）Schwefels Problem 1.2 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （4）Schwefels Problem 2.21 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （5）G

7、eneralized Rosenbrocks Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （6）Step Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （6）Step Function,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （7）Quartic Function i.e. Niose 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)

8、算,湖北民族學(xué)院,測試函數(shù) （8）Generalized Schwefels Problem 2.26 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （8）Generalized Schwefels Problem 2.26,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （9）Generalized Rastrigins Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （10）Ackleys Fun

9、ction 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （10）Ackleys Function,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （11）Generalized Griewank Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （11）Generalized Griewank Function,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù)

10、 （12）Generalized Penalized Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （13）Generalized Penalized Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （14）Shekels Foxholes Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其

11、分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （15）Kowaliks Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （16）Six-Hump Camel-Back Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （17）Brani

12、n Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （18）Goldstein-Price Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （19）Hartmans Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （20）Hartmans Func

13、tion 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （21）Shekels Family m分別取5，7和10，其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （22）J. D. Schaffer 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問

14、題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,測試函數(shù) （22）J. D. Schaffer 此函數(shù)在距全局最優(yōu)點(diǎn)大約3.14范圍內(nèi)存在無窮多個(gè)局部極小將其包圍，并且函數(shù)強(qiáng)烈振蕩。,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)； 影響因素： （1）曲面拓?fù)湫再|(zhì)，線性或凸函數(shù)比無規(guī)律的函數(shù)更容易求解； （2）可行區(qū)域的疏密程度，通常以可行區(qū)域占整個(gè)搜索空間的比值來度量；,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)； 影響因素： （3）整體最優(yōu)解與可行區(qū)域

15、最優(yōu)解之比； （4）在最優(yōu)解處活躍約束的數(shù)目，活躍約束數(shù)目越多則最優(yōu)解離可行區(qū)域的邊界越近。,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,數(shù)學(xué)表述 所屬范疇 涉及離散事件的最優(yōu)編排、分類、次序篩選等問題，是運(yùn)籌學(xué)的一個(gè)重要分支。,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,典型問題旅行商問題（Traveling salesman problem, TSP） 給定n個(gè)城市和兩兩 城市之間的距離，要 求確定一條經(jīng)過各城 市當(dāng)且僅當(dāng)一次的最 短路線。,1.2.2 組合優(yōu)化問題,1,2,3,4,12,1,8,10,3,2,1.

16、2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,典型問題旅行商問題（Traveling salesman problem, TSP） 計(jì)算復(fù)雜度：指數(shù)災(zāi)難,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,典型問題加工調(diào)度問題（Scheduling problem,如Flow-shop, Job-shop） Job-shop：n個(gè)工件在m臺機(jī)器上加工，Oij：第i個(gè)工件在第j臺機(jī)器上的操作， Tij：相應(yīng)的操作時(shí)間，已知。事先給定各工件在各機(jī)器上的加工次序（技術(shù)約束條件），要求確定與技術(shù)約束條件相容的各機(jī)器上所有工件的加工順序，使得加工性能指標(biāo)達(dá)到最優(yōu)。 若

17、各工件技術(shù)約束條件相同，轉(zhuǎn)化為Flow-shop。,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,典型問題加工調(diào)度問題（Scheduling problem,如Flow-shop, Job-shop） 計(jì)算復(fù)雜性：可能的排列方式有（n?。﹎ 多目標(biāo)優(yōu)化 動(dòng)態(tài)性 狀態(tài)相依,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,典型問題01背包問題（Knapsack problem） 對于n個(gè)體積為ai、價(jià)值分別為ci的物品，如何將它們裝入總體積為b的背包中，使得所選物品的總價(jià)值最大。,1.2.2 組合優(yōu)化問題,背包問題的貪婪算法,1

18、.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,典型問題裝箱問題（Bin packing problem） 有n個(gè)尺寸不超過1的物品，有數(shù)個(gè)尺寸為1的箱子，如何將這些物品裝入箱子，使得所需箱子的個(gè)數(shù)最少。,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,典型問題圖著色問題（Graph coloring problem） 對于n個(gè)頂點(diǎn)的無環(huán)圖G，要求對其各個(gè)頂點(diǎn)進(jìn)行著色，使得任意兩個(gè)相鄰的頂點(diǎn)都有不同的顏色，且所用顏色種類最少。,1.2.2 組合優(yōu)化問題,C1：第一種顏色 C2：第二種顏色 C3：第三種顏色,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民

19、族學(xué)院,典型問題聚類問題（Clustering problem） m維空間上的n個(gè)模式Xi|i=1,2,n，要求聚成k類，使得各類本身內(nèi)的點(diǎn)最相近，如要求 其中Rp為第p類的中心，即 其中，p=1,2,k，np為第p類中的點(diǎn)數(shù)。,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計(jì)算,湖北民族學(xué)院,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問題（n=1,3,5,39,41） FT n or MT

20、n Job-shop問題（n=6,10,20） LA n Job-shop問題（n=1,6,11,16,21,26,31,36）,1.2.2 組合優(yōu)化問題,30城市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; 58 35; 45 21; 4

21、1 26; 44 35; 4 50,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,最優(yōu)算法 一個(gè)問題的最優(yōu)算法求得該問題每個(gè)實(shí)例的最優(yōu)解； 啟發(fā)式算法 一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（計(jì)算時(shí)間、占用空間等）下給出待解決優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。,1.3.1 啟發(fā)式算法的定義,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,啟發(fā)式算法的特點(diǎn) 是一種技術(shù)； 不能保證所得解的最優(yōu)性； 啟發(fā)式算法的發(fā)展歷史 20世紀(jì)40年代起步 20世紀(jì)6070年代被鄙視 20世紀(jì)70年代觀點(diǎn)轉(zhuǎn)變 20世紀(jì)80年代至今研究熱潮,1.3.1 啟發(fā)式算法

22、的定義,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,例子背包問題的貪婪算法（Greedy algorithm） 貪婪算法：采用逐步構(gòu)造最優(yōu)解的方法。 在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedy criterion）。,1.3.1 啟發(fā)式算法的定義,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,例子背包問題的貪婪算法（Greedy algorithm） STEP 1 STEP 2,1.3.1 啟發(fā)式算法的定義,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,啟發(fā)式算法的優(yōu)點(diǎn) 1. 模型誤差、數(shù)據(jù)不精確性

23、、參數(shù)估計(jì)誤差等可能造成最優(yōu)算法的解比啟發(fā)式算法的解更差； 2. 復(fù)雜問題無法求得最優(yōu)算法或最優(yōu)算法太復(fù)雜； 3. 簡單易行，直觀，程序簡單。 啟發(fā)式算法的缺點(diǎn) 1. 不能保證最優(yōu)； 2. 不穩(wěn)定； 3. 依賴于實(shí)際問題、設(shè)計(jì)者經(jīng)驗(yàn)。,1.3.1 啟發(fā)式算法的定義,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,簡單直觀的算法 一步算法：不在兩個(gè)可行解之間比較，在未終止的迭代過程中，得到的中間解有可能不是可行解； 例：背包問題的貪婪算法 改進(jìn)算法：迭代過程是從一個(gè)可行解到另一個(gè)可行解變換，通過兩個(gè)解的比較而選擇好的解，直到滿足一定的要求為止； 例：TSP問題的2opt方法,1.3.2 啟發(fā)式算

24、法的分類,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,數(shù)學(xué)規(guī)劃算法 用連續(xù)優(yōu)化（如線性規(guī)劃）的方法求解組合優(yōu)化問題（如整數(shù)線性規(guī)劃模型），其中包括一些啟發(fā)式規(guī)則。 基于數(shù)學(xué)規(guī)劃的理論。,1.3.2 啟發(fā)式算法的分類,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,現(xiàn)代優(yōu)化算法 禁忌搜索算法 模擬退火算法 遺傳算法 人工神經(jīng)網(wǎng)絡(luò) 蟻群算法 粒子群算法 混合算法,1.3.2 啟發(fā)式算法的分類,特點(diǎn)： 基于客觀世界中的一些自然現(xiàn)象； 建立在計(jì)算機(jī)迭代計(jì)算的基礎(chǔ)上； 具有普適性，可解決實(shí)際應(yīng)用問題。,1.3 啟發(fā)式算法,智能優(yōu)化計(jì)算,湖北民族學(xué)院,評價(jià)算法優(yōu)劣的指標(biāo) 算法的復(fù)雜性（計(jì)算效率） 解的

25、偏離程度（計(jì)算效果） 算法的穩(wěn)健性（不同實(shí)例、不同時(shí)間、不同起點(diǎn)的差異） 評價(jià)算法優(yōu)劣的手段 最壞情況分析（純理論） 概率分析（理論分析） 計(jì)算模擬分析（統(tǒng)計(jì)特性）,1.3.3 啟發(fā)式算法的性能分析,1.4 計(jì)算復(fù)雜性與NP完全問題,智能優(yōu)化計(jì)算,湖北民族學(xué)院,時(shí)間復(fù)雜性和空間復(fù)雜性概念 算法的時(shí)間復(fù)雜性：算法對時(shí)間的需要量（加、減、乘、除、比較、讀、寫等操作的總次數(shù)）； 算法的空間復(fù)雜性：算法對空間的需要量（存儲空間的大小，二進(jìn)制位數(shù)）； 問題的時(shí)間復(fù)雜性：所有算法中時(shí)間復(fù)雜性最小的算法時(shí)間復(fù)雜性； 問題的空間復(fù)雜性：所有算法中空間復(fù)雜性最小的算法空間復(fù)雜性；,1.4.1 計(jì)算復(fù)雜性的基本概

26、念,1.4 計(jì)算復(fù)雜性與NP完全問題,智能優(yōu)化計(jì)算,湖北民族學(xué)院,復(fù)雜性問題分類 P類、NP類、NP完全類 復(fù)雜性表示方法 復(fù)雜性表示為問題規(guī)模n（如TSP的n）的函數(shù)， 時(shí)間復(fù)雜性T(n)，關(guān)鍵操作的次數(shù)； 空間復(fù)雜性S(n)，占用的存儲單元數(shù)量；,1.4.1 計(jì)算復(fù)雜性的基本概念,1.4 計(jì)算復(fù)雜性與NP完全問題,智能優(yōu)化計(jì)算,湖北民族學(xué)院,復(fù)雜性表示方法 若算法A的時(shí)間復(fù)雜性為TA(n)=O(p(n)，O(p(n)為復(fù)雜性函數(shù)p(n)主要項(xiàng)的階，且p(n)為n的多項(xiàng)式函數(shù)，則稱算法A為多項(xiàng)式算法。 當(dāng)不存在多項(xiàng)式函數(shù)p(n)時(shí)，稱相應(yīng)的算法為非多項(xiàng)式時(shí)間算法或指數(shù)時(shí)間算法； 隨著變量的增

27、加，多項(xiàng)式函數(shù)增長的速度比指數(shù)函數(shù)和非多項(xiàng)式函數(shù)增長的速度要慢得多。,1.4.1 計(jì)算復(fù)雜性的基本概念,1.4 計(jì)算復(fù)雜性與NP完全問題,智能優(yōu)化計(jì)算,湖北民族學(xué)院,P類問題（ deterministic polynomial ） 具有多項(xiàng)式時(shí)間求解算法的問題類 迄今為止，許多組合優(yōu)化問題都沒有找到求最優(yōu)解的多項(xiàng)式時(shí)間算法。 NP類問題(Nondeterministic polynomial) 定義1 實(shí)例是問題的特殊表現(xiàn)，所謂實(shí)例就是確定了描述問題特性的所有參數(shù)的問題，其中參數(shù)值稱為數(shù)據(jù)，這些數(shù)據(jù)占有計(jì)算機(jī)的空間稱為實(shí)例的輸入長度。,1.4.2 P,NP,NP-C和NP-hard,1.4 計(jì)

28、算復(fù)雜性與NP完全問題,智能優(yōu)化計(jì)算,湖北民族學(xué)院,NP類問題(Nondeterministic polynomial) 定義2 若一個(gè)問題的每個(gè)實(shí)例只有“是”或“否”兩種回答，則稱該問題為判定問題。 例，TSP的判定問題：給定z，是否存在n個(gè)城市的一個(gè)排列W，使得f(W)z。滿足f(W)z的一個(gè)排列W稱為判定問題的“是”答案（可行解）。,1.4.2 P,NP,NP-C和NP-hard,1.4 計(jì)算復(fù)雜性與NP完全問題,智能優(yōu)化計(jì)算,湖北民族學(xué)院,NP類問題(Nondeterministic polynomial) 若存在一個(gè)多項(xiàng)式 g(x) 和一個(gè)驗(yàn)證算法 H ，對一類判定問題 A 的任何一個(gè)“是”的判定實(shí)例 I