夏威

(惠州市技師學(xué)院, 電子工程系, 廣東, 惠州 516000)

0 引言

在此背景下,作為集群路由器的主要組件,通信背板上的電子元器件的數(shù)量急劇增加,組裝路徑也越來(lái)越復(fù)雜,通訊背板的電子器件組裝的效率和質(zhì)量也受到了業(yè)內(nèi)人士的廣泛關(guān)注[1-2]。

許頔等[3]探討了PEDOT的制備及改進(jìn)方法,并研究了改進(jìn)PEDOT在電子器件組裝中的應(yīng)用效果。Robert van der Zwan等[4]討論了印刷電路板中電子元器件的作用,以及電子元器件的未來(lái)發(fā)展趨勢(shì)。崔譯文等[5]結(jié)合改進(jìn)的Hough圓檢測(cè)算法和SURF算法,提出一種電子元器件的質(zhì)量檢測(cè)方法,實(shí)驗(yàn)證明該方法的特征點(diǎn)匹配率超過(guò)80%。

通過(guò)上述內(nèi)容可知,目前對(duì)電子器件組裝的相關(guān)研究更關(guān)注組裝質(zhì)量,忽視了組裝效率。為此,研究采用暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)算法(TCNN)來(lái)求解電子組裝中的大規(guī)模優(yōu)化問(wèn)題,并針對(duì)TCNN精度低,易陷入局部最優(yōu)的缺陷,采用分治策略對(duì)算法進(jìn)行改進(jìn),期望能夠有效縮短電子組裝路徑,進(jìn)而提升大規(guī)模電子組裝的生產(chǎn)效率。

1 TCNN算法的構(gòu)建與優(yōu)化

1.1 TCNN算法的構(gòu)建與更新方式選擇

通信背板的大規(guī)模電子組裝路徑優(yōu)化問(wèn)題與旅行商問(wèn)題類似,均是在多個(gè)點(diǎn)之間尋找一條最優(yōu)路徑,因此研究采用旅行商問(wèn)題數(shù)學(xué)模型來(lái)對(duì)電子組裝路徑優(yōu)化問(wèn)題進(jìn)行描述[6-7]。電子組裝路徑優(yōu)化本質(zhì)上是最小化組合優(yōu)化問(wèn)題:若存在N個(gè)電子元器件C={c1,c2,…,cN},電子元器件的遍歷路徑表示為S={s1,s2,…,sN}。電子組裝路徑優(yōu)化的數(shù)學(xué)模型就是在滿足目標(biāo)函數(shù)的前提下,通過(guò)計(jì)算獲取到一個(gè)最優(yōu)路徑S。目標(biāo)函數(shù)的表達(dá)式如式(1)所示。

(1)

式(1)中,d(ci,ci+1)表示電子元器件集合中第i個(gè)電子元器件和第j個(gè)電子元器件之間的權(quán)重。在實(shí)際生產(chǎn)工作中,一般采用近似算法來(lái)求解電子組裝路徑優(yōu)化問(wèn)題。目前,在電子組裝路徑優(yōu)化問(wèn)題中,蟻群算法(ACO)的應(yīng)用較為廣泛。但蟻群算法的求解速度較低,已逐漸無(wú)法滿足規(guī)模越來(lái)越大的電子組裝路徑優(yōu)化問(wèn)題求解需求[8-9]。因此研究將Hopfield 神經(jīng)網(wǎng)絡(luò)算法(HNN)與混沌神經(jīng)網(wǎng)絡(luò)相結(jié)合,構(gòu)建TCNN算法,并將TCNN應(yīng)用到大規(guī)模電子組裝路徑優(yōu)化問(wèn)題求解中?；煦缟窠?jīng)網(wǎng)絡(luò)可用式(2)進(jìn)行描述。

(2)

式(2)中,i表示第i個(gè)神經(jīng)元,vi表示第i個(gè)神經(jīng)元的輸出,ui表示該神經(jīng)元的內(nèi)部狀態(tài),wij表示2個(gè)神經(jīng)元i和j的連接權(quán)值,Ii表示該神經(jīng)元的輸入偏置,α表示一個(gè)輸入縮放參數(shù),k表示神經(jīng)元阻尼因子,且有0≤k≤1,zi表示一個(gè)自反饋連接權(quán)值,且有zi>0,ε表示輸出方程的步進(jìn)參數(shù),且有ε>0?；贖NN算法的能量函數(shù),結(jié)合混沌算法,提出新的能量式,如式(3)所示。

