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

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

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

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

在管理科學(xué)、計(jì)算機(jī)科學(xué)、分子物理學(xué)、生物學(xué)、超大規(guī)模集成電路設(shè)計(jì)、代碼設(shè)計(jì)、圖象處理和電子工程等領(lǐng)域中，存在著大量的組合優(yōu)化問(wèn)題。例如，貨郎擔(dān)問(wèn)題、最大截問(wèn)題、0—1背包問(wèn)題、圖著色問(wèn)題、設(shè)備布局問(wèn)題以及布線問(wèn)題等，這些問(wèn)題至今仍未找到多項(xiàng)式時(shí)間算法。這些問(wèn)題已被證明是NP完全問(wèn)題。一、模擬退火算法根據(jù)NP完全性理論，除非P=NP，否則所有的NP難問(wèn)題都不存在多項(xiàng)式時(shí)間算法。但是，這并不意味著問(wèn)題的終結(jié)。相反，由于這類問(wèn)題廣泛應(yīng)用性，反而刺激人們以更大的熱情對(duì)NP完全問(wèn)題進(jìn)行研究。為解決這類問(wèn)題，人們提出了許多近似算法，但這些算法或過(guò)于注意個(gè)別問(wèn)題的特征而缺乏通用性，或因所得解強(qiáng)烈地依賴初始解的選擇而缺乏實(shí)用性。模擬退根據(jù)NP完全性理論，除非P=NP，否則所有的NP難問(wèn)題都不存火算法是近年提出的一種適合解大規(guī)模組合優(yōu)化問(wèn)題，特別是解NP完全問(wèn)題的通用有效的近似算法，與以往近似算法相比，具有描述簡(jiǎn)單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受初始條件限制的優(yōu)點(diǎn)，而且特別適合并行計(jì)算，因此具有很大的使用價(jià)值。同時(shí)由于其討論涉及隨機(jī)分析、馬氏鏈理論、漸進(jìn)收斂性等學(xué)科，所以其研究還具有重要的理論意義。火算法是近年提出的一種適合解大規(guī)模組合優(yōu)化問(wèn)題，特別是解NP1.模擬退火算法的物理背景固體退火過(guò)程的物理圖象和統(tǒng)計(jì)性質(zhì)是模擬退火算法的物理背景。在熱力學(xué)與統(tǒng)計(jì)物理學(xué)的研究領(lǐng)域中，固體退火是其重要的研究對(duì)象。固體退火是指先將固體加熱至熔化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過(guò)程。1.模擬退火算法的物理背景

在高溫狀態(tài)下，液體的分子彼此之間可以自由移動(dòng)。如果液體徐徐冷卻，它的分子就會(huì)喪失由于溫度而引起的流動(dòng)性。這時(shí)原子就會(huì)自己排列起來(lái)而形成一種純晶體，它們依次地朝各個(gè)方向幾十億倍于單個(gè)原子大小的距離，這個(gè)純晶狀態(tài)就是該系統(tǒng)的最小能量狀態(tài)，有趣的是：對(duì)于一個(gè)徐徐冷卻的系統(tǒng)，當(dāng)這些原子在逐漸失去活力的同時(shí)，它們自己就同時(shí)地排列在高溫狀態(tài)下，液體的分子彼此之間可以自由移動(dòng)而形成一個(gè)純晶體，使這個(gè)系統(tǒng)的能量達(dá)到其最小值。這里我們特別強(qiáng)調(diào)在這個(gè)物理系統(tǒng)的冷卻過(guò)程中，這些原子就同時(shí)的把它們自己排列成一個(gè)純晶體的。如果一種金屬熔液是被快速的冷卻，則它不能達(dá)到純晶體狀態(tài)，而是變成一種多晶體或非晶體狀態(tài)，系統(tǒng)處在這種狀態(tài)時(shí)具有較高的能量。而形成一個(gè)純晶體，使這個(gè)系統(tǒng)的能量達(dá)到其最小值。這里我們特別

模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過(guò)程的一種通用隨機(jī)搜索技術(shù)，可用馬氏鏈的遍歷理論給它以數(shù)學(xué)上的描述。在搜索最優(yōu)解的過(guò)程中，模擬退火除了可以接受優(yōu)化解外，還用一個(gè)隨機(jī)準(zhǔn)則(Metropolis準(zhǔn)則)有限地接受惡化解，并使接受惡化解的概率逐漸趨于零，這使得算法有可能從局部最優(yōu)解中跳出，盡可能找到全局最優(yōu)解，并保證了算法的收斂性。模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過(guò)程1982年Kipatrick等人首次把固體退火與組合極小化聯(lián)系在一起，他們分別用目標(biāo)函數(shù)和組合極小化問(wèn)題的解替代物理系統(tǒng)的能量和狀態(tài)，從而物理系統(tǒng)內(nèi)粒子的攝動(dòng)等價(jià)于組合極小化問(wèn)題中解的試探。極小化過(guò)程就是：首先在一個(gè)高溫（溫度現(xiàn)在就成為一個(gè)參數(shù)控制）狀態(tài)下有效的“溶化”解空間，然后慢慢地降低溫度直到系統(tǒng)“晶體”到一個(gè)穩(wěn)定解。1982年Kipatrick等人首次把固體退

