周艷平,王功明

（青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,青島 266061）

遺傳算法（Genetic Algorithm,GA）是進化算法中產(chǎn)生最早、影響最大、應(yīng)用最為廣泛的一種群智能優(yōu)化算法[1].但遺傳算法在理論和應(yīng)用方面還有很多不足,如收斂速度慢,容易陷入局部最優(yōu)等問題.

Ehrlich和Rave在研究植物和植食性動物的關(guān)系時提出了協(xié)同進化這一概念,近年來這一概念已經(jīng)成為計算智能領(lǐng)域的一個研究熱點[2].由于協(xié)同進化的搜索能力強,越來越多的優(yōu)化算法采取了協(xié)同進化方式[3-5].協(xié)同進化研究的應(yīng)用領(lǐng)域也在不斷擴展,在車間調(diào)度[6]、電力調(diào)度[7]、機器人路徑規(guī)劃[8]、交通規(guī)劃[9]等領(lǐng)域都得到了成功應(yīng)用.

生產(chǎn)調(diào)度通過對生產(chǎn)資源的合理安排,以縮短生產(chǎn)時間和成本,使資源能夠得到更有效的利用,在生產(chǎn)系統(tǒng)中扮演重要的角色.其應(yīng)用領(lǐng)域十分廣泛,涵蓋工業(yè)、商業(yè)等方方面面.按主流的分類方法,生產(chǎn)調(diào)度可分為單機調(diào)度、并行機調(diào)度、流水車間調(diào)度、作業(yè)車間調(diào)度等.其中流水車間調(diào)度模型作為典型生產(chǎn)調(diào)度模型之一,是一個NP-hard問題[10].該問題主要是安排待加工工件在加工機器上的加工順序,最終求解得到的是一個最符合要求的工件加工順序.流水車間調(diào)度問題有很多的求解方法,其中包括精確方法、構(gòu)造型方法、改進型方法等.精確方法計算量較大,一般適用于小規(guī)模問題.構(gòu)造型方法通過一定的規(guī)則來構(gòu)造問題的解,能夠快速構(gòu)造解,但是解的質(zhì)量較差.改進型算法從若干解出發(fā),通過對其鄰域不斷搜索和當(dāng)前解的替換來改進解的質(zhì)量,是解決流水車間調(diào)度問題的主要研究方向,如遺傳算法、協(xié)同進化算法等.作為車間調(diào)度的典型問題,流水車間調(diào)度問題得到了廣泛研究和應(yīng)用[11].

本文在遺傳算法和協(xié)同進化框架的基礎(chǔ)上,提出了一種自適應(yīng)協(xié)同進化遺傳算法（Adaptive Co-evolutionary Genetic Algorithm,ACGA）.與傳統(tǒng)算法相比,該算法通過兩個中間組的進化實現(xiàn)了優(yōu)質(zhì)解組和劣質(zhì)解組個體信息的交互,兼顧了種群內(nèi)的自我進化和種群間的共同優(yōu)化; 同時引入了自適應(yīng)策略,根據(jù)個體的進化情況采用了自適應(yīng)變異因子及自適應(yīng)災(zāi)變幾率策略.通過函數(shù)優(yōu)化實驗驗證了ACGA算法在求解簡單問題方面的有效性.接著描述了流水車間調(diào)度模型,并且使用ACGA算法求解流水車間調(diào)度問題,通過與其他相關(guān)算法對該問題求解的對比實驗,驗證了ACGA算法求解流水車間調(diào)度問題的有效性.

1 協(xié)同進化遺傳算法及函數(shù)優(yōu)化測試

1.1 自適應(yīng)協(xié)同進化遺傳算法

