優(yōu)化樂 英,岳艷波

(華北電力大學(xué) 能源動力與機械工程學(xué)院,河北 保定071000)

?

基于改進(jìn)粒子群算法的白車身焊接路徑

優(yōu)化樂 英,岳艷波

(華北電力大學(xué) 能源動力與機械工程學(xué)院,河北 保定071000)

為優(yōu)化白車身焊接路徑,提高焊接效率,提出一種改進(jìn)粒子群算法,在傳統(tǒng)粒子群算法思想的基礎(chǔ)上,將算法尋優(yōu)過程分為追隨和盤旋兩部分.基于較近原則生成初始粒子,以減少種群規(guī)模,加快收斂速度;在追隨部分,通過個體極值追隨全局極值和隨機原始參考值以貪婪重組的方式重新生成粒子,在增強算法局部尋優(yōu)能力的同時加快算法的收斂速度;在盤旋部分,采用多次局部調(diào)序的策略,通過隨機調(diào)整粒子局部排列序,保證算法種群的多樣性,防止陷入局部最優(yōu)解;從種群進(jìn)化代數(shù)和種群個體適應(yīng)度函數(shù)值實現(xiàn)算法各參數(shù)的自適應(yīng)調(diào)節(jié),加快收斂速度;對粒子個體采取精英保留策略,保留最優(yōu)粒子.算法通過Matlab平臺實現(xiàn),實驗仿真結(jié)果表明,提出的改進(jìn)粒子群算法對于中小規(guī)模的白車身焊點旅行推銷員問題(Travelling Salesman Problem,TSP)有良好的尋優(yōu)能力.

焊接路徑; 改進(jìn)粒子群; 貪婪重組; 多次局部調(diào)序; 自適應(yīng)調(diào)節(jié)

汽車白車身有上千個焊點,合理地規(guī)劃這些焊點順序可以有效提升生產(chǎn)節(jié)拍,提高生產(chǎn)效率.白車身焊點路徑的優(yōu)化問題可以歸結(jié)為旅行推銷員或貨郎擔(dān)問題(Travelling Salesman Problem,TSP)[1-2],因此研究TSP具有很重要的現(xiàn)實和理論意義.

求解TSP的方法有很多,而各種智能算法是其中的一個重要研究內(nèi)容,例如遺傳算法、模擬退火法、蟻群算法、人工魚群算法和粒子群算法等.其中粒子群算法因具有易理解、調(diào)節(jié)參數(shù)少、收斂速度快、易于實現(xiàn)等優(yōu)點,在組合優(yōu)化問題領(lǐng)域有很強的應(yīng)用價值.但是,標(biāo)準(zhǔn)粒子群算法在求解TSP時,易陷入局部最優(yōu)解,求解精度不高,為此,眾多學(xué)者對其進(jìn)行了很多改進(jìn).

采用粒子群算法與其他智能算法結(jié)合的混合算法是其中的一個熱點.文獻(xiàn)[3-5]采用蟻群算法和粒子群算法的混合算法,求解旅行商問題的最優(yōu)解.文獻(xiàn)[6-7]通過經(jīng)粒子群算法優(yōu)化參數(shù)后的蟻群算法來求解TSP.文獻(xiàn)[8]采用神經(jīng)網(wǎng)絡(luò)和粒子群算法相結(jié)合的混合算法,提高了算法的收斂速度和尋優(yōu)能力.文獻(xiàn)[9]將混沌原理應(yīng)用于粒子群算法中,提高了算法的尋優(yōu)性能,混合算法不同程度上提高了算法的尋優(yōu)性能,但尋優(yōu)過程較為復(fù)雜.文獻(xiàn)[10]分析比較了粒子群算法的參數(shù)與求解的最優(yōu)解關(guān)系,求出了最優(yōu)解的參數(shù)區(qū)間.文獻(xiàn)[11]通過分析比較幾種不同的變異策略,提出了近鄰搜索優(yōu)化策略.文獻(xiàn)[12]通過引入個體最優(yōu)值分布信息的概率模型,提高了算法的尋優(yōu)能力.文獻(xiàn)[13]通過在粒子群算法中引入遺傳算法的算子,并通過改進(jìn)計算公式改善算法的性能.文獻(xiàn)[14]改進(jìn)了粒子群算法,通過設(shè)計新的粒子群算子來提高算法的尋優(yōu)能力.文獻(xiàn)[15]在粒子速度更新方程中加入鄰域信息,提高算法收斂精度.

