謝偉松　鄧　錚　丁伯慧

1.天津大學(xué)，天津，3000722.天津大學(xué)機(jī)構(gòu)理論與裝備設(shè)計(jì)教育部重點(diǎn)實(shí)驗(yàn)室，天津，300072

用GAAA優(yōu)化多階段裝配過程中的夾具布局

謝偉松1鄧錚1丁伯慧2

1.天津大學(xué)，天津，3000722.天津大學(xué)機(jī)構(gòu)理論與裝備設(shè)計(jì)教育部重點(diǎn)實(shí)驗(yàn)室，天津，300072

改進(jìn)了遺傳算法與蟻群算法的融合(GAAA)算法，利用它來解決多階段裝配過程中二維剛性零件的夾具布局優(yōu)化問題，合理選擇定位銷的位置使得靈敏度指標(biāo)最小化。通過改變遺傳算法的變異算子，變異長度以及交叉、變異在蟻群算法中發(fā)生的位置，提高了GAAA的穩(wěn)定性和收斂性。以汽車側(cè)邊裝配為例驗(yàn)證了改進(jìn)算法的有效性，結(jié)果表明改進(jìn)后的GAAA比基本的GAAA和蟻群算法求得的結(jié)果要好，且收斂速度更快，穩(wěn)定性更好。

多階段裝配過程；狀態(tài)空間模型；夾具布局優(yōu)化；遺傳算法與蟻群算法的融合

0　引言

夾具設(shè)計(jì)在很大程度上影響了裝配過程中的產(chǎn)品尺寸變化，對(duì)于一種新產(chǎn)品的過程設(shè)計(jì)，它是最重要的設(shè)計(jì)任務(wù)之一。在汽車工業(yè)中，裝配過程是一種典型的多階段板類裝配過程，其中，夾具用來定義零件和子配件的位置，并且為其提供物理支撐。夾具設(shè)計(jì)極大地影響了多階段裝配過程中最終產(chǎn)品尺寸的準(zhǔn)確性，從而相對(duì)于外部變化，夾具布局設(shè)計(jì)合理可以減小過程靈敏度。一個(gè)最優(yōu)的夾具布局能夠改善一個(gè)夾具系統(tǒng)的魯棒性，克服環(huán)境噪聲，減少產(chǎn)品變化和降低制造成本。

多階段板類裝配過程中的夾具通常用n-2-1布局，包括兩個(gè)定位銷和n個(gè)凈接觸(net contact，NC)塊，記為{P4way,P2way,NCi,i=1,2,…,n}。對(duì)于二維模型，我們只考慮定位銷引起的變化，所以布局可寫為{P4-way,P2-way}。

在夾具布局優(yōu)化問題中，子配件重新定位引起的變化在各階段間的聯(lián)系，使得夾具分布問題或者主要定位點(diǎn)(PLPs)分布簡化問題在多階段過程中變得更困難。Kim等[1]解決了多階段裝配過程中二維剛性零件的此類問題，將改進(jìn)后的基本交換算法作為優(yōu)化方法來確定PLP的分布。Izquierdo等[2]在產(chǎn)品系列的夾具布局設(shè)計(jì)中延伸了Kim等[1]的工作，提出了一種新方法：在一種產(chǎn)品系列的多階段裝配中，通過定位元件的最優(yōu)分布來獲得夾具布局設(shè)計(jì)的魯棒性。Huang等[3]用序列空間填充方法來解決多階段裝配系統(tǒng)中夾具布局的魯棒設(shè)計(jì)問題，并將序列子空間搜索方法和直接的空間填充以及遺傳算法(GA)進(jìn)行了比較。在單一階段的夾具布局優(yōu)化問題中，文獻(xiàn)[4-6]分別采用ANN(artificialneuralnetworks)和GA解決了魯棒夾具布局設(shè)計(jì)和夾緊力優(yōu)化的問題。文獻(xiàn)[7-8]分別采用基于離散型和連續(xù)型的蟻群算法(ACA)對(duì)夾具布局進(jìn)行優(yōu)化，使得工件的彈性變形最小。通過上述的研究工作可以發(fā)現(xiàn)：GA和ACA在夾具布局優(yōu)化問題中具有廣泛的應(yīng)用性，但是文獻(xiàn)[7-8]采用ACA只是對(duì)單一階段單一工件的夾具布局進(jìn)行優(yōu)化，并且ACA的初期信息素匱乏，求解速度慢。

