一種復(fù)合算法的裝配序列規(guī)劃方法

劉恩福，劉　博，劉曉陽，李　伊

(河北科技大學(xué)機(jī)械工程學(xué)院，河北石家莊　050018)

?

一種復(fù)合算法的裝配序列規(guī)劃方法

劉恩福，劉博，劉曉陽，李伊

(河北科技大學(xué)機(jī)械工程學(xué)院，河北石家莊050018)

摘要：針對(duì)復(fù)雜產(chǎn)品裝配規(guī)劃的組合爆炸和盲目搜索難題，提出一種復(fù)合算法解決裝配序列規(guī)劃問題的方法。復(fù)合算法首先采取多色集合形式化推理獲取足夠數(shù)量的可行裝配序列，并將可行裝配序列作為遺傳算法的初始種群；然后，通過遺傳算法和蟻群算法將人的模糊知識(shí)融入規(guī)劃過程中求精確解；最后，通過實(shí)例驗(yàn)證了復(fù)合算法的可行性。

關(guān)鍵詞：計(jì)算機(jī)輔助制造；裝配序列規(guī)劃；復(fù)合算法；多色集合；遺傳算法；蟻群算法

E-mail：liuef@hebust.edu.cn

劉恩福，劉博，劉曉陽，等.一種復(fù)合算法的裝配序列規(guī)劃方法[J].河北科技大學(xué)學(xué)報(bào),2016,37(1):52-57.

LIU Enfu，LIU Bo，LIU Xiaoyang，et al.An assembly sequence planning method based on composite algorithm[J].Journal of Hebei University of Science and Technology,2016,37(1):52-57.

產(chǎn)品裝配序列規(guī)劃是產(chǎn)品設(shè)計(jì)開發(fā)過程中的重要環(huán)節(jié)，裝配序列規(guī)劃的結(jié)果能夠直接影響產(chǎn)品的裝配質(zhì)量。因此，計(jì)算機(jī)輔助裝配序列規(guī)劃技術(shù)對(duì)于縮短裝配時(shí)間和減小裝配成本等方面具有重要意義，是目前國內(nèi)外研究的熱點(diǎn)。

計(jì)算機(jī)輔助裝配序列規(guī)劃的研究始于20世紀(jì)80年代，常見的裝配序列規(guī)劃方法有基于裝配優(yōu)先約束關(guān)系的裝配序列生成方法、基于組件識(shí)別的裝配序列求解方法、基于矩陣運(yùn)算的方法、基于知識(shí)的求解方法、拆卸法等[1]。

20世紀(jì)末，隨著研究的深入，人們開始將各類智能優(yōu)化算法如遺傳算法、蟻群算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法等應(yīng)用到裝配序列規(guī)劃中，這些智能優(yōu)化算法可以良好地克服傳統(tǒng)方法中存在的組合爆炸問題和裝配知識(shí)的局限性問題。遺傳算法[2-6]是目前在裝配序列規(guī)劃中應(yīng)用最為廣泛的算法，但遺傳算法在解決裝配序列規(guī)劃問題時(shí)具有全局收斂能力較差和存在大量冗余迭代的問題，而且要求初始種群必須為可行序列，初始設(shè)置較復(fù)雜；蟻群算法[7-12]在裝配序列規(guī)劃問題中也有著廣泛的應(yīng)用，但它具有初始信息素累積較慢，計(jì)算效率較低且容易局部收斂的缺點(diǎn)；多色集合理論體系[13-15]是一種新興的系統(tǒng)理論和信息處理的數(shù)學(xué)工具，在近幾年也被用來解決裝配序列規(guī)劃問題，但它僅能提供可行裝配序列，需要進(jìn)一步優(yōu)化才能獲得最優(yōu)裝配序列；混合蛙跳算法[16]和粒子群算法[17-19]已經(jīng)成功地應(yīng)用于復(fù)雜產(chǎn)品裝配序列規(guī)劃領(lǐng)域，但混合蛙跳算法在后期的收斂速度較慢，粒子群算法也存在著容易陷入局部最優(yōu)解的問題。

