基于矩陣編碼遺傳算法的PCB生產線元件分配優化

杜 軒 李登橋 朱 康

（三峽大學 機械與動力學院，湖北 宜昌 443002）

電子產品需求的日益增加，促進了印制電路板（Print Circuit Board，PCB）的大批量組裝生產，連續生產線作為工業生產中一種典型的布置方式，在PCB組裝生產過程中也得到了廣泛的應用，即把組裝過程中所用到的設備依照一定的工藝次序組合，用傳送帶串聯成一條連續的生產線，所有PCB以相同的順序通過生產線上的所有設備，完成元件組裝.PCB在生產線上的組裝時間是由生產線上所有設備中耗時最長的設備所決定，對PCB在不同設備上組裝的元件進行分配優化，可實現各臺設備間的負荷平衡，縮短PCB組裝時間，此問題即為連續生產線上的元件分配問題.PCB組裝生產線上的元件分配和PCB分配優化屬于典型的組合優化問題，其計算復雜度高，也是一種NP－hard難題.

目前，針對PCB生產線元件分配問題的研究主要采用數學規劃方法、啟發式方法等.而遺傳算法在求解組合優化問題中，具有全局性概率搜索的特點，在搜索過程中能自動獲取和積累相關搜索空間的知識，并結合自適應的控制搜索過程，因此在這一類問題的優化計算中表現出了較大的優勢.文獻［1］中Ho W和Ji P，建立了連續PCB組裝生產線上元件分配優化模型，然后應用傳統遺傳算法對問題進行求解，從而解決了連續生產線上元件分配和多條生產線上的PCB分配優化問題.文獻［2］基于多臺不同類型典型表面貼裝設備所組裝成的印制電路板組裝生產線，針對上述組裝機及組裝流水線的調度問題，建立相應的集成調度優化模型，從而為后續研究電子產品制造企業生產線調度問題的智能優化算法提供了理論依據和技術支持.文獻［3］中針對表面組裝生產線負荷平衡問題，建立了以最小化最大單機貼裝時間為目標函數的整數規劃模型，并采用傳統的傘布式搜索方法對模型進行優化求解，最后通過實驗仿真得到優化結果，表明了此算法在求解此類問題的有效性.文獻［4］提出了流水線調度優化問題，進而采用傳統遺傳算法（TGA）對問題進行求解，同時應用實際生產數據進行試驗，證明此方法的優越性.

目前，針對PCB組裝生產線上元件分配優化問題的研究已經取得了部分的研究成果，但是，還有一定的優化提升空間，主要表現在以下幾個方面：1）部分研究所建立的優化模型不能夠很好反應企業實際情況，導致所求的結果不能直接應用于實際生產；2）一般的研究在進行模型求解時所采用的方法有一定的局限性，而且求解效率較低，求解結果表述不明了，在諸多方面還有改善和提升空間［5］.基于上述的分析和已有的研究成果，本文設計了一種新的基于矩陣編碼方式，提出了結合最小元素法的方法，高效實現了種群初始化操作；采用兩點交叉的方式進行交叉操作，從而提高了種群多樣性；采用改進的局部變異法，再次結合最小元素法實現了變異操作；最終，通過算法求解實現了PCB組裝連續生產線上的元件分配優化問題，并通過實例仿真驗證，表明了此方法的有效性和優越性.

1 PCB生產線元件分配問題描述及優化模型建立

1.1 PCB生產線元件分配問題描述

考慮一種PCB在一條連續生產線上組裝，由于組成生產線的設備性能差異，不同的設備組裝同一類型的元件所用的時間是不一樣的，即使是同一設備在組裝不同元件時所需要的時間也不同，甚至有些設備對某些特定的元件根本無法完成組裝.因此需要將PCB上的元件合理地分配到不同的組裝設備上，平衡各臺設備上的工作負荷，以減少PCB的組裝時間［6］.如圖1中所示即為n中不同類型的元件在一條生產線上m個不同設備之間進行分配的模型.

圖1 元件在設備間分配的分配模型

1.2 元件分配優化模型

假設PCB上有L種不同類型的元件，在M臺設備上進行組裝，第i種類型的元件在設備k上組裝的數量為Cki，第i種類型的元件在設備k上組裝所需的時間為tki；組裝設備的調整時間為sk.元件分配優化問題的數學模型可描述如下：

式中，i為元件類型的編號，i＝1，2，…，L；k為組裝設備的編號，k＝1，2，…，M；cki為元件類型i在設備k上組裝的數量；sk為組裝設備k的調整時間；tki為元件類型i在設備k上的組裝時間；N為PCB上組裝元件的數量.

目標函數式是使生產線上耗時最長設備的組裝時間最小化.

2 遺傳算法求解與實現

2.1 染色體編碼

