最優(yōu)化讀書筆記

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、精確一維搜索下幾種共扼梯度法的分析比較共扼梯度法是求解無 約束昨線性規(guī) 劃問題的一 種重要方法>針對(duì)的幾種 計(jì)算公式,通過幾個(gè)典型計(jì)算實(shí)例,對(duì)精確一維搜索下 所述 幾種 風(fēng) 的幾種計(jì)葬公式所決定的葬法的收斂效 果進(jìn)行比較,分析 了它們 的數(shù)值 計(jì)算過程、收斂速度及全局收斂性的優(yōu)劣共扼方向法是求解非線性規(guī)劃無約束極值問題的一類方法,共扼梯度法是其中最重要的一種。共扼梯度法中的計(jì)算公式很多，不同的計(jì)算公式所決定的算法的數(shù)值計(jì)算過程、收斂速度及全局收斂性有所不同。非線性規(guī)劃無約束級(jí)值問題的數(shù)學(xué)模型為：。共軛梯度法是逐次利用以為搜索得到的極小點(diǎn)處的梯度方向來生成共軛

2、方向的一種較為有效的共軛方法，是共軛方向法中最重要的一種。用這類方法求解n元二次函數(shù)的極小值問題，最多經(jīng)行n次一維搜就可以求得極值點(diǎn)。由于可微的非二次函數(shù)在極小值點(diǎn)附近的性態(tài)近似于二次函數(shù)，故此類方法也能用于求解可微的非二次函數(shù)的無約束極小值問題。在正定二次函數(shù)的極小化過程中，令在點(diǎn)的梯度為，第迭代方向取為為使方向和共軛，必須滿足：，即，由此解得，稱為共軛系數(shù)。從而得到共軛梯度的一般公式：，其中是步長，共軛系數(shù)是數(shù)值。進(jìn)而，共軛梯度法迭代過程的一般步驟為以下幾步：1） 給定初始點(diǎn)，允許誤差2） 檢查是否滿足收斂準(zhǔn)則，若滿足，則停止迭代，極值點(diǎn)；否則進(jìn)行3；3） 令，置；4） 一維搜索：由公式=

3、，求；5） 令；6） 檢驗(yàn)是否滿足收斂準(zhǔn)則，若滿足，則極值點(diǎn)；否則進(jìn)行7；7） 判斷是否成立。若成立，則令，返回3；否則（即），計(jì)算，并取，令，返回4.1 共軛梯度法的集中算法1.1 PRP算法PRP算法（polak-ribiere-polyak）是由Polak、Ribiere、Polyak在1969年獨(dú)立提出的一種非線性共軛梯度法，PRP法是目前認(rèn)為數(shù)值表現(xiàn)最好的共軛梯度法之一，該方法具有如下形式：,其中，參數(shù)的計(jì)算公式為：1.2 FR算法FR算法（flectcher-reeves）是最早的非線性共軛梯度法，它是由Fletcher和Reeves于1964年將求解線性方程的共軛梯度法推廣得來的

4、。這種方法的形式如下：,其中參數(shù)的計(jì)算公式為：。1.3 共軛下降法 1987年Fletcher引入共軛下降（即CD法）。求解無約束規(guī)劃問題的共軛下降法具體如下形式：,其中參數(shù)的計(jì)算公式為：。1.4 HS法求解無約束規(guī)劃問題額HS法的形式為：其中參數(shù)的計(jì)算公式為：。與PRP方法相比，HS法德一個(gè)重要性質(zhì)是：不論線搜索是否精確，共軛關(guān)系式總是成立，而HS方法的理論性質(zhì)表現(xiàn)與PRP方法很類似。1,5 Dal-Yuan算法 Dai和Yuan在1995年提出該算法，其形式為： 其中參數(shù)的計(jì)算公式為：FR方法的數(shù)值計(jì)算過程不是十分理想，迭代時(shí)可能產(chǎn)生小步長而導(dǎo)致收斂速度較慢；PRP方法是迭代效果最好的非線