針對工業(yè)生產(chǎn)領(lǐng)域的TSP,結(jié)合標(biāo)準(zhǔn)粒子群算法的特點,提出一種改進(jìn)的粒子群算法.在粒子群算法思想的基礎(chǔ)上,參考其他智能算法的尋優(yōu)過程,重新設(shè)定了算法的尋優(yōu)過程.設(shè)計的算法通過Matlab平臺仿真實現(xiàn),采用通用的TSP數(shù)據(jù)庫進(jìn)行測試分析比較,驗證所改進(jìn)粒子群算法的有效性和穩(wěn)定性.

1 改進(jìn)的粒子群算法

粒子群算法最初解決的是連續(xù)性優(yōu)化問題,而TSP是離散型問題,為此，需要對算法中的符號和規(guī)則重新定義,主要基于速度-位置模型,由粒子個體追隨個體歷史最佳值和全局最佳值搜索最優(yōu)解.通過設(shè)定調(diào)節(jié)慣性參數(shù)和學(xué)習(xí)參數(shù),生成交換序形成新的粒子個體.

pbest為個體極值點,gbest為全局極值點,N維向量X為粒子信息，即X=(x1,x2,…,xn),速度為V=(v1,v2,…,vn),速度和粒子的更新方程為

(1)

式中:w為慣性系數(shù);c1和c2為學(xué)習(xí)因子;r1和r2為[0,1]之間的隨機數(shù).

與上述原理不同,本文采用一種貪婪重組方式生成新的粒子個體,同時，加入了局部調(diào)整和精英保留的策略.

1.1 基于較近原則生成初始解

一般在TSP問題的最優(yōu)解中,與某個城市相鄰的城市都是距離其較近的城市,但不一定是距離其最近的城市.若隨機生成初始解,需要較大的初始粒子種群和迭代次數(shù),這將影響算法的收斂速度,且容易陷入局部最優(yōu)解.這里采用較近原則生成初始解.首先，由所有城市中隨機選取一個城市作為初始點x1;然后,在距離x1最近的pn個城市中隨機選取一個城市作為第二個城市x2,以此類推,直到遍歷所有城市,生成一個初始粒子.pn的取值依數(shù)據(jù)的規(guī)模設(shè)定,粒子種群規(guī)模大時取較大值,規(guī)模小時取較小值.取值過大會影響算法收斂速度,達(dá)不到設(shè)置的效果;過小影響種群的多樣性,容易陷入局部最優(yōu)解.重復(fù)上述過程生成n個初始解.

1.2 計算種群個體的適應(yīng)度

本文基于路徑最短原則,以遍歷所有城市回到出發(fā)點距離的倒數(shù)為適應(yīng)度函數(shù)的大小,如下:

(2)

式中:f(i)為每個粒子個體的適應(yīng)度函數(shù)值;T(i)為每個粒子個體中城市之間的距離.

1.3 進(jìn)化選擇

每次進(jìn)化前,采用精英策略,將個體適應(yīng)度最差的c個個體用最好的c個個體代替.

每次進(jìn)行追隨和盤旋操作后生成的新粒子個體,都與原粒子個體進(jìn)行比較,若原個體適應(yīng)度值較大,則恢復(fù)為原個體.

本文以進(jìn)化的代數(shù)作為算法終止的條件.

1.4 追隨算子

為了提高算法的局部尋優(yōu)能力,引入一個追隨算子,通過個體極值追隨全局極值和隨機原始參考值以一種啟發(fā)式貪婪重組的方式重新生成粒子個體,防止陷入局部最優(yōu)解.具體原理如圖1所示.

圖1 追隨算子原理圖