本文對(duì)基于連續(xù)型方法的ACA與GA的融合算法(geneticalgorithm-antcolonyalgorithm,GAAA)進(jìn)行了改進(jìn)，用GA克服了ACA初期信息素匱乏的問題，采用改進(jìn)的GAAA來解決二維剛性零件在多階段裝配過程中夾具布局優(yōu)化問題，并將改進(jìn)的GAAA與基本的GAAA以及ACA求得的結(jié)果進(jìn)行比較。將E-optimality標(biāo)準(zhǔn)的最小化作為目標(biāo)函數(shù)，合理選擇定位銷或者PLPs的位置使得靈敏度指標(biāo)最小化。

1　變化傳播模型與優(yōu)化方案

1.1變化傳播模型

xk=Ak-1xk-1+Bkuk+wk

(1)

yk=Ckuk+vk

(2)

其中，xk為階段k(k=1,2,…,N)的變化(零件的偏移和旋轉(zhuǎn))，xk∈Rn；uk為夾具偏差,uk∈Rp；wk為其他未建模的偏差，wk∈Rn；矩陣Ak-1表示兩個(gè)相連階段夾具布局的關(guān)系，決定了階段k子配件重新定位的位置；矩陣Bk表示階段k的夾具布局,Bk∈Rn×p；yk表示階段k的測(cè)量或輸出，依賴于測(cè)量點(diǎn)的位置,yk∈Rm；矩陣Ck表示零件變化與測(cè)量點(diǎn)之間的關(guān)系,Ck∈Rm×n；vk為噪聲,vk∈Rm。上述方程中矩陣Ak、Bk、Ck的具體表示參見文獻(xiàn)[1,13]。

由于狀態(tài)空間模型具有線性性質(zhì)，所以得到線性輸入-輸出狀態(tài)空間模型：

(3)

1.2靈敏度指標(biāo)

假設(shè)在裝配過程中變化的主要來源是夾具(例wk≈0,vN≈0,x0≈0)，則夾具引起的產(chǎn)品變化可寫為

在夾具布局設(shè)計(jì)中有三種優(yōu)化標(biāo)準(zhǔn):

D-optimality:min det(DTD)

A-optimality:min tr(DTD)

E-optimality:minλmax(DTD)

三種標(biāo)準(zhǔn)的具體描述可見文獻(xiàn)[1]，本文采用E-optimality標(biāo)準(zhǔn)。Kim等[1]將靈敏度指標(biāo)定義為

在分析9個(gè)注水系統(tǒng)中，果7注水系統(tǒng)存在回流，回流量為5 m3/h，如果通過及時(shí)調(diào)整注水泵的運(yùn)行頻率，使注水量與注水泵排量吻合，避免出現(xiàn)打回流現(xiàn)象。系統(tǒng)的注水單耗為14.33 kWh/m3，此運(yùn)行狀況按照運(yùn)行2個(gè)月計(jì)算，則避免回流可節(jié)約電量為10.32×104kW。

1.3優(yōu)化方案

Kim等[1]用E-optimality標(biāo)準(zhǔn)得到優(yōu)化方案：

minφSmax=λmax(DTD)

s.t.G(φ)>0

約束G(φ)是限制產(chǎn)品的主要定位點(diǎn)(PLPs)位置φ的幾何約束的集合，它們包括定位元件的可行域以及零件之間的關(guān)系。如果產(chǎn)品在XZ平面上定位m個(gè)零件，則向量φ包括2m個(gè)PLPs的位置。PLPs的位置主要是2個(gè)定位銷的位置，產(chǎn)品的PLPs位置表示為φ=(P1,P2,…,P2m)，其中,Pk=(xk,zk),k=1,2,…,2m，所以φ還可寫為φ=((x1,z1),(x2,z2),…,(x2m,z2m))。

2　優(yōu)化算法

2.1改進(jìn)的融合算法

遺傳算法與蟻群算法的融合是由丁建立等[14]提出的。本文中，將文獻(xiàn)[14]中的GAAA稱為基本的GAAA，本文的算法稱為改進(jìn)的GAAA。

