基于染色體分化遺傳算法的工業(yè)生產(chǎn)線柔性加工

吳林彥，李艷萍，王 琪，朱 青，馬義飛

（山東建筑大學(xué)，濟(jì)南 250100）

0 引言

隨著科學(xué)技術(shù)的進(jìn)步和計(jì)算機(jī)技術(shù)的發(fā)展，原有的傳統(tǒng)機(jī)械制造方式在計(jì)算機(jī)等輔助工具的幫助下得到了新的發(fā)展，增加了新的內(nèi)涵。由于傳統(tǒng)的機(jī)械制造方式受環(huán)境等不確定因素影響較大，操作人員疲勞、設(shè)備老舊、零部件損壞等問(wèn)題會(huì)嚴(yán)重影響作業(yè)效果。因此計(jì)算機(jī)輔助設(shè)計(jì)（CAD）、計(jì)算機(jī)輔助制造（CAM）、柔性制造系統(tǒng)、計(jì)算機(jī)集成制造系統(tǒng)（CIMS）等新技術(shù)被廣泛應(yīng)用于機(jī)械制造領(lǐng)域。而在工業(yè)生產(chǎn)線的分配布局過(guò)程中，我們必須對(duì)之前所說(shuō)的不確定因素進(jìn)行評(píng)價(jià)并優(yōu)化，以提高生產(chǎn)線的平衡性和魯棒性，而這就是柔性制造系統(tǒng)（Flexible Manufacturing System，F(xiàn)MS）。

自從20世紀(jì)80年代FMS逐漸走向?qū)嵱茫瑖?guó)內(nèi)外對(duì)FMS相關(guān)的研究就一直在進(jìn)行。1977年Solberg采用CAN-Q模型評(píng)價(jià)FMS性能，首次將工業(yè)生產(chǎn)系統(tǒng)建立解析模型進(jìn)行優(yōu)化[1]。1983年Suri和Hildebrant對(duì)FMS的優(yōu)化問(wèn)題進(jìn)行了討論，采取了排隊(duì)網(wǎng)絡(luò)方法建立了整個(gè)制造系統(tǒng)的解析模型[2]。20世紀(jì)以來(lái)，閉排隊(duì)網(wǎng)絡(luò)（ClosedQue，CQN）模型作為求解速度更快效果更好的優(yōu)化排隊(duì)網(wǎng)絡(luò)模型被廣泛采用[3]。Rajagopalan提出了一個(gè)混合整數(shù)規(guī)劃（MIP）解決方案，解決了零件分組和零件刀具分配問(wèn)題[4]。隨后Sawik提出了基于零件類型選擇、機(jī)器裝載、零件輸入序列和操作調(diào)度的生產(chǎn)計(jì)劃任務(wù)的層次結(jié)構(gòu)以確定柔性制造系統(tǒng)[5]。阿蒙斯等人描述并討論了機(jī)器裝載問(wèn)題的兩個(gè)目標(biāo)，即平衡工作負(fù)載和最小化工位用量[6]。文獻(xiàn)[7]中也討論了裝載問(wèn)題的雙準(zhǔn)則目標(biāo)，包括平衡工作負(fù)載和滿足零件類型流水線中的選擇搭配。文獻(xiàn)[6,7]指出，之前建立的一系列數(shù)學(xué)模型方法是不切實(shí)際的，因?yàn)榧词箤?duì)于中等大小的測(cè)試問(wèn)題也需要大量的計(jì)算時(shí)間。盡管在過(guò)去的20年里在算法方面取得了進(jìn)步，要解決這個(gè)問(wèn)題仍然比較困難，同時(shí)在生產(chǎn)過(guò)程中實(shí)現(xiàn)所需的軟件方面存在著一些障礙。后來(lái)Kumar和Shanker通過(guò)建立MIP模型來(lái)解決零件類型選擇和機(jī)器裝載問(wèn)題，提出了基于遺傳算法（GA）的求解方法，并且使得計(jì)算量更小[8]。Yang和Wu還應(yīng)用了基于遺傳算法的集成方法來(lái)解決FMS零件類型選擇和機(jī)器裝載問(wèn)題，在實(shí)現(xiàn)算法的編碼方案的同時(shí)，引入了虛擬作業(yè)和虛擬操作的概念[9]。

本文采用了基于染色體分化（GACD）原理的新型遺傳算法，這是一種求解FMS中機(jī)型配置工序優(yōu)化問(wèn)題的新型算法。GACD具有優(yōu)于傳統(tǒng)遺傳算法的以下 優(yōu)點(diǎn)。