通過(guò)以下示例，我們可以將組合優(yōu)化問(wèn)題與固體退火進(jìn)行類比：組合優(yōu)化問(wèn)題固體退火解狀態(tài)最優(yōu)解能量最低狀態(tài)費(fèi)用函數(shù)能量通過(guò)以下示例，我們可以將組合優(yōu)化問(wèn)題與固體退2.模擬退火算法的基本思想與算法用傳統(tǒng)優(yōu)化算法優(yōu)化多峰值函數(shù)時(shí)，往往由于過(guò)分追求“下降”而極易陷于局部最優(yōu)解。為了克服這個(gè)缺陷，在搜索最優(yōu)解的過(guò)程中，模擬退火方法除了接受優(yōu)化解外，還根據(jù)一個(gè)隨機(jī)接受準(zhǔn)則有限地接受惡化解，并使接受惡化解的概率逐漸趨于零。這既可使得算法以較大概率跳出局部最優(yōu)解，又保證了算法的收斂性。2.模擬退火算法的基本思想與算法模擬退火算法的求解過(guò)程如下：(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，若，接受新解，否則拒模擬退火算法的求解過(guò)程如下：絕新解；(4)重復(fù)第(2),(3)步若干次，使解接近當(dāng)前溫度下的最優(yōu)解，這相當(dāng)于用足夠慢的速度降溫，以保證在每個(gè)溫度時(shí)系統(tǒng)都能處于當(dāng)前溫度下的能量最低狀態(tài)；(5)按一定的方式降低溫度，例如，其中；(6)若滿足收斂條件，退火過(guò)程結(jié)束，否則，轉(zhuǎn)(2)。絕新解；

通常，收斂條件為。理論已證明：只要初始溫度足夠高，退火過(guò)程足夠慢，模擬退火算法以概率1收斂到全局最優(yōu)解。通常

模擬退火算法在許多領(lǐng)域有非常廣泛的應(yīng)用，尤其適用于求解組合優(yōu)化問(wèn)題。如旅行商問(wèn)題(TSP)、0-1背包問(wèn)題(ZKP)、最大截問(wèn)題(MCP)、獨(dú)立集問(wèn)題(ISP)、調(diào)度問(wèn)題(SCP)、圖著色問(wèn)題(GCP)等。例用模擬退火算法求的極小值。模擬退火算法在許多領(lǐng)域有非常廣泛的應(yīng)用，尤其3.模擬退火算法的應(yīng)用模擬退火算法具有廣泛的應(yīng)用性，可用于求解許多組合優(yōu)化問(wèn)題。根據(jù)模擬退火算法的過(guò)程（產(chǎn)生新解——計(jì)算目標(biāo)函數(shù)差——判別是否接受新解——接受或舍棄新解），在算法的實(shí)際應(yīng)用中必須解決好三個(gè)問(wèn)題：第一，問(wèn)題的數(shù)學(xué)描述；第二，新解的產(chǎn)生和接受機(jī)制；第三，冷卻進(jìn)度表的選取。冷卻進(jìn)度表包括：初始溫3.模擬退火算法的應(yīng)用度、降溫策略、馬氏鏈長(zhǎng)度以及停止準(zhǔn)則四個(gè)方面。此外，還包括隨機(jī)數(shù)發(fā)生器。問(wèn)題的描述主要包括解空間和目標(biāo)函數(shù)兩部分。解空間為所有可行解的集合，它限定了初始解選取和新解產(chǎn)生的范圍。對(duì)于無(wú)約束優(yōu)化問(wèn)題，任一可能解即為可行解；對(duì)于有約束優(yōu)化問(wèn)題，解集中還可以包含一些不可行解，同時(shí)在目標(biāo)函數(shù)中加上懲函數(shù)，以懲罰出現(xiàn)的不可行解。度、降溫策略、馬氏鏈長(zhǎng)度以及停止準(zhǔn)則四個(gè)方面。此外，還包括

新解的產(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)化問(wèn)題往往還伴隨有新解可行性的判斷；第四，接受或舍棄新新解的產(chǎn)生和接受可分為四個(gè)步驟：第一，給出新解，若接受，用新解代替當(dāng)前解，同時(shí)修正目標(biāo)函數(shù)值，否則當(dāng)前解與目標(biāo)函數(shù)值保持不變。下面僅對(duì)幾個(gè)典型的組合優(yōu)化問(wèn)題給出算法描述，以揭示其建立數(shù)學(xué)模型和新解產(chǎn)生裝置的基本方法。解，若接受，用新解代替當(dāng)前解，同時(shí)修正目標(biāo)函數(shù)值，否則當(dāng)前解(1)旅行商問(wèn)題（tsp）設(shè)有n個(gè)城市和距離矩陣，其中表示城市i到城市j的距離，i,j=1,…，n，則問(wèn)題是尋找遍訪每個(gè)城市恰好一次的一條回路，且其路徑長(zhǎng)度為最短。求解的模擬退火算法描述如下：①解空間解空間S可表為{1,2，…，n}的所有循環(huán)排列的集合，即(1)旅行商問(wèn)題（tsp）其中每一循環(huán)排列表示遍訪n個(gè)城市的一條回路，表示在第i個(gè)次序訪問(wèn)城市j，并約定。初始解可選為（1,2，…，n）。②目標(biāo)函數(shù)此時(shí)的目標(biāo)函數(shù)為訪問(wèn)所有城市的路徑長(zhǎng)度之和，即其中。其中每一循環(huán)排列表示遍訪n個(gè)城市的一條回路，③新解的產(chǎn)生（2變換法）任選訪問(wèn)的序號(hào)u和v，逆轉(zhuǎn)u和v及其之間的訪問(wèn)順序，此時(shí)新路徑為（設(shè)u<v）④代價(jià)函數(shù)差新解的目標(biāo)函數(shù)差可由公式計(jì)算。特別地，當(dāng)問(wèn)題為對(duì)稱的，即距離矩陣為對(duì)稱矩陣時(shí)，上式可簡(jiǎn)化為③新解的產(chǎn)生（2變換法）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}};現(xiàn)代優(yōu)化方法之模擬退火課件非數(shù)值并行算法——模擬退火算法康立山《科學(xué)出版社》非數(shù)值并行算法排擠小生境遺傳算法改進(jìn)研究

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

