虛擬裝配中拆卸序列規(guī)劃算法的研究與實現(xiàn)

米小珍 甄曉陽 周韶澤

大連交通大學,大連,116028

虛擬裝配中拆卸序列規(guī)劃算法的研究與實現(xiàn)

米小珍 甄曉陽 周韶澤

大連交通大學,大連,116028

為了解決裝配體拆卸序列的生成與優(yōu)化問題,利用零件的拆卸約束關系,建立了矩陣表達的包括幾何約束、拆卸工具約束以及穩(wěn)定性約束的多目標數(shù)學模型。利用干涉矩陣確定可行的拆卸方向,利用支撐矩陣分析拆卸過程的穩(wěn)定性,利用拆卸工具列表分析拆卸過程中所用的拆卸工具。在運用蟻群算法尋求最優(yōu)的拆卸序列過程中,加入方向變化因子、工具變化因子和穩(wěn)定性因子,對拆卸轉(zhuǎn)移概率公式進行了改進,通過更新局部和全局信息素,指導算法快速尋找最優(yōu)解,最后以動車組轉(zhuǎn)向架輪對作為實例驗證了算法的可行性。

拆卸序列規(guī)劃;干涉矩陣;支撐矩陣;蟻群算法

0 引言

裝配/拆卸序列規(guī)劃作為虛擬裝配技術(VA)的重要組成部分,可在產(chǎn)品設計階段實現(xiàn)裝配體的預裝配/拆卸,進而驗證裝配/拆卸工藝的正確性,為產(chǎn)品設計開發(fā)人員提供研究平臺和手段。裝配/拆卸序列規(guī)劃實際上是一個組合優(yōu)化問題,傳統(tǒng)的優(yōu)先約束關系法和圖論中的割集理論都存在組合爆炸的弊端,對解決復雜裝配體的序列規(guī)劃效果欠佳。近年來許多學者開始采用基于智能計算的軟計算方法來解決裝配/拆卸序列規(guī)劃問題,并取得了一定成果。目前,大多數(shù)學者采用的是遺傳算法和蟻群算法(ant colony algorithm,ACO),遺傳算法是一種基于自然選擇和自然遺傳學機制的搜索算法,能解決調(diào)度、過程規(guī)劃、車間布局等組合優(yōu)化問題,但也存在著收斂速度慢和所選參數(shù)影響大的缺點。文獻[1-2]將遺傳算法和蟻群算法進行了比較,實際應用表明蟻群算法在解決裝配/拆卸序列規(guī)劃問題上要優(yōu)于遺傳算法。

蟻群算法的基本思想是模仿螞蟻依賴信息素(pherom one)進行通信而顯示出它的群體本性,每只螞蟻根據(jù)路徑上的信息素強度進行選擇,最終體現(xiàn)為整個蟻群尋找到最優(yōu)路徑。文獻[3]首先將蟻群算法應用于裝配/拆卸序列規(guī)劃研究,但其算法沒有涉及裝配/拆卸序列的可行性。文獻[4]從拆卸幾何性出發(fā),給出了解決裝配/拆卸問題的蟻群算法,但假設裝配體處于“失重”的情況下,沒有考慮到裝配體的拆卸穩(wěn)定性。文獻[5]將蟻群算法應用于產(chǎn)品拆卸序列規(guī)劃,考慮了拆卸改變次數(shù)和拆卸零件總數(shù)原則。文獻[6]將產(chǎn)品的拆卸序列規(guī)劃問題描述為對該加權有向圖中具備最優(yōu)值的路徑搜索和尋優(yōu)問題,提出了一種蟻群優(yōu)化算法。本文運用裝配體的拆卸干涉矩陣來判斷可行的拆卸方向,用支撐矩陣判斷拆卸零件對裝配體穩(wěn)定性的影響,并加大穩(wěn)定性在拆卸過程中的主導作用,對拆卸序列的生成及優(yōu)化進行深入研究,使最終序列更加貼近工程實際。

本文按照“可拆即可裝”的原則,運用蟻群算法研究裝配體的完全拆卸序列規(guī)劃,綜合考慮了可行性、穩(wěn)定性和裝配或拆卸中所使用的工具等信息。

1 拆卸數(shù)學模型的建立

裝配體拆卸模型提供了裝配體和零部件的相關信息,是進行拆卸序列規(guī)劃的基礎。為了保證算法的有效性和實用性,要求所建立的拆卸模型既準確又不過于復雜。常用的拆卸信息表達模型可分為圖模型和矩陣模型[1],圖模型相對矩陣模型更加直觀,圖中的節(jié)點對應零件,邊表示零件間的拆卸關系,但是圖模型不易于計算機的表達和實現(xiàn);矩陣模型可利用拆卸干涉矩陣描述零部件沿坐標軸拆卸時與其他零件的干涉情況,利用支撐矩陣描述某零件對其他零件的重力支撐情況,因而不僅可以較為完善地體現(xiàn)實際裝配/拆卸工藝需求,而且易于算法的實現(xiàn)。本文采用矩陣方式對裝配體進行建模,為蟻群算法進行拆卸序列規(guī)劃提供必要信息。

