周艷平,王功明

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

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

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

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

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

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

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

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

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

圖1 ACGA算法流程圖

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

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

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

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

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

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

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

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

ACGA算法的步驟如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 求解步驟

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

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

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

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

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

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

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

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

2.3.1 實(shí)驗(yàn)準(zhǔn)備

程序運(yùn)行平臺(tái)為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.編碼采取隨機(jī)初始化方法.數(shù)據(jù)集選擇TA類[17]車間調(diào)度問(wèn)題,該數(shù)據(jù)集是由Taillard等給出,包括了12個(gè)不同規(guī)模的120個(gè)典型問(wèn)題,本次實(shí)驗(yàn)選取3種規(guī)模的數(shù)據(jù)集,分別為20×5、50×5以及100×5,在每種規(guī)模的數(shù)據(jù)集下選取一個(gè)典型問(wèn)題,通過(guò)這3個(gè)規(guī)模數(shù)據(jù)集下的3個(gè)典型問(wèn)題來(lái)驗(yàn)證算法.

2.3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

3 結(jié)論與展望

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