改進激素算法求解置換流水車間調度問題

鄭 堃，練志偉，王玉國，朱長建，顧新艷，劉 軒

(1. 南京工程學院汽車與軌道交通學院 南京 211167；2. 中德智能制造研究院 南京 211800)

置換流水車間調度問題(permutation flow shop scheduling problem, PFSP)是流水車間調度中經典的問題之一，也是實際工程應用最廣泛的規劃問題。目前，精確方法、啟發式方法和元啟發式方法是求解PFSP 常用的3 類方法。精確方法不適合求解復雜度會呈指數增加的調度問題[1]。啟發式方法[2]可快速給出確定的調度方案，但過分依賴局部調度規則。元啟發式方法又稱為智能優化算法，是目前求解PFSP 的重點研究方法。

智能優化算法又可分為進化算法(evolution algorithm, EA)、群智能算法(swarm intelligence, SI)和局部搜索算法(local search, LS)等。EA 通過模仿自然界的進化過程抽象而來，是PFSP 的主要處理手段。EA 中應用最廣泛與深入的是遺傳算法(genetic algorithm, GA)[3]，文獻[4-5]針對GA 存在的缺點進行改進，并用現有的PFSP 標準算例進行驗證，證明其改進的有效性。SI 是受自然界種群的群體智能行為啟發，如共生生物搜索算法(symbiotic organisms search, SOS)[6]是根據自然界的共生關系啟發得出的。LS 通常根據PFSP 的特點設計相應的鄰域操作，并利用該鄰域操作對當前局部最優解進行深度挖掘，如文獻[7]研究了3 個基本鄰域操作求解PFSP 的性能，并與粒子群(particle swarm optimization, PSO)算法相結合，取得了不錯的效果。

GA 的深入研究使其在多個領域獲得了廣泛應用[8-9]。GA 的操作主要包括選擇、交叉以及變異這3 個基本遺傳算子，其中交叉算子是GA 區別于其他EA 的重要特征，是GA 產生新個體的主要方法。文獻[10]首次利用提出的兩點交叉(two-points crossover, TPX)探索PFSP 解空間，取得了不錯的效果，被多次引用[11-12]，但TPX 的交叉點為隨機選取，所以存在冗余度高和算法中后期效率低等缺陷。文獻[4]針對GA 本身不具備記憶功能而導致優質解易丟失、收斂速度慢和最終解的質量低等缺點，提出保優機制和選擇策略，按一定保優比例，將優質解遺傳到下一代種群中。文獻[5]利用限優策略保持種群多樣性，解決GA 陷入局部等問題。因此有學者提出混合算法，即將智能算法中的各類算法進行混合，作為適用域拓展和算法性能提高的重要手段，如文獻[13]將SOS 與LS 結合，提出了混合共生生物搜索算法(hybrid symbiotic organisms search, HSOS)，采用標準算例集證明其優越性和穩定性，在優化過程中可同時滿足探索(exploitation)和開發(exploration)、集中性(intensification)和廣泛性(diversification)，但會增加算法的計算復雜度和搜索時間。

近年來，學者們進一步提出了生物學和生產制造系統相結合的方法。文獻[14-15]在這方面研究頗多。利用生物體的激素調節對體內各種激素的調控具有較好的自適應性和穩定性等優點，文獻[16]提出了基于激素調節規律的改進型自適應遺傳算法(improved adaptive genetic algorithm, IAGA)，并結合作業車間調度問題進行了驗證；文獻[17-18]將激素調節規律應用至PSO 的速度更新公式和慣性因子來求解PFSP 和混合流水車間調度問題。目前基于激素調節的算法已被證實能有效克服種群進化緩慢、個體早熟等缺陷問題，但受激素濃度的影響，一般激素濃度的計算方法使激素調節規律在目標函數較大時，出現了失調現象，因而無法保證基于激素調節的算法能具有更好的優化結果。

綜上所述，在采用GA 求解PFSP 問題時，為解決常用選擇算子中TPX 的缺陷、全局最優解收斂困難問題以及IAGA 的局限性，本文提出了基于改進激素濃度計算法的IAGA(improved hormone concentration calculation method-iaGA, IHCCMIAGA)。該算法主要將激素調節機制引入到選擇算子中，通過改進激素濃度的計算方法，使基于激素調節規律的參數在目標函數值較大時仍有較好的靈敏度；采用了精確取點的ITPX 算子進行交叉，提高算法的探索能力；通過建立優良基因庫及免疫因子，保存并監控每代進化過程的優質解，同時將多種擾動操作和局部搜索算法進行組合，設置湮滅因子并利用免疫因子映射的影子標記優質染色體來共同引導局部搜索，提高算法的局部開發特性。

PFSP 描述為：有n個相互獨立工件{J1,J2,····,Jn}，使用m臺加工機器{M1,M2,····,Mm}，每個工件在每臺機器上的加工時間都不相同。調度目標為優化工件的加工順序使得最后的完工時間最小，此過程需滿足如下約束。

