基于RLS的用于貼片機(jī)貼裝順序優(yōu)化的禁忌搜索算法*

羅家祥 羅樹浩 吳忻生

(華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣東廣州510640)

表面貼裝技術(shù)是一種無需在印制電路板(PCB)上鉆插裝孔，而直接將表面貼裝元器件貼到PCB上，然后用焊料使元器件與PCB構(gòu)成機(jī)械和電氣連接的電子組裝技術(shù)．在PCB的組裝過程中，元器件的貼裝是整條生產(chǎn)線生產(chǎn)效率的關(guān)鍵環(huán)節(jié)，是生產(chǎn)線上的“瓶頸”．

為減少將電子元器件貼裝到PCB上所耗費(fèi)的時(shí)間，提高生產(chǎn)效率，表面貼裝技術(shù)的優(yōu)化受到越來越多的關(guān)注．單臺(tái)貼片機(jī)的貼裝優(yōu)化一般存在兩個(gè)相關(guān)但仍然有一定獨(dú)立性的子問題［1］:1)喂料器的位置分配問題，確定不同類型的元器件喂料器在喂料槽上的安放位置;2)元器件的貼裝順序優(yōu)化問題，確定元器件的拾取和貼裝順序．前者通常被認(rèn)為是一個(gè)二次分配問題(QAP)［2］，后者被認(rèn)為是非對(duì)稱的旅行商問題(TSP)，均屬于NP難的組合優(yōu)化問題．文中主要研究元器件的貼裝順序優(yōu)化問題，即在喂料器安放位置確定的情況下，對(duì)元器件的拾取順序與貼裝順序進(jìn)行優(yōu)化，使得貼裝過程中貼裝頭移動(dòng)的總路徑最短．對(duì)該問題求解方法的研究主要集中在遺傳算法和其它一些啟發(fā)式算法．文獻(xiàn)［3］中提出了具有獨(dú)特的染色體編碼解碼方式和交叉算子的遺傳算法，該算法能有效解決元器件的貼裝順序問題．文獻(xiàn)［4］中將一種二維符號(hào)編碼方法應(yīng)用到遺傳算法中，實(shí)現(xiàn)了轉(zhuǎn)塔式貼片機(jī)的元器件貼裝順序和喂料槽分配的同時(shí)優(yōu)化．文獻(xiàn)［5］中針對(duì)貼裝順序優(yōu)化問題建立了以貼裝總時(shí)間為最小的數(shù)學(xué)模型，使用改進(jìn)混合蛙跳算法來求解，結(jié)果表明該算法比遺傳算法具有更好的收斂性．文獻(xiàn)［6］在文獻(xiàn)［5］的混合蛙跳算法的基礎(chǔ)上，把混合蛙跳算法與蟻群算法相融合，實(shí)現(xiàn)對(duì)貼片機(jī)的元件貼裝順序優(yōu)化問題的求解，測(cè)試結(jié)果表明混合算法取得了更小的目標(biāo)函數(shù)值．此外，元器件貼裝順序優(yōu)化問題的求解方法還有傘布搜索算法［7］等．

雖然遺傳算法已被廣泛用于求解元器件貼裝順序優(yōu)化及其它復(fù)雜工業(yè)問題的優(yōu)化［8］，但遺傳算法具有過早收斂等局限性．為尋求更好的優(yōu)化結(jié)果，文中采用基于禁忌搜索的優(yōu)化算法對(duì)該問題進(jìn)行求解．

