隨機演算法退火技巧

① 模擬退火演算法和粒子群演算法的優缺點有那些具體點，謝啦

他們有類似之處，但差別也不小。
蒙特卡洛演算法是數值計算方法，原理是利用隨機數來解決計算問題。與它對應的是確定性演算法。也就是說該種演算法屬於隨機演算法，得到的解是近似解。
而遺傳演算法、粒子群、模擬退火雖然也是隨機近似演算法，但這三種都是仿生智能演算法，且比蒙特卡洛演算法要復雜，應用的領域也不太相同。
顯然，蒙特卡洛演算法很輕巧，求解問題更快速。

② 隨機演算法原理

展開專欄
登錄
企鵝號小編
5.7K 篇文章
關注
詳解各種隨機演算法
2018-02-06閱讀 1.4K0
轉自：JarvisChu

之前將的演算法都是確定的，即對於相同的輸入總對應著相同的輸出。但實際中也常常用到不確定的演算法，比如隨機數生成演算法，演算法的結果是不確定的，我們稱這種演算法為（隨機）概率演算法，分為如下四類：

1、數值概率演算法

用於數值問題的求解，通常是近似解

2、蒙特卡洛演算法Monte Carlo

能得到問題的一個解，但不一定是正確解，正確的概率依賴於演算法運行的時間，演算法所用的時間越多，正確的概率也越高。求問題的准確解；

3、拉斯維加斯演算法 Las Vegas

不斷調用隨機演算法求解，直到求得正確解或調用次數達到某個閾值。所以，如果能得到解，一定是正確解。

4、舍伍德演算法 Sherwood

利用隨機演算法改造已有演算法，使得演算法的性能盡量與輸入數據無關，即平滑演算法的性能。它總能求得問題的一個解，且求得的解總是正確的。

隨機數

概述

計算機產生的隨機數都是偽隨機數，通過線性同餘法得到。

方法：產生隨機序列


d稱為種子；m取值越大越好；m，b互質，常取b為質數；

③ 模擬退火演算法的簡介

模擬退火演算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人於1953年提出。1983 年,S. Kirkpatrick 等成功地將退火思想引入到組合優化領域。它是基於Monte-Carlo迭代求解策略的一種隨機尋優演算法，其出發點是基於物理中固體物質的退火過程與一般組合優化問題之間的相似性。模擬退火演算法從某一較高初溫出發，伴隨溫度參數的不斷下降,結合概率突跳特性在解空間中隨機尋找目標函數的全局最優解，即在局部最優解能概率性地跳出並最終趨於全局最優。模擬退火演算法是一種通用的優化演算法，理論上演算法具有概率的全局優化性能,目前已在工程中得到了廣泛應用，諸如VLSI、生產調度、控制工程、機器學習、神經網路、信號處理等領域。
模擬退火演算法是通過賦予搜索過程一種時變且最終趨於零的概率突跳性，從而可有效避免陷入局部極小並最終趨於全局最優的串列結構的優化演算法。

④ 非數值演算法的模擬退火演算法

