基于差分算法的貼裝順序優(yōu)化問題求解

朱光宇，羅 哲，陳志錦

（福州大學 機械工程及自動化學院，福建 福州 350002）

當今電子元器件的封裝技術迅速向小型化、微型化、片式化、高性能方向發(fā)展［1］，而傳統(tǒng)通過人工插件組裝的方式在印刷電路板（Printed Circuit Board，PCB）上安裝元器件的方法已經遠遠不能適應于當今的要求.由于表面貼裝技術（SMT）的先進性，已被廣泛使用于工業(yè)生產中，而其中的拱架型多頭貼片機又由于其適用元器件的范圍最廣且最具柔性而得到廣泛應用［2－4］.拱架型多頭貼片機的高效運行已經成為制約該類設備發(fā)展的關鍵所在，而其高效運行又可歸結為一種典型的表面貼裝工藝優(yōu)化問題，主要包括供料器位置分配優(yōu)化、元器件取料順序優(yōu)化、元器件貼放順序優(yōu)化［5－6］3個子問題，而這些問題均屬于NP（Nondeterministic Polynomial）問題，具有高維數(shù)、離散和非線性的特點.

眾多學者針對表面貼裝工藝優(yōu)化問題開展研究，主要是利用多種智能型優(yōu)化算法來解決拱架型多頭貼片機貼裝的優(yōu)化問題［7－8］，如遺傳算法（GA）［9－10］、粒子群算法［11］等.文獻［12］在給定元器件取料順序和貼放順序的前提下，利用遺傳算法解決了供料器分配的優(yōu)化問題.文獻［3］提出了一種以正負數(shù)為符號的染色體編碼方式的遺傳算法對供料器位置分配進行了優(yōu)化，實驗表明該算法取得了有效的優(yōu)化結果.文獻［11］在分析了表面貼裝過程調度問題特征的基礎上，提出了一種離散粒子群優(yōu)化算法對供料器位置和取料順序進行了優(yōu)化.文獻［13］提出了一種以作者名字第一個字母命名的基因遺傳算法（LBM-GA）來優(yōu)化供料器位置分配和元件的取料順序.文獻［14］用神經網(wǎng)絡算法來求解元器件貼放順序的優(yōu)化問題.此外，元器件貼裝順序優(yōu)化問題的求解方法還有模擬退火算法［15］等.

雖然文獻［3］和文獻［12］應用遺傳算法或改進的遺傳算法在解決貼片機貼裝的優(yōu)化問題中取得了較為滿意的結果，但無法擺脫遺傳算法本身所具有過早收斂的局限性［16］.鑒于這種情況，本文提出了應用差分算法來解決拱架型多頭貼片機取料、貼放的優(yōu)化問題.差分算法（Differential Evolution，DE）的主要應用領域為函數(shù)優(yōu)化、組合優(yōu)化、神經網(wǎng)絡訓練［17］及其他進化算法常用的應用領域.文獻［18］和文獻［19］應用DE算法在求解旅行商問題、布局優(yōu)化、圖形劃分問題等具有NP難度的問題上獲得了成功.因此，將DE算法應用于SMT的貼裝順序優(yōu)化問題具有十分廣闊的前景.本文針對上述情況，以貼片機取料、貼放時間為研究對象，建立了以取料、貼放總時間為優(yōu)化目標的數(shù)學模型，對DE進行改造，使其適應于表面貼裝工藝優(yōu)化問題，并進一步改進差分算法，建立帶遷徙操作的差分算法（Differential Evolution with Migration，MDE）.通過實驗選擇DE算分的參數(shù)，將DE，MDE，GA算法進行比較.

1 PCB取、貼順序描述及數(shù)學模型

1.1 問題描述

拱架型多頭貼片機主要由放置PCB的工作臺、供料槽、供料器、貼片頭、吸嘴等組成，其結構如圖1所示.貼片機表面貼裝優(yōu)化中的貼片工藝過程如下［20］：首先，裝有元器件的各供料器擺放在貼片機供料槽的不同位置，PCB通過輸送帶被輸送到貼片機并固定下來，貼片頭上的吸嘴依次或同時在取料點吸取供料器中的元器件，通過視覺檢測后，貼片頭移到PCB上的相應位置，依次貼放這些元器件，然后返回取料點再次取料.這樣一次取料、貼放操作過程稱為一個取、貼循環(huán)，如此循環(huán)取、貼，直到所有元器件取、貼完畢.通過上述貼片工藝可知，影響貼裝效率的主要因素便是貼裝元器件的取料、貼放順序，因此合理地安排貼裝元器件的取料、貼放循環(huán)順序，便能夠減少貼裝過程的總體時間，進而提高貼裝效率.

