基于螞蟻算法的PCB板路徑優(yōu)化研究ppt課件

1、基于螞蟻算法的PCB板途徑優(yōu)化研討 參考文獻(xiàn)模型背景 在印刷電路板PCB焊接消費(fèi)、缺點(diǎn)檢測(cè)以及維修過程中，現(xiàn)行以人工方式為主的途徑規(guī)劃方法缺乏嚴(yán)厲的數(shù)學(xué)論證，以致經(jīng)常導(dǎo)致自動(dòng)化作業(yè)順序不合理的情況，導(dǎo)致消費(fèi)周期過長，影響整條消費(fèi)線的消費(fèi)。 如何根據(jù)PCB板焊接的實(shí)踐任務(wù)情況以及通用途徑規(guī)劃技術(shù)尋求一種高效的途徑規(guī)劃處理方案，已成為PCB板制造業(yè)中的一個(gè)重點(diǎn)模型假設(shè) 本模型中采取從CAD文件提取焊點(diǎn)信息，經(jīng)過逐點(diǎn)焊接的方式控制系統(tǒng)驅(qū)開任務(wù)臺(tái)挪動(dòng) 當(dāng)待焊焊點(diǎn)到達(dá)激光半點(diǎn)位置時(shí)，系統(tǒng)按給定的加熱功率以及時(shí)間輸出激光 當(dāng)一個(gè)焊點(diǎn)焊接終了后再挪動(dòng)下一個(gè)焊點(diǎn)，直至一切焊點(diǎn)焊接終了。模型假設(shè) 假設(shè)每次焊接的

2、效率到達(dá)最高 顯然當(dāng)焊點(diǎn)的焊接規(guī)范給定后，全部焊接時(shí)間決議于總的行走道路模型建立 在焊接PCB板任務(wù)過程中，焊接從最原始位置出發(fā)，途徑各個(gè)焊點(diǎn)，最終回到原始位置，完成一個(gè)任務(wù)循環(huán)，這與TSP游覽商問題的數(shù)學(xué)模型一致。TSP游覽商模型 游覽商從駐地出發(fā)，經(jīng)過一切目的地后再次前往原地，應(yīng)如何安排其游覽道路才干使游覽間隔最小。模型求解 本模型中我們采用蟻群算法ACS即：在算法的初始時(shí)辰，將m只螞蟻隨機(jī)放到n座城市，然后螞蟻同時(shí)由一個(gè)城市到另一個(gè)城市，逐漸完成搜索過程。整個(gè)算法的迭代過程以N為刻度，1=N=Nmax(Nmax為最大迭代次數(shù))。在每次迭代中，以t為刻度，0=t=n,螞蟻kk=1,2,3，

3、m根據(jù)概率轉(zhuǎn)換規(guī)那么選擇下一個(gè)城市，由此可以生成一個(gè)由n個(gè)城市組成的行動(dòng)道路，并伴有信息素的更新。影響螞蟻轉(zhuǎn)移到下一城市的要素1 忌諱列表tube 忌諱表是為了防止螞蟻反復(fù)走進(jìn)同一個(gè)城市的一個(gè)數(shù)據(jù)構(gòu)造。 設(shè)tubek為螞蟻k的忌諱表，那么螞蟻k在經(jīng)過城市i以后，就將該城市參與到本人的忌諱表tubek中，表示下一次不能再選擇城市i。用tubek(s)示忌諱表中第s個(gè)元素，也即螞蟻所走過的第s個(gè)城市；完成一次周游后，即遍歷n個(gè)城市后，清空忌諱表。2 能見度 定義為間隔的倒數(shù)。=1/d。 兩個(gè)城市的間隔越近，能見度越高，被選擇的愿望越大，由此引導(dǎo)螞蟻的搜索。這種信息是固定不變的，稱為啟發(fā)信息。3 信

4、息素 當(dāng)螞蟻由城市i選擇城市j后算法將在ij途徑上遺留信息素，是一種動(dòng)態(tài)的全局信息，代表了由城市i到j(luò)的獲知性愿望。反映了螞蟻在處理問題過程中的閱歷積累和向其他螞蟻學(xué)習(xí)的才干。信息素有添加和減少兩方面。揮發(fā)機(jī)制是為了防止殘留信息素過多導(dǎo)致殘留信息淹沒啟發(fā)信息。部分信息素更新 部分信息素更新的作用是使已選的邊對(duì)后來的螞蟻具有較小的影響力，從而使螞蟻對(duì)沒有被選中的邊有更強(qiáng)的探求才干。 在ACS算法中，當(dāng)螞蟻從城市i轉(zhuǎn)移到城市j后，邊ij上的信息素量按下式進(jìn)展更新：其中0為常數(shù)，(0,1)為可調(diào)參數(shù)。全局信息素更新針對(duì)全局最優(yōu)解所屬的邊按下式進(jìn)展更新：其中Lgb為當(dāng)前最好解的長度，為信息素蒸發(fā)系數(shù)。

5、轉(zhuǎn)換規(guī)那么： 在ACS算法中，螞蟻運(yùn)用偽隨機(jī)比率選擇規(guī)那么選擇下一座城市。即對(duì)位于城市i的螞蟻k，以概率q0挪動(dòng)到城市l(wèi)，其中l(wèi)為使il (t)*il 到達(dá)最大的城市。該選擇方式意味著螞蟻將以概率q0將最大能夠的城市選入螞蟻所構(gòu)造的解；除此之外，螞蟻以(1-q 0) 的概率按下式選擇下一座城市j。在ACS算法中，螞蟻的形狀轉(zhuǎn)移公式為： 其中q0 (0,1)為常數(shù)，q(0,1)為隨機(jī)數(shù)，iu (t)表示t時(shí)辰城市i與城市u之間的信息素，iu表示城市i與城市u之間的啟發(fā)式因子，表示啟發(fā)式因子的相對(duì)強(qiáng)弱。在選擇下一座城市之前隨機(jī)生成q，假設(shè)q的值小于等于常數(shù)q0，那么從城市i到一切可行的城市中找出

6、iu (t) iu最大的城市，即為下一個(gè)要選擇的城市；假設(shè)隨機(jī)數(shù)q大于q0，那么按下式來選擇下一座城市。其中Jk(i)為螞蟻k當(dāng)前的可行城市集合。上述四個(gè)要素控制著螞蟻系統(tǒng)實(shí)現(xiàn)途徑選擇和信息素更新戰(zhàn)略，兩者相互配合，實(shí)現(xiàn)模型的正負(fù)反響機(jī)制，促使人工螞蟻收斂于最優(yōu)解。 ACS算法可以表述如下：在算法的初始時(shí)辰，將m只螞蟻隨機(jī)地放到n座城市，同時(shí)，將每只螞蟻的忌諱表的第一個(gè)元素設(shè)置為它當(dāng)前所在的城市。此時(shí)各途徑上的信息素量相等，設(shè)ij (0)= C C為一較小的常數(shù)。接下來，每只螞蟻根據(jù)途徑上殘留的信息素量和啟發(fā)式信息兩城市間的間隔獨(dú)立地選擇下一座城市。蟻群算法的參數(shù)信息素的相對(duì)重要程度；啟發(fā)式因子的相對(duì)重要程度；信息素蒸發(fā)系數(shù)(1-)表示信息素的耐久性系數(shù)；Q螞蟻釋放的信息素量。結(jié)果分析 經(jīng)過對(duì)PCB板的焊接途徑優(yōu)化，最終仿真結(jié)果比為優(yōu)