基于遺傳-蟻群算法的裝配序列規(guī)劃研究

孟冠軍，楊大春

(合肥工業(yè)大學(xué) 機(jī)械工程學(xué)院，合肥 230009)

0 引言

裝配是制造業(yè)很重要的主題，對(duì)于一個(gè)結(jié)構(gòu)復(fù)雜零件眾多的產(chǎn)品，其裝配時(shí)間幾乎占整個(gè)生產(chǎn)時(shí)間的一半，在勞動(dòng)成本方面大約要占30%～50%，如果使用傳統(tǒng)方法會(huì)產(chǎn)生大量可行的裝配序列且效率無法保證[1]。好的裝配序列會(huì)大大提高裝配效率、降低裝配成本和提高企業(yè)競(jìng)爭(zhēng)力，裝配序列規(guī)劃(Assembly sequence planning,ASP)的重要性得到越來越廣泛的重視。

近20年來，智能算法被用于裝配序列規(guī)劃求解領(lǐng)域，Bonneville首次使用遺傳算法后，很多智能算法被發(fā)展起來，比如模擬退火、人工免疫系統(tǒng)、蟻群算法、粒子群算法等。模擬退火算法[2]可以求解一些非線性問題，能以較大的概率求得最優(yōu)解，其缺陷是全局搜索能力差，當(dāng)問題規(guī)模較大時(shí)，只能獲得近似解。粒子群算法[3]源于對(duì)鳥類捕食行為的研究，相對(duì)于遺傳算法[4]，其收斂速度更快，并且具有記憶功能，但是容易陷入局部最優(yōu)。免疫算法[5]在智能算法領(lǐng)域?qū)儆诒容^新的算法，該算法在系統(tǒng)建模等方面存在諸多問題。

本文采用蟻群算法和遺傳算法相結(jié)合的混合算法，利用遺傳算法選擇、交叉、變異操作對(duì)裝配序列進(jìn)行優(yōu)化，以及蟻群算法具有較強(qiáng)的魯棒性和全局搜索能力，二者可以取長補(bǔ)短，不僅克服了遺傳算法的早熟現(xiàn)象，而且可以使蟻群算法可以更快、更好地收斂到全局最優(yōu)解。表明遺傳-蟻群算法比傳統(tǒng)的蟻群算法在尋找最優(yōu)解方面可以獲得更優(yōu)的路徑，效率更高。

1 算法原理

蟻群算法由M Dorigo提出并初次使用，其靈感來源于螞蟻對(duì)食物的搜尋。通過建立合適的信息矩陣，螞蟻會(huì)搜尋到從巢穴通往食物地點(diǎn)的最短路徑。螞蟻在搜尋過程中會(huì)在其走過的路徑上分泌信息素，通常路徑越短信息素越濃，一段時(shí)間后信息素會(huì)衰減一部分，這樣螞蟻?zhàn)罱K會(huì)集中在同一條路徑上，此路徑便是最短路徑[6-7]。

蟻群算法部分以旅行商問題(Traveling Salesman Problem,TSP)為例說明，設(shè)定螞蟻數(shù)量m，信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、城市數(shù)目為n，初始狀態(tài)下不同城市間的信息素濃度相同，螞蟻k根據(jù)不同零件間的信息素濃度來選擇下一個(gè)要訪問的城市，令Pij(t)為第t次迭代螞蟻從城市i轉(zhuǎn)移到城市j的概率。

其中，ηij(t)表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程度；τij(t)表示螞蟻從城市i轉(zhuǎn)移到城市j的信息素濃度；allowk表示螞蟻k所有待訪問的城市集合；α和β這倆值越大，表示螞蟻在轉(zhuǎn)移過程中起到的作用越大。當(dāng)所有螞蟻完成一次循環(huán)后，各個(gè)城市間的連接路徑上的信息素濃度需要進(jìn)行一次更新，即：

本文針對(duì)蟻群算法作如下幾個(gè)方面的更新：

(1)局部信息素更新。螞蟻從城市i轉(zhuǎn)移到城市j后，通過揮發(fā)掉一部分信息素，螞蟻對(duì)已經(jīng)訪問過的城市就會(huì)缺乏吸引力，轉(zhuǎn)而去搜尋未訪問的城市，這樣可以促使解的多樣性，更新規(guī)則為：

τij=(1-ζ)τij

