含精英策略的小生境遺傳退火算法研究及其應(yīng)用

劉愛軍 楊 育 邢青松 陸 惠 張煜東

1.重慶大學(xué)機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，重慶，400030 2.西南交通大學(xué)，成都，610031

3.上海師范大學(xué)，上海，201815 4.哥倫比亞大學(xué)，紐約，美國(guó)，10032

0 引言

生產(chǎn)調(diào)度是一個(gè)交叉性研究領(lǐng)域，涉及數(shù)學(xué)、控制工程、工業(yè)工程等多個(gè)學(xué)科，其主要任務(wù)是在有限的資源約束下，確定工件在相關(guān)設(shè)備上的加工順序，以保證所選定的生產(chǎn)目標(biāo)最優(yōu)。生產(chǎn)調(diào)度的核心內(nèi)容是算法設(shè)計(jì)，主要包括算法編碼、種群初始化、操作邏輯等抽象問(wèn)題的算法實(shí)現(xiàn)過(guò)程。高效穩(wěn)定的算法研究與應(yīng)用，是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)與關(guān)鍵。目前，已發(fā)展了包括遺傳算法、模擬退火算法、免疫算法等多種人工智能算法，但這些算法各自存在性能上的缺陷，同時(shí)，在復(fù)雜優(yōu)化問(wèn)題求解方面，單一算法的優(yōu)化結(jié)果往往不理想，因此，算法的融合成為提高算法性能的一個(gè)重要且有效的途徑。

國(guó)內(nèi)外學(xué)者選擇優(yōu)化領(lǐng)域應(yīng)用最為廣泛的遺傳和退火算法進(jìn)行研究，以期改善算法性能。梁旭等［1］提出了并串混聯(lián)結(jié)構(gòu)的遺傳退火算法，該算法綜合了遺傳算法（GA）全局并行和退火算法（SA）局部串行的搜索特點(diǎn)，增強(qiáng)了系統(tǒng)的全局和局部搜索能力，但該算法沒(méi)有解決在搜索初期由于采用比例選擇算子導(dǎo)致的優(yōu)良個(gè)體急劇增加致使種群失去多樣性的問(wèn)題。張昊等［2］提出了一種自適應(yīng)模擬退火遺傳算法，將模擬退火算法嵌入到自適應(yīng)遺傳算法的循環(huán)體中，解決了遺傳算法局部搜索能力較差、容易陷入局部最優(yōu)解等問(wèn)題，采用自適應(yīng)交叉和變異操作，解決了進(jìn)化過(guò)程中因交叉和變異概率不變所導(dǎo)致的收斂速度慢的問(wèn)題，該算法依然沒(méi)有解決搜索初期有效基因缺失的問(wèn)題。潘全科等［3］采用4－2選擇代替常用的轉(zhuǎn)輪選擇方式，進(jìn)化中，被選擇的2個(gè)個(gè)體經(jīng)過(guò)遺傳操作產(chǎn)生2個(gè)新的個(gè)體，然后從這4個(gè)個(gè)體中選擇生產(chǎn)周期不同的2個(gè)優(yōu)秀個(gè)體進(jìn)入下一代，這樣既有利于保留優(yōu)秀個(gè)體，又有利于維持群體的多樣性，克服了轉(zhuǎn)輪選擇易造成群體中模式單一的缺陷，但這種改進(jìn)的選擇方式在提高算法性能的同時(shí)，額外增加了算法的復(fù)雜度和運(yùn)算資源的消耗。劉敏等［4］針對(duì)遺傳算法變異概率固定不變的缺陷，提出了自適應(yīng)變異概率，針對(duì)選擇算子對(duì)種群多樣性的影響，提出用整體退火選擇的方式選擇雜交母體，避免種群早熟化，這種概率選擇機(jī)制部分地改善了搜索初期有效基因的缺失問(wèn)題，但因優(yōu)化過(guò)程中沒(méi)有充分利用進(jìn)化歷史信息，故要實(shí)現(xiàn)較好的優(yōu)化效果依然需要較長(zhǎng)的搜索過(guò)程。馮毅等［5］提出了基于混合策略的3層并行搜索算法，混合算法在各溫度下依次進(jìn)行GA、SA和小生境搜索。其中，SA的初始解來(lái)自GA的進(jìn)化結(jié)果，經(jīng)Metropolis抽樣過(guò)程得到的解與GA的結(jié)果一起構(gòu)成小生境的處理群體，處理結(jié)果又成為GA進(jìn)一步優(yōu)化的初始種群。這種融入了小生境技術(shù)的改進(jìn)算法雖然算法性能得到改善，但依然沒(méi)有克服交叉和變異概率在整個(gè)搜索過(guò)程中固定不變所導(dǎo)致的求解過(guò)程長(zhǎng)的缺陷，同時(shí)，優(yōu)化過(guò)程也沒(méi)有充分利用歷史信息。

