運(yùn)用含復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的多種群遺傳算法求解FJSP

石宇強(qiáng)，田永政，張雨琦，石小秋

西南科技大學(xué) 制造科學(xué)與工程學(xué)院，四川 綿陽621000

遺傳算法[1]（Genetic Algorithm，GA）是歷史上備受關(guān)注的進(jìn)化算法之一。標(biāo)準(zhǔn)GA 在求解組合優(yōu)化等問題上具有獨(dú)特的優(yōu)勢，但是極易早熟收斂。為了克服這一缺點(diǎn)，多種群遺傳算法（Multi-population Genetic Algorithm，MGA）隨之出現(xiàn)，并獲得了廣泛的關(guān)注和應(yīng)用[2-4]。MGA將標(biāo)準(zhǔn)GA的單種群劃分為多個(gè)子群，保證了種群的多樣性，每個(gè)子群內(nèi)的個(gè)體按照標(biāo)準(zhǔn)GA 進(jìn)化，精英個(gè)體在子群間遷徙傳播優(yōu)勢基因，從而避免早熟收斂[5-6]。如文獻(xiàn)[2]利用MGA 實(shí)現(xiàn)非線性動(dòng)力學(xué)模型參數(shù)的辨識，預(yù)測橡膠波形發(fā)生器產(chǎn)生的沖擊脈沖。文獻(xiàn)[3]采用MGA 對常用的多孔吸聲結(jié)構(gòu)參數(shù)進(jìn)行優(yōu)化。但是，傳統(tǒng)MGA的子群數(shù)有限，且大多忽略了子群結(jié)構(gòu)對算法性能的影響。如果把子群以及它們之間的交流（優(yōu)勢基因的傳播）分別看作節(jié)點(diǎn)和邊，那么MGA就是一個(gè)復(fù)雜網(wǎng)絡(luò)，代表了不同子群間的相互作用關(guān)系[7-8]。以往研究表明，復(fù)雜網(wǎng)絡(luò)的集體行為會受到網(wǎng)絡(luò)結(jié)構(gòu)的顯著影響[9-13]。類似地，MGA中子群間的交流構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)也將影響其尋優(yōu)行為，進(jìn)而影響MGA 的性能。

復(fù)雜網(wǎng)絡(luò)可以描述自然界和人類社會中各種復(fù)雜系統(tǒng)[14]。其研究在許多領(lǐng)域都得到了應(yīng)用，如金融網(wǎng)絡(luò)[15]、蛋白質(zhì)網(wǎng)絡(luò)[16]、供需網(wǎng)絡(luò)[17]等。在進(jìn)化計(jì)算領(lǐng)域，許多研究者也利用復(fù)雜網(wǎng)絡(luò)對GA 等進(jìn)化算法進(jìn)行了研究。文獻(xiàn)[18]將進(jìn)化算法的動(dòng)態(tài)可視化為復(fù)雜網(wǎng)絡(luò)，提出網(wǎng)絡(luò)進(jìn)化算法框架，并應(yīng)用于GA、粒子群算法和差分進(jìn)化算法中。文獻(xiàn)[19]簡述了進(jìn)化算法的動(dòng)態(tài)性如何轉(zhuǎn)化為復(fù)雜網(wǎng)絡(luò)，并根據(jù)其網(wǎng)絡(luò)特征改進(jìn)了自組織遷移算法、人工蜂群算法和GA 等算法。文獻(xiàn)[20]在蟻群算法的基礎(chǔ)上，在狀態(tài)轉(zhuǎn)移規(guī)則等中加入節(jié)點(diǎn)度系數(shù)，將改進(jìn)算法用于移動(dòng)Agent 問題中，顯著提高了移動(dòng)Agent的遷移效率。文獻(xiàn)[21]利用復(fù)雜網(wǎng)絡(luò)分析了不同的隨機(jī)化對差分進(jìn)化算法的影響。文獻(xiàn)[22]提出了一種基于復(fù)雜網(wǎng)絡(luò)的差分進(jìn)化動(dòng)力學(xué)建模方法，揭示了差分進(jìn)化收斂速度與加權(quán)聚類系數(shù)之間的聯(lián)系。文獻(xiàn)[23]提出了一種動(dòng)態(tài)小世界網(wǎng)絡(luò)來優(yōu)化粒子群算法，提高了算法性能。文獻(xiàn)[24]將差分進(jìn)化算法中個(gè)體看作節(jié)點(diǎn)，動(dòng)力學(xué)傳播方向看作邊，提出利用個(gè)體的目標(biāo)函數(shù)值及網(wǎng)絡(luò)參數(shù)信息依概率選取目標(biāo)向量的機(jī)制，改變不同函數(shù)類型的收斂速度。文獻(xiàn)[25]將GA進(jìn)化過程建模為復(fù)雜網(wǎng)絡(luò)，并設(shè)計(jì)一種自組織動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)，有效提高了GA的性能。文獻(xiàn)[26]利用不同網(wǎng)絡(luò)模型作為算法的底層結(jié)構(gòu)，研究了不同網(wǎng)絡(luò)結(jié)構(gòu)對進(jìn)化算法動(dòng)態(tài)性能的影響，發(fā)現(xiàn)網(wǎng)絡(luò)特性對算法的動(dòng)態(tài)性和解的多樣性有顯著的影響。文獻(xiàn)[27]提出了一種基于復(fù)雜網(wǎng)絡(luò)的粒子群算法，并將該算法用于改進(jìn)AdaBoost算法，縮短了樣本訓(xùn)練時(shí)間，提高了人臉檢測率。

