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

1、第三部分第三部分 現(xiàn)代優(yōu)化方法選講現(xiàn)代優(yōu)化方法選講 現(xiàn)代優(yōu)化方法包括禁忌搜索、模擬退火、智能計(jì)算等。其中模擬退火、神經(jīng)網(wǎng)絡(luò)和遺傳算法并稱(chēng)為現(xiàn)代優(yōu)化算法中的三大杰出代表。模糊邏輯進(jìn)化規(guī)劃進(jìn)化策略遺傳算法進(jìn)化計(jì)算神經(jīng)網(wǎng)絡(luò)智能計(jì)算)()()(EPESGA一、模擬退火算法一、模擬退火算法 在管理科學(xué)、計(jì)算機(jī)科學(xué)、分子物理學(xué)、生物學(xué)、超大規(guī)模集成電路設(shè)計(jì)、代碼設(shè)計(jì)、圖象處理和電子工程等領(lǐng)域中，存在著大量的組合優(yōu)化問(wèn)題。例如，貨郎擔(dān)問(wèn)題、最大截問(wèn)題、01背包問(wèn)題、圖著色問(wèn)題、設(shè)備布局問(wèn)題以及布線問(wèn)題等，這些問(wèn)題至今仍未找到多項(xiàng)式時(shí)間算法。這 些 問(wèn) 題 已 被 證 明 是 N P 完 全 問(wèn) 題 。根據(jù)N

2、P完全性理論，除非P=NP，否則所有的NP難問(wèn)題都不存在多項(xiàng)式時(shí)間算法。但是，這并不意味著問(wèn)題的終結(jié)。相反，由于這類(lèi)問(wèn)題廣泛應(yīng)用性，反而刺激人們以更大的熱情對(duì)NP完全問(wèn)題進(jìn)行研究。 為解決這類(lèi)問(wèn)題，人們提出了許多近似算法，但這些算法或過(guò)于注意個(gè)別問(wèn)題的特征而缺乏通用性，或因所得解強(qiáng)烈地依賴(lài)初始解的選擇而缺乏實(shí)用性。模擬退火算法是近年提出的一種適合解大規(guī)模組合優(yōu)化問(wèn)題，特別是解NP完全問(wèn)題的通用有效的近似算法，與以往近似算法相比，具有描述簡(jiǎn)單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受初始條件限制的優(yōu)點(diǎn)，而且特別適合并行計(jì)算，因此具有很大的使用價(jià)值。同時(shí)由于其討論涉及隨機(jī)分析、馬氏鏈理論、漸進(jìn)收斂性

3、等學(xué)科，所以其研究還具有重要的理論意義。 1. 模擬退火算法的物理背景模擬退火算法的物理背景 固體退火過(guò)程的物理圖象和統(tǒng)計(jì)性質(zhì)是模擬退火算法的物理背景。在熱力學(xué)與統(tǒng)計(jì)物理學(xué)的研究領(lǐng)域中，固體退火是其重要的研究對(duì)象。固體退火是指先將固體加熱至熔化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過(guò)程。 在高溫狀態(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í)，它們自己就

4、同時(shí)地排列 而形成一個(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í)具有較高的能量。 模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過(guò)程的一種通用隨機(jī)搜索技術(shù)，可用馬氏鏈的遍歷理論給它以數(shù)學(xué)上的描述。在搜索最優(yōu)解的過(guò)程中，模擬退火除了可以接受優(yōu)化解外，還用一個(gè)隨機(jī)準(zhǔn)則(Metropolis準(zhǔn)則)有限地接受惡化解，并使接受惡化解的概率逐漸趨于零，這使得算法有可能從局部最優(yōu)解中跳出，盡可能找到全局最優(yōu)解，并保證了算法的

5、收斂性。 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)定解。 通過(guò)以下示例，我們可以將組合優(yōu)化問(wèn)題與固體退火進(jìn)行類(lèi)比： 組合優(yōu)化問(wèn)題 固體退火 解 狀態(tài) 最優(yōu)解 能量最低狀態(tài) 費(fèi)用函數(shù) 能量2. 模擬退火算法的基本思想與算法模擬退火算法的基本思想與算法 用傳統(tǒng)優(yōu)化算法優(yōu)化多峰值函數(shù)時(shí)，往往由于過(guò)分追求“下降”而極易陷于局部