(2)全局信息素更新。該更新的目的是增加最優(yōu)解節(jié)點(diǎn)信息素，使得螞蟻更快得集中于最優(yōu)解，即：

τij=(1-ρ)τij+ρΔτij

其中，Δτij=Q*1/min_Length，是螞蟻k從節(jié)點(diǎn)i移動(dòng)到節(jié)點(diǎn)j的信息素增量。

遺傳算法部分本文主要采用交叉和變異操作對(duì)裝配序列進(jìn)行優(yōu)化。本文采用的是部分映射交叉，產(chǎn)生兩個(gè)[1,n]范圍內(nèi)隨機(jī)整數(shù)以確定交叉位置，對(duì)這兩交叉位置之間的數(shù)據(jù)進(jìn)行交換。交換后，同一個(gè)個(gè)體中有重復(fù)的編號(hào)和有沖突的數(shù)字采用部分映射的方法消除沖突。變異操作的策略是采取隨機(jī)選取兩個(gè)點(diǎn)，將其對(duì)換位置。隨機(jī)產(chǎn)生兩個(gè)[1,n]范圍內(nèi)的整數(shù)，交換這兩位置。

2 裝配信息模型

2.1 干涉矩陣

假設(shè)零件只能沿著{+X,+Y,+Z,-X,-Y,-Z}6個(gè)方向進(jìn)行裝配，一次性裝配只能是一個(gè)方向和一個(gè)工具。例如，Pi,j=101表示零件j沿著+X和+Z方向與零件i發(fā)生干涉，但是如果沿著+Y方向則不發(fā)生干涉，可以正常裝配。Pj,i表示零件i與零件j的干涉情況，同時(shí)也表示零件j沿著-X,-Y,-Z與零件i的干涉情況[8-9]。如果Pi,j=111011，表示零件j可以沿著-X方向在零件i后安裝，Pi,j=111111，表示零件j無法在零件i后安裝。

本文建立的干涉矩陣形式如下：

為求解簡(jiǎn)便，本文將干涉矩陣分拆為三個(gè)矩陣，分別表示X、Y、Z三個(gè)方向。

2.2 啟發(fā)信息

啟發(fā)信息所表達(dá)的是可以讓螞蟻對(duì)于接下來需要去的節(jié)點(diǎn)作一個(gè)大概的判斷。通常情況下對(duì)于一個(gè)給定的裝配序列，螞蟻對(duì)節(jié)點(diǎn)的一次搜尋會(huì)被已經(jīng)完成的序列深深的影響到。

mj表示零件j的質(zhì)量；lj表示零件j的體積；dij表示零件j在零件i后安裝其安裝方向是否發(fā)生變化，如果變化則是1，否則是0；nij表示零件裝配在不同方向的值，如果沿著重力方向nij為0.0001，如果與重力方向相反，則是1，如果與重力方向垂直，nij為0.5；tij表示零件j在零件i后安裝其安裝工具發(fā)生變化情況，如果發(fā)生變化，tij為1，不變則是0；gij表示零件的安裝難易程度，如果可以正常安裝，gij為1，如果有點(diǎn)難度gij為0.05，如果特別難以安裝gij為0.0001[10]。

2.3 判斷裝配序列

有些零件雖然不發(fā)生干涉，但是在裝配時(shí)卻存在優(yōu)先約束關(guān)系，如果反過來裝配的話，其本身不符合邏輯且在實(shí)際中根本無法裝配。針對(duì)這種情況，可以設(shè)置一個(gè)優(yōu)先約束矩陣PR，如果兩零件不符合邏輯的話，則令PRij=1，否則PRij=0。例如剛剛裝配好的零件Ik，如果發(fā)現(xiàn)PRij=1，那么就調(diào)換兩零件的順序這樣就符合邏輯且可以正常裝配。

2.4 適應(yīng)度函數(shù)

為了評(píng)價(jià)生成好的裝配序列，需要通過幾個(gè)參數(shù)來確定此裝配序列的優(yōu)劣，為了盡可能地提高裝配效率，本文通過以下幾個(gè)參數(shù)來評(píng)價(jià)裝配序列：

(1)裝配序列的穩(wěn)定性。為了提高裝配的穩(wěn)定性和可靠性，我們需要建立接觸矩陣確保裝配過程的正常進(jìn)行[11]。設(shè)穩(wěn)定性參數(shù)為S1，如果兩零件直接接觸且保持穩(wěn)定連接關(guān)系則S1=0.1，兩零件僅僅直接接觸則S1=0.4，否則S1=1。