綜上所述，目前具有代表性的遺傳退火算法的研究成果，均強(qiáng)調(diào)通過(guò)融合的思想來(lái)實(shí)現(xiàn)算法的優(yōu)勢(shì)互補(bǔ)，以達(dá)到改善算法性能的目的。但上述諸算法在進(jìn)化過(guò)程中明顯缺乏種群間歷史信息的交流與反饋，以及種群進(jìn)化的參考標(biāo)準(zhǔn)，這樣不僅易造成種群進(jìn)化方向短時(shí)間內(nèi)偏離理論目標(biāo)值的缺陷，而且會(huì)造成在有限的搜索時(shí)間內(nèi)可能錯(cuò)失最優(yōu)解?；谝陨戏治霾⒔Y(jié)合前述研究成果，本文提出了基于3層融合思想的小生境遺傳退火算 法 （niche genetic simulated annealing algorithm，NGSA），采用小生境思想來(lái)實(shí)現(xiàn)遺傳算法的選擇操作，通過(guò)相似個(gè)體種群中選擇概率的不均衡分配，從而有效避免算法落入局部陷阱，改善了搜索初期有效基因的缺失問(wèn)題；采用GA和SA相結(jié)合的串行搜索結(jié)構(gòu)來(lái)提高參數(shù)對(duì)算法性能作用的魯棒性，充分利用GA的全局和SA的局部搜索能力，把SA的處理結(jié)果轉(zhuǎn)變?yōu)镚A進(jìn)一步優(yōu)化的初始種群，使算法的全局尋優(yōu)能力得到明顯提高；采用精英保留策略的進(jìn)化信息共享機(jī)制，在進(jìn)化的每個(gè)階段保留最優(yōu)解個(gè)體，指導(dǎo)算法的進(jìn)化方向；采用自適應(yīng)交叉和變異概率相結(jié)合的方法來(lái)提高算法進(jìn)化的速度，并將之與其他算法進(jìn)行對(duì)比，以考察其有效性，然后把該算法用于車間調(diào)度，以驗(yàn)證其在解決該類調(diào)度問(wèn)題時(shí)的優(yōu)良性能。

1 NGSA算法

小生境遺傳退火算法的執(zhí)行過(guò)程由三部分組成：首先通過(guò)小生境的濃度控制機(jī)制實(shí)現(xiàn)優(yōu)秀個(gè)體的選擇，然后通過(guò)自適應(yīng)遺傳算法的進(jìn)化操作（側(cè)重全局搜索）產(chǎn)生較優(yōu)良的一個(gè)群體，再利用模擬退火操作（側(cè)重局部搜索）來(lái)進(jìn)行基因個(gè)體的優(yōu)化調(diào)整，運(yùn)行過(guò)程反復(fù)迭代，直到滿足終止條件為止。這種算法思路著眼于從全局最優(yōu)解的搜索角度和算法的進(jìn)化速度上來(lái)提高算法的性能，其流程如圖1所示。

小生境遺傳退火算法的生成步驟可描述為：

（1）設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t＝1，隨機(jī)產(chǎn)生含m個(gè)個(gè)體的初始種群pop0（t），同時(shí)計(jì)算各個(gè)個(gè)體的適應(yīng)度f(wàn)i，i＝1，2，…，m。

（2）對(duì)種群pop0（t）中的個(gè)體按其適應(yīng)度大小降序排列，并把適應(yīng)度最高的個(gè)體和目標(biāo)值保存在最優(yōu)解集中。

（3）判斷是否滿足收斂條件，若滿足終止條件，則終止運(yùn)算，輸出計(jì)算結(jié)果；如不滿足終止條件，轉(zhuǎn)（4）。