首先，針對(duì)該優(yōu)化問題建立數(shù)學(xué)規(guī)劃模型，該模型考慮了貼裝過程中貼裝頭的移動(dòng)路徑長度受貼裝頭間距的影響，并提出根據(jù)元器件的拾取路徑求取對(duì)應(yīng)最小貼裝路徑的方法．然后，分析了解序列的常見鄰域變換方法對(duì)貼裝頭運(yùn)動(dòng)路徑的影響，并據(jù)此選擇了交換鄰域結(jié)構(gòu);設(shè)計(jì)了包括禁忌移動(dòng)和禁忌歷史局部最優(yōu)解的雙禁忌表，避免迭代過程中相同解序列的重復(fù)更新，增強(qiáng)算法避免迂回搜索的能力;引入了基于取貼循環(huán)插入移動(dòng)的RLS策略，參照某個(gè)參考序列來搜索以取貼循環(huán)為單位的改進(jìn)的插入移動(dòng)．最后，通過實(shí)驗(yàn)驗(yàn)證所提算法的有效性．

1 問題描述及數(shù)學(xué)模型

1．1 問題描述

文中研究的拱架式貼片機(jī)組成包括機(jī)架、喂料槽、喂料器、拱架、貼裝頭、吸嘴和視覺識(shí)別攝像機(jī)等，如圖1所示．

圖1 拱架式貼片機(jī)結(jié)構(gòu)示意圖Fig．1 Schematic diagram of surface mounting machine with overhead－gantry

同一類型的元器件一般放在相同的喂料槽上．貼片機(jī)貼裝元器件的流程如下:

(1)傳送帶將PCB送到工作位置并夾緊固定;

(2)貼裝頭移動(dòng)到喂料槽位置，同時(shí)或依次拾取指定的H(貼裝頭個(gè)數(shù))個(gè)元器件;

(3)帶著元器件的貼裝頭經(jīng)過視覺檢測(cè)區(qū)后，移動(dòng)到工作臺(tái)上，將元器件按指定順序貼裝到PCB上的待貼裝位置;

(4)返回步驟(2)，直至PCB上的元器件貼裝完畢．

從貼裝元器件的流程可知，不同元器件的貼裝順序?qū)?yīng)不同長度的貼裝路徑．在視覺檢測(cè)時(shí)，貼裝頭的移動(dòng)距離基本固定．因此元器件的取貼順序是影響貼裝效率的主要因素，是提高貼裝效率的要點(diǎn)．步驟(2)和(3)實(shí)現(xiàn)了拾取和貼裝H個(gè)元器件的過程，稱為一個(gè)取貼循環(huán)．一個(gè)取貼循環(huán)包括拾取H個(gè)元器件、貼裝H個(gè)元器件和返回下一個(gè)循環(huán)第一個(gè)元器件的拾取位置，如圖2所示．

圖2 一個(gè)取貼循環(huán)Fig．2 A picking and mounting cycle

文中擬將待貼裝的元器件組成取貼循環(huán)，確定取貼循環(huán)順序和每個(gè)循環(huán)內(nèi)的元器件拾取及貼裝順序，最小化貼裝頭在貼裝過程中移動(dòng)的總路徑．

1．2 數(shù)學(xué)模型