針對(duì)以上問題，本文提出一種基于復(fù)合算法進(jìn)行裝配序列規(guī)劃的方法。

1復(fù)合算法的基本原理

該復(fù)合算法利用多色集合形式化推理算法，并借鑒遺傳算法和蟻群算法推理過程快速生成最優(yōu)裝配序列。圖1為復(fù)合算法的原理圖。

圖1　復(fù)合算法基本原理圖Fig.1　Basic principle of composite algorithm

2復(fù)合算法研究

2.1　可行裝配序列生成

多色集合形式化推理算法能夠快速求出可行裝配序列，該算法在面對(duì)復(fù)雜產(chǎn)品時(shí)可以較大程度上縮小求解空間，有效降低計(jì)算的復(fù)雜性，所以，復(fù)合算法利用多色集合形式化推理算法來進(jìn)行可行裝配序列的生成。

2.1.1裝配關(guān)系模型

多色集合形式化推理算法以裝配約束關(guān)系方程組作為篩選可行裝配序列的充要條件。裝配約束關(guān)系方程組包括定位關(guān)系方程組和干涉關(guān)系方程組，它們分別由定位關(guān)系模型和干涉關(guān)系模型求取得出[20]，如圖2和圖3所示。

圖2　定位關(guān)系模型Fig.2　Location relationship model

圖3　干涉關(guān)系模型Fig.3　Interference relationship model

圖2和圖3中，(ai,aj)表示零件j對(duì)零件i的邏輯關(guān)系；F1~F6表示零件在x,y,z方向平動(dòng)、轉(zhuǎn)動(dòng)的定位關(guān)系；F7~F12表示零件在±x,±y,±z方向的干涉關(guān)系；·表示存在定位關(guān)系或者干涉關(guān)系。

2.1.2定位關(guān)系方程的建立

定位關(guān)系方程是由定位元件(能夠確定某一零件在裝配體中正確位置的零件集)按一定的邏輯關(guān)系組成的關(guān)系式，定位關(guān)系方程的值代表零件在裝配時(shí)能否定位。

定位關(guān)系方程組的求取算法：

3)若B(ak)=aj∧am，且B(ak)=aj∧al，則B(ak)=aj∧(am∨al)。

其中：ai代表零件i是否安裝，如果零件i已安裝，則ai=1，如果零件i未安裝，則ai=0；B(ai)的值代表零件i的定位狀態(tài)，B(ai)=1代表零件i在裝配時(shí)能夠定位，B(ai)=0代表零件i在裝配時(shí)不能定位。

2.1.3干涉關(guān)系方程的建立

干涉關(guān)系方程是由1組干涉某一零件進(jìn)入裝配區(qū)間的其他零件按照一定的邏輯關(guān)系組成的關(guān)系式，干涉關(guān)系方程的值代表零件在裝配時(shí)是否會(huì)發(fā)生干涉。

干涉關(guān)系方程組的求取算法如下：

3)若W(ak)=aj∧am，且W(ak)=aj∧al，則W(ak)=aj∧(am∨al)。

其中W(ai)的值代表零件i的干涉狀態(tài)，W(ai)=1代表零件i在裝配時(shí)會(huì)與其他零件發(fā)生干涉，W(ai)=0代表零件i在裝配時(shí)不會(huì)與其他零件發(fā)生干涉。

2.2　可行裝配序列優(yōu)化

基于多色集合形式化推理生成的可行裝配序列，通過對(duì)遺傳算法的變異操作進(jìn)行改進(jìn)，快速生成新的可行裝配序列，并對(duì)可行裝配序列進(jìn)一步優(yōu)化。

2.2.1適應(yīng)度函數(shù)建立

適應(yīng)度函數(shù)的建立直接影響著新的可行裝配序列生成效率和質(zhì)量。優(yōu)秀的裝配序列應(yīng)具有較低的裝配成本、較短的裝配時(shí)間及較高的裝配質(zhì)量，因此，本文主要以裝配方向的改變次數(shù)、裝配工具的更換次數(shù)以及裝配體的穩(wěn)定性這3項(xiàng)評(píng)價(jià)指標(biāo)來構(gòu)建適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)的構(gòu)建方法如下：