（4）小生境濃度控制運(yùn)算選擇程序?yàn)椋簩⒌冢?）步得到的m個(gè)個(gè)體，按照下式求出每2個(gè)個(gè)體a和b適應(yīng)度之間的海明距離：

式中，ObjV為個(gè)體目標(biāo)值；k為求解問(wèn)題的決策變量個(gè)數(shù)。

當(dāng)d＜L（L是預(yù)先指定的小生境之間的距離參數(shù)）時(shí)，比較個(gè)體和個(gè)體的適應(yīng)度大小，并對(duì)其中適應(yīng)度較低的個(gè)體處以罰函數(shù)fmin（xi，xj）＝Fpenalty，以極大地降低其適應(yīng)度，即增加其被淘汰的概率。

（5）采用遺傳算法進(jìn)行選擇、交叉和變異等操作，以生成群體pop2（t）。其過(guò)程為：①對(duì)種群pop0（t）進(jìn)行預(yù)選擇操作，選擇操作時(shí)，先進(jìn)行賭盤選擇，再采用精英選擇，其每個(gè)個(gè)體的被選擇概率為

在選擇的過(guò)程中使用保優(yōu)原則，即上一代最優(yōu)的個(gè)體以概率1保存至下一代；②采用自適應(yīng)交叉算子對(duì)種群pop0（t）進(jìn)行交叉操作，從而得到種群pop1（t）；將最優(yōu)解存入知識(shí)庫(kù)，在搜索過(guò)程中首先查詢知識(shí)庫(kù)，以避免最優(yōu)解的丟失，提高種群的進(jìn)化能力；③采用自適應(yīng)均勻變異算子對(duì)種群pop1（t）進(jìn)行變異操作，從而獲得種群pop2（t）。

圖1 小生境遺傳退火算法流程圖

（6）用“黃金分割”率進(jìn)行退火操作選擇，如果滿足退火條件（I＝1），則執(zhí)行步驟（7），否則（I＝0）執(zhí)行步驟（8）。其執(zhí)行過(guò)程為：①定義“黃金分割”點(diǎn)G1、G2和退火溫度控制值DD，G1＝G2－round（0.618 G2），G2＝ maxGen － round（0.618 maxGen），其中 maxGen 為最大循環(huán)代數(shù)；②根據(jù)循環(huán)代數(shù)j判斷是否執(zhí)行退火操作，具體偽代碼如下：

（7）以pop2（t）為初始種群，對(duì)其中各個(gè)個(gè)體進(jìn)行模擬退火運(yùn)算，即在絕對(duì)溫度T，由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為Ei和Ej。若Ej＜Ei，則接受新狀態(tài)j為當(dāng)前狀態(tài)；否則，若概率Pr＝exp［－（Ej－Ei）／（k0T）］大于［0，1］區(qū)間內(nèi)的隨機(jī)數(shù)，則仍舊接受新狀態(tài)j為當(dāng)前狀態(tài)，若不成立則保留狀態(tài)i為當(dāng)前狀態(tài)，其中k0為Boltzmann常數(shù)。對(duì)得到的規(guī)模為m的新群體pop3（t）的個(gè)體按其適應(yīng)度大小降序排列。

（8）將pop1（t）、pop2（t）合并構(gòu)成一個(gè)新群體，并對(duì)其進(jìn)行適應(yīng)度排序，更新pop3（t）中個(gè)體，并轉(zhuǎn)步驟（2）。

從小生境遺傳退火算法的優(yōu)化流程，可歸納出該算法的如下特點(diǎn)：

（1）算法機(jī)制的融合。小生境遺傳退火算法實(shí)現(xiàn)了基于優(yōu)勝劣汰思想的群體遺傳操作優(yōu)化和基于退溫歷程控制實(shí)現(xiàn)最優(yōu)解搜索方法的融合。

（2）算法結(jié)構(gòu)的互補(bǔ)。小生境濃度控制機(jī)制優(yōu)化初始種群的選擇機(jī)制是，把經(jīng)過(guò)GA進(jìn)化的結(jié)果作為SA串行優(yōu)化的初始解，經(jīng)Metropolis抽樣過(guò)程得到的解又成為GA進(jìn)一步進(jìn)化的初始種群。