圖中:p1為粒子個體歷史最佳值;p2為由2.1節(jié)隨機生成的初始參考粒子;p3為粒子群體全局最佳值.隨機選擇一個點作為初始點x1,圖中x1取p2中的城市6,將城市6加入備選粒子p4中,然后由p1,p2,p33個粒子中找到城市6相應(yīng)的下一個城市分別為城市7,1,4,比較3個城市與城市6距離的大小,若城市1距離最近,將城市1加入到備選粒子p4中,同時刪除p1,p2,p33個粒子中的6序號,以此類推,直到生成完整的備選個體p4,完成一次追隨操作.將p4與p1進(jìn)行比較,若優(yōu)于p1,則將p4作為新的粒子,否則保持粒子p1不變.每次追隨操作隨機選擇某城市的下一個城市是向前選取或是向后選取.

由于在算法的每次迭代中,各個不同的個體都追隨同一個全局極值,隨著進(jìn)化的進(jìn)行,各個粒子的相似度會越來越高,種群多樣性下降,容易陷入局部最優(yōu)解.因此,每次重組時加入一個原始隨機參考粒子可有效保持粒子的多樣性,增加優(yōu)良排列結(jié)構(gòu)的備選個數(shù),提高收斂精度.

粒子個體是否參與追隨操作由追隨概率pf控制.在進(jìn)化前期,適當(dāng)大小的追隨概率能有效加快算法收斂速度.當(dāng)種群進(jìn)化到一定代數(shù),過大的追隨概率可能會破壞潛在最優(yōu)解的結(jié)構(gòu),這里設(shè)置隨進(jìn)化的進(jìn)行,梯級減小追隨概率的數(shù)值,以保存潛在最優(yōu)解,同時加快算法收斂速度.追隨概率pf的數(shù)值設(shè)置如下:

式中:pfmax,pfmin分別為與種群進(jìn)化代數(shù)相對應(yīng)的最大、最小追隨概率;pave為粒子群個體的平均適應(yīng)度值大小;G為最大進(jìn)化代數(shù);g為當(dāng)前進(jìn)化代數(shù).

1.5 盤旋算子

盤旋算子可有效增強算法的局部尋優(yōu)能力,防止算法陷入局部最優(yōu)解.通過隨機選取兩個城市點,將兩點之間的排列以逆序排列并重新插回原處.盤旋算子原理如圖2所示.

圖2 盤旋算子原理圖

隨機選擇兩個點x3,x4,這里取x3,x4分別為點2,5,將兩點之間的排列2,3,4,5逆序排列成5,4,3,2插回原位置,完成一次盤旋操作.

在盤旋操作中,隨機點x3和x4之間的間隔pd對算子的性能有很大影響,以數(shù)據(jù)bayg29為例,間隔數(shù)pd在1～28之間隨機選取,將一次程序運行后盤旋操作的總次數(shù)、成功優(yōu)化次數(shù)以及相應(yīng)的間隔數(shù)目加以統(tǒng)計,如圖3所示.

圖3 間隔數(shù)目與算子性能關(guān)系

圖3中,每次盤旋操作的間隔數(shù)目pd隨機選擇,由圖可知(間隔數(shù)pd最大為28,pd取28和27時,粒子的排列順序雖然有變化,但是粒子個體的相對排列順序不變),算子操作成功率以pd取最大和最小的部分比較高,且基本呈對稱分布.以對稱點為界,分別取相應(yīng)的較小pd值和較大pd值.pd取1和26時的優(yōu)化成功率要比其他值高很多,因此，在選擇間隔數(shù)pd時,增大這兩個數(shù)的被選擇概率,并依據(jù)粒子種群規(guī)模的大小,合理選擇兩側(cè)一定數(shù)量的間隔數(shù).

兩隨機點之間間隔選取規(guī)則如下:

由兩邊各選擇pd個間隔數(shù)再加上兩個最大和最小的間隔數(shù),盤旋操作時由這些數(shù)中隨機選擇一個.以bayg29為例,若pd為3,則備選間隔數(shù)組成的數(shù)列為[1 2 3 26 25 24 1 26].

由圖3可以看出,盡管優(yōu)化的總次數(shù)很多,但是成功優(yōu)化的次數(shù)并不多,優(yōu)化成功率比較低,尤其是到了粒子種群進(jìn)化后期,各個粒子越來越接近最優(yōu)解,優(yōu)化成功率會更低(圖中數(shù)據(jù)是采用多次調(diào)整局部排序的策略得出),因此，加大每次盤旋操作中局部調(diào)序的次數(shù)是必要的.