隨機(jī)選取10個(gè)夾具布局，將每個(gè)夾具布局的目標(biāo)函數(shù)值按其從小到大的順序排列，第1～6個(gè)夾具布局稱為上解，第7～10個(gè)夾具布局稱為下解。用蟻群算法的全局搜索來改變下解的夾具布局(如文獻(xiàn)[7-8])，用遺傳算法的順序交叉法和逆轉(zhuǎn)變異法(如文獻(xiàn)[14-15])來改變上解的夾具布局，將第1～6個(gè)夾具布局的P4-way(或P2-way)的x或y軸坐標(biāo)值組成一個(gè)父串，并采用十進(jìn)制對(duì)其編碼。例如P4-way的橫坐標(biāo)可以組成一個(gè)父串：

本文針對(duì)GAAA作了如下三點(diǎn)改進(jìn)：

(1)改變遺傳算法中的變異算子?；镜腉AAA是選擇一個(gè)處于相連位置的變異序列，這樣發(fā)生變異的元素會(huì)相對(duì)集中。改進(jìn)措施為，隨機(jī)選取一些不相連的變異位置，將處于這些變異位置的數(shù)碼取出來組成一個(gè)變異序列，將其逆轉(zhuǎn)后再依次放入原來序列的空位置中。

假設(shè)最優(yōu)布局的編碼為1，2，3，4，5，6。

(2)每次選定的變異長度不是一個(gè)定值，而是一個(gè)隨機(jī)變化的變異長度。

(3)遺傳算法的交叉、變異過程嵌在蟻群算法過程中，如圖1所示。步驟(8)、(9)、(10)在步驟(7)和(11)之間進(jìn)行，而不是只在蟻群算法運(yùn)行前進(jìn)行。

圖1　融合算法流程圖

2.2收斂過程

用融合算法對(duì)每個(gè)夾具布局的每個(gè)夾具元件進(jìn)行優(yōu)化，求出每個(gè)夾具布局的最大特征值Smax，存儲(chǔ)所有夾具布局M中最大特征值Smax的最小值Δmin以及相對(duì)應(yīng)的夾具布局(圖1)。對(duì)所有的迭代過程N(yùn)均重復(fù)同樣的過程，求出所有Δmin中的最小值Δwork以及最小值對(duì)應(yīng)的夾具布局。如果迭代次數(shù)達(dá)到設(shè)定的最大迭代次數(shù)N，并且每次迭代后的元件位置均在夾具元件的位置范圍內(nèi)，或者每一次迭代的結(jié)果浮動(dòng)范圍較小，趨于穩(wěn)定，那么算法收斂。

3　實(shí)例分析

下面以車身側(cè)邊裝配過程為例驗(yàn)證算法的有效性。這個(gè)側(cè)邊主要包括車頭(fender side)、車身(A-B ring)和車尾(rear quarter)三個(gè)部分，如圖2a所示。每個(gè)零件的形狀簡化為矩形，這三個(gè)部分記為零件1、零件2和零件3，三個(gè)零件在坐標(biāo)中的大小已在圖2b中標(biāo)出。圖3給出了裝配順序和基準(zhǔn)變換：

{{P1,P2},{P3,P4}}Ⅰ→

{{P1,P4},{P5,P6}}Ⅱ→{{P1,P6}}Ⅲ

(a)車輛側(cè)邊框

(b)零件大小示意圖2　裝配的幾何參數(shù)

(a)階段1

(b)階段2

(c)階段3圖3　裝配過程

用MATLAB軟件求得的結(jié)果如下(所有單位為mm)：

圖4a、圖5a、表1和表2表示在相同參數(shù)和相同的初始夾具布局下，蟻群算法和改進(jìn)的GAAA求得的結(jié)果比較。其中，圖4a所示為二者的迭代過程，表1所示為二者求得的最優(yōu)夾具布局。圖5a將表1中PLPs的坐標(biāo)用CAD軟件標(biāo)注在工件上，“+”表示蟻群算法求得的最優(yōu)夾具布局，“o”表示改進(jìn)的GAAA求得的最優(yōu)夾具布局；表2是二者求得的最小目標(biāo)函數(shù)值。從圖4a可以看出，在相同參數(shù)和相同的初始夾具布局下，改進(jìn)的GAAA比蟻群算法穩(wěn)定性更好，收斂速度更快，蟻群算法在大概迭代50次之后趨于穩(wěn)定，而改進(jìn)的GAAA在大概迭代40 次之后就趨于穩(wěn)定，且從表2可以看出，改進(jìn)的GAAA求得的最小目標(biāo)函數(shù)值2.0071也比蟻群算法求得的結(jié)果2.0240要小。