1) 初始時刻，所有工件和加工機器準備就緒；

2) 機器之間的順序是固定的，所有工件需以相同的順序經過每臺機器；

3) 任意時刻一臺機器只可加工一個工件；

4) 機器一旦開始加工，則不能中斷；

5) 工件之間存在先后排序。

PFSP 的數學模型描述如下：假設p(i,j)表示工件j在機器i上的加工時間，且工件之間的排序為集合O(O1,O2,····,On)，工件在機器上的加工順序為機器1～機器m，則n個工件在m臺機器上的完工時間C(i,Oj)分別為：

1 置換流水車間調度問題描述

因此，求解PFSP 的目標函數為min{Cmax(O)}。

2 IHCCM 在IAGA 中的應用

2.1 IHCCM-IAGA 流程

IHCCM-IAGA 流程如圖1 所示，該算法能很好地彌補傳統GA 的不足，使得改進算法在求解的性能上擁有更大優勢。

圖1 IHCCM-IAGA 流程框圖

由圖中可知，IHCCM-IAGA 算法較普通GA流程的主要差別為激素的應用、優良基因庫和免疫因子的引入、兩種交叉方式的實現、變異算子與局部搜索的融合以及種群湮滅算子和湮滅因子的建立。其具體執行步驟如下。

1) 確定參數。包括種群N和基因庫規模NP、迭代次數G、種群湮滅因子Af、自適應選擇門檻Po、交叉概率Pc和變異概率Pm等一些參數；

2) 利用反向學習法生成初始種群法和初始化UMax；

3) 評價種群中每個染色體的適應度值，計算自適應選擇門檻Po、交叉概率Pc和變異概率Pm，并判斷是否更新UMax，同時根據要求更新基因庫或初始化基因庫；如果達到最大迭代次數則輸出最優解或近似最優解，其中輸出解為免疫因子攜帶的染色體和其適應度值，結束運行；否則執行步驟4)；

4) 生成隨機概率P或P1，若P＜Pc，則在種群和優良基因庫各選一個染色體進行ITPX 交叉，否則，P＜1-Pc或P1＜1-Pc時，在種群選出兩個染色體進行ITPX 交叉，其中如果從種群選取染色體，則按選擇操作選取個體，否則隨機選取；

5) 若隨機概率P＜Pc，則按變異規則進行局部搜索變異和多樣性變異，產生下一代種群；

6) 更新當前迭代次數g，并檢查免疫因子攜帶的適應度值是否有改變，若有改變，則不對當前種群做任何變動，且重置累計迭代次數的計算；否則更新累計迭代次數，并檢測累計迭代次數是否達到湮滅門檻，若達到湮滅門檻，則對當前種群實行湮滅和更新湮滅因子Af，同時重置累計迭代次數的計算；

7) 返回步驟3)。

2.2 IHCCM-IAGA 原理

2.2.1 基于激素調節的IAGA 參數設計

通常種群進化過程主要分為兩個階段：1)種群進化前期：交叉概率大、變異概率小，有利于種群的快速收斂，較優解不易丟失的特點；2)種群進化后期：交叉概率小、變異概率大，有利于精細化搜索，種群多樣性的保持。但傳統GA 的交叉概率和變異概率固定，且參數選擇困難，而這極大影響GA 的優化結果。因此，借鑒內分泌激素調節規律的上升和下降函數，文獻[16,19]提出了基于激素調節的改進型自適應遺傳算法(IAGA)。

同時種群多樣性還與選擇算子息息相關，因此，有必要設置一個由激素調節的自適應選擇門檻。

內分泌激素的基本規律由文獻[20]提出，它揭示激素具有單調性和非負性的變化特性，激素調節的上升規律函數Fup(X)和下降規律函數Fdown(X)遵循Hill 函數規律，其公式如下：

式中，X為函數自變量；D為閥值，且D＞0；n為Hill 系數，且n≥1；n和D共同決定上升下降曲線斜率。

圖2 為參數D=1，n=1,2,3 情況下的Hill 變化曲線。當參數D不變、n值由小到大時，Hill 曲線收斂的速度越來越快，到達穩定狀態所需時間也越來越少。

圖2 參數n 對Hill 曲線的影響

如果激素x受激素y調控，則激素x的分泌速度Sx與激素y的濃度Cy的關系為：

式中，Sx0為激素x的基礎分泌速率；α 為常量系數。

將式(7)和式(8)代入式(9)，得：

模仿式(10)和式(11)，設計了與種群優劣程度相關的自適應選擇門檻、交叉概率和變異概率因子函數，具體如下。

1) 自適應交叉概率[16]：由式(11)設計出自適應交叉概率為：

2) 自適應變異概率[16]：根據式(10)，設計自適應變異概率為：