f(s)=ω1vc-ω2vt-ω3vd+vp，

(1)

vp為裝配序列的幾何可行性，取

ω1,ω2,ω3為權(quán)重系數(shù)。

2.2.2改進(jìn)變異算法

為了保證新的可行裝配序列快速生成，本文提出一種新的變異方法：選取1個(gè)父代個(gè)體，從這個(gè)個(gè)體中隨機(jī)選擇1個(gè)零件，對(duì)選擇零件后的序列利用多色集合形式化推理部分的算法重新進(jìn)行排序，由于多色集合形式化推理算法具有快速性和準(zhǔn)確性，可以有效生成新的可行序列，這樣就免去了對(duì)生成序列進(jìn)行可行性判斷的步驟，有效提高了迭代效率。

2.2.3可行裝配序列優(yōu)化終止條件

2.3　最優(yōu)裝配序列生成

該復(fù)合算法借鑒蟻群算法使裝配序列優(yōu)化過程快速收斂，生成最優(yōu)裝配序列。

2.3.1狀態(tài)轉(zhuǎn)移概率函數(shù)的建立

在構(gòu)建裝配序列的過程中，從基礎(chǔ)件出發(fā)，根據(jù)狀態(tài)轉(zhuǎn)移概率選擇下一級(jí)裝配零件，狀態(tài)轉(zhuǎn)移概率由信息素、裝配方向和裝配工具決定。

狀態(tài)轉(zhuǎn)移概率函數(shù)的構(gòu)建方法如下：

(2)

2.3.2信息素初始值設(shè)定

信息素初始值設(shè)計(jì)如下：

(3)

3復(fù)合算法的實(shí)現(xiàn)流程

該復(fù)合算法的實(shí)現(xiàn)流程如圖4所示。

圖4　復(fù)合算法流程圖Fig.4　Flow chart of the composite algorithm

4實(shí)例驗(yàn)證

為了驗(yàn)證算法的可行性，以圖5所示裝配體為例，使用Visual C++ 6.0分別對(duì)復(fù)合算法、遺傳算法、蟻群算法進(jìn)行編程實(shí)現(xiàn)。其中，設(shè)定遺傳算法的初始種群數(shù)N=5，變異概率為1，最小遺傳迭代次數(shù)I=10，最小進(jìn)化率P=0.05，螞蟻數(shù)量M=5，全局信息素蒸發(fā)率為0.3。

圖5　軸系部件Fig.5　Shaft parts

通過多色集合形式化推理算法對(duì)裝配體進(jìn)行可行裝配序列生成，得到5個(gè)可行裝配序列，分別是：

1)a1→a3→a2→a4→a5→a6；

2)a1→a3→a2→a5→a4→a6；

3)a1→a3→a2→a5→a6→a4；

4)a1→a3→a4→a2→a5→a6；

5)a1→a4→a3→a2→a5→a6。

運(yùn)行程序所得的最優(yōu)裝配序列為a1→a3→a2→a5→a6→a4。圖6為3種算法中各代種群的平均適應(yīng)度函數(shù)值圖。

圖6　種群各代平均適應(yīng)度值Fig.6　Fitness value of each generation

同時(shí)，分別采用不同的種群數(shù)量和不同的螞蟻數(shù)量對(duì)3種算法進(jìn)行比較，其結(jié)果如表1所示。

表1　不同參數(shù)下的算法運(yùn)行結(jié)果

由圖6和表1可以看出，遺傳算法雖然收斂性較為穩(wěn)定，但其收斂速度較慢，而且初始種群必須為可行序列，初始設(shè)置較為復(fù)雜，蟻群算法雖然收斂速度較快，但由于其初始信息素累積的盲目性，造成收斂不穩(wěn)定的現(xiàn)象，很容易局部收斂，該復(fù)合算法既改進(jìn)了遺傳算法收斂較慢的缺點(diǎn)，又避免了蟻群算法收斂不穩(wěn)定的缺點(diǎn)。

5結(jié)語