(3)

式(3)中,W1表示電子組裝路徑優(yōu)化問(wèn)題的約束條件參數(shù),W2表示最小化路徑的長(zhǎng)度參數(shù),dik表示電子元器件i和電子元器件k之間的距離。與原有的能量函數(shù)公式相比較,式(3)的動(dòng)力學(xué)特性更為豐富,并且能夠同時(shí)滿足電子組裝路徑優(yōu)化問(wèn)題的約束條件以及最小化路徑長(zhǎng)度準(zhǔn)則。電子組裝路徑優(yōu)化問(wèn)題的約束條件與旅行商問(wèn)題的約束條件類似,是指:在電子元器件的組裝過(guò)程中,每一次只能在一個(gè)點(diǎn)組裝一個(gè)電子元器件,并且每個(gè)點(diǎn)只能組裝一個(gè)電子元器件[10]。基于上述內(nèi)容,即可聯(lián)合HNN算法和混沌神經(jīng)網(wǎng)絡(luò)構(gòu)建TCNN算法。TCNN算法的更新方式主要有2種,即異步更新與同步更新,如圖1所示。

(a) 異步更新流程

在圖1(a)中可知,異步更新在算法的每次更新迭代時(shí)均只更新一個(gè)神經(jīng)元a的狀態(tài),其余的神經(jīng)元?jiǎng)t保持原有狀態(tài)。該方法的更新速度較慢,適用于迭代次數(shù)少、規(guī)模小的神經(jīng)網(wǎng)絡(luò)使用場(chǎng)景。同步更新則在每次更新時(shí)都會(huì)更新所有神經(jīng)元,單次更新時(shí)間會(huì)長(zhǎng)于異步更新方式,但總迭代次數(shù)和時(shí)間會(huì)遠(yuǎn)少于異步更新,更適用于大規(guī)模的神經(jīng)網(wǎng)絡(luò)使用場(chǎng)景?；谕ㄐ疟嘲宓拇笠?guī)模電子組裝路徑優(yōu)化問(wèn)題規(guī)模大的特點(diǎn),研究選擇同步更新方式。

1.2 并行化策略與分治策略下的TCNN算法改進(jìn)

相比ACO算法,TCNN算法的求解速度更快,求解時(shí)間需求更少,能夠極大地節(jié)約時(shí)間[11-12]。但TCNN算法求解精度與傳統(tǒng)的求解算法相比卻很低,無(wú)法滿足需求[13-14]。因此,研究對(duì)TCNN算法進(jìn)行并行化改進(jìn),使其兼具求解精度和求解效率。GPU設(shè)備能夠?qū)仃囘\(yùn)算進(jìn)行提速,因此將能量函數(shù)的更新迭代方式優(yōu)化為矩陣運(yùn)算,再通過(guò)GPU設(shè)備進(jìn)行加速,能量函數(shù)的矩陣運(yùn)算模式如式(4)所示。

U=kU-z(V-I0E)+α{-W1(VM+MV)-

W2(DVN)+W1E}

(4)

式(4)中,V表示輸出神經(jīng)元矩陣,U表示一個(gè)能夠描述神經(jīng)元內(nèi)部狀態(tài)的矩陣,D表示距離矩陣和距離居住的對(duì)角線矩陣之差。通過(guò)TCNN算法的矩陣運(yùn)算模型,就能夠使TCNN算法在GPU設(shè)備上運(yùn)行,并借助GPU設(shè)備實(shí)現(xiàn)所有神經(jīng)元的快速同步更新,進(jìn)一步提升TCNN算法的求解速度[15]。在大規(guī)模的求解問(wèn)題中,常用分治策略將待求解問(wèn)題分成多個(gè)小規(guī)模問(wèn)題,并依次求解并還原,最終實(shí)現(xiàn)對(duì)大規(guī)模問(wèn)題的求解。分治策略的原理如圖2所示。

圖2 分治策略的原理

