用GAAA優化多階段裝配過程中的夾具布局

謝偉松　鄧　錚　丁伯慧

1.天津大學，天津，3000722.天津大學機構理論與裝備設計教育部重點實驗室，天津，300072

用GAAA優化多階段裝配過程中的夾具布局

謝偉松1鄧錚1丁伯慧2

1.天津大學，天津，3000722.天津大學機構理論與裝備設計教育部重點實驗室，天津，300072

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

多階段裝配過程；狀態空間模型；夾具布局優化；遺傳算法與蟻群算法的融合

0　引言

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

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

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

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

1　變化傳播模型與優化方案

1.1變化傳播模型

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

(1)

yk=Ckuk+vk

(2)

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

由于狀態空間模型具有線性性質，所以得到線性輸入-輸出狀態空間模型：

(3)

1.2靈敏度指標

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

在夾具布局設計中有三種優化標準:

D-optimality:min det(DTD)

A-optimality:min tr(DTD)

E-optimality:minλmax(DTD)

三種標準的具體描述可見文獻[1]，本文采用E-optimality標準。Kim等[1]將靈敏度指標定義為

在分析9個注水系統中，果7注水系統存在回流，回流量為5 m3/h，如果通過及時調整注水泵的運行頻率，使注水量與注水泵排量吻合，避免出現打回流現象。系統的注水單耗為14.33 kWh/m3，此運行狀況按照運行2個月計算，則避免回流可節約電量為10.32×104kW。

1.3優化方案

Kim等[1]用E-optimality標準得到優化方案：

minφSmax=λmax(DTD)

s.t.G(φ)>0

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

2　優化算法

2.1改進的融合算法

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

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

本文針對GAAA作了如下三點改進：

(1)改變遺傳算法中的變異算子。基本的GAAA是選擇一個處于相連位置的變異序列，這樣發生變異的元素會相對集中。改進措施為，隨機選取一些不相連的變異位置，將處于這些變異位置的數碼取出來組成一個變異序列，將其逆轉后再依次放入原來序列的空位置中。

假設最優布局的編碼為1，2，3，4，5，6。

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

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

圖1　融合算法流程圖

2.2收斂過程

用融合算法對每個夾具布局的每個夾具元件進行優化，求出每個夾具布局的最大特征值Smax，存儲所有夾具布局M中最大特征值Smax的最小值Δmin以及相對應的夾具布局(圖1)。對所有的迭代過程N均重復同樣的過程，求出所有Δmin中的最小值Δwork以及最小值對應的夾具布局。如果迭代次數達到設定的最大迭代次數N，并且每次迭代后的元件位置均在夾具元件的位置范圍內，或者每一次迭代的結果浮動范圍較小，趨于穩定，那么算法收斂。

3　實例分析

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

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

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

(a)車輛側邊框

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

(a)階段1

(b)階段2

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

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

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

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

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

(a)蟻群算法與改進的GAAA求得的最優夾具布局

(b)基本的與改進的GAAA求得的最優夾具布局圖5　最優夾具布局

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

表1　蟻群算法和改進的GAAA求得的最優夾具布局　mm

表2　蟻群算法和改進的GAAA結果比較

表3　基本的GAAA和改進的GAAA求得的最優夾具布局　mm

表4　基本的GAAA和改進的GAAA結果比較

4　結語

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

[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]陳蔚芳, 倪麗君, 王寧生. 夾具布局和夾緊力的優化方法研究[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]丁建立, 陳增強, 袁著祉. 遺傳算法與螞蟻算法的融合[J]. 計算機研究與發展, 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

國家自然科學基金資助項目(51205286, 51275348)

TH122；TH16< class="emphasis_italic">DOI

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

謝偉松，男，1967年生。天津大學理學院副教授。主要研究方向為微分方程數值解、計算幾何。鄧錚，女，1990年生。天津大學理學院碩士研究生。丁伯慧(通信作者)，女，1976年生。天津大學機械工程學院講師。