2.2.2 參數的選擇范圍討論

1) α、β 和γ

α、β 和γ 的取值將影響自適應交叉概率、變異概率和選擇門檻的增幅和減幅，其取值范圍由式(12)～式(14)確定，可得：

2)nc、nm和no

同樣，參數nc、nm和no的取值會對自適應交叉概率、變異概率和選擇門檻的進化速度產生影響。一般地，取值范圍為1～4 之間的整數。

2.2.3 內分泌激素濃度計算法的改進

激素調節規律與激素的濃度有關，而GA 中的激素濃度由fav決定，一般fav的適應度值主要由目標函數值取倒數(1/Makespan)獲得，從而使得激素濃度總是能夠與Hill 上升和下降函數呈正相關和負相關的聯系，即適應度值越大，適應能力就越強。所以在Makespan 較小時，對激素調節有很好的引導作用，但適應度由目標函數取倒數不僅會有參數的影響，且隨著Makespan 越來越大，其適應度值會以降低數量級的形式表達，因此個體適應度值之間的變化量就越小，此時受激素濃度影響的激素調節規律將會出現調節不明顯、失調等現象，即選擇門檻、交叉概率和變異概率不再嚴格遵循Hill 下降和上升函數的規律。為此，本文將對計算激素濃度的方法進行改進，以解決激素規律失調的問題。

對激素公式中適應度值的計算方法改進如下：

1) 評價初始種群中每個染色體，記其中最差染色體的最大適應度值max{Cmax(O)}為UMax=max{Cmax(O)}+50；

2) 以UMax為標準，對種群中所有染色體計算標準化適應度值，標準化公式為fSi=UMax-fi，i=1,2,···,N，為種群中每個染色體離目前已知最差染色體的距離；染色體越好，離最差染色體就越遠，其fSi越大，相反，離最差染色體就越近，其fSi就越小；可見，改進的計算方法可以與激素的調節規律和現實意義成正比，具有可行性。

3) 用標準化適應度值計算激素公式中的fav、fmin和fmax，在種群每次迭代后計算標準適應度值時，如有fSi≤0，則在計算完fav、fmin和fmax后，更新當前UMax，更新方法為計算當代種群中最差染色體的最大適應度值max{Cmax(O)}為UMax=max{Cmax(O)}+50；

激素調節規律除受激素濃度fav調控外，還受激素震蕩的影響，激素震蕩由fmax與fmin的差值決定。當差值過大時，激素規律則認為種群染色體分布趨于兩極化，由激素震蕩成為主控因子，調節選擇門檻、交叉概率快速增大和變異概率快速減小，以確保種群染色體分布均勻，保持種群的穩定。相反，當差值過小時，激素規律則認為種群染色體分布過于集中、多樣性過少，此時激素震蕩仍是主控因子，調節選擇門檻、交叉概率快速減小和變異概率快速增大，以確保種群染色體分布均勻、增加多樣性；而差值過大或過小，使得激素震蕩成為主控因子，無法正確反映種群的實際情況，因此收斂速度不穩定、解的質量也難以保證。為此，只有在差值合適時，激素濃度才是主控因子，而一般激素濃度的計算方法可以做到此點，且受激素震蕩的微調作用。為此，本文對標準化的fmin改為fmin=fav/2+fmin，使改進后的激素濃度計算法與一般激素濃度計算法具有相同的調節作用。

3.1.1 染色體的編碼

用 集 合O={O1,O2,···,On}表 示 工 件 在 機 器1～機器m上的加工順序，集合O中的元素用工件的整數編號表示，用集合J={J1,J2,···,Jn}表示工件集，從而構造出基于工件編號的整數編碼，例如7 個工件的集合O={1,3,4,2,6,5,7}所對應工件的加工順序為J1→J3→J4→J2→J6→J5→J7。

本文將采用文獻[21]提出的反向學習法(opposition-based learning, OBL)，設工件編號的最小數為1，最大數為n，當前工序的工件編號為Oi，則Oi的反向學習Oi的編號如為：

3 IHCCM-IAGA 求解PFSP

3.1 初始化種群

3.1.2 初始化方法

因此本文的初始化過程如下。

1) 設置初始種群個體數為N，隨機初始化N個染色體，生成初始種群P1；然后對種群P1 中的所有染色體進行如圖3 所示的反向學習，生成初始種群P2；

圖3 染色體的反向學習

2) 將初始種群P1 和P2 合并，計算合并后所有染色體的目標值并從小到大進行排列，選取前N個染色體作為最后的初始種群。

3.2 適應度函數

根據每個染色的集合O編碼計算其目標函數值Makespan，并作為其適應度值，即fitness=min{Cmax(O)}。

3.3 選擇操作

本文采用文獻[22]提出的錦標賽選擇方法，并加以改進，確保在種群進化后期能夠更好的保持種群多樣性。

