程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C#數值計算之模擬退火法簡介(一)

C#數值計算之模擬退火法簡介(一)

編輯：關於C語言

摘要

本文簡介了模擬退火的基本思想，以於模擬時的主要參數的選擇根據，然後給出一個求二維函數極值的具體問題和解法,並給出C#源代碼。

l 概述

在管理科學、計算機科學、分子物理學和生物學以及超大規模集成電路設計、代碼設計、圖像處理和電子工程等科技領域中，存在大量組合優化瓿。其中許多問題如貨郎擔問題、圖著色問題、設備布局問題以及布線問題等，至今沒有找到有效的多項式時間算法。這些問題已被證明是NP完全問題。

1982年,KirkPatrick將退火思想引入組合優化領域，提出一種解大規模組合優化問題的算法，對NP完全組合優化問題尤其有效。這源於固體的退火過程，即先將溫度加到很高,再緩慢降溫(即退火)，使達到能量最低點。如果急速降溫(即為淬火)則不能達到最低點.。

在［1］中的解釋為：Simulation Annealing is a technique which can be applIEd to any minimisation or learning process based on successive update steps (either random or deterministic) where the update step length is proportional to an arbitrarily set parameter which can play the role of a temperature. Then, in analogy with the annealing of metals, the temperature is made high in the early stages of the process for faster minimisation or learning, then is reduced for greater stability.

即：模擬退火算法是一種能應用到求最小值問題或基本先前的更新的學習過程（隨機或決定性的）。在此過程中，每一步更新過程的長度都與相應的參數成正比，這些參數扮演著溫度的角色。然後，與金屬退火原理相類似，在開始階段為了更快地最小化或學習，溫度被升得很高，然後才（慢慢）降溫以求穩定。

l 模擬退火算法的主要思想

就函數最小值問題來說，模擬退火的主要思想是：在搜索區間（二維平面中）隨機游走（即隨機選擇點），再以Metropolis抽樣准則，使隨機游走逐漸收斂於局部最優解。而溫度即是Metropolis算法中的一個重要控制參數，可以認為這個參數的大小控制了隨時過程向局部或全局最優解移動的快慢。

冷卻參數表、領域結構和新解產生器、接受准則和隨機數產生器（即Metropolis算法）一起構成算法的三大支柱。

l 重點抽樣與Metroplis算法：

Metropolis是一種有效的重點抽樣法，其算法為：系統從能量一個狀態變化到另一個狀態時，相應的能量從E1變化到E2，概率為p = exp[ - (E2- E1)/kT ]。如果E2 < E1，系統接收此狀態，否則，以一個隨機的概率接收此或丟棄此狀態。這種經常一定次數的迭代，系統會逐漸趨於一引穩定的分布狀態。

重點抽樣時，新狀態下如果向下則接受（局部最優），若向上（全局搜索），以一定機率接受。模擬退火方法從某個初始解出發,經過大量解的變換後,可以求得給定控制參數值時組合優化問題的相對最優解。然後減小控制參數T的值，重復執行Metropolis算法，就可以在控制參數T趨於零時，最終求得組合優化問題的整體最優解。控制參數的值必須緩慢衰減。

其中溫度是一個Metropolis的重要控制參數，模擬退火可視為遞減控制參數什時Metroplis算法的迭代。開始T值大，可能接受較差的惡化解，隨著T的減小，只能接受較好的惡化解，最後在T趨於0時，就不再接受任何惡化解了。

在無限高溫時，系統立即均勻分布，接受所有提出的變換。T的衰減越小，T到達終點的時間越長；但可使馬可夫鏈越小，到達准平衡分布的時間越短，

l 參數的選擇：

我們稱調整模擬退火法的一系列重要參數為冷卻進度表。它控制參數T的初值及其衰減函數，對應的MARKOV鏈長度和停止條件，非常重要。

一個冷卻進度表應當規定下述參數：

1．控制參數t的初值t0;

2．控制參數t的衰減函數；

3．馬爾可夫鏈的長度Lk。（即每一次隨機游走過程，要迭代多少次，才能趨於一個准平衡分布，即一個局部收斂解位置）

4．結束條件的選擇

有效的冷卻進度表判據：

一．算法的收斂：主要取決於衰減函數和馬可夫鏈的長度及停止准則的選擇

二．算法的實驗性能：最終解的質量和CPU的時間

參數的選擇：

一）控制參數初值T0的選取

一般要求初始值t0的值要充分大，即一開始即處於高溫狀態，且Metropolis的接收率約為1。

二）衰減函數的選取　

衰減函數用於控制溫度的退火速度，一個常用的函數為：T(n + 1) = K*T(n)，其中K是一個非常接近於1的常數。

三）馬可夫鏈長度L的選取

原則是：在衰減參數T的衰減函數已選定的前提下，L應選得在控制參數的每一取值上都能恢復准平衡。

四）終止條件

有很多種終止條件的選擇，各種不同的條件對算法的性能和解的質量有很大影響，本文只介紹一個常用的終止條件。即上一個最優解與最新的一個最優解的之差小於某個容差，即可停止此次馬爾可夫鏈的迭代。

l 例題：

以上說明可能太過於抽象，下一節將以一個實際的例子來說明，其中所有的源碼已貼出，可以從中了解到很多細節。

l 參考文獻：

1． http://www.computer-dictionary-online.org/index.ASP?q=simulated+annealing　計算機詞典

2． Numeric Recipes in C

3．計算方法叢書非數值並行算法（第一冊）模擬退火算法