演算法原理 – 模擬退火法(SA)

演算法原模擬退火法(SA)模擬退火法(SimulatedAnnealing)是貪婪演算法的一種，但其大大改善貪婪演算法容陷入?yún)^(qū)域最佳解的況，因?yàn)槟M退火法在貪婪演算法的基礎(chǔ)上，加入治中退火的概。在治的過(guò)程中，會(huì)先將材加熱後再經(jīng)特定速卻，目的是增大晶的體積，並且減少晶格中的缺陷。自然界中的原子原本就會(huì)自停在局部最小能的位置，加熱使能變大，原子會(huì)開(kāi)原位置，而隨機(jī)在其他位置中移動(dòng)，在溫的過(guò)程中，原子們會(huì)趨向低能、高。退火模擬法即是將治中，求最小能態(tài)之自過(guò)程的概抽象化，用一非線性函的全域最佳解。貪婪演算法之所以容陷於區(qū)域最佳解，就是因?yàn)槠錈o(wú)法接受找到的值變差的情形，但在區(qū)域最佳解與全域最佳解中，經(jīng)常解會(huì)先變差，如下圖圖1貪婪演算法陷於區(qū)域最佳解而模擬退火法則是使用波茲曼分佈一一非線性函一決定現(xiàn)是否接受目前變壞的情形，以防陷入?yún)^(qū)域最佳解。模擬退火法的執(zhí)以下為模擬退火法大概的程：輸入一個(gè)目標(biāo)繞射圖形後，產(chǎn)生一個(gè)與目標(biāo)繞射圖形相同大小的矩陣，並計(jì)算其能(評(píng)價(jià)函)。接著，擾動(dòng)一個(gè)或多個(gè)像素(pixel)，並計(jì)算擾動(dòng)後的能，能的變化為負(fù)，則接受此變化；能的變化為正，則用波茲曼分佈計(jì)算此時(shí)接受此變化的機(jī)，再隨機(jī)產(chǎn)生一個(gè)隨機(jī)值，隨機(jī)值比接受此變化的機(jī)高，則接受此變化，反之，則接受。重複上述步驟，待達(dá)到我們?cè)O(shè)定的穩(wěn)態(tài)條件，則依我們?cè)O(shè)定的溫方式溫，直至冰點(diǎn)。最適合用描述模擬退火法的學(xué)模型就是馬克夫鏈 （Markovchain），所謂的馬克夫鏈?zhǔn)敲枋鲆焕m(xù)嘗試的過(guò)程，且當(dāng)前的態(tài)只與上一個(gè)態(tài)相關(guān)，與上一個(gè)態(tài)之前態(tài)無(wú)關(guān)[1]。溫的設(shè)定「初溫的設(shè)定」的問(wèn)題，可大可小。我們可以隨意設(shè)一個(gè)溫為初溫，但如此一，我們?nèi)菘刂颇M退火法，我們能確定在初溫時(shí)，程式接受結(jié)構(gòu)變壞的機(jī)。我們初溫設(shè)太低，雖然程式在一開(kāi)始較容接受結(jié)構(gòu)變差的情形，但其總接受的次亦將較少；我們初溫設(shè)太高，則程式在一開(kāi)始就接受結(jié)構(gòu)變壞的情況，換話，前面做白工，費(fèi)時(shí)間。最常用的方法是統(tǒng)計(jì)的方式，在程式開(kāi)始前先設(shè)定在程式執(zhí)之初，我們希望程式接愛(ài)變壞的機(jī)— -般設(shè)定85%—接著寫-個(gè)模擬退火法，計(jì)算平均的能變化 AE（評(píng)價(jià)函的變化），並取能變化 AE（評(píng)價(jià)函的變化）為正者，最後藉由波茲曼分布P=exp（—AE/kT），反推溫，計(jì)算出的溫即為初溫。順帶一提，在模擬退火法中，B我們會(huì)忽波茲曼常 kB。另一個(gè)初溫的方式是—嘗試錯(cuò)誤，我們?cè)诔淌揭婚_(kāi)始，擇一較高之初溫，並視程式接受結(jié)構(gòu)變差的機(jī)，決定是否要下修或上調(diào)初溫。發(fā)現(xiàn)一開(kāi)始接受的機(jī)小於我們的預(yù)設(shè)值，則加倍初溫並重新執(zhí)程式，反覆這個(gè)步驟，直至接受機(jī)到達(dá)我們的預(yù)設(shè)值。在本文所執(zhí)的模擬退火法，其初溫的訂定是使用統(tǒng)計(jì)的方式。末溫（即冰點(diǎn)）的設(shè)定，最直觀的做法是設(shè)末溫為0，但White與Huang等人分別提出較為嚴(yán)格的定義。White提出，當(dāng)某一個(gè)馬克夫鏈的結(jié)構(gòu)及接續(xù)的個(gè)馬克夫鏈的結(jié)構(gòu)相同，我們視此系統(tǒng)已達(dá)冰點(diǎn)。Huang等人［2］則提出在古個(gè)馬克夫鏈的最後，比較接受改變的結(jié)構(gòu)中，能最大與能最小者的改變，者相同，則改變?yōu)?，意即?dāng)前之馬克夫鏈中，所有結(jié)構(gòu)均擁有相同的能。故模擬退火法已可再需要，末溫為以終止演算。在討初渥及夫渥的制訂後，接下要討如何渥一渥計(jì)劃表。渥計(jì)劃表有許多型式，勝枚舉，筆者出三種被廣泛應(yīng)用的退火方式，即對(duì)型 （Exponential）、柯西（cauchy）、指型（Logarithmic）退火，指型又稱為幾何型，它們的學(xué)表達(dá)式分別如下：對(duì)型：T=T/Inkki柯西型：T二T/kki指型：T=Te-ck或T=akTki k iT由於本文的渥計(jì)表是使用柯西型退火，設(shè)定T=-^，再加上設(shè)定上的方，所以夫k1+k溫設(shè)定為0.04。第一穩(wěn)態(tài)條件輸入一個(gè)目標(biāo)繞射圖形後，產(chǎn)生一個(gè)與目標(biāo)繞射圖形相同大小的矩陣，並計(jì)算其能（評(píng)價(jià)函）。接著，擾動(dòng)一個(gè)或多個(gè)像素（pixel），並計(jì)算擾動(dòng)後的能，能的變化為負(fù)，則接受此變化；能的變化為正，則用波茲曼分佈計(jì)算此時(shí)接受此變化的機(jī)，再隨機(jī)產(chǎn)生一個(gè)隨機(jī)值，隨機(jī)值比接受此變化的機(jī)高，則接受此變化，反之，則接受。重複上述步驟，待被接受的次達(dá)到我們?cè)O(shè)定的次，則依我們?cè)O(shè)定的溫方式溫，直至冰點(diǎn)。在本文中，第一穩(wěn)態(tài)所設(shè)定的「被接受的次」為 1000000次。第二穩(wěn)態(tài)條件輸入一個(gè)目標(biāo)繞射圖形後，產(chǎn)生一個(gè)與目標(biāo)繞射圖形相同大小的矩陣，並計(jì)算其能（評(píng)價(jià)函）。接著，擾動(dòng)一個(gè)或多個(gè)像素（pixel），並計(jì)算擾動(dòng)後的能，能的變化為負(fù)，則接受此變化；能的變化為正，則用波茲曼分佈計(jì)算此時(shí)接受此變化的機(jī)，再隨機(jī)產(chǎn)生一個(gè)隨機(jī)值，隨機(jī)值比接受此變化的機(jī)高，則接受此變化，反之，則接受。我們給定一個(gè)馬克夫的長(zhǎng)，並重複上述步驟，待達(dá)到我們?cè)O(shè)定的馬克夫之長(zhǎng)，則依我們?cè)O(shè)定的溫方式溫，直至冰點(diǎn)；換話，我們?cè)O(shè)定「斷地給予擾動(dòng)」幾次後溫。在本文中，第二穩(wěn)態(tài)所設(shè)定的一個(gè)馬克夫的長(zhǎng)為500000次。第二穩(wěn)態(tài)條件尚有-改進(jìn)的版本一重新模擬退火法，此法與第二穩(wěn)態(tài)-樣，但在每次溫達(dá)冰點(diǎn)時(shí)，會(huì)再以一定的比回溫，以防模擬退火法陷入局部最佳解，但礙於此法在繞射光學(xué)元件的域上成效彰，所以本文予討。 [3]第三穩(wěn)態(tài)條件輸入一個(gè)目標(biāo)繞射圖形後，產(chǎn)生一個(gè)與目標(biāo)繞射圖形相同大小的矩陣，並計(jì)算其能（評(píng)價(jià)函）。接著，擾動(dòng)一個(gè)或多個(gè)像素（pixel），並計(jì)算擾動(dòng)後的能，能的變化為負(fù)，則接受此變化；能的變化為正，則用波茲曼分佈計(jì)算此時(shí)接受此變化的機(jī)，再隨機(jī)產(chǎn)生一個(gè)隨機(jī)值，隨機(jī)值比接受此變化的機(jī)高，則接受此變化，反之，則接受。當(dāng)能差E小於初始能的百分之五；也就是初始相位的能，即達(dá)穩(wěn)態(tài)條件，此時(shí)，得溫一次。在開(kāi)始執(zhí)模擬退火法第三穩(wěn)態(tài)條件前，先以一個(gè)程式斷地對(duì)此繞射光學(xué)元件微擾，並回傳其平均的能變化，接著我們將此能變化乘以一定的比做為穩(wěn)態(tài)條件（在Yoshikawa的文中，是乘以百分之五[4]），然後在程式中，我們也以一個(gè)向評(píng)估函計(jì)算其平均能差，當(dāng)此平均能差小於穩(wěn)態(tài)條件，則依我們?cè)O(shè)定的溫方式溫，直至冰點(diǎn)，而且在每次溫後，平均能差必需重新計(jì)算。在程式開(kāi)始前所計(jì)算出的平均能差所需乘的比，是依繞射光學(xué)元件的需要而設(shè)定，在本文中，第三穩(wěn)態(tài)的穩(wěn)態(tài)條件所乘的比為0.9。

執(zhí)結(jié)果討穩(wěn)態(tài)條件耗費(fèi)時(shí)間(s)總迴圈次接受的回圈次繞射效方均根誤差訊雜比第-穩(wěn)態(tài)條徉17701.512592600284628460.12100.21750.00074924第二穩(wěn)態(tài)條徉7543.332795350000062460.21480.23140.0032第三穩(wěn)態(tài)條徉雖然模擬退火法較容找到最佳解，也是比較好掌控的，但其花費(fèi)的時(shí)間將會(huì)比較多，這也是我們?cè)谟懽罴鸦瘑?wèn)題一NP-Complete的問(wèn)題—時(shí)，我們會(huì)去討其時(shí)間

複雜，因?yàn)槲覀冋业氖亲罴选附狻?，而非最佳「時(shí)間」；必竟魚與熊掌難以兼得。考資[1]W.Feller,“Anintroductiontoprobabilitytheoryanditsapplications”,Wiley,NewYork,vol.1,1950.[2]M.D.Huang,F.RomeoandA.L.Sangiovanni-Vincent