6、最優(yōu)解。為了克服這個(gè)缺陷，在搜索最優(yōu)解的過(guò)程中，模擬退火方法除了接受優(yōu)化解外，還根據(jù)一個(gè)隨機(jī)接受準(zhǔn)則有限地接受惡化解，并使接受惡化解的概率逐漸趨于零。這既可使得算法以較大概率跳出局部最優(yōu)解，又保證了算法的收斂性。模擬退火算法的求解過(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，若 ，接受新解，否則拒XXk)()(kkXEXXEE0EkkXXX)exp(kTEEPrEP )(絕新解； (4) 重復(fù)第(2),(3)步若干次，使解

7、接近當(dāng)前溫度下的最優(yōu)解，這相當(dāng)于用足夠慢的速度降溫，以保證在每個(gè)溫度時(shí)系統(tǒng)都能處于當(dāng)前溫度下的能量最低狀態(tài)；(5) 按一定的方式降低溫度，例如 ，其中 ；(6) 若滿(mǎn)足收斂條件，退火過(guò)程結(jié)束，否則 ，轉(zhuǎn)(2)。kkTT) 1 , 0(1 kk 通常 ，收斂條件為 。 理論已證明：只要初始溫度足夠高，退火過(guò)程足夠慢，模擬退火算法以概率1收斂到全局最優(yōu)解。 95. 085. 0kT 模擬退火算法在許多領(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)等。 例例 用模

8、擬退火算法求的極小值。xxxxxf3223 . 0)(2343. 模擬退火算法的應(yīng)用模擬退火算法的應(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)度表包括：初始溫度、降溫策略、馬氏鏈長(zhǎng)度以及停止準(zhǔn)則四個(gè)方面。 此外，還包括隨機(jī)數(shù)發(fā)生器。 問(wèn)題的描述主要包括解空間和目標(biāo)函數(shù)兩部分。解空間為所有可行解的集合，它限定了初始解選取和新解產(chǎn)生的范圍。對(duì)于無(wú)約束優(yōu)化問(wèn)題，任一可能解即為可行解；對(duì)

9、于有約束優(yōu)化問(wèn)題，解集中還可以包含一些不可行解，同時(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)化問(wèn)題往往還伴隨有新解可行 性 的 判 斷 ； 第 四 ， 接 受 或 舍 棄 新 解，若接受，用新解代替當(dāng)前解，同時(shí)修正目標(biāo)函數(shù)值，否則當(dāng)前解與目標(biāo)函數(shù)值保持不變。 下面僅對(duì)幾個(gè)典型的組合優(yōu)化問(wèn)題給出算法描述，以揭示其建立

10、數(shù)學(xué)模型和新解產(chǎn)生裝置的基本方法。 (1) 旅行商問(wèn)題（旅行商問(wèn)題（tsp） 設(shè)有n個(gè)城市和距離矩陣 ，其中 表示城市i 到城市j的距離，i,j=1,，n，則問(wèn)題是尋找遍訪每個(gè)城市恰好一次的一條回路，且其路徑長(zhǎng)度為最短。 求解的模擬退火算法描述如下： 解空間 解空間S可表為1,2，n的所有循環(huán)排列的集合，即 ijdD ijd的循環(huán)排列為nSnn, 2 , 1,11其中每一循環(huán)排列表示遍訪n個(gè)城市的一條回路， 表示在第i個(gè)次序訪問(wèn)城市j，并約定 。初始解可選為（1,2，n）。 目標(biāo)函數(shù) 此時(shí)的目標(biāo)函數(shù)為訪問(wèn)所有城市的路徑長(zhǎng)度之和，即其中 。jj11nniniidf111,11n 新解的產(chǎn)生（2變

11、換法） 任選訪問(wèn)的序號(hào)u和v，逆轉(zhuǎn)u和v及其之間的訪問(wèn)順序，此時(shí)新路徑為（設(shè)uv） 代價(jià)函數(shù)差 新解的目標(biāo)函數(shù)差可由公式計(jì)算。特別地，當(dāng)問(wèn)題為對(duì)稱(chēng)的，即距離矩陣 為對(duì)稱(chēng)矩陣時(shí)，上式可簡(jiǎn)化為 nvuuvvu11111vuiiivvuuvuiiivuvuddddddf11111111 ijdD int d1111=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

12、,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;)()(11111vvuuvuvuddddf非數(shù)值并行算法模擬退火算法康立山科學(xué)出版社排擠小生境遺傳算法改進(jìn)研究排擠小生境遺傳算法改進(jìn)研究 1、排擠小生境遺傳算法及其改

13、進(jìn)、排擠小生境遺傳算法及其改進(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)處理后其適應(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)行降序排序，

14、記憶前N個(gè)個(gè)體（NM）；進(jìn)行比例選擇、單點(diǎn)交叉、基本位變異運(yùn)算；), 2 , 1(MiFi小生境淘汰運(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ǎn)足終止條件，則將第步排序中的前M個(gè)個(gè)體作為新的下一代群體，然 iXjXijdLdijiXjX后轉(zhuǎn)到第步；若滿(mǎn)足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束。 本文對(duì)上述算法做了兩處改

15、進(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)的選擇壓，可有效地提高種群的多樣性。(+)選擇允許個(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)后算法維持種群多樣性的能力

16、以及收斂速度的提高程度，我們采用下列函數(shù)表示種群的多樣性程度 其中n為種群規(guī)模， 為個(gè)體的二進(jìn)制編碼長(zhǎng)度， 為種群中第i個(gè)個(gè)體的第j個(gè)二進(jìn)制的值。顯然，越?。ù螅?，種群的多樣性就越高（低）。 測(cè)試函數(shù)為1、五峰函數(shù) ljniijniijaanlPd111, )1 (max1)(lija)(Pd1041 . 05exp5sin)(24xxxxf函數(shù)分別在 處有極大點(diǎn)，其中 為全局極大點(diǎn)。2、六峰值駝背函數(shù)9 . 0, 7 . 0, 5 . 0, 3 . 0, 1 . 0 x1 . 0 x22, 334431 . 24),(22242yxyyxyxxxyxf函數(shù)有六個(gè)極大點(diǎn)其中為 全局極大點(diǎn)，極大

17、值為 。 ,5687. 0,6071. 1,1623. 0,2302. 1,1623. 0,2302. 1 7127. 0,8984. 0,7127. 0,8984. 0,5687. 0,6071. 1 7127. 0,8984. 0,7127. 0,8984. 0031628. 1 測(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ì)搜尋到更多的峰。 由于新算法采

18、用（2+2）競(jìng)爭(zhēng)選擇機(jī)制，較原算法增加了計(jì)算量，因此對(duì)于相同進(jìn)化代數(shù)，改進(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ù)的例子。 例例1、初始群體（群體大小M=100） 2441 . 05exp5sin)(xxxf第1代群體 第5代群體 求最小值時(shí)的第100代群體 例例2、Shubert函數(shù)此函數(shù)共有760個(gè)局部極小點(diǎn)，其中18個(gè)為

19、全局最小點(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é)果。 10,101cos1cos),(5151yxiyiiixiiyxfii 4.8578 -7.0835 -186.7307 10.3365 4.8578 -0.8003 -186.7307 10.3365 4.8578 5.4829 -186.7307 10.3365 5.4828 -1.4251 -186.7309 10.3365 5.4828 -7.7083 -186.7309 10.

20、3365 5.4828 4.8581 -186.7309 10.3365 -1.4252 -7.0835 -186.7309 10.3365 -1.4252 -0.8003 -186.7309 10.3365 -1.4252 5.4829 -186.7309 10.3365 -7.7083 -7.0835 -186.7309 10.3365 -7.7083 -0.8003 -186.7309 10.3365 -0.8003 -1.4251 -186.7309 10.3365 -0.8003 -7.7083 -186.7309 10.3365 -7.0835 -1.4251 -186.7309

21、10.3365 -7.0835 -7.7083 -186.7309 10.3365 -0.8003 4.8581 -186.7309 10.3365 -7.0835 4.8581 -186.7309 10.3365 -7.7083 5.4829 -186.7309 10.33652、基于改進(jìn)、基于改進(jìn)K均值聚類(lèi)分析的排擠小生境遺均值聚類(lèi)分析的排擠小生境遺傳算法傳算法 適應(yīng)值共享算法是遺傳算法解決多峰優(yōu)化問(wèn)題的重要手段之一。標(biāo)準(zhǔn)適應(yīng)值共享算法要求事先知道小生境半徑，并假設(shè)解空間中小生境具有相同的小生境半徑。本文 1 中討論的排擠小生境算法同樣也要預(yù)先設(shè)定適當(dāng)?shù)姆灏霃?，否則算法不能保證求出所有最優(yōu)