協(xié)同進化遺傳算法的實質(zhì)是對遺傳算法采用協(xié)同進化的方式進行優(yōu)化.遺傳算法的操作算子包括選擇、交叉和變異3種基本形式,構(gòu)成了遺傳算法強大搜索能力的核心,是模擬自然選擇和遺傳過程中發(fā)生的繁殖、雜交和突變現(xiàn)象的主要載體[12].選擇因子是按照一定的規(guī)則選擇出更加符合要求的多個個體組成一個新的種群,常見的方法包括輪盤賭算法、最佳保留策略等.交叉因子是兩個個體互相交換部分染色體,最終得到兩個新個體,常見的方法有單點交叉和多點交叉等.變異是對單個個體的染色體按照一定的規(guī)則進行變更,最終得到一個新個體,常見方法有單點變異和多點變異等.其中交叉和變異操作會導(dǎo)致原個體部分染色體發(fā)生改變,可能產(chǎn)生沖突,需要進行沖突檢測.協(xié)同進化遺傳算法相比遺傳算法在一定程度上增強了優(yōu)化的效果,但仍存在搜索速度慢、經(jīng)常找不到全局最優(yōu)解的問題.

ACGA算法結(jié)合了遺傳算法和協(xié)同進化算法,在此基礎(chǔ)上引入自適應(yīng)變異因子以及災(zāi)變機制達到自適應(yīng)的目的,算法流程圖如圖1所示.

圖1 ACGA算法流程圖

首先針對收斂速度過慢的問題,ACGA算法采取操作協(xié)同.對原始種群根據(jù)適應(yīng)度值進行分組,考慮不同組內(nèi)各個個體的優(yōu)良情況以及個體差異情況,優(yōu)質(zhì)解組采用多點交叉和單點變異,盡可能的保持更多優(yōu)良個體; 劣質(zhì)解組采用多點交叉搭配多點變異,產(chǎn)生更多新個體; 中間組采用單點交叉配合多點變異,完成組與組之間的交叉和變異操作.

針對容易陷入局部最優(yōu)的問題.在傳統(tǒng)算法中,變異率通常采取固定數(shù)值.但變異率對于種群優(yōu)化起著重要作用,不同階段甚至于不同種群都需要合適的變異率,變異率較大時,容易產(chǎn)生新個體,跳出局部最優(yōu);變異率較小時容易保留較優(yōu)個體.局部最優(yōu)問題正是由于進化到后期時,變異率較低,無法產(chǎn)生新個體,使得種群內(nèi)個體的多樣性不足.為解決這個問題,考慮采用自適應(yīng)變異率來動態(tài)確定[13],隨著迭代次數(shù)的增加,變異率也在動態(tài)改變,來適應(yīng)種群的進化.本文根據(jù)種群的要求提出了一種自適應(yīng)變異因子:

其中,F0為變異因子,Gm為最大進化代數(shù),為當(dāng)前進化代數(shù).

在進化初期時,λ趨于0,此時變異因子趨近F0,種群按照正常的變異率進行種群的進化.當(dāng)進化到后期時,當(dāng)前迭代次數(shù)無限接近于最大迭代次數(shù),此時λ趨于1,變異因子趨近于2F0,變異率增大到原來的2倍.變異率的增加也意味著可以產(chǎn)生更多的新個體以此來增強種群的多樣性,而陷入局部最優(yōu)正是由于種群內(nèi)個體的多樣性不足造成的.由此可見,該變異因子對于緩解局部最優(yōu)問題起到了一定的效果.

但僅僅通過調(diào)整變異率來增強種群多樣性的效果是十分有限的.當(dāng)初始變異率F0較低時,2F0雖然一定程度上有了提高,但程度還不夠;初始變異率F0較高時,2F0可能會過大,導(dǎo)致搜索變?yōu)殡S機搜索,這樣就不能起到逐代進化的作用.為應(yīng)對以上情況,本文在引入自適應(yīng)變異因子的同時引入了災(zāi)變機制來進行改善.災(zāi)變是生物進化中十分重要的現(xiàn)象,每一次災(zāi)變的過程都是生物進化過程中的一個巨大的飛躍,不僅打破了舊基因的壟斷,增加了生物的多樣性,同時破壞性的改變并沒有消滅之前進化的成果,反而是在已有的基礎(chǔ)上大大提高了進化程度[14].傳統(tǒng)災(zāi)變只再次生產(chǎn)新的個體,并未考慮迭代的次數(shù)、個體的優(yōu)良情況.在進化的前期,迭代次數(shù)較小,此時需要較大的災(zāi)變幾率來增強種群多樣性;當(dāng)進化到后期,種群中的個體較優(yōu),如果災(zāi)變幾率過大容易喪失種群進化的成果.因此災(zāi)變幾率最好動態(tài)適應(yīng)進化的過程.同時,傳統(tǒng)災(zāi)變并未考慮個體的優(yōu)良情況,導(dǎo)致優(yōu)秀個體和較差個體同樣進行災(zāi)變,破壞了種群的優(yōu)良基因.因此需要對兩種個體分別處理,優(yōu)秀個體應(yīng)保持較小的災(zāi)變幾率,保留優(yōu)良信息,較差個體保持較大災(zāi)變幾率,產(chǎn)生新個體增加多樣性.為實現(xiàn)上面兩種情況,本文采用了葉彥斐等人[15]提出的一種動態(tài)自適應(yīng)概率來替換種群中的個體,公式如下:

其中,i為當(dāng)前進化代數(shù);N為最大進化代數(shù);Pz為災(zāi)變概率;kz為常數(shù);tmax為當(dāng)前種群最大適應(yīng)度值;ta為當(dāng)前種群平均適應(yīng)度值;tz為災(zāi)變個體適應(yīng)度值.

如式（2）、式（3）所示,首先該自適應(yīng)概率考慮到了迭代次數(shù)的影響,隨著迭代次數(shù)的增大,u逐漸由0增大到π/2,相應(yīng)的余弦函數(shù)從1到0,使得概率隨迭代次數(shù)的增大而逐漸減小,防止后期災(zāi)變幾率過大,破壞優(yōu)良個體.其次,式（3）考慮到個體的優(yōu)良情況,當(dāng)個體適應(yīng)度低于平均值,說明個體較差,此時采取固定的較高災(zāi)變幾率產(chǎn)生新個體,反之,優(yōu)良個體采取了較小的動態(tài)災(zāi)變幾率,防止優(yōu)良基因被破壞.同時加入精英保留策略,保證種群中的最優(yōu)個體不會被消滅,指引種群向正確的方向進化.

災(zāi)變機制的觸發(fā)條件也格外重要,本文的災(zāi)變觸發(fā)條件設(shè)置為全局最優(yōu)值連續(xù)3次相同,只有在這種情況下才觸發(fā)災(zāi)變機制,否則只采用自適應(yīng)變異因子.

ACGA算法的步驟如下:

1）初始化進化參數(shù),包括最大迭代次數(shù),種群規(guī)模以及3種因子的具體實現(xiàn)形式;

2）隨機生成一個初始種群,計算種群中個體的適應(yīng)度值;

3）對種群內(nèi)的個體根據(jù)適應(yīng)度值由小到大進行排序,取適應(yīng)度值較小那部分的前2/3個體組成優(yōu)質(zhì)解組,取適應(yīng)度值較大部分的前2/3個體組成劣質(zhì)解組,將兩部分剩下的1/3部分合并成一個組,命名為中間組;

4）對優(yōu)質(zhì)解組采用單點交叉以及單點變異,交叉概率設(shè)為0.8,變異概率設(shè)為0.03,盡可能的保留優(yōu)質(zhì)個體; 對劣質(zhì)解組采用單點交叉以及多點變異,交叉概率設(shè)為0.95,變異概率設(shè)為0.1,盡可能的產(chǎn)生更多新的個體; 對中間組采用多點交叉以及單點變異,交叉概率設(shè)為0.9,變異概率設(shè)為0.07;

5）交叉變異之后得到一個臨時種群,計算臨時種群中各個個體的適應(yīng)度值,當(dāng)臨時種群中相對應(yīng)個體的適應(yīng)度值小于當(dāng)前種群中的個體時,就使用臨時種群中的這個個體更新當(dāng)前種群,否則將保持當(dāng)前種群中的個體;

6）計算最優(yōu)解連續(xù)相同的次數(shù),若次數(shù)小于3,則根據(jù)式（1）計算當(dāng)前的變異因子; 若次數(shù)大于等于3次時,根據(jù)災(zāi)變機制進行災(zāi)變;

