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

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

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

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

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

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

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

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

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

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

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

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

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