研究采用分治策略來(lái)對(duì)TCNN算法進(jìn)行改進(jìn),主要有4個(gè)步驟。首先對(duì)表示電路板上所有安裝節(jié)點(diǎn)的數(shù)據(jù)集進(jìn)行分割操作,將其劃分為n個(gè)小規(guī)模的子集,即在電路板上將組裝節(jié)點(diǎn)分割成n個(gè)包含了若干組裝節(jié)點(diǎn)的區(qū)域。分割操作則借助凝聚式層次聚類方法來(lái)實(shí)現(xiàn)。其次,利用TCNN算法求得所有子集的最短路徑,即n個(gè)區(qū)域中組裝節(jié)點(diǎn)的最短組裝路徑。然后將所有子集均作為一個(gè)節(jié)點(diǎn),將所有節(jié)點(diǎn)視作一個(gè)新的數(shù)據(jù)集,并采用TCNN算法求解該數(shù)據(jù)集的最短路徑,獲取所有子集的排列順序。最后則是選擇一個(gè)連接策略,將所有節(jié)點(diǎn)按順序連接,從而得到初始問(wèn)題的最優(yōu)解。也就是說(shuō),將電路板上的所有電子器件組裝節(jié)點(diǎn)分割成若干區(qū)域,在這些區(qū)域內(nèi)求得電子組裝的最優(yōu)路徑,再將這些區(qū)域整體視為一個(gè)組裝節(jié)點(diǎn),最終在整個(gè)電路板上求解最優(yōu)路徑。電子組裝路徑優(yōu)化問(wèn)題數(shù)據(jù)集的拆分,本質(zhì)上是依據(jù)空間距離分布劃分節(jié)點(diǎn),因此采用層次聚類方法來(lái)將距離相近的節(jié)點(diǎn)劃分為一個(gè)子集。當(dāng)數(shù)據(jù)集規(guī)模變大時(shí),層次聚類算法的運(yùn)行時(shí)間會(huì)呈指數(shù)上升,為此,研究采用Tensorflow來(lái)尋找距離矩陣的最小值,快速劃分子集,極大地縮短子集劃分時(shí)間。聚類數(shù)目,即劃分子集的數(shù)量,直接影響到大規(guī)模旅行商問(wèn)題的求解效果。為了確定最佳聚類數(shù)目,提高算法的求解精度,研究采用TSPLIB數(shù)據(jù)集進(jìn)行相關(guān)實(shí)驗(yàn),對(duì)不同聚類數(shù)目下TCNN算法的求解精度進(jìn)行驗(yàn)證。算法的求解精度用表現(xiàn)率指標(biāo)來(lái)評(píng)估,表現(xiàn)率的計(jì)算方式如式(5)所示。

(5)

式(5)中,R表示表現(xiàn)率,L′表示所求解數(shù)據(jù)集的已知最優(yōu)路徑長(zhǎng)度,L表示TCNN算法求解的該數(shù)據(jù)集的路徑長(zhǎng)度。實(shí)驗(yàn)結(jié)果表明,在大規(guī)模問(wèn)題、中等規(guī)模問(wèn)題以及小規(guī)模問(wèn)題的數(shù)據(jù)集中,最佳聚類數(shù)目均為20,如圖3所示。

(a) 小規(guī)模數(shù)據(jù)

因此,在通信背板的大規(guī)模電子組裝路徑優(yōu)化問(wèn)題中,均將子集數(shù)量分割成20個(gè)。利用基于GPU設(shè)備的TCNN算法對(duì)子集內(nèi)部路徑進(jìn)行優(yōu)化求解。為更好地處理大規(guī)模路徑優(yōu)化問(wèn)題,研究采取將所有內(nèi)存應(yīng)用到同一個(gè)子集的優(yōu)化上的策略,即對(duì)每個(gè)子集依次進(jìn)行優(yōu)化計(jì)算。對(duì)子集內(nèi)部路徑進(jìn)行優(yōu)化后,還需要對(duì)子集之間的路徑進(jìn)行優(yōu)化。求得所有子集的開口端的兩個(gè)點(diǎn)的中點(diǎn),該點(diǎn)即表示該點(diǎn)所在的數(shù)據(jù)子集。用所有的子集的中點(diǎn)構(gòu)建一個(gè)新的數(shù)據(jù)集,并利用TCNN算法對(duì)新數(shù)據(jù)集進(jìn)行求解,最終得到所有子集的最終排列順序。綜合上述內(nèi)容,即可完成對(duì)TCNN算法的優(yōu)化和改進(jìn),進(jìn)而實(shí)現(xiàn)電子組裝路徑優(yōu)化,提高大規(guī)模電子組裝效率。