（3）算法操作的結(jié)合。小生境操作使個(gè)體在整個(gè)約束空間中分散開來(lái)，增強(qiáng)了種群的多樣性。GA的選擇操作有利于優(yōu)化過(guò)程中產(chǎn)生優(yōu)良模態(tài)的冗余信息；交叉操作有利于后代繼承父代的優(yōu)良模式；精英保留策略，可充分利用歷史信息指導(dǎo)搜索行為。

2 算法性能分析

為了驗(yàn)證上述小生境遺傳退火算法的求解效率、有效性和可靠性，采用3個(gè)典型的非線性函數(shù)進(jìn)行對(duì)比驗(yàn)證，其各自的表達(dá)式分別為

［6-7］分別采用f2和f3驗(yàn)證其算法性能的方法，將函數(shù)f1、f2、f3各自獨(dú)立運(yùn)行20次后的結(jié)果與其他算法結(jié)果進(jìn)行對(duì)比，對(duì)比結(jié)果如表1所示。各種實(shí)驗(yàn)方法的參數(shù)如下：①遺傳算法的交叉和變異概率分別為0.85和0.1；②小生境遺傳退火算法尋優(yōu)參數(shù)精度為1×10－4，自適應(yīng)交叉概率為［0.6，0.99］，自適應(yīng)變異概率為［0.01，0.1］，距門限上界距離為3，初始溫度為100K，溫度降低參數(shù)為0.98，退火溫度控制值為0.15；③退火遺傳算法種群規(guī)模為100，進(jìn)化代數(shù)為800，交叉和變異概率分別為0.7和0.1，初始溫度為100K，溫度降低參數(shù)為0.98；④改進(jìn)協(xié)同粒子群分為5個(gè)子群，種群規(guī)模為100，進(jìn)化代數(shù)為800，慣性權(quán)重為0.4，學(xué)習(xí)因子c1＝c2為1.49，擾動(dòng)因子為150；⑤混合量子遺傳算法變量精度為10－5，交叉和變異概率分別為1和0.05。圖2所示為遺傳退火算法f2函數(shù)優(yōu)化結(jié)果。圖3所示為小生境遺傳退火算法f2函數(shù)優(yōu)化結(jié)果。

表1 各種方法的性能比較

圖2 終止代數(shù)為800的適應(yīng)度曲線遺傳退火算法f2函數(shù)優(yōu)化

圖3 小生境遺傳退火算法f2函數(shù)優(yōu)化

由表1和圖2、圖3分析可知：

（1）在優(yōu)化函數(shù)f1時(shí)，相同的種群規(guī)模及進(jìn)化代數(shù)下，小生境遺傳算法比遺傳算法收斂速度更快，達(dá)到更優(yōu)的解，同時(shí)搜索過(guò)程表現(xiàn)出穩(wěn)健性。

（2）在優(yōu)化函數(shù)f2時(shí)，小生境遺傳退火算法收斂速度最快，能搜索到較優(yōu)解，小生境遺傳算法所求解的平均值和偏差最小。另外，小生境遺傳退火算法的尋優(yōu)時(shí)間比小生境遺傳算法約快34倍，節(jié)省了大量的資源消耗，且求解過(guò)程穩(wěn)定，平均值波動(dòng)小。

（3）在優(yōu)化函數(shù)f3時(shí)，與混合量子遺傳算法相比，小生境遺傳退火算法表現(xiàn)出更快的收斂速度，更強(qiáng)的搜索能力。

數(shù)值實(shí)驗(yàn)證明，NGSA混合算法在搜索能力和優(yōu)化效率等方面具有明顯的優(yōu)越性。

3 算法在車間調(diào)度中的應(yīng)用

3.1 車間調(diào)度問(wèn)題描述

n個(gè)工件J1，J2，…，Jn在m 臺(tái)機(jī)器M1，M2，…，Mm上加工，工件之間的加工順序無(wú)約束，每個(gè)工件的Ni（i＝1，2，…，n）個(gè)工序有先后約束，Ji＝Ji1，Ji2，…，Jil為工件Ji的工序序列，每道工序在固定的機(jī)器上加工。調(diào)度的目標(biāo)是最小化最大完工時(shí)間，其數(shù)學(xué)描述為

約束條件：

（1）工序約束。前道工序完成以后才能開始后道工序的加工。其數(shù)學(xué)表述為

