基于逆轉算子的遺傳算法在螺母緊固路徑中的優(yōu)化

陳震，彭先濤

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

0 前言

裝配生產(chǎn)線上緊固螺母路徑優(yōu)化問題是在一條裝配線上用一個機械手去緊固待裝配部件上的螺母問題。機械手由其初始位置開始，依次移動到其余的每一個螺母，最后返回到起點。機械手的運行軌跡是以螺母為節(jié)點的一條周游路線。該問題的最優(yōu)解是機械手對該配件上的所有螺母進行緊固后回到始點的工作時間最小，即尋找機械手在螺母間的最短運行路徑，此時，該問題可以轉換為TSP 問題。由此可見，該問題也是典型的多項式復雜程度的非確定性問題(Non－deterministic Polynomial problem)，即最壞情況下的尋優(yōu)時間隨著問題規(guī)模的增大按指數(shù)方式增長，該問題的答案是無法直接計算得到的，只能通過間接的“猜算”來得到結果，到目前為止還沒有找到一個多項式時間的有效算法［1］。

遺傳算法(genetic algorithm，GA)［2］的特點是先對問題參數(shù)進行編碼，編成GA 可以處理的染色體，再對該染色體進行優(yōu)化?；诖丝芍?，GA 優(yōu)化不是問題參數(shù)自身，故函數(shù)約束條件的限制可以不考慮;優(yōu)化過程開始于問題解的某個集合(不是一個個體)，其具有的隱含并行搜索特性可減少算法陷入局部極小值的概率，隱含并行性和全局解控制鍵搜索是其兩個最明顯的特點;GA 的最大缺點是對結構復雜的組合優(yōu)化問題進行優(yōu)化時，需要進行搜索的空間大，進行優(yōu)化搜索的時間長，出現(xiàn)早熟收斂和收斂性能差的可能性很大;初始種群的選擇對算法影響很大［3］。針對GA 算法容易陷入局部極小值的缺點，本文提出了一種改進的GA(IGA):在選擇、交叉、變異之后引入連續(xù)多次的進化逆轉操作(這里的進化是指逆轉算子的單方向性，即只有經(jīng)過逆轉后，適應度有提高的染色體才接受下來，否則逆轉無效)［1］。仿真結果表明，該方法可以較快的找到機械手的最優(yōu)運行路徑，且運行穩(wěn)定。

1 基于進化逆轉算子改進的遺傳算法

GA 算法的基本過程:以隨機產(chǎn)生的待解決問題的一種排列為一條染色體，初始種群由隨機構造的若干條染色體構成，計算每個個體的適應度值，根據(jù)適應度值的高低進行選擇(遺傳操作中的優(yōu)勝劣汰機制)，兩個雙親產(chǎn)生一個子代為一次繁殖;根據(jù)交叉算子進行交叉操作、變異算子進行變異操作，交叉算子和變異算子都是選擇得到的，交叉概率(pc)一般的選取范圍為［0.40，0.99］，變異概率(pm)的選取范圍一般為［0.0001，0.1］。以設定的迭代次數(shù)或某個條件作為算法終止的條件。

本文中采用IGA 對螺母緊固路徑優(yōu)化，進行優(yōu)化的步驟如下［1］:

1)螺母緊固路徑優(yōu)化參數(shù)集進行編碼

編碼方式采用整數(shù)編碼(采用一個基因一個參數(shù)來編碼，將原問題的解空間映射到整數(shù)串空間上，然后在整數(shù)串空間上進行遺傳操作，結果再通過解碼過程還原成其表現(xiàn)型以進行適應度評估)，以提高解的精度和運算速度［4］。如對8 個螺母的優(yōu)化問題{1，2，3，4，5，6，7，8}，則|1|2|8|7|5|3|6|4 就是一個合法的染色體。

2)種群初始化

初始種群是起始解，本文產(chǎn)生的初始種群為100。

3)計算適應度函數(shù)

設k1|k2|…|ki|…|kn |為一個采用整數(shù)編碼的染色體，Dkikj為螺母ki到螺母kj的距離，則該個體的適應度函數(shù)fitness 為:

其中，n 是螺母個數(shù)。