模擬退火演算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體
內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平
衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis 准則，粒子在溫度T 時趨於
平衡的概率為e-ΔE/(kT)，其中E 為溫度T 時的內能，ΔE 為其改變數，k 為Boltzmann 常
數。用固體退火模擬組合優化問題，將內能E 模擬為目標函數值f，溫度T 演化成控制參數
t，即得到解組合優化問題的模擬退火演算法：由初始解i 和控制參數初值t 開始，對當前解重
復「產生新解→計算目標函數差→接受或舍棄」的迭代，並逐步衰減t 值，演算法終止時的當
前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火
過程由冷卻進度表(Cooling Schele)控制，包括控制參數的初值t 及其衰減因子Δt、每個t
值時的迭代次數L 和停止條件S。
1、模擬退火演算法可以分解為解空間、目標函數和初始解三部分 。 它為問題的所有可能(可行的或包括不可行的)解的集合，它限定了初始解選取和新解產
生時的范圍。對無約束的優化問題，任一可能解(possible solution)即為一可行解(feasible
solution)，因此解空間就是所有可行解的集合；而在許多組合優化問題中，一個解除滿足目
標函數最優的要求外，還必須滿足一組約束(constraint)，因此在解集中可能包含一些不可行
解(infeasible so1ution)。為此，可以限定解空間僅為所有可行解的集合，即在構造解時就考
慮到對解的約束；也可允許解空間包含不可行解，而在目標函數中加上所謂罰函數(penalty
function)以「懲罰」不可行解的出現。 它是對問題的優化目標的數學描述，通常表述為若干優化目標的一個和式。目標函數的
選取必須正確體現對問題的整體優化要求。例如，如上所述，當解空間包含不可行解時，目
標函數中應包含對不可行解的罰函數項，藉此將一個有約束的優化問題轉化為無約束的優化
問題。一般地，目標函數值不一定就是問題的優化目標值，但其對應關系應是顯明的。此外，
目標函數式應當是易於計算的，這將有利於在優化過程中簡化目標函數差的計算以提高演算法
的效率。 是演算法迭代的起點，試驗表明，模擬退火演算法是魯棒的(Robust)，即最終解的求得幾乎
不依賴於初始解的選取。
2、基本思想：
(1) 初始化：初始溫度T(充分大)，初始解狀態S(是演算法迭代的起點)， 每個T 值的迭
代次數L
(2) 對k=1，，L 做第(3)至第6 步：
(3) 產生新解S′
(4) 計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數
(5) 若Δt′<0 則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的
當前解.
(6) 如果滿足終止條件則輸出當前解作為最優解，結束程序。
終止條件通常取為連續若干個新解都沒有被接受時終止演算法。
(7) T 逐漸減少，且T->0，然後轉第2 步。
二、遺傳演算法
遺傳演算法的基本思想是基於Darwin 進化論和Mendel 的遺傳學說的。
Darwin 進化論最重要的是適者生存原理。它認為每一物種在發展中越來越適應環境。物種
每個個體的基本特徵由後代所繼承，但後代又會產生一些異於父代的新變化。在環境變化時，
只有那些能適應環境的個體特徵方能保留下來。
Mendel 遺傳學說最重要的是基因遺傳原理。它認為遺傳以密碼方式存在細胞中，並以基因
形式包含在染色體內。每個基因有特殊的位置並控制某種特殊性質；所以，每個基因產生的
個體對環境具有某種適應性。基因突變和基因雜交可產生更適應於環境的後代。經過存優去
劣的自然淘汰，適應性高的基因結構得以保存下來。
遺傳演算法簡稱GA(Genetic Algorithm)，在本質上是一種不依賴具體問題的直接搜索方法。
1、遺傳演算法的原理
遺傳演算法GA 把問題的解表示成「染色體」，在演算法中也即是以二進制編碼的串。並且，在
執行遺傳演算法之前，給出一群「染色體」，也即是假設解。然後，把這些假設解置於問題的
「環境」中，並按適者生存的原則，從中選擇出較適應環境的「染色體」進行復制，再通過
交叉，變異過程產生更適應環境的新一代「染色體」群。這樣，一代一代地進化，最後就會
收斂到最適應環境的一個「染色體」上，它就是問題的最優解。
長度為L 的n 個二進制串bi(i=1，2，，n)組成了遺傳演算法的初解群，也稱為初始群體。
在每個串中，每個二進制位就是個體染色體的基因。根據進化術語，對群體執行的操作有三
種：
（1）．選擇(Selection)
這是從群體中選擇出較適應環境的個體。這些選中的個體用於繁殖下一代。故有時也稱這一
操作為再生(Reproction)。由於在選擇用於繁殖下一代的個體時，是根據個體對環境的適
應度而決定其繁殖量的，故而有時也稱為非均勻再生(differential reproction)。
（2）．交叉(Crossover)
這是在選中用於繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而
產生新的個體。
（3）．變異(Mutation)
這是在選中的個體中，對個體中的某些基因執行異向轉化。在串bi 中，如果某位基因為1，
產生變異時就是把它變成0；反亦反之。
2、遺傳演算法的特點
（1）．遺傳演算法從問題解的中集開始嫂索，而不是從單個解開始。
這是遺傳演算法與傳統優化演算法的極大區別。傳統優化演算法是從單個初始值迭代求最優解的；
容易誤入局部最優解。遺傳演算法從串集開始搜索，覆蓋面大，利於全局擇優。
（2）．遺傳演算法求解時使用特定問題的信息極少，容易形成通用演算法程序。
由於遺傳演算法使用適應值這一信息進行搜索，並不需要問題導數等與問題直接相關的信息。
遺傳演算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。
（3）．遺傳演算法有極強的容錯能力
遺傳演算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅
速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，
遺傳演算法有很高的容錯能力。
（4）．遺傳演算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。
這說明遺傳演算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最
優解的產生，變異體現了全局最優解的覆蓋。
三、神經網路演算法
「人工神經網路」(ARTIFICIAL NEURAL NETWORK，簡稱A.N.N.)是在對人腦組織結構和
運行機智的認識理解基礎之上模擬其結構和智能行為的一種工程系統。早在本世紀40 年代
初期，心理學家McCulloch、數學家Pitts 就提出了人工神經網路的第一個數學模型，從此開
創了神經科學理論的研究時代。其後，F.Rosenblatt、Widrow 和Hopf、J.J.Hopfield 等學者又
先後提出了感知模型，使得人工神經網路技術得以蓬勃發展。
神經系統的基本構造是神經元(神經細胞)，它是處理人體內各部分之間相互信息傳遞的基本
單元。據神經生物學家研究的結果表明，人的一個大腦一般有10 10 ～10 11
個神經元。每個神經元都由一個細胞體，一個連接其他神經元的軸突和一些向外伸出的其它
較短分支——樹突組成。軸突的功能是將本神經元的輸出信號(興奮)傳遞給別的神經元。其
末端的許多神經末梢使得興奮可以同時傳送給多個神經元。樹突的功能是接受來自其它神經
元的興奮。神經元細胞體將接受到的所有信號進行簡單地處理(如：加權求和，即對所有的
輸入信號都加以考慮且對每個信號的重視程度——體現在權值上——有所不同)後由軸突輸
出。神經元的樹突與另外的神經元的神經末梢相連的部分稱為突觸。
1、神經網路的工作原理
人工神經網路首先要以一定的學習准則進行學習，然後才能工作。現以人工神經網路對手寫
「A」、「B」兩個字母的識別為例進行說明，規定當「A」輸入網路時，應該輸出「1」，而
當輸入為「B」時，輸出為「0」。所以網路學習的准則應該是：如果網路作出錯誤的的判決，
則通過網路的學習，應使得網路減少下次犯同樣錯誤的可能性。首先，給網路的各連接權值
賦予(0，1)區間內的隨機值，將「A」所對應的圖象模式輸入給網路，網路將輸入模式加權
求和、與門限比較、再進行非線性運算，得到網路的輸出。在此情況下，網路輸出為「1」
和「0」的概率各為50%，也就是說是完全隨機的。這時如果輸出為「1」(結果正確)，則使
連接權值增大，以便使網路再次遇到「A」模式輸入時，仍然能作出正確的判斷。如果輸出
為「0」(即結果錯誤)，則把網路連接權值朝著減小綜合輸入加權值的方向調整，其目的在
於使網路下次再遇到「A」模式輸入時，減小犯同樣錯誤的可能性。如此操作調整，當給網
絡輪番輸入若干個手寫字母「A」、「B」後，經過網路按以上學習方法進行若干次學習後，
網路判斷的正確率將大大提高。這說明網路對這兩個模式的學習已經獲得了成功，它已將這
兩個模式分布地記憶在網路的各個連接權值上。當網路再次遇到其中任何一個模式時，能夠
作出迅速、准確的判斷和識別。一般說來，網路中所含的神經元個數越多，則它能記憶、識
別的模式也就越多。
2、人工神經網路的特點
人工神經網路是由大量的神經元廣泛互連而成的系統，它的這一結構特點決定著人工神經網
絡具有高速信息處理的能力。人腦的每個神經元大約有10 3～10 4 個樹突及相應的突
觸，一個人的大腦總計約形成10 14 ～10 15 個突觸。用神經網路的術語來說，
即是人腦具有10 14 ～10 15 個互相連接的存儲潛力。雖然每個神經元的運算
功能十分簡單，且信號傳輸速率也較低(大約100 次/秒)，但由於各神經元之間的極度並行互
連功能，最終使得一個普通人的大腦在約1 秒內就能完成現行計算機至少需要數10 億次處
理步驟才能完成的任務。
人工神經網路的知識存儲容量很大。在神經網路中，知識與信息的存儲表現為神經元之間分
布式的物理聯系。它分散地表示和存儲於整個網路內的各神經元及其連線上。每個神經元及
其連線只表示一部分信息，而不是一個完整具體概念。只有通過各神經元的分布式綜合效果
才能表達出特定的概念和知識。
由於人工神經網路中神經元個數眾多以及整個網路存儲信息容量的巨大，使得它具有很強的
不確定性信息處理能力。即使輸入信息不完全、不準確或模糊不清，神經網路仍然能夠聯想
思維存在於記憶中的事物的完整圖象。只要輸入的模式接近於訓練樣本，系統就能給出正確
的推理結論。
正是因為人工神經網路的結構特點和其信息存儲的分布式特點，使得它相對於其它的判斷識
別系統，如：專家系統等，具有另一個顯著的優點：健壯性。生物神經網路不會因為個別神
經元的損失而失去對原有模式的記憶。最有力的證明是，當一個人的大腦因意外事故受輕微
損傷之後，並不會失去原有事物的全部記憶。人工神經網路也有類似的情況。因某些原因，
無論是網路的硬體實現還是軟體實現中的某個或某些神經元失效，整個網路仍然能繼續工
作。
人工神經網路是一種非線性的處理單元。只有當神經元對所有的輸入信號的綜合處理結果超
過某一門限值後才輸出一個信號。因此神經網路是一種具有高度非線性的超大規模連續時間
動力學系統。它突破了傳統的以線性處理為基礎的數字電子計算機的局限，標志著人們智能
信息處理能力和模擬人腦智能行為能力的一大飛躍。

