改進粒子群算法在緊固螺母路徑中的優化

陳 震，彭先濤

CHEN Zhen1，PENG Xian-tao2

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

0 引言

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

1 解決方法的提出

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

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

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

2 GA-PSO

本文采用GA-PSO實現緊固螺母路徑優化問題的具體步驟如下：

1)種群初始化：初始產生1000個粒子。

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

3)計算適應度值

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

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

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

產生的新個體如果存在重復位置則對其進行調整，采用的調整方法為用個體中未包括的螺母代替重復包括的螺母，具體如下：

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

同時對得到的新個體采用了保留優秀個體的策略，只有當新離子適應度值好于舊粒子時才對粒子進行更新。

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

3 GA-PSO仿真研究

本文以浙江寧波某汽車配件廠某條流水線上的某型號配件上的螺母固定為研究對象，數據如圖1所示。

圖1 螺母坐標數據

機械手在每個螺母上停留的時間為4s(機械手移動到待固定的螺母上方、對螺母進行固定、離開螺母的總時間)，機械手在螺母間的運動速度為勻速(5cm/s)。對該問題進行優化得到的目標是使機械手在對該配件上所有螺母進行固定后的總時間最小，也就是使機械手在該配件上所有螺母間的移動路徑最短。

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

圖2 GA-PSO算法螺母緊固優化路徑流程圖

用GA-PSO算法進行Matlab仿真研究得到仿真結果如圖3、圖4所示。可尋到的機械手最優運行軌跡如圖3所示。迭代過程如圖4所示。

圖3 GA-PSO算法尋找的機械手最優運行路徑

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

機械手最優運行路徑為：

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

機械手運行最短距離：297.6495(cm)

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

4 結果比較與分析

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

圖5 ACO算法螺母緊固優化路徑流程圖

ACO可尋優到的機械手最優路徑如圖6所示。迭代過程如圖7所示。

圖6 ACO算法尋找的機械手最優運行路徑

圖7 ACO算法的迭代過程

機械手最優運行路徑:

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

機械手運行最短距離: 297.978(cm)

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

5 結束語

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

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

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

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

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

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

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

[6] 胡中功,李靜.群智能算法的研究進展[J].自動化技術與應用.2008,27(2):13-15.

[7] 劉波.粒子群優化算法及其工程應用[M].北京:電子工業出版社.2010.

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

[9] 紀震,廖惠連,吳青華.粒子群算法及應用[M].北京:科學出版社.2009.1:第1版。

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

[11] 鄧先習.遺傳算法求解TSP問題的研究與改進[D].沈陽:東北大學,2008.6.