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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

(2)

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

1.3 進(jìn)化選擇

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

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

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

1.4 追隨算子

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

圖1 追隨算子原理圖

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

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

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

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

1.5 盤(pán)旋算子

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

圖2 盤(pán)旋算子原理圖

隨機(jī)選擇兩個(gè)點(diǎn)x3,x4,這里取x3,x4分別為點(diǎn)2,5,將兩點(diǎn)之間的排列2,3,4,5逆序排列成5,4,3,2插回原位置,完成一次盤(pán)旋操作.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 bayg29 運(yùn)行結(jié)果圖

圖5 att48運(yùn)行結(jié)果圖

圖6 eli51運(yùn)行結(jié)果圖

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

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

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

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

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

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

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

表1 對(duì)照組運(yùn)行結(jié)果

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

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

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

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

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

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

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

表3 無(wú)參考粒子運(yùn)行結(jié)果

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

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

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

各算法對(duì)所列數(shù)據(jù)運(yùn)行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.

各算法運(yùn)行結(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)定性較好,對(duì)不同的數(shù)據(jù)有所差異,但總體較所列其他算法有很大的提升.

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

表5 各算法運(yùn)行結(jié)果對(duì)比分析對(duì)比

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

圖7 eli51收斂曲線

2.6 轎車白車身車門(mén)焊點(diǎn)路徑仿真分析

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

圖8 轎車車門(mén)焊點(diǎn)圖

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

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

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

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

3 結(jié)語(yǔ)

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

仿真結(jié)果表明：改進(jìn)的粒子群算法可以有效優(yōu)化白車身的焊接路徑,對(duì)于中小規(guī)模的白車身焊點(diǎn)TSP,設(shè)計(jì)的改進(jìn)粒子群算法有良好的尋優(yōu)能力,優(yōu)化精度和穩(wěn)定性較好.對(duì)較大規(guī)模的白車身焊點(diǎn)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é)報(bào)(自然科學(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é)報(bào),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é)報(bào)(自然科學(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] 周雅蘭,王甲海,黃聰.求解排列問(wèn)題的分布估計(jì)離散粒子群優(yōu)化算法[J].電子學(xué)報(bào),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)粒子群的焊點(diǎn)檢測(cè)路徑規(guī)劃方法[J].儀器儀表學(xué)報(bào),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] 時(shí)應(yīng)盼.基于離散精英粒子群算法的焊接機(jī)器人路徑規(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é)基金資助項(xiàng)目(E2014502042);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(11QJ61)

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

TP 183

A

1672-5581(2017)02-0099-08