貼裝頭在貼裝過程中移動(dòng)的總路徑由多個(gè)取貼循環(huán)組成，每個(gè)取貼循環(huán)中又包括了拾取、貼裝元器件等多個(gè)階段．貼裝過程中的視覺檢測(cè)不是貼裝效率的主要影響因素，所以在優(yōu)化時(shí)不給予考慮．在已知喂料器位置的前提下，元器件的拾取位置和待貼裝位置均為已知條件．不失一般性，設(shè)待貼裝元器件個(gè)數(shù)n為貼裝頭個(gè)數(shù)H的整數(shù)倍．最大限度利用貼裝頭時(shí)，取貼循環(huán)個(gè)數(shù)為N=n/H．設(shè)J為待貼裝的元器件集合，J={1，2，…，n};S為元器件拾取順序，S=(S1，S2，…，Sk，…，SN)，Sk為第 k(k=1，2，…，N)個(gè)取貼循環(huán)中的元器件拾取順序，Sk=(sk，1，sk，2，…，sk，H)，該循環(huán)內(nèi)貼裝順序?yàn)?Πk=(πk，1，πk，2，…，πk，H);所有貼裝順序?yàn)?Π =(Π1，Π2，…，Πk，…，ΠN); 集 合 {sk，1，sk，2，…，sk，H} ={ πk，1，πk，2，…，πk，H}，即兩個(gè)集合包含的元器件相同;二維向量Ai、Bi分別為元器件i所在喂料器位置及其在PCB上的貼裝位置在直角坐標(biāo)系中的坐標(biāo);Δd為相鄰貼裝頭的間距;dkj為第k個(gè)取貼循環(huán)中貼裝頭拾取第j與第 j+1(j=1，2，…，H －1)個(gè)元器件所移動(dòng)的距離;gk為第k個(gè)取貼循環(huán)中貼裝頭拾取第H個(gè)元器件后移動(dòng)到貼裝PCB上本循環(huán)的第一個(gè)元器件所移動(dòng)的距離;Dkj為第k個(gè)取貼循環(huán)中貼裝頭貼裝第j(j=1，2，…，H－1)與第j+1個(gè)元器件所移動(dòng)的距離;bk為貼裝頭在第k個(gè)取貼循環(huán)中貼裝第H個(gè)元器件后至拾取第k+1個(gè)循環(huán)的第1個(gè)元器件所移動(dòng)的距離;mk，j為第k個(gè)取貼循環(huán)中第j個(gè)貼裝元器件所在的貼裝頭．則建立的數(shù)學(xué)模型如下:

其中，· 為距離函數(shù)．目標(biāo)函數(shù)(1)包括拾取元器件路徑、從喂料槽到達(dá)PCB的路徑、貼裝元器件的路徑和從PCB回到喂料槽的路徑．約束(2)－(5)分別為 dkj、gk、Dkj、bk的計(jì)算式．上述模型考慮了貼裝頭的間距，更接近于實(shí)際貼裝生產(chǎn)．在計(jì)算貼裝頭移動(dòng)距離時(shí)，對(duì)每次移動(dòng)的起始位置坐標(biāo)進(jìn)行補(bǔ)償，而不是將相鄰拾取或貼裝的兩個(gè)元器件之間的坐標(biāo)距離作為移動(dòng)距離，如圖3所示．

圖3 考慮貼裝頭間距時(shí)的移動(dòng)距離Fig．3 Moving distance considering the space between heads

上述模型所描述的元器件拾取與貼裝過程可看成一個(gè)特殊的TSP問題，因此所研究的優(yōu)化問題為NP難問題．

2 求解方法

禁忌搜索(TS)算法首先由 Glover［9］提出，通過引入一個(gè)存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，保證了多樣的有效搜索，已成功地解決了各類經(jīng)典的優(yōu)化問題．文中從TS算法的組成要素入手，結(jié)合貼片機(jī)貼裝順序優(yōu)化問題的特點(diǎn)，提出了一種基于參考解的局部搜索(RLS)的改進(jìn)TS算法，設(shè)計(jì)了包括傳統(tǒng)禁忌表與歷史解禁忌表的雙禁忌表來避免迂回搜索，以提高搜索的多樣性．同時(shí)設(shè)計(jì)了基于取貼循環(huán)插入移動(dòng)的RLS局部搜索策略，以提高算法的搜索性能．

2．1 解的表達(dá)形式及特點(diǎn)

一個(gè)取貼循環(huán)主要包括拾取和貼裝兩個(gè)過程，顯然元器件的拾取順序與貼裝順序是不一定相同的．在模型描述中，已用 S=(S1，S2，…，Sk，…，SN)和 Π =(Π1，Π2，…，Πk，…，ΠN)表示取貼循環(huán)中的元器件拾取序列和貼裝序列，兩者可進(jìn)一步分別用長序列 S=(s1，s2，…，sH，…，sH(k－1)+1，…，sHk，…，sn)和 Π =(π1，π2，…，πH，…，πH(k－1)+1，…，πHk，…，πn)表示，并滿足{sH(k－1)+1，…，sHk}={πH(k－1)+1，…，πHk}的條件，表示第k個(gè)取貼循環(huán)內(nèi)拾取的元器件與貼裝的元器件相同．

