模擬退火算法的案例
模擬退火算法優化指派問題
1、引言
之前二狗已經分別介紹過了，如何用模擬退火算法和遺傳算法，進行背包問題的求解。其實背包問題是可以看成是一個可以看成是一個比較特殊的，有線性約束的，0-1規劃問題。在數學中還有很多其他特殊的問題，比如指派問題。指派問題可以看成是更特殊的多個背包問題（很多個背包求優，每個背包只能裝一樣物品）。基本指派問題一般可以描述為有n個任務n個人。要求為n個任務分配給指定的人來完成。并且在這種基本情況下，人和任務需要是一一對應的關系。不能有重復，不能出現兩個人做同一個任務，或者一個人同時做兩個任務的情況。（這些情況也屬于指派問題的范疇，但屬于更加復雜的情況，今天就不做講解）。指派問題已經有了明確可解的算法，也就是我們大家都知道的匈牙利算法。同樣的，這個問題也可以使用模擬退火來解決。今天我們就使用模擬退火算法來為大家演示，如何在指派問題進行優化？
2、 數據結構及重點講解
指派矩陣如圖
每行代表每個人單獨做每個工作的時間或費用（cost），每列代表每個工作分別由每個人完成時的cost。矩陣中位于(i,j)的元素是第i個人做第j個工作的cost。將這四個元素相加即為整個問題的最優解。由于是cost，當然越小越好。
模擬退火算法這個名稱的來源大家已經知道了，我們就不再贅述。這里要提的是退火算法中的馬爾可夫鏈。如果將每個特定時間序列上的解空間狀態看成離散的，并將這些離散狀態連成一條鏈的話。那么整個求解過程就是一條馬爾可夫鏈，這一個時刻的狀態，只和上一個相鄰的時間點上的狀態相關，而與之前的時間點狀態都無關。這聽起來有點像還錢。我不管誰欠你的錢，但是我只知道你欠我錢，我只管你要。SA中馬爾可夫鏈的長度就是模擬退火中溫度的變化。
展開 采用模擬退火算法改進懸索結構找形
為了解決上述問題，采用模擬退火算法，即模型更新的比例系數隨著相對誤差的大小變化。當相對誤差較給定相對誤差大時，取模型更新系數為1，當相對誤差小于給定相對誤差的相反數時，采用退火算法，并構建相對誤差與模型更新系數的函數：
其中：factor為模型更新比例系數，A為待定系數，err為相對誤差值
這樣人為需要調整的參數就只有待定系數A。這里的負號確保了即使再迭代的時候錯過了有效解，也可以退回去，確保迭代的有效進行。
也可根據輸出文件，繪制誤差和水平張力隨迭代次數的曲線。
由以上2個曲線可知，隨著迭代的進行，相對誤差和水平張力急劇下降，從而減少了迭代的次數。
另外模擬退火算法本質是一種貪婪算法，收斂的精度與快慢與給定的模型更新比例系數關系非常大。當采用定值更新系數時，更新比例系數越小時，其收斂的精度越高，但是收斂越慢；當更新的比例系數越大時，其收斂精度越低，同時有可能因為過大，導致錯過了有效解，而陷入死循環；在設置時需要綜合考慮。
展開 基于遺傳模擬退火算法的聚類算法-matlab
源碼如下： %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %功能：遺傳模擬優化初始聚類中心示例 %環境：Win7，Matlab2015b %Modi: C.S %時間：2022-07-09 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% 清空環境 clc clear all close all tic load X m=size(X,2);% 樣本特征維數 % 中心點范圍[lb;ub] lb=min(X); ub=max(X); %% 模糊C均值聚類參數 % 設置冪指數為3，最大迭代次數為20，目標函數的終止容限為1e-6 options=[3,20,1e-6]; % 類別數cn cn=4; %% 模擬退火算法參數 q =0.8; % 冷卻系數 T0=100; % 初始溫度 Tend=99.999; % 終止溫度 %% 定義遺傳算法參數 sizepop=10; %個體數目(Numbe of individuals) MAXGEN=100; %最大遺傳代數(Maximum number of generations) NVAR=m*cn; %變量的維數 PRECI=10; %變量的二進制位數(Precision of variables) pc=0.7; pm=0.01; trace=zeros(NVAR+1,MAXGEN); %建立區域描述器(Build field descriptor) FieldD=[rep([PRECI],[1,NVAR]);rep([lb;ub],[1,cn]);rep([1;0;1;1],[1
展開 51基于matlab模擬退火算法矩形排樣 ￥60
基于matlab模擬退火算法矩形排樣，基于最低水平線算法完成矩形板材下料優化，輸出最優剩料率和最后的水平線，可替換自己的數據進行優化，程序已調通，可直接運行。
46基于matlab的模擬退火算法（SA）優化車輛路徑問題（VRP） ￥40.9
基于matlab的模擬退火算法（SA）優化車輛路徑問題（VRP），在位置已知的條件下，確定車輛到各個指定位置的行程路線圖，使得路徑最短，運輸成本最低。一個位置由一臺車服務，且始于起點，返回起點，程序已調通，可直接運行。
模擬退火、遺傳算法和神經網絡之比較
模擬退火和遺傳算法屬于優化領域的，神經元網絡屬于近似模型的國外叫做metamodel（模型的模型），是完全不同的東西，只所以兩者經常出現是因為在優化問題里神經元網絡扮演著重要角色．一般的有數學表達式的優化問題是最簡單的了這中問題是不會出現神經元網絡的，在工程實際優化過程中，目標函數和優化設計變量之間是隱函數的關系而且可能高度的非線形，并且這種問題一次的計算機仿真時間可能就很長，如果用遺傳算法或者模擬退火的話直接優化是相當的消耗時間的，所以很多人引入近似模型的概念，神經元網絡是屬于其中一種，而且可以近似逼近高度非線性的問題．還有就是遺傳算法用到神經元網絡訓練方面，不知道大家對神經元網絡了解多少，其實神經元網絡沒有那么玄，是有數學基礎的，有一種網絡叫誤差反饋網絡，這種網絡在訓練過程中是用剃度法不斷調整權值直到達到滿足誤差才算收斂剃度法有個問題就是求解得到的是局部最優．所以就有人在網絡訓練中引入了遺傳算法來訓練網絡權值．綜上可以看到遺傳算法和神經元網絡的關系是如此的緊密．
展開 新書推薦(3)——《現代優化計算方法》
目錄：
第1章 概論
1.1 組合最優化問題
1.2 計算復雜性的概念
1.3 鄰域的概念
1.4 啟發式算法
1.5 NP,NP完全和NP難
1.6 多項式時間迫近格式
1.7 小結
練習題
參考文獻
第2章 禁忌搜索算法
2.1 局部搜索
2.2 禁忌搜索
2.3 技術問題
2.4 應用案例——圖節點著色和車間作業排序
練習題
參考文獻
第3章 模擬退火算法
3.1 模擬退火算法及模型
3.2 馬爾可夫鏈
3.3 時齊算法的收斂性
3.4 非時齊算法收斂性簡介
3.5 實現的技術問題
3.6 應用案例——下料問題
練習題
參考文獻
第4章 遺傳算法
4.1 遺傳算法
4.2 模板理論
4.3 馬爾可夫鏈收斂分析
4.4 實現的技術問題
4.5 遺傳模擬退火算法
4.6 應用案例——生產批量問題
練習題
參考文獻
第5章 蟻群優化算法
5.1 蟻群優化算法的概念
5.2 算法模型和收斂性分析
5.3 技術問題
5.4 應用案例——醫學診斷的數據挖掘
練習題
參考文獻
第6章 人工神經網絡
6.1 人工神經網絡的基本概念
6.2 單層前向神經網絡
6.3 多層前向神經網絡
6.4 競爭學習神經網絡
6.5 反饋型神經網絡
練習題
參考文獻
第7章 拉格朗日松弛算法
7.1 基于規劃論的松弛方法
7.2 拉格朗日松弛理論
7.3 拉格朗日松弛的進一步討論
7.4 拉格朗日松弛算法
7.5 應用案例——能力約束單機排序問題
練習題
參考文獻
索引
展開 清華大學：一種新的全局優化算法——統計歸納算法
一種新的全局優化算法——統計歸納算法
劉志宏 施工 胡永明
清華大學工程物理系 清華大學核能技術設計研究院
摘要：在多極值問題的優化領域，主要有模擬退火算法（SA），遺傳算法（GA），人工神經網絡算法（ANN），它們都是基于對自然現象模擬的算法。該文從更基本的優化思想出發，基于概率論提出了一種新的全局優化算法——統計歸納算法（SIA）。在一些標準測試函數以及“貨郎擔問題”（TSP）上的計算結果表明，該算法在智能型（所需的函數計算次數）和解的全局性方面都遠遠好于SA和GA。在中國144個城市的TSP問題實例中，它甚至很快就找到了比參考計算中給出的“目前已知的最優路徑”更短的路徑。從這一算法思想的角度，闡述了SA和GA為何對全局優化問題有效，以及SA和GA各自固有的不足之處。
關鍵詞： 全局優化 ，模擬退火算法（SA），遺傳算法（GA），統計歸納算法（SIA）
內容簡介：
1 算法的基本思想
2 算法的結構
3 實例計算
3.1 連續優化問題
3.2 組合優化問題
4 結論
一種新的全局優化算法——統計歸納算法.pdf
展開 壓力管道輸水灌溉優化設計研究進展（上）
3.2.2 基于模擬退火算法的壓力管道輸水灌溉優化設計研究進展
模擬退火算法（Simulated Annealing）于1953年由Metropolis N等提出，Kirkpatrick S等最早在組合優化領域中使用。它主要是受物理中固體物質退火過程的啟發，因為該過程和一般組合優化問題有一定的相似性。模擬退火算法核心的數學思想是采用數值分析中Monte－Carlo迭代求解方法來隨機尋優而得到最優解。在尋優過程中，它通過在全局中給定一個時變的概率來防止計算結果是局部極小的情況，給定概率具有全局優化性與最終趨于零的突跳性，且搜索過程是一種全局的串行結構，運行效率較高［43］。Cunha（1999）等較早地在管道系統優化設計研究中采用了模擬退火逼近算法［44］。王新坤等［45－46］則先是將模擬退火算法與多重群體遺傳算法相結合，建立了管道系統的樹狀管網優化模型，以用于大型樹狀管網的優化設計；后來又設計出一種新的退火遺傳算法，除繼承退火模擬的局部尋優能力外，還兼備遺傳算法的全局尋優能力，大大地提高了求解結果的效率與精度。洪濤等［47］基于模擬退火遺傳算法，提出以造價最小為目標函數，節點壓力為約束條件，標準管徑為決策變量的自壓微灌干管布設優化模型。
目前模擬退火算法在圖象處理、路徑優化、集成電路設計、工業優化調度等方面應用較多，在壓力管道灌溉系統優化設計上應用相對較少。由于該算法與以往的算法相比，具有描述簡單，使用靈活，運行效率高，較少受初始條件限制，適合并行計算等優點，因此未來其在壓力管道灌溉系統優化設計中的應用有較為廣闊的前景。
3.2.3 基于人工神經網絡優化算法的壓力管道輸水灌溉優化設計研究進展
人工神經網絡（Artificial Neural Networks）是受生物學啟發，對生物神經網絡從結構、實現機理和功能上進行模擬與近似的一種智能算法。
展開 ISIGHT里面的部分優化方法介紹
（7）序列二次規劃法（DONLP）：
此方法對拉各朗日法的海森矩陣進行了微小的改動，進行變量的縮放，并且改善了armijo型步長算法。這種算法在設計空間中通過梯度投影法進行搜索。
（8）序列二次規劃法（NLPQL）：
這種算法假設目標函數是連續可微的。基本思想是將目標函數以二階拉氏方程展開，并把約束條件線性化，使得轉化為一個二次規劃問題。二階方程通過quasi－Newton公式得到了改進，而且加入了直線搜索提高了算法的穩定性。
（9）逐次逼近法（SAM）：
逐次逼近法把非線性問題當作線性問題來處理。使用了稀疏矩陣法和單純形法求解線性問題。如果某個變量被聲明成整型，單純形法通過重復大量的矩陣運算來達到預期的最優值。逐次逼近法是在M. Berkalaar和J.J. Dirks提出的二次線性算法。
2.探索優化方法
探索優化法避免了在局部出現最優解的情況。這種方法通常在整個設計空間中搜索全局最優值。iSIGHT中有以下兩種：
（1）多島遺傳算法（MIGA）：
在多島遺傳算法中，和其他的遺傳算法一樣每個設計點都有一個適應度值,這個值是建立在目標函數值和約束罰函數值的基數上。個體如有好的目標函數值，罰函數也就有一個更高的適應度值。多島遺傳法區別于傳統遺傳算法的最大區別在于每個種群都被分為若干個子種群，也稱為島。分別在各自的子種群中進行傳統的遺傳算法。一些個體被選出來周期的“移民”到其他的島上。這種操作成為“移民”。有兩個參數控制著移民過程：移民間隔（每次移民之后繁殖后代的個數）；移民率（移民個體所占的百分比）。
（2）自適應模擬退火算法（ASA）：
自適應模擬退火算法非常適用于用算法簡單的編碼來解決高度非線性優化問題，尤其是當發現找全局目標值比尋求好的設計方法更為重要的時候。這種方法能夠辨別不同的局部最優解。該算法能夠以最小的成本就獲得最優解。
展開 ISIGHT中的優化方法
（7）序列二次規劃法（DONLP）：
此方法對拉各朗日法的海森矩陣進行了微小的改動，進行變量的縮放，并且改善了armijo型步長算法。這種算法在設計空間中通過梯度投影法進行搜索。
（8）序列二次規劃法（NLPQL）：
這種算法假設目標函數是連續可微的。基本思想是將目標函數以二階拉氏方程展開，并把約束條件線性化，使得轉化為一個二次規劃問題。二階方程通過quasi－Newton公式得到了改進，而且加入了直線搜索提高了算法的穩定性。
（9）逐次逼近法（SAM）：
逐次逼近法把非線性問題當做線性問題來處理。使用了稀疏矩陣法和單純形法求解線性問題。如果某個變量被聲明成整型，單純形法通過重復大量的矩陣運算來達到預期的最優值。逐次逼近法是在M. Berkalaar和J.J. Dirks提出的二次線性算法。
2. 探索優化方法
探索優化法避免了在局部出現最優解的情況。這種方法通常在整個設計空間中搜索全局最優值。iSIGHT中有以下兩種：
（1）多島遺傳算法（MIGA）：
在多島遺傳算法中，和其他的遺傳算法一樣每個設計點都有一個適應度值,這個值是建立在目標函數值和約束罰函數值的基數上。個體如有好的目標函數值，罰函數也就有一個更高的適應度值。多島遺傳法區別于傳統遺傳算法的最大區別在于每個種群都被分為若干個子種群，也稱為島。分別在各自的子種群中進行傳統的遺傳算法。一些個體被選出來周期的“移民”到其他的島上。這種操作成為“移民”。有兩個參數控制著移民過程：移民間隔（每次移民之后繁殖后代的個數）；移民率（移民個體所占的百分比）。
（2）自適應模擬退火算法（ASA）：
自適應模擬退火算法非常適用于用算法簡單的編碼來解決高度非線性優化問題，尤其是當發現找全局目標值比尋求好的設計方法更為重要的時候。
展開 
iSIGHT中優化方法種類
（2）自適應模擬退火算法- Adaptive Simulated Annealing（ASA）：
自適應模擬退火算法非常適用于用算法簡單的編碼來解決高度非線性優化問題，尤其是當發現找全局目標值比尋求好的設計方法更為重要的時候。這種方法能夠辨別不同的局部最優解。該算法能夠以最小的成本就獲得最優解。
3、專家系統優化
（1）定向啟發式搜索算法-Directed Heuristic Search (DHS)：
定向啟發式搜索算法只注重于可以直接影響到優化解的參數。
iSIGHT中優化算法分類.pdf
展開 飛機及其工裝零件智能化檢測規劃技術
對此我們采用了聚類算法與改進模擬退火算法相結合的混合優化算法優化選擇測量方向：首先通過聚類算法合并具有相同許用測量方向的測量點以大幅減小問題規模，然后再采用改進的模擬退火算法優化選擇測量必需的最少測量方向。
基于上述技術方法我們開發了一個面向坐標測量機應用的飛機及其工裝零件智能化檢測規劃原型系統。用戶可以自行定義形狀特征及其檢測知識并將其存入檢測知識庫。系統能夠采用統一的特征識別算法自動識別用戶自定義的任意類型的形狀特征，并引用用戶定義的檢測知識自動完成采樣點分布和測量方向優選等工作，最后生成測量程序，控制坐標測量機自動完成工件檢測。該系統能夠滿足諸如飛機結構件一類的大型復雜零件需要檢測復雜形狀特征以及便于拓展形狀特征檢測范圍的迫切需求，并已在多個重大航空產品的研制中得到應用。自系統投入使用以來，平均每人每年完成的檢測規劃任務量由應用系統前的182.5項提高到1125.4項，顯著提升了飛機及其工裝零件檢測規劃的自動化和智能化程度以及檢測規劃和實際測量的效率，為縮短飛機研制周期、降低研制成本做出了貢獻。
展開 飛機及其工裝零件智能化檢測規劃技術
對此我們采用了聚類算法與改進模擬退火算法相結合的混合優化算法優化選擇測量方向：首先通過聚類算法合并具有相同許用測量方向的測量點以大幅減小問題規模，然后再采用改進的模擬退火算法優化選擇測量必需的最少測量方向。
基于上述技術方法我們開發了一個面向坐標測量機應用的飛機及其工裝零件智能化檢測規劃原型系統。用戶可以自行定義形狀特征及其檢測知識并將其存入檢測知識庫。系統能夠采用統一的特征識別算法自動識別用戶自定義的任意類型的形狀特征，并引用用戶定義的檢測知識自動完成采樣點分布和測量方向優選等工作，最后生成測量程序，控制坐標測量機自動完成工件檢測。該系統能夠滿足諸如飛機結構件一類的大型復雜零件需要檢測復雜形狀特征以及便于拓展形狀特征檢測范圍的迫切需求，并已在多個重大航空產品的研制中得到應用。自系統投入使用以來，平均每人每年完成的檢測規劃任務量由應用系統前的182.5項提高到1125.4項，顯著提升了飛機及其工裝零件檢測規劃的自動化和智能化程度以及檢測規劃和實際測量的效率，為縮短飛機研制周期、降低研制成本做出了貢獻。
展開 遺傳算法方面論文
遺傳算法方面論文 01<BR><Font color=#FF0000><B>.PS.:</B>該帖附件于2007-07-29 09:02:41被向陽評為4星級，為發貼者加分80。</Font><BR><Font color=#FF0000><B>點評:</B></Font>
SECTAM18.pdf
避免近親繁殖的遺傳算法.pdf
多目標優化遺傳算法的收斂性定義及實例研究.pdf
防止遺傳算法成熟前收斂的有效方法英.PDF
改進遺傳算法在非線性熱傳導參數識別中的應用.PDF
基于純數值函數優化的一種混合遺傳算法.pdf
基于擴展串的等價遺傳算法的收斂性.PDF
基于擴展串的等價遺傳算法的收斂性.PDF
基于遺傳算法的微機電系統魯棒性優化設計.pdf
基于遺傳算法的支持向量機時間序列預測模型優化.pdf
均勻設計法在GA欺騙問題中的應用研究.pdf
求解全局最優化的遺傳 算法的研究.pdf
十進制遺傳算法的收斂性分析.PDF
演化算法的收斂性分析及算法改進.PDF
一種全局優化算法遺傳算法_單純形法.pdf
遺傳模擬退火算法在約束求解中的應用.pdf
遺傳算法的早熟收斂.pdf
遺傳算法機理的研究.pdf
展開 