現(xiàn)代優(yōu)化方法之模擬退火

第三部分現(xiàn)代優(yōu)化方法選講

現(xiàn)代優(yōu)化方法包括禁忌搜索、模擬退火、智能計算等。其中模擬退火、神經(jīng)網(wǎng)絡(luò)和遺傳算法并稱為現(xiàn)代優(yōu)化算法中的三大杰出代表。一、模擬退火算法

在管理科學(xué)、計算機(jī)科學(xué)、分子物理學(xué)、生物學(xué)、超大規(guī)模集成電路設(shè)計、代碼設(shè)計、圖象處理和電子工程等領(lǐng)域中，存在著大量的組合優(yōu)化問題。例如，貨郎擔(dān)問題、最大截問題、0—1背包問題、圖著色問題、設(shè)備布局問題以及布線問題等，這些問題至今仍未找到多項式時間算法。這些問題已被證明是NP完全問題。根據(jù)NP完全性理論，除非P=NP，否則所有的NP難問題都不存在多項式時間算法。但是，這并不意味著問題的終結(jié)。相反，由于這類問題廣泛應(yīng)用性，反而刺激人們以更大的熱情對NP完全問題進(jìn)行研究。為解決這類問題，人們提出了許多近似算法，但這些算法或過于注意個別問題的特征而缺乏通用性，或因所得解強(qiáng)烈地依賴初始解的選擇而缺乏實用性。模擬退火算法是近年提出的一種適合解大規(guī)模組合優(yōu)化問題，特別是解NP完全問題的通用有效的近似算法，與以往近似算法相比，具有描述簡單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受初始條件限制的優(yōu)點，而且特別適合并行計算，因此具有很大的使用價值。同時由于其討論涉及隨機(jī)分析、馬氏鏈理論、漸進(jìn)收斂性等學(xué)科，所以其研究還具有重要的理論意義。1.模擬退火算法的物理背景固體退火過程的物理圖象和統(tǒng)計性質(zhì)是模擬退火算法的物理背景。在熱力學(xué)與統(tǒng)計物理學(xué)的研究領(lǐng)域中，固體退火是其重要的研究對象。固體退火是指先將固體加熱至熔化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過程。在高溫狀態(tài)下，液體的分子彼此之間可以自由移動。如果液體徐徐冷卻，它的分子就會喪失由于溫度而引起的流動性。這時原子就會自己排列起來而形成一種純晶體，它們依次地朝各個方向幾十億倍于單個原子大小的距離，這個純晶狀態(tài)就是該系統(tǒng)的最小能量狀態(tài)，有趣的是：對于一個徐徐冷卻的系統(tǒng)，當(dāng)這些原子在逐漸失去活力的同時，它們自己就同時地排列而形成一個純晶體，使這個系統(tǒng)的能量達(dá)到其最小值。這里我們特別強(qiáng)調(diào)在這個物理系統(tǒng)的冷卻過程中，這些原子就同時的把它們自己排列成一個純晶體的。如果一種金屬熔液是被快速的冷卻，則它不能達(dá)到純晶體狀態(tài)，而是變成一種多晶體或非晶體狀態(tài)，系統(tǒng)處在這種狀態(tài)時具有較高的能量。模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過程的一種通用隨機(jī)搜索技術(shù)，可用馬氏鏈的遍歷理論給它以數(shù)學(xué)上的描述。在搜索最優(yōu)解的過程中，模擬退火除了可以接受優(yōu)化解外，還用一個隨機(jī)準(zhǔn)則(Metropolis準(zhǔn)則)有限地接受惡化解，并使接受惡化解的概率逐漸趨于零，這使得算法有可能從局部最優(yōu)解中跳出，盡可能找到全局最優(yōu)解，并保證了算法的收斂性。1982年Kipatrick等人首次把固體退火與組合極小化聯(lián)系在一起，他們分別用目標(biāo)函數(shù)和組合極小化問題的解替代物理系統(tǒng)的能量和狀態(tài)，從而物理系統(tǒng)內(nèi)粒子的攝動等價于組合極小化問題中解的試探。極小化過程就是：首先在一個高溫（溫度現(xiàn)在就成為一個參數(shù)控制）狀態(tài)下有效的“溶化”解空間，然后慢慢地降低溫度直到系統(tǒng)“晶體”到一個穩(wěn)定解。通過以下示例，我們可以將組合優(yōu)化問題與固體退火進(jìn)行類比：組合優(yōu)化問題固體退火解狀態(tài)最優(yōu)解能量最低狀態(tài)費用函數(shù)能量2.模擬退火算法的基本思想與算法用傳統(tǒng)優(yōu)化算法優(yōu)化多峰值函數(shù)時，往往由于過分追求“下降”而極易陷于局部最優(yōu)解。為了克服這個缺陷，在搜索最優(yōu)解的過程中，模擬退火方法除了接受優(yōu)化解外，還根據(jù)一個隨機(jī)接受準(zhǔn)則有限地接受惡化解，并使接受惡化解的概率逐漸趨于零。這既可使得算法以較大概率跳出局部最優(yōu)解，又保證了算法的收斂性。模擬退火算法的求解過程如下：(1)隨機(jī)產(chǎn)生初始解X0，給定初始溫度T0，令k=0；(2)隨機(jī)產(chǎn)生新解，并計算函數(shù)增量