總的來說，現(xiàn)有研究利用復(fù)雜網(wǎng)絡(luò)來改進(jìn)進(jìn)化算法或者研究網(wǎng)絡(luò)結(jié)構(gòu)對進(jìn)化算法的影響時(shí)，它們大多是對算法個(gè)體間優(yōu)勢基因的傳播構(gòu)成的網(wǎng)絡(luò)進(jìn)行研究，鮮有研究考慮子群間優(yōu)勢基因的傳播構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)對算法的影響，且較少考慮網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)的變化對算法的影響并從實(shí)際問題的角度進(jìn)行分析。因此，不同網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)下網(wǎng)絡(luò)結(jié)構(gòu)控制子群間優(yōu)勢基因的傳播對MGA尋優(yōu)性能的影響尚不清楚?，F(xiàn)實(shí)生活中，許多網(wǎng)絡(luò)的節(jié)點(diǎn)度分布服從冪律分布，即無標(biāo)度網(wǎng)絡(luò)[28]?，F(xiàn)實(shí)復(fù)雜網(wǎng)絡(luò)的標(biāo)度指數(shù)各不相同，有的網(wǎng)絡(luò)有核心節(jié)點(diǎn)存在但不具有無標(biāo)度特性[29-30]。因此，本文利用不同標(biāo)度指數(shù)的無標(biāo)度網(wǎng)絡(luò)，或有核心節(jié)點(diǎn)但不具有無標(biāo)度特性的網(wǎng)絡(luò)來設(shè)計(jì)MGA，得到一種含復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的多種群遺傳算法（Multi-population Genetic Algorithms with Complex Network Structures，MGA-CNS），然后以經(jīng)典的柔性作業(yè)車間調(diào)度問題（Flexible Job shop Scheduling Problem，F(xiàn)JSP）[31]為例，利用MGA-CNS 來解決一個(gè)FJSP 基準(zhǔn)測試問題，研究在解決實(shí)際問題時(shí)不同網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)對算法性能的影響。最后，將參數(shù)優(yōu)化后的MGA-CNS來求解更多FJSP 實(shí)例并與多種其他算法進(jìn)行比較，驗(yàn)證其有效性。

綜上所述，為了了解在不同網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)下網(wǎng)絡(luò)結(jié)構(gòu)控制子群間優(yōu)勢基因的傳播對MGA 尋優(yōu)性能的影響，本文進(jìn)行了以下研究：（1）提出一種含復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的多種群遺傳算法；（2）通過仿真控制網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)的變化，研究網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)對算法尋優(yōu)性能的影響。

1 模型與算法

1.1 柔性作業(yè)車間調(diào)度問題

FJSP由Brucker等[31]提出，可以簡單地描述為：在一個(gè)車間有m 臺機(jī)器(M1,M2,…,Mm) 對n 個(gè)工件(J1,J2,…,Jn) 進(jìn)行加工。其中，每個(gè)工件Ji有若干個(gè)工序，分別記為：Oi1,Oi2,…,Oini。每個(gè)工序可以在一個(gè)候選機(jī)器集上進(jìn)行加工，第i 個(gè)工件第j 個(gè)工序的候選機(jī)器集記為Sij，其在第k 臺機(jī)器(Mk)上進(jìn)行加工的時(shí)間表示為Pijk。每臺機(jī)器一次只能加工一個(gè)工序，同一工序可在多臺機(jī)器上進(jìn)行加工，但每個(gè)工序每次只能在一臺機(jī)器上加工。FJSP 可以分為兩個(gè)子問題：一是為每個(gè)工件的每個(gè)工序選擇合適的機(jī)器，另一個(gè)是為分配給同一機(jī)器的所有工序安排合適的加工順序。FJSP通常有最小化最大完工時(shí)間和最小化最大機(jī)器工作載荷等優(yōu)化目標(biāo)。本文以研究算法性能為目的，因此選擇最常用的最小化最大完工時(shí)間為優(yōu)化目標(biāo)，F(xiàn)JSP 的數(shù)學(xué)模型如下所示[7]：

公式（1）表示目標(biāo)函數(shù)，即最小化最大完工時(shí)間。Fij和Fmax分別表示工序Oij的完工時(shí)間和所有作業(yè)的最大完工時(shí)間。公式（2）表示工藝約束，確保了同一工件的所有工序的正確加工順序，當(dāng)工序Oij在第k 臺機(jī)器上進(jìn)行加工時(shí)，Xijk等于1，否則為0。公式（3）表示每個(gè)工序每次只能在一臺機(jī)器上加工，Bijk和Fijk分別表示工序Oij在第k 臺機(jī)器上的加工開始時(shí)間和加工完成時(shí)間。公式（4）表示每臺機(jī)器一次只能加工一個(gè)工序。其中，符號“∧”和“∨”分別表示邏輯與和邏輯或。表1給出了一個(gè)FJSP例子。

表1 一個(gè)FJSP例子

在表1的例子中，給出了三個(gè)工件，六臺機(jī)器，每個(gè)工件都有兩個(gè)工序。其中，數(shù)字0表示該工序不能在對應(yīng)的機(jī)器上進(jìn)行加工，其余數(shù)字表示工序Oij在機(jī)器Mk上的加工時(shí)間。比如，第五行第一列的0 表示第三個(gè)工件的第一個(gè)工序O31不能在機(jī)器M1上進(jìn)行加工，第二行第一列的8表示第一個(gè)工件的第二個(gè)工序O12在機(jī)器M1上的加工時(shí)間為8。