日本學(xué)者提出了一種基于罰函數(shù)的排擠小生境遺傳算法，其基本思想是：首先比較群體中每?jī)蓚€(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)處排擠小生境遺傳算法改進(jìn)研究理后其適應(yīng)度變得更差，在后面的進(jìn)化過(guò)程中被淘汰的概率就極大。也就是說(shuō)，在距離L之內(nèi)將只存在一個(gè)優(yōu)良的個(gè)體，從而既維護(hù)了群體的多樣性，又使得各個(gè)個(gè)體之間保持一定的距離。上述小生境遺傳算法具體實(shí)現(xiàn)過(guò)程如下：①隨機(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īng)度變得更差，在后面的進(jìn)化過(guò)程中被淘汰的概率就極大。④小生境淘汰運(yùn)算：將第③步得到的M個(gè)個(gè)體和第②步所記憶的N個(gè)個(gè)體合并在一起，得到一個(gè)含有M+N個(gè)個(gè)體的新群體。對(duì)這M+N個(gè)個(gè)體，求出每?jī)蓚€(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è)體作為新的下一代群體，然④小生境淘汰運(yùn)算：將第③步得到的M個(gè)個(gè)體和第②步所記憶的后轉(zhuǎn)到第③步；若滿足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束。本文對(duì)上述算法做了兩處改進(jìn)。第一，原算法用Hamming距離來(lái)衡量?jī)蓚€(gè)個(gè)體的遠(yuǎn)近程度。我們認(rèn)為這是不妥的，因?yàn)榧词购Ｃ骶嚯x很小的兩個(gè)個(gè)休，其實(shí)際距離也可能很大。本文采用歐氏距離來(lái)衡量個(gè)體的遠(yuǎn)近程度。第二，原算法在進(jìn)行小生境運(yùn)算時(shí)采用的是通常的（1+1）淘汰。Goldberg指出，在小生境的競(jìng)爭(zhēng)選擇機(jī)制中，(μ+λ)選擇機(jī)制具有較強(qiáng)的選擇壓，后轉(zhuǎn)到第③步；若滿足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束?？捎行У靥岣叻N群的多樣性。(μ+λ)選擇允許μ個(gè)父代個(gè)體和λ個(gè)子代個(gè)體共同競(jìng)爭(zhēng)，確定性地選擇高適應(yīng)值個(gè)體進(jìn)入新的種群。仿真實(shí)驗(yàn)表明，用(μ+λ)競(jìng)爭(zhēng)選擇能大大提高種群的多樣性，產(chǎn)生較快的收斂速度。綜合考慮計(jì)算速度和計(jì)算量，本文采用（2+2）競(jìng)爭(zhēng)選擇機(jī)制。為了定量描述改進(jìn)后算法維持種群多樣性的能力以及收斂速度的提高程度，我們采用下列函數(shù)表示種群的多樣性程度

可有效地提高種群的多樣性。(μ+λ)選擇允許μ個(gè)父代個(gè)體和λ其中n為種群規(guī)模，為個(gè)體的二進(jìn)制編碼長(zhǎng)度，為種群中第i個(gè)個(gè)體的第j個(gè)二進(jìn)制的值。顯然，越小（大），種群的多樣性就越高（低）。測(cè)試函數(shù)為1、五峰函數(shù)

現(xiàn)代優(yōu)化方法之模擬退火課件函數(shù)分別在處有極大點(diǎn)，其中為全局極大點(diǎn)。2、六峰值駝背函數(shù)現(xiàn)代優(yōu)化方法之模擬退火課件函數(shù)有六個(gè)極大點(diǎn)其中為全局極大點(diǎn)，極大值為。

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

測(cè)試參數(shù)為種群規(guī)模100，個(gè)體編碼長(zhǎng)度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ìng)爭(zhēng)選擇機(jī)制，較原算法增加了計(jì)算量，因此對(duì)于相同進(jìn)化代數(shù)，測(cè)試參數(shù)為種群規(guī)模100，個(gè)體編碼長(zhǎng)度20，改進(jìn)算法的運(yùn)行時(shí)間比原算法略長(zhǎng)。但在相同的進(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ù)的例子。改進(jìn)算法的運(yùn)行時(shí)間比原算法略長(zhǎng)。但在相同的進(jìn)化代數(shù)下，兩者的例1、初始群體（群體大小M=100）例1、第1代群體第1代群體第5代群體第5代群體求最小值時(shí)的第100代群體求最小值時(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é)果的精確度超過(guò)了所有公開(kāi)報(bào)道的計(jì)算結(jié)果。例2、Shubert函數(shù)現(xiàn)代優(yōu)化方法之模擬退火課件

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.33654.8578-7.0835-186.73現(xiàn)代優(yōu)化方法之模擬退火課件2、基于改進(jìn)K—均值聚類分析的排擠小生境遺傳算法適應(yīng)值共享算法是遺傳算法解決多峰優(yōu)化問(wèn)題的重要手段之一。標(biāo)準(zhǔn)適應(yīng)值共享算法要求事先知道小生境半徑，并假設(shè)解空間中小生境具有相同的小生境半徑。本文1中討論的排擠小生境算法同樣也要預(yù)先設(shè)定適當(dāng)?shù)姆灏霃?，否則算法不能保證求出所有最優(yōu)解。然而，在實(shí)際多峰優(yōu)化問(wèn)題中峰半徑往往無(wú)法事先估計(jì)。2、基于改進(jìn)K—均值聚類分析的排擠小生境遺傳算法