⑤ 模擬退火演算法每次的解為什麼不一樣

模擬退火每次的解不同是很正常的，因為模擬退火本身是一種隨機演算法，轉移向更差的解不是必然而是概率性的，也就是說每次執行演算法時，執行過程轉移到的解可能都是完全不一樣的。

至於TSP問題，本身屬於NP-hard問題，找不到存在多項式時間復雜度的解。

如果要求精確的解，目前可行的方法有枚舉、分支限界、動態規劃等，但這些方法適用的數據范圍都很小，一旦數據規模變大，它們都將無能為力。

所以目前廣泛使用的大都是一些隨機演算法，比如蟻群、遺傳等，模擬退火就是其中的一種，這些演算法的一大特點就是通過隨機去逼近最優解，但也有可能得到錯解。

只有窮舉法可以保證得到最優解，但是窮舉法在數據量比較大的時候運行時間通常是不能接受的，所以用了各種近似方法。

模擬退火演算法新解的產生和接受可分為如下四個步驟：

第一步是由一個產生函數從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少演算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。

第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。

第三步是判斷新解是否被接受,判斷的依據是一個接受准則，最常用的接受准則是Metropolis准則: 若ΔT<0則接受S′作為新的當前解S，否則以概率exp(-ΔT/T)接受S′作為新的當前解S。

