耿育科,孫薈博

（1.中航飛機(jī)西安飛機(jī)分公司，西安 710089；2.上海中信信息發(fā)展股份有限公司，上海 200333）

裝配序列規(guī)劃（Assembly Sequence Planning，簡(jiǎn)稱ASP）是產(chǎn)品生產(chǎn)過程中非常重要的一個(gè)環(huán)節(jié)。裝配序列的優(yōu)劣直接影響了產(chǎn)品裝配的質(zhì)量、裝配的效率以及成本，甚至影響可裝配性[1]。為了提高找尋可行裝配序列的效率，一些智能優(yōu)化算法被應(yīng)用到裝配序列規(guī)劃中。Lazzerini等[2]將遺傳算法應(yīng)用到了裝配序列規(guī)劃中。Ong[3]和Milner[4]等在各自的研究中將模擬退火算法應(yīng)用到了裝配序列規(guī)劃中，不足之處是單獨(dú)的模擬退火算法對(duì)最優(yōu)搜尋空間的尋找能力表現(xiàn)不佳。Wang[5]和Failli[6]等提出了一種結(jié)合蟻群優(yōu)化算法的裝配序列規(guī)劃方式。

粒子群算法（Particle Swarm Optimization，PSO）具有便于實(shí)現(xiàn)、占用計(jì)算機(jī)內(nèi)存少、全局搜尋能力強(qiáng)等特點(diǎn)，在解決不同的優(yōu)化問題時(shí)有著良好的表現(xiàn)，吸引了很多工程應(yīng)用領(lǐng)域內(nèi)學(xué)者的注意[7-10]，因此本文采用粒子群算法進(jìn)行裝配序列的規(guī)劃。

1 粒子群算法在裝配序列規(guī)劃中的應(yīng)用

將粒子群算法引入到裝配序列規(guī)劃當(dāng)中，PSO中的粒子對(duì)應(yīng)每一條裝配序列，然后根據(jù)裝配過程中影響成本和時(shí)間的因素，構(gòu)建適應(yīng)度函數(shù)，作為序列的評(píng)判標(biāo)準(zhǔn)，并且根據(jù)幾何關(guān)系構(gòu)建數(shù)學(xué)模型，確保裝配序列的可行性，對(duì)不滿足的序列實(shí)行懲罰，降低其作為最優(yōu)解的可能。

1.1 適應(yīng)度函數(shù)評(píng)價(jià)

影響裝配序列規(guī)劃的因素有很多，而裝配過程中裝配方向或者裝配工具的改變通常會(huì)導(dǎo)致裝配時(shí)間以及裝配成本的增加，因此本文將工具變換次數(shù)、裝配方向變換次數(shù)以及裝配操作類型變換次數(shù)作為衡量一個(gè)裝配序列的標(biāo)準(zhǔn)，加入到適應(yīng)度函數(shù)之中。

根據(jù)Lu等[11]的研究，對(duì)于一個(gè)裝配產(chǎn)品，若給出了一個(gè)可行的裝配序列，那么該裝配序列所對(duì)應(yīng)的適應(yīng)度函數(shù)為：

式中，S為裝配體中的零部件總數(shù)量；nt、nor以及nop分別代表了裝配工具的變換次數(shù)、裝配方向的變換次數(shù)和裝配操作的變換次數(shù)；ωt、ωor和ωop分別為nt、nor以及nop的權(quán)重，值為在[0，1]上平均分布的隨機(jī)數(shù)?？梢钥闯?，nt、nor和nop越小，即裝配成本和時(shí)間越小，適應(yīng)度函數(shù)F的值越大。

對(duì)于一個(gè)裝配產(chǎn)品，給出了一個(gè)不可行的裝配序列，即裝配序列不滿足裝配干涉關(guān)系的時(shí)候，其對(duì)應(yīng)的適應(yīng)度函數(shù)值按式（2）求取，m為該裝配序列中不滿足干涉關(guān)系的次數(shù)，有：

1.2 裝配干涉矩陣的構(gòu)建