聚類分析作為一種有效的數(shù)據(jù)分析手段，已經(jīng)在模式識(shí)別、知識(shí)獲取、數(shù)據(jù)挖掘等多個(gè)領(lǐng)域獲得了比較廣泛的應(yīng)用。將聚類分析與排擠小生境遺傳算法相結(jié)合，可以在一定程度上解決峰半徑的設(shè)定問(wèn)題，大大提高算法的實(shí)用性。在聚類分析方法中最常用的是K—均值聚類方法，其基本流程如下：聚類分析作為一種有效的數(shù)據(jù)分析手段，已經(jīng)在模①隨機(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ì)的保守值。這樣，如果第①步中中心的①隨機(jī)產(chǎn)生q個(gè)中心；位置不理想，會(huì)導(dǎo)致最后計(jì)算出來(lái)的中心不能真實(shí)反映群體的小生境數(shù)。為了彌補(bǔ)這個(gè)缺陷，我們將通常的K—均值聚類方法做了改進(jìn)，引進(jìn)了一個(gè)最小聚類距離。在第③步后，如果有兩個(gè)中心之間的距離小于最小聚類距離，則將這兩個(gè)中心合并。使用改進(jìn)后的算法產(chǎn)生出來(lái)的聚類數(shù)目可能小于預(yù)定值，能在很大程度上反映出群體中實(shí)際的小生境數(shù)。位置不理想，會(huì)導(dǎo)致最后計(jì)算出來(lái)的中心不能真實(shí)反映群體的小生境

本文通過(guò)對(duì)小生境遺傳算法的分析，提出了一種新的基于聚類分析的排擠小生境算法，這種算法將聚類分析、排擠技術(shù)有機(jī)地結(jié)合起來(lái)，可以有效地搜索多模函數(shù)空間的多個(gè)極值點(diǎn)，同時(shí)可以通過(guò)調(diào)節(jié)最小聚類距離控制收斂到的小生境的數(shù)目，避免找到無(wú)效的極值點(diǎn)，這種算法無(wú)需事先確定生境的具體數(shù)目和生境半徑的大小，能夠適應(yīng)各種問(wèn)題的優(yōu)化。本文通過(guò)對(duì)小生境遺傳算法的分析，提出了一種新

算法的具體步驟如下：①隨機(jī)生成M個(gè)初始個(gè)體組成初始群體，并計(jì)算適應(yīng)度；②根據(jù)各個(gè)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排序，記憶前N個(gè)個(gè)體(N<M)；③使用改進(jìn)的K-均值算法對(duì)群體進(jìn)行聚類分析，將群體劃分為q個(gè)聚類；④計(jì)算每個(gè)聚類中個(gè)體的數(shù)目，計(jì)算個(gè)體的競(jìng)爭(zhēng)適應(yīng)度；⑤按照個(gè)體適應(yīng)度進(jìn)行選擇、交叉、變異運(yùn)算；算法的具體步驟如下：

⑥將第⑤步得到的M個(gè)子代個(gè)體和第②步所記憶的N個(gè)個(gè)體合并在一起，得到一個(gè)含有M+N個(gè)個(gè)體的新群體。確定新群體中的個(gè)代屬于哪個(gè)聚類，在每一個(gè)聚類中計(jì)算每?jī)蓚€(gè)個(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é)⑥將第⑤步得到的M個(gè)子代個(gè)體和第②步所記憶的N個(gè)個(gè)體合并在果，算法結(jié)束。3、數(shù)值實(shí)驗(yàn)為了測(cè)試基于改進(jìn)K—均值聚類分析的排擠小生境遺傳算法的性能，我們選擇了下列幾個(gè)難度較大的標(biāo)準(zhǔn)測(cè)試函數(shù)。例3、不均勻分布等高峰函數(shù)該函數(shù)有5個(gè)不均勻分布的峰，分別為，峰高均為1.000。果，算法結(jié)束?，F(xiàn)代優(yōu)化方法之模擬退火課件例4、不均勻分布不等高峰函數(shù)該函數(shù)有5個(gè)不均勻分布的峰，分別為峰高分別為。例4、不均勻分布不等高峰函數(shù)例6、二元不均勻分布等高峰函數(shù)該函數(shù)有4個(gè)不均勻分布的峰，分別在峰高均為2500。由圖形可以看出，該函數(shù)的峰比較平坦，性能不佳的算法很難精確搜索到全部四個(gè)峰。例6、二元不均勻分布等高峰函數(shù)現(xiàn)代優(yōu)化方法之模擬退火課件