1.2 含復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的多種群遺傳算法

生成無標(biāo)度網(wǎng)絡(luò)的模型中，最經(jīng)典的當(dāng)屬BA 模型[28]。BA 模型的主要特點(diǎn)是增長和優(yōu)先連接，其節(jié)點(diǎn)度(K)服從冪律分布：K-γ（γ 為標(biāo)度指數(shù)）。然而，由BA模型所生成的無標(biāo)度網(wǎng)絡(luò)的標(biāo)度指數(shù)接近一個(gè)常數(shù)(γ=3)，但實(shí)際復(fù)雜網(wǎng)絡(luò)的標(biāo)度指數(shù)各不相同，也有的網(wǎng)絡(luò)不具有無標(biāo)度特性，但總有核心節(jié)點(diǎn)的存在[29-30]。因此，本文利用文獻(xiàn)[29]和[32]提到的參數(shù)可控的復(fù)雜網(wǎng)絡(luò)模型，生成不同標(biāo)度指數(shù)的無標(biāo)度網(wǎng)絡(luò)，或生成含有核心節(jié)點(diǎn)但不具有無標(biāo)度特性的網(wǎng)絡(luò)，以研究不同網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)對MGA的影響規(guī)律。該模型可描述如下：

從一個(gè)初始規(guī)模為m0（初始節(jié)點(diǎn)數(shù)為m0）的全連接網(wǎng)絡(luò)開始，每一時(shí)間步t 引入一個(gè)新節(jié)點(diǎn)j，每個(gè)新節(jié)點(diǎn)j 與m(≤m0)個(gè)老節(jié)點(diǎn)相連接，不允許重邊與自環(huán)。老節(jié)點(diǎn)i 被選擇的概率與其產(chǎn)生核(Ai)有關(guān)，表示為：

式（6）中，?k 表示求和號涵蓋所有老節(jié)點(diǎn)，Ai表示為：

其中，α 和β 是兩個(gè)可控參數(shù)，Ki為節(jié)點(diǎn)度（節(jié)點(diǎn)i 的鄰居節(jié)點(diǎn)數(shù)量）。當(dāng)β 不變時(shí)，不同的α 值可生成不同標(biāo)度指數(shù)的無標(biāo)度網(wǎng)絡(luò)。當(dāng)α 不變時(shí)，不同的β 值可生成含有核心節(jié)點(diǎn)但不具有無標(biāo)度特性的網(wǎng)絡(luò)。圖1 繪出了具有12個(gè)節(jié)點(diǎn)的無標(biāo)度網(wǎng)絡(luò)示意圖。

圖1（a）繪出了其網(wǎng)絡(luò)結(jié)構(gòu)，圖1（b）中，橫軸按節(jié)點(diǎn)度對12個(gè)節(jié)點(diǎn)進(jìn)行排序，縱軸表示相應(yīng)的節(jié)點(diǎn)度。

圖1 一個(gè)含有12個(gè)節(jié)點(diǎn)的無標(biāo)度網(wǎng)絡(luò)

如前所述，MGA將標(biāo)準(zhǔn)GA的單種群劃分為多個(gè)子群，這些子群構(gòu)成節(jié)點(diǎn)，子群之間優(yōu)勢基因的傳播構(gòu)成邊，不同的連接構(gòu)成了不同的網(wǎng)絡(luò)結(jié)構(gòu)。MGA 中所有子群的數(shù)量稱為子群數(shù)，每個(gè)子群的個(gè)體數(shù)量稱為子群大小[7]。MGA 在執(zhí)行過程中，首先進(jìn)行種群初始化，生成N 個(gè)子群，每個(gè)子群的大小為S。然后，所有子群中的個(gè)體都同時(shí)進(jìn)化，都會根據(jù)適應(yīng)度函數(shù)來評價(jià)個(gè)體，根據(jù)精英制選擇精英個(gè)體，精英個(gè)體在子群間遷徙，從而優(yōu)勢基因在不同子群之間進(jìn)行傳播，產(chǎn)生新一代子群，實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程，直到得到最優(yōu)解。

本文利用上述網(wǎng)絡(luò)模型生成的網(wǎng)絡(luò)來設(shè)計(jì)MGA，控制子群間優(yōu)勢基因的傳播，得到MGA-CNS。節(jié)點(diǎn)就是MGA-CNS 的子群，用V 表示節(jié)點(diǎn)集合；邊就是子種群間優(yōu)勢基因的傳播，用E 表示邊集合；若節(jié)點(diǎn)Vi與Vj連接構(gòu)成邊eij，則eij∈E 。MGA-CNS 的流程圖如圖2所示，具體步驟如下：

步驟1 初始化，根據(jù)編碼規(guī)則隨機(jī)初始化N 個(gè)子群，每個(gè)子群中的個(gè)體數(shù)量為S。

步驟2 判斷是否達(dá)到最大迭代次數(shù)，如果當(dāng)前迭代次數(shù)(Inow)等于最大迭代次數(shù)(Imax)，則輸出最優(yōu)解，并結(jié)束計(jì)算，否則，轉(zhuǎn)向步驟3。

圖2 MGA-CNS的流程圖

步驟3 用解碼算法計(jì)算每個(gè)子群中個(gè)體的適應(yīng)度，將精英個(gè)體保存到精英集合中。

步驟4 根據(jù)適應(yīng)度，采用標(biāo)準(zhǔn)的競標(biāo)賽方法選擇每個(gè)子群的下一代個(gè)體。