7）判斷是否滿足終止迭代條件,若是,輸出全局最優(yōu)解以及最優(yōu)個體; 若否,返回步驟3）繼續(xù)進行迭代進化.

1.2 函數(shù)優(yōu)化測試

為了檢驗ACGA算法在優(yōu)化求解方面的性能,將該算法與GA算法進行了對比,分別采用ACGA算法和GA算法對以下函數(shù)進行求解.

該目標(biāo)函數(shù)是傳統(tǒng)的多峰函數(shù),在N維可行域中有2N?1局部最優(yōu)解,其中極小值為0.為了保證實驗結(jié)果的準(zhǔn)確性,2種算法相同參數(shù)的數(shù)值必須保證一致,包括初始化方法為隨機初始化,迭代次數(shù)為100,種群規(guī)模為90,維度為30等.2種算法的性能對比圖如圖2所示.

圖2 ACGA算法和GA算法的性能比較

從圖2可以看出,在迭代次數(shù)相同的情況下ACGA算法的求解結(jié)果優(yōu)于GA算法,更加接近全局最優(yōu)解;在求解結(jié)果相同的情況下,ACGA算法的迭代次數(shù)也明顯小于GA算法的迭代次數(shù).ACGA算法無論在收斂速度還是在求解精度上的表現(xiàn)都要優(yōu)于GA算法,展現(xiàn)了ACGA算法的優(yōu)良性能.

2 ACGA算法求解流水車間調(diào)度問題

2.1 流水車間調(diào)度問題模型

流水車間調(diào)度問題主要是研究n個工件在m臺機器上進行流水加工,作為最簡單的車間調(diào)度模型,該模型要求每個工件都有m道工序,同時每臺機器只能加工一道工序,這就意味著每個工件都要經(jīng)過m臺機器的加工; 每個工件在各個機器上的加工順序相同,各個工件在各機器上的加工時間和準(zhǔn)備時間已知,優(yōu)化目標(biāo)為最小化最大完工時間.

令Tik表示工件i在機器k上的完工時間,tik表示工件i在機器k上的加工時間,且tik>0,i,j=1,2,…,n,k=1,2,…,m.該流水車間調(diào)度問題的目標(biāo)函數(shù)[16]為:

2.2 求解步驟

1）初始化算法求解參數(shù),如種群規(guī)模、迭代次數(shù)、3種因子的具體實現(xiàn)形式;

2）根據(jù)流水車間調(diào)度問題,采用特定的編碼以及解碼方式隨機生成一個可以進化的初始種群,根據(jù)問題模型計算種群內(nèi)各個個體的適應(yīng)度值;

3）根據(jù)適應(yīng)度值由低到高對種群內(nèi)的個體進行排序,將種群平均分成兩部分,并且從兩部分中各取該部分適應(yīng)度值較高的1/3個體組成一個中間組,用來進行種群間的交叉變異,同時將剩下的兩部分中適應(yīng)度值較低種群的取為優(yōu)質(zhì)解組,適應(yīng)度值較高的種群取為劣質(zhì)解組;

4）根據(jù)不同組的個體特點采取不同的操作,優(yōu)質(zhì)解組采用多點交叉以及單點變異; 劣質(zhì)解組采用多點交叉和多點變異; 中間組采用單點交叉和多點變異; 變異因子選取自適應(yīng)變異因子;

5）操作后得到臨時一個種群,計算該種群中各個個體的適應(yīng)度值,并根據(jù)適應(yīng)度值使用臨時種群對原種群進行更新操作;

6）計算全局最優(yōu)解連續(xù)相同的次數(shù),若次數(shù)少于3次,根據(jù)式（1）計算自適應(yīng)變異率,并更新之前的變異率; 若次數(shù)不少于3次,計算種群的平均適應(yīng)度,根據(jù)式（2）和式（3）分情況計算除最優(yōu)個體之外的每個個體的災(zāi)變幾率,將需要災(zāi)變的個體根據(jù)編碼方式隨機初始化,使用災(zāi)變最新產(chǎn)生的個體貪婪替換原個體;