(2)裝配序列的連續(xù)性。連續(xù)性表示零件間具有一定的接觸連接關(guān)系，產(chǎn)品是否可以實(shí)現(xiàn)連續(xù)安裝。設(shè)連續(xù)性參數(shù)為S2，如果兩零件具有配合關(guān)系則S2=0.1，否則S2= 1。

(3)裝配方向的改變次數(shù)。裝配的方向如果變化的過于頻繁會(huì)大大增加裝配的成本和難度，因此我們需要盡量減少裝配的重定向。設(shè)方向改變參數(shù)為S3，如果兩零件方向不發(fā)生變化則S3=0.1，否則S3=1。

(4)裝配工具的改變次數(shù)。每一個(gè)零件都有一個(gè)裝配工具，如果連續(xù)幾個(gè)零件裝配時(shí)使用的都是不同的裝配工具，同樣會(huì)增加裝配的成本。設(shè)連續(xù)性參數(shù)為S4，如果兩零件裝配工具不發(fā)生變化則S4=0.1，否則S4=1。

根據(jù)以上4個(gè)參數(shù)建立一個(gè)適應(yīng)度函數(shù)：F=w1S1+w2S2+w3S3+w4S4。此適應(yīng)度函數(shù)可以通過其較大的區(qū)分度來評(píng)價(jià)裝配的優(yōu)劣，提高了裝配序列規(guī)劃搜索范圍。

3 遺傳蟻群算法操作步驟

(1)信息初始化。首先要對(duì)算法相關(guān)參數(shù)進(jìn)行初始化，包括螞蟻的數(shù)量m，最大迭代次數(shù)iter_max，信息素重要程度因子α，啟發(fā)信息重要程度因子β，全局信息素?fù)]發(fā)因子ρ，局部信息素?fù)]發(fā)因子ζ，信息素釋放總量Q，各優(yōu)化目標(biāo)的相對(duì)權(quán)重w1～w4,流程圖如圖1所示。

圖1 流程圖

(2)構(gòu)建解空間。計(jì)算啟發(fā)信息，讓螞蟻全部集中于基礎(chǔ)件，對(duì)所以螞蟻按照公式1進(jìn)行選擇下一個(gè)要去的零件，螞蟻每訪問一個(gè)零件進(jìn)行局部信息素更新，這樣可以讓螞蟻有更多的選擇。

(3)可行解判斷。使用干涉矩陣判斷所有的裝配序列，如果某一零件與之前所有零件在所有6個(gè)方向均發(fā)生干涉，可以判斷該序列為不可行序列。遍歷所有可行的裝配序列，若發(fā)現(xiàn)不符合邏輯的兩零件，調(diào)換二者位置。

(4)遺傳操作。針對(duì)所有可行的裝配序列進(jìn)行遺傳操作，包括選擇、交叉、變異，結(jié)束后再重新插入種群。

(5)評(píng)價(jià)裝配序列。使用公式評(píng)價(jià)所有可行的裝配序列，計(jì)算最短距離和平均距離，更新全局信息素以突出最優(yōu)解，這樣算法會(huì)收斂得更快。

(6)結(jié)束。當(dāng)?shù)螖?shù)等于iter_max，則該算法終止運(yùn)行，定義最后一次迭代所獲得的最優(yōu)解為全局最優(yōu)裝配序列。

4 實(shí)例

本文的算法在Matlab平臺(tái)上編寫，將與傳統(tǒng)的蟻群算法想比較，考察遺傳蟻群算法的優(yōu)化性能。如圖2所示為二沖程發(fā)動(dòng)機(jī)，該裝配體共包含19個(gè)零件，零件裝配信息如表1所示。

圖2 二沖程發(fā)動(dòng)機(jī)

表1 二沖程發(fā)動(dòng)機(jī)零件屬性表