下面給出用基于改進(jìn)K—均值聚類分析的排擠小生境遺傳算法連續(xù)三次的計(jì)算結(jié)果。x=3.0000-3.7687-2.80373.5845y=2.2509-3.27983.1230-1.8486z=2498.82500.02500.02500.0x=-3.75003.56253.0030-2.8076y=-3.2549-1.84271.99803.1318z=2499.92500.02500.02500.0

x=-2.81253.0034-3.77783.5845y=3.12891.9981-3.2827-1.8457z=2500.02500.02500.02500.0下面給出用基于改進(jìn)K—均值聚類分析的排擠小生現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件例6、復(fù)雜欺騙性問(wèn)題其中，，定義為：顯然，是一個(gè)簡(jiǎn)單欺騙性問(wèn)題，它有兩個(gè)高度為1的峰和一個(gè)高度為0.640576的峰。復(fù)雜欺騙性問(wèn)題由5個(gè)這樣的簡(jiǎn)單欺騙性問(wèn)題相加而成，例6、復(fù)雜欺騙性問(wèn)題它的峰的數(shù)量約為，其中全局峰僅有32個(gè)，分別在,

，…，。之所以稱之為復(fù)雜欺騙性問(wèn)題，不僅因?yàn)槠渚薮蟮木植糠鍞?shù)量，而且因?yàn)楸姸嗟木植糠灏鼑址?，這就使得即使較好的算法也極難尋找到所有全局峰。大量計(jì)算顯示，本文提出的算法在優(yōu)化復(fù)雜欺騙性問(wèn)題時(shí)效果欠佳，多數(shù)情況下只能找到8個(gè)全局最優(yōu)解，只有偶爾能找到16個(gè)全局最優(yōu)解。它的峰的數(shù)量約為，其中全局峰僅現(xiàn)代優(yōu)化方法之模擬退火課件例7、復(fù)雜多峰函數(shù)其中該函數(shù)有8個(gè)不均勻分布的峰，峰的高度相差比較懸殊，很難同時(shí)搜索到所有8個(gè)峰。

例7、復(fù)雜多峰函數(shù)現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件現(xiàn)代優(yōu)化方法之模擬退火課件一、概念1、梯度2、海色（Hessain）矩陣3、凸函數(shù)4、共軛方向二、問(wèn)題1、最優(yōu)化中下降算法的基本思想和算法結(jié)構(gòu)2、0.618法的基本思想與步驟3、最速下降法的缺陷4、擬牛頓法對(duì)牛頓法的改進(jìn)之處一、概念三、證明：在最速下降法中，相鄰兩次搜索方向正交。

四、模擬退火算法與遺傳算法與傳統(tǒng)優(yōu)化方法相比各有什么優(yōu)缺點(diǎn)？五、你能否搜集一些資料，說(shuō)明本門(mén)課中所介紹的一些優(yōu)化算法，特別是現(xiàn)代優(yōu)化算法可以用于解決你所學(xué)專業(yè)中的某些問(wèn)題。三、證明：在最速下降法中，相鄰兩次搜索方向正交。兩條巷道間的最短距離這是一個(gè)來(lái)自新集煤礦的實(shí)際問(wèn)題。某礦井中有兩條巷道，巷道可近似為半圓柱面，現(xiàn)要求一條巷道的工作面到另一條巷道的最短距離。根據(jù)建立的坐標(biāo)系和現(xiàn)場(chǎng)數(shù)據(jù)，可以得出其中一條巷道工作面所在的平面方程為巷道工作面為下列四個(gè)點(diǎn)所圍成的矩形部分兩條巷道間的最短距離另一條巷道的方程為根據(jù)上述數(shù)據(jù)計(jì)算工作面到巷道的最短距離。

現(xiàn)代優(yōu)化方法之模擬退火課件考核方式及所占比例：平時(shí)出勤（20%）+實(shí)際問(wèn)題建模計(jì)算（30%）+書(shū)面考試（閉卷）（50%）下周一書(shū)面考試，下周五交實(shí)際問(wèn)題計(jì)算答卷?？己朔绞郊八急壤褐R(shí)回顧KnowledgeReview祝您成功！知識(shí)回顧KnowledgeReview祝您成功！第三部分現(xiàn)代優(yōu)化方法選講

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

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

在管理科學(xué)、計(jì)算機(jī)科學(xué)、分子物理學(xué)、生物學(xué)、超大規(guī)模集成電路設(shè)計(jì)、代碼設(shè)計(jì)、圖象處理和電子工程等領(lǐng)域中，存在著大量的組合優(yōu)化問(wèn)題。例如，貨郎擔(dān)問(wèn)題、最大截問(wèn)題、0—1背包問(wèn)題、圖著色問(wèn)題、設(shè)備布局問(wèn)題以及布線問(wèn)題等，這些問(wèn)題至今仍未找到多項(xiàng)式時(shí)間算法。這些問(wèn)題已被證明是NP完全問(wèn)題。一、模擬退火算法根據(jù)NP完全性理論，除非P=NP，否則所有的NP難問(wèn)題都不存在多項(xiàng)式時(shí)間算法。但是，這并不意味著問(wèn)題的終結(jié)。相反，由于這類問(wèn)題廣泛應(yīng)用性，反而刺激人們以更大的熱情對(duì)NP完全問(wèn)題進(jìn)行研究。為解決這類問(wèn)題，人們提出了許多近似算法，但這些算法或過(guò)于注意個(gè)別問(wèn)題的特征而缺乏通用性，或因所得解強(qiáng)烈地依賴初始解的選擇而缺乏實(shí)用性。模擬退根據(jù)NP完全性理論，除非P=NP，否則所有的NP難問(wèn)題都不存火算法是近年提出的一種適合解大規(guī)模組合優(yōu)化問(wèn)題，特別是解NP完全問(wèn)題的通用有效的近似算法，與以往近似算法相比，具有描述簡(jiǎn)單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受初始條件限制的優(yōu)點(diǎn)，而且特別適合并行計(jì)算，因此具有很大的使用價(jià)值。同時(shí)由于其討論涉及隨機(jī)分析、馬氏鏈理論、漸進(jìn)收斂性等學(xué)科，所以其研究還具有重要的理論意義?；鹚惴ㄊ墙晏岢龅囊环N適合解大規(guī)模組合優(yōu)化問(wèn)題，特別是解NP1.模擬退火算法的物理背景固體退火過(guò)程的物理圖象和統(tǒng)計(jì)性質(zhì)是模擬退火算法的物理背景。在熱力學(xué)與統(tǒng)計(jì)物理學(xué)的研究領(lǐng)域中，固體退火是其重要的研究對(duì)象。固體退火是指先將固體加熱至熔化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過(guò)程。1.模擬退火算法的物理背景

