基于GA的矩陣式TSP算法及在飛針測試機上的應(yīng)用研究.pdf

1、飛針測試機是一個在制造環(huán)境測試PCB(印刷電路板)的系統(tǒng).它用探針代替車床,在X-Y機構(gòu)上裝有4-8個由電機驅(qū)動的可分別快速移動的探針,利用探針在Z方向的移動同PCB的焊點進(jìn)行接觸并進(jìn)行電氣測量.測試人員把設(shè)計工程師的CAD數(shù)據(jù)轉(zhuǎn)換成可使用的文件,這些文件包含了需要測試的焊點的坐標(biāo)(X,Y)及焊點在PCB中的網(wǎng)絡(luò)值,由此決定驅(qū)動各個探針的X、Y、Z電機的移動.通常,一塊PCB上可能有上千個焊點,如果探針不按一種最優(yōu)或較優(yōu)的路徑移動進(jìn)行測

2、試,可能會耗費數(shù)倍的測試時間,延誤生產(chǎn).把旅行商問題(Traveling Salesman Problem,簡記為TSP)應(yīng)用到該系統(tǒng)上,很好的解決了探針移動軌跡優(yōu)化的問題.TSP屬于組合數(shù)學(xué)中一個古老而又困難的問題.有效的解決它,在可計算理論上具有重要的理論意義,同時也具有重要的實際應(yīng)用價值.首先,基于該文的研究背景,引出了TSP在飛針測試機上應(yīng)用的意義和價值.隨后敘述了TSP的一般提法,描述了其數(shù)學(xué)模型,綜合介紹了關(guān)于解決TSP的相

3、關(guān)算法,并做了性能比較.其次,把不完全算法中的遺傳算法應(yīng)用到TSP中.對其中關(guān)鍵的交叉算子介紹了一種針對TSP的改進(jìn)措施.此外,基于局部尋優(yōu)的思想,介紹了一種特殊的矩陣式TSP的解決方法.最后,介紹了飛針測試機控制系統(tǒng)的開發(fā)過程,包括硬件系統(tǒng)和軟件設(shè)計兩個部分.此外,把遺傳尋優(yōu)和矩陣式TSP綜合應(yīng)用于探針路徑優(yōu)化問題上.把需要測試的焊點看作是各個城市,探針看作旅行商,而"旅行的費用"就是探針遍歷所有焊點所行走的距離,實際運行結(jié)果表明,飛