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

1、智 能 優(yōu) 化 計 算,湖北民族學(xué)院理學(xué)院 向長城,課程名稱 智能優(yōu)化計算 教師聯(lián)系方式 辦公地點：TelEmail： 上課時間地點:辦公室：理學(xué)院二樓 創(chuàng)新中心一樓辦公室 本周及補課時間 17-18,智能優(yōu)化計算,湖北民族學(xué)院,課程定位 解決的問題：優(yōu)化問題 解決的方法：智能方法 數(shù)學(xué)工具 實用方法 考核方式 課程論文，一人一篇 作業(yè)（編程，2次）,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,參考書 1 邢文訓(xùn), 謝金星. 現(xiàn)代優(yōu)化計算方法. 北京: 清華大學(xué)出版社, 2005. 2 王凌. 智能優(yōu)化算法及其應(yīng)用. 北京: 清華大學(xué)出版社, 2001. 3 閻平凡, 張長水. 人工神經(jīng)網(wǎng)絡(luò)與模擬進化計算. 北京: 清華大學(xué)出版社, 2005.,智能優(yōu)化計算,湖北民族學(xué)院,參考書 4王小平, 曹立明. 遺傳算法理論、應(yīng)用與軟件實現(xiàn). 西安:

3、 西安交通大學(xué)出版社, 2002. 5黃席樾等. 現(xiàn)代智能算法理論及應(yīng)用. 北京：科學(xué)出版社, 2005. 6高尚, 楊靜宇. 群智能算法及其應(yīng)用. 北京: 中國水利水電出版社, 2006.,智能優(yōu)化計算,湖北民族學(xué)院,第一章 緒論,智能優(yōu)化計算,湖北民族學(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 計算復(fù)雜性與NP完全問題 1.4.1 計算復(fù)雜性

4、的基本概念 1.4.2 P,NP,NP-C和NP-hard,智能優(yōu)化計算,湖北民族學(xué)院,1.1 引言,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,最優(yōu)化問題的描述 最優(yōu)化問題的數(shù)學(xué)模型的一般描述：,1.1.1 優(yōu)化問題,1.1 引言,智能優(yōu)化計算,湖北民族學(xué)院,待解決的問題 連續(xù)性問題，以微積分為基礎(chǔ)，規(guī)模較小 傳統(tǒng)的優(yōu)化方法 理論上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等

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

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)化計算,湖北民族學(xué)院,測試函數(shù) （8）Generalized Schwefels Problem 2.26,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) （9）Generalized Rastrigins Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,測試函數(shù) （10）Ackleys Function,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) （11）Generalized Griewank Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) （11）Generalized Griewank Function,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) （13）Generalized Penalized Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) （15）Kowaliks Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,測試函數(shù) （18）Goldstein-Price Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) （19）Hartmans Function 其最優(yōu)狀態(tài)和最優(yōu)值為,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,測試函數(shù) 其中，,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,測試函數(shù) （22）J. D. Schaffer 此函數(shù)在距全局最優(yōu)點大約3.14范圍內(nèi)存在無窮多個局部極小將其包圍，并且函數(shù)強烈振蕩。,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)； 影響因素： （1）曲面拓撲性質(zhì)，線性或凸函數(shù)比無規(guī)律的函數(shù)更容易求解； （2）可行區(qū)域的疏密程度，通常以可行區(qū)域占整個搜索空間的比值來度量；,1.2.1 函數(shù)優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,數(shù)學(xué)表述 所屬范疇 涉及離散事件的最優(yōu)編排、分類、次序篩選等問題，是運籌學(xué)的一個重要分支。,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,典型問題旅行商問題（Traveling salesman problem, TSP） 給定n個城市和兩兩 城市之間的距離，要 求確定一條經(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)化計算,湖北民族學(xué)院,典型問題旅行商問題（Traveling salesman problem, TSP） 計算復(fù)雜度：指數(shù)災(zāi)難,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(xué)院,典型問題加工調(diào)度問題（Scheduling problem,如Flow-shop, Job-shop） Job-shop：n個工件在m臺機器上加工，Oij：第i個工件在第j臺機器上的操作， Tij：相應(yīng)的操作時間，已知。事先給定各工件在各機器上的加工次序（技術(shù)約束條件），要求確定與技術(shù)約束條件相容的各機器上所有工件的加工順序，使得加工性能指標(biāo)達到最優(yōu)。 若

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

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

19、族學(xué)院,典型問題聚類問題（Clustering problem） m維空間上的n個模式Xi|i=1,2,n，要求聚成k類，使得各類本身內(nèi)的點最相近，如要求 其中Rp為第p類的中心，即 其中，p=1,2,k，np為第p類中的點數(shù)。,1.2.2 組合優(yōu)化問題,1.2 最優(yōu)化問題及其分類,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,最優(yōu)算法 一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解； 啟發(fā)式算法 一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費（計算時間、占用空間等）下給出待解決優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計。,1.3.1 啟發(fā)式算法的定義,1.3 啟發(fā)式算法,智能優(yōu)化計算,湖北民族學(xué)院,啟發(fā)式算法的特點 是一種技術(shù)； 不能保證所得解的最優(yōu)性； 啟發(fā)式算法的發(fā)展歷史 20世紀(jì)40年代起步 20世紀(jì)6070年代被鄙視 20世紀(jì)70年代觀點轉(zhuǎn)變 20世紀(jì)80年代至今研究熱潮,1.3.1 啟發(fā)式算法

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

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

24、法的分類,1.3 啟發(fā)式算法,智能優(yōu)化計算,湖北民族學(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)化計算,湖北民族學(xué)院,現(xiàn)代優(yōu)化算法 禁忌搜索算法 模擬退火算法 遺傳算法 人工神經(jīng)網(wǎng)絡(luò) 蟻群算法 粒子群算法 混合算法,1.3.2 啟發(fā)式算法的分類,特點： 基于客觀世界中的一些自然現(xiàn)象； 建立在計算機迭代計算的基礎(chǔ)上； 具有普適性，可解決實際應(yīng)用問題。,1.3 啟發(fā)式算法,智能優(yōu)化計算,湖北民族學(xué)院,評價算法優(yōu)劣的指標(biāo) 算法的復(fù)雜性（計算效率） 解的

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

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

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

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