5、性共軛梯度法之一，收斂速度較快；HS方法在計(jì)算過程中的收斂效果與PRP方法較為類似；CD方法在計(jì)算過程中的收斂表現(xiàn)與FR方法相差不是很大；DY方法的全局收斂性較好，對(duì)于嚴(yán)格凸函數(shù)，其收斂效果明顯優(yōu)于其它的算法，但是大多數(shù)情況下其收斂效果與FR方法較為類似。二、基于一維搜索和動(dòng)態(tài)調(diào)節(jié)的非線性規(guī)劃 PSO 算法對(duì)非線性規(guī)劃問題而言，最優(yōu)解往往靠近約束區(qū)域的邊界，而距離最優(yōu)解較近的不可行解攜帶的可用信息要遠(yuǎn)比距離最優(yōu)解較遠(yuǎn)的可行解攜帶的信息更重要，因此，在算法的搜索過程中使群體中可行解與不可行解保持一定的比例有助于群體向最優(yōu)解逼近。因此，我們給出下列適應(yīng)度函數(shù)其中：N為群體規(guī)模，p為當(dāng)前群體中可行解

6、的個(gè)數(shù)，和分別為當(dāng)前群體中可行解得最小值與最大值。那么，由上式的適應(yīng)度函數(shù)，對(duì)于群體中的任意兩個(gè)個(gè)體：1）當(dāng)這兩個(gè)個(gè)體可行時(shí)，比較它們的函數(shù)值，函數(shù)值小的當(dāng)選。2）當(dāng)這兩個(gè)個(gè)體可行時(shí)，比較它們違反約束的度，違反約束的度函數(shù)值小的當(dāng)選。3）當(dāng)其中一個(gè)可行，另一個(gè)不可行時(shí)，另一個(gè)可行時(shí)，比較它們與群體中可行解的最小值的偏離程度，如果群體中包含的可行解比較大，則不可行解被選的概率較大，反之，若群體中包含的不可行解的個(gè)數(shù)較大，則可行的個(gè)體被選的概率增大，這樣在選擇的時(shí)候，可以保持群體中可行解和不可行解的一定比例，進(jìn)而利用被選的不可行解來增加群體的多樣性，使得群體向最優(yōu)解逼近。動(dòng)態(tài)一維搜索利用PSO算法

7、求解非線性規(guī)劃問題，一方面，要考慮如何處理和利用約束條件的信息。使得算法更好、更快的向最優(yōu)解靠攏。另一方面，如何使PSO算法跳出局部最優(yōu)區(qū)域，繼續(xù)尋找全局最優(yōu)解，設(shè)計(jì)如下的一種動(dòng)態(tài)一維搜索技術(shù)：情形1 如果，則沿該點(diǎn)目標(biāo)函數(shù)的負(fù)梯度方向在上做一維不精確搜索，這樣的搜索的結(jié)果可使點(diǎn)x向可行域D靠近或進(jìn)入可行域D。這里：是搜索梯度方向權(quán)重，且，為大于等于1的自然數(shù)。三、神經(jīng)網(wǎng)絡(luò)計(jì)算平臺(tái)基于網(wǎng)格的應(yīng)用（模擬退火算法分析）1 算法基本思想 模擬退火算法的特點(diǎn)是在求解過程中，不但接受對(duì)目標(biāo)函數(shù)有改善的狀態(tài)，還以某種概率接受使目標(biāo)函數(shù)惡化的狀態(tài)，這樣避免了過早收斂到某個(gè)局部極值點(diǎn)，從而能夠比較有效地進(jìn)行全