1.1 拆卸可行性分析

一個幾何可行的拆卸序列是指當沿著坐標軸拆卸零件時與其他未拆卸零件不發(fā)生干涉。裝配體有n個零件的情況下,集成拆卸矩陣I D是一個n行、3n列的矩陣[7],它能完整描述拆卸過程中的干涉情況,其表達式如下:

集成矩陣I D中元素Iijx表示零件Pi不發(fā)生移動時,Pj沿+x方向拆卸時與零件Pi的干涉情況,如果Pj沿+x方向拆卸時與零件Pi發(fā)生干涉,那么定義Iijx=1;反之,則Iijx=0。零件Pj沿-x方向拆卸時與零件P i的干涉情況與Pi沿+x方向拆卸與零件Pj的干涉情況相同,由元素 Ijix表示。同樣,可以確定集成干涉矩陣中其他元素的值。

零件Pj的可行拆卸方向是由未拆卸的m個零件決定的,當前待拆卸零件Pj的可行拆卸方向可用下式表示:

式(2)表示零件Pj沿d方向與未拆卸零件的干涉情況,假如Pj與所有未拆卸零件都沒有干涉,即ψd=0,那么Pj沿著d方向是可以拆卸的,d方向為可拆卸方向,反之,不可拆卸。

1.2 拆卸穩(wěn)定性分析

拆卸穩(wěn)定性很大程度上決定了拆卸序列中零件的優(yōu)先次序,傳統(tǒng)的根據(jù)力和力矩平衡關系對裝配體穩(wěn)定性進行分析的方法,由于涉及大量數(shù)學計算,故效率較低。本文通過建立拆卸支撐矩陣[8]分析拆卸過程中裝配體的穩(wěn)定性,方法簡單且實用性強,拆卸支撐矩陣S為

矩陣元素Sij表示零件Pi對零件P j的重力支撐關系,假如零件Pi對零件Pj有穩(wěn)定支撐則定義Sij=1,零件Pi必須后于零件P j拆卸,反之,Sij=0,顯然零件之間不接觸時Sij=0。當前拆卸零件Pi對裝配體的穩(wěn)定性也是由未拆卸的m個零件決定的,可用下式進行分析:

當拆卸零件Pi時,需要判斷零件Pi對所有未拆卸零件是否具有支撐作用,假如對其中任意的一個零件具有支撐作用,即Z＞0時,不建議拆卸零件Pi;假如零件Pi對所有未拆卸零件都不具有支撐作用,即Z=0時,建議拆卸零件Pi。

2 基于蟻群算法的拆卸序列規(guī)劃

實際拆卸序列的具體要求為:①拆卸可行且穩(wěn)定;②拆卸方向變化最少;③使用工具變化最少;④拆卸難度小。本文以拆卸重定向次數(shù)和拆卸聚合性為標準,設置拆卸序列目標函數(shù):

式中,Dn為拆卸方向改變次數(shù)(重定向性);Tn為拆卸工具更換次數(shù)(聚合性);w1、w2為二者的權重比系數(shù)。

運用蟻群算法進行拆卸序列規(guī)劃時,可在拆卸轉(zhuǎn)移概率中加入方向改變因子dij(t)、工具變化因子tij(t)和穩(wěn)定性因子sij(t),引導螞蟻向目標函數(shù)靠近。

2.1 拆卸轉(zhuǎn)移概率的定義

采用P表示零件號、D表示該零件的可拆卸方向、T表示拆卸該零件所需要的工具,則可定義拆卸操作為(P,D,T)。對于每個螞蟻個體下一步所選擇的拆卸操作由拆卸轉(zhuǎn)移概率確定,i操作與j操作間的拆卸轉(zhuǎn)移概率由信息素因子和期望啟發(fā)函數(shù)因子決定,定義如下:

式中,τij(t)為信息素因子,表示 t時刻拆卸操作i與拆卸操作j之間的信息素殘余量;dij(t)為期望啟發(fā)函數(shù)因子,表示t時刻從拆卸操作i到拆卸操作j的拆卸方向變化因子,如果方向發(fā)生改變,取(0,1]之間較小的數(shù),反之,取該區(qū)間內(nèi)較大的數(shù);tij(t)為期望啟發(fā)函數(shù)因子,表示t時刻從拆卸操作i到拆卸操作j的拆卸工具變化因子,如果工具發(fā)生改變,取(0,1]之間較小的數(shù),反之,取該區(qū)間內(nèi)較大的數(shù);sij(t)為期望啟發(fā)函數(shù)因子,表示t時刻待拆卸零件j對其余未拆卸零件的穩(wěn)定性影響,如果能夠穩(wěn)定拆卸,取(0,10]之間較大的數(shù),反之,取該區(qū)間內(nèi)較小的數(shù);α、β、μ、γ分別為τij(t)、dij(t)、tij(t)、sij(t)的權值,表示各個因子對轉(zhuǎn)移概率的影響強弱,β、μ、γ反映了啟發(fā)信息在螞蟻選擇路徑中的受重視程度,其值越大,則該轉(zhuǎn)移概率越接近貪心規(guī)則[9]。

兩個不同的拆卸操作之間的信息素殘留越大,啟發(fā)函數(shù)的值越大,則拆卸轉(zhuǎn)移概率也就越大,螞蟻就更傾向于選擇此路徑。

2.2 信息素矩陣的更新

信息素矩陣的行和列代表拆卸操作,當裝配體包含n個零件時,該矩陣為6n×6n。為了避免路徑上殘余信息素過多而淹沒啟發(fā)信息,使搜索陷入局部最優(yōu)解,在每只螞蟻走完一步,即完成一次拆卸操作、或者將裝配體完成拆卸后,要對殘留信息素進行更新處理,本文采用局部更新和全局更新兩種方式。

(1)局部信息素更新。更新方式如下:

式中,τ0為初始信息素濃度;φ為局部信息素揮發(fā)系數(shù),φ∈(0,1),隨著φ值增大,算法收斂性速度變慢。

完成從拆卸操作i到拆卸操作j后,更新此路徑上的信息素,能夠有效避免優(yōu)勢路徑上信息素過分積累,使整個蟻群對未選中的路徑有較強的探索能力。

(2)全局信息素更新。更新方式如下:

式中,ρ為全局信息素揮發(fā)系數(shù),ρ∈(0,1);M為螞蟻總數(shù);Q為常數(shù),用來調(diào)整信息素的增長量;Sk為解的質(zhì)量,表示此條路徑的好壞。

當螞蟻完成一次周游后根據(jù)解的質(zhì)量對此路徑上的信息素進行更新。

2.3 算法步驟

拆卸序列規(guī)劃流程如圖1所示。

圖1 基于蟻群算法的拆卸序列規(guī)劃流程圖

3 拆卸實例分析

圖2為CRH 3動車組轉(zhuǎn)向架輪對爆炸圖,為簡化計算,拆卸序列規(guī)劃中把螺栓組作為單個零件來處理。輪對裝配體零件數(shù)為21,各個零件所用拆卸工具如表1所示。

應用上述蟻群算法,參數(shù)選擇如下:初始信息素濃度τ0=1,信息素權值α=0,方向變化因子權值β=2,工具變化因子權值γ=2,穩(wěn)定性因子權值μ=3,信息素總量Q=10,螞蟻個數(shù)M=6,循環(huán)次數(shù)Nc,max=200,選擇零件11為基準件,算法在循環(huán)到第70次時獲得如下近優(yōu)/最優(yōu)解:(7,-z,T6)→(6,-z,T6)→(17,-z,T6)→(16,+x,T6)→(15,+x,T3)→(14,+x,T4)→(21,+x,T1)→(19,+x,T2)→(20,+x,T2)→(18,+x,T2)→(13,+x,T3)→(5,-x,T3)→(8,-x,T4)→(1,-x,T1)→(2,-x,T2)→(4,-x,T2)→(3,-x,T2)→(9,-x,T3)→(10,-x,T4)→(12,-x,T4)→(11,-x,T5),最終序列的拆卸方向變化次數(shù)為2,拆卸工具變化次數(shù)為11,目標函數(shù)值 f=5.6,算法耗時1.078s。圖3體現(xiàn)了循環(huán)次數(shù)與當前最優(yōu)解之間的函數(shù)關系。

圖2 CRH 3動車組轉(zhuǎn)向架輪對爆炸圖

表1 各零件所用的拆卸工具

圖3 循環(huán)次數(shù)與當前最優(yōu)值關系

在搜索近優(yōu)/最優(yōu)解過程中,信息素在不斷地發(fā)生變化,每一步尋優(yōu)的過程就是在可行的拆卸操作中尋找信息素較大的兩個拆卸操作。優(yōu)化前,不同拆卸操作之間信息素量初始值τ0=1,螞蟻選擇各拆卸操作的幾率相同。優(yōu)化后,較優(yōu)的拆卸操作之間信息素量增大(為使螞蟻有探索新路徑的能力,信息素量不大于7),較差的拆卸操作之間信息素量減少(選擇最少的路徑上信息素量接近0),從而引導螞蟻在概率選擇過程中尋找優(yōu)化的拆卸路徑。