步驟5 將得到的個(gè)體隨機(jī)進(jìn)行交叉，產(chǎn)生新的個(gè)體。

步驟6 將得到的個(gè)體根據(jù)變異概率(Pr)進(jìn)行變異產(chǎn)生新的個(gè)體。

步驟7 隨機(jī)選擇一個(gè)子群（節(jié)點(diǎn)Vi），根據(jù)設(shè)計(jì)的網(wǎng)絡(luò)，找到節(jié)點(diǎn)Vi的所有鄰居節(jié)點(diǎn)，找到這些節(jié)點(diǎn)（包含節(jié)點(diǎn)Vi）中最好的精英個(gè)體，將它放入這些節(jié)點(diǎn)中，并保持它們的子群規(guī)模不變。返回步驟2。

圖3 給出了一個(gè)含四個(gè)子群的MGA-CNS，每個(gè)子群含有四個(gè)個(gè)體，個(gè)體間通過遺傳算子進(jìn)化，子群間通過精英個(gè)體的遷徙傳播優(yōu)勢基因。

圖3 MGA-CNS的示意圖

1.3 MGA-CNS解決FJSP

MGA-CNS 在求解FJSP 時(shí)，包含四個(gè)主要的操作，分別是編碼、解碼、交叉和變異。

1.3.1 編碼

使用MGA-CNS 解決FJSP 時(shí)，第一步是知道如何得到一個(gè)暫定的編碼解。文獻(xiàn)[5]中描述了使用整數(shù)編碼方法來獲得編碼解。整數(shù)編碼分為兩個(gè)階段：第一個(gè)階段為機(jī)器編碼，第二個(gè)階段為工序編碼。

在機(jī)器編碼階段，用一個(gè)整數(shù)串表示編碼解；整數(shù)串的數(shù)量表示所有工件的工序總數(shù)量，整數(shù)的位置表示工序，整數(shù)的數(shù)值代表候選機(jī)器中加工該項(xiàng)工序的機(jī)器序號。例如表1 中的FJSP 例子，一共有六個(gè)工序，一個(gè)編碼解為（3 3 2 1 3 1）。這個(gè)整數(shù)串里一共有六個(gè)整數(shù)，代表一共有六個(gè)工序。第一個(gè)整數(shù)3 代表了工序O11在候選機(jī)器中的第三臺機(jī)器中進(jìn)行加工，即機(jī)器M5而不是M3。第二個(gè)整數(shù)3 代表了工序O12在機(jī)器M6上進(jìn)行加工，以此類推。

在工序編碼階段，用一個(gè)整數(shù)串表示編碼解，整數(shù)串的數(shù)量表示所有工件的工序總數(shù)量，整數(shù)的位置表示加工順序，整數(shù)的值表示工序號。如果一個(gè)工件有n 個(gè)工序，那么這個(gè)工件號就會出現(xiàn)n 次。例如表1中的例子，工序編碼解為（2 1 2 3 1 3）。這個(gè)整數(shù)串里一共有六個(gè)整數(shù)，代表一共有六個(gè)工序。1、2、3分別出現(xiàn)了兩次，這代表工件1、2、3分別有兩項(xiàng)工序。第一個(gè)整數(shù)2 代表這次加工工序O21，第二個(gè)整數(shù)1 代表這次加工工序O11，第三個(gè)整數(shù)2代表這次加工工序O22，以此類推。

將兩個(gè)階段得到的機(jī)器編碼解和工序編碼解結(jié)合起來考慮會得到，先是在機(jī)器M2上加工工序O21，然后，在機(jī)器M5上加工工序O11，接著在機(jī)器M1上加工工序O22，以此類推。從而，整數(shù)串（3 3 2 1 3 1 2 1 2 3 1 3）代表了一個(gè)個(gè)體。

1.3.2 解碼

為了獲得最終可行的解決方案，需要對編碼的個(gè)體進(jìn)行解碼。文獻(xiàn)[5]提出的解碼算法被用于從個(gè)體中獲得解決方案。還以表1 的FJSP 為例，考慮個(gè)體（3 3 2 1 3 1 2 1 2 3 1 3），可以得到的解為一個(gè)矩陣M′=[2 1 2 3 0 0；1 1 5 2 0 0；2 2 1 1 0 0；3 1 5 3 0 0；1 2 6 1 0 0；3 2 1 1 0 0]。第一個(gè)整數(shù)表示工件號，第二個(gè)整數(shù)表示該工件的工序號，第三個(gè)整數(shù)表示加工該工序的機(jī)器號，第四個(gè)整數(shù)表示在該機(jī)器上的加工開始時(shí)間，第五個(gè)整數(shù)表示在該機(jī)器上的加工結(jié)束時(shí)間。例如（2 1 2 3 0 0）就表示的是第二個(gè)工件的第一個(gè)工序由第二臺機(jī)器M2加工，加工時(shí)間為P212=3。但開始和結(jié)束時(shí)間未知（用0表示），以此類推。

開始和結(jié)束時(shí)間初始化都為0。用Bijk表示工序Oij的加工開始時(shí)間，F(xiàn)ijk表示工序Oij的加工結(jié)束時(shí)間，加工結(jié)束時(shí)間等于加工開始時(shí)間加上加工時(shí)間。分為四種情況討論，如表2所示。所有情況要保證考慮到了所有M′行。

表2 一個(gè)FJSP例子

1.3.3 交叉

