改進(jìn)粒子群算法在緊固螺母路徑中的優(yōu)化

陳 震，彭先濤

CHEN Zhen1，PENG Xian-tao2

(1.泰州職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，泰州 225300；2. 遼寧石油化工大學(xué) 信息與控制工程學(xué)院，撫順 113001)

0 引言

裝配生產(chǎn)線上緊固螺母路徑優(yōu)化問題是在一條裝配線上用一個(gè)機(jī)械手去緊固待裝配部件上的螺母問題。機(jī)械手由其初始位置開始，依次移動(dòng)到其余的每一個(gè)螺母，最后返回到初始的位置。機(jī)械手的運(yùn)行軌跡就是以螺母為節(jié)點(diǎn)的一條周游路線。優(yōu)化之前，機(jī)械手的運(yùn)行軌跡是隨機(jī)的，完成一塊板子的裝配耗時(shí)過長，使得生產(chǎn)效率低下，產(chǎn)品的成本較高，競(jìng)爭力低下。因此工藝上要求機(jī)械手運(yùn)行時(shí)間盡可能短，需要對(duì)機(jī)械手的運(yùn)行軌跡進(jìn)行優(yōu)化，從而使機(jī)械手完成對(duì)該配件的裝配總時(shí)間最小。該問題的最優(yōu)解就是尋找機(jī)械手在螺母間的最短運(yùn)行路徑，此時(shí)，該問題可以轉(zhuǎn)換為TSP問題。由此可見，該問題也是典型的多項(xiàng)式復(fù)雜程度的非確定性問題(Non-deterministic Polynomial的問題，NP問題)，即其最壞情況下的時(shí)間復(fù)雜度隨著問題規(guī)模的增大按指數(shù)方式增長，該問題的答案是無法直接計(jì)算得到的，只能通過間接的“猜算”來得到結(jié)果，到目前為止還沒有找到一個(gè)多項(xiàng)式時(shí)間的有效算法[1]。

1 解決方法的提出

目前這類問題的解決方法主要有：近鄰法、插入法、禁忌搜索算法[2]、遺傳算法[3]、模擬退火算法[4]等等。但以上方法各存在一些問題，近鄰法簡單，也許是多數(shù)人的直覺做法，但是近鄰法的短視使其表現(xiàn)非常不好，通常后段的路程會(huì)非常痛苦；插入法中點(diǎn)的選擇及法則的選取較繁瑣，且計(jì)算量大，前期的工作量很大，有先苦后甜的滋味；禁忌搜索算法是一種局部搜索能力很強(qiáng)的全局迭代尋優(yōu)算法，不足之處在于對(duì)初始解較強(qiáng)的依賴性和串行的迭代搜索過程[5]；GA兩個(gè)最顯著的優(yōu)點(diǎn)是隱含并行性和全局解空間搜索，但實(shí)際應(yīng)用時(shí)易出現(xiàn)早熟收斂和收斂性能差等缺點(diǎn)[4]；模擬退火算法突出地具有脫離局域最優(yōu)陷阱的能力，實(shí)驗(yàn)性能具有質(zhì)量高、初值魯棒性強(qiáng)、通用易實(shí)現(xiàn)的優(yōu)點(diǎn)，最大缺點(diǎn)是往往優(yōu)化過程較長[5]。

粒子群優(yōu)化算法(Particle Swarm Optimization ，PSO)是一種基于群體智能的新興演化計(jì)算技術(shù)[6]，廣泛用于解決科學(xué)研究和工程實(shí)踐中的優(yōu)化問題。PSO通過粒子追隨自己找到的最好解和整個(gè)群的最好解來完成優(yōu)化。該算法簡單易實(shí)現(xiàn)，可調(diào)參數(shù)少，已得到廣泛研究和應(yīng)用。PSO算法求解優(yōu)化問題時(shí)，算法中每個(gè)粒子都代表問題的一個(gè)潛在解，每個(gè)粒子對(duì)應(yīng)一個(gè)由適應(yīng)度函數(shù)決定的適應(yīng)度值，問題的解對(duì)應(yīng)于搜索空間中一個(gè)粒子(或稱為主體)的位置，每個(gè)粒子都有自己的位置和速度(決定自身飛行的方向和距離)。各個(gè)粒子記憶、追隨當(dāng)前的最優(yōu)粒子，在解空間中搜索。每次迭代的過程不是完全隨機(jī)的，如果找到較好解，將會(huì)以此為依據(jù)來尋找下一個(gè)解[7～9]。PSO的優(yōu)點(diǎn)是簡單且易于實(shí)現(xiàn)，沒有許多參數(shù)需要進(jìn)行調(diào)整[3]。