（2）機(jī)器約束。同一臺(tái)機(jī)器k上，一個(gè)加工任務(wù)完成后才能開始另一個(gè)加工任務(wù)。其數(shù)學(xué)表述為

（3）完成時(shí)間約束。其數(shù)學(xué)表述為

式中，Ci（j－1）l為工件Ji的完工時(shí)間；Pijk為工件i的第j道工序在機(jī)器k上的加工時(shí)間；Cijk為工件i的第j道工序在機(jī)器k上的完成時(shí)間；STijk為工件i的第j道工序在機(jī)器k上的開始加工時(shí)間。

工件i的第一道工序的完成時(shí)間Ci1k須滿足約束：

（4）每個(gè)工件的每道工序在任何一臺(tái)機(jī)器上加工時(shí)不允許中斷。

（5）所有工件在零時(shí)刻都可以被加工。

3.2 算法實(shí)現(xiàn)

3.2.1 算法編碼

在初始化過(guò)程中，本文采用基于工序的表達(dá)法進(jìn)行編碼，如針對(duì)表2中的3×3問(wèn)題，假設(shè)給定的染色體為［321123123］，其中1代表工件J1，2代表工件J2，3代表工件J3，因?yàn)槊總€(gè)工件有3道工序，所以每個(gè)工件在一個(gè)染色體中剛好出現(xiàn)3次，染色體與工件的對(duì)應(yīng)關(guān)系如圖4所示。

表2 3個(gè)工件、3臺(tái)機(jī)器的車間調(diào)度問(wèn)題

圖4 染色體、工件和機(jī)器的對(duì)應(yīng)關(guān)系

3.2.2 基于共享機(jī)制的小生境技術(shù)

基于共享機(jī)制的小生境實(shí)現(xiàn)方法是由Goldberg于1987年提出的。主要通過(guò)共享函數(shù)調(diào)整個(gè)體適應(yīng)度來(lái)維持種群的多樣性。其過(guò)程為：先根據(jù)個(gè)體之間的海明距離定義個(gè)體的共享函數(shù)，然后通過(guò)共享函數(shù)調(diào)整種群中每個(gè)個(gè)體的適應(yīng)度，并把調(diào)整后的適應(yīng)度作為遺傳算子的依據(jù)。這種小生境技術(shù)限制了群體內(nèi)某一特殊物種的無(wú)限制增長(zhǎng)，對(duì)保證解的多樣性無(wú)疑是有效的，提高了獲得最優(yōu)解的概率［8］。涉及的主要定義如下：

定義1 所謂個(gè)體之間的距離是指2個(gè)個(gè)體基因或基因表現(xiàn)形式之間的差異，記為d（i，j）。本文采用海明距離公式來(lái)描述種群中個(gè)體ci與cj之間的差異。其數(shù)學(xué)表述為

式中，Llength為個(gè)體染色體長(zhǎng)度。

式（8）中的d越大，則表示車間調(diào)度問(wèn)題的排序差異越大。

定義2 共享函數(shù)用來(lái)衡量2個(gè)個(gè)體之間的密切程度，本文采用三角函數(shù)作為共享函數(shù)。其數(shù)學(xué)表述為

式中，σshare為小生境半徑。

定義3 個(gè)體的共享度即指?jìng)€(gè)體的小生境數(shù)，定義種群中個(gè)體的小生境數(shù)為該個(gè)體與種群中其他個(gè)體的共享函數(shù)值的和［9］。個(gè)體在種群中的共享程度用共享度進(jìn)行衡量，記為Si，從而每一個(gè)體在種群中的共享度可描述為

式中，n為種群規(guī)模。

式（10）中的Si越大，則表示圍繞該個(gè)體的其他個(gè)體數(shù)量越多。當(dāng)個(gè)體的共享度值確定以后，種群個(gè)體的適應(yīng)度函數(shù)即調(diào)整為

式中，fi為個(gè)體i調(diào)整前的適應(yīng)度；f′i為個(gè)體i調(diào)整后的適應(yīng)度。

式（11）中的共享度Si越大，經(jīng)調(diào)整后的適應(yīng)度f(wàn)′i就越小，從而達(dá)到抑制適應(yīng)度高的個(gè)體無(wú)限制增長(zhǎng)的目的［10－11］。共享機(jī)制小生境偽代碼如下：