圖1 拱架式多頭貼片機結構示意圖Fig.1 Example of gantry surface mounting machine

1.2 模型建立

通過分析可以看出PCB貼片工藝的優(yōu)化是一個非常復雜的問題，而且也會增加模型的求解難度.因此，為建立一個合適的數(shù)學模型，必須簡化一些不必要的環(huán)節(jié).本文假設①貼片頭的運動為均勻運動；②貼片頭每次取料、視覺檢查及貼放所耗費的時間為恒定值；③每種元件只對應一種吸嘴.設t1為貼片頭每次上下運動完成取料或貼放所耗費的時間；t2（i）為第i次循環(huán)中吸嘴更換所需的時間；t3（i）為第i次循環(huán)中貼片頭在供料器上完成這輪取料移動所用的時間；t4（i）為第i次循環(huán)中貼片頭從某一取料點移動到PCB，并完成這輪元件貼放過程中移動所用的時間；tij為貼片頭從取、貼循環(huán)i最后一個貼放點移動到取、貼循環(huán)j第一個取料點移動所用的時間；xi，j用于判斷取貼循環(huán)i，j是否相鄰（相鄰取1，否者取0）；n為PCB總的元器件數(shù)；L為取、貼循環(huán)的總次數(shù).則元器件貼裝順序用時間來表示的目標函數(shù)及約束條件如下：

其中：

式（2）—（5）保證每個取、貼循環(huán)有且僅有一次.

2 DE算法在貼片機取、貼順序優(yōu)化中的應用

2.1 解的表現(xiàn)形式

在表面貼裝優(yōu)化中，元器件的取料、貼放順序是離散的，本文利用元器件編號的順序編碼來表達取、貼順序，即解的表現(xiàn)形式是取料、貼放順序的整數(shù)編碼，每個碼位值是PCB上一個元器件的整數(shù)編碼.

首先對PCB上所有的元器件進行編碼，假設一塊PCB上共有n個m類型的元件，貼片機有f個供料槽｛s1，s2，…，sf｝，對n個元件依次進行編碼：｛1，2，…，n｝，用｛c1，c2，…，cm｝分別表示m種類型的元件，則元件、類型、供料槽的對應關系為：｛1，2，…，n｝→｛c1，c2，…，cm｝→｛s1，s2，…，sf｝，其中m≤f≤n，即每種類型元件（也即裝載這種元件的供料器）安放在某個或某幾個供料槽上，那么只要知道了要貼裝的元件代碼i（i∈（1，2，…，n）），通過這種對應關系就可以知道元件的類型以及它所在的供料槽.

例如用拱架型4頭貼片機貼裝12個元件，有關系如下：

2.2 帶遷徙操作的DE算法

DE算法的關鍵步驟是變異操作，而變異操作是基于群體的差異向量信息來修正各個體的值，隨著進化代數(shù)的增加，各個體之間的差異化信息在逐漸縮小，導致后期收斂速度變慢，甚至有時會陷入局部最優(yōu)解.因此，本文在原有DE算法的基礎上提出MDE算法，即在算法搜索過程中引入遷徙操作，在保持個體優(yōu)良性的同時增大了種群的多樣性.

遷徙操作的主要思想是：當?shù)螖?shù)達到總迭代次數(shù)τ的1/4時，保留當下目標函數(shù)值較好的前半部分群體，作為種群1，然后重新開始迭代，當?shù)螖?shù)達到總迭代次數(shù)τ的1/2時，保留當下目標函數(shù)值較好的前半部分群體，作為種群2，綜合種群1和種群2，繼續(xù)迭代下去，直到達到總迭代次數(shù)τ，其目的是增加種群多樣性，以此來跳出局部最優(yōu)解，從而得到了更優(yōu)解.

2.3 算法流程及實現(xiàn)方式

在算法運行前需設定的參數(shù)為：種群規(guī)模數(shù)N，縮放因子η，交叉概率C及進化過程的總迭代次數(shù)τ，面向貼裝優(yōu)化問題的MDE算法流程如下：

（8）遷徙進化進程3.利用種群3，重復（1）至（4），直至種群3的迭代次數(shù)t＝τ時算法終止.

（9）檢測算法終止條件t＝τ.若滿足終止條件，則轉入（10），否則轉入（2）.

3 實驗分析