1）GACD在系統(tǒng)的應(yīng)用和配置之間有更好的平衡性，因此與傳統(tǒng)的遺傳算法相比能得到更好的結(jié)果。

2）種群多樣性的增加和限制交叉導(dǎo)致染色體之間更快的信息交換，從而比傳統(tǒng)遺傳算法收斂速度更快。

3）通過(guò)對(duì)GACD的分析，特別是對(duì)Bandhopadhyay和Pal提出的樣例進(jìn)行分析，GACD得到的優(yōu)化值要優(yōu)于傳統(tǒng)遺傳算法的優(yōu)化值[10]。

1 染色體分化的遺傳算法

遺傳算法是一種“智能”概率進(jìn)化搜索和優(yōu)化算法，它通過(guò)采集一組稱為種群的染色體并應(yīng)用各種生物啟發(fā)的遺傳算子，如選擇、交叉和變異來(lái)模擬染色體成熟過(guò)程。種群內(nèi)的每一個(gè)染色體通過(guò)已經(jīng)設(shè)定好的適應(yīng)性函數(shù)進(jìn)行評(píng)估，并通過(guò)選擇、交叉、變異進(jìn)行繁殖，產(chǎn)生新的子代并用適應(yīng)性高的染色體組代替差的染色體組。以此類推不斷選擇和優(yōu)化，直到找到令人滿意且接近最優(yōu)的解決方案[11]。

在本文所提出的染色體分化遺傳算法中，我們應(yīng)用性別分化使得染色體被分成兩類，即男性（M）和女性（F），從而產(chǎn)生兩個(gè)群體，即男性群體（MP）和女性群體（FP）。另外，在構(gòu)造兩類群體時(shí)我們?nèi)斯さ厥惯@些種群不同，以最大化兩個(gè)類之間的漢明距離（HammingDistance）的方式產(chǎn)生這兩個(gè)種群。同時(shí)我們規(guī)定只有屬于兩個(gè)不同種群的個(gè)體之間才允許交叉，而選擇則適用于所有種群[12]。因此，GACD在選擇和優(yōu)化之間更好的實(shí)現(xiàn)了平衡，這也是任何自適應(yīng)系統(tǒng)的主要特征之一，從而使GACD優(yōu)于簡(jiǎn)單的遺傳算法（GA）。GA的基本步驟如圖1所示，而GACD也基本遵循圖1的步驟，2.1節(jié)～2.6節(jié)介紹了GACD與傳統(tǒng)GA算法的參數(shù)不同之處。

圖1 遺傳算法步驟流程圖

1.1 種群初始化

圖2描述了GACD染色體的構(gòu)建過(guò)程。染色體的前兩位稱為數(shù)據(jù)類位，因?yàn)樗鼈冇脕?lái)指示染色體的類是男性（M）還是女性（F）。這兩個(gè)互相獨(dú)立的類，一個(gè)由男性群體染色體（M）組成，另一個(gè)由女性群體染色體（F）組成。總種群（TP）等于男性群體（MP）+女性群體（ F P ） 。 最開(kāi)始各類染色體數(shù)量為MP=FP=TP/2，但是隨著交叉和變異，這兩類染色體（MP和FP）的大小在不同的世代中會(huì)逐漸出現(xiàn)差異。首先種群中的MP首先被初始化，每個(gè)M類染色體的數(shù)據(jù)位被隨機(jī)初始化為01或10。然后對(duì)FP進(jìn)行初始化，通過(guò)最大化男性群體和女性群體之間的漢明距離來(lái)生成每個(gè)F類染色體的數(shù)據(jù)位。而每個(gè)F染色體的所有數(shù)據(jù)類位都設(shè)置為0。因此對(duì)于兩個(gè)染色體γ1和γ2：γ1，γ2，其中τ是染色體初始種群，HD（γ1，γ2）被定義為兩個(gè)染色體不相同數(shù)據(jù)位的數(shù)量。兩個(gè)群體MP和FP之間的HD表示為：

1.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)定義也如式(1)、式(2)所示，通過(guò)計(jì)算男性群體和女性群體每個(gè)染色體前兩個(gè)數(shù)據(jù)位的漢明距離確定新種群的適應(yīng)度。

1.3 選擇操作

通過(guò)確定種群的適應(yīng)度函數(shù)，每次進(jìn)化完畢后比較父代和子代的適應(yīng)度，適應(yīng)度高的被選擇為新的男性群體和女性群體。

1.4 交叉操作

