智能優(yōu)化算法及其應用intelligent

1、by 謝廣明 ， 2005~2006學年度第一學期,1,第一章 緒論,優(yōu)化問題的分類與描述Benchmark問題介紹優(yōu)化算法及其分類鄰域函數(shù)與局部搜索計算復雜性與NP、NP-hard、NP-Complete,by 謝廣明 ， 2005~2006學年度第一學期,2,1.1 優(yōu)化問題分類,嚴格數(shù)學化以后的狹義優(yōu)化問題函數(shù)優(yōu)化問題組合優(yōu)化問題混合型優(yōu)化問題,by 謝廣明 ， 2005~2006學年度第

2、一學期,3,函數(shù)優(yōu)化問題 1,本質求解自變量為連續(xù)變量的函數(shù)的最小值定義,by 謝廣明 ， 2005~2006學年度第一學期,4,函數(shù)優(yōu)化問題 2,有約束和無約束是否存在一些限制自變量取值的約束條件，一般以不等式和等式形式出現(xiàn)g(x)<0, h(x)=0,by 謝廣明 ， 2005~2006學年度第一學期,5,函數(shù)優(yōu)化問題 3,有約束轉化為無約束的處理,by 謝廣明 ， 2005~2006學年度第一學期,

3、6,組合優(yōu)化問題,本質求解自變量為離散變量的函數(shù)的最小值定義組合爆炸！,by 謝廣明 ， 2005~2006學年度第一學期,7,1.2 Benchmark問題,含義基準研究對象很多科學研究和實際事物都有意義具有一些典型特征，便于驗證有關方法便于比較不同方法的性能優(yōu)略產生最先研究者提出后來者加以改進,by 謝廣明 ， 2005~2006學年度第一學期,8,函數(shù)優(yōu)化Benchmark問題,典型特點

4、單極小非凸非線性多極小高維強振蕩噪聲不可微平臺,by 謝廣明 ， 2005~2006學年度第一學期,9,by 謝廣明 ， 2005~2006學年度第一學期,10,by 謝廣明 ， 2005~2006學年度第一學期,11,by 謝廣明 ， 2005~2006學年度第一學期,12,by 謝廣明 ， 2005~2006學年度第一學期,13,組合問題旅行商問題(TSP)加工調度問題背包問題

5、裝箱問題著色問題聚類問題實際問題生產線、交通、網(wǎng)絡路由、VLSI等,組合優(yōu)化Benchmark問題,by 謝廣明 ， 2005~2006學年度第一學期,14,TSP(Traveling Salesman Problem),by 謝廣明 ， 2005~2006學年度第一學期,15,1.3 優(yōu)化算法及其分類,所謂優(yōu)化算法, 其實就是一種搜索過程或規(guī)則, 它基于某種原理和機制, 通過一定的途徑或規(guī)則來得到滿足用戶要求的問

6、題的解.就優(yōu)化機制與行為而分, 常用的優(yōu)化算法主要可分為: 經典算法, 構造型算法, 改進型算法, 基于系統(tǒng)動態(tài)演化的算法, 混合型算法等.從其他角度分類, 如確定性算法和不確定性算法, 局部優(yōu)化算法和全局優(yōu)化算法等.,by 謝廣明 ， 2005~2006學年度第一學期,16,經典算法,如線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃和分枝定界等。其算法計算復雜性大, 只適于求解小規(guī)模問題, 在工程中往往不實用。,by 謝廣明 ， 20

7、05~2006學年度第一學期,17,構造型算法,用構造的方法快速建立問題的解, 通常解的質量差, 難以滿足工程需要.調度中的典型構造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、Baker的基于枚舉樹的分區(qū)法和NEH法等.,by 謝廣明 ， 2005~2006學年度第一學期,18,改進型算法,從任一解出發(fā), 對其鄰域的不斷搜索和當前解的替換來實現(xiàn)優(yōu)化.通?？煞譃榫植克阉鞣?/p>

8、和指導性搜索法.局部搜索法. 以局部優(yōu)化策略在當前解的鄰域中貪婪搜索, 如只接受優(yōu)于當前解的狀態(tài)作為下一當前解的爬山法, 接受當前解鄰域中的最好解作為下一當前解的最陡下降法等.指導性搜索法. 利用一些指導規(guī)則來指導整個解空間中優(yōu)良解的探索, 如SA、GA、EP、ES和TS等.,by 謝廣明 ， 2005~2006學年度第一學期,19,基于動態(tài)演化的方法,將優(yōu)化過程轉化為系統(tǒng)動態(tài)的演化過程, 基于系統(tǒng)動態(tài)的演化來實現(xiàn)優(yōu)化, 如神

9、經網(wǎng)絡、混沌搜索、蟻群搜索等.,by 謝廣明 ， 2005~2006學年度第一學期,20,混合算法,上述各算法從結構或操作上相混合而產生的各類算法。如GASA,by 謝廣明 ， 2005~2006學年度第一學期,21,一些值得重視和發(fā)展的優(yōu)化技術與算法,量子優(yōu)化蟻群系統(tǒng)基于生命行為的優(yōu)化技術：人工選擇、遷徙、免疫混合算法計算智能的研究,by 謝廣明 ， 2005~2006學年度第一學期,22,1.4 鄰域函

10、數(shù)和局部搜索,鄰域函數(shù)是優(yōu)化中的一個重要概念, 其作用就是指導如何由一個(組)解來產生一個(組)新的解, 其設計往往依賴于問題的特性和解的表達方式(編碼).,by 謝廣明 ， 2005~2006學年度第一學期,23,組合優(yōu)化問題,傳統(tǒng)距離問題不在適用，必須重新定義。根據(jù)具體問題類型不同采用有針對性的方法同時所謂局部極小、全局極小也要重新定義,by 謝廣明 ， 2005~2006學年度第一學期,24,by 謝廣明 ，

11、 2005~2006學年度第一學期,25,by 謝廣明 ， 2005~2006學年度第一學期,26,by 謝廣明 ， 2005~2006學年度第一學期,27,by 謝廣明 ， 2005~2006學年度第一學期,28,1.5 計算復雜性,算法對時間和空間的需要量稱為算法的時間復雜性和空間復雜性. 問題的時間復雜性是指求解該問題的所有算法中時間復雜性最小的算法的時間復雜性, 問題的空間復雜性也可類似定義. 按照計算復

12、雜性理論研究問題求解的難易程度, 可把問題分為P類、NP類和NP完全類.,by 謝廣明 ， 2005~2006學年度第一學期,29,by 謝廣明 ， 2005~2006學年度第一學期,30,by 謝廣明 ， 2005~2006學年度第一學期,31,by 謝廣明 ， 2005~2006學年度第一學期,32,by 謝廣明 ， 2005~2006學年度第一學期,33,by 謝廣明 ， 2005~2006學年