1、研究生課程工程數(shù)學(xué)之“最優(yōu)化方法”現(xiàn) 代 最 優(yōu) 化 方 法College of Energy and Power Engineering 1 現(xiàn)代優(yōu)化算法包括隨機(jī)試驗法、禁忌搜索算法、模擬退火算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法和拉格朗日松弛算法等，這些算法涉及生物進(jìn)化、人工智能、數(shù)學(xué)和物理科學(xué)、神經(jīng)系統(tǒng)和統(tǒng)計力學(xué)等概念。都是以一定的直觀基礎(chǔ)而構(gòu)造的算法，通常稱之為啟發(fā)式算法。 啟發(fā)式算法的興起與計算復(fù)雜性理論的形成有密切的聯(lián)系。 1. 對目標(biāo)函數(shù)和約束函數(shù)不必附加可解析性條件，對于目標(biāo)函數(shù)而言甚至可以不要求有顯示表達(dá)式； 2. 對于約束變量可以去離散值或特殊整數(shù)如0和1等； 3. 在通常情況下，這

2、些算法能夠求解全局最優(yōu)解。2第一節(jié) 隨 機(jī) 試 驗 法 一、基本思想 用隨機(jī)的方法產(chǎn)生試驗點，再從試驗點中選出滿足約束條件的點，進(jìn)而求出最優(yōu)點的一種方法。二、 隨機(jī)試驗法 成立的最優(yōu)解x*設(shè)問題首先用隨機(jī)方法產(chǎn)生試驗點 ，然后從中找出滿足約束條件的點 ,求出使得3一、基本思想 禁忌搜索法(Tabu search)是一種人工智能方法，是局部鄰域搜索算法的推廣，是人工智能在組合優(yōu)化中的一個成功應(yīng)用。 其基本思想是：標(biāo)記已經(jīng)得到的局部最優(yōu)解，并在進(jìn)一步的迭代中避開這些局部最優(yōu)解。所謂的禁忌就是禁止重復(fù)前面的工作，為了避開局部鄰域搜索陷入局部最優(yōu)，禁忌搜索算法設(shè)計了一種禁忌表，記錄已達(dá)到過的局部最優(yōu)點

3、。在下一次的搜索中，就利用禁忌表中的信息，不再或者有選擇地搜索這些點，以此跳出局部最優(yōu)點。第二節(jié) 禁 忌 搜 索 法 41. 算法的提出 模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。2. 算法的目的 解決NP復(fù)雜性問題； 克服優(yōu)化過程陷入局部極??； 克服初值依賴性。一、物理退火過程第三節(jié) 模 擬 退 火 算 法 53.物理退火過程 什么是退火? 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 第三節(jié) 模 擬 退 火 算 法 6物理退火過程 加溫

4、過程增強(qiáng)粒子的熱運動，消除系統(tǒng)原先可能存在的非均勻態(tài)； 等溫過程對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時，系統(tǒng)達(dá)到平衡態(tài)； 冷卻過程使粒子熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。第三節(jié) 模 擬 退 火 算 法 74. 數(shù)學(xué)表述 在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布第三節(jié) 模 擬 退 火 算 法 8在同一個溫度T，選定兩個能量E1E2， 在同一個溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。0第三節(jié) 模 擬 退 火 算 法 9 若|D|為狀態(tài)空間D中狀態(tài)的個數(shù)，D0是具有最

5、低能量的狀態(tài)集合： 當(dāng)溫度很高時，每個狀態(tài)概率基本相同，接近平均值1/|D|； 狀態(tài)空間存在超過兩個不同能量時，具有最低能量狀態(tài)的概率超出平均值1/|D| ； 當(dāng)溫度趨于0時，分子停留在最低能量狀態(tài)的概率趨于1。能量最低狀態(tài) 非能量最低狀態(tài)第三節(jié) 模 擬 退 火 算 法 10Metropolis準(zhǔn)則(1953)以概率接受新狀態(tài) 固體在恒定溫度下達(dá)到熱平衡的過程可以用Monte Carlo方法(計算機(jī)隨機(jī)模擬方法)加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，計算量很大。第三節(jié) 模 擬 退 火 算 法 若在溫度T，當(dāng)前狀態(tài)i 新狀態(tài)j 若Ej=randrom0,1 s=sj;