男性種群M和女性種群F之間的交叉操作概率xc。其中每個(gè)父代為子代提供一個(gè)類位，很明顯女性種群F只能貢獻(xiàn)類位0。因此，后代的類別只由能貢獻(xiàn)1或0的男性種群M決定。如前文所示的交叉操作被應(yīng)用于數(shù)據(jù)的類位上，直到滿足以下條件則交叉停止。

1）原種群中沒(méi)有染色體存在。

2）原種群中只有男性染色體M存在或只有女性染色體F存在。

在情況1中，交叉過(guò)程終止。在情況2中，剩余的M或F染色體與適應(yīng)度最好的F或M染色體配對(duì)。如果在初始階段，交配池只包含一個(gè)類的染色體，同樣也中止雜交程序。

1.5 變異操作

變異操作概率為μp且應(yīng)用在染色體的數(shù)據(jù)位中，并不應(yīng)用在染色體的類位上。

2 GACD算法的具體應(yīng)用

本節(jié)定義了GACD算法的相關(guān)術(shù)語(yǔ)，并討論了GACD算法應(yīng)用在生產(chǎn)線時(shí)出現(xiàn)的各種設(shè)計(jì)問(wèn)題（例如編碼、群體初始化、適應(yīng)度函數(shù)評(píng)價(jià)、交叉、變異、選擇和縮放）。GACD的主要優(yōu)點(diǎn)是它的靈活性和適應(yīng)不斷變化的優(yōu)化標(biāo)準(zhǔn)和約束的能力。對(duì)于單個(gè)個(gè)體的表示、編碼方法、初始M和F種群、選擇和縮放方法以及遺傳算子的選擇等因素對(duì)GACD算法的性能都會(huì)有很大的影響。因此在接下來(lái)的幾小節(jié)中，本文對(duì)這些因素進(jìn)行了詳細(xì)的討論。

2.1 編碼

對(duì)染色體的編碼方式是遺傳算法實(shí)現(xiàn)中的一個(gè)關(guān)鍵問(wèn)題。GACD編碼包括對(duì)類位的編碼和對(duì)數(shù)據(jù)位的編碼。Holland等人采用了二進(jìn)制字符串編碼方案，但這樣的方案后來(lái)被驗(yàn)證不適用于現(xiàn)實(shí)世界的問(wèn)題[13]。在過(guò)去的十年中，各種非字符串編碼技術(shù)已經(jīng)被開(kāi)發(fā)用于特定的問(wèn)題，例如用于解決約束優(yōu)化問(wèn)題的實(shí)數(shù)編碼和組合優(yōu)化問(wèn)題的整數(shù)編碼。除了這些之外，鄰接、置換和基于矩陣的編碼也都被廣泛應(yīng)用。本研究采用的編碼方式為，類位采用二進(jìn)制編碼，數(shù)據(jù)位采用面向數(shù)據(jù)序列的編碼方案。例如，如果工業(yè)生產(chǎn)線生產(chǎn)一個(gè)機(jī)器需要8個(gè)步驟，那么它可以被編碼為：

這里，類位01表示該染色體為男性（M）染色體，數(shù)據(jù)位依次表示生產(chǎn)步驟。

2.2 種群初始化

種群初始化的原則在2.2節(jié)已經(jīng)討論過(guò)，同樣對(duì)于8個(gè)步驟的生產(chǎn)過(guò)程可以假設(shè)其表示為：

Male population 0 1 4 5 7 3 1 6 2 8 0 1 5 6 1 4 2 8 7 3 1 0 7 2 6 4 5 1 3 8 1 0 3 1 5 2 4 7 8 6

Female population 0 0 5 4 2 6 8 3 7 1 0 0 4 3 8 5 7 1 2 6 0 0 2 7 3 5 4 8 6 1 0 0 6 8 4 7 5 2 1 3

2.3 選擇操作

選擇操作是對(duì)所有染色體進(jìn)行選擇，同時(shí)不考慮染色體的類信息。選擇操作中采用合適縮放方法有助于整個(gè)遺傳算法保持合適的擇優(yōu)速率，并防止種群過(guò)早收斂到次優(yōu)解。在本研究中，我們測(cè)試了各種縮放方法，包括動(dòng)態(tài)線性縮放、冪律縮放、對(duì)數(shù)縮放、加窗、歸一化和玻爾茲曼選擇。計(jì)算實(shí)驗(yàn)表明，“玻爾茲曼選擇”方案中的基于比例選擇的“輪盤賭策略”比其他策略具有更高的效率。對(duì)于染色體K和適應(yīng)度f(wàn)k，尺度函數(shù)可以定義為：