22、解。然而，在實(shí)際多峰優(yōu)化問(wèn)題中峰半徑往往無(wú)法事先估計(jì)。 聚類(lèi)分析作為一種有效的數(shù)據(jù)分析手段，已經(jīng)在模式識(shí)別、知識(shí)獲取、數(shù)據(jù)挖掘等多個(gè)領(lǐng)域獲得了比較廣泛的應(yīng)用。將聚類(lèi)分析與排擠小生境遺傳算法相結(jié)合，可以在一定程度上解決峰半徑的設(shè)定問(wèn)題，大大提高算法的實(shí)用性。 在聚類(lèi)分析方法中最常用的是K均值聚類(lèi)方法，其基本流程如下： 隨機(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è)聚類(lèi)中心，在預(yù)先難以確定小生境數(shù)目時(shí)，往往只能取一個(gè)估計(jì)的保守

23、值。這樣，如果第步中中心的位置不理想，會(huì)導(dǎo)致最后計(jì)算出來(lái)的中心不能真實(shí)反映群體的小生境數(shù)。為了彌補(bǔ)這個(gè)缺陷，我們將通常的K均值聚類(lèi)方法做了改進(jìn)，引進(jìn)了一個(gè)最小聚類(lèi)距離 。在第步后，如果有兩個(gè)中心之間的距離小于最小聚類(lèi)距離 ，則將這兩個(gè)中心合并。使用改進(jìn)后的算法產(chǎn)生出來(lái)的聚類(lèi)數(shù)目可能小于預(yù)定值，能在很大程度上反映出群體中實(shí)際的小生境數(shù)。mindmind 本文通過(guò)對(duì)小生境遺傳算法的分析，提出了一種新的基于聚類(lèi)分析的排擠小生境算法，這種算法將聚類(lèi)分析、排擠技術(shù)有機(jī)地結(jié)合起來(lái)，可以有效地搜索多模函數(shù)空間的多個(gè)極值點(diǎn)，同時(shí)可以通過(guò)調(diào)節(jié)最小聚類(lèi)距離控制收斂到的小生境的數(shù)目，避免找到無(wú)效的極值點(diǎn)，這種算法無(wú)