提出了一種新的復(fù)合算法來解決裝配序列規(guī)劃問題，此算法由多色集合形式化推理算法、遺傳算法、蟻群算法融合而成，有效避免了遺傳算法對(duì)初始種群依賴性強(qiáng)以及蟻群算法容易局部收斂的問題。通過實(shí)驗(yàn)驗(yàn)證,復(fù)合算法不僅能夠有效地生成裝配序列，而且具有更好的收斂效率和全局收斂性。

參考文獻(xiàn)/References:

[1]彭琛, 劉克能, 周長省. 機(jī)械產(chǎn)品裝配序列規(guī)劃研究[J]. 南京師范大學(xué)學(xué)報(bào)(工程技術(shù)版), 2006,6(2):81-85.

PENG Chen, LIU Keneng, ZHOU Changsheng. Study on mechanical product’s assembly sequence planning[J]. Journal of Nanjing Normal University (Engineering and Technology), 2006,6(2):81-85.

[2]李原, 張開富, 王挺, 等. 基于遺傳算法的飛機(jī)裝配序列規(guī)劃優(yōu)化方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2006,12(2):188-191.

LI Yuan, ZHANG Kaifu, WANG Ting, et al. Assembly sequence planning optimization for aircraft assembly based on GA[J]. Computer Integrated Manufacturing Systems, 2006,12(2):188-191.

[3]韓曉東, 蔡勇, 蔣剛. 基于改進(jìn)的遺傳算法的裝配序列規(guī)劃[J]. 機(jī)械設(shè)計(jì)與制造, 2009(3):212-214.

HAN Xiaodong, CAI Yong, JIANG Gang. Assembly sequence planning based on the improved genetic algorithm[J]. Machinery Design & Manufacture, 2009(3):212-214.

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

JIANG Chao, WU Bo, LI Mingyu, et al. Product assembly sequence planning method based on genetic algorithm[J]. Machinery & Electronics, 2012(4):7-11.

[5]丁慧敏, 李蓓智, 周亞琴. 基于遺傳算法的裝配序列規(guī)劃[J]. 東華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2001,27(6):10-13.

DING Huimin, LI Beizhi, ZHOU Yaqin. Assembly sequence planning based on genetic algorithm[J]. Journal of Donghua University(Natural Science), 2001,27(6):10-13.

[6]陳穎悅, 吳豪杰. 基于改進(jìn)遺傳算法的拆卸序列優(yōu)化研究[J]. 廈門理工學(xué)院學(xué)報(bào), 2014,22(5):72-77.

CHEN Yingyue, WU Haojie. Disassembly sequence optimization based on the improved genetic algorithm[J]. Journal of Xiamen University of Technology, 2014,22(5):72-77.

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

SHI Shicai, LI Rong, FU Yili, et al. Assembly sequence planning based on improved ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2010,16(6):1189-1194.

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

DENG Mingxing, TANG Qiuhua, LEI Zhe. A novel approach for assembly sequence planning based on ant colony algorithm[J]. Engineering Journal of Wuhan University, 2013,46(2):246-251.

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

FANG Jianxin. Research on Assembly Sequence Planning based on Ant Colony Algorithm[D]. Wuhan: Huazhong University of Science & Technology, 2007.

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

XIE Long, FU Yili, MA Yulin. Ant-colony-optimization strategy for assembly sequence planning[J]. Journal of Harbin Institute of Technology, 2006,38(2): 180-183.

[11]盧天宇. 遺傳蟻群混合算法研究及應(yīng)用[D]. 西安：西安科技大學(xué), 2012.

LU Tianyu. Research and Application of Genetic Ant Colony Hybrid Algorithm[D]. Xi’an: Xi’an University of Science and Technology, 2012.

[12]趙義武, 牛慶銀, 王憲成. 遺傳算法與蟻群算法的融合研究[J]. 科學(xué)技術(shù)與工程, 2010,10(16):4017-4020.

ZHAO Yiwu, NIU Qingyin, WANG Xiancheng. Study on the combination of genetic algorithm and ant algorithm[J]. Science Technology and Engineering, 2010,10(16):4017-4020.