本文使用MATLAB軟件實現(xiàn)算法，實驗以有4個貼片頭的拱架型貼片機為試驗對象，貼片機槽位總數(shù)為80，貼裝循環(huán)中貼片頭的移動速度為v＝1 000mm·s－1，測試的對象為A，B兩塊PCB，其中A板面積為137mm×91mm，B板面積為230mm×152mm，A板包含6類元件：15個電阻（R）類、11個連接器（U）類、4個集成電路（IC）類、10個三極管（RL）類、5個可控硅（IR）類、15個電容（C）類元件，分配貼片頭1取、貼R類，貼片頭2取、貼U，IC類，貼片頭3取、貼RL，IR類，貼片頭4取、貼C類元器件.B板包含7類元件：29個RL類、19個IR類、36個C類、19個IC類、11個電感器（IV）類、12個U類、42個二極管（OR）類元件，分配貼片頭1取、貼RL，IR類，貼片頭2取、貼RL，C類，貼片頭3取、貼IC，IV，U類，貼片頭4取、貼OR類元器件，使得各貼片頭的負載盡量均衡.

3.1 算法參數(shù)對算法的影響

DE算法包含3個參數(shù)，本文采用在3個參數(shù)中保持2個參數(shù)不變、改變另一個參數(shù)的情況下對A，B板進行實驗，以確定較佳的算法參數(shù).實驗中，A，B板的N，η，C作為不變參數(shù)時分別設為50，0.5，0.5和75，0.5，0.5，所用的實驗迭代次數(shù)均為400次，每次實驗獨立運行20次，實驗分為3個過程：①η，C保持不變，參數(shù)N分別取25，50，75，100，125，150；②η，N保持不變，參數(shù)C分別取0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9；③C，N保持不變，參數(shù)η分別取0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9.A，B板按照上述過程20次優(yōu)化結果平均最優(yōu)值依次如圖2所示.

圖2 實驗A，B板時算法參數(shù)對性能的影響Fig.2 Influence of algorithm parameter to performance for testing A and B board.

實驗結果表明：①種群N的選擇跟優(yōu)化對象的規(guī)模相關，一般來說元器件數(shù)量大的優(yōu)化問題，種群相應增大，能夠得到較好的優(yōu)化結果，但種群大到一定程度后優(yōu)化結果反而會隨種群的增大而減少；②交叉參數(shù)C的選擇不宜過小，大于0.4的值較好；③縮放因子η選擇在0.4～0.8的范圍內較好.

3.2 DE，MDE，GA算法的比較

分別將DE，MDE，GA算法采用相同隨機初始值，對A，B板的貼裝工藝進行優(yōu)化，各運行20次優(yōu)化實驗，記錄下3種算法每次的最優(yōu)貼裝時間并求平均值.DE，MDE算法中，C＝0.7，η＝0.8，最大迭代步數(shù)τ＝600；GA算法中，C＝0.5，變異概率為0.08，最大迭代步數(shù)τ＝600，實驗結果如圖3、表1所示.

圖3 A，B板三種算法20次平均最優(yōu)值的迭代過程Fig.3 Iteration process of optimal value to 20times′ means for three algorithm of A and B board

表1 三種算法計算結果比較Tab.1 Comparation of results for three algorithm

從圖3中可以看出DE，MDE算法的收斂速度明顯較GA算法快，在迭代到300步時，由于遷徙操作的使用，MDE平均最優(yōu)值出現(xiàn)階躍下降，表明遷徙操作能夠顯著地使DE算法跳出局部最優(yōu)解.同時，從表1可知，針對兩個不同實驗對象，DE，MDE的平均最優(yōu)值、最佳最優(yōu)值要好于GA算法的結果.MDE的平均最優(yōu)值要好于DE的結果，表明遷徙操作使算法有更多機會收斂到最優(yōu)解.本文所采用的DE算法較GA算法的優(yōu)化結果要好，優(yōu)化質量要高，且隨著PCB元件數(shù)量越多優(yōu)化結果越好，但由于實驗的PCB元器件之間的間距較小，且板面本身面積較小，因此提高的比率較少.

4 結語

本文探討利用DE算法及其改進后的帶遷徙操作的DE算法對貼片機貼裝工藝進行優(yōu)化，解決了拱架型多頭貼片機的元器件取、貼優(yōu)化問題.通過實驗表明，DE算法、MDE算法能夠有效地解決拱架型多頭貼片機元器件的取料、貼放優(yōu)化問題，優(yōu)化結果較GA算法明顯好.本文所建立的DE算法流程能夠滿足貼片機取料、貼放順序優(yōu)化的需求，而且對其他離散優(yōu)化問題具有借鑒意義.

［1］王英章.高精高速微孔PCB數(shù)控鉆床關鍵技術的研究與應用［D］.重慶：重慶大學，2005.

WANG Yingzhang.Study and application of some key techniques of high accuracy and high speed PCB NC drilling machine［D］.Chongqing：Chongqing University，2005.