為了提高盤旋算子的局部搜索能力,采用多次調(diào)整局部排序的策略,每個粒子個體所進(jìn)行的盤旋操作次數(shù)以其適應(yīng)度為基礎(chǔ)自適應(yīng)調(diào)節(jié),每次盤旋操作隨機不重復(fù)地選擇盤旋點.這里設(shè)置一個盤旋因子pgp,其數(shù)值為0～1之間的數(shù),用以調(diào)節(jié)調(diào)整排序的次數(shù).其值為0時,不進(jìn)行盤旋操作;為1時,進(jìn)行所有可進(jìn)行的盤旋操作.種群是否參與盤旋操作由盤旋概率pg控制,設(shè)置盤旋因子pgp與pg的取值相同.

隨著進(jìn)化的進(jìn)行,種群中的粒子個體越來越接近于最優(yōu)解,此時,較大盤旋概率和盤旋因子可能會破壞潛在最優(yōu)解的排列,這里設(shè)置隨進(jìn)化的進(jìn)行,梯級減小盤旋概率和盤旋因子的數(shù)值,以保存潛在最優(yōu)解,同時加快算法收斂速度.設(shè)置pg的數(shù)值如下:

1.6 改進(jìn)算法的基本流程

步驟1 基于較近原則生成n個粒子種群;

步驟2 依據(jù)適應(yīng)度函數(shù)計算每個粒子個體的適應(yīng)度值大小;

步驟3 依精英保留策略進(jìn)行選擇操作,保留適應(yīng)度值高的粒子個體;

步驟4 依追隨概率進(jìn)行追隨操作;

步驟5 依盤旋概率和盤旋因子進(jìn)行盤旋操作;

步驟6 判斷是否滿足迭代結(jié)束條件,如果滿足條件,則結(jié)束迭代,輸出結(jié)果,否則轉(zhuǎn)到步驟2.

2 算法運行結(jié)果及分析

為了驗證本文中所提算子和策略對改進(jìn)粒子群算法性能的影響,以tsplib中的bayg29,att48和eli51中的數(shù)據(jù)為例進(jìn)行分析,通過對比分析,采用不同參數(shù)改進(jìn)算法的運行結(jié)果,驗證所提理論的正確性.算法在Matlab平臺上運行實現(xiàn).

2.1 最近個數(shù)對改進(jìn)算法的影響

對3種數(shù)據(jù)的最近個數(shù)pn設(shè)置為1～15共15個數(shù),改進(jìn)算法對每個最近個數(shù)均運行100次.由于算法中間隔數(shù)pd的設(shè)置對算法性能有很大影響,為排除間隔數(shù)pd設(shè)置對結(jié)果的影響,每種數(shù)據(jù)的每個最近個數(shù)對應(yīng)兩個不同的間隔數(shù).

算法對應(yīng)于3種數(shù)據(jù)的基本參數(shù)設(shè)置如下:

bayg29:種群規(guī)模30個,迭代次數(shù)50次;

att48:種群規(guī)模50個,迭代次數(shù)100次;

eli51:種群規(guī)模50個,迭代次數(shù)100次.

最近個數(shù)pn運行結(jié)果圖如圖4、圖5和圖6中的(a),(b)子圖所示.

圖4 bayg29 運行結(jié)果圖

圖5 att48運行結(jié)果圖

圖6 eli51運行結(jié)果圖

由圖4、圖5和圖6可以看出,當(dāng)最近個數(shù)pn不同時,對應(yīng)于各數(shù)據(jù)其成功收斂到最優(yōu)結(jié)果的次數(shù)也不同.對于bayg29,由于其數(shù)據(jù)規(guī)模較小,由圖可以看出,pn取3時,其成功尋優(yōu)次數(shù)最多,隨著pn的增加,尋優(yōu)成功次數(shù)逐漸變少,最后在某一區(qū)域內(nèi)擺動.當(dāng)數(shù)據(jù)規(guī)模增大時,最佳的pn值也隨數(shù)據(jù)規(guī)模變大,對att48和eli51,其最佳的最近個數(shù)pn主要在6～8之間.綜合3張圖來看,算法對應(yīng)于依次增加的最近數(shù)pn的尋優(yōu)成功次數(shù),都有先增加后減少的趨勢.當(dāng)最近個數(shù)pn取1時,3種尋優(yōu)成功次數(shù)都比較少,說明生成初始種群時,下一個城市總選最近城市的策略并不是最佳的.