8、局搜索。另外該算法還具有不需要求目標(biāo)函數(shù)的偏導(dǎo)數(shù)，并且程序編寫簡單的優(yōu)點(diǎn)。模擬退火算法的基本思想：（1）初始化：初始溫度T（充分大），初始解狀態(tài)S（是算法迭代的起點(diǎn)），每個(gè)T值的迭代次數(shù)L;(2)對(duì)做第（3）至第6步；（3）產(chǎn)生新解（4）計(jì)算增量，其中為評(píng)價(jià)函數(shù)；（5）若則接受作為新的當(dāng)前解，否則以概率接受作為新的當(dāng)前解；（6）如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。（7）T逐漸減少，且T->0，然后轉(zhuǎn)第2步。在整個(gè)算法過程中，控制系數(shù)T逐漸減小，最終將搜索限制早一個(gè)小區(qū)域內(nèi)。由于可將退火過程控制得足夠慢，會(huì)使系統(tǒng)跳出晶體局

9、部能量極小點(diǎn)。2 模擬退火算法步驟模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟：第一步：由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解第二步：計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。第二步：判斷新解是否被接受，判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropolis準(zhǔn)則：若則接受作為新的當(dāng)前解S，否則以概率接受作為新的當(dāng)前解S。第四步：當(dāng)前解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。模擬退火算法與初值無關(guān)，算法求得的解與初始解狀態(tài)S（是算法迭代的起點(diǎn)）無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率1收斂于全局最優(yōu)

10、解的全局優(yōu)化算法；模擬退火算法具有并行性。模擬退火算法是基于蒙特卡羅（MonteCaro）迭代求解法的一種啟發(fā)式隨機(jī)搜索算法。組合優(yōu)化問題，把每種組合狀態(tài)Si看成某一物質(zhì)體系的微觀狀態(tài)，而將C(Si)看成該物質(zhì)體系在狀態(tài)SI下的能量，并在控制參數(shù)T表示為溫度。讓T從一個(gè)足夠的值慢慢下降，對(duì)每一用Metropolis抽樣法模擬該體系在此T下的熱平衡狀態(tài)，即對(duì)當(dāng)前狀態(tài)S做隨機(jī)擾動(dòng)以產(chǎn)生一個(gè)新的狀態(tài)S，計(jì)算增量并以概率接受S作為新的當(dāng)前狀態(tài)。當(dāng)這樣的隨機(jī)擾動(dòng)重復(fù)足夠后，系統(tǒng)將達(dá)到該溫度下的熱平衡狀態(tài)，且服從Bolztmann分布。四、一種混合遺傳模擬退火算法及其應(yīng)用遺傳算法遺傳算法（Genetic

11、Algorithms，簡稱GA）是J.Holland于1975年受生物進(jìn)化論的啟發(fā)而提出的，它是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化考慮搜索法。遺傳算法模擬自然進(jìn)化中 “優(yōu)勝劣汰、 適者生存”的原理進(jìn)行自學(xué)習(xí)和尋優(yōu) ,它將問題的求解通過編碼表示成染色體 ,由計(jì)算機(jī)隨機(jī)產(chǎn)生一群染色體 ,每個(gè)染色體在問題的 “環(huán)境” 中對(duì)應(yīng)著其本身的適應(yīng)度 ,根據(jù)適者生存的原則 ,從中挑選適應(yīng)度高的個(gè)體進(jìn)行雜交、 變異等基因操作產(chǎn)生出新一代個(gè)體 ,不斷迭代進(jìn)化最終收斂到適應(yīng)度最高的個(gè)體上 ,此個(gè)體經(jīng)過解碼后就是問題的最優(yōu)解. 遺傳算法求解問題的具體實(shí)現(xiàn)過程為:用某種編碼技術(shù)作用于輸入量以