PSO算法有全局版本和局部版本，這兩個(gè)版本的差別在于粒子的鄰域不同，研究發(fā)現(xiàn)，全局PSO算法收斂較快，但易陷入局部最優(yōu)，而局部PSO算法可搜索到更優(yōu)的解，但速度稍慢?？梢娝惴ㄟx擇的領(lǐng)域不同，會(huì)對(duì)算法的性能有很大的影響。同時(shí)基本PSO算法局部搜索能力較差，搜索精度不高，不能保證搜索到全局最優(yōu)解；隨著迭代次數(shù)的增加，當(dāng)種群收斂集中時(shí)，各粒子也越來越相似，容易陷入局部最優(yōu)解而無法跳出；對(duì)參數(shù)有一定的依賴性等不足之處[11]。因此，對(duì)PSO提出改進(jìn)，以提高PSO的搜索能力具有很高的研究意義，一些成果可參考文獻(xiàn)[10]。本文采用將GA[11]與PSO相結(jié)合得到的GA-PSO對(duì)該問題進(jìn)行優(yōu)化：摒棄傳統(tǒng)PSO中通過跟蹤極值來更新粒子位置的方法，引入GA中的交叉和變異操作，通過粒子同個(gè)體極值和群體極值的交叉、粒子自身變異的方式來搜索最優(yōu)解。仿真結(jié)果表明改進(jìn)的PSO能夠很好的跳出局部極小值，較快地尋找到機(jī)械手的最優(yōu)運(yùn)行路徑。

2 GA-PSO

本文采用GA-PSO實(shí)現(xiàn)緊固螺母路徑優(yōu)化問題的具體步驟如下：

1)種群初始化：初始產(chǎn)生1000個(gè)粒子。

2)個(gè)體編碼：粒子個(gè)體編碼采用采用整數(shù)編碼，每個(gè)粒子表示歷經(jīng)的所有螺母，如當(dāng)經(jīng)歷的螺母數(shù)為9，個(gè)體編碼為[5 9 3 6 7 2 1 4 8]，表示螺母遍歷從5開始，經(jīng)過9，3，6，7，2，1，4，8，最終返回螺母5，完成TSP遍歷。

3)計(jì)算適應(yīng)度值

適應(yīng)度值表示為機(jī)械手遍歷路徑的長度，按公式（1）進(jìn)行計(jì)算，其中Li,j為螺母i，j間的距離。

4)粒子的更新：粒子的速度和位置按式（2）、（3）進(jìn)行更新：

5)交叉操作：交叉操作包括個(gè)體最優(yōu)交叉(個(gè)體與個(gè)體極值交叉更新)和群體最優(yōu)交叉(個(gè)體與群體極值進(jìn)行交叉更新)，交叉操作采用整數(shù)交叉法。先選擇兩個(gè)交叉位置，然后分別進(jìn)行個(gè)體最優(yōu)交叉、群體最優(yōu)交叉，假定隨機(jī)選取的交叉位置為2和4，操作如下：

產(chǎn)生的新個(gè)體如果存在重復(fù)位置則對(duì)其進(jìn)行調(diào)整，采用的調(diào)整方法為用個(gè)體中未包括的螺母代替重復(fù)包括的螺母，具體如下：

6)粒子變異操作：變異操作采用個(gè)體內(nèi)部兩位互換法，先隨機(jī)選擇兩個(gè)變異位置，然后把兩個(gè)變異位置進(jìn)行互換，如假定選擇的變異位置為3和6，變異操作如下：

同時(shí)對(duì)得到的新個(gè)體采用了保留優(yōu)秀個(gè)體的策略，只有當(dāng)新離子適應(yīng)度值好于舊粒子時(shí)才對(duì)粒子進(jìn)行更新。

7)判斷算法是否結(jié)束：算法結(jié)束條件為迭代200次。

3 GA-PSO仿真研究

本文以浙江寧波某汽車配件廠某條流水線上的某型號(hào)配件上的螺母固定為研究對(duì)象，數(shù)據(jù)如圖1所示。

圖1 螺母坐標(biāo)數(shù)據(jù)

機(jī)械手在每個(gè)螺母上停留的時(shí)間為4s(機(jī)械手移動(dòng)到待固定的螺母上方、對(duì)螺母進(jìn)行固定、離開螺母的總時(shí)間)，機(jī)械手在螺母間的運(yùn)動(dòng)速度為勻速(5cm/s)。對(duì)該問題進(jìn)行優(yōu)化得到的目標(biāo)是使機(jī)械手在對(duì)該配件上所有螺母進(jìn)行固定后的總時(shí)間最小，也就是使機(jī)械手在該配件上所有螺母間的移動(dòng)路徑最短。

本文改進(jìn)的粒子群算法(GA-PSO)的流程圖如圖2所示。

圖2 GA-PSO算法螺母緊固優(yōu)化路徑流程圖

