基于改進TCNN算法的電子組裝路徑優化研究

夏威

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

0 引言

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

許頔等[3]探討了PEDOT的制備及改進方法,并研究了改進PEDOT在電子器件組裝中的應用效果。Robert van der Zwan等[4]討論了印刷電路板中電子元器件的作用,以及電子元器件的未來發展趨勢。崔譯文等[5]結合改進的Hough圓檢測算法和SURF算法,提出一種電子元器件的質量檢測方法,實驗證明該方法的特征點匹配率超過80%。

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

1 TCNN算法的構建與優化

1.1 TCNN算法的構建與更新方式選擇

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

(1)

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

(2)

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

(3)

式(3)中,W1表示電子組裝路徑優化問題的約束條件參數,W2表示最小化路徑的長度參數,dik表示電子元器件i和電子元器件k之間的距離。與原有的能量函數公式相比較,式(3)的動力學特性更為豐富,并且能夠同時滿足電子組裝路徑優化問題的約束條件以及最小化路徑長度準則。電子組裝路徑優化問題的約束條件與旅行商問題的約束條件類似,是指:在電子元器件的組裝過程中,每一次只能在一個點組裝一個電子元器件,并且每個點只能組裝一個電子元器件[10]?；谏鲜鰞热?即可聯合HNN算法和混沌神經網絡構建TCNN算法。TCNN算法的更新方式主要有2種,即異步更新與同步更新,如圖1所示。

(a) 異步更新流程

在圖1(a)中可知,異步更新在算法的每次更新迭代時均只更新一個神經元a的狀態,其余的神經元則保持原有狀態。該方法的更新速度較慢,適用于迭代次數少、規模小的神經網絡使用場景。同步更新則在每次更新時都會更新所有神經元,單次更新時間會長于異步更新方式,但總迭代次數和時間會遠少于異步更新,更適用于大規模的神經網絡使用場景?；谕ㄐ疟嘲宓拇笠幠ｋ娮咏M裝路徑優化問題規模大的特點,研究選擇同步更新方式。

1.2 并行化策略與分治策略下的TCNN算法改進

相比ACO算法,TCNN算法的求解速度更快,求解時間需求更少,能夠極大地節約時間[11-12]。但TCNN算法求解精度與傳統的求解算法相比卻很低,無法滿足需求[13-14]。因此,研究對TCNN算法進行并行化改進,使其兼具求解精度和求解效率。GPU設備能夠對矩陣運算進行提速,因此將能量函數的更新迭代方式優化為矩陣運算,再通過GPU設備進行加速,能量函數的矩陣運算模式如式(4)所示。

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

W2(DVN)+W1E}

(4)

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

圖2 分治策略的原理

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

(5)

式(5)中,R表示表現率,L′表示所求解數據集的已知最優路徑長度,L表示TCNN算法求解的該數據集的路徑長度。實驗結果表明,在大規模問題、中等規模問題以及小規模問題的數據集中,最佳聚類數目均為20,如圖3所示。

(a) 小規模數據

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

2 改進TCNN算法的性能分析

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

表1 并行化TCNN算法的改進效果

在表1中能夠看出,并行化優化后,在CPU和GPU上運行的TCNN算法的運算速度均得到了極大的提升,處理相同的數據集時,并行化優化的TCNN算法的運行時間遠低于未優化的TCNN算法。當數據規模較小時,并行化優化的TCNN算法在CPU上的計算效率更高,當數據規模超過200時,并行化優化的TCNN算法在GPU設備上的運行效率更高。這是因為研究采取將所有GPU設備的內存集中計算一個子集后,再依次計算其余子集的策略,當數據規模較小時,其效率會略低于同時計算所有子集的策略;當數據規模超過一定程度時,則能極大地提升計算速度。處理不同規模的數據集時,3種算法的平均表現率沒有明顯差別。以上結果表明,并行化優化TCNN能夠在保證優化精度的基礎上,極大地提升算法的運算速度。為驗證本文提出的優化TCNN算法在處理旅行商問題上的性能,分別基于ACO算法和優化TCNN算法構建模型,利用相同的訓練數據對兩個模型進行充分訓練后,采用相同的旅行商問題測試數據集對兩種模型進行測試,測試結果如圖4所示。

圖4 優化TCNN算法處理旅行商問題的性能分析

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

(a) 默認路徑

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

3 總結

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