產(chǎn)品的可裝配性是裝配規(guī)劃的第一要求。在算法執(zhí)行的過程中，產(chǎn)品的裝配干涉矩陣是判斷某一條裝配序列是否可行的依據(jù)，對(duì)于不符合裝配干涉矩陣的序列，視為不滿足約束條件，進(jìn)行懲罰處理[12]。

根據(jù)裝配體零部件之間的幾何關(guān)系，構(gòu)建在三維空間上裝配干涉矩陣。裝配干涉矩陣以Ma表示，a∈（±X,±Y,±Z），則一個(gè)具有d個(gè)零部件的裝配體在方向a上的裝配干涉矩陣可表示為：

式中，C1，C2，…，Cd分別代表了裝配體的d個(gè)零部件；Cij=1表示零件Ci在方向a上，往裝配位置移動(dòng)時(shí)，將與零件Cj發(fā)生碰撞；由于零件不與自身發(fā)生碰撞，因此Cij=0；由于a方向上的Cij等同于-a方向上的Cji，因此取3個(gè)正方向上的干涉矩陣M+X，M+Y和M+Z，即可對(duì)裝配序列的可行性進(jìn)行評(píng)價(jià)。

對(duì)于給出的裝配序列，通過提前定義，每一步裝配操作都對(duì)應(yīng)了固定的工具以及裝配操作類型，從而使工具變換次數(shù)nt和裝配操作類型變換次數(shù)nop較容易獲得。而裝配方向的變換次數(shù)nor以及m可由3個(gè)裝配干涉矩陣得出。

1.3 粒子群在裝配序列規(guī)劃中的數(shù)學(xué)表示

相對(duì)標(biāo)準(zhǔn)群粒子算法，應(yīng)用在裝配序列規(guī)劃中的PSO有著相同的執(zhí)行步驟，和不同的粒子位置、速度表達(dá)式以及更新公式。裝配序列是一串標(biāo)示著各個(gè)零件在裝配過程中序號(hào)的數(shù)字，因此最優(yōu)解也應(yīng)該分布在離散的正整數(shù)空間上。零件的總個(gè)數(shù)d即為粒子所在的維度[13-14]。

粒子i的位置表示為：

式中，xij代表了粒子i在第j維度上的位置的值。xi（t）中任意兩個(gè)元素的值都不相同，且為正整數(shù)。在算法進(jìn)行初始化的時(shí)候，應(yīng)該隨機(jī)將1～d的正整數(shù)分配給d個(gè)元素。隨機(jī)產(chǎn)生的xi（t）有利于提高種群的多樣性，增強(qiáng)算法在迭代初期的局部尋優(yōu)能力。

粒子i的速度表達(dá)式與位置表達(dá)式形式上相近：

式中，vij代表粒子i在第j維度上的速度的值。與粒子的位置一樣，隨機(jī)產(chǎn)生初始速度，并且vi（t）中的任意兩個(gè)非零元素的值都不相同。

位置相減得到一個(gè)新的速度：

式中，x1、x2為兩個(gè)位置，代表兩個(gè)裝配序列。對(duì)于第j維，x1j等于x2j，則vj= 0 ；若x1j不等于x2j，則vj=x1j，即速度v繼承了x1的有效元素。

位置的更新如下：

式中，x1（t）為粒子在第t次迭代時(shí)的位置，vi（t+1）為第t+1次迭代時(shí)的速度，兩者相加得到第t+1次迭代時(shí)的位置xi（t+1）。若第j維的速度vij（t+1）等于零，則xij（t+1）=xij（t）；若vij（t+1）不等于零，則交換xij（t）與vij（t+1）的值。

參數(shù)乘以速度用以調(diào)整速度，控制速度v2從v1中繼承到的元素個(gè)數(shù)，如下：

式中，r為[0，1]上平均分布的隨機(jī)數(shù)?？芍猚的取值越大，v2繼承v1的元素越多。速度相加得到一個(gè)新的速度，其各個(gè)維度上元素的值根據(jù)式（9）得出。