2 改進(jìn)TCNN算法的性能分析

為驗(yàn)證改進(jìn)TCNN算法的優(yōu)化效果,以及改進(jìn)TCNN在通信背板的大規(guī)模電子組裝路徑優(yōu)化問(wèn)題中的求解效果,研究對(duì)其進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)來(lái)源為5家PCB板生產(chǎn)廠商,實(shí)驗(yàn)數(shù)據(jù)的獲取方法為數(shù)據(jù)挖掘,最終獲取5個(gè)電子器件組裝路徑的數(shù)據(jù)集,分別記為數(shù)據(jù)集1、數(shù)據(jù)集2、數(shù)據(jù)集3以及數(shù)據(jù)集4、數(shù)據(jù)集5。首先驗(yàn)證并行化TCNN算法的性能提升效果。采用Windows 10系統(tǒng)運(yùn)行程序,Python語(yǔ)言實(shí)現(xiàn)。GPU設(shè)備采用英偉達(dá)1050Ti,運(yùn)行內(nèi)存為4 GB。采用相同的數(shù)據(jù)集對(duì)優(yōu)化前后的TCNN算法進(jìn)行測(cè)試。并行化改進(jìn)TCNN算法測(cè)試兩次,第一次在CPU上運(yùn)行,第二次則是在GPU上運(yùn)行。兩種算法對(duì)各個(gè)數(shù)據(jù)集求解所需的時(shí)間,以及表現(xiàn)率如表1所示。

表1 并行化TCNN算法的改進(jìn)效果

在表1中能夠看出,并行化優(yōu)化后,在CPU和GPU上運(yùn)行的TCNN算法的運(yùn)算速度均得到了極大的提升,處理相同的數(shù)據(jù)集時(shí),并行化優(yōu)化的TCNN算法的運(yùn)行時(shí)間遠(yuǎn)低于未優(yōu)化的TCNN算法。當(dāng)數(shù)據(jù)規(guī)模較小時(shí),并行化優(yōu)化的TCNN算法在CPU上的計(jì)算效率更高,當(dāng)數(shù)據(jù)規(guī)模超過(guò)200時(shí),并行化優(yōu)化的TCNN算法在GPU設(shè)備上的運(yùn)行效率更高。這是因?yàn)檠芯坎扇⑺蠫PU設(shè)備的內(nèi)存集中計(jì)算一個(gè)子集后,再依次計(jì)算其余子集的策略,當(dāng)數(shù)據(jù)規(guī)模較小時(shí),其效率會(huì)略低于同時(shí)計(jì)算所有子集的策略;當(dāng)數(shù)據(jù)規(guī)模超過(guò)一定程度時(shí),則能極大地提升計(jì)算速度。處理不同規(guī)模的數(shù)據(jù)集時(shí),3種算法的平均表現(xiàn)率沒(méi)有明顯差別。以上結(jié)果表明,并行化優(yōu)化TCNN能夠在保證優(yōu)化精度的基礎(chǔ)上,極大地提升算法的運(yùn)算速度。為驗(yàn)證本文提出的優(yōu)化TCNN算法在處理旅行商問(wèn)題上的性能,分別基于ACO算法和優(yōu)化TCNN算法構(gòu)建模型,利用相同的訓(xùn)練數(shù)據(jù)對(duì)兩個(gè)模型進(jìn)行充分訓(xùn)練后,采用相同的旅行商問(wèn)題測(cè)試數(shù)據(jù)集對(duì)兩種模型進(jìn)行測(cè)試,測(cè)試結(jié)果如圖4所示。

圖4 優(yōu)化TCNN算法處理旅行商問(wèn)題的性能分析