每次從種群中選擇若干個體進行適應度比較，選出最差的個體和最優的個體，若隨機值(在0～1 之間隨機產生)小于門檻(受激素調節的值)，則選擇最優的一個，否則就選擇最差的一個。這樣可保證在種群進化前期，高性能個體能最大限度的遺傳至下一代，以提高種群的全局收斂速度；在種群進化后期，提高較差個體進入下一代種群的概率，以確保種群多樣性，從而更好地克服個體早熟和局部收斂等現象。

3.4 交叉操作

3.4.1 ITPX 算子

對基于工件編號整數排列的編碼方式，一般采用TPX[10]來產生子代，如圖4 所示，此方法容易出現冗余、效率低等問題，無法高效地對解空間進行搜索，因此最后解的質量得不到保障。

圖4 TPX 交叉算子

本文將在此交叉算子的基礎上進行改進，提出一種精確的取點方式ITPX，具體步驟如下。

1) 對兩個父代染色體從左向右依次等基因位對比，標注等基因位值不同的基因位，記作集合T={T1,T2,···,Ts}，其中T1為兩父代染色體第一不同的基因位，Ts為兩父代染色體最后不同的基因位，T1至Ts的基因位距離稱為最大不同基因位區間；

2) 設置兩個交叉點分別為n1、n2，且n2＞n1。n1和n2分兩次從集合T中選取基因位作為其交叉點。當n1從集合T選取交叉點時，n1第一個交叉點必須從染色體的第一個基因位開始選取(不管染色體第一基因位是否為不同基因位)，記為a0；n1其余交叉點從集合T中按1～s的順序選取，記為a1，同時若從集合中選取的第一個基因位T1為染色體第一基因位，則按順序重新選取，直至集合T選取完畢。n2則從左向右依次選取交叉點，n2開始交叉點b0選取規則為：若n1=a0，且a0≠T1，則n2開始交叉點為T1，若a0=T1，則n2開始交叉點為a0+1；若n1選取的交叉點為a1，則n2開始交叉點為a1+1；n2結束交叉點均為Ts-2。每當n1選取一個交叉點，n2則從b0開始，依次加1，直至結束點Ts-2；n1只能從集合T中選取Ts-2 之前的點；

3) 當n2從集合T選取交叉點時，n2第一個交叉點必須從染色體的最后一個基因位開始選取，記為an-1；n2其余交叉點從集合T中按1～s的順序選取，記為a2，直至集合T選取完畢，其中如果從集合中選取的最后基因位Ts為染色體最后基因位，則提前結束選取。n1則從右向左依次選取交叉點，n1開始交叉點b1選取規則為：若n2=an-1，且an-1≠Ts，則n1開始交叉點為Ts，若an-1=Ts，則n1開始交叉點為an-1-1；若n2選取的交叉點為a2，則n1開始交叉點為a2-1；n1結束交叉點均為T1+2。每當n2選取一個交叉點，n1則從b1開始，依次減1，直至結束點T1+2。以上過程，如圖5所示。值得注意的是，n2只能從集合T中選取T1+2 之后的點。

圖5 ITPX 算子的精確交叉取點方式

通過ITPX 方法生成兩父代所有子代，從各自子代集中選取最優的染色體作為下一代，且免疫因子實時監測兩父代產生的子代集，以保證優質解的不丟失。同時本文引入優良基因庫，并采用兩個交叉概率來實現兩種交叉方式，一種是分別從優良基因庫隨機選擇染色體，按選擇操作從種群中選擇染色體以Pc概率進行交叉；另一種是兩個染色體均按選擇操作從種群中選取以1-Pc的概率進行交叉。

3.4.2 優良基因庫

優良基因庫主要分為以下幾個部分。

1) 免疫因子：免疫因子主要監控每代種群在交叉算子中所有的子代染色體和變異算子中局部搜索部分，實時更新優于免疫因子所攜帶的染色體；

2) 免疫因子映射的影子：影子只映射免疫因子攜帶的值，利用影子標記基因庫中適應度值相同，但兩兩個體H 距離均不同的染色體(兩個染色體中不同基因位的個數稱為海明距離，簡稱H 距離)，并對這些染色體從零開始標號，記最大標號為M，利用映射的影子標記優質染色體來引導下一代種群的局部搜索；

3) 優良基因庫初始化：設優良基因庫最大容量為NP，初始化時，從初始化種群引入適應度由低到高排序的前NP/2 染色體到基因庫中，剩余的容量在種群進化時按更新策略填充引入；同時對免疫因子初始化，記錄基因庫中適應度最優的染色體；