當(dāng)控制參數(shù)T高時(shí)，選擇壓力較低。因此選擇概率可以等價(jià)為：

由式(4)可知，適應(yīng)度最高的個(gè)體總是可以存活到下一代，以便使GACD能夠更快地收斂。

2.4 交叉操作

在GACD算法中，交叉應(yīng)用直到滿足適應(yīng)度函數(shù)的條件為止。交叉操作是一個(gè)M染色體和一個(gè)F染色體重組產(chǎn)生兩個(gè)染色體的過(guò)程。目前解決排序和調(diào)度問(wèn)題時(shí)常用的標(biāo)準(zhǔn)交叉算子為有啟發(fā)式交叉、部分映射交叉（PMX）、增強(qiáng)邊緣重組（EER）、順序交叉（OX）、基于均勻順序的交叉（UOX）和循環(huán)交叉（CX）。在本研究中采用了部分映射交叉的方法。部分映射交叉的操作流程為如下：

隨機(jī)選取兩個(gè)交叉點(diǎn)，按性別交換兩個(gè)交叉點(diǎn)之間的片段。將男性染色體中的片段替換為女性染色體中同樣交叉點(diǎn)間的片段。

將男性染色體交叉點(diǎn)外重復(fù)的工序按對(duì)應(yīng)方式替換為交叉點(diǎn)內(nèi)的工序步驟，同時(shí)將女性染色體按同樣步驟處理，即可得到男性染色體的子代和女性染色體的子代，PMX流程如圖2所示。

圖2 部分交叉映射流程圖

2.5 變異操作

染色體經(jīng)過(guò)交叉操作后，染色體往往會(huì)受到突變，這些突變會(huì)為染色體增加額外的變異性，提供并維持了整個(gè)種群中的多樣性，并能基本遍歷所有的搜索空間。在本研究中，變異操作被作用于染色體的數(shù)據(jù)位。變異概率表示染色體中的基因?qū)⒈桓淖兊母怕省Ｔ谶^(guò)去的研究中，人們提出了若干種用于遺傳算法的變異算子，例如反轉(zhuǎn)、插入、移位、互換變異等。而在本研究中，本文采用一種基于啟發(fā)式的方法，使用鄰域技術(shù)變異產(chǎn)生一個(gè)改進(jìn)的后代。變異的基本原理如下，示意圖如圖3所示。

1）隨機(jī)選擇n個(gè)基因片段。

2）通過(guò)考慮所選基因的所有可能排列來(lái)產(chǎn)生鄰域后代。

3）評(píng)價(jià)所有鄰域后代的適應(yīng)度并選出最優(yōu)的 后代。

圖3 變異操作示意圖

2.6 參數(shù)設(shè)置

遺傳算法的參數(shù)設(shè)置及優(yōu)化是一個(gè)非常耗時(shí)的問(wèn)題。主要可調(diào)的參數(shù)位種群大小POP_SIZE、進(jìn)化次數(shù)MAX_ GEN、交叉概率xp、變異概率μp。其中：

種群大小通常根據(jù)染色體長(zhǎng)度（CL）的倍數(shù)變化，如式(5)所示。其中PSF為種群大小因子。在本研究中，POP_SIZE=INIM_POP+INIF_POP，即種群大小為初始男性種群和初始女性種群的數(shù)量和。

遺傳算法通常采用較大的xp（0.4～0.9）和較小的μp（0.05～0.2），xp和μp的增加可以優(yōu)化過(guò)程中的遍歷程度，但同時(shí)也會(huì)增加算法的耗時(shí)。在本研究中，已經(jīng)進(jìn)行了大量的實(shí)驗(yàn)以實(shí)現(xiàn)優(yōu)化和耗時(shí)之間的平衡，并且所得到的結(jié)果也在上述的范圍內(nèi)，這些參數(shù)的精確值將在下一章的示例中給出。

3 生產(chǎn)線示例

為了證明本文提出的GACD算法的有效性，將本方法應(yīng)用到文獻(xiàn)[14]至文獻(xiàn)[16]中給出的一個(gè)隨機(jī)機(jī)型的FMS示例中。表1為給定FMS類型的測(cè)試問(wèn)題的詳細(xì)描述下面的步驟描述了上述基于GACD方法在解決柔性制造問(wèn)題上的應(yīng)用。

1）設(shè)置初始變量INIM_POP=INIF_POP=5，xp=0.5，μp=0.1，MAX_GEN=30。