在圖4中容易看出,隨著樣本規(guī)模的增加,2種算法的處理時(shí)間和表現(xiàn)率均在增加。在樣本規(guī)模達(dá)到600時(shí),ACO算法的處理時(shí)間遠(yuǎn)超過(guò)12 s,表現(xiàn)率為3.03;優(yōu)化TCNN算法的處理時(shí)間為0.23 s,表現(xiàn)率為1.73,比ACO算法低2.70。當(dāng)樣本規(guī)模達(dá)到800時(shí),ACO算法的處理時(shí)間遠(yuǎn)超過(guò)12 s,表現(xiàn)率為5.14;優(yōu)化TCNN算法的處理時(shí)間為0.72 s,表現(xiàn)率為2.68,比ACO算法低2.46。將算法整合到電子組裝設(shè)備控制系統(tǒng)上位機(jī)軟件中,進(jìn)而優(yōu)化電子組裝路徑。試驗(yàn)選擇的PCB基板上需要組裝的電子元器件的數(shù)目為50,分別利用ACO算法和本文提出的優(yōu)化TCNN算法進(jìn)行路徑優(yōu)化。優(yōu)化后,經(jīng)ACO算法優(yōu)化后的路徑,經(jīng)改進(jìn)TCNN算法優(yōu)化后的路徑以及連接器默認(rèn)壓接路徑效果如圖5所示。

(a) 默認(rèn)路徑

在圖5中容易看出,連接器默認(rèn)壓接路徑有許多交叉,因此產(chǎn)生了許多冗余路徑,導(dǎo)致整個(gè)路徑長(zhǎng)度較長(zhǎng)。在經(jīng)過(guò)ACO算法和改進(jìn)TCNN算法進(jìn)行路徑優(yōu)化后,交叉部分基本消除,冗余路徑大大減少,總路徑長(zhǎng)度也因此縮短。其中,連接器默認(rèn)壓接路徑總長(zhǎng)度為3163 mm;經(jīng)ACO算法優(yōu)化后路徑總長(zhǎng)度為2700 mm,優(yōu)化比為30.6%;經(jīng)改進(jìn)TCNN算法優(yōu)化后路徑總長(zhǎng)度為2749 mm,優(yōu)化比為28.2%。綜合上述內(nèi)容可以得知,研究提出的改進(jìn)TCNN算法在電子組裝路徑優(yōu)化比與ACO算法相差僅2.4%,但改進(jìn)TCNN算法所需時(shí)間遠(yuǎn)低于ACO算法,更適用于大規(guī)模電子組裝路徑優(yōu)化。

3 總結(jié)

通信背板的大規(guī)模電子組裝路徑優(yōu)化問(wèn)題關(guān)系到通信背板的生產(chǎn)效率,因此受到業(yè)內(nèi)人士的廣泛關(guān)注。電子組裝路徑優(yōu)化問(wèn)題中,傳統(tǒng)的優(yōu)化算法為ACO算法,但ACO算法的效率較低,因此研究提出一種TCNN算法,并采用并行化策略和分治策略對(duì)其進(jìn)行優(yōu)化和改進(jìn)。仿真實(shí)驗(yàn)結(jié)果顯示,并行化優(yōu)化后,在CPU和GPU上運(yùn)行的TCNN算法的運(yùn)算速度均得到了極大的提升;處理相同規(guī)模的數(shù)據(jù)集時(shí),改進(jìn)TCCN算法的表現(xiàn)率與ACO算法的表現(xiàn)率無(wú)明顯差距,處理時(shí)間則遠(yuǎn)低于ACO算法。將AOC算法和改進(jìn)TCCN算法應(yīng)用到電子組裝路徑優(yōu)化中,ACO算法優(yōu)化后路徑總長(zhǎng)度為2700 mm,優(yōu)化比為30.6%;經(jīng)改進(jìn)TCNN算法優(yōu)化后路徑總長(zhǎng)度為2749 mm,優(yōu)化比為28.2%,僅比ACO算法低2.4%。綜上所述,改進(jìn)TCNN算法的優(yōu)化精度比ACO算法略差,但優(yōu)化效率遠(yuǎn)高于ACO算法,因此更適用于大規(guī)模電子組裝路徑優(yōu)化。研究未探討超大規(guī)模數(shù)據(jù)下算法的優(yōu)化效果,還需要日后進(jìn)一步研究。