4) 優良基因庫更新策略：在每代種群進化完成時，對基因庫更新，更新策略分為兩種情況: ①當優良基因庫有容量時，評價當代種群中每個染色體，并與當前基因庫中最差染色體比較，如果小于，則檢查當前染色體是否有與基因庫中染色體適應度值相同，如有相同，則計算兩個染色體H 距離，若H=0，則不引入，否則引入填充；②當優良基因庫沒有容量時，利用替換方法實現更新策略，并重新標記當前基因庫中最差染色體及其適應度值。

3.4.3 種群湮滅

為了更好地開發空間多樣性和探索解空間，利用優良基因庫中的免疫因子對種群湮滅是否觸發進行判斷，其判斷過程為：當種群連續累計迭代一定次數后，免疫因子仍不更新，則觸發；當免疫因子有更新時，則重新累計迭代次數。同時，設置湮滅因子Af，種群每湮滅一次，湮滅因子則從初始值依次疊加。湮滅因子主要用來影響變異算子的局部搜索，旨在增強變異的局部搜索特性。

本文對種群80%個體實行湮滅，湮滅方式為將種群前40%的個體實行反向學習，并依次隨機打亂生成新染色體，后40%的個體利用隨機初始化法生成新染色體。基因庫只保留由免疫因子映射影子標記的優質染色體，保留數目不得超過整個基因庫最大容量的20%，其余優質染色體實行刪除操作，由種群湮滅后的染色體以適應度由低到高排序依次填充基因庫，其中免疫因子等不參與湮滅。

3.5 變異操作

本文將具有豐富結構的多種擾動操作和局部搜索算法進行組合，構成組合變異算子，相比在選擇-交叉-變異等操作之后再引入局部搜索算法，組合變異算子能更好地維持種群的多樣性。

變異過程如圖6 所示，主要步驟為：滿足變異概率后，變異開始：生成隨機概率P1，若P1＜Pm，則開始局部搜索，否則進行多樣性變異；其中當父代染色體的適應度值等于免疫因子映射影子的值(fc=fIfs)，則實施局部搜索1，否則從局部搜索2 開始，若搜索過程當中有新染色體優于免疫因子，則替換后，觸發湮滅因子重置準則和直接跳轉至多樣性變異，即fn＜fIf；因此圖中的“是”表示有更加優質的新染色體，“否”表示無。具體實現如下：擾動操作主要包括① 插入：隨機選擇染色體的兩個不同基因位，將其中一個基因位插入到另一個基因位的前面；② 反轉逆序：隨機選擇染色體的兩個不同基因位，對兩個不同基因之間的所有基因反轉逆序；③ 打亂互換：隨機選擇染色體中一些不同的基因位，然后隨機打亂，重新排序；④ 兩點互換：隨機選擇染色體的兩個不同基因位，將這兩個不同基因互換。

圖6 變異過程

局部搜索主要分成3 部分。

1) 首先利用擾動操作對此父代染色體局部變換，共變換5Af次，生成Af×5 個子代染色體，擾動選擇過程為：設置隨機整數r，范圍為0～5，當r=0 時，采用①；當r=1 時，采用②；當r=2 或3 或4 時，采用③；當r=5 時，采用④。然后評價所有子代染色體，判斷fn＜fIf；否則從父代染色體開始以1-Pc的概率進入循環搜索，如圖7 所示。循環搜索分為大循環和小循環，大循環次數為Af，小循環次數為Af×5，衰減系數Q=0.12/Af-(fc-fIf)/(fIf×0.062 4×Af2)；大循環均從零遞增計數，小循環從準許的最大次數遞減計數，滿足循環次數或fn＜fIf時結束，同時記當前染色體適應度值為f1和f2，染色體為C1和C2；記當前大循環的次數為T，則衰減值為1+TQ，記當前小循環的次數為t和對染色體C1的更新次數為Count，每次大循環時，初始化Count=0，則小循環過程為：先利用擾動①②④生成新的染色體，根據文獻[7]的分析，設隨機概率P＜0.15 時，選擇②，隨機概率P＜0.4或P1＜0.4 時，則選擇①，若上述概率都不滿足，則選擇④，新染色體判斷準則和處理分類如下：I. 判斷fn＜fIf；II. 若fn＜f1&fn＜f2，則接受fn，并更新f1、f2、C1、C2和Count；III. 若fn＞f1&fn＜f2，也接受fn，但只更新f2和C2；IV. 若fn＞f1&fn＞f2，則計算接受概率Pa=(t×衰減值)/(Af×10)，若隨機概率P≤Pa，則接受fn，并更新f2和C2，否則不接受fn，利用C2對當前染色體重置，若隨機概率P＞Pa且Count=0，則利用C1和f1對當前染色體和f2重置。

圖7 循環搜索

每進入下一次小循環時，則利用C1和f1對C2、f2和當前染色體重置，直至當前大循環結束，輸出C1和f1，同時若當前搜索的染色體為子代染色體且輸出的f1≠fIfs，則利用C1和f1對當前子代染色體更新。若父代染色體和所有子代染色體循環搜索完畢，且沒有fn＜fIf，則隨機概率P＜1-Pc，將從子代染色體中隨機選取一個替換當前染色體，否則選擇子代染色體中最優的個體替換，并進入第二部分局部搜索。