對(duì)于第k個(gè)取貼循環(huán)中貼裝順序Πk的改變，只影響本循環(huán)的路徑總長度，不影響其它循環(huán)．因此，可以在不影響其它循環(huán)的前提下，尋找一個(gè)循環(huán)內(nèi)的最優(yōu)貼裝順序，使得本循環(huán)的貼裝總路徑長度最?。赟k確定的條件下，最優(yōu)的Πk為:以本循環(huán)拾取的最后一個(gè)元器件sHk為起點(diǎn)、下一循環(huán)拾取的第一個(gè)元器件sHk+1為終點(diǎn)共H+2個(gè)城市的小規(guī)模TSP問題的解，如圖4所示．

圖4 單循環(huán)內(nèi)最優(yōu)貼裝順序Fig．4 Optimal mounting sequence in a single cycle

因此，求解所研究的優(yōu)化問題可集中在拾取序列S，而S對(duì)應(yīng)的貼裝順序可通過若干個(gè)小規(guī)模的TSP問題的求解獲得．貼裝順序的求解可在計(jì)算對(duì)應(yīng)拾取序列的目標(biāo)值時(shí)進(jìn)行．

2．2 初始解的產(chǎn)生

文中基于最近鄰的啟發(fā)式方法［10］來獲取拾取順序的初始解．按最近鄰原則，分3個(gè)階段逐步確定當(dāng)前取貼循環(huán)內(nèi)的元器件拾取順序、當(dāng)前循環(huán)內(nèi)的元器件貼裝順序、下一循環(huán)拾取的第一個(gè)元器件．設(shè)Ω=J={1，2，…，n}，為待拾取的元器件集合，第 k個(gè)循環(huán)內(nèi)的元器件拾取順序?yàn)?Sk=(sH(k－1)+1，sH(k－1)+2，…，sHk)，貼裝順序?yàn)?Πk=(πH(k－1)+1，πH(k－1)+2，…，πHk)，c1，i，j為貼裝頭從拾取元器件 i移動(dòng)到拾取元器件 j所經(jīng)過的距離．c2，i，j為貼裝頭在PCB上從貼裝元器件i移動(dòng)到貼裝元器件j所經(jīng)過的距離;c3，i，j為貼裝頭從拾取元器件 i移動(dòng)到貼裝元器件j所經(jīng)過的距離;c4，i，j為貼裝頭從貼裝元器件 i移動(dòng)到拾取元器件 j所經(jīng)過的距離．c1，i，j、c2，i，j、c3，i，j、c4，i，j(i，j=1，2，…，n)可通過已知喂料器和貼裝點(diǎn)的坐標(biāo)計(jì)算得到．產(chǎn)生初始解的具體步驟描述如下:

(1)令 k:=1，在 Ω 中任意選擇元器件 i，sH(k－1)+1:=i，Ω:= Ω /{i};

(2)對(duì)所有 h(h=2，3，…，H)，在 Ω 中選擇 i=

(4)對(duì)所有 h(h=2，3，…，H)，在 Ψ 中選擇 i=

2．3 鄰域

交換、插入、2－opt和 3－opt是常見的鄰域結(jié)構(gòu)，常應(yīng)用于搜索算法中．當(dāng)對(duì)解序列中的1個(gè)或2個(gè)元器件移動(dòng)時(shí)，插入、2－opt和3－opt移動(dòng)會(huì)使得多個(gè)取貼循環(huán)發(fā)生改變，導(dǎo)致當(dāng)前解結(jié)構(gòu)產(chǎn)生較大變化，搜索的隨機(jī)性太強(qiáng)．因此，文中算法采用交換鄰域．在解序列中選擇兩點(diǎn)，然后交換在解序列中的位置，得到一個(gè)新的鄰解，如圖5所示．對(duì)解序列中任意兩點(diǎn)進(jìn)行交換，得到的所有解構(gòu)成交換鄰域．

