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

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

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

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