2) 利用基因庫被標記的隨機染色體對當前父代染色體進行比對，保留相同或不同的基因，對不同或相同的基因全排列搜索或擾動③搜索，生成所有子代染色體，然后評價所有子代染色體，記錄其中適應度最小的染色體fmin、適應度最大的染色體fmax和隨機一條染色體frand，并判斷fn＜fIf；否則以Pc概率接受fmin染色體，如不滿足上述概率，則以1-Pc概率接受frand染色體，若不滿足上述所有概率，則接受fmax染色體，且進行第三部分的局部搜索。比對選擇方式：若當前染色體經過第一部分局部搜索，則隨機概率P＜Po時，保留相同的基因，對不同的基因搜索，否則保留不同基因，對相同的基因搜索；若當前染色未經過第一部分局部搜索，則隨機概率P＜Po時，保留不同基因，對相同的基因搜索，否則保留相同的基因，對不同的基因搜索；如搜索的基因數超過5 個，則利用擾動③生成120 個子代染色體，否則全排列生成所有子代染色體。

3) 對當前染色體進行循環搜索，大循環次數為隨機整數R，范圍1～Af，小循環次數為30，衰減系數Q=R1-(fc-fIf)/(fIf×0.285×R)，其中R1為0.004～0.013 的隨機數。若記當前大循環的次數為T，則衰減值仍為1+TQ，其循環過程與上述的循環過程一致。

多樣性變異：主要采用擾動①②③作為種群多樣性保持的策略，設置隨機整數r，范圍為0～2，當r=0 時，采用擾動①；當r=1 時，采用擾動②；當r=2 時，采用擾動③；不同的擾動操作可以保持豐富的多樣性結構。

4 試驗仿真與結果分析

為了驗證本文所提算法的性能，進行以下兩個比較實驗。

1) 改進激素濃度計算法(IHCCM)與普通激素濃度計算法的對比實驗。通過Rec[23]算例測試比較改進激素濃度計算法與普通激素濃度計算法的求解性能，為客觀評價改進激素濃度計算法對算法整體性能的提升提供依據。

2) IHCCM-IAGA 對比實驗。通過國際標準算例集Carlier[24]、Rec[23]、Taillard[25]測試比較IHCCMIAGA 與其他算法的求解性能，為客觀評價IHCCMIAGA 和ITPX 的性能提供依據。同時以上所有比較實驗最終輸出解均為免疫因子信息。

改進的遺傳算法采用DEV C++編程，程序在環境為Intel(R) Core(TM)，主頻2.3 GHZ，內存8 GB的個人計算機上運行。經過多次試驗比較，設定如表1 所示的實驗參數。同時為了節省優化時間和提高算法性能，ITPX 交叉點設定如下選取規則：若集合T的個數為小于等于4，全部選取；若集合T的個數大于4，但小于等于10，則記集合T的個數為Num，選取個數SN 為5～Num，選取點為從集合T中隨機選取SN 個不同的點；若集合的個數大于10，則選取個數SN 為5～10，選取點為從集合T中隨機選取SN 個不同的點。其中n1和n2選取的交叉點一致，針對每個算例分別連續運行20 次，同時使用最佳相對誤差 (best relative error,BRE)、平均相對誤差 (average relative error, ARE)和最差相對誤差 (worst relative error, WRE)評價本文算法結果，其計算公式分別如下：

表1 實驗參數

式中，C*為目前該問題已知的最優值；Cbest為算法在規定次數內求解該算例的最優值；Cavg為算法在規定次數內求解該算例的平均值；Cworst為算法在規定次數內求該算例的最差值。

4.1 IHCCM 對比實驗

激素濃度測試算法框架不包括種群湮滅和局部搜索變異，改進激素濃度計算法與普通激素濃度計算法下自適應參數均采用如表1 所示的實驗參數，為了節省運行時間，迭代次數G改為100。因變異除了可保持多樣性還具有較強的局部搜索能力，結合本文具有優良基因庫等原因，為了實驗數據的有效性和嚴謹性，將兩者的Pm設為可收斂的最大近似值0.41，同時兩者采用同一初始種群進化比較。

如圖8 所示，“I”表示改進法的參數，如IPcav、IPo等；“av”表示連續運行20 次的平均參數變化曲線，如Pcav、Poav等；“1”表示其中的特例，如Pc1、Po1 等。自適應參數主要表現在圖8的上、中、下3 個區間的變化曲線。

圖8 基于不同激素濃度計算法下的自適應參數變化曲線