圖5 交換移動(dòng)示例Fig．5 An example of exchange move

與其它移動(dòng)相比，交換移動(dòng)只改變交換的兩個(gè)點(diǎn)所在的取貼循環(huán)內(nèi)元器件的拾取順序，對(duì)其余的循環(huán)沒有影響．此外，由于同一循環(huán)內(nèi)元器件的拾取按一個(gè)方向進(jìn)行，可避免貼裝頭在喂料槽上來回移動(dòng)，使得該循環(huán)的拾取總路徑最小，因此解序列中同一循環(huán)內(nèi)的兩個(gè)元器件交換意義不大．由此可知，對(duì)于取貼循環(huán)總數(shù)N和循環(huán)內(nèi)貼裝元器件總數(shù)H，有效的交換鄰域大小為

2．4 禁忌表

文中提出的TS算法采用雙禁忌表TL1和TL2，禁忌表TL1記錄交換移動(dòng)，禁忌表TL2記錄歷史解．

2．4．1 禁忌表 TL1

在TS算法中，為避免迂回搜索，一旦一個(gè)移動(dòng)被接受，它的反移動(dòng)就會(huì)被記錄到表中，在此后固定迭代步長內(nèi)該反移動(dòng)會(huì)被禁忌．對(duì)于交換鄰域結(jié)構(gòu)，禁忌表TL1中的禁忌對(duì)象為交換的兩個(gè)點(diǎn)，而禁忌表長度根據(jù)問題的規(guī)模而定．

2．4．2 禁忌表 TL2

雖然禁忌表TL1在一定程度上可避免迂回搜索，但對(duì)于統(tǒng)治性較強(qiáng)的局部最優(yōu)解，算法可能會(huì)在若干次迭代后再次陷入該解，所以TL1不能保證完全杜絕迂回搜索現(xiàn)象．若盲目地增大禁忌表的長度，不僅會(huì)削弱禁忌表的作用，而且會(huì)導(dǎo)致TS算法的性能因禁忌太多而變差．

由序優(yōu)化理論［11］可知，在解空間中均勻抽取v個(gè)不同的解，設(shè)好解在所有解中占的比率為u，則v個(gè)解存在好解的概率為1－(1－u)v．這說明若能保證搜索到足夠多的不同的解，那么能搜索到足夠好解的概率接近1．

基于該思想，文中設(shè)計(jì)禁忌表TL2來禁忌迭代搜索過程中出現(xiàn)過的歷史局部最優(yōu)解，使得當(dāng)前解盡量不陷入被禁忌的局部最優(yōu)解，以避免重復(fù)搜索．

禁忌表TL2包括禁忌的解序列S和對(duì)應(yīng)的目標(biāo)函數(shù)值f(S)，TL2的規(guī)模會(huì)隨著搜索的進(jìn)行而增大．在判斷某個(gè)解是否被TL2禁忌時(shí)，考慮到直接將解序列與TL2中所有存放的解相比較計(jì)算復(fù)雜，為了提高算法的效率，首先對(duì)解的目標(biāo)值進(jìn)行判斷．若目標(biāo)值未被禁忌，則解序列一定不同;若目標(biāo)值相同，再完整比較解序列是否一致．經(jīng)判斷后，若解被TL2禁忌，則將其舍棄，在余下鄰域中繼續(xù)搜索．

2．5 RLS