交叉和編碼一樣分為兩個(gè)階段，第一個(gè)階段為機(jī)器交叉，第二個(gè)階段為工序交叉。在機(jī)器交叉階段，隨機(jī)生成兩個(gè)小于工序總數(shù)的整數(shù)，以這兩個(gè)隨機(jī)整數(shù)為節(jié)點(diǎn)實(shí)現(xiàn)兩點(diǎn)交叉，如圖4（a）。在工序交叉階段，如文獻(xiàn)[5]所描述，隨機(jī)選擇兩個(gè)個(gè)體（父代1和父代2），所有工序被隨機(jī)分成兩組（第一組和第二組），那么子代1和子代2分別繼承父代1和父代2的屬于組1和組2的整數(shù)，同時(shí)保留這些整數(shù)的位置，子代1 和子代2 分別繼承父代2和父代1 的不屬于組1 和組2 的整數(shù)，并保留這些整數(shù)的序列，如圖4（b）。

圖4 交叉運(yùn)算

1.3.4 變異

變異保持了個(gè)體的多樣性，是MGA-CNS的主要算子之一。變異也分為兩個(gè)階段。第一個(gè)階段是機(jī)器變異階段，第二個(gè)階段是工序變異階段。在機(jī)器變異階段，根據(jù)變異概率隨機(jī)選擇幾個(gè)個(gè)體，然后在選中的每個(gè)個(gè)體中再隨機(jī)選擇幾個(gè)位置，用幾個(gè)小于機(jī)器總數(shù)的整數(shù)來替換這幾個(gè)位置上的整數(shù)。在工序變異階段，也是根據(jù)變異概率隨機(jī)選擇幾個(gè)個(gè)體，隨機(jī)產(chǎn)生兩個(gè)小于工序總數(shù)的整數(shù)，這兩個(gè)整數(shù)代表了被選中個(gè)體上的兩個(gè)位置數(shù)，同時(shí)代替被選中個(gè)體這兩個(gè)位置上的整數(shù)。

1.4 評價(jià)指標(biāo)

標(biāo)準(zhǔn)GA 按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前種群中每個(gè)個(gè)體能遺傳到下一代種群中的機(jī)會多少。在MGA-CNS 中，除了考慮個(gè)體適應(yīng)度以外，還要考慮子群的適應(yīng)度。正如文獻(xiàn)[7]所描述的，MGA 的本質(zhì)是一種隨機(jī)搜索算法，具有一些控制條件，算法的個(gè)體總數(shù)(TIN) 越大，算法的性能應(yīng)該越好。因?yàn)?，?dāng)TIN 越大時(shí)，算法搜索的次數(shù)就越多，就應(yīng)該能找到更優(yōu)的解。MGA-CNS的TIN 計(jì)算公式如下：

S 代表子群大小，N 代表子群數(shù)，TG 代表相應(yīng)MGACNS 的總代數(shù)。當(dāng)某一變量改變時(shí)，TIN 會有很大的不同。例如，有A和B兩個(gè)MGA-CNS，A和B的TG 都為100，但是它們的S 和N 不同，A的S 和N 為40，40，B的S 和N 為400，400，那么A和B的TIN 分別為160 000和16 000 000。理論上說，B能找到更優(yōu)的解，但如果它們找到相同的解，則A 要好得多，因?yàn)樗业酵瑯觾?yōu)的解所用的搜索次數(shù)更少。

如文獻(xiàn)[5]中所述，他們在解決FJSP時(shí)，采用的最大的TIN 是100萬。為了使子群擁有更多交流機(jī)會，本文采用的最大的TIN 為200 萬。如前所述，F(xiàn)JSP 的目標(biāo)是盡量縮短最大完工時(shí)間。因此，使用基于TIN 的最大完工時(shí)間來評估MGA-CNS的性能，其中較小的最大完工時(shí)間表示較好的MGA-CNS。每個(gè)算法獨(dú)立運(yùn)行Nt次，得到的最大完工時(shí)間的平均值稱為平均最優(yōu)值，用于評估MGA-CNS的性能。并且，還通過計(jì)算成功率(SR)來評價(jià)MGA-CNS 的優(yōu)劣，成功率越高，則表示算法越好。成功率的計(jì)算公式如下：

這里的Ns表示式中所用算法在Nt次運(yùn)行中能夠找到所解決的FJSP的最優(yōu)解的次數(shù)。

2 仿真研究

2.1 實(shí)驗(yàn)設(shè)置

使用一個(gè)10×10FJSP 實(shí)例[7]來測試MGA-CNS，研究所使用網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)是怎樣影響MGA-CNS 的性能。分別進(jìn)行以下幾個(gè)實(shí)驗(yàn)：

實(shí)驗(yàn)1 子群大小S 對MGA-CNS性能的影響；

實(shí)驗(yàn)2 子群數(shù)N 對MGA-CNS性能的影響；

實(shí)驗(yàn)3 可控參數(shù)α 對MGA-CNS性能的影響；

實(shí)驗(yàn)4 可控參數(shù)β 對MGA-CNS性能的影響；

實(shí)驗(yàn)5 初始網(wǎng)絡(luò)規(guī)模m0對MGA-CNS性能的影響。

為了保證實(shí)驗(yàn)的準(zhǔn)確性，在分別測試網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)S、N、α、β 和m0對MGA-CNS的影響時(shí)，除了被測參數(shù)按規(guī)則變化外，其余參數(shù)均保持不變。

2.2 子群大小S 對MGA-CNS性能的影響