即適應度函數(shù)為機械手恰好走遍n 個螺母，在回到開始時待固定的螺母上方的距離的倒數(shù)。優(yōu)化目標就是選擇適應度函數(shù)值盡可能大的染色體，適應度函數(shù)值越大的染色體品質越好，反之越次。

4)選擇操作

從舊群體中以移動概率選擇個體到新群體中，根據(jù)3)計算出來的適應度進行選擇，個體適應度值越大，被選中的概率越大。

5)交叉操作

交叉概率pc=0.9。采用部分映射交叉，確定交叉操作的父代，將父代樣本兩兩分組，每組重復以下過程(假定有8 個螺母):

a)產(chǎn)生兩個［1，8］區(qū)間內的隨機整數(shù)r1和r2，確定兩個位置，對兩位置的中間數(shù)據(jù)進行交叉，如:r1=2，r2=5，

7 6 | 5 2 4 1 | 8 3 交叉為7 6 | 2 5 1 3 | 8 *

8 6 | 2 5 1 3 | 4 7 8 6 | 5 2 4 1 | * 7

b)交叉后，同一個個體中有重復的螺母編號，不重復的數(shù)字保留，有重復的數(shù)字(帶* 位置)采用部分映射的方法消除沖突，即利用中間段的隨影關系進行映射。結果為:

7 6 | 2 5 1 3 | 8 4 8 6 | 5 2 4 1 | 3 7 。

6)變異操作

變異概率pm=0.05。變異策略采取隨機選擇兩個點，將其兌換位置。產(chǎn)生兩個［1，8］范圍內的隨機整數(shù)r1和r2，確定兩個位置，將其兌換位置，如:r1=2，r2=5，7 |6| 5 2 4 |1| 8 3 變異后為7 |1| 5 2 4 |6| 8 3。

7)進化逆轉操作［5－6］

在標準遺傳算法中，交叉算子的地位和作用很大，通過交叉操作可以使GA 算法的搜索能力得到很大的提高。對順序交叉算子進行考察研究時發(fā)現(xiàn)，即使兩個父代一樣，通過交叉以后任然會有不同于父代的子代產(chǎn)生，并且子代的碼串排列順序與父代的排列有很大的差異，交叉算子的這種變異效果可以起到兩方面的作用:a)在一定程度上可以維持種群的多樣性，使算法避免陷入局部最優(yōu)解;b)子代不能夠很好的繼承父代較多的信息，尤其是當進化過程進行到后期的時候，種群空間中有很多的高適應度值的個體，這種操作會在很大程度上破壞父代的較優(yōu)基因組合，父代的優(yōu)良基因組難以被子代繼承，從而導致算法的搜索能力降低。

由于這種交叉算子使子代難以繼承父代優(yōu)良基因組的缺點，本文采用一種進化逆轉算子(利用遺傳學中的“倒位”:在染色體中存在著兩點，在這兩點之間的基因位置是倒轉的，從而使得那些在父代中離得很遠的基因位在后代中緊靠在一起。基于此現(xiàn)象，Holland 提出一種“逆轉算子”，并在煙花算法中得到很好的應用，使得染色體位串上的重要基因更加緊湊，交叉算子很難將其分裂)——使子代可以繼承父代較多的信息，將進化逆轉操作用于GA 算法的選擇、交叉、變異之后，進而提高算法的局部搜索能力。逆轉算子首先在染色體的個體串上隨機選擇兩點，位串被這2 點分為3 段，然后將第2 段(中間段)的左右順序倒轉過來并與第1 段和第3 段連接起來，從而形成新的染色體個體位串。以(7 6 5* 2 4 1 8 * 3)為例介紹，其中* 為隨機選擇的倒位點，經(jīng)過逆轉算子作用后形成的新位串為(7 6 5 8 1 4 2 3)。

這里的“進化”是指逆轉算子的單方向性，即只有經(jīng)逆轉后，適應度有提高的才接受下來(本文中適應度提高10%的才被接受下來)。和交叉算子對比可知，逆轉算子可以使父代的基因信息被子代繼承的更多，且文中的逆轉操作是單方向的——只接受朝著好的方向的逆轉，故它搜索最優(yōu)解的能力比順序交叉算子更強。