3張圖中的(a),(b)子圖其總體趨勢比較一致,都是先增大后減小,所反映出的最佳最近個數(shù)也比較接近,但是在數(shù)值大小方面有一定的差異,主要由于所取的間隔數(shù)不同,說明不同的間隔數(shù)對改進(jìn)算法的性能有一定的影響,也說明了對算法而言,最近個數(shù)pn的選取和間隔數(shù)pd的選取沒有必然的聯(lián)系.

2.2 間隔數(shù)對改進(jìn)算法的影響

為驗證間隔數(shù)對改進(jìn)算法性能的影響,設(shè)置間隔數(shù)pd為1～10共10個數(shù),3種數(shù)據(jù)的每個間隔數(shù)也都對應(yīng)兩個不同的最近個數(shù).算法對應(yīng)于3種數(shù)據(jù)的基本參數(shù)設(shè)置同2.1節(jié),運行結(jié)果如圖4、圖5和圖6的(c),(d)子圖所示.

由圖4、圖5和圖6可以看出,隨著間隔數(shù)pd的增加,算法尋優(yōu)成功的次數(shù)也不相同.算法對各數(shù)據(jù)運行成功的次數(shù)也有先增加后減少的總體趨勢,且有一個或多個峰值.對于bayg29,其最佳間隔數(shù)pd的選取區(qū)間小些,而att48和eli51其最佳間隔數(shù)pd的選取區(qū)間大些,說明隨著種群規(guī)模的增加,最佳間隔數(shù)pd也隨之變大.

同樣3張圖中的(c),(d)子圖在總體趨勢上比較相似,在數(shù)值大小上有所差異,這是由于選取的最近個數(shù)pn不同,也說明最近個數(shù)pn的選取對算法的性能有一定的影響.由圖4的(a),(b)子圖可知,其最佳間隔數(shù)pd為3,對比(c),(d)子圖,可以看出,pn取3時,對應(yīng)不同的間隔數(shù)pd,算法尋優(yōu)成功次數(shù)大部分在70～80次之間,而當(dāng)pn取6時,尋優(yōu)成功次數(shù)多在50～60次之間.同樣由(c),(d)子圖可得最佳間隔數(shù)為3,對比(a),(b)子圖可以看出,當(dāng)間隔數(shù)取3時尋優(yōu)成功平均次數(shù)要高于間隔數(shù)取5時的平均次數(shù).由圖5和圖6中也可得出相類似的結(jié)論.

當(dāng)最近個數(shù)pn或間隔數(shù)pd取最大值,算法性能將有所下降,為此設(shè)置對照組,算法對每個對照組均運行100次,算法對每個數(shù)據(jù)的基本設(shè)置同2.1節(jié),其他設(shè)置和運行結(jié)果如表1所示.

表1 對照組運行結(jié)果

由表1可以看出,若不對最近個數(shù)和間隔數(shù)進(jìn)行規(guī)劃設(shè)置,算法性能將受到很大的影響.圖5中尋優(yōu)最佳次數(shù)最大值為84次,而表1中,若不對最近個數(shù)和間隔數(shù)同時進(jìn)行規(guī)劃設(shè)置,其成功次數(shù)只有31次.其他數(shù)據(jù)對比圖4、圖5和圖6中的最佳值也有類似的結(jié)論.

2.3 調(diào)序次數(shù)對改進(jìn)算法的影響

為了驗證本文采用多次調(diào)序策略的效果,設(shè)置3組實例進(jìn)行驗證.算法對3種數(shù)據(jù)的基本設(shè)置同2.1節(jié),每次算法迭代時采取單次調(diào)序的策略,其他設(shè)置和運行結(jié)果如表2所示.

表2 單次調(diào)序運行結(jié)果