圖9 為兩者連續運行20 次最優解的分布圖，其中IHCCM 表示改進濃度計算法，HCCM 表示普通濃度計算法。可以發現，IHCCM 在解的分布上，有13 個優于HCCM，且圖中最優解在IHCCM一側，而HCCM 只有7 個解優于IHCCM，且圖中最差解在HCCM 一側。綜上所述，可以發現改進激素濃度計算法相比普通激素濃度計算法在求解較大Makespan 時更具優越性，能有效解決因激素濃度變化量過小而導致激素失調的問題。

圖9 不同激素濃度計算法下解的分布比較

4.2 IHCCM-IAGA 對比實驗

4.2.1 Carlier 測試集

Carlier 算例集為小規模測試集，為了檢驗本文算法對小規模問題的性能，與混合蝙蝠算法(hybrid bat algorithm, HBA)[26]、基于變鄰域搜索的粒子群算法(particle swarm optimization based on variable neighborhood search, PSOVNS)[27]、混合回溯搜索算法(hybrid backtracking search algorithm,HBSA)[28]以及混合共生生物搜索算法(HSOS)[13]進行比較，比較結果如表2 和表3 所示，其中CPU/S為連續運行20 次的平均優化時間。

表2 Car 測試集的最優解比較

表3 Car 測試集的計算結果誤差比較

可以發現本文算法與HSOS 一樣，在BRE、ARE 和WRE 均可取得最好的測試結果，而其他算法卻都會出現細微偏差，說明本文算法不僅具有很好的穩定性，而且具有非常好的局部搜索特性，不易陷入局部最優，這不僅得益于變異中的局部搜索，更得益于ITPX 算子和激素調節下的多樣性變異，同時算法的運行時間也在可接受范圍內。

4.2.2 Rec 測試集

Rec 算例集為中、大規模的測試集，為了檢驗本文算法對中、大規模問題的性能，與離散蝙蝠算法(discrete bat algorithm, DBA)[29]、混合差分估計分布算法(differential evolution and estimation of distribution algorithm, DE-EDA)[30]、混合共生生物搜索算法(HSOS)[13]和變參數量子進化算法(variable parameters quantum-inspired evolutionary algorithm,VP-QEA)[31]進行比較，比較結果如表4 所示，其中CPU/S 為連續運行20 次的平均優化時間。

表4 Rec 測試集的計算結果誤差比較

從表中可發現，本文算法在21 個Rec 算例取得的誤差，絕大數都小于表中所比較的算法，其中有20 個算例的BRE 優于或等于其他算法求解的BRE；有17 個算例的ARE 優于或等于其他算法的ARE；有17 個算例的WRE 優于或等于其他算法的WRE。

圖10～12 所示為表4 中各個算法在BRE、ARE 和WRE 的曲線圖，從圖中可以發現不管是BRE 還是ARE、WRE，本文算法的整體曲線均處在其他所有算法的最下面，可見本文算法可以取得非常好的優化效果。本文算法在BRE、ARE 和WRE的平均值上均為最小值，排在所有比較算法中的第一位，表現出本文算法具有很強的穩定性和收斂性。

圖10 調度結果最佳相對誤差比較

如圖13 所示為Rec29 算例的進化曲線圖，可見算法在激素調節的作用下，迭代25 次左右就已經收斂于局部最優解，此時自適應選擇門檻、交叉概率和變異概率均已達到理論峰值，隨后ITPX 將結合變異算子中的局部搜索和湮滅因子等因素，進行精細化搜索，使得算法在中后期仍有很強的搜索能力和局部開發特性，以至在迭代250 次之后仍有下降趨勢，直至找到最優解2 287。相比其他算法，均無法找其最優解，且存在一定誤差，體現了本文算法的有效性，具有克服個體早熟、增強全局探索能力和局部開發特性。

圖11 調度結果平均相對誤差比較

圖12 調度結果最差相對誤差比較

圖13 Rec29 算例的進化曲線

因此，在實際生產應用中，若著重實時調度，則IHCCM-IAGA 在激素的調節下可快速收斂于最優解或近似最優解，優化時間較少，如Rec29 算例的近似最優解；若著重解的質量，則IHCCM-IAGA可在ITPX 的支持下進行精細化搜索，以達到最優解，如Rec29 算例的最優解。

4.2.3 Taillard 測試集

Taillard 算例集由中到超大規模的測試集組成，包 括20×5、20×10、20×20、50×5、50×10、50×20、100×5、100×10、100×20、200×10、200×20、500×20 共12 個不同規模組成的算例集，每個規模有10 個算例，取每種規模最后一個算例作為代表，組成本文的測試集。

為了檢驗本文算法對中、大和超大規模問題的性能，與混合遺傳算法(HGA)[32]、混合共生生物搜索算法(HSOS)[13]、貪心禁忌搜索算法(tabumechanism improved iterated greedy, TMIIG)[33]、離散水波優化算法(discrete water wave optimization algorithm, DWWO)[34]、NEH 啟發式算法[35]以及改進的貪心迭代算法(improved iterated greedy algorithm,IIGA)[36]進行比較。比較結果如表5 所示，其中Cav表示該算法在一定運行次數內的平均值。