第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。

⑥ 模擬退火演算法解決VRP問題

像這種隨機演算法，一般都要調試好長時間，不斷地修改參數等，才能最終得到滿意解。

⑦ MATLAB模擬退火求解最優化問題時每次的結果都不一樣，如何解決回答後適當加分

模擬退火演算法，蟻群演算法和遺傳演算法都是啟發式隨機搜索演算法，這種演算法理論上式不可能得到最優解的，只能去接近它，由於初始解是隨機的，所以每次運行結果必然是不一樣的。根據你問題的規模運行數十次和數百次，然後求平均值，可以判斷你的演算法優劣。

⑧ 遺傳演算法、粒子群、模擬退火相比於普通的蒙特卡洛演算法有什麼優勢他們相互的優缺點都是什麼

他們有類似之處，但差別也不小。
蒙特卡洛演算法是數值計算方法，原理是利用隨機數來解決計算問題。與它對應的是確定性演算法。也就是說該種演算法屬於隨機演算法，得到的解是近似解。
而遺傳演算法、粒子群、模擬退火雖然也是隨機近似演算法，但這三種都是仿生智能演算法，且比蒙特卡洛演算法要復雜，應用的領域也不太相同。
顯然，蒙特卡洛演算法很輕巧，求解問題更快速。

⑨ 模擬退火演算法 一定能收斂到全局最優解嗎

不一定，這是一個隨機演算法，這就意味著它有可能會止步於部分最優解。所以一般比賽的時候都要交上好幾遍來通過代碼