在高溫狀態(tài)下，液體的分子彼此之間可以自由移動(dòng)。如果液體徐徐冷卻，它的分子就會(huì)喪失由于溫度而引起的流動(dòng)性。這時(shí)原子就會(huì)自己排列起來(lái)而形成一種純晶體，它們依次地朝各個(gè)方向幾十億倍于單個(gè)原子大小的距離，這個(gè)純晶狀態(tài)就是該系統(tǒng)的最小能量狀態(tài)，有趣的是：對(duì)于一個(gè)徐徐冷卻的系統(tǒng)，當(dāng)這些原子在逐漸失去活力的同時(shí)，它們自己就同時(shí)地排列在高溫狀態(tài)下，液體的分子彼此之間可以自由移動(dòng)而形成一個(gè)純晶體，使這個(gè)系統(tǒng)的能量達(dá)到其最小值。這里我們特別強(qiáng)調(diào)在這個(gè)物理系統(tǒng)的冷卻過(guò)程中，這些原子就同時(shí)的把它們自己排列成一個(gè)純晶體的。如果一種金屬熔液是被快速的冷卻，則它不能達(dá)到純晶體狀態(tài)，而是變成一種多晶體或非晶體狀態(tài)，系統(tǒng)處在這種狀態(tài)時(shí)具有較高的能量。而形成一個(gè)純晶體，使這個(gè)系統(tǒng)的能量達(dá)到其最小值。這里我們特別

模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過(guò)程的一種通用隨機(jī)搜索技術(shù)，可用馬氏鏈的遍歷理論給它以數(shù)學(xué)上的描述。在搜索最優(yōu)解的過(guò)程中，模擬退火除了可以接受優(yōu)化解外，還用一個(gè)隨機(jī)準(zhǔn)則(Metropolis準(zhǔn)則)有限地接受惡化解，并使接受惡化解的概率逐漸趨于零，這使得算法有可能從局部最優(yōu)解中跳出，盡可能找到全局最優(yōu)解，并保證了算法的收斂性。模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過(guò)程1982年Kipatrick等人首次把固體退火與組合極小化聯(lián)系在一起，他們分別用目標(biāo)函數(shù)和組合極小化問(wèn)題的解替代物理系統(tǒng)的能量和狀態(tài)，從而物理系統(tǒng)內(nèi)粒子的攝動(dòng)等價(jià)于組合極小化問(wèn)題中解的試探。極小化過(guò)程就是：首先在一個(gè)高溫（溫度現(xiàn)在就成為一個(gè)參數(shù)控制）狀態(tài)下有效的“溶化”解空間，然后慢慢地降低溫度直到系統(tǒng)“晶體”到一個(gè)穩(wěn)定解。1982年Kipatrick等人首次把固體退