用GA-PSO算法進(jìn)行Matlab仿真研究得到仿真結(jié)果如圖3、圖4所示。可尋到的機(jī)械手最優(yōu)運(yùn)行軌跡如圖3所示。迭代過程如圖4所示。

圖3 GA-PSO算法尋找的機(jī)械手最優(yōu)運(yùn)行路徑

圖4 GA-PSO算法的迭代過程

機(jī)械手最優(yōu)運(yùn)行路徑為：

6-1-11-8-12-13-19-10-15-23-21-16-18-20-17-14-22-5-2-4-7-3-9-6

機(jī)械手運(yùn)行最短距離：297.6495(cm)

機(jī)械手完成裝配最短時(shí)間：151.539(s)

4 結(jié)果比較與分析

作為對(duì)比，本文也采用蟻群算法(Ant Colony Optimization，ACO)對(duì)該問題進(jìn)行研究，與GAPSO進(jìn)行對(duì)比，以驗(yàn)證改進(jìn)算法的有效性。本文采用的ACO解決緊固螺母路徑優(yōu)化問題的流程圖如圖5所示。

圖5 ACO算法螺母緊固優(yōu)化路徑流程圖

ACO可尋優(yōu)到的機(jī)械手最優(yōu)路徑如圖6所示。迭代過程如圖7所示。

圖6 ACO算法尋找的機(jī)械手最優(yōu)運(yùn)行路徑

圖7 ACO算法的迭代過程

機(jī)械手最優(yōu)運(yùn)行路徑:

5-7-2-4-3-9-6-8-11-1-10-19-12-13-15-23-21-16-18-20-17-14-22-5

機(jī)械手運(yùn)行最短距離: 297.978(cm)

機(jī)械手完成裝配最短時(shí)間：151.5956(s)

5 結(jié)束語

本文采用將GA中的交叉和變異操作引入到PSO中得到的改進(jìn)的粒子群算法GA-PSO對(duì)該問題進(jìn)行研究，通過大量的仿真進(jìn)行研究，作為對(duì)比，本文也采用了ACO對(duì)該問題進(jìn)行研究。仿真結(jié)果表明兩種算法都能在較短的時(shí)間內(nèi)尋找到最優(yōu)解，但GA-PSO能夠跳出局部極小值(在優(yōu)化距離上精確了0.3cm左右，在運(yùn)行時(shí)間上精確了0.06s左右)，快速、穩(wěn)定的尋找到最優(yōu)路徑，驗(yàn)證了改進(jìn)算法的有效性。而且，ACO中所要設(shè)置的參數(shù)較多且參數(shù)的設(shè)置值對(duì)算法性能的影響很大。

改進(jìn)的粒子群算法GA-PSO通過在浙江寧波某汽車配件廠流水線上的使用，有效地求解出機(jī)械手的最短路徑，縮短機(jī)械手工位的作業(yè)時(shí)間，提高生產(chǎn)節(jié)拍，大大提高流水線的生產(chǎn)效率，從而節(jié)約成本，提高企業(yè)競(jìng)爭力，使生產(chǎn)效益最大化。

[1] 史峰,王輝,郁磊,胡斐.MATLAB智能算法30個(gè)案例分析[M].北京:北京航空航天大學(xué)出版社,2011.

[2] 田貴超,黎明,韋雪潔.旅行商問題(TSP)的幾種求解方法[J].計(jì)算機(jī)仿真.2006,23(08):153-157.

[3] 劉青鳳,李敏.基于遺傳算法的TSP問題優(yōu)化求解[J].計(jì)算機(jī)與現(xiàn)代化,2008(02):43-45.

[4] 馮劍,岳琪.模擬退火算法求解TSP問題[J].森林工程,2008,24(1):94-96.

[5] 高海昌,馮博琴,朱利.智能優(yōu)化算法求解TSP問題[J].控制與決策.2006,21(03):241-247.

[6] 胡中功,李靜.群智能算法的研究進(jìn)展[J].自動(dòng)化技術(shù)與應(yīng)用.2008,27(2):13-15.

[7] 劉波.粒子群優(yōu)化算法及其工程應(yīng)用[M].北京:電子工業(yè)出版社.2010.

[8] 楊維,李歧強(qiáng).粒子群優(yōu)化算法綜述[J].中國工程科學(xué).2004,6(5):87-94.

[9] 紀(jì)震,廖惠連,吳青華.粒子群算法及應(yīng)用[M].北京:科學(xué)出版社.2009.1:第1版。

[10] Lv Zhensu,Hou Zhirong.Particle Swarm Optimization with Adaptive Mutation[J].Acta Electronica Sinica,2004,32(3):416-420.

[11] 鄧先習(xí).遺傳算法求解TSP問題的研究與改進(jìn)[D].沈陽:東北大學(xué),2008.6.