由表2可以看出,若采用單次調(diào)序的策略,改進(jìn)算法的性能有很大下降.即使與表1的數(shù)據(jù)進(jìn)行對比,也有很大的差距.說明算法每次迭代時,調(diào)序的次數(shù)對算法的收斂精度有很大影響,加大調(diào)序的次數(shù)可以較大地提高算法的尋優(yōu)性能,但若次數(shù)過多,算法的運行時間會增加很大.因此,應(yīng)根據(jù)數(shù)據(jù)規(guī)模的大小和迭代的次數(shù)合理設(shè)置調(diào)序次數(shù).

2.4 原始隨機參考粒子對改進(jìn)算法的影響

加入原始隨機參考粒子有利于增加粒子種群的多樣性,為了驗證參考粒子的性能,設(shè)置3組實例進(jìn)行驗證,算法對3種數(shù)據(jù)的基本設(shè)置同2.1節(jié),每次算法迭代重組時無原始隨機參考粒子,其他設(shè)置和運行結(jié)果如表3所示.

表3 無參考粒子運行結(jié)果

由表3可以看出,對bayg29,當(dāng)數(shù)據(jù)量較少時,參考粒子對算法性能影響不大,當(dāng)數(shù)據(jù)規(guī)模增大時,無參考粒子的算法性能有了很大的下降,盡管pn和pd設(shè)置為較佳值,尋優(yōu)成功次數(shù)依然很低.說明對于較大規(guī)模的TSP,加入原始隨機參考粒子能有效提高算法尋優(yōu)精度,避免陷入局部最優(yōu)解.

2.5 改進(jìn)算法與其他算法的對比分析

為了分析比較改進(jìn)粒子群算法的綜合性能,采用通用的tsplib數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行分析驗證,并結(jié)合遺傳算法、傳統(tǒng)粒子群算法、蟻群算法等進(jìn)行比較.

各算法對所列數(shù)據(jù)運行100次,其中前4行數(shù)據(jù)種群規(guī)模取50,進(jìn)化代數(shù)為100;后4行取種群規(guī)模為100,進(jìn)化代數(shù)為200.各算法的參數(shù)設(shè)置如下:遺傳算法,pc=0.5,pm=0.8;蟻群算法,alpha為1,beta為5,rho為0.1,Q=100;傳統(tǒng)粒子群算法,w=1-g/G(G為最大進(jìn)化代數(shù);g為當(dāng)前進(jìn)化代數(shù).),c1=0.8,c2=0.7;改進(jìn)粒子群算法,pn=6,pd=6.

各算法運行結(jié)果分別如表4和表5所示.

由表4和表5可以看出，改進(jìn)的粒子群算法相較其他算法尋優(yōu)能力有很大改善,較少的迭代次數(shù)能搜索到最優(yōu)解.表4中,后4行數(shù)據(jù)若設(shè)定種群規(guī)模為100,進(jìn)化代數(shù)100,很難搜索到最優(yōu)解,適當(dāng)增大種群的規(guī)模和進(jìn)化的代數(shù),改進(jìn)粒子群算法的性能還可以進(jìn)一步提高,但提高到一定程度后,進(jìn)一步增大規(guī)模和迭代代數(shù),改進(jìn)算法的尋優(yōu)性能變化不大.表5中,改進(jìn)算法的穩(wěn)定性較好,對不同的數(shù)據(jù)有所差異,但總體較所列其他算法有很大的提升.

表4 算法運行結(jié)果

表5 各算法運行結(jié)果對比分析對比

以eli51數(shù)據(jù)為例,改進(jìn)粒子群算法運行后的收斂曲線如圖7所示.對于設(shè)定參數(shù)下的數(shù)據(jù),改進(jìn)的粒子群算法有良好的尋優(yōu)能力和收斂速度,算法迭代到30代左右就已經(jīng)搜索到最優(yōu)值.由于算法尋優(yōu)過程的隨機性,算法程序每次運行得到的收斂曲線均不相同,但總體趨勢保持一致.

圖7 eli51收斂曲線

2.6 轎車白車身車門焊點路徑仿真分析