研究子群大小S 對MGA-CNS 性能的影響。相關(guān)參數(shù)的設(shè)置如下：Pr=0.08,N=100,TIN=2 000 000，α=1,β=1,m0=2,S 以20 為步長從10 變化到200，Nt=20。圖5 給出了平均最優(yōu)值和成功率隨S 的變化情況。

如圖5 所示，當(dāng)S=20 時(shí)，MGA-CNS 的性能較差，平均最優(yōu)值為8.9，成功率為40%。隨著子群大小的擴(kuò)大，MGA-CNS 的性能變好。當(dāng)S=60 時(shí)，平均最優(yōu)值為7.5，成功率為50%。當(dāng)子群大小在60 到100 之間擴(kuò)大時(shí)，MGA-CNS 性能逐漸變差。當(dāng)S=100 時(shí)，平均最優(yōu)值為7.7，成功率為30%。當(dāng)子群大小大于100 時(shí)，隨著子群大小的擴(kuò)大，平均最優(yōu)值減小，成功率增加。因此，子群大小最好大于100，并且子群越大，MGA-CNS性能越好。

圖5 平均最優(yōu)值和成功率隨子群大小的變化情況

2.3 子群數(shù)N 對MGA-CNS性能的影響

研究子群數(shù)N 對MGA-CNS 性能的影響。相關(guān)參數(shù)的設(shè)置如下：Pr=0.08,S=40,TIN=2 000 000,α=1,β=1,m0=2,N 以10 為步長從10 變化到200，Nt=20。圖6給出了平均最優(yōu)值和成功率隨N 的變化情況。

圖6 平均最優(yōu)值和成功率隨子群數(shù)的變化情況

如圖6所示，當(dāng)N=10 時(shí)，平均最優(yōu)值為8.95，成功率為45%，MGA-CNS 的性能較差。隨著N 的增加，MGA-CNS的性能變好。當(dāng)N=70 時(shí)，平均最優(yōu)值為8.1，成功率為90%。隨著N 的進(jìn)一步增大，平均最優(yōu)值逐漸減小，但是成功率也逐漸降低。因此，為了使MGA-CNS的性能較好，N 不能取值過小，更不能取值過大。

2.4 參數(shù)α 對MGA-CNS性能的影響

研究可控參數(shù)α 對MGA-CNS 性能的影響。相關(guān)參數(shù)的設(shè)置如下所示：Pr=0.08,S=40,N=100,TIN=2 000 000,β=1,m0=2,α 從0.1變化到20，當(dāng)從0.1變化到1時(shí)，步長為0.1，當(dāng)從1變化到20時(shí)，步長為2，Nt=20。如文獻(xiàn)[29]所述，通過調(diào)整α 的值可以生成不同標(biāo)度指數(shù)的網(wǎng)絡(luò)。當(dāng)α 從0 變化到1 時(shí)，標(biāo)度指數(shù)從無窮大趨近于3，由于0 到1 的區(qū)間較小，因此以0.1 為步長；當(dāng)α大于1 時(shí)，標(biāo)度指數(shù)小于3，此時(shí)α 可調(diào)區(qū)間較大，因此以2為步長。圖7給出了平均最優(yōu)值和成功率隨α 的變化情況。

圖7 平均最優(yōu)值和成功率隨α 的變化情況

在圖7 中，當(dāng)α=0.1 時(shí)，平均最優(yōu)值為7.75，成功率為35%，MGA-CNS 的性能較好。當(dāng)α 大于0.3 時(shí)，平均最優(yōu)值顯著上升，而成功率顯著下降，這說明MGA-CNS的性能也顯著下降。隨著α 的增加，平均最優(yōu)值總體呈上升趨勢，而成功率總體呈下降趨勢（不考慮α=7 時(shí)的異常，見圖7（b）中標(biāo)注點(diǎn)）。這意味著，當(dāng)α 較大時(shí)，MGA-CNS的性能反而會降低。當(dāng)α=0.2 時(shí)，MGA-CNS的性能達(dá)到最優(yōu)，平均最優(yōu)值為7.65，成功率為40%，但α 在區(qū)間[0.1，0.3]變化時(shí)，算法性能波動(dòng)不大，α=0.2 的左右兩個(gè)區(qū)間表現(xiàn)相同的趨勢，都具有較好的性能。因此，為了獲得更好的MGA-CNS，α 不能太大，更具體地說，當(dāng)α 的值不大于0.3時(shí)，MGA-CNS的性能更好。

2.5 參數(shù)β 對MGA-CNS性能的影響

研究可控參數(shù)β 對MGA-CNS 性能的影響。相關(guān)參數(shù)如下：Pr=0.08,S=40,N=100,TIN=2 000 000,α=1,m0=2,β 從0.2變化到3，步長為0.2，Nt=20。圖8給出了平均最優(yōu)值和成功率隨β 的變化情況。