文中引入一種基于插入鄰域的RLS搜索策略，當(dāng)?shù)阉飨萑刖植孔顑?yōu)時(shí)，以一定概率P對(duì)解實(shí)行變換，使得搜索盡量逃離局部最優(yōu)．RLS是一種重復(fù)插入的局部搜索方法［12］，對(duì)解為序列或集合的優(yōu)化問題較為有效．由于單個(gè)元器件的插入移動(dòng)會(huì)改變一系列取貼循環(huán)的組成，對(duì)解的整體結(jié)構(gòu)造成較大的改變．因此文中將解分成N部分，每部分是一個(gè)取貼循環(huán)的拾取序列．RLS直接對(duì)每個(gè)取貼循環(huán)進(jìn)行重復(fù)插入，而不是對(duì)每個(gè)元器件實(shí)施變換，如圖6所示．

圖6 基于取貼循環(huán)插入的RLSFig．6 RLS based on inserting mounting circles

設(shè)當(dāng)前解序列 Sc=(S1，S2，…，SN)，對(duì)應(yīng)目標(biāo)函數(shù)值為fc，對(duì)Sc應(yīng)用RLS搜索策略進(jìn)行以取貼循環(huán)為單位的變換，步驟如下:

1)對(duì)當(dāng)前解進(jìn)行擾動(dòng)

(1)隨機(jī)選擇r個(gè)取貼循環(huán)，并按照取貼循環(huán)在解序列中的位置進(jìn)行升序排序，得到(J1，J2，…，Jr)，對(duì)應(yīng)在序列中的位置為(p［1］，p［2］，…，p［r］)，令 h:=1．

(2)從當(dāng)前序列中取出Jh并插入到p［h］所在位置之前的所有位置，得到p［h］個(gè)新序列，選取具有最小目標(biāo)函數(shù)值fnew的新解Snew．

(3)若 fnew＜ fc，則 fc:=fnew，Sc:=Snew．h:=h+1．若h≤r，則返回步驟(1);否則輸出擾動(dòng)后的解Sc．

2)基于參考解的搜索

(1)隨機(jī)生成拾取序列并作為參考序列R，令h:=1，k:=1．

(2)h:=h%N(%為取余運(yùn)算)，將 R［h］從序列 Sc中移出，分別插入到位置 0，1，…，h，得到解集對(duì)應(yīng)的序列為Snew．

(3)若 fnew＜fc，則更新 fc:=fnew，Sc:=Snew，k:=1;否則 k:=k+1．

(4)h:=h+1，若 k≤N，則返回步驟(2);否則基于參考解的搜索結(jié)束，輸出Sc．

通過插入移動(dòng)，RLS將參考解的特性融入到當(dāng)前解中．參考解的分散性強(qiáng)時(shí)，有助于提高算法的分散搜索能力．拾取序列對(duì)應(yīng)的貼裝序列則在計(jì)算目標(biāo)值時(shí)，通過全枚舉小規(guī)模TSP問題的解獲得．

2．6 算法步驟

基于RLS的改進(jìn)TS算法步驟如下:

1)運(yùn)用2．2節(jié)中所描述的方法產(chǎn)生初始解，并設(shè)為當(dāng)前解Sc和當(dāng)前最好解Sbest，對(duì)應(yīng)目標(biāo)函數(shù)值為fc和fbest．設(shè)置最大迭代步數(shù)itermax、最大未改進(jìn)迭代步數(shù) Un_itermax、禁忌表TL1的長度L、進(jìn)行 RLS變換的概率P，循環(huán)次數(shù)iter=0，未改進(jìn)迭代次數(shù)Un_iter=0．

2)搜索當(dāng)前解的交換鄰域，記錄最好的鄰解Snei和未被TL1和TL2禁忌的鄰解Sl．

3)判斷藐視準(zhǔn)則是否成立，若f(Snei)＜fbest，則fbest:=f(Snei)，Sbest:=Snei，Sc:=Snei;否則 Sc:=Sl．

4)生成隨機(jī)數(shù) r'～［0，1］，若 r'＜ P，則按 2．5節(jié)中的RLS方法對(duì)解Sc進(jìn)行變換．

