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

1.重慶大學機械傳動國家重點實驗室，重慶，400030 2.西南交通大學，成都，610031

3.上海師范大學，上海，201815 4.哥倫比亞大學，紐約，美國，10032

0 引言

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

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

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

1 NGSA算法

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

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

（1）設置進化代數(shù)計數(shù)器t＝1，隨機產(chǎn)生含m個個體的初始種群pop0（t），同時計算各個個體的適應度fi，i＝1，2，…，m。

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

（3）判斷是否滿足收斂條件，若滿足終止條件，則終止運算，輸出計算結果；如不滿足終止條件，轉（4）。

（4）小生境濃度控制運算選擇程序為：將第（1）步得到的m個個體，按照下式求出每2個個體a和b適應度之間的海明距離：

式中，ObjV為個體目標值；k為求解問題的決策變量個數(shù)。

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

（5）采用遺傳算法進行選擇、交叉和變異等操作，以生成群體pop2（t）。其過程為：①對種群pop0（t）進行預選擇操作，選擇操作時，先進行賭盤選擇，再采用精英選擇，其每個個體的被選擇概率為

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

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

（6）用“黃金分割”率進行退火操作選擇，如果滿足退火條件（I＝1），則執(zhí)行步驟（7），否則（I＝0）執(zhí)行步驟（8）。其執(zhí)行過程為：①定義“黃金分割”點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）為初始種群，對其中各個個體進行模擬退火運算，即在絕對溫度T，由當前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為Ei和Ej。若Ej＜Ei，則接受新狀態(tài)j為當前狀態(tài)；否則，若概率Pr＝exp［－（Ej－Ei）／（k0T）］大于［0，1］區(qū)間內的隨機數(shù)，則仍舊接受新狀態(tài)j為當前狀態(tài)，若不成立則保留狀態(tài)i為當前狀態(tài)，其中k0為Boltzmann常數(shù)。對得到的規(guī)模為m的新群體pop3（t）的個體按其適應度大小降序排列。

（8）將pop1（t）、pop2（t）合并構成一個新群體，并對其進行適應度排序，更新pop3（t）中個體，并轉步驟（2）。

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

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

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

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

2 算法性能分析

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

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

表1 各種方法的性能比較

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

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

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

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

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

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

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

3 算法在車間調度中的應用

3.1 車間調度問題描述

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

約束條件：

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

（2）機器約束。同一臺機器k上，一個加工任務完成后才能開始另一個加工任務。其數(shù)學表述為

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

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

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

（4）每個工件的每道工序在任何一臺機器上加工時不允許中斷。

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

3.2 算法實現(xiàn)

3.2.1 算法編碼

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

表2 3個工件、3臺機器的車間調度問題

圖4 染色體、工件和機器的對應關系

3.2.2 基于共享機制的小生境技術

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

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

式中，Llength為個體染色體長度。

式（8）中的d越大，則表示車間調度問題的排序差異越大。

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

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

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

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

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

式中，fi為個體i調整前的適應度；f′i為個體i調整后的適應度。

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

3.2.3 自適應雙點交叉操作

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

圖5 雙點交叉

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

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

3.2.4 自適應隨機變異操作

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

圖6 隨機互換變異

隨機選擇染色體中的兩基因位，交換其值。同樣采用自適應變異概率來提高收斂速度，自適應調整公式為

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

3.2.5 精英保留策略

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

3.3 仿真實驗

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

表3 20次實驗各種算法最優(yōu)結果比較

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

從表2可以得出：

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

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

4 結論

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

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

參考文獻：

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

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

［3］潘全科，王文宏，朱劍英.一類解決車間調度問題的遺傳退火算法［J］.機械科學與技術，2006，25（3）：317－321.

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

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

［6］虞斌能，焦斌，顧幸生.改進協(xié)同粒子群優(yōu)化算法及其在Flow Shop調度中的應用［J］.華東理工大學學報（自然科學版），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.