2）生產(chǎn)的總工序步驟pmax=8，同時(shí)工序的步驟順序按照第三節(jié)中提到的種群初始化方式構(gòu)造。

3）選擇合適的適應(yīng)度函數(shù)以最小化整體系統(tǒng)的不平衡性。

4）初始化進(jìn)化次數(shù)GEN，并使GEN+1，對(duì)第2）步中初始化的種群進(jìn)行操作，假設(shè)待操作的染色體為[0 1 5 4 3 7 1 6 8 2]。

5）對(duì)每個(gè)男性群體和每個(gè)女性群體計(jì)算適應(yīng)度函數(shù)f1的值。其中只有染色體的數(shù)據(jù)位參與計(jì)算。

6）對(duì)于步驟4）給出的染色體，其代表的工作順序?yàn)閇5 4 3 7 1 6 8 2]，性別為男性。按照第三章所述進(jìn)行PMX交叉以及基于啟發(fā)式的變異操作。交叉后的子代和變異后的子代共同構(gòu)成進(jìn)化后的子代。按照前文給出的適應(yīng)度函數(shù)進(jìn)行評(píng)價(jià)，并選擇出最優(yōu)染色體構(gòu)成一次進(jìn)化的結(jié)果。

7）終止條件如下：如果GEN=MAX_GEN，則終止進(jìn)化，否則GEN=GEN+1，并回到第5）步。

經(jīng)過(guò)以上給定步驟的GACD算法運(yùn)算后，示例FMS的利用率可以達(dá)到76%。

表1 FMS示例

表1（續(xù)）

4 結(jié)語(yǔ)

本文提出了一種基于啟發(fā)式的GACD算法，并將其與普通遺傳算法進(jìn)行了比較。圖4給出了GACD原理下幾種交叉和變異算子組合的性能及其對(duì)示例給出的FMS加載問(wèn)題結(jié)果的影響。同時(shí)，對(duì)于Tiwari和Vidyarthi在[17]提出的問(wèn)題，我們將GACD算法與GA進(jìn)行了比較，結(jié)果如圖5所示。由比較可知，二者得到最優(yōu)結(jié)果的進(jìn)化次數(shù)是相同的，但對(duì)于結(jié)果的評(píng)價(jià)函數(shù)來(lái)說(shuō)，GACD得到的結(jié)果使得系統(tǒng)的平衡性更高。

PMX-RE：部分映射交叉+相互交換

EER-INS：增強(qiáng)邊緣重組交叉+插入交換

CX-DIS：循環(huán)交叉+替換

圖4 不同算子的性能比較

圖5 GA與GACD最佳適應(yīng)度(a)和平均適應(yīng)度(b)的比較

PMX-HEU：部分映射交叉+啟發(fā)式變異本文對(duì)一個(gè)具有四個(gè)目標(biāo)函數(shù)和兩個(gè)技術(shù)約束的機(jī)器裝載問(wèn)題進(jìn)行分析。本研究所要解決的關(guān)鍵問(wèn)題是藉由滿足工藝約束來(lái)決定機(jī)器上待加工零件類型的數(shù)目和順序，以達(dá)到最小系統(tǒng)不平衡和最大產(chǎn)量。因此本文提出了一種基于染色體分化的遺傳算法，利用染色體分化的概念來(lái)增強(qiáng)現(xiàn)有遺傳算法的能力。其中在對(duì)算法進(jìn)行編碼時(shí)，將二進(jìn)制編碼應(yīng)用于類位，并且使用實(shí)數(shù)編碼對(duì)數(shù)據(jù)位進(jìn)行編碼，同時(shí)最大化染色體間的漢明距離，限制交叉，使得進(jìn)化過(guò)程可以發(fā)生更快的信息交換。該方法在給出的示例測(cè)試問(wèn)題中的應(yīng)用表明，GACD在求解質(zhì)量和求解耗時(shí)上都表現(xiàn)良好。同時(shí)本研究還可以進(jìn)行進(jìn)一步的研究，比如增加對(duì)資源的其他方面的分配，如增加工位，增加固定裝置和自動(dòng)引導(dǎo)車輛（AGV），都可以進(jìn)一步的優(yōu)化整個(gè)生產(chǎn)線系統(tǒng)。同時(shí)我們還可以增加一些懲罰概念和更多的目標(biāo)函數(shù)，例如要求零件運(yùn)輸距離的最小化、加工器械在生產(chǎn)過(guò)程中的改變等等，而這也是我們下一步要考慮的主要問(wèn)題。