12、形成數(shù)串 ,模擬由數(shù)串組成的群體的進(jìn)化過程. 通過復(fù)制、 交叉、 變異過程有組織地 ,然而又是隨機(jī)地由信息交換來重新組合那些適應(yīng)性好的數(shù)串 ,在每一代中 ,利用上一代數(shù)串結(jié)構(gòu)中適應(yīng)性好的位和段來生成一個(gè)新的數(shù)串 ,并偶爾也在數(shù)串結(jié)構(gòu)中嘗試用新的位和段來替代原來的部分.遺傳算法用簡單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象 ,不受搜索空間的限制性假設(shè)的約束 ,不必要求諸如連續(xù)性、 導(dǎo)數(shù)存在和單峰的假設(shè) ,并且具有內(nèi)在的并行性 ,收斂速度快6 ,所以比較適合用來解決非常困難的尋優(yōu)問題. 遺傳算法具有良好的全局搜索能力 ,可以快速地將解空間中的全體解搜索出 ,而不會(huì)陷入局部最優(yōu)解的快速下降陷阱. 利用它

13、的內(nèi)在并行性 ,可以方便地進(jìn)行分布式計(jì)算 ,加快求解速度. 但是遺傳算法的局部搜索能力較差 ,這就導(dǎo)致了單純的遺傳算法比較費(fèi)時(shí). 混合遺傳模擬退火算法混合遺傳模擬退火算法的基本思想是將遺傳算法與模擬退火算法相結(jié)合而構(gòu)成的一種優(yōu)化算法. 與基本遺傳算法的總體運(yùn)行過程相類似 ,遺傳模擬退火算法也是從一組隨機(jī)產(chǎn)生的初始解(初始群體)開始全局最優(yōu)解的搜索過程 ,它先通過選擇、 交叉、 變異等遺傳操作來產(chǎn)生一組新的個(gè)體 ,然后再獨(dú)立地對(duì)所產(chǎn)生出的各個(gè)個(gè)體進(jìn)行模擬退火過程 ,以其結(jié)果作為下一代群體中的個(gè)體. 這個(gè)運(yùn)行過程反復(fù)迭代地進(jìn)行 ,直到滿足某個(gè)終止條件為止. 遺傳模擬退火算法將遺傳算法和模擬退火算法

14、的優(yōu)點(diǎn)充分結(jié)合起來 ,大大提高了算法的效率. 混合遺傳模擬退火算法的求解過程如下:Step 1. 初始化：進(jìn)化代數(shù)計(jì)數(shù)器k初始值為0，給出種群初始值，給定初始退火溫度Step 2：評(píng)價(jià)當(dāng)前群體的適應(yīng)度。Step 3：執(zhí)行個(gè)體交叉操作，同時(shí)在交叉之后可以附帶保優(yōu)操作：Step 4：執(zhí)行個(gè)體交叉變異操作，根據(jù)變異結(jié)果可以附帶保優(yōu)操作Step 5: 由模擬退火狀態(tài)函數(shù)產(chǎn)生新個(gè)體。Step 6: 以概率接受新個(gè)體，執(zhí)行個(gè)體的模擬退火操作：Step 7：判斷模擬退火抽樣是否穩(wěn)定。若不穩(wěn)定則返回步驟5（Step 5）；若穩(wěn)定則往下執(zhí)行退溫操作Step 8 ：個(gè)體復(fù)制操作：由擇優(yōu)選擇模型保留最佳種群：Ste

15、p 9：終止條件判斷。若不滿足終止條件，則，轉(zhuǎn)到步驟2（Step 2）；若滿足終止條件，則輸出當(dāng)前最優(yōu)個(gè)體，結(jié)束算法。遺傳算法與模擬退火算法的混合策略 遺傳算法與模擬退火算法分析仔細(xì)分析遺傳算法和模擬退火算法的基本原理可以發(fā)現(xiàn):遺傳算法和模擬退火算法各自都有很多的優(yōu)點(diǎn) ,但也存在著很多不足之處 ,兩種優(yōu)化算法有很強(qiáng)的互補(bǔ)性.遺傳算法是模擬生物遺傳和進(jìn)化過程中選擇、 交叉、 變異機(jī)理而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法 ,遺傳算法最為嚴(yán)重的缺陷是 “過早收斂” 問題. 所謂 “過早收斂” 是指在搜索的初期 ,由于優(yōu)良個(gè)體急劇增加使種群失去多樣性 ,從而造成程序陷入局部 ,達(dá)不到全局最優(yōu)解的現(xiàn)象