編碼方式的選擇是運用遺傳算法解決問題的關鍵.對于元件分配優化問題，如果采用傳統的二進制字符串編碼方式，當元件的類型及設備數量增加時，染色體的長度會急劇增加，導致算法實現時間復雜度和空間復雜度增加，影響求解效率［4］.根據元件分配問題自身的特點，可采用矩陣形式的編碼方式，一條染色體的編碼為

式中，行表示生產線上的設備，列表示PCB上的元件類型，矩陣的元素xij表示第j種類型的原價在設備i上組裝的數量.一條染色體的結構實際上就描述了元件分配問題的一種方案.因此采用矩陣編碼有利于問題的求解.

2.2 種群初始化

如何保證產生的初始種群中的所有個體都能滿足問題的約束條件式是初始種群產生的難點所在.對于整數約束，只需要保證染色體中每個元素變量都是大于0的整數即可.對于如何保證元件數量約束存在一定的難度.本文中將采用最小元素法，即找出運價表中最小的元素，在運量表內對應的格填入允許取得的最大數，若某行（列）的產量（銷量）已滿足，則把運價表中該運價所在行（列）劃去；找出未劃去的運價中的最小數值，按此辦法進行下去，直至得到一個基本可行解的方法［7］.

通過問題的數學模型和解的表達形式，可以看出，此問題與運輸問題很相似.對于產銷平衡的運輸問題的可行解是很容易被確定的，且產銷平衡的運輸問題一定存在有限最優解.求解運輸問題的常用方法是表上作業法，雖然此方法的求解效率很低，有可能得不到問題的最優解，但是可以借鑒其中的最小元素法的思想來產生滿足約束條件的初始種群［8］.

對比元件分配問題的數學模型與產銷平衡運輸問題的數學模型后可以發現，兩種問題的最大不同點在于前者比后者少了一個約束條件，即對每臺設備要組裝的原價類型數量沒有限制.但是由于問題的實際意義可以看出，這一約束條件是隱含存在的，為了使元件得以順利的組裝，必須使所有的設備組裝元件的個數之和等于元件的總個數.此處假設每臺設備上組裝元件的個數為bi（i＝1，2，…，m）且bi≥0，上述的描述可以用下式來表示：

增加一個約束條件：

此時，元件分配問題就轉化為了“產銷平衡的運輸問題”，初始化種群按照以下步驟來生成：

1）隨機分配給bi一個整數，并且使得bi滿足元件的數量約束條件.

2）從集合δ＝（1，2，…，m×n）中隨機選擇一個數k.

3）由下式計算k在編碼矩陣中所對應的行i和列j：

j＝ （k－1）mod（n）＋1（“mod”為取余運算）（7）

4）確定變量xij的值.

5）由下式更新bi和ci的值，并從集合δ中刪除元素k.

如果bi＜0，則將其置為0，cj也做類似操作.

6）重復步驟2）～5），直到集合δ為空，這樣就產生了問題的一個可行解，即一條染色體.

對上述步驟1）～6）重復操作執行多次，便可得到問題的初始種群.可以看出，采用這種方法所得到的個體全部滿足問題的約束條件，即為問題的可行解，進而充分保證了后續搜索空間的有效性.

2.3 適應度函數及選擇

適應度函數用來對個體的優劣程度進行評價，這里采用個體時間作為個體的適應度，對其進行評價［9］.

本文的選擇操作將采用二元錦標賽選擇方法和最優保存策略相結合的方法來進行個體的選擇，采用二元錦標賽選擇方法選擇進行交叉變異的個體，交叉變異所產生的新個體和父代種群中的個體同時采用最優選擇策略，用適應度高的個體產生下一代種群，且種群的數量要保持不變.

2.4 交叉與變異

交叉操作即對父代的兩個染色體在指定的基因位進行交叉運算，以產生新個體.交叉概率Pc控制著交叉算子的應用頻率，在種群大小為M的群體中，需要對pc×m個染色體進行交叉操作，交叉概率越高，群體中新結構的引入越快，已獲得的優良基因基因機構的丟失速度也相應越高，而交叉概率太低則可能導致搜索阻滯［10］.此處采用線性遞減函數產生交叉率Pc，假設第一代與最后一代的Pc分別為Pc1和Pcn，迭代終止次數為N，則第i代的交叉概率Pci為

為了保證交叉之后的個體滿足最初的約束條件，基于矩陣編碼的方式需保證每列的和滿足題設中的要求.即在進行交叉時只能保證對應列進行交叉.采用這種交叉方式就可以保證個體始終是滿足約束條件的有效個體，從而有效保證了遺傳操作的正常進行.

變異即改變染色體上的一個或一些基因座上的基因值為其它的基因，以產生新的個體.對采用二進制編碼的染色體只需對指定的基因位進行0和1之間的轉換即可.而對于此處采用矩陣形式表示的染色體，為了使變異后的個體也是問題的可行解，則不能進行簡單的基因位的轉換，因此，變異采用以下的方法進行.

3 算法實現及優化實例