(3)若，則接受新解，，轉(zhuǎn)(2)，否則以概率決定是否接受新解。具體方法是：產(chǎn)生0和1之間的一個隨機(jī)數(shù)r，若，接受新解，否則拒絕新解；(4)重復(fù)第(2),(3)步若干次，使解接近當(dāng)前溫度下的最優(yōu)解，這相當(dāng)于用足夠慢的速度降溫，以保證在每個溫度時系統(tǒng)都能處于當(dāng)前溫度下的能量最低狀態(tài)；(5)按一定的方式降低溫度，例如，其中；(6)若滿足收斂條件，退火過程結(jié)束，否則，轉(zhuǎn)(2)。通常，收斂條件為。理論已證明：只要初始溫度足夠高，退火過程足夠慢，模擬退火算法以概率1收斂到全局最優(yōu)解。模擬退火算法在許多領(lǐng)域有非常廣泛的應(yīng)用，尤其適用于求解組合優(yōu)化問題。如旅行商問題(TSP)、0-1背包問題(ZKP)、最大截問題(MCP)、獨立集問題(ISP)、調(diào)度問題(SCP)、圖著色問題(GCP)等。例用模擬退火算法求的極小值。3.模擬退火算法的應(yīng)用模擬退火算法具有廣泛的應(yīng)用性，可用于求解許多組合優(yōu)化問題。根據(jù)模擬退火算法的過程（產(chǎn)生新解——計算目標(biāo)函數(shù)差——判別是否接受新解——接受或舍棄新解），在算法的實際應(yīng)用中必須解決好三個問題：第一，問題的數(shù)學(xué)描述；第二，新解的產(chǎn)生和接受機(jī)制；第三，冷卻進(jìn)度表的選取。冷卻進(jìn)度表包括：初始溫度、降溫策略、馬氏鏈長度以及停止準(zhǔn)則四個方面。此外，還包括隨機(jī)數(shù)發(fā)生器。問題的描述主要包括解空間和目標(biāo)函數(shù)兩部分。解空間為所有可行解的集合，它限定了初始解選取和新解產(chǎn)生的范圍。對于無約束優(yōu)化問題，任一可能解即為可行解；對于有約束優(yōu)化問題，解集中還可以包含一些不可行解，同時在目標(biāo)函數(shù)中加上懲函數(shù)，以懲罰出現(xiàn)的不可行解。新解的產(chǎn)生和接受可分為四個步驟：第一，給出新解的變換方法，得到一個產(chǎn)生裝置，以從當(dāng)前解產(chǎn)生一個新解；第二，計算新解和當(dāng)前解的目標(biāo)函數(shù)差，由于目標(biāo)函數(shù)差僅由變換部分產(chǎn)生，因此，通常按增量計算目標(biāo)函數(shù)差；第三，判斷新解是否被接受，判斷的依據(jù)是Metropolis準(zhǔn)則，對于有約束優(yōu)化問題往往還伴隨有新解可行性的判斷；第四，接受或舍棄新解，若接受，用新解代替當(dāng)前解，同時修正目標(biāo)函數(shù)值，否則當(dāng)前解與目標(biāo)函數(shù)值保持不變。下面僅對幾個典型的組合優(yōu)化問題給出算法描述，以揭示其建立數(shù)學(xué)模型和新解產(chǎn)生裝置的基本方法。(1)旅行商問題（tsp）設(shè)有n個城市和距離矩陣，其中表示城市i到城市j的距離，i,j=1,…，n，則問題是尋找遍訪每個城市恰好一次的一條回路，且其路徑長度為最短。求解的模擬退火算法描述如下：①解空間解空間S可表為{1,2，…，n}的所有循環(huán)排列的集合，即其中每一循環(huán)排列表示遍訪n個城市的一條回路，表示在第i個次序訪問城市j，并約定。初始解可選為（1,2，…，n）。②目標(biāo)函數(shù)此時的目標(biāo)函數(shù)為訪問所有城市的路徑長度之和，即其中。③新解的產(chǎn)生（2變換法）任選訪問的序號u和v，逆轉(zhuǎn)u和v及其之間的訪問順序，此時新路徑為（設(shè)u<v）④代價函數(shù)差新解的目標(biāo)函數(shù)差可由公式計算。特別地，當(dāng)問題為對稱的，即距離矩陣為對稱矩陣時，上式可簡化為intd[11][11]={{0,3,93,66,13,100,25,33,9,57,19}, {24,0,33,77,42,21,16,45,34,21,109}, {45,107,0,81,36,16,4,28,25,37,62}, {139,90,80,0,56,7,44,56,20,91,75}, {18,64,188,33,0,11,25,96,5,57,43}, {3,88,18,46,92,0,55,33,20,91,7}, {44,26,33,27,84,39,0,101,9,72,36}, {11,39,24,98,103,76,54,0,50,63,99}, {77,82,67,19,30,42,56,9,0,88,28}, {12,133,32,69,21,52,87,66,43,0,55}, {92,32,81,73,44,24,64,15,77,9,0}};非數(shù)值并行算法——模擬退火算法康立山《科學(xué)出版社》排擠小生境遺傳算法改進(jìn)研究

