智能優(yōu)化計(jì)算.ppt_第1頁
智能優(yōu)化計(jì)算.ppt_第2頁
智能優(yōu)化計(jì)算.ppt_第3頁
智能優(yōu)化計(jì)算.ppt_第4頁
智能優(yōu)化計(jì)算.ppt_第5頁
已閱讀5頁,還剩73頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論