以某轎車車門焊點路徑為例進(jìn)行分析,車門焊點示意圖及優(yōu)化前焊接路徑分別如圖8和圖9所示.

圖8 轎車車門焊點圖

圖9 優(yōu)化前的車門焊接路徑

在不考慮車門焊接變形的情況下,采用改進(jìn)的粒子群算法結(jié)果為580.244 5 cm,優(yōu)于文獻(xiàn)[16]中的結(jié)果601.69 cm.當(dāng)焊點數(shù)量進(jìn)一步增加時,優(yōu)化效果會更加明顯.優(yōu)化后的車門焊點路徑圖如圖10所示.

圖10 優(yōu)化后的車門焊接路徑

綜上可以看出,引入的兩個算子是有效的,提高了算法的收斂速度和局部尋優(yōu)能力.對于中小規(guī)模的數(shù)據(jù),改進(jìn)的粒子群算法可以搜索到最優(yōu)或接近最優(yōu)值的解.

3 結(jié)語

針對汽車車身焊點的TSP,提出一種改進(jìn)的粒子群算法.在粒子群算法思想的基礎(chǔ)上,重新設(shè)定了算法的尋優(yōu)過程,依據(jù)種群規(guī)模合理設(shè)置最近個數(shù)生成初始粒子,通過個體極值追隨全局極值和原始隨機參考值重新生成粒子,依據(jù)種群規(guī)模合理設(shè)置調(diào)序間隔數(shù)并采用了多次調(diào)整的策略.設(shè)計的改進(jìn)算法通過Matlab平臺仿真實現(xiàn),結(jié)合通用的TSP數(shù)據(jù)庫和車身焊點數(shù)據(jù)進(jìn)行測試分析比較,驗證尋優(yōu)結(jié)果的質(zhì)量.

仿真結(jié)果表明：改進(jìn)的粒子群算法可以有效優(yōu)化白車身的焊接路徑,對于中小規(guī)模的白車身焊點TSP,設(shè)計的改進(jìn)粒子群算法有良好的尋優(yōu)能力,優(yōu)化精度和穩(wěn)定性較好.對較大規(guī)模的白車身焊點TSP,要得到良好的解需要較大的粒子群體規(guī)模和進(jìn)化代數(shù)并調(diào)節(jié)相關(guān)的參數(shù),在后續(xù)研究中還須進(jìn)一步改進(jìn).

[1] 章權(quán),溫惠英,孫博.適于配送車輛導(dǎo)航路徑規(guī)劃的遍歷模型的改進(jìn)型粒子群優(yōu)化算法[J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2011,39(8):109-112,117.

ZHANG Quan,WEN Huiying,SUN Bo.Improved particle swarm optimization algorithm of ergodic model for routing planning of delivery vehicle navigation[J].Journal of South China University of Technology(Natural Science Edition),2011,39(8):109-112,117.

[2] 林巨廣,陳甦欣,戴淮初,等.蟻群算法在白車身底板焊接路徑規(guī)劃中的應(yīng)用[J].焊接學(xué)報,2015,36(1):5-9,113.

LIN Juguang,CHEN Suxin,DAI Huaichu,et al.Application of ant colony algorithm to process planning of welding path in BIW[J].Transactions of the China Welding Institution,2015,36(1):5-9,113.

[3] ELLOUMI W,ABED H E,ABRAHAM A,et al.A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP[J].Applied Soft Computing Journal,2014,25:234-241.

[4] BING S,CHEN J P,LI Z B.Study on hybrid PS-ACO algorithm[J].Applied Intelligence,2011,34(1):64-73.

[5] ZHANG Y,ZHANG M,LIANG Y C.A hybrid ACO/PSO algorithm and its applications[J].International Journal of Modelling,Identification and Control,2009,8(4):309-316.

[6] ROKBANI N,ABRAHAM A,ALIMI A M.Fuzzy ant supervised by PSO and simplified ant supervised PSO applied to TSP[C]//13th International Conference on Hybrid Intelligent Systems.Gammarth:IEEE,2013:251-255.

[7] 李擎,張超,陳鵬,等.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J].控制與決策,2013,28(6):873-878,883.