產(chǎn)生連個［1，8］區(qū)間累的隨機整數(shù)r1和r2，確定兩個位置，將其對換位置，如:r1=2，r2=5，7 |6 2 5| 1 3 8 4 進化逆轉后為7 |5 2 6 |1 3 8 4。

對每個個體進行交叉變異，然后代入適應度函數(shù)進行評估，擇出適應值大的個體進行下一代的交叉和變異以及進化逆轉操作。循環(huán)操作:判斷是否滿足設定的終止條件(最大進化代數(shù)200)，滿足則返回第3 步;則結束遺傳操作，輸出最優(yōu)解。

2 仿真研究

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

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

改進的遺傳算法的流程圖如圖2 所示。

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

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

利用本文提出的改進遺傳算法對螺母緊固路徑優(yōu)化問題進行Matlab 仿真研究得到仿真結果如圖3、圖4所示。

圖3 IGA 算法尋找的機械手最優(yōu)運行路徑

機械手最優(yōu)運行路徑為:10－1－11－8－6－9－3－7－4－2－5－22－14－17－20－18－16－21－23－15－13－12－19－10

圖4 IGA 算法的迭代過程

最短路徑為:297.562 2(cm)

機械手運行的最短時間為:151.512 4(s)

基本GA 算法解決螺母緊固路徑優(yōu)化問題的流程圖如圖5。

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

采用的基本參數(shù)與仿真數(shù)據(jù)同IGA 中的一樣，仿真結果如圖6 和圖7 所示。

圖6 基本GA 算法尋找的機械手最優(yōu)運行路徑

圖7 基本GA 算法的迭代過程

機械手最優(yōu)運行路徑為:

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

最短路徑為:335.616(cm)

機械手運行的最短時間為:175.904(s)

3 仿真結果比較和分析

由以上結果可知，IGA 算法尋找的機械手最優(yōu)運行路徑為297.562 2 cm，完成一塊配件的裝配時間為151.512 4 s;基本GA 算法尋找的機械手最優(yōu)運行路徑為335.616 cm，完成一塊配件的裝配時間為175.904 s?？芍?，IGA 的尋優(yōu)精度較高，且IGA 能夠很好的跳出局部極小值，快速、穩(wěn)定的尋找到螺母緊固路徑優(yōu)化問題最優(yōu)解，而基本GA 算法容易陷入局部極小值，尋優(yōu)效果并不是很理想，IGA 算法的尋優(yōu)結果、尋優(yōu)能力遠遠高于基本GA算法的性能。由此驗證了該改進算法的有效性。

4 結語

本文采用引入進化逆轉算子的GA 對機械手緊固螺母的運行路徑優(yōu)化進行了深入研究。仿真結果表明，GA能在較短的時間內尋找到最小目標，使該問題得到很好的解決，但是IGA 能夠很好的跳出局部極小值，并且采用IGA 尋優(yōu)的結果較為穩(wěn)定，在尋優(yōu)能力上IGA 優(yōu)于GA。

IGA 通過在某汽車配件廠流水線上的使用，有效地求解出機械手的最短路徑，縮短機械手工位的作業(yè)時間，大大提高流水線的生產(chǎn)效率，從而節(jié)約成本，提高企業(yè)競爭力，使生產(chǎn)效益最大化。

［1］史峰，王輝，郁磊，等.MATLAB 智能算法30 個案例分析［M］.北京:北京航空航天大學出版社，2011，7.

［2］王小平，曹立明.遺傳算法－理論、應用與軟件實現(xiàn)［M］.西安:西安交通大學出版社，2002，1.

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

［4］廖美英，郭荷清，張勇軍.一種整數(shù)編碼的改進遺傳算法［J］.計算機工程與應用，2003，01:103-105，120.

［5］蘇勁松，周昌樂，蔣旻雋.一種基于逆轉算子的求解TSP 問題的改進演化算法［J］.計算機技術與發(fā)展，2007，07:94-97.

［6］陳湘州，黎志明，劉祖潤.一種改進的整數(shù)編碼遺傳算法在車輛路徑優(yōu)化問題中的應用［J］.南方冶金學院學報，2004，01:36-41.