3.2.3 自適應(yīng)雙點(diǎn)交叉操作

交叉操作是遺傳算法中增加種群多樣性，防止算法早熟、停滯的操作。為充分利用歷史信息，本文采用雙點(diǎn)交叉，如圖5所示。

圖5 雙點(diǎn)交叉

在進(jìn)化的過(guò)程中，為達(dá)到較快的搜索速度，當(dāng)前代種群中個(gè)體的適應(yīng)度低于平均適應(yīng)度值時(shí)，就需要提高交叉率；當(dāng)適應(yīng)度值高于平均適應(yīng)度值時(shí)，則需要降低交叉率，這樣就需要交叉率隨著適應(yīng)度值自動(dòng)地調(diào)整。為此，本文提出交叉概率動(dòng)態(tài)調(diào)整策略，交叉率的自適應(yīng)調(diào)整公式為

式中，Pc1、Pc2為交叉概率，且Pc1＞Pc2。

3.2.4 自適應(yīng)隨機(jī)變異操作

變異是按一定的概率改變個(gè)體基因鏈，變異操作的目的是維持群體的多樣性，改善局部的搜索能力，同時(shí)防止出現(xiàn)早熟現(xiàn)象。為增加種群多樣性，本文采用隨機(jī)互換變異，如圖6所示。

圖6 隨機(jī)互換變異

隨機(jī)選擇染色體中的兩基因位，交換其值。同樣采用自適應(yīng)變異概率來(lái)提高收斂速度，自適應(yīng)調(diào)整公式為

式中，Pm1、Pm2為變異概率，且Pm1＞Pm2。

3.2.5 精英保留策略

在傳統(tǒng)遺傳算法中，由于遺傳算子操作具有隨機(jī)性，可能造成最優(yōu)個(gè)體的丟失，進(jìn)而導(dǎo)致收斂周期較長(zhǎng)。同樣，小生境共享機(jī)制的引入，雖然增大了個(gè)體的搜索空間和收斂到最優(yōu)解的概率，但卻導(dǎo)致進(jìn)化過(guò)程漫長(zhǎng)，收斂進(jìn)度緩慢。為解決上述2個(gè)問(wèn)題，本文引入精英保留策略，其偽代碼如下：

3.3 仿真實(shí)驗(yàn)

在Pentium 4計(jì)算機(jī)上（CPU主頻為2.71GHz、內(nèi)存為1.75GB、操作系統(tǒng)為 Windows XP），利用MATLAB 2009仿真工具編程實(shí)現(xiàn)上述算法。設(shè)置的算法基本運(yùn)行參數(shù)為：群體規(guī)模500，最大迭代數(shù)100，交叉率0.6，變異率0.06，衰減參數(shù)0.95，迭代初始溫度500K。經(jīng)過(guò)20次測(cè)試，得到表3所示的結(jié)果。

表3 20次實(shí)驗(yàn)各種算法最優(yōu)結(jié)果比較

表3中的min V、ave V和ave t分別為最小值、平均值和平均時(shí)間；Pmin、Pave分別為最小值相對(duì)改善率、平均值相對(duì)改善率。其計(jì)算公式為

從表2可以得出：

（1）在FT類問(wèn)題求解方面，3種算法都能絕對(duì)收斂到FT06的最小值，其中，本文所提小生境遺傳退火算法平均收斂時(shí)間最長(zhǎng)，可見，在小規(guī)模問(wèn)題上，該方法沒(méi)有表現(xiàn)出本身的優(yōu)勢(shì)；對(duì)于FT10標(biāo)準(zhǔn)問(wèn)題，小生境遺傳退火算法和遺傳退火算法都可以收斂到最小值，小生境遺傳退火算法平均值的相對(duì)改善率為2.66%；對(duì)于FT20標(biāo)準(zhǔn)問(wèn)題，只有小生境遺傳退火算法可以收斂到最小值，并且最小值相對(duì)改善率為0.43%。

（2）在LA 類問(wèn)題求解方面，對(duì)于LA01、LA06、LA11標(biāo)準(zhǔn)問(wèn)題，3種算法都可以收斂到最小值，同時(shí)，小生境遺傳退火算法與其他2種算法相比，其平均值相對(duì)改善率分別為0.60%、0.43%和1.13%；對(duì)于LA16、LA26標(biāo)準(zhǔn)問(wèn)題，在可接受的收斂時(shí)間范圍內(nèi)，小生境遺傳退火算法與其他2種算法相比，其最小值和平均值都有所改善。

