朱光宇，羅 哲，陳志錦

（福州大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院，福建 福州 350002）

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

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

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

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

1.1 問題描述

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

圖1 拱架式多頭貼片機(jī)結(jié)構(gòu)示意圖Fig.1 Example of gantry surface mounting machine

1.2 模型建立

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

其中：

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

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

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

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

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

例如用拱架型4頭貼片機(jī)貼裝12個(gè)元件，有關(guān)系如下：

2.2 帶遷徙操作的DE算法

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

DE算法包含3個(gè)參數(shù)，本文采用在3個(gè)參數(shù)中保持2個(gè)參數(shù)不變、改變另一個(gè)參數(shù)的情況下對(duì)A，B板進(jìn)行實(shí)驗(yàn)，以確定較佳的算法參數(shù).實(shí)驗(yàn)中，A，B板的N，η，C作為不變參數(shù)時(shí)分別設(shè)為50，0.5，0.5和75，0.5，0.5，所用的實(shí)驗(yàn)迭代次數(shù)均為400次，每次實(shí)驗(yàn)獨(dú)立運(yùn)行20次，實(shí)驗(yàn)分為3個(gè)過程：①η，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)化結(jié)果平均最優(yōu)值依次如圖2所示.

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

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

3.2 DE，MDE，GA算法的比較

分別將DE，MDE，GA算法采用相同隨機(jī)初始值，對(duì)A，B板的貼裝工藝進(jìn)行優(yōu)化，各運(yùn)行20次優(yōu)化實(shí)驗(yàn)，記錄下3種算法每次的最優(yōu)貼裝時(shí)間并求平均值.DE，MDE算法中，C＝0.7，η＝0.8，最大迭代步數(shù)τ＝600；GA算法中，C＝0.5，變異概率為0.08，最大迭代步數(shù)τ＝600，實(shí)驗(yàn)結(jié)果如圖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 三種算法計(jì)算結(jié)果比較Tab.1 Comparation of results for three algorithm

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

4 結(jié)語

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

［1］王英章.高精高速微孔PCB數(shù)控鉆床關(guān)鍵技術(shù)的研究與應(yīng)用［D］.重慶：重慶大學(xué)，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］伍楷舜，郝井華，劉民，等.表面貼裝過程調(diào)度問題的粒子群優(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］田福厚，李少遠(yuǎn).貼片機(jī)喂料器分配的優(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ìn)自適應(yīng)遺傳算法［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］王雪松，程玉虎.一種基于時(shí)間差分算法的神經(jīng)網(wǎng)絡(luò)預(yù)測控制系統(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］朱光宇.模因內(nèi)三角概率選擇混合蛙跳算法［J］.計(jì)算機(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.