5)若Sbest在本次迭代中更新，則Un_iter:=0，否則Un_iter:=Un_iter+1．將禁忌表TL1中非0元素減1，并將新禁忌的兩個(gè)點(diǎn)的禁忌長度設(shè)定為L，將Sc及其fc寫入禁忌表TL2中，令iter:=iter+1．

6)若Un_iter＞Un_itermax(達(dá)到最大未改進(jìn)最好解的迭代次數(shù))或 iter＞itermax(達(dá)到最大迭代次數(shù))，則算法終止，輸出結(jié)果Sbest和f(Sbest);否則轉(zhuǎn)步驟2)．

3 實(shí)驗(yàn)及算法性能分析

文中算法使用VC++6．0軟件編程，并在內(nèi)存為4096MB的FUJITSU計(jì)算機(jī)上運(yùn)行．測(cè)試實(shí)例是20塊PCB的實(shí)際貼裝數(shù)據(jù)，對(duì)每個(gè)數(shù)據(jù)均測(cè)試10次取結(jié)果的平均值．實(shí)驗(yàn)對(duì)象為四貼裝頭的拱架式貼片機(jī)，貼裝頭間距為16mm，兩側(cè)分別有50個(gè)槽位，喂料器分配給定，禁忌表TL1長度L=12，最大迭代步數(shù)itermax=200，最大未改進(jìn)迭代步數(shù)Un_itermax=20，RLS變換的概率P=0．2．為驗(yàn)證文中算法的有效性，將算法計(jì)算結(jié)果與使用蟻群 －混合蛙跳算法［6］、參數(shù)相同情況下不帶RLS搜索策略的改進(jìn)TS算法的結(jié)果進(jìn)行了比較，如表1所示，算例運(yùn)行時(shí)間見表2．

表1表明，使用文中算法求解貼裝順序優(yōu)化問題得到的結(jié)果優(yōu)于蟻群－混合蛙跳算法［6］的求解結(jié)果，20塊PCB的解平均值提高了16．17%．文獻(xiàn)［6］算法將元器件的貼裝順序作為解序列，而元器件的拾取順序取與貼裝順序相同的序列，該處理方法可能導(dǎo)致取貼循環(huán)內(nèi)貼裝頭在喂料槽上來回移動(dòng)的次數(shù)增加，從而使總路徑增加．文中算法對(duì)這兩個(gè)序列同時(shí)優(yōu)化，求解方法更為有效．根據(jù)表1，對(duì)于元器件數(shù)量超過100的后12組數(shù)據(jù)，RLS搜索策略能帶來平均1．14%的改進(jìn)，證明了文中算法的性能更優(yōu)，在解決規(guī)模較大的問題上效果更突出．

表1 幾種算法的實(shí)驗(yàn)結(jié)果比較Table 1 Comparison of the experimental results obtained by several algorithms

根據(jù)表2，盡管文中算法的運(yùn)行時(shí)間會(huì)隨著問題規(guī)模的增大而增加，但當(dāng)元器件數(shù)量為378時(shí)求取一個(gè)解所用的時(shí)間約為43．043 s，因此算法的計(jì)算時(shí)間在實(shí)際應(yīng)用中是可以接受的．

表2 每個(gè)實(shí)例的運(yùn)行時(shí)間Table 2 Running time for each instance

4 結(jié)語

文中針對(duì)拱架式貼片機(jī)貼裝順序優(yōu)化問題，建立了數(shù)學(xué)規(guī)劃模型，提出了一種基于RLS的改進(jìn)TS算法．在該算法中，應(yīng)用了最近鄰算法生成初始解，采用了交換鄰域結(jié)構(gòu)，設(shè)計(jì)了雙禁忌表來避免迂回搜索，并引入以取貼循環(huán)為單位的RLS變換策略來提高算法突破局部最優(yōu)的能力．通過對(duì)實(shí)際生產(chǎn)的20塊PCB數(shù)據(jù)進(jìn)行仿真計(jì)算，并將結(jié)果與文獻(xiàn)計(jì)算結(jié)果作比較，結(jié)果表明文中提出的改進(jìn)TS算法能更有效地解決貼片機(jī)貼裝順序優(yōu)化問題．