3.1 實例分析

采用實際生產中的實例進行例證分析，以文獻［1］中所用的元件和設備信息為例，計算元件的分配問題.具體的數據如圖2所示，圖2中共有7種不同類型的貼片元件和3臺不同的貼片設備，各種類型的元件個數Cj和設備調整時間Si如圖所示.圖2中的右上角的數據表示相應的設備組裝相應的元件所需的時間（單位0.1s），符號∞表示相應的設備不能對相應的元件進行組裝［11］，在算法實現時，可以將∞符號賦值為一個較大的實數即可，這樣在進行元件分配時，如果分配給此種設備的相應元件類型時，此個體的適應度就會較高，因此在遺傳操作過程中就會逐漸被淘汰.

圖2 實例數據圖

3.2 算法實現步驟

采用改進的遺傳算法，其具體實現步驟：

1）設置遺傳算法（GA）參數.主要包括種群大小（Psize）、遺傳代數（Count）、交叉概率（Pc）和變異概率（Pm）.

2）種群初始化.根據染色體的編碼規則和要求，生成Psize個二維十進制分段的染色體，形成初始化種群.

3）計算適應度.根據適應度評價函數，計算種群個體的適應度值.

4）適應度值比較.采用二元錦標賽選擇方法，保留個體中適應度值較大的個體，進行下一步的交叉和變異操作.

5）交叉操作.采用改進的交叉方法生成新種群.

6）變異操作.結合最小元素法，應用改進的局部變異以及自適應的變異率方法進行變異操作.

7）通過遺傳操作之后保留每代中的最優個體.

8）重復步驟4）～8），直到完成所設定的迭代次數，得到最優個體以及最大適應度值.

3.3 求解結果及分析

本文算法使用Matlab編程，采用GA算法對實例數據進行求解，測試實際生產線的數據.實驗對象為一條連續的PCB組裝生產線，共3臺組裝設備，7種不同的元件類型，每種不同類型的元件都有不同的數量，不同類型組裝設備在組裝不同類型元件時其速度也各不相同，每臺組裝設備的調整時間也不同.

在算法的實現過程中采用的主要遺傳操作參數為：初始種群Psize＝100，遺傳代數Count＝50，初始交叉概率Pc1＝0.8，終止交叉概率Pcn＝0.6，變異概率Pm＝0.2，采用改進的遺傳算法對圖2中的工程實際問題進行求解，多次運行之后取平均值，得到算法收斂圖如圖3所示.

圖3 PCB組裝生產線元件分配優化收斂圖

最終得到的最優化結果為99.5s.元件分配結果為

4 結 論

本文主要分析了PCB組裝連續生產線上的元件分配優化問題，并建立了此問題的優化數學模型.詳細介紹了元件分配優化問題的改進遺傳算法求解過程，并通過實例驗證了算法的有效性.基于矩陣編碼的改進遺傳算法，在求解類似元件分配組合優化問題中表現出了較好的尋優能力，同時此方法也可以應用于PCB分配優化問題求解，對此方法進行有效的拓展使用，可以很好地解決很多工程實際問題，具有一定的應用研究價值.

［1］ Ho W，Ji P.Optimal Production Planning for PCB Assembly［M］.London：Springer，2007.

［2］ 靳志宏.印刷電路板組裝生產線調度優化問題建模［J］.中國管理科學，2008，16：122－127.

［3］ 劉海明，袁 鵬，羅家祥，等.表面組裝生產線的負荷平衡優化算法研究［C］.Proceedings of the 32nd Chinese Control Conference，July 26－28，2013，Xi＇an，China.2585－2590.

［4］ 郭妹娟，靳志宏.表面組裝技術生產線貼片機負荷均衡優化［J］.計算機集成制造系統，2009，15（4）：817－822.

［5］ 王 君，羅家祥，胡躍明.基于混合搜索算法的貼片機貼裝過程優化［J］.計算機測量與控制，2011，19（3）：603－605.

［6］ 路軍營，朱光宇.基于灰熵關聯分析的表面貼裝多目標優化［J］.計算機集成制造系統，2013，19（4）：766－772.

［7］ 張 屹，萬興余，鄭小東，等.基于改進元胞多目標遺傳算法的機床主軸優化［J］.計算機工程與應用，2013（7）：31.

［8］ 李 超.裝備制造企業物流運輸成本的控制研究［D］.西安：西安科技大學，2011.

［9］ 王 君，羅家祥，胡躍明.基于改進蟻群算法的貼片機貼裝過程優化［J］.計算機工程，2011，37（14）：256－258.

［10］曾又姣，金 燁.基于遺傳算法的貼片機貼裝順序優化［J］.計算機集成制造系統，2004，10（2）：205－208.

［11］李軍華，黎 明.元胞遺傳算法的收斂性分析和收斂速度估計［J］.模式識別與人工智能，2012，25（5）：874－878.