該算法所使用的相關(guān)參數(shù)為蟻群數(shù)目m=35，最大迭代次數(shù)iter_max=100，α=6，β=7，ρ=0.2，ζ=0.1，交叉概率PC=0.9，變異PM=0.05，w1=0.3，w2=0.3，w3=0.4，w4=0.3。最終獲得最優(yōu)解為11.09，最優(yōu)路徑為：(1,X)→(2,Z)→(9,Z)→ (10,Z)→(3,-X)→ (8,X)→(6,Z)→(4,Z)→(5,X)→(11,-X)→(17,Z)→(7,Z)→(18,Z) →(12,Z)→(13,-X)→ (14,Z) →(16,Z)→(15,Z)→(19,-Y)，如圖3所示，傳統(tǒng)蟻群算法最優(yōu)解為12.58。當(dāng)然算法的最優(yōu)解不唯一，其他的最優(yōu)路徑在這里就不一一列舉了。

為了驗(yàn)證遺傳蟻群算法的有效性和優(yōu)越性，通過多次試驗(yàn)，將遺傳蟻群算法與蟻群算法作比較。由圖3～圖6可知，蟻群算法搜索速度較慢，需要花費(fèi)較長的代數(shù)才能找到最優(yōu)解，遺傳蟻群算法可以在較短的時(shí)間內(nèi)尋找到最優(yōu)解，且遺傳蟻群算法所搜尋到的最短路徑比傳統(tǒng)蟻群算法更加優(yōu)秀。對(duì)比來看遺傳蟻群算法可以獲得更理想的結(jié)果。

圖3 蟻群算法最短距離 圖4 蟻群算法可行解個(gè)數(shù)

圖5 遺傳蟻群算法最短距離 圖6 遺傳蟻群算法可行解個(gè)數(shù)

5 結(jié)束語

本文對(duì)蟻群算法作了部分改進(jìn)，并且和遺傳算法相結(jié)合，在求解裝配序列規(guī)劃問題上取得很好的效果。干涉矩陣和工具列表矩陣表達(dá)了產(chǎn)品可行裝配方向等信息，在此基礎(chǔ)上，基于遺傳算法和蟻群算法的原理和模型，構(gòu)建了面向裝配序列規(guī)劃的遺傳蟻群算法，并從裝配可行方向的改變次數(shù)和裝配工具的改變次數(shù)等四方面建立目標(biāo)優(yōu)化函數(shù)，求解裝配序列。最后通過實(shí)例研究，證明了遺傳蟻群算法能較好地搜索出裝配最優(yōu)序列。

[參考文獻(xiàn)]

[1] Ghandi S, Masehian E. Assembly sequence planning of rigid and flexible parts[J]. Journal of Manufacturing Systems,2015,36:128-146.

[2] 王孝義,張友良,張帆.基于模擬退火算法的裝配序列生成與優(yōu)化[J].機(jī)械科學(xué)與技術(shù)(西安),2005,24(5):624-627.

[3] 邢彥鋒,趙曉昱.粒子群算法在裝配順序規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)集成制造系統(tǒng),2011(3):80-82.

[4] 蔣超,吳波,李明宇,等.基于遺傳算法的產(chǎn)品裝配序列規(guī)劃研究[J].機(jī)械與電子,2012(4):7-11.

[5] 寧黎華,古天龍.基于免疫算法的裝配序列規(guī)劃問題求解[J].計(jì)算機(jī)集成制造系統(tǒng)，2007,13(1):81-87.

[6] 鄧明星,唐秋華,雷喆.基于蟻群算法的改進(jìn)裝配序列規(guī)劃方法[J].武漢大學(xué)學(xué)報(bào)(工學(xué)版),2013,46(2):246-251.

[7] 謝龍,付宜利,馬玉林.基于蟻群算法的裝配序列生成策略[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2006,38(2):180-184.

[8] 彭濤,李世其,王峻峰,等.基于集成干涉矩陣的蟻群裝配序列規(guī)劃[J].計(jì)算機(jī)科學(xué),2010,37(4):179-182.

[9] 崔小龍, 劉新華, 宋國民.基于子裝配的裝配序列規(guī)劃方法研究[J].組合機(jī)床與自動(dòng)化加工技術(shù),2012(5):78-81,85.

[10] 史士財(cái),李榮,付宜利,等.基于改進(jìn)蟻群算法的裝配序列規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng),2010,16(6):1189-1194.

[11] 于嘉鵬,王成恩,王健熙.基于最大_最小蟻群系統(tǒng)的裝配序列規(guī)劃[J].機(jī)械工程學(xué)報(bào),2012,48(23):152-166.

(編輯李秀敏)