4 結(jié)論

（1）本文提出的小生境遺傳退火算法，通過(guò)相似個(gè)體群中選擇概率的不均衡分配增加了種群的多樣性，有效避免了算法掉入局部陷阱，提高了算法的全局收斂性能；通過(guò)自適應(yīng)交叉和變異操作提高了算法的進(jìn)化速度；通過(guò)精英保留策略，利用優(yōu)良的染色體模板，使個(gè)體在迭代過(guò)程中有效地繼承了父代的優(yōu)良特征，避免了最優(yōu)解的丟失，確保了搜索過(guò)程加速向最優(yōu)的方向逼近。

（2）本文提出的小生境遺傳退火算法，注重算法機(jī)制的融合，實(shí)現(xiàn)了基于優(yōu)勝劣汰思想的群體遺傳操作優(yōu)化（側(cè)重全局搜索），以及基于退溫歷程控制來(lái)實(shí)現(xiàn)最優(yōu)解搜索方法（側(cè)重局部搜索）的融合。注重算法搜索結(jié)構(gòu)的互補(bǔ)，實(shí)現(xiàn)了遺傳算法的并行搜索與模擬退火算法的串行搜索的互補(bǔ)。重視算法操作的融匯和結(jié)合，實(shí)現(xiàn)了小生境操作增強(qiáng)種群多樣性的目的，亦即：選擇操作能從多樣性群體中選擇優(yōu)良個(gè)體；交叉操作能讓后代繼承父代的優(yōu)良模式；變異操作能以優(yōu)良個(gè)體為模板拓寬最優(yōu)解的搜索范圍；精英保留操作能充分利用小生境操作、交叉操作和變異操作等進(jìn)化過(guò)程歷史信息指導(dǎo)搜索行為。

參考文獻(xiàn)：

［1］梁旭，黃明，常征.求解車間調(diào)度問(wèn)題的一種新遺傳退火混合策略［J］.計(jì)算機(jī)集成制造系統(tǒng)，2005，11（6）：851－854.

［2］張昊，陶然，李志勇，等.基于自適應(yīng)模擬退火遺傳算法的特征選擇方法［J］.兵工學(xué)報(bào)，2009，30（1）：81－85.

［3］潘全科，王文宏，朱劍英.一類解決車間調(diào)度問(wèn)題的遺傳退火算法［J］.機(jī)械科學(xué)與技術(shù)，2006，25（3）：317－321.

［4］劉敏，嚴(yán)雋薇.基于自適應(yīng)退火遺傳算法的車間日作業(yè)計(jì)劃調(diào)度方法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（7）：1164－1172.

［5］馮毅，李利，高艷明，等.一種基于小生境的混合遺傳退火算法［J］.機(jī)械科學(xué)與技術(shù)，2004，23（12）：1494－1498.

［6］虞斌能，焦斌，顧幸生.改進(jìn)協(xié)同粒子群優(yōu)化算法及其在Flow Shop調(diào)度中的應(yīng)用［J］.華東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，35（3）：468－474.

［7］王凌，吳昊，唐芳，等.混合量子遺傳算法及其性能分析［J］.控制與決策，2005，20（2）：156－158.

［8］Jia Chunqiang，Yu Ling，Shu Jun，et al.Optimal Design of Hydraulic Manifold Blocks Based on Niching Genetic Simulated Annealing Algorithm［J］.High Technology Letters，2007，13（4）：363－368.

［9］Sadegheig A.Scheduling Problem Using Genetic Algorithm，Simulated Annealing and the Effects of Parameter Values on GA Performance［J］.Applied Mathematical Modelling，2006，30（2）：147－154.

［10］Andresen M，Brasel H，Morig，et al.Simulated Annealing and Genetic Algorithms for Minimizing Mean Flow Time in an Open Shop［J］.Mathematical and Computer Modelling，2008，48（7／8）：1279－1293.

［11］Pere E，Herrera F，Hernandez C.Finding Multiple Solutions in Job Shop Scheduling by Niching Genetic Algorithms［J］.Journal of Intelligent Manufacturing，2003，14：323－339.