(a)蟻群算法和改進(jìn)的GAAA的迭代過程

(b)基本的GAAA和改進(jìn)的GAAA的迭代過程圖4　迭代過程

(a)蟻群算法與改進(jìn)的GAAA求得的最優(yōu)夾具布局

(b)基本的與改進(jìn)的GAAA求得的最優(yōu)夾具布局圖5　最優(yōu)夾具布局

圖4b、圖5b、表3和表4表示在相同參數(shù)和相同的初始夾具布局下，基本的GAAA和改進(jìn)的GAAA求得的結(jié)果比較。其中，圖4b所示為二者的迭代過程，表3所示為二者求得的最優(yōu)夾具布局。圖5b將表3中PLPs的位置用CAD軟件標(biāo)注在工件上，“+”表示基本的GAAA求得的最優(yōu)夾具布局，“o”表示改進(jìn)的GAAA求得的最優(yōu)夾具布局；表4是二者求得的最小目標(biāo)函數(shù)值。從圖4b可以看出，在相同參數(shù)和相同的初始夾具布局下，改進(jìn)的GAAA也比基本的GAAA穩(wěn)定性好，收斂速度更快，基本的GAAA在大概迭代50次之后趨于穩(wěn)定，而改進(jìn)的GAAA在大概迭代30多次之后就趨于穩(wěn)定，且從表4可以看出，改進(jìn)的GAAA求得的最小目標(biāo)函數(shù)值2.0126也比蟻群算法求得的結(jié)果2.0253要小。

表1　蟻群算法和改進(jìn)的GAAA求得的最優(yōu)夾具布局　mm

表2　蟻群算法和改進(jìn)的GAAA結(jié)果比較

表3　基本的GAAA和改進(jìn)的GAAA求得的最優(yōu)夾具布局　mm

表4　基本的GAAA和改進(jìn)的GAAA結(jié)果比較

4　結(jié)語

在本文中，分別用改進(jìn)的GAAA、基本的GAAA以及蟻群算法對(duì)多階段裝配過程的夾具布局進(jìn)行了優(yōu)化，以找到滿足最小目標(biāo)函數(shù)值Smax的最優(yōu)夾具布局。通過改變遺傳算法的變異算子、變異長度以及交叉、變異在蟻群算法中發(fā)生的位置，改進(jìn)了GAAA，提高了GAAA的穩(wěn)定性和收斂性。在實(shí)例分析中可以得出結(jié)論：改進(jìn)的GAAA比基本的GAAA和蟻群算法求得的結(jié)果要好，收斂速度更快，穩(wěn)定性更好。盡管文中對(duì)改進(jìn)的GAAA在設(shè)計(jì)二維夾具布局方面給了詳細(xì)描述，但在實(shí)際工程應(yīng)用中，三維零件要比二維的更加實(shí)用。所以我們將進(jìn)一步改進(jìn)GAAA，來解決多階段裝配過程中三維剛性零件的夾具布局優(yōu)化問題。

[1]Kim P, Ding Y. Optimal Design of Fixture Layout in Multistation Assembly Processes[J]. IEEE Transactions on Automation Science and Engineering, 2004, 1(2): 133-145.

[2]Izquierdo L E, Hu S J, Jin R, et al. Robust Fixture Layout Design for a Product Family Assembled in a Multistage Reconfigurable Line[J]. Journal of Manufacturing Science and Engineering, 2009, 131(4): 041008.

[3]Huang W, Kong Z, Chennamaraju A. Robust Design for Fixture Layout in Multistation Assembly Systems Using Sequential Space Filling Methods[J]. Journal of computing and information science in engineering, 2010, 10(4): 041001.

[4]Selvakumar S, Arulshri K P, Padmanaban K P, et al. Design and Optimization of Machining Fixture Layout Using ANN and DOE[J]. The International Journal of Advanced Manufacturing Technology, 2013, 65(9/12): 1573-1586.

[5]Wang B F, Nee A Y C. Robust Fixture Layout with the Multi-objective Non-dominated ACO/GA Approach[J]. CIRP Annals-Manufacturing Technology, 2011, 60(1): 183-186.

