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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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