在圖8 中，當(dāng)β=0.2 時(shí)，平均最優(yōu)值為7.7，成功率為35%，此時(shí)，MGA-CNS的性能最優(yōu)。隨著β 的增加，平均最優(yōu)值總體呈上升趨勢，它先隨著β 的增加而增加，當(dāng)β 在2.2和2.8之間擴(kuò)大時(shí)，平均最優(yōu)值隨之減小，之后，平均最優(yōu)值又隨著β 的增加而增加。與平均最優(yōu)值相反，成功率呈下降趨勢，特別是，當(dāng)β 大于0.8 時(shí)（圖8中圓圈標(biāo)注點(diǎn)），成功率顯著下降，當(dāng)β 大于1時(shí)，成功率的波動(dòng)較小，基本趨于穩(wěn)定（不考慮β=3 和3.2時(shí)的異常，見圖8 中矩形標(biāo)注點(diǎn)）。這意味著，MGACNS 的性能先隨著β 的增加而下降，然后隨著β 的增加而增加，再隨之下降，總體呈下降趨勢。根據(jù)平均最優(yōu)值和成功率的變化可看出，β 在區(qū)間[0.2，0.8]變化時(shí)，MGA-CNS 可獲得較好的性能，且越往后，MGACNS的性能越差。因此，為了獲得更好的MGA-CNS，β的取值不能太大，更具體地說，當(dāng)β 的值不大于0.8時(shí)可以得到較好的MGA-CNS。

圖8 平均最優(yōu)值和成功率隨β 的變化情況

2.6 初始網(wǎng)絡(luò)規(guī)模m0 對MGA-CNS性能的影響

研究初始網(wǎng)絡(luò)規(guī)模m0對MGA-CNS 性能的影響。相關(guān)參數(shù)的設(shè)置如下：Pr=0.08,S=40,N=100,TIN=2 000 000,α=1,β=1,m0從2變化到10，步長為1，Nt=20。圖9給出了平均最優(yōu)值和成功率隨m0的變化情況。

圖9 平均最優(yōu)值和成功率隨初始網(wǎng)絡(luò)規(guī)模的變化情況

如圖9 所示，隨著m0的增加，平均最優(yōu)值在7.9 和8.2 之間波動(dòng)，成功率在5%和20%之間波動(dòng)。當(dāng)m0=4時(shí)，平均最優(yōu)值取得最小值為7.9，成功率取得最大值為20%，此時(shí)，MGA-CNS 的性能較好。仔細(xì)觀察可以發(fā)現(xiàn)，雖然平均最優(yōu)值一直在上下波動(dòng)，但總體呈上升趨勢，而成功率波動(dòng)較小，基本趨于穩(wěn)定。這意味著，MGA-CNS 的性能隨著m0的增加而下降。因此，為了獲得更好的MGA-CNS，m0的取值不能太大，當(dāng)m0不大于4時(shí)可以得到較好的MGA-CNS。

2.7 MGA-CNS求解FJSP的有效性

以文獻(xiàn)[33]提到的18個(gè)FJSP實(shí)例為例，驗(yàn)證MGACNS 的有效性。通過前文的研究，確定相關(guān)參數(shù)：Pr=0.08,S=200,N=70,TIN=2 000 000,α=0.2,β=0.2,m0=4,Nt=20。表3給出了用MGA-CNS求解文獻(xiàn)[33]提到的18個(gè)FJSP實(shí)例與文獻(xiàn)[34-37]所提算法求解的比較結(jié)果。圖10給出了求解MFJS08得到的甘特圖。

圖10 MFJS08實(shí)例的甘特圖

表3中，文獻(xiàn)[34]有AIS和HHS兩種算法，符號“—”表示原文沒有給出相應(yīng)數(shù)據(jù)。用MGA-CNS 求解MFJS02 時(shí)最優(yōu)值為446，比文獻(xiàn)[34]的448 更優(yōu)；求解MFJS05 時(shí)最優(yōu)值為514，比文獻(xiàn)[34]的527 更優(yōu)；求解MFJS06 時(shí)最優(yōu)值為634，比文獻(xiàn)[34]的635 更優(yōu)；求解MFJS04 時(shí)最優(yōu)值為554，比文獻(xiàn)[35]的564 更優(yōu)；求解MFJS07時(shí)最優(yōu)值為881，比文獻(xiàn)[35]的928更優(yōu)；說明了MGA-CNS的有效性。

2.8 結(jié)果分析

標(biāo)準(zhǔn)GA 有一個(gè)非常明顯的缺點(diǎn)，就是過早收斂。GA 靠交叉算子把父代的優(yōu)勢基因遺傳給子代，使優(yōu)勢基因很快就積累起來，而很少破壞它們，這導(dǎo)致GA 可以非常快速地獲得局部最優(yōu)值。在之前的很多文獻(xiàn)中都提出了很多解決這個(gè)問題的辦法，而本文提到的MGA-CNS也同樣是為了解決GA過早收斂的問題。當(dāng)MGA-CNS的不同子群彼此交流時(shí)，優(yōu)勢基因不僅能夠在子群內(nèi)進(jìn)行傳播，而且還能在子群之間進(jìn)行傳播。子群之間優(yōu)勢基因的傳播主要受其網(wǎng)絡(luò)結(jié)構(gòu)控制，已有研究表明，網(wǎng)絡(luò)平均路徑長度越小，優(yōu)勢基因傳播速率越高[29]。本文研究了五個(gè)網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)（S、N、α、β 和m0）分別在其余參數(shù)都不改變的情況下對MGA-CNS的影響。

如2.2 節(jié)所述，在一定的TIN 下，隨著S 的增大，MGA-CNS 的性能先逐漸提高，然后逐漸降低，當(dāng)S 大于100后，MGA-CNS的性能又逐漸提高。S 越大，平均最優(yōu)值越小，成功率越高，此時(shí)更容易得到最優(yōu)解，MGA-CNS 的性能就越好。因?yàn)?，?dāng)S 很小時(shí)，子群中個(gè)體的數(shù)量較少，此時(shí)基因池較單一，存在多樣性不足的問題，容易早熟收斂，所以此時(shí)的算法性能較差；而隨著S 的增加，子群中的個(gè)體數(shù)量增加，子群中的多樣性得到了保持，所以算法性能越來越好。