7）判斷是否滿足終止條件,若是,則將得到的全局最優(yōu)解進行解碼,生成最優(yōu)的調(diào)度方案; 若否,則返回步驟3,繼續(xù)進行.

2.3 仿真實驗

2.3.1 實驗準(zhǔn)備

程序運行平臺為Windows 10操作系統(tǒng)下的Matlab軟件.輸入的種群規(guī)模為90,最大迭代次數(shù)為800,初始災(zāi)變概率kz為0.2.優(yōu)質(zhì)解組的交叉概率為0.8初始變異概率為0.03; 劣質(zhì)解組的交叉概率為0.95,初始變異概率為0.1; 中間組的交叉概率為0.9,初始變異概率為0.07.編碼采取隨機初始化方法.數(shù)據(jù)集選擇TA類[17]車間調(diào)度問題,該數(shù)據(jù)集是由Taillard等給出,包括了12個不同規(guī)模的120個典型問題,本次實驗選取3種規(guī)模的數(shù)據(jù)集,分別為20×5、50×5以及100×5,在每種規(guī)模的數(shù)據(jù)集下選取一個典型問題,通過這3個規(guī)模數(shù)據(jù)集下的3個典型問題來驗證算法.

2.3.2 實驗結(jié)果與分析

分別采用ACGA算法、MDE算法[13]以及GA算法對上述3種規(guī)模的數(shù)據(jù)集進行流水車間調(diào)度問題的求解,以最小化最大完工時間為優(yōu)化目標(biāo).在實驗過程中,為使結(jié)果更加精準(zhǔn),避免實驗偶然性,每種算法在每個數(shù)據(jù)集分別運行10次.實驗結(jié)果的參考指標(biāo)主要為10次結(jié)果的平均值以及10次結(jié)果的方差,均值和方差越小越好.均值越小,說明算法優(yōu)化的精度越高;方差越小說明算法的穩(wěn)定性越高.

仿真結(jié)果如表1所示.首先看10次結(jié)果的平均值,在同等規(guī)模、相同問題的情況下,ACGA算法在每一種問題上都可以得到比MDE算法和GA算法更小的完工時間,而GA算法和MDE算法相比,GA算法更適合較小規(guī)模,MDE算法更適合較大規(guī)模; 從10次結(jié)果的最優(yōu)值來看,ACGA算法在每種問題下的最優(yōu)值也小于MDE算法GA算法,而MDE算法與GA算法的對比情況與均值類似; 從10次結(jié)果的方差來看,ACGA算法的方差明顯要小于GA算法和MDE算法,MDE算法在小規(guī)模情況下比GA算法穩(wěn)定,較大規(guī)模下的穩(wěn)定性不如GA算法,從這3個指標(biāo)可以看出ACGA算法的求解效果更加穩(wěn)定.由此可以得出結(jié)論,ACGA算法在求解流水車間調(diào)度問題方面與GA算法和MDE算法相比,求解結(jié)果更加精準(zhǔn),求解效果更加穩(wěn)定,精確性和穩(wěn)定性都是最佳的.

表1 3種算法對不同規(guī)模調(diào)度集的仿真結(jié)果

圖3給出了使用ACGA算法對數(shù)據(jù)規(guī)模為20×5進行流水車間調(diào)度得到的甘特圖.

圖3 ACGA算法對規(guī)模為20×5調(diào)度及優(yōu)化的甘特圖

3 結(jié)論與展望

本文提出了自適應(yīng)協(xié)同進化遺傳算法,該算法通過引入自適應(yīng)策略、災(zāi)變機制以及協(xié)同進化思想,適當(dāng)加快收斂速度,提高優(yōu)化效果.通過函數(shù)優(yōu)化實驗,驗證了ACGA算法的可行性和有效性.用ACGA算法求解以最小化最大完工時間為指標(biāo)的流水車間調(diào)度問題,通過與GA算法和MDE算法對比,取得了滿意的調(diào)度效果,具有一定的應(yīng)用價值.接下來的研究工作將著重于研究ACGA算法使用不同變異因子及災(zāi)變因子的優(yōu)化效果,以及ACGA算法在其它車間調(diào)度問題中的應(yīng)用.