6、Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫tk+1=update(tk)并令k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。第三節(jié) 模 擬 退 火 算 法 147. 影響優(yōu)化結(jié)果的主要因素分析 給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0； Repeat Repeat 產(chǎn)生新狀態(tài)sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫tk+1=update(tk)并令k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。函數(shù)1函數(shù)2函數(shù)3準(zhǔn)則1準(zhǔn)則2初始溫度第三節(jié) 模 擬

7、 退 火 算 法 15二、 模擬退火算法的馬氏鏈描述 1.馬氏鏈定義 第三節(jié) 模 擬 退 火 算 法 16 一步轉(zhuǎn)移概率： n步轉(zhuǎn)移概率： 若解空間有限，稱馬爾可夫鏈為有限狀態(tài)； 若 ，稱馬爾可夫鏈為時齊的。第三節(jié) 模 擬 退 火 算 法 17模擬退火算法對應(yīng)了一個馬爾可夫鏈 模擬退火算法：新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。 若固定每一溫度，算法均計算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時齊算法； 若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時齊算法。第三節(jié) 模 擬 退 火 算 法 18二、模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計1. 狀態(tài)產(chǎn)生函

8、數(shù)原則 產(chǎn)生的候選解應(yīng)遍布全部解空間方法 在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生第三節(jié) 模 擬 退 火 算 法 192. 狀態(tài)接受函數(shù)原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率； (2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??； (3)當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)下降的解。方法具體形式對算法影響不大， 一般采用min1,exp(-C/t)第三節(jié) 模 擬 退 火 算 法 203. 初溫收斂性分析 通過理論分析可以得到初溫的解析式，但解決實際問題時難以得到精確的參數(shù)； 初溫應(yīng)充分大；實驗表明 初溫越

9、大，獲得高質(zhì)量解的機(jī)率越大，但花費較多的計算時間；第三節(jié) 模 擬 退 火 算 法 21方法 (1) 均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫； (2) 隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫； (3) 利用經(jīng)驗公式。第三節(jié) 模 擬 退 火 算 法 224 溫度更新函數(shù)時齊算法的溫度下降函數(shù) (1) ，越接近1溫度下降越慢，且其大小可以不斷變化； (2) ，其中t0為起始溫度，K為算法溫度下降的總次數(shù)。第三節(jié) 模 擬 退 火 算 法 23非時齊模擬退火算法 每個溫度下只產(chǎn)生一個或少量候選解時齊算法常用的Metropolis抽樣穩(wěn)定準(zhǔn)則 （1）檢驗?zāi)繕?biāo)

10、函數(shù)的均值是否穩(wěn)定； （2）連續(xù)若干步的目標(biāo)值變化較??； （3）按一定的步數(shù)抽樣。5 內(nèi)循環(huán)終止準(zhǔn)則第三節(jié) 模 擬 退 火 算 法 24常用方法 （1）設(shè)置終止溫度的閾值； （2）設(shè)置外循環(huán)迭代次數(shù)； （3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （4）概率分析方法。6 外循環(huán)終止準(zhǔn)則第三節(jié) 模 擬 退 火 算 法 25模擬退火算法的優(yōu)點 質(zhì)量高； 初值魯棒性強(qiáng)； 簡單、通用、易實現(xiàn)。模擬退火算法的缺點 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。 三、 模擬退火算法的優(yōu)缺點第三節(jié) 模 擬 退 火 算 法 26換熱器模型 兩級管殼式換熱