［1］ Michael O B，Michael J M．Sequencing of insertions in printed circuit board assembly ［J］．Operations Research in Manufacturing，1988，36(2):192－201．

［2］ Leip?l?T，Nevalainen O．Optimization of the movements of a component placement machine［J］．European Journal of Operational Research，1989，38(2):167－177．

［3］ 曾又姣，金燁．基于遺傳算法的貼片機(jī)貼裝順序優(yōu)化［J］．計(jì)算機(jī)集成制造系統(tǒng)，2004，10(2):205－208．Zeng You－jiao，Jin Ye．Component placement sequence optimization for surface mounting machine based on genetic algorithm ［J］．Computer Integrated Manufacturing Systems，2004，10(2):205－208．

［4］ 杜軒，李宗斌，高新勤，等．基于遺傳算法的轉(zhuǎn)塔式貼片機(jī)貼裝過程優(yōu)化［J］．西安交通大學(xué)學(xué)報(bào)，2008，42(3):295－299．Du Xuan，Li Zong－bin，Gao Xin－qin，et al．Component placement process optimization for chip shooter machine based on genetic algorithm［J］．Journal of Xi’an Jiaotong University，2008，42(3):295－299．

［5］ 朱光宇，林蔚清．基于改進(jìn)混合蛙跳算法的貼片機(jī)貼裝順序優(yōu)化 ［J］．中國工程機(jī)械報(bào)，2008，6(4):428－432．Zhu Guang－yu，Lin Wei－qing．Mounting sequential optimization on surface mounting machine using improved hybrid frog－jumping algorithm ［J］．Chinese Journal of Construction Machinery，2008，6(4):428－432．

［6］ 陳鐵梅，羅家祥，胡躍明．基于蟻群－混合蛙跳算法的貼片機(jī)貼裝順序優(yōu)化［J］．控制理論與應(yīng)用，2011，28(12):1813－1820．Chen Tie－mei，Luo Jia－xiang，Hu Yue－ming．Mounting sequence optimization on surface mounting machine using ant－colony algorithm and shuffled frog－leaping algorithm［J］．Journal of Control Theory ＆ Applications，2011，28(12):1813－1820．

［7］ 袁鵬，劉海明，胡躍明．基于傘布搜索法的貼片機(jī)貼裝順序優(yōu)化算法［J］．電子工藝技術(shù)，2007，28(6):316－320．Yuan Peng，Liu Hai－ming，Hu Yue－ming．Scatter searching algorithm for multi－h(huán)eaded surface mounter ［J］．Electronics Process Technology，2007，28(6):316－320．

［8］ 俞國燕，鄭時(shí)雄，劉桂雄，等．復(fù)雜工程問題全局優(yōu)化算法研究［J］．華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2000，28(8):104－110．Yu Guo－yan，Zheng Shi－xiong，Liu Gui－xiong，et al．Study on global optimization algorithms for complex engineering problem ［J］．Journal of South China University of Technology:Natural Science Edition，2000，28(8):104－110．

［9］ Glover F．Future paths for integer programming and links to artificial intelligence［J］．Computers and Operations Research，1986，13(5):533－549．

［10］ Glover F，Gutin G，Yeo A，et al．Construction heuristics for the asymmetric TSP ［J］．European Journal of Operational Research，2001，129(3):555－568．

［11］ Edward Lau T W，Ho Y C．Universal alignment probabilities and subset selection for ordinal optimization ［J］．Journal of Optimization Theory and Applications，1997，93(3):455－489．

［12］ Tasgetiren F，Pan Q K，Liang Y C．A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times［J］．Computers and Operations Research，2009，36(6):1900－1915．