4 結(jié)語

本文建立拆卸干涉矩陣和支撐矩陣來表達幾何約束關系和穩(wěn)定性約束關系,由此分析幾何可行性和拆卸穩(wěn)定性,通過改進的拆卸轉(zhuǎn)移概率公式以及更新局部和全局信息素,在運用蟻群算法尋求最優(yōu)的拆卸序列過程中指導算法快速尋找最優(yōu)解。最后將算法成功應用于動車組轉(zhuǎn)向架的虛擬裝配/拆卸序列規(guī)劃,實際應用表明該方法的效果良好。但是在零件數(shù)目較大的情況下,算法易出現(xiàn)陷入局部最優(yōu)解,為了解決這個問題,將蟻群算法與其他智能算法的融合是一個可行的研究方向。另外,評價函數(shù)的準確建立、參數(shù)的搭配優(yōu)化、子裝配體的識別以及拆卸信息的自動獲取方面還有很多的工作要做,這是下一步對該方法進行改進的重點。

[1] 寧黎華.面向裝配序列規(guī)劃的軟計算方法研究[D].桂林:桂林電子科技大學,2006.

[2] 章小紅.基于蟻群算法的產(chǎn)品拆卸序列規(guī)劃方法研究[D].武漢:華中科技大學,2007.

[3] Failli F,DiniG.Ant Co lony Systems in Assemb ly Planning:a New A pp roach to Sequence Detec tion and Op tim ization[C]//Proceeding of the 2nd CIRP International Sem inar in Intelligent Computation in Manufac turing Engineering.Cap ri,2000:227-232.

[4] W ang JF,Liu JH,Zhong Y F.A Novel Ant Colony Algorithm for Assembly Sequence Planning[C]//Advanced Manufacturing Technology.London,2004:1137-1143.

[5] 王峻峰,李世琪,劉繼紅.面向綠色制造的產(chǎn)品選擇拆卸技術研究[J].計算機集成制造系統(tǒng),2007,13(6):1907-1102.

[6] 王輝,向東,段廣洪.基于蟻群算法的產(chǎn)品拆卸序列規(guī)劃研究[J].計算機集成制造系統(tǒng),2006,12(9):1431-1437.

[7] 方建新.基于蟻群算法的裝配序列規(guī)劃研究[D].武漢:華中科技大學,2007.

[8] 管強,張申生,劉繼紅.裝配過程穩(wěn)定性分析[J].上海交通大學學報,2004,38(4):501-505.

[9] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005.

Research and Implementation of Disassembly Sequence Planning Algorithm in Virtual Assembly

Mi Xiaozhen Zhen Xiaoyang Zhou Shaoze
Dalian Jiaotong University,Dalian,116028

In order to solve the com binatorial optim ization problem of disassembly sequence planning,an ant colony algorithm-based approach was presented.A multi-objectivem athematicalmodelwasestablished w hich w asexpressed bymatrixes and contained geometric constraints,stability constraints and disassembly tool constraints.Interference matrix was used to analyze the feasible disassemb ly direction,support matrix was used to analyze the stability,and disassembly tool lists were used to analyze the tools used during operations.In order to find the optimal disassembly sequence more quickly,redirection factor,tool change factor and stability factor were added to the state-transition ru le.Local and g lobal pheromone were updated after operations so as to avoid a local op timal solution,to accumu late pheromone according to the quality of solutions and to guide ant co lony in searching the app roximate/optimal solutions quick ly.Finally,the disassem b ly sequence of CRH 3 bogie w heels was used as a case research to show the feasibility of the algorithm.

disassemb ly sequence p lanning;interferencematrix;supportm atrix;ant colony algorithm

TP391.9

1004—132X(2011)13—1576—04

2010—08—30

鐵道部科技研究開發(fā)計劃重點項目(2008J012-C);遼寧省教育廳科學技術研究計劃高等學校創(chuàng)新團隊項目(2008T18)

(編輯 郭 偉)

米小珍,女,1962年生。大連交通大學交通運輸工程學院教授、博士研究生導師。主要研究方向為基于復雜裝備的多學科協(xié)同設計、協(xié)同仿真、優(yōu)化與集成管理、虛擬裝配等。獲國家科技進步二等獎1項、教育部科技進步二等獎 1項、大連市科技進步一等獎1項、中國航天工業(yè)總公司科技進步二等獎1項、實用新型專利1項。發(fā)表論文40篇。甄曉陽,男,1986年生。大連交通大學機械工程學院碩士研究生。周韶澤,男,1977年生。大連交通大學交通運輸工程學院講師。