11、器組成的換熱器系統(tǒng)，數(shù)學(xué)模型高度非線性，其目標(biāo)函數(shù)通常是多峰(谷)的，具有很多局部最優(yōu)解。 四、模擬退火算法的應(yīng)用第三節(jié) 模 擬 退 火 算 法 27優(yōu)化目標(biāo) 以換熱器系統(tǒng)的總費用年值最小作為優(yōu)化設(shè)計的目標(biāo)。 其中，f1 (X)是兩級換熱器的初始投資， f2 (X)是兩級換熱器年維護(hù)費(包括除垢、保養(yǎng)、維修等)， f3 (X)是冷卻水資源費以及管程壓降能耗費， f4 (X)是殼程壓降能耗費。第三節(jié) 模 擬 退 火 算 法 28優(yōu)化目標(biāo) 經(jīng)過分析，優(yōu)化問題的獨立變量共12個，分別是一級換熱器工質(zhì)出口溫度t2、冷卻水流量G1、兩個換熱器的管內(nèi)徑d1，d2和管間距S1，S2、折流板間距B1，B2、折

12、流板開口角1，2、單管長度L1，L2。第三節(jié) 模 擬 退 火 算 法 29應(yīng)用模擬退火算法解決優(yōu)化設(shè)計 狀態(tài)表示12個變量的實數(shù)表示； 初始溫度100； 結(jié)束溫度0.001； 狀態(tài)產(chǎn)生函數(shù) ，為擾動幅度參數(shù)，為隨機(jī)擾動變量，隨機(jī)擾動可服從柯西、高斯、均勻分布。 降溫因子0.98； 馬氏鏈長度1200。第三節(jié) 模 擬 退 火 算 法 30優(yōu)化結(jié)果 優(yōu)化目標(biāo)值 0.25565E06 獨立變量取值t2G1Kg/sd1mmS1mmB1m1弧度64.419415.9716615.5716334.097160.924361.93421L1md2mmS2mmB2m2弧度L2m5.9423416.779352

13、7.740120.729532.199285.78314第三節(jié) 模 擬 退 火 算 法 31一、遺傳算法簡介第四節(jié) 遺 傳 算 法 早在50年代，一些生物學(xué)家開始研究運用數(shù)字計算機(jī)模擬生物的自然遺傳與自然進(jìn)化過程；1963年，德國柏林技術(shù)大學(xué)的I. Rechenberg和H. P. Schwefel，做風(fēng)洞實驗時，產(chǎn)生了進(jìn)化策略的初步思想；60年代， L. J. Fogel在設(shè)計有限態(tài)自動機(jī)時提出進(jìn)化規(guī)劃的思想。1966年Fogel等出版了基于模擬進(jìn)化的人工智能，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想。 3260年代中期，美國Michigan大學(xué)的J. H. Holland教授提出借鑒生物自然遺傳的基本原理

14、用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；1967年，他的學(xué)生J. D. Bagley在博士論文中首次提出“遺傳算法(Genetic Algorithms)”一詞；1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，標(biāo)志遺傳算法的誕生。第四節(jié) 遺 傳 算 法 3370年代初，Holland提出了“模式定理”（Schema Theorem），一般認(rèn)為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；1985年，在美國召開了第一屆遺傳算法國際會議，并且成立了國際遺傳算法學(xué)會(ISGA，Internati

15、onal Society of Genetic Algorithms)；1989年，Holland的學(xué)生D. J. Goldherg出版了“Genetic Algorithms in Search, Optimization, and Machine Learning”，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述；1991年，L. Davis編輯出版了遺傳算法手冊，其中包括了遺傳算法在工程技術(shù)和社會生活中大量的應(yīng)用實例。第四節(jié) 遺 傳 算 法 34二、幾個名詞概念 1. 進(jìn)化計算：由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)域的研究人員分別獨立提出的，在相當(dāng)長的時期里相互之間沒有正式溝通。直到90年代