通過(guò)以下示例，我們可以將組合優(yōu)化問(wèn)題與固體退火進(jìn)行類比：組合優(yōu)化問(wèn)題固體退火解狀態(tài)最優(yōu)解能量最低狀態(tài)費(fèi)用函數(shù)能量通過(guò)以下示例，我們可以將組合優(yōu)化問(wèn)題與固體退2.模擬退火算法的基本思想與算法用傳統(tǒng)優(yōu)化算法優(yōu)化多峰值函數(shù)時(shí)，往往由于過(guò)分追求“下降”而極易陷于局部最優(yōu)解。為了克服這個(gè)缺陷，在搜索最優(yōu)解的過(guò)程中，模擬退火方法除了接受優(yōu)化解外，還根據(jù)一個(gè)隨機(jī)接受準(zhǔn)則有限地接受惡化解，并使接受惡化解的概率逐漸趨于零。這既可使得算法以較大概率跳出局部最優(yōu)解，又保證了算法的收斂性。2.模擬退火算法的基本思想與算法模擬退火算法的求解過(guò)程如下：(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，若，接受新解，否則拒模擬退火算法的求解過(guò)程如下：絕新解；(4)重復(fù)第(2),(3)步若干次，使解接近當(dāng)前溫度下的最優(yōu)解，這相當(dāng)于用足夠慢的速度降溫，以保證在每個(gè)溫度時(shí)系統(tǒng)都能處于當(dāng)前溫度下的能量最低狀態(tài)；(5)按一定的方式降低溫度，例如，其中；(6)若滿足收斂條件，退火過(guò)程結(jié)束，否則，轉(zhuǎn)(2)。絕新解；

通常，收斂條件為。理論已證明：只要初始溫度足夠高，退火過(guò)程足夠慢，模擬退火算法以概率1收斂到全局最優(yōu)解。通常

模擬退火算法在許多領(lǐng)域有非常廣泛的應(yīng)用，尤其適用于求解組合優(yōu)化問(wèn)題。如旅行商問(wèn)題(TSP)、0-1背包問(wèn)題(ZKP)、最大截問(wèn)題(MCP)、獨(dú)立集問(wèn)題(ISP)、調(diào)度問(wèn)題(SCP)、圖著色問(wèn)題(GCP)等。例用模擬退火算法求的極小值。模擬退火算法在許多領(lǐng)域有非常廣泛的應(yīng)用，尤其3.模擬退火算法的應(yīng)用模擬退火算法具有廣泛的應(yīng)用性，可用于求解許多組合優(yōu)化問(wèn)題。根據(jù)模擬退火算法的過(guò)程（產(chǎn)生新解——計(jì)算目標(biāo)函數(shù)差——判別是否接受新解——接受或舍棄新解），在算法的實(shí)際應(yīng)用中必須解決好三個(gè)問(wèn)題：第一，問(wèn)題的數(shù)學(xué)描述；第二，新解的產(chǎn)生和接受機(jī)制；第三，冷卻進(jìn)度表的選取。冷卻進(jìn)度表包括：初始溫3.模擬退火算法的應(yīng)用度、降溫策略、馬氏鏈長(zhǎng)度以及停止準(zhǔn)則四個(gè)方面。此外，還包括隨機(jī)數(shù)發(fā)生器。問(wèn)題的描述主要包括解空間和目標(biāo)函數(shù)兩部分。解空間為所有可行解的集合，它限定了初始解選取和新解產(chǎn)生的范圍。對(duì)于無(wú)約束優(yōu)化問(wèn)題，任一可能解即為可行解；對(duì)于有約束優(yōu)化問(wèn)題，解集中還可以包含一些不可行解，同時(shí)在目標(biāo)函數(shù)中加上懲函數(shù)，以懲罰出現(xiàn)的不可行解。度、降溫策略、馬氏鏈長(zhǎng)度以及停止準(zhǔn)則四個(gè)方面。此外，還包括

新解的產(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)化問(wèn)題往往還伴隨有新解可行性的判斷；第四，接受或舍棄新新解的產(chǎn)生和接受可分為四個(gè)步驟：第一，給出新解，若接受，用新解代替當(dāng)前解，同時(shí)修正目標(biāo)函數(shù)值，否則當(dāng)前解與目標(biāo)函數(shù)值保持不變。下面僅對(duì)幾個(gè)典型的組合優(yōu)化問(wèn)題給出算法描述，以揭示其建立數(shù)學(xué)模型和新解產(chǎn)生裝置的基本方法。解，若接受，用新解代替當(dāng)前解，同時(shí)修正目標(biāo)函數(shù)值，否則當(dāng)前解(1)旅行商問(wèn)題（tsp）設(shè)有n個(gè)城市和距離矩陣，其中表示城市i到城市j的距離，i,j=1,…，n，則問(wèn)題是尋找遍訪每個(gè)城市恰好一次的一條回路，且其路徑長(zhǎng)度為最短。求解的模擬退火算法描述如下：①解空間解空間S可表為{1,2，…，n}的所有循環(huán)排列的集合，即(1)旅行商問(wèn)題（tsp）其中每一循環(huán)排列表示遍訪n個(gè)城市的一條回路，表示在第i個(gè)次序訪問(wèn)城市j，并約定。初始解可選為（1,2，…，n）。②目標(biāo)函數(shù)此時(shí)的目標(biāo)函數(shù)為訪問(wèn)所有城市的路徑長(zhǎng)度之和，即其中。其中每一循環(huán)排列表示遍訪n個(gè)城市的一條回路，③新解的產(chǎn)生（2變換法）任選訪問(wèn)的序號(hào)u和v，逆轉(zhuǎn)u和v及其之間的訪問(wèn)順序，此時(shí)新路徑為（設(shè)u<v）④代價(jià)函數(shù)差新解的目標(biāo)函數(shù)差可由公式計(jì)算。特別地，當(dāng)問(wèn)題為對(duì)稱的，即距離矩陣為對(duì)稱矩陣時(shí)，上式可簡(jiǎn)化為③新解的產(chǎn)生（2變換法）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}};現(xiàn)代優(yōu)化方法之模擬退火課件非數(shù)值并行算法——模擬退火算法康立山《科學(xué)出版社》非數(shù)值并行算法排擠小生境遺傳算法改進(jìn)研究

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

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

可有效地提高種群的多樣性。(μ+λ)選擇允許μ個(gè)父代個(gè)體和λ其中n為種群規(guī)模，為個(gè)體的二進(jìn)制編碼長(zhǎng)度，為種群中第i個(gè)個(gè)體的第j個(gè)二進(jìn)制的值。顯然，越?。ù螅?，種群的多樣性就越高（低）。測(cè)試函數(shù)為1、五峰函數(shù)