[13]李宗斌, 高新勤, 趙麗萍. 基于多色集合理論的信息建模與優(yōu)化技術(shù)[M]. 北京:科學(xué)出版社, 2010.

[14]趙姍姍, 李宗斌. 基于多色集合的裝配序列形式化推理方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2008,14(8):1579-1585.

ZHAO Shanshan, LI Zongbin. Formalization reasoning method for assembly sequences based on polychromatic sets[J]. Computer Integrated Manufacturing Systems, 2008,14(8):1579-1585.

[15]李宗斌. 先進(jìn)制造中多色集合理論的研究及應(yīng)用[M]. 北京:中國水利水電出版社, 2005.

[16]王松, 孫振忠, 郭建文, 等. 基于混合蛙跳算法的復(fù)雜產(chǎn)品裝配序列規(guī)劃[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2014,20(12):2991-2999.

WANG Song, SUN Zhenzhong, GUO Jianwen, et al. Assembly sequence planning based on shuffled frog leaping algorithm[J]. Computer Integrated Manufacturing Systems, 2014,20(12):2991-2999.

[17]于宏, 王成恩, 于嘉鵬, 等. 基于粒子群算法的復(fù)雜產(chǎn)品裝配序列規(guī)劃[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010,31(2):261-264.

YU Hong, WANG Cheng’en, YU Jiapeng, et al. Assembly sequence planning based on particle swarm optimization algorithm for complex product[J]. Journal of Northeastern University (Natural Science), 2010,31(2):261-264.

[18]張秀芬, 張樹有. 基于粒子群算法的產(chǎn)品拆卸序列規(guī)劃方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2009,15(3):508-514.

ZHANG Xiufen, ZHANG Shuyou. Product disassembly sequence planning based on particle swarm optimization algorithm[J]. Computer Integrated Manufacturing Systems, 2009,15(3):508-514.

[19]陳海彬, 郭建文, 孫振忠, 等. 基于自適應(yīng)變異粒子群優(yōu)化算法的產(chǎn)品裝配序列規(guī)劃[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015(7):153-156.

CHEN Haibin, GUO Jianwen, SUN Zhenzhong, et al. Product assembly sequences planning based on adaptive particle swarm optimization algorithm with mutation[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2015(7):153-156.

[20]張博, 張洪濤, 趙姍姍, 等. 基于多色集合理論的產(chǎn)品裝配規(guī)劃建模與算法研究[J]. 西安交通大學(xué)學(xué)報(bào), 2005,39(11):1254-1258.

ZHANG Bo, ZHANG Hongtao, ZHAO Shanshan, et al. Product assembly planning modeling and algorithm based on polychromatic sets[J]. Journal of Xi’an Jiaotong University, 2005,39(11):1254-1258.

An assembly sequence planning method based on composite algorithm

LIU Enfu， LIU Bo， LIU Xiaoyang， LI Yi

(School of Mechanical Engineering, Hebei University of Science and Technology, Shijiazhuang, Hebei 050018, China)

Abstract:To solve the combination explosion problem and the blind searching problem in assembly sequence planning of complex products, an assembly sequence planning method based on composite algorithm is proposed. In the composite algorithm, a sufficient number of feasible assembly sequences are generated using formalization reasoning algorithm as the initial population of genetic algorithm. Then fuzzy knowledge of assembly is integrated into the planning process of genetic algorithm and ant algorithm to get the accurate solution. At last, an example is conducted to verify the feasibility of composite algorithm.

Keywords:computer aided manufacturing; assembly sequence planning; composite algorithm; polychromatic sets; genetic algorithm; ant algorithm

作者簡(jiǎn)介：劉恩福(1960—)，男，河北石家莊人，教授，主要從事制造業(yè)信息化方面的研究。

基金項(xiàng)目：河北省應(yīng)用基礎(chǔ)研究計(jì)劃重點(diǎn)基礎(chǔ)研究項(xiàng)目(14961811D)

收稿日期：2015-09-11；修回日期：2015-11-23；責(zé)任編輯：馮民

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

doi:10.7535/hbkd.2016yx01009

文章編號(hào)：1008-1542(2016)01-0052-06