24、需事先確定生境的具體數(shù)目和生境半徑的大小，能夠適應(yīng)各種問(wèn)題的優(yōu)化。 算法的具體步驟如下：算法的具體步驟如下：隨機(jī)生成M個(gè)初始個(gè)體組成初始群體，并計(jì)算適應(yīng)度；根據(jù)各個(gè)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排序，記憶前N個(gè)個(gè)體(NM)；使用改進(jìn)的K-均值算法對(duì)群體進(jìn)行聚類(lèi)分析，將群體劃分為q個(gè)聚類(lèi)；計(jì)算每個(gè)聚類(lèi)中個(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è)聚類(lèi)，在每一個(gè)聚類(lèi)中計(jì)算每?jī)蓚€(gè)個(gè)體和的適應(yīng)度大小，并對(duì)其中適應(yīng)度較低的個(gè)體處以罰函數(shù)；根據(jù)這M+N個(gè)個(gè)體的新適

25、應(yīng)度對(duì)各個(gè)個(gè)體進(jìn)行降序排序，記憶前N個(gè)個(gè)體； 終止條件判斷：若不滿(mǎn)足終止條件，則將第步排序中的前M個(gè)個(gè)體作為新的下一代群體，然后轉(zhuǎn)到第步；若滿(mǎn)足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束。 3、數(shù)值實(shí)驗(yàn)、數(shù)值實(shí)驗(yàn) 為了測(cè)試基于改進(jìn)K均值聚類(lèi)分析的排擠小生境遺傳算法的性能，我們選擇了下列幾個(gè)難度較大的標(biāo)準(zhǔn)測(cè)試函數(shù)。例例3、不均勻分布等高峰函數(shù)該函數(shù)有5個(gè)不均勻分布的峰，分別為，峰高均為1.000。 1 , 005. 05sin)(75. 06xxxf934. 0,681. 0,451. 0,247. 0,080. 0 x例例4、不均勻分布不等高峰函數(shù) 該函數(shù)有5個(gè)不均勻分布的峰，分別為峰高分別為 。93

26、4. 0,681. 0,451. 0,247. 0,080. 0 x250. 0,503. 0,770. 0,948. 0,000. 1例例6、二元不均勻分布等高峰函數(shù)該函數(shù)有4個(gè)不均勻分布的峰，分別在峰高均為2500。 由圖形可以看出，該函數(shù)的峰比較平坦，性能不佳的算法很難精確搜索到全部四個(gè)峰。 1 , 005. 05sin854. 008. 02ln2exp)(75. 062xxxxf 131. 3,805. 2,283. 3,779. 3,848. 1,584. 3,000. 2,000. 3 下面給出用基于改進(jìn)K均值聚類(lèi)分析的排擠小生境遺傳算法連續(xù)三次的計(jì)算結(jié)果。x = 3.0000

27、-3.7687 -2.8037 3.5845y = 2.2509 -3.2798 3.1230 -1.8486z = 2498.8 2500.0 2500.0 2500.0 x =-3.7500 3.5625 3.0030 -2.8076y =-3.2549 -1.8427 1.9980 3.1318z = 2499.9 2500.0 2500.0 2500.0 x =-2.8125 3.0034 -3.7778 3.5845y =3.1289 1.9981 -3.2827 -1.8457z = 2500.0 2500.0 2500.0 2500.0例例6、復(fù)雜欺騙性問(wèn)題其中， ， 定義為：

28、顯然， 是一個(gè)簡(jiǎn)單欺騙性問(wèn)題，它有兩個(gè)高度為1的峰和一個(gè)高度為0.640576的峰。復(fù)雜欺騙性問(wèn)題由5個(gè)這樣的簡(jiǎn)單欺騙性問(wèn)題相加而成， 405062910),(ijjixuxxxf29, 1 , 0,1, 0kxk)(su 3640576. 04 , 2360384. 05 , 116 , 01)(sssssu)(su它的峰的數(shù)量約為 ，其中全局峰僅有32個(gè)，分別在 , ， 。之所以稱(chēng)之為復(fù)雜欺騙性問(wèn)題，不僅因?yàn)槠渚薮蟮木植糠鍞?shù)量，而且因?yàn)楸姸嗟木植糠灏鼑址?，這就使得即使較好的算法也極難尋找到所有全局峰。 大量計(jì)算顯示，本文提出的算法在優(yōu)化復(fù)雜欺騙性問(wèn)題時(shí)效果欠佳，多數(shù)情況下只能找到8個(gè)全局最優(yōu)解，只有偶爾能找到16個(gè)全局最優(yōu)解。