[6]陳蔚芳, 倪麗君, 王寧生. 夾具布局和夾緊力的優(yōu)化方法研究[J]. 中國機(jī)械工程, 2007, 18(12): 1413-1417.

Chen Weifang, Ni Lijun, Wang Ningsheng. Investigation on Optimization Method for Fixture Layout and Clamping Forces[J]. China Mechanical Engineering. 2007, 18(12): 1413-1417.[7]Padmanaban K P, Prabhaharan G. Dynamic Analysis on Optimal Placement of Fixturing Elements Using Evolutionary Techniques[J]. International Journal of Production Research, 2008, 46(15): 4177-4214. [8]Padmanaban K P, Arulshri K P, Prabhakaran G. Machining Fixture Layout Design Using Ant Colony Algorithm Based Continuous Optimization Method[J]. The International Journal of Advanced Manufacturing Technology, 2009, 45(9/10): 922-934.

[9]Ding Y, Shi J, Ceglarek D. Diagnosability Analysis of Multi-station Manufacturing Processes[J]. Journal of Dynamic Systems, Measurement, and Control, 2002, 124(1): 1-13.

[10]Wang H, Ceglarek D. Variation Propagation Modeling and Analysis at Preliminary Design Phase of Multi-station Assembly Systems[J]. Assembly Automation, 2009, 29(2): 154-166.

[11]Shi J. Stream of Variation Modeling and Analysis for Multistage Manufacturing Processes[M]. Boca Raton:CRC Press, 2010.

[12]Liu J, Jin J, Shi J. State Space Modeling for 3-D Variation Propagation in Rigid-body Multistage Assembly Processes[J]. IEEE Transactions on Automation Science and Engineering, 2010, 7(2): 274-290.

[13]Abellan-Nebot J V, Liu J, Subirón F R, et al. State Space Modeling of Variation Propagation in Multistation Machining Processes Considering Machining-induced Variations[J]. Journal of Manufacturing Science and Engineering, 2012, 134(2): 021002.

[14]丁建立, 陳增強(qiáng), 袁著祉. 遺傳算法與螞蟻算法的融合[J]. 計(jì)算機(jī)研究與發(fā)展, 2003, 40(9): 1351-1356.

Ding Jianli, Chen Zengqiang, Yuan Zhuzhi. On the Combination of Genetic Algorithm and Ant Algorithm[J]. Journal of Computer Research and Development, 2003, 40(9): 1351-1356.

[15]Ciornei I, Kyriakides E. Hybrid Ant Colony-genetic Algorithm (GAAPI) for Global Continuous Optimization[J]. Systems, Man, and Cybernetics, Part B: IEEE Transactions on Cybernetics, 2012, 42(1): 234-245.

(編輯王艷麗)

Fixture Layout Optimization in Multi-station Assembly Processes Using GAAA

Xie Weisong1Deng Zheng1Ding Bohui2

1.Tianjin University,Tianjin,300072 2.Key Laboratory of Mechanism Theory and Equipment Design of Ministry of Education,Tianjin University,Tianjin,300072

GAAA (genetic algorithm-ant colony algorithm) was augmented to solve fixture layout optimization problems of 2D rigid parts in multi-station assembly processes, and the coordinates of two locating pins were properly selected to minimize the sensitivity index. The stability and convergence of GAAA were improved by changing the mutation operator, mutation length of genetic algorithm and the position where crossover and mutation occured in ant colony algorithm. A case about automotive side aperture assembly processes was studied to verify the effectiveness of the augmented GAAA. The results show that the augmented GAAA can generate more accurate results with a faster rate of convergence and a better stability than the basic GAAA and ant colony algorithm.

multi-station assembly process; state space model; fixture layout optimization; genetic algorithm-ant colony algorithm(GAAA)

2014-01-13

國家自然科學(xué)基金資助項(xiàng)目(51205286, 51275348)

TH122；TH16< class="emphasis_italic">DOI

：10.3969/j.issn.1004-132X.2015.05.016

謝偉松，男，1967年生。天津大學(xué)理學(xué)院副教授。主要研究方向?yàn)槲⒎址匠虜?shù)值解、計(jì)算幾何。鄧錚，女，1990年生。天津大學(xué)理學(xué)院碩士研究生。丁伯慧(通信作者)，女，1976年生。天津大學(xué)機(jī)械工程學(xué)院講師。