基于矩陣編碼遺傳算法的PCB生產(chǎn)線元件分配優(yōu)化

杜 軒 李登橋 朱 康

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

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

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

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

1 PCB生產(chǎn)線元件分配問題描述及優(yōu)化模型建立

1.1 PCB生產(chǎn)線元件分配問題描述

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

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

1.2 元件分配優(yōu)化模型

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

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

目標函數(shù)式是使生產(chǎn)線上耗時最長設備的組裝時間最小化.

2 遺傳算法求解與實現(xiàn)

2.1 染色體編碼

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

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

2.2 種群初始化

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

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

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

增加一個約束條件：

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

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

2）從集合δ＝（1，2，…，m×n）中隨機選擇一個數(shù)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），直到集合δ為空，這樣就產(chǎn)生了問題的一個可行解，即一條染色體.

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

2.3 適應度函數(shù)及選擇

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

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

2.4 交叉與變異

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

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

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

3 算法實現(xiàn)及優(yōu)化實例

3.1 實例分析

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

圖2 實例數(shù)據(jù)圖

3.2 算法實現(xiàn)步驟

采用改進的遺傳算法，其具體實現(xiàn)步驟：

1）設置遺傳算法（GA）參數(shù).主要包括種群大?。≒size）、遺傳代數(shù)（Count）、交叉概率（Pc）和變異概率（Pm）.

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

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

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

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

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

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

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

3.3 求解結(jié)果及分析

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

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

圖3 PCB組裝生產(chǎn)線元件分配優(yōu)化收斂圖

最終得到的最優(yōu)化結(jié)果為99.5s.元件分配結(jié)果為

4 結(jié) 論

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

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

［2］ 靳志宏.印刷電路板組裝生產(chǎn)線調(diào)度優(yōu)化問題建模［J］.中國管理科學，2008，16：122－127.

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

［4］ 郭妹娟，靳志宏.表面組裝技術(shù)生產(chǎn)線貼片機負荷均衡優(yōu)化［J］.計算機集成制造系統(tǒng)，2009，15（4）：817－822.

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

［6］ 路軍營，朱光宇.基于灰熵關(guān)聯(lián)分析的表面貼裝多目標優(yōu)化［J］.計算機集成制造系統(tǒng)，2013，19（4）：766－772.

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

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

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

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

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