16、，才有所交流。他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，于是提出將這類方法統(tǒng)稱為“進(jìn)化計算” ( Evolutionary Computation ) 。第四節(jié) 遺 傳 算 法 352. 計算智能：計算智能主要包括神經(jīng)計算、進(jìn)化計算和模糊計算等。它們分別從不同的角度模擬人類的智能活動，以使計算機(jī)具有智能。 通常將基于符號處理的傳統(tǒng)人工智能稱為符號智能，以區(qū)別于正在興起的計算智能。符號智能的特點是以知識為基礎(chǔ)，偏重于邏輯推理，而計算智能則是以數(shù)據(jù)為基礎(chǔ)，偏重于數(shù)值計算。第四節(jié) 遺 傳 算 法 36三、達(dá)爾文的自然選擇說遺傳（heredity）：子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變

17、異（variation）：子代與父代，子代不同個體之間總有差異，是生命多樣性的根源；生存斗爭和適者生存：具有適應(yīng)性變異的個體被保留，不具適應(yīng)性變異的個體被淘汰。 自然選擇過程是長期的、緩慢的、連續(xù)的過程。第四節(jié) 遺 傳 算 法 37自組織、自適應(yīng)和自學(xué)習(xí)性 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。本質(zhì)并行性 內(nèi)在并行性與內(nèi)含并行性不需求導(dǎo) 只需目標(biāo)函數(shù)和適應(yīng)度函數(shù)概率轉(zhuǎn)換規(guī)則 強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則四、 遺傳算法的思路與特點 第四節(jié) 遺 傳 算 法 381. 適應(yīng)度計算：按比例的適應(yīng)度函數(shù)（proportional fitness a

18、ssignment）基于排序的適應(yīng)度計算（Rank-based fitness assignment）2.選擇算法：輪盤賭選擇（roulette wheel selection）隨機(jī)遍歷抽樣（stochastic universal selection）局部選擇（local selection）截斷選擇（truncation selection）錦標(biāo)賽選擇（tournament selection）五、 遺傳算法的基本操作 第四節(jié) 遺 傳 算 法 393. 交叉或基因重組實值重組（real valued recombination）：離散重組（discrete recombination）中間

19、重組（intermediate recombination）線性重組（linear recombination）擴(kuò)展線性重組（extended linear recombination）二進(jìn)制交叉（binary valued crossover）：單點交叉（single-point crossover）多點交叉（multiple-point crossover）均勻交叉（uniform crossover）洗牌交叉（shuffle crossover）縮小代理交叉（crossover with reduced surrogate）第四節(jié) 遺 傳 算 法 404. 變異 實值變異 二進(jìn)制變異第四

20、節(jié) 遺 傳 算 法 415.簡單實例Step1. 產(chǎn)生初始種群Step2. 計算適應(yīng)度0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）第四節(jié) 遺 傳 算 法 42Step3. 選擇個體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100

21、1011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174第四節(jié) 遺 傳 算 法 43個體染色體適應(yīng)度選擇概率累積概率100011000008201011110015300000001012410011101001051010101010761110010110127100101101158110000000119

22、9100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000第四節(jié) 遺 傳 算 法 44在01之間產(chǎn)生一個隨機(jī)數(shù)：個體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101

23、101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘

24、汰！第四節(jié) 遺 傳 算 法 450001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011Step4. 交叉0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110100000010110111100110000100111010000011001110100110

25、0000001010011第四節(jié) 遺 傳 算 法 46Step5. 變異0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100110001111010000001011011110011000010010101000001100111010011000000010100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 11000000

26、01 1001110100 0001010011000111101000000101101111001100001001110100000110011101001100000001010011第四節(jié) 遺 傳 算 法 47Step6. 至下一代，適應(yīng)度計算選擇交叉變異，直至滿足終止條件。第四節(jié) 遺 傳 算 法 48函數(shù)優(yōu)化 是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域;組合優(yōu)化 實踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效;自動控制 如基于遺傳算法的模糊控制器優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)等;六、 遺傳算法的應(yīng)用領(lǐng)域 第四節(jié) 遺 傳 算 法 49機(jī)器