表3 比較結(jié)果

如2.3 節(jié)所述，在一定的TIN 下，隨著N 的增大，MGA-CNS 的性能先逐漸提高，隨后又逐漸降低，為了使MGA-CNS的性能較好，N 不能取值過小，更不能取值過大。這是因?yàn)?，?dāng)N 值很小時(shí)，子群個(gè)數(shù)過少，不利于子群之間的交流，但是又因?yàn)槊總€(gè)子群的規(guī)模適當(dāng)，所以MGA-CNS的性能不會太差。隨著N 的增大，子群個(gè)數(shù)變多，更有利于保持種群多樣性，所以MGACNS的性能逐漸變好，但是當(dāng)N 進(jìn)一步增大時(shí)，一次迭代所用的個(gè)體數(shù)很多，又因N 是一個(gè)定值，所以總的迭代次數(shù)很少，個(gè)體來不及積累優(yōu)勢基因，MGA-CNS 的性能也就變差。因此，可以得出如文獻(xiàn)[38]所述的結(jié)論：在一定的總個(gè)體數(shù)下，多代尋優(yōu)是合理的策略。

如2.4 節(jié)所述，在一定的TIN 下，隨著α 的增大，MGA-CNS 的性能逐漸降低。因此，為了獲得更好的MGA-CNS，α 的取值不能太大，更具體地說，當(dāng)α 的值不大于0.3時(shí)，MGA-CNS的性能更好。因?yàn)?，?dāng)α 較小時(shí)，網(wǎng)絡(luò)中具有更多的高節(jié)點(diǎn)度的節(jié)點(diǎn)，網(wǎng)絡(luò)的連接性更好，網(wǎng)絡(luò)的平均路徑長度較小，從而子群間優(yōu)勢基因的傳播速率較高，更有利于保持種群多樣性且較快地獲得最優(yōu)解，所以α 的取值不能太大。

如2.5 節(jié)所述，在一定的TIN 下，隨著β 的增大，MGA-CNS 的性能先逐漸降低，再逐漸提高，然后又逐漸降低，總體呈下降趨勢。為了獲得更好的MGA-CNS，β 的取值不能太大，當(dāng)β 不大于0.8 時(shí)，MGA-CNS 的性能較好。因?yàn)?，?dāng)β 較大時(shí)，網(wǎng)絡(luò)中會出現(xiàn)一個(gè)凝聚點(diǎn)，這個(gè)節(jié)點(diǎn)幾乎與其他所有節(jié)點(diǎn)連接[32]。此時(shí)，網(wǎng)絡(luò)的平均路徑長度非常小，子群間優(yōu)勢基因傳播速率非常高，MGA-CNS將非?？焖俚孬@得局部最優(yōu)值，從而導(dǎo)致早熟收斂。所以，當(dāng)β 大于0.8時(shí)算法性能會變差。

如2.6 節(jié)所述，在一定的TIN 下，隨著m0的增大，MGA-CNS 的性能逐漸降低。因此，為了獲得更好的MGA-CNS，m0取值不能太大，當(dāng)m0不大于4時(shí)可以得到較好的MGA-CNS。這是因?yàn)?，?dāng)m0越大時(shí)，新引入的節(jié)點(diǎn)與網(wǎng)絡(luò)中具有高節(jié)點(diǎn)度的節(jié)點(diǎn)連接的概率越大，這意味著優(yōu)勢基因?qū)⒑苌賯鞑サ狡渌淖尤?，便無法從其他精英個(gè)體中獲益，所以，m0取值不能太大。

3 總結(jié)

GA 在處理組合優(yōu)化等問題上具有獨(dú)特的優(yōu)勢，但是卻容易出現(xiàn)早熟收斂的問題。為了克服這一缺點(diǎn)，多種群是一種有效的方法。但以往研究中，往往忽略了子群間優(yōu)勢基因的傳播構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)對算法的影響，沒有考慮到某些網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)（S、N、α、β 和m0）對MGA 的影響。因此，本文設(shè)計(jì)了一種含復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的多種群遺傳算法（MGA-CNS）來對這五個(gè)參數(shù)對算法性能的影響規(guī)律進(jìn)行研究。

仿真結(jié)果表明，子群大小S 的取值最好大于100，并且S 越大，MGA-CNS的性能越好；為了使MGA-CNS的性能較好，子群數(shù)N 不能取值過小，更不能取值過大；可控參數(shù)α 的值不能太大，更具體地說，當(dāng)α 不大于0.3時(shí)，MGA-CNS的性能更好；可控參數(shù)β 的取值不能太大，當(dāng)β 不大于0.8 時(shí)，可以得到較好的MGA-CNS；為了獲得更好的MGA-CNS，初始網(wǎng)絡(luò)規(guī)模m0的取值也不能太大，當(dāng)m0不大于4時(shí)，MGA-CNS的性能更好。

本文研究了用MGA-CNS 解決組合優(yōu)化問題時(shí)不同網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)對算法的影響，但是在優(yōu)化問題中還有連續(xù)優(yōu)化問題。另外，多種群能夠改善GA 的性能，而入侵雜草優(yōu)化算法（Invasive Weed Optimization，IWO）[39]的改善不能僅靠多種群[5]，所以在今后的研究中會對連續(xù)優(yōu)化問題和IWO的性能改善進(jìn)行進(jìn)一步的研究。