式中，r為[0，1]上平均分布的隨機(jī)數(shù)，常數(shù)const越大，v從速度v1中繼承的元素越多。在本文中，取const=0.5。

粒子速度及位置更新如下：

式中，ω控制粒子現(xiàn)有速度對(duì)新速度的影響；c1控制粒子歷史自身最優(yōu)位置（自身最優(yōu)裝配序列）對(duì)新速度的影響；c2控制著粒子全局最優(yōu)位置（全局最優(yōu)裝配序列）對(duì)新速度的影響；ω、c1和c2在[0，1]范圍內(nèi)取值。式中包含了位置與速度相加、位置相減、速度相加以及速度的乘法。式（6）～（9）所定義的特殊的運(yùn)算確保了裝配序列的可行性。

圖1 發(fā)動(dòng)機(jī)化油器裝配體Fig.1 Engine carburetor assembly

圖2 發(fā)動(dòng)機(jī)化油器展開圖Fig.2 Engine carburetor unfolded drawing

表1 發(fā)動(dòng)機(jī)化油器零件

2 案例研究與分析

以發(fā)動(dòng)機(jī)化油器的裝配為例，對(duì)粒子群算法在裝配序列中的應(yīng)用進(jìn)行分析與驗(yàn)證，如圖1、圖2所示。圖2中，發(fā)動(dòng)機(jī)化油器由15個(gè)零件組成，每個(gè)零件沿著±X、±Y、±Z軸有6個(gè)可能的裝配方向。按圖2中的編號(hào)，依次對(duì)應(yīng)的零件如表1所示。

裝配體所有零件沿著+X、+Y、+Z3個(gè)坐標(biāo)軸方向上的裝配干涉矩陣為M+X、M+Y、M+Z：

發(fā)動(dòng)機(jī)化油器的零件裝配過程中所用的裝配工具以及裝配操作類型如表2所示。

其中，零件裝配工具更換次數(shù)、裝配方向變換次數(shù)以及裝配操作類型變換次數(shù)的權(quán)值分別設(shè)定為ωt=0.3、ωor=0.4、ωop=0.3?？偟螖?shù)t=100，取式（9）中常數(shù)const=0.5。算法各參數(shù)及適應(yīng)度函數(shù)各評(píng)價(jià)指標(biāo)的權(quán)值保持不變，ω、c1、c2的取值均為0.5，粒子群種群容量分別取 10、20、40、60、80、100，在 Matlab 中編寫、運(yùn)行程序，不同種群容量的算法程序分別運(yùn)行20次，獲取優(yōu)化或者近似優(yōu)化解。根據(jù)適應(yīng)度函數(shù)式（1）計(jì)算可知，對(duì)于可行的裝配序列，其適應(yīng)度函數(shù)值F的最大值為28.3，因此優(yōu)化過程中適應(yīng)度函數(shù)值接近或等于28.3的裝配序列即可認(rèn)為是優(yōu)化結(jié)果。

表3為種群容量大小取100時(shí)，適應(yīng)度函數(shù)值取得最優(yōu)值28.3的一條裝配序列的相關(guān)信息。表3種群容量為100的最優(yōu)裝配序列。

從表2中可以看出，裝配工具變換次數(shù)nt=2，裝配方向變換次數(shù)nor=2，裝配操作類型變換次數(shù)為nop=1。結(jié)合裝配干涉矩陣M+X、M+Y、M+Z可以得到：（1）零件3必須在零件1和零件2之前安裝；（2）零件15必須在零件 10 之前安裝；（3）零件 10 必須在零件 4、5、6、7之前安裝；（4）零件14必須在零件8和9之前安裝；（5）裝配過程中存在3個(gè)裝配方向；（6）在尋找最優(yōu)裝配序列的過程中，裝配方向的變換次數(shù)、裝配工具變換次數(shù)與裝配類型的變換次數(shù)，這3者之間往往存在著矛盾。

表2 零件裝配工具及操作類型