27、人智能控制 遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運動軌跡規(guī)劃、機(jī)器人逆運動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動協(xié)調(diào)等;組合圖像處理和模式識別 目前已在圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識別等方面得到了應(yīng)用;人工生命 基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力；遺傳程序設(shè)計 Koza發(fā)展了遺傳程序設(shè)計的慨念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作自動生成計算機(jī)程序;第四節(jié) 遺 傳 算 法 50一、發(fā)展簡介第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 “神經(jīng)網(wǎng)絡(luò)”與“人工神經(jīng)網(wǎng)絡(luò)”1943年，

28、Warren McCulloch和Walter Pitts建立了第一個人工神經(jīng)網(wǎng)絡(luò)模型；1969年，Minsky和Papert發(fā)表Perceptrons；20世紀(jì)80年代，Hopfield將人工神經(jīng)網(wǎng)絡(luò)成功應(yīng)用在組合優(yōu)化問題。511. McCulloch-Pitts神經(jīng)元 現(xiàn)代的神經(jīng)網(wǎng)絡(luò)開始于McCulloch, Pitts(1943)的先驅(qū)工作； 他們的神經(jīng)元模型假定遵循有-無模型律； 如果如此簡單的神經(jīng)元數(shù)目足夠多和適當(dāng)設(shè)置連接權(quán)值并且同步操作, McCulloch & Pitts證明這樣構(gòu)成的網(wǎng)絡(luò)原則上可以計算任何可計算函數(shù)； 標(biāo)志著神經(jīng)網(wǎng)絡(luò)和人工智能的誕生。二、基本概念第五節(jié) 神經(jīng)網(wǎng)絡(luò)

29、優(yōu)化算法 52McCulloch-Pitts神經(jīng)元結(jié)構(gòu) McCulloch-Pitts輸出函數(shù)定義為：InputsignalSynapticweightsSummingfunctionActivationfunctionOutputyx1x2xnw2wnw1-第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 532. 網(wǎng)絡(luò)的構(gòu)建 Y=F(X) x1y1輸出層隱藏層輸入層x2y2ymxn第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 543. 網(wǎng)絡(luò)結(jié)構(gòu)的確定網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) 前向型、反饋型等神經(jīng)元激活函數(shù) 階躍函數(shù) 線性函數(shù) Sigmoid函數(shù)f(x)x0+1第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 55確定的內(nèi)容 權(quán)值wi和確定的方式 學(xué)習(xí)（訓(xùn)練） 有指導(dǎo)

30、的學(xué)習(xí)：已知一組正確的輸入輸出結(jié)果的條件下，神經(jīng)網(wǎng)絡(luò)依據(jù)這些數(shù)據(jù)，調(diào)整并確定權(quán)值； 無指導(dǎo)的學(xué)習(xí)：只有輸入數(shù)據(jù)，沒有正確的輸出結(jié)果情況下，確定權(quán)值。 4. 關(guān)聯(lián)權(quán)值的確定第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 56學(xué)習(xí)與工作的關(guān)系 先學(xué)習(xí)再工作5. 工作階段第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 57多層 兩層以上前向 無反饋1. 一般結(jié)構(gòu)三 、 多層前向神經(jīng)網(wǎng)絡(luò)x1y1輸出層隱藏層輸入層x2y2ymxn第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 58目的 確定權(quán)值方法 反向推導(dǎo)2 反向傳播算法第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 59一般結(jié)構(gòu) 各神經(jīng)元之間存在相互聯(lián)系分類 連續(xù)系統(tǒng)：激活函數(shù)為連續(xù)函數(shù) 離散系統(tǒng)：激活函數(shù)為階躍函數(shù)四 、反饋型神經(jīng)網(wǎng)