［2］AYOBM，KENDALL G.A survey of surface mount device placement machine optimization：machine classification［J］.European Journal of Operational Research，2008，186（3）：893－914.

［3］LI Shaoyuan，HU Chaofang，TIAN Fuhou.Enhancing optimal feeder assignment of the multi-head surface mounting machine using genetic algorithms［J］.Applied Soft Computing，2008，8（1）：522－529.

［4］ELLISS K P，VITES F J，KOBZA J E.Optimizing the performance of a surface mount placement machine［J］.Transactions on Electronice Packaging Manufacturing，2002，24（3）：160－170.

［5］SUNA D S，LEEA T E，KIM K H.Component allocation and feeder arrangement for a dual-gantry multi-head surface mounting placement tool［J］.Production Economics，2005，95：245－264.

［6］ALTINKEMER K，KAZAZ B，KOKSALAN M，et al.Optimization of printed circuit board manufacturing：integrated modeling and algorithms［J］.European Journal of Operational Research，2002，124（2）：409－421.

［7］KUMAR R，SENIOR，LUO Z H.Optimizing the operation sequence of a chip placement machine using TSP model［J］.IEEE Transactions on Electronics Packaging Manufacturing，2003，26（1）：14－21.

［8］KENDALL M A G.Real-time scheduling for multi headed art placement machine［C］∥Proceedings of the IEEE International Symposium on Assembly and Task Planning.Piscataway，New Jersey：IEEE，2003：128－133.

［9］EILLIAM H，PING J I.Component scheduling for chip shooter machines：a hybrid genetic algorithm approach［J］.Computers ＆Operations Research，2003，30（14）：2175－2189.

［10］OONG N S，KHOO L P.Sequence placement planning high-speed PCB assembly machine［J］.Integrated Manufacturing Systems，2002，13（1）：35－46.

［11］伍楷舜，郝井華，劉民，等.表面貼裝過程調度問題的粒子群優(yōu)化算法［J］.控制工程，2007，14（2）：132－139.

WU Kaishun，HAO Jinghua，LIU Min，et al.Particle swarm optimization algorithm for scheduling problem of surface mounting process［J］.Control Engineering of China，2007，14（2）：132－139.

［12］田福厚，李少遠.貼片機喂料器分配的優(yōu)化及其遺傳算法求解［J］.控制與決策，2005，20（8）：955－960.

TIAN Fuhou，LI Shaoyuan.Optimization of feeder assignment using genetic algorithms in surface mounting machine［J］.Control and Decision，2005，20（8）：955－960.

［13］TECK S L，SATISH T S B，DEBORAH M，et al.A genetic algorithm for sequential part assignment for PCB assembly［J］.Computer ＆Industrial Engineering，2001，40：293－307.

［14］SU Y Y，SRIHARI K.Placement sequence identification using neural networks in surface mount PCE assembly［J］.International Journal of Advance Manufacturing Technology，1996，11（4）：285－290.

［15］TIPAK T M，NELSON P C，ASWANI A J.Optimization of revolver head SMT machine using adaptive simulated annealing（ASA）［C］∥Twenty-Sixth IEEE/CPMT International，Electronics Manufacturing Technology Symposium.Santa Clara，CA：IEEE Service，2000：214－220.

［16］劉智明，賀新，周激流，等.基于排序的改進自適應遺傳算法［J］.信息與控制，2001，33（1）：6－8.

LIU Zhiming，HE Xin，ZHOU Jiliu，et al.Study on improved adaptive genetic algorithm based on ranking［J］.Information and Control，2001，33（1）：6－8.

［17］王雪松，程玉虎.一種基于時間差分算法的神經網(wǎng)絡預測控制系統(tǒng)［J］.信息與控制，2001，33（5）：531－535.

WANG Xuesong，CHENG Yuhu.A neural network-based predictive control system with temporal differences method［J］.Information and Control，2004，33（5）：531－535.

［18］CHANGC S，DU D.Further improvement of optimization method for mass transit signaling B lock-layout design using differential evolution［J］.IEEE Proceedings on Electric Power Applications，1999，146（5）：559－569.

［19］STORN R，PRICE K.Differential evolution——a simple and efficient adaptive scheme for global optimization over continuous spaces［R］.Berkeley：University of California，1995.

［20］朱光宇.模因內三角概率選擇混合蛙跳算法［J］.計算機集成制造系統(tǒng)，2009，15（10）：1979－1985.

ZHU Guangyu.Meme triangular probability distribution shuffled frog-leaping algorithm［J］.Computer Integrated Manufacturing Systems，2009，15（10）：1979－1985.