表3 種群容量為100的最優(yōu)裝配序列

3 結(jié)束語

本文根據(jù)裝配序列規(guī)劃的特點(diǎn)和要求，采用粒子群算法來解決裝配序列規(guī)劃問題。將裝配過程工具變換次數(shù)、裝配方向變換次數(shù)以及裝配操作類型變換次數(shù)作為衡量一個(gè)裝配序列的標(biāo)準(zhǔn)，加入到適應(yīng)度函數(shù)之中，完成了適應(yīng)度函數(shù)的構(gòu)建。根據(jù)裝配體零部件之間的幾何關(guān)系，構(gòu)建了三維空間上的裝配干涉矩陣。最后通過發(fā)動(dòng)機(jī)化油器裝配實(shí)例，驗(yàn)證了本文方法的可行性。

[1]劉繼紅，王峻峰. 復(fù)雜產(chǎn)品協(xié)同裝配設(shè)計(jì)與規(guī)劃[M]. 武漢：華中科技大學(xué)出版社，2011.

LIU Jihong, WANG Junfeng. Complex product collaborative assembly design and planning[M]. Wuhan: Huazhong University of Science and Technology Press,2011.

[2]LAZZERINI B, MARCELLONI F. A genetic algorithm for generating optimal assembly plans[J]. Artificial Intelligence in Engineering,2000, 14(4): 319-329.

[3]ONG S K, DING J, NEE A Y C. Hybrid GA and SA dynamic setup planning optimization[J]. International Journal of Production Research,2002, 40(18): 4697-4719.

[4]MILNER J M, GRAVES S C, WHITNEY D E. Using simulated annealing to select least-cost assembly sequences[C]//Proceeding of Robotics and Automation. New York: IEEE, 1994: 2058-2063.

[5]WANG J F, LIU J H, ZHONG Y F. A novel ant colony algorithm for assembly sequence planning[J]. The International Journal of Advanced Manufacturing Technology, 2005, 25(11-12): 1137-1143.

[6]FAILLI F, DINI G. Ant colony systems in assembly planning: a new approach to sequence detection and optimization[C]//Proceedings of the 2nd CIRP international seminar on intelligent computation in manufacturing engineering. 2000: 227-232.

[7]CLERC M, KENNEDY J. The particle swarm-explosion,stability, and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58-73.

[8]LOVBJERG M, RASMUSSEN T K, KRINK T. Hybrid particle swarm optimiser with breeding and subpopulations[C]//Proceedings of the Genetic and Evolutionary Computation Conference. San Francisco, 2001:469-476.

[9]SHI Y, EBERHART R C. Empirical study of particle swarm optimization[J]. Academic Press, 1967.

[10]NOEL M M, JANNETT T C. Simulation of a new hybrid particle swarm optimization algorithm[C]//Symposium on System Theory. New York:IEEE, 2004: 150-153.

[11]LU C, WONG Y S, FUH J Y H. An enhanced assembly planning approach using a multi-objective genetic algorithm[J]. Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture, 2006,220(2):255-272.

[12]BONNEVILLE F, PERRARD C, HENRIOUD J M. A genetic algorithm to generate and evaluate assembly plans[C]//Proceedings of Emerging Technologies and Factory Automation. New York: IEEE,1995:231-239.

[13]王峻峰，李世其，劉繼紅，等. 計(jì)算機(jī)輔助裝配規(guī)劃研究綜述 [J]. 工程圖形學(xué)報(bào)，2005，2:1-7.

WANG Junfeng, LI Shiqi, LIU Jihong, et al. Computer aided assembly planning: a survey[J]. Journal of Engineering Graphics, 2005,2:1-7.

[14]楊冰，張林鍹. 面向裝配工藝規(guī)劃的集成式裝配模型研究[J]. 系統(tǒng)仿真學(xué)報(bào)， 2008，18(2):533-536.

YANG Bing, ZHANG Linxuan. Introduction of integrated assembly model for assembly process planning[J]. Journal of System Simulation,2008,18(2):533-536.