31、絡(luò)第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 60Hopfield神經(jīng)網(wǎng)絡(luò) 1982年提出Hopfield反饋神經(jīng)網(wǎng)絡(luò)（HNN），證明在高強(qiáng)度連接下的神經(jīng)網(wǎng)絡(luò)依靠集體協(xié)同作用能自發(fā)產(chǎn)生計算行為。 是典型的全連接網(wǎng)絡(luò)，通過引入能量函數(shù)，使網(wǎng)絡(luò)的平衡態(tài)與能量函數(shù)極小值解相對應(yīng)。第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 61網(wǎng)絡(luò)結(jié)構(gòu) N為網(wǎng)絡(luò)節(jié)點總數(shù)。1. 離散Hopfield神經(jīng)網(wǎng)絡(luò)s1(t+1)s2(t+1)sn(t+1)s1(t)s2(t)sn(t)w12w1nw21w2nwn1wn2第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 62 一般認(rèn)為vj(t)=0時神經(jīng)元保持不變sj(t+1)=sj(t); 一般情況下網(wǎng)絡(luò)是對稱的（wij=wji）且無

32、自反饋（wjj=0）; 整個網(wǎng)絡(luò)的狀態(tài)可用向量s表示：第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 63工作方式 串行（異步，asynchronous）:任一時刻只有一個單元改變狀態(tài)，其余單元保持不變； 并行（同步，synchronous）：某一時刻所有神經(jīng)元同時改變狀態(tài)。穩(wěn)定狀態(tài) 如果從t=0的任一初始態(tài)s(0)開始變化，存在某一有限時刻t，從此以后網(wǎng)絡(luò)狀態(tài)不再變化，即s(t+1)=s(t)，則稱網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)。第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 64能量函數(shù)的定義 異步方式： 同步方式：第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 65能量函數(shù) 能量是有界的： 從任一初始狀態(tài)開始，若在每次迭代時都滿足E0，則網(wǎng)絡(luò)的能量將越來越小，最后趨

33、向于穩(wěn)定狀態(tài)E0 。第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 66網(wǎng)絡(luò)結(jié)構(gòu) 與電子線路對應(yīng)： 放大器神經(jīng)元 電阻、電容神經(jīng)元的時間常數(shù) 電導(dǎo)（電阻的倒數(shù)）權(quán)系數(shù) 2. 連續(xù)Hopfield神經(jīng)網(wǎng)絡(luò)第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 67網(wǎng)絡(luò)的微分方程能量函數(shù) 可證明，若g-1為單調(diào)增且連續(xù)，Cj0，Tji=Tij，則有dE/dt0，當(dāng)且僅當(dāng)dvi/dt=0時dE/dt=0。第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 68能量函數(shù) 將動力系統(tǒng)方程 簡單記為： 如果 ，則稱ve是動力系統(tǒng)的平衡點，也稱ve為吸引子。 隨著時間的增長，神經(jīng)網(wǎng)絡(luò)在狀態(tài)空間中的解軌跡總是向能量函數(shù)減小的方向變化，且網(wǎng)絡(luò)的穩(wěn)定點就是能量函數(shù)的極小點。第五節(jié) 神經(jīng)網(wǎng)絡(luò)

34、優(yōu)化算法 69能量函數(shù) 當(dāng)從某一初始狀態(tài)變化時，網(wǎng)絡(luò)的演變是使E下降，達(dá)到某一局部極小時就停止變化。這些能量的局部極小點就是網(wǎng)絡(luò)的穩(wěn)定點或稱吸引子。第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 70Hopfield網(wǎng)絡(luò)設(shè)計 當(dāng)Hopfield用于優(yōu)化計算時，網(wǎng)絡(luò)的權(quán)值是確定的，應(yīng)將目標(biāo)函數(shù)與能量函數(shù)相對應(yīng)，通過網(wǎng)絡(luò)的運行使能量函數(shù)不斷下降并最終達(dá)到最小，從而得到問題對應(yīng)的極小解。3. Hopfield神經(jīng)網(wǎng)絡(luò)在TSP 中的應(yīng)用(Travelling Salesman Problem)第五節(jié) 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 71Hopfield網(wǎng)絡(luò)設(shè)計 通常需要以下幾方面的工作： （1）選擇合適的問題表示方法，使神經(jīng)網(wǎng)絡(luò)的輸出與問題的解相對應(yīng)； （2）構(gòu)造合適的能量函數(shù)，使其最小