LI Qin,ZHANG Chao,CHEN Peng,et al.Improved ant colony optimization algorithm based on particle swarm optimization[J].Control and Decision,2013,28(6):873-878,883.

[8] LIU T D,ZHANG H F,GAO Y.Solving TSP via fuzzy dynamic PSO and HNN algorithm[C]//The 7th International Conference on Computer Science & Education.Melbourne:IEEE,2012:105-109.

[9] CHEN L G,WANG Z D,HE C Y.Chaos particle swarm optimization applications in the TSP problem[C]//Third International Conference on Genetic and Evolutionary Computing.Guilin:IEEE,2009:682-685.

[10] ZHANG J S,Lü R J,WANG L.Parameters analysis of PSO algorithm in intelligent system optimization[J].Journal of Applied Sciences,2013,13(22):5498-5502.

[11] 余伶俐,蔡自興.改進(jìn)混合離散粒子群的多種優(yōu)化策略算法[J].中南大學(xué)學(xué)報(自然科學(xué)版),2009,40(4):1047-1053.

YU Lingli,CAI Zixing.Multiple optimization strategies for improving hybrid discrete particle swarm[J].Journal of Central South University(Science and Technology),2009,40(4):1047-1053.

[12] 周雅蘭,王甲海,黃聰.求解排列問題的分布估計離散粒子群優(yōu)化算法[J].電子學(xué)報,2014,42(3):561-571.

ZHOU Yalan,WANG Jiahai,HUANG Cong.Estimation of distribution-discrete particle swarm optimization algorithm for permutation-based problems[J].Acta Electronica Sinica,2014,42(3):561-571.

[13] LIU Z,HUANG L.A mixed discrete particle swarm optimization for TSP[C]//2010 3rd International Conference on Advanced Computer Theory and Engineering.Chengdu:IEEE,2010:208-211.

[14] FAN H L,LI X L.Discrete particle swarm optimization for TSP based on neighborhood[J].Journal of Computational Information Systems,2010,6(10):3407-3414.

[15] 朱霞,陳仁文,徐棟霞,等.基于改進(jìn)粒子群的焊點檢測路徑規(guī)劃方法[J].儀器儀表學(xué)報,2014,35(11):2484-2493.

ZHU Xia,CHEN Renwen,XU Dongxia,et al.Welding spot detection path planning method based on a novel particle swarm algorithm[J].Chinese Journal of Scientific Instrument,2014,35(11):2484-2493.

[16] 時應(yīng)盼.基于離散精英粒子群算法的焊接機器人路徑規(guī)劃[D].上海:華東理工大學(xué),2015.

SHI Yingpan.Discrete elite PSO based welding robot path planning[D].Shanghai:East China University of Science and Technology,2015.

Research on process planning of welding path in BIW based on modified particle swarm algorithm

YUE Ying,YUE Yanbo

(School of Energy,Power and Mechanics Engineering,North China Electric Power University,Baoding 071000,Hebei,China)

A modified particle swarm algorithm is proposed to optimize the welding path and improve the welding efficiency.Based on the traditional particle swarm optimization algorithm,the optimization process of algorithm is subdivided under the following and gyrating.In order to reduce the population size and improve the convergence speed,the proximity principle is introduced into particle species initialization;in the following part,in order to keep the algorithm good convergence and improve the convergence speed,the particle is re-generated by means of the greedy recombination of the individual extreme value following global extreme value and random original reference value;in the gyrating part,in order to keep the population diversity and prevent the local minimum,a multi-bit adjustment order strategy is introduced,the partial arrangement of particles is randomly adjusted;the adaptive update of algorithm parameters is realized according to the evolution stages and the fitness value of particle individuals,and the convergence speed is improved;the optimal particle individual is propagated using the strategy of keeping the best individuals.The modified algorithm is realized using Matlab,the simulation results show that the proposed modified particle swarm optimization has a powerful search capability in solving travelling salesman problem (TSP).

welding path; modified particle swarm optimization; greedy restructuring;multi-bit adjustment order; adaptive adjustment

河北省自然科學(xué)基金資助項目(E2014502042);中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目(11QJ61)

樂 英(1971—),女,副教授,博士.E-mail:yueying71@163.com

TP 183

A

1672-5581(2017)02-0099-08