16、.模擬退火算法是基于金屬退火的機(jī)理而建立起的一種全局最優(yōu)化方法 ,雖然它能夠以隨機(jī)搜索技術(shù)從概率意義上找出目標(biāo)函數(shù)的全局最優(yōu)點(diǎn) ,但它本身也有很多缺陷. 模擬退火算法的不足之處主要是:盡管理論上只要計(jì)算時(shí)間足夠長 ,模擬退火法就可以保證以概率 110 收斂于全局最優(yōu)點(diǎn) ,但是在實(shí)際算法的實(shí)現(xiàn)過程中 ,由于計(jì)算速度和時(shí)間的限制 ,在優(yōu)化效果和計(jì)算時(shí)間之間存在矛盾 ,因而難以保證計(jì)算結(jié)果為全局最優(yōu)點(diǎn) ,優(yōu)化效果不甚理想. 為得到一個(gè)好的近似最優(yōu)解 ,需要進(jìn)行反復(fù)迭代運(yùn)算 ,當(dāng)問題的規(guī)模不可避免地增大時(shí) ,缺乏可行的解決途徑.遺傳算法和模擬退火算法的直接互補(bǔ)性體現(xiàn)在:遺傳算法把握總體的能力較強(qiáng) ,但

17、局部搜索能力較差;模擬退火算法具有較強(qiáng)的局部搜索能力;因此可以將遺傳算法和模擬退火算法相互結(jié)合 ,取長補(bǔ)短. 為了克服遺傳算法和模擬退火算法各自的缺點(diǎn) ,發(fā)揮它們的優(yōu)勢(shì) ,本文將遺傳算法和模擬退火算法混合起來 ,設(shè)計(jì)了混合遺傳模擬退火算法 混合遺傳模擬退火算法用于解決TSP問題 混合遺傳模擬退火算法兼具遺傳算法和模擬退火算法兩者的優(yōu)點(diǎn) ,較為適合于解決 TSP 這種組合優(yōu)化問題 ,能夠做到很好的尋優(yōu). 下面是用混合遺傳模擬退火算法對(duì) TSP問題的求解過程。（1）問題的定義：設(shè)n為城市數(shù)目，為階矩陣，代表城市i到城市j的距離。則問題是要找出遍訪每個(gè)城市恰好一次的一條回路，且其路徑長路為最短。（2

18、）解空間：解空間S可表示為的所有循環(huán)排列的集合，即為的排列表示第i個(gè)城市第個(gè)被訪問。（3）目標(biāo)函數(shù)：目標(biāo)函數(shù)為訪問所有城市的路徑長度或稱為代價(jià)函數(shù)，需求其最小值，選為為最小。表1是用混合遺傳模擬退火算法(GASA) 、 遺傳算法和模擬退火算法進(jìn)行求解 TSP問題過程中試驗(yàn)結(jié)果的比較: 說明:其中最優(yōu)率為求得最優(yōu)值的次數(shù)占據(jù)總求解計(jì)算次數(shù)的比例;迭代總次數(shù)為求解轉(zhuǎn)移迭代總次數(shù). 方差計(jì)算公式為:是最終目標(biāo)k的函數(shù)值，是最優(yōu)目標(biāo)函數(shù)值。使用混合遺傳模擬退火算法 ,將中國 31 個(gè)首府城市(北京、 上海、 拉薩、 昆明、 、 臺(tái)北)之間的距離作為已知條件輸入后 ,求得最短路徑為15 408km. 具體的路徑為:北京 呼和浩特 銀川 蘭州 西寧 烏魯木齊 拉薩 成都 昆明 貴陽 南寧 ?？?廣州 長沙 武漢 南昌 福州 臺(tái)北 杭州 上海 南京 合肥 鄭州 西安 太原 石家莊 濟(jì)南 天津 沈陽 長春 哈爾濱 北京. 從實(shí)驗(yàn)結(jié)果看 ,可以看出