基于染色體分化遺傳算法的工業生產線柔性加工

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

（山東建筑大學，濟南 250100）

0 引言

隨著科學技術的進步和計算機技術的發展，原有的傳統機械制造方式在計算機等輔助工具的幫助下得到了新的發展，增加了新的內涵。由于傳統的機械制造方式受環境等不確定因素影響較大，操作人員疲勞、設備老舊、零部件損壞等問題會嚴重影響作業效果。因此計算機輔助設計（CAD）、計算機輔助制造（CAM）、柔性制造系統、計算機集成制造系統（CIMS）等新技術被廣泛應用于機械制造領域。而在工業生產線的分配布局過程中，我們必須對之前所說的不確定因素進行評價并優化，以提高生產線的平衡性和魯棒性，而這就是柔性制造系統（Flexible Manufacturing System，FMS）。

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

本文采用了基于染色體分化（GACD）原理的新型遺傳算法，這是一種求解FMS中機型配置工序優化問題的新型算法。GACD具有優于傳統遺傳算法的以下 優點。

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

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

3）通過對GACD的分析，特別是對Bandhopadhyay和Pal提出的樣例進行分析，GACD得到的優化值要優于傳統遺傳算法的優化值[10]。

1 染色體分化的遺傳算法

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

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

圖1 遺傳算法步驟流程圖

1.1 種群初始化

圖2描述了GACD染色體的構建過程。染色體的前兩位稱為數據類位，因為它們用來指示染色體的類是男性（M）還是女性（F）。這兩個互相獨立的類，一個由男性群體染色體（M）組成，另一個由女性群體染色體（F）組成?？偡N群（TP）等于男性群體（MP）+女性群體（ F P ） 。 最開始各類染色體數量為MP=FP=TP/2，但是隨著交叉和變異，這兩類染色體（MP和FP）的大小在不同的世代中會逐漸出現差異。首先種群中的MP首先被初始化，每個M類染色體的數據位被隨機初始化為01或10。然后對FP進行初始化，通過最大化男性群體和女性群體之間的漢明距離來生成每個F類染色體的數據位。而每個F染色體的所有數據類位都設置為0。因此對于兩個染色體γ1和γ2：γ1，γ2，其中τ是染色體初始種群，HD（γ1，γ2）被定義為兩個染色體不相同數據位的數量。兩個群體MP和FP之間的HD表示為：

1.2 適應度函數

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

1.3 選擇操作

通過確定種群的適應度函數，每次進化完畢后比較父代和子代的適應度，適應度高的被選擇為新的男性群體和女性群體。

1.4 交叉操作

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

1）原種群中沒有染色體存在。

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

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

1.5 變異操作

變異操作概率為μp且應用在染色體的數據位中，并不應用在染色體的類位上。

2 GACD算法的具體應用

本節定義了GACD算法的相關術語，并討論了GACD算法應用在生產線時出現的各種設計問題（例如編碼、群體初始化、適應度函數評價、交叉、變異、選擇和縮放）。GACD的主要優點是它的靈活性和適應不斷變化的優化標準和約束的能力。對于單個個體的表示、編碼方法、初始M和F種群、選擇和縮放方法以及遺傳算子的選擇等因素對GACD算法的性能都會有很大的影響。因此在接下來的幾小節中，本文對這些因素進行了詳細的討論。

2.1 編碼

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

這里，類位01表示該染色體為男性（M）染色體，數據位依次表示生產步驟。

2.2 種群初始化

種群初始化的原則在2.2節已經討論過，同樣對于8個步驟的生產過程可以假設其表示為：

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 選擇操作

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

當控制參數T高時，選擇壓力較低。因此選擇概率可以等價為：

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

2.4 交叉操作

在GACD算法中，交叉應用直到滿足適應度函數的條件為止。交叉操作是一個M染色體和一個F染色體重組產生兩個染色體的過程。目前解決排序和調度問題時常用的標準交叉算子為有啟發式交叉、部分映射交叉（PMX）、增強邊緣重組（EER）、順序交叉（OX）、基于均勻順序的交叉（UOX）和循環交叉（CX）。在本研究中采用了部分映射交叉的方法。部分映射交叉的操作流程為如下：

隨機選取兩個交叉點，按性別交換兩個交叉點之間的片段。將男性染色體中的片段替換為女性染色體中同樣交叉點間的片段。

將男性染色體交叉點外重復的工序按對應方式替換為交叉點內的工序步驟，同時將女性染色體按同樣步驟處理，即可得到男性染色體的子代和女性染色體的子代，PMX流程如圖2所示。

圖2 部分交叉映射流程圖

2.5 變異操作

染色體經過交叉操作后，染色體往往會受到突變，這些突變會為染色體增加額外的變異性，提供并維持了整個種群中的多樣性，并能基本遍歷所有的搜索空間。在本研究中，變異操作被作用于染色體的數據位。變異概率表示染色體中的基因將被改變的概率。在過去的研究中，人們提出了若干種用于遺傳算法的變異算子，例如反轉、插入、移位、互換變異等。而在本研究中，本文采用一種基于啟發式的方法，使用鄰域技術變異產生一個改進的后代。變異的基本原理如下，示意圖如圖3所示。

1）隨機選擇n個基因片段。

2）通過考慮所選基因的所有可能排列來產生鄰域后代。

3）評價所有鄰域后代的適應度并選出最優的 后代。

圖3 變異操作示意圖

2.6 參數設置

遺傳算法的參數設置及優化是一個非常耗時的問題。主要可調的參數位種群大小POP_SIZE、進化次數MAX_ GEN、交叉概率xp、變異概率μp。其中：

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

遺傳算法通常采用較大的xp（0.4～0.9）和較小的μp（0.05～0.2），xp和μp的增加可以優化過程中的遍歷程度，但同時也會增加算法的耗時。在本研究中，已經進行了大量的實驗以實現優化和耗時之間的平衡，并且所得到的結果也在上述的范圍內，這些參數的精確值將在下一章的示例中給出。

3 生產線示例

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

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

2）生產的總工序步驟pmax=8，同時工序的步驟順序按照第三節中提到的種群初始化方式構造。

3）選擇合適的適應度函數以最小化整體系統的不平衡性。

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

5）對每個男性群體和每個女性群體計算適應度函數f1的值。其中只有染色體的數據位參與計算。

6）對于步驟4）給出的染色體，其代表的工作順序為[5 4 3 7 1 6 8 2]，性別為男性。按照第三章所述進行PMX交叉以及基于啟發式的變異操作。交叉后的子代和變異后的子代共同構成進化后的子代。按照前文給出的適應度函數進行評價，并選擇出最優染色體構成一次進化的結果。

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

經過以上給定步驟的GACD算法運算后，示例FMS的利用率可以達到76%。

表1 FMS示例

表1（續）

4 結語

本文提出了一種基于啟發式的GACD算法，并將其與普通遺傳算法進行了比較。圖4給出了GACD原理下幾種交叉和變異算子組合的性能及其對示例給出的FMS加載問題結果的影響。同時，對于Tiwari和Vidyarthi在[17]提出的問題，我們將GACD算法與GA進行了比較，結果如圖5所示。由比較可知，二者得到最優結果的進化次數是相同的，但對于結果的評價函數來說，GACD得到的結果使得系統的平衡性更高。

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

EER-INS：增強邊緣重組交叉+插入交換

CX-DIS：循環交叉+替換

圖4 不同算子的性能比較

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

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