1、排擠小生境遺傳算法及其改進(jìn)

日本學(xué)者提出了一種基于罰函數(shù)的排擠小生境遺傳算法，其基本思想是：首先比較群體中每兩個個體之間的距離，若這個距離小于預(yù)先指定的距離L，再比較兩者的適應(yīng)度，并對其中適應(yīng)度較小的個體施加一個較強(qiáng)的罰函數(shù)，極大地降低其適應(yīng)度。這樣，對于在距離L之內(nèi)的兩個個體，其中較差的個體經(jīng)處理后其適應(yīng)度變得更差，在后面的進(jìn)化過程中被淘汰的概率就極大。也就是說，在距離L之內(nèi)將只存在一個優(yōu)良的個體，從而既維護(hù)了群體的多樣性，又使得各個個體之間保持一定的距離。上述小生境遺傳算法具體實現(xiàn)過程如下：①隨機(jī)生成M個初始個體組成初始群體，并計算適應(yīng)度；②根據(jù)各個個體的適應(yīng)度對其進(jìn)行降序排序，記憶前N個個體（N<M）；③進(jìn)行比例選擇、單點交叉、基本位變異運(yùn)算；④小生境淘汰運(yùn)算：將第③步得到的M個個體和第②步所記憶的N個個體合并在一起，得到一個含有M+N個個體的新群體。對這M+N個個體，求出每兩個個體和之間的Hamming距離。當(dāng)時，比較個體和的適應(yīng)度大小，并對其中適應(yīng)度較低的個體處以罰函數(shù)；⑤根據(jù)這M+N個個體的新適應(yīng)度對各個個體進(jìn)行降序排序，記憶前N個個體；⑥終止條件判斷：若不滿足終止條件，則將第⑤步排序中的前M個個體作為新的下一代群體，然后轉(zhuǎn)到第③步；若滿足終止條件，則輸出計算結(jié)果，算法結(jié)束。本文對上述算法做了兩處改進(jìn)。第一，原算法用Hamming距離來衡量兩個個體的遠(yuǎn)近程度。我們認(rèn)為這是不妥的，因為即使海明距離很小的兩個個休，其實際距離也可能很大。本文采用歐氏距離來衡量個體的遠(yuǎn)近程度。第二，原算法在進(jìn)行小生境運(yùn)算時采用的是通常的（1+1）淘汰。Goldberg指出，在小生境的競爭選擇機(jī)制中，(μ+λ)選擇機(jī)制具有較強(qiáng)的選擇壓，可有效地提高種群的多樣性。(μ+λ)選擇允許μ個父代個體和λ個子代個體共同競爭，確定性地選擇高適應(yīng)值個體進(jìn)入新的種群。仿真實驗表明，用(μ+λ)競爭選擇能大大提高種群的多樣性，產(chǎn)生較快的收斂速度。綜合考慮計算速度和計算量，本文采用（2+2）競爭選擇機(jī)制。為了定量描述改進(jìn)后算法維持種群多樣性的能力以及收斂速度的提高程度，我們采用下列函數(shù)表示種群的多樣性程度

其中n為種群規(guī)模，為個體的二進(jìn)制編碼長度，為種群中第i個個體的第j個二進(jìn)制的值。顯然，越?。ù螅N群的多樣性就越高（低）。測試函數(shù)為1、五峰函數(shù)

函數(shù)分別在處有極大點，其中為全局極大點。2、六峰值駝背函數(shù)函數(shù)有六個極大點其中為全局極大點，極大值為。

測試參數(shù)為種群規(guī)模100，個體編碼長度20，交叉概率0.9，變異概率0.01，小生境半徑0.5，Penalty=1E-30。下面給出相關(guān)測試數(shù)據(jù)。從表中可以看出，隨著進(jìn)化代數(shù)的增加，原算法種群的多樣性快速下降，而改進(jìn)算法種群的多樣性能穩(wěn)定在一個理想的水平，這表明改進(jìn)算法有更多機(jī)會搜尋到更多的峰。由于新算法采用（2+2）競爭選擇機(jī)制，較原算法增加了計算量，因此對于相同進(jìn)化代數(shù)，改進(jìn)算法的運(yùn)行時間比原算法略長。但在相同的進(jìn)化代數(shù)下，兩者的搜索效率是不同的。仿真實驗表明，采用同樣的參數(shù)，原算法和改進(jìn)算法對五峰函數(shù)搜索到全部峰的百分比分別約為92%和99%，對六峰值駝背函數(shù)分別約為67%和86%，鑒于此我們認(rèn)為改進(jìn)算法的相對收斂速度高于原算法。下面給出用基于罰函數(shù)改進(jìn)的小生境遺傳算法優(yōu)化函數(shù)的例子。例1、初始群體（群體大小M=100）第1代群體第5代群體求最小值時的第100代群體例2、Shubert函數(shù)此函數(shù)共有760個局部極小點，其中18個為全局最小點，最小值為-186.7309。以下給出某一次計算出的全部18個為全局最小點的具體數(shù)值，其中第1、2列為橫、縱坐標(biāo)，第3列為目標(biāo)函數(shù)值，第4列為適應(yīng)度。這個結(jié)果的精確度超過了所有公開報道的計算結(jié)果。

4.8578-7.0835-186.730710.33654.8578-0.8003-186.730710.33654.85785.4829-186.730710.33655.4828-1.4251-186.730910.33655.4828-7.7083-186.730910.33655.48284.8581-186.730910.3365-1.4252-7.0835-186.730910.3365-1.4252-0.8003-186.730910.3365-1.42525.4829-186.730910.3365-7.7083-7.0835-186.730910.3365-7.7083-0.8003-186.730910.3365-0.8003-1.4251-186.730910.3365-0.8003-7.7083-186.730910.3365-7.0835-1.4251-186.730910.3365-7.0835-7.7083-186.730910.3365-0.80034.8581-186.730910.3365-7.08354.8581-186.730910.3365-7.70835.4829-186.730910.33652、基于改進(jìn)K—均值聚類分析的排擠小生境遺傳算法適應(yīng)值共享算法是遺傳算法解決多峰優(yōu)化問題的重要手段之一。標(biāo)準(zhǔn)適應(yīng)值共享算法要求事先知道小生境半徑，并假設(shè)解空間中小生境具有相同的小生境半徑。本文1中討論的排擠小生境算法同樣也要預(yù)先設(shè)定適當(dāng)?shù)姆灏霃剑駝t算法不能保證求出所有最優(yōu)解。然而，在實際多峰優(yōu)化問題中峰半徑往往無法事先估計。聚類分析作為一種有效的數(shù)據(jù)分析手段，已經(jīng)在模式識別、知識獲取、數(shù)據(jù)挖掘等多個領(lǐng)域獲得了比較廣泛的應(yīng)用。將聚類分析與排擠小生境遺傳算法相結(jié)合，可以在一定程度上解決峰半徑的設(shè)定問題，大大提高算法的實用性。在聚類分析方法中最常用的是K—均值聚類方法，其基本流程如下：①隨機(jī)產(chǎn)生q個中心；②將每一個點按照某種距離量度分配到最近的一個中心；③對于每一個中心，計算所有屬于此中心的點的重心，作為新的中心坐標(biāo)；④如果某個中心發(fā)生變化，轉(zhuǎn)到②；⑤計算結(jié)束，返回q個中心位置。上述K—均值算法只能產(chǎn)生預(yù)定的q個聚類中心，在預(yù)先難以確定小生境數(shù)目時，往往只能取一個估計的保守值。這樣，如果第①步中中心的位置不理想，會導(dǎo)致最后計算出來的中心不能真實反映群體的小生境數(shù)。為了彌補(bǔ)這個缺陷，我們將通常的K—均值聚類方法做了改進(jìn)，引進(jìn)了一個最小聚類距離。在第③步后，如果有兩個中心之間的距離小于最小聚類距離，則將這兩個中心合并。使用改進(jìn)后的算法產(chǎn)生出來的聚類數(shù)目可能小于預(yù)定值，能在很大程度上反映出群體中實際的小生境數(shù)。本文通過對小生境遺傳算法的分析，提出了一種新的基于聚類分析的排