現(xiàn)代優(yōu)化方法之模擬退火課件函數(shù)分別在處有極大點(diǎn)，其中為全局極大點(diǎn)。2、六峰值駝背函數(shù)現(xiàn)代優(yōu)化方法之模擬退火課件函數(shù)有六個(gè)極大點(diǎn)其中為全局極大點(diǎn)，極大值為。

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

測(cè)試參數(shù)為種群規(guī)模100，個(gè)體編碼長(zhǎng)度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ìng)爭(zhēng)選擇機(jī)制，較原算法增加了計(jì)算量，因此對(duì)于相同進(jìn)化代數(shù)，測(cè)試參數(shù)為種群規(guī)模100，個(gè)體編碼長(zhǎng)度20，改進(jìn)算法的運(yùn)行時(shí)間比原算法略長(zhǎng)。但在相同的進(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ù)的例子。改進(jìn)算法的運(yùn)行時(shí)間比原算法略長(zhǎng)。但在相同的進(jìn)化代數(shù)下，兩者的例1、初始群體（群體大小M=100）例1、第1代群體第1代群體第5代群體第5代群體求最小值時(shí)的第100代群體求最小值時(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é)果的精確度超過(guò)了所有公開(kāi)報(bào)道的計(jì)算結(jié)果。例2、Shubert函數(shù)現(xiàn)代優(yōu)化方法之模擬退火課件

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.33654.8578-7.0835-186.73現(xiàn)代優(yōu)化方法之模擬退火課件2、基于改進(jìn)K—均值聚類分析的排擠小生境遺傳算法適應(yīng)值共享算法是遺傳算法解決多峰優(yōu)化問(wèn)題的重要手段之一。標(biāo)準(zhǔn)適應(yīng)值共享算法要求事先知道小生境半徑，并假設(shè)解空間中小生境具有相同的小生境半徑。本文1中討論的排擠小生境算法同樣也要預(yù)先設(shè)定適當(dāng)?shù)姆灏霃?，否則算法不能保證求出所有最優(yōu)解。然而，在實(shí)際多峰優(yōu)化問(wèn)題中峰半徑往往無(wú)法事先估計(jì)。2、基于改進(jìn)K—均值聚類分析的排擠小生境遺傳算法

聚類分析作為一種有效的數(shù)據(jù)分析手段，已經(jīng)在模式識(shí)別、知識(shí)獲取、數(shù)據(jù)挖掘等多個(gè)領(lǐng)域獲得了比較廣泛的應(yīng)用。將聚類分析與排擠小生境遺傳算法相結(jié)合，可以在一定程度上解決峰半徑的設(shè)定問(wèn)題，大大提高算法的實(shí)用性。在聚類分析方法中最常用的是K—均值聚類方法，其基本流程如下：聚類分析作為一種有效的數(shù)據(jù)分析手段，已經(jīng)在模①隨機(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ì)的保守值。這樣，如果第①步中中心的①隨機(jī)產(chǎn)生q個(gè)中心；位置不理想，會(huì)導(dǎo)致最后計(jì)算出來(lái)的中心不能真實(shí)反映群體的小生境數(shù)。為了彌補(bǔ)這個(gè)缺陷，我們將通常的K—均值聚類方法做了改進(jìn)，引進(jìn)了一個(gè)最小聚類距離。在第③步后，如果有兩個(gè)中心之間的距離小于最小聚類距離，則將這兩個(gè)中心合并。使用改進(jìn)后的算法產(chǎn)生出來(lái)的聚類數(shù)目可能小于預(yù)定值，能在很大程度上反映出群體中實(shí)際的小生境數(shù)。位置不理想，會(huì)導(dǎo)致最后計(jì)算出來(lái)的中心不能真實(shí)反映群體的小生境

本文通過(guò)對(duì)小生境遺傳算法的分析，提出了一種新的基于聚類分析的排擠小生境算法，這種算法將聚類分析、排擠技術(shù)有機(jī)地結(jié)合起來(lái)，可以有效地搜索多模函數(shù)空間的多個(gè)極值點(diǎn)，同時(shí)可以通過(guò)調(diào)節(jié)最小聚類距離控制收斂到的小生境的數(shù)目，避免找到無(wú)效的極值點(diǎn)，這種算法無(wú)需事先確定生境的具體數(shù)目和生境半徑的大小，能夠適應(yīng)各種問(wèn)題的優(yōu)化。本文通過(guò)對(duì)小生境遺傳算法的分析，提出了一種新

算法的具體步驟如下：①隨機(jī)生成M個(gè)初始個(gè)體組成初始群體，并計(jì)算適應(yīng)度；②根據(jù)各個(gè)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排序，記憶前N個(gè)個(gè)體(N<M)；③使用改進(jìn)的K-均值算法對(duì)群體進(jìn)行聚類分析，將群體劃分為q個(gè)聚類；④計(jì)算每個(gè)聚類中個(gè)體的數(shù)目，計(jì)算個(gè)體的競(jìng)爭(zhēng)適應(yīng)度；⑤按照個(gè)體適應(yīng)度進(jìn)行選擇、交叉、變異運(yùn)算；算法的具體步驟如下：

⑥將第⑤步得到的M個(gè)子代個(gè)體和第②步所記憶的N個(gè)個(gè)體合并在一起，得到一個(gè)含有M+N個(gè)個(gè)體的新群體。確定新群體中的個(gè)代屬于哪個(gè)聚類，在每一個(gè)聚類中計(jì)算每?jī)蓚€(gè)個(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è)