表5 Taillard 測試集的計算結果比較

本文使用平均錯誤率(average error, AE)評價算法對Taillard 測試集的性能，計算公式如下：

式中，Cavi為算法求第i算例的平均完工時間；UB為該算例目前已知解的上界值；k為算例的數量。

從表5 可以發現，IHCCM-IAGA 有9 個算例的Cav均優于或等于其他算法，有3 個算例的Cav略高于HSOS，但均優于除HSOS 外的其他算法，可見IHCCM-IAGA 在Taillard 測試集上也具有較好的優越性。圖14 為基于Taillard 測試集不同算法的平均錯誤率(AE)，可以發現IHCCM-IAGA 的AE 為1.11，均小于其他算法，其中與HSOS 的AE 相差值為0.4，與除HSOS 外的其他算法AE 相差值均超過20，表現出IHCCM-IAGA 具有更好的穩定性和魯棒性。

圖14 基于Taillard 測試集不同算法的平均錯誤率

綜述上面的實驗結果與分析，可以發現本文的IHCCM-IAGA 具有更好的局部開發特性和更快的全局收斂速度，使得解在質量上和收斂速度上都有明顯提升。

5 結 束 語

本文提出了一種基于改進激素濃度計算法的IHCCM-IAGA 來求解NP 問題的置換流水車間調度問題。針對傳統遺傳算法在求解PFSP 中存在的不足和缺陷，使用了一種基于改進激素濃度計算法的IAGA，通過激素的相互促進與抑制，自適應地調整選擇門檻、交叉概率和變異概率值，使得種群可自適應各種進化環境，同時引入優良基因庫及免疫因子，實現兩種交叉方式并監控整個進化過程，避免優質染色體的丟失。最后，為了進一步提高算法在中后期的探索和開發能力，提出了一種ITPX 算子，并結合組合變異算子和種群湮滅算子等，確保IHCCM-IAGA 在收斂速度和求解的質量上能夠得到更好應用。通過Rec41 算例比較實驗，驗證了改進激素濃度計算法的優越性和有效性。通過國際標準算例比較實驗，也驗證了IHCCMIAGA 和ITPX 的有效性，其在縮減最小完工時間的應用中可取得滿意效果。

編 輯 稅 紅

[23] REEVES C R. A genetic algorithm for flowshop sequencing[J]. Computers and Operations Research, 1995,22(1): 5-13.

[24] CARLIER J. Ordonnancements à contraintes disjonctives[J]. RAIRO-Operations Research, 1978, 12(4):333-350.

[25] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research,1993, 64(2): 278-285.

[26] TOSUN ?, MARICHELVAM M K. Hybrid bat algorithm for flow shop scheduling problems[J]. International Journal of Mathematics in Operational Research, 2016,9(1): 125-138.

[27] TASGETIREN M F, LIANG Y C, SEVKLI M, et al. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem[J]. European Journal of Operational Research, 2007, 177(3): 1930-1947.

[28] LIN Q, GAO L, LI X, et al. A hybrid backtracking search algorithm for permutation flow-shop scheduling problem[J]. Computers and Industrial Engineering, 2015,85(C): 437-446.

[29] LUO Q, ZHOU Y, XIE J, et al. Discrete bat algorithm for optimal problem of permutation flow shop scheduling[J].The Scientific World Journal, 2014, DOI: 10.1155/2014/630280.

[30] LI Z, GUO Q, TANG L. An effective DE-EDA for permutation flow-shop scheduling problem[J]. 2016 IEEE Congress on Evolutionary Computation. [S.l.]:IEEE, 2016:2927-2934.

[31] 張先超, 周泓. 變參數量子進化算法及其在求解置換流水車間調度問題中的應用[J]. 計算機集成制造系統,2016, 22(3): 774-781.ZHANG X C, ZHOU H. Variable parameters quantuminspired evolutionary algorithm and its application permutation flow-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2016, 22(3): 774-781.

[32] TSENG L Y, LIN Y T. A hybrid genetic algorithm for nowait flowshop scheduling problem[J]. International Journal of Production Economics, 2010, 128(1): 144-152.

[33] DING J Y, SONG S, GUPTA J N D, et al. An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem[J]. Applied Soft Computing, 2015,30(1): 604-613.

[34] ZHAO F, LIU H, ZHANG Y, et al. A discrete water wave optimization algorithm for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2017,91(1): 347-363.

[35] NAWAZ M, ENSCORE E, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. The International Journal of Management Science, 1983, 11(1): 91-95.

[36] PAN Q K, WANG L, ZHAO B H. An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion[J]. The International Journal of Advanced Manufacturing Technology, 2008,38(7): 778-786.