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

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

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

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

(3)若，則接受新解，，轉(zhuǎn)(2)，否則以概率決定是否接受新解。具體方法是：產(chǎn)生0和1之間的一個(gè)隨機(jī)數(shù)r，若，接受新解，否則拒絕新解；(4)重復(fù)第(2),(3)步若干次，使解接近當(dāng)前溫度下的最優(yōu)解，這相當(dāng)于用足夠慢的速度降溫，以保證在每個(gè)溫度時(shí)系統(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)、獨(dú)立集問題(ISP)、調(diào)度問題(SCP)、圖著色問題(GCP)等。例用模擬退火算法求的極小值。3.模擬退火算法的應(yīng)用模擬退火算法具有廣泛的應(yīng)用性，可用于求解許多組合優(yōu)化問題。根據(jù)模擬退火算法的過程（產(chǎn)生新解——計(jì)算目標(biāo)函數(shù)差——判別是否接受新解——接受或舍棄新解），在算法的實(shí)際應(yīng)用中必須解決好三個(gè)問題：第一，問題的數(shù)學(xué)描述；第二，新解的產(chǎn)生和接受機(jī)制；第三，冷卻進(jìn)度表的選取。冷卻進(jìn)度表包括：初始溫度、降溫策略、馬氏鏈長度以及停止準(zhǔn)則四個(gè)方面。此外，還包括隨機(jī)數(shù)發(fā)生器。問題的描述主要包括解空間和目標(biāo)函數(shù)兩部分。解空間為所有可行解的集合，它限定了初始解選取和新解產(chǎn)生的范圍。對(duì)于無約束優(yōu)化問題，任一可能解即為可行解；對(duì)于有約束優(yōu)化問題，解集中還可以包含一些不可行解，同時(shí)在目標(biāo)函數(shù)中加上懲函數(shù)，以懲罰出現(xiàn)的不可行解。新解的產(chǎn)生和接受可分為四個(gè)步驟：第一，給出新解的變換方法，得到一個(gè)產(chǎn)生裝置，以從當(dāng)前解產(chǎn)生一個(gè)新解；第二，計(jì)算新解和當(dāng)前解的目標(biāo)函數(shù)差，由于目標(biāo)函數(shù)差僅由變換部分產(chǎn)生，因此，通常按增量計(jì)算目標(biāo)函數(shù)差；第三，判斷新解是否被接受，判斷的依據(jù)是Metropolis準(zhǔn)則，對(duì)于有約束優(yōu)化問題往往還伴隨有新解可行性的判斷；第四，接受或舍棄新解，若接受，用新解代替當(dāng)前解，同時(shí)修正目標(biāo)函數(shù)值，否則當(dāng)前解與目標(biāo)函數(shù)值保持不變。下面僅對(duì)幾個(gè)典型的組合優(yōu)化問題給出算法描述，以揭示其建立數(shù)學(xué)模型和新解產(chǎn)生裝置的基本方法。(1)旅行商問題（tsp）設(shè)有n個(gè)城市和距離矩陣，其中表示城市i到城市j的距離，i,j=1,…，n，則問題是尋找遍訪每個(gè)城市恰好一次的一條回路，且其路徑長度為最短。求解的模擬退火算法描述如下：①解空間解空間S可表為{1,2，…，n}的所有循環(huán)排列的集合，即其中每一循環(huán)排列表示遍訪n個(gè)城市的一條回路，表示在第i個(gè)次序訪問城市j，并約定。初始解可選為（1,2，…，n）。②目標(biāo)函數(shù)此時(shí)的目標(biāo)函數(shù)為訪問所有城市的路徑長度之和，即其中。③新解的產(chǎn)生（2變換法）任選訪問的序號(hào)u和v，逆轉(zhuǎn)u和v及其之間的訪問順序，此時(shí)新路徑為（設(shè)u<v）④代價(jià)函數(shù)差新解的目標(biāo)函數(shù)差可由公式計(jì)算。特別地，當(dāng)問題為對(duì)稱的，即距離矩陣為對(duì)稱矩陣時(shí)，上式可簡化為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ù)的排擠小生境遺傳算法，其基本思想是：首先比較群體中每兩個(gè)個(gè)體之間的距離，若這個(gè)距離小于預(yù)先指定的距離L，再比較兩者的適應(yīng)度，并對(duì)其中適應(yīng)度較小的個(gè)體施加一個(gè)較強(qiáng)的罰函數(shù)，極大地降低其適應(yīng)度。這樣，對(duì)于在距離L之內(nèi)的兩個(gè)個(gè)體，其中較差的個(gè)體經(jīng)處理后其適應(yīng)度變得更差，在后面的進(jìn)化過程中被淘汰的概率就極大。也就是說，在距離L之內(nèi)將只存在一個(gè)優(yōu)良的個(gè)體，從而既維護(hù)了群體的多樣性，又使得各個(gè)個(gè)體之間保持一定的距離。上述小生境遺傳算法具體實(shí)現(xiàn)過程如下：①隨機(jī)生成M個(gè)初始個(gè)體組成初始群體，并計(jì)算適應(yīng)度；②根據(jù)各個(gè)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排序，記憶前N個(gè)個(gè)體（N<M）；③進(jìn)行比例選擇、單點(diǎn)交叉、基本位變異運(yùn)算；④小生境淘汰運(yùn)算：將第③步得到的M個(gè)個(gè)體和第②步所記憶的N個(gè)個(gè)體合并在一起，得到一個(gè)含有M+N個(gè)個(gè)體的新群體。對(duì)這M+N個(gè)個(gè)體，求出每兩個(gè)個(gè)體和之間的Hamming距離。當(dāng)時(shí)，比較個(gè)體和的適應(yīng)度大小，并對(duì)其中適應(yīng)度較低的個(gè)體處以罰函數(shù)；⑤根據(jù)這M+N個(gè)個(gè)體的新適應(yīng)度對(duì)各個(gè)個(gè)體進(jìn)行降序排序，記憶前N個(gè)個(gè)體；⑥終止條件判斷：若不滿足終止條件，則將第⑤步排序中的前M個(gè)個(gè)體作為新的下一代群體，然后轉(zhuǎn)到第③步；若滿足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束。本文對(duì)上述算法做了兩處改進(jìn)。第一，原算法用Hamming距離來衡量兩個(gè)個(gè)體的遠(yuǎn)近程度。我們認(rèn)為這是不妥的，因?yàn)榧词购Ｃ骶嚯x很小的兩個(gè)個(gè)休，其實(shí)際距離也可能很大。本文采用歐氏距離來衡量個(gè)體的遠(yuǎn)近程度。第二，原算法在進(jìn)行小生境運(yùn)算時(shí)采用的是通常的（1+1）淘汰。Goldberg指出，在小生境的競爭選擇機(jī)制中，(μ+λ)選擇機(jī)制具有較強(qiáng)的選擇壓，可有效地提高種群的多樣性。(μ+λ)選擇允許μ個(gè)父代個(gè)體和λ個(gè)子代個(gè)體共同競爭，確定性地選擇高適應(yīng)值個(gè)體進(jìn)入新的種群。仿真實(shí)驗(yàn)表明，用(μ+λ)競爭選擇能大大提高種群的多樣性，產(chǎn)生較快的收斂速度。綜合考慮計(jì)算速度和計(jì)算量，本文采用（2+2）競爭選擇機(jī)制。為了定量描述改進(jìn)后算法維持種群多樣性的能力以及收斂速度的提高程度，我們采用下列函數(shù)表示種群的多樣性程度

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

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

測(cè)試參數(shù)為種群規(guī)模100，個(gè)體編碼長度20，交叉概率0.9，變異概率0.01，小生境半徑0.5，Penalty=1E-30。下面給出相關(guān)測(cè)試數(shù)據(jù)。從表中可以看出，隨著進(jìn)化代數(shù)的增加，原算法種群的多樣性快速下降，而改進(jìn)算法種群的多樣性能穩(wěn)定在一個(gè)理想的水平，這表明改進(jìn)算法有更多機(jī)會(huì)搜尋到更多的峰。由于新算法采用（2+2）競爭選擇機(jī)制，較原算法增加了計(jì)算量，因此對(duì)于相同進(jìn)化代數(shù)，改進(jìn)算法的運(yùn)行時(shí)間比原算法略長。但在相同的進(jìn)化代數(shù)下，兩者的搜索效率是不同的。仿真實(shí)驗(yàn)表明，采用同樣的參數(shù)，原算法和改進(jìn)算法對(duì)五峰函數(shù)搜索到全部峰的百分比分別約為92%和99%，對(duì)六峰值駝背函數(shù)分別約為67%和86%，鑒于此我們認(rèn)為改進(jìn)算法的相對(duì)收斂速度高于原算法。下面給出用基于罰函數(shù)改進(jìn)的小生境遺傳算法優(yōu)化函數(shù)的例子。例1、初始群體（群體大小M=100）第1代群體第5代群體求最小值時(shí)的第100代群體例2、Shubert函數(shù)此函數(shù)共有760個(gè)局部極小點(diǎn)，其中18個(gè)為全局最小點(diǎn)，最小值為-186.7309。以下給出某一次計(jì)算出的全部18個(gè)為全局最小點(diǎn)的具體數(shù)值，其中第1、2列為橫、縱坐標(biāo)，第3列為目標(biāo)函數(shù)值，第4列為適應(yīng)度。這個(gè)結(jié)果的精確度超過了所有公開報(bào)道的計(jì)算結(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ù)姆灏霃?，否則算法不能保證求出所有最優(yōu)解。然而，在實(shí)際多峰優(yōu)化問題中峰半徑往往無法事先估計(jì)。聚類分析作為一種有效的數(shù)據(jù)分析手段，已經(jīng)在模式識(shí)別、知識(shí)獲取、數(shù)據(jù)挖掘等多個(gè)領(lǐng)域獲得了比較廣泛的應(yīng)用。將聚類分析與排擠小生境遺傳算法相結(jié)合，可以在一定程度上解決峰半徑的設(shè)定問題，大大提高算法的實(shí)用性。在聚類分析方法中最常用的是K—均值聚類方法，其基本流程如下：①隨機(jī)產(chǎn)生q個(gè)中心；②將每一個(gè)點(diǎn)按照某種距離量度分配到最近的一個(gè)中心；③對(duì)于每一個(gè)中心，計(jì)算所有屬于此中心的點(diǎn)的重心，作為新的中心坐標(biāo)；④如果某個(gè)中心發(fā)生變化，轉(zhuǎn)到②；⑤計(jì)算結(jié)束，返回q個(gè)中心位置。上述K—均值算法只能產(chǎn)生預(yù)定的q個(gè)聚類中心，在預(yù)先難以確定小生境數(shù)目時(shí)，往往只能取一個(gè)估計(jì)的保守值。這樣，如果第①步中中心的位置不理想，會(huì)導(dǎo)致最后計(jì)算出來的中心不能真實(shí)反映群體的小生境數(shù)。為了彌補(bǔ)這個(gè)缺陷，我們將通常的K—均值聚類方法做了改進(jìn)，引進(jìn)了一個(gè)最小聚類距離。在第③步后，如果有兩個(gè)中心之間的距離小于最小聚類距離，則將這兩個(gè)中心合并。使用改進(jìn)后的算法產(chǎn)生出來的聚類數(shù)目可能小于預(yù)定值，能在很大程度上反映出群體中實(shí)際的小生境數(shù)。本文通過對(duì)小生境遺傳算法的分析，提出了一種新的基于聚類分析的排