一種復合算法的裝配序列規劃方法

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

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

?

一種復合算法的裝配序列規劃方法

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

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

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

關鍵詞：計算機輔助制造；裝配序列規劃；復合算法；多色集合；遺傳算法；蟻群算法

E-mail：liuef@hebust.edu.cn

劉恩福，劉博，劉曉陽，等.一種復合算法的裝配序列規劃方法[J].河北科技大學學報,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.

產品裝配序列規劃是產品設計開發過程中的重要環節，裝配序列規劃的結果能夠直接影響產品的裝配質量。因此，計算機輔助裝配序列規劃技術對于縮短裝配時間和減小裝配成本等方面具有重要意義，是目前國內外研究的熱點。

計算機輔助裝配序列規劃的研究始于20世紀80年代，常見的裝配序列規劃方法有基于裝配優先約束關系的裝配序列生成方法、基于組件識別的裝配序列求解方法、基于矩陣運算的方法、基于知識的求解方法、拆卸法等[1]。

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

針對以上問題，本文提出一種基于復合算法進行裝配序列規劃的方法。

1復合算法的基本原理

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

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

2復合算法研究

2.1　可行裝配序列生成

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

2.1.1裝配關系模型

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

圖2　定位關系模型Fig.2　Location relationship model

圖3　干涉關系模型Fig.3　Interference relationship model

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

2.1.2定位關系方程的建立

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

定位關系方程組的求取算法：

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的定位狀態，B(ai)=1代表零件i在裝配時能夠定位，B(ai)=0代表零件i在裝配時不能定位。

2.1.3干涉關系方程的建立

干涉關系方程是由1組干涉某一零件進入裝配區間的其他零件按照一定的邏輯關系組成的關系式，干涉關系方程的值代表零件在裝配時是否會發生干涉。

干涉關系方程組的求取算法如下：

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

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

2.2　可行裝配序列優化

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

2.2.1適應度函數建立

適應度函數的建立直接影響著新的可行裝配序列生成效率和質量。優秀的裝配序列應具有較低的裝配成本、較短的裝配時間及較高的裝配質量，因此，本文主要以裝配方向的改變次數、裝配工具的更換次數以及裝配體的穩定性這3項評價指標來構建適應度函數。

適應度函數的構建方法如下：

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

(1)

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

ω1,ω2,ω3為權重系數。

2.2.2改進變異算法

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

2.2.3可行裝配序列優化終止條件

2.3　最優裝配序列生成

該復合算法借鑒蟻群算法使裝配序列優化過程快速收斂，生成最優裝配序列。

2.3.1狀態轉移概率函數的建立

在構建裝配序列的過程中，從基礎件出發，根據狀態轉移概率選擇下一級裝配零件，狀態轉移概率由信息素、裝配方向和裝配工具決定。

狀態轉移概率函數的構建方法如下：

(2)

2.3.2信息素初始值設定

信息素初始值設計如下：

(3)

3復合算法的實現流程

該復合算法的實現流程如圖4所示。

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

4實例驗證

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

圖5　軸系部件Fig.5　Shaft parts

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

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。

運行程序所得的最優裝配序列為a1→a3→a2→a5→a6→a4。圖6為3種算法中各代種群的平均適應度函數值圖。

圖6　種群各代平均適應度值Fig.6　Fitness value of each generation

同時，分別采用不同的種群數量和不同的螞蟻數量對3種算法進行比較，其結果如表1所示。

表1　不同參數下的算法運行結果

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

5結語

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

參考文獻/References:

[1]彭琛, 劉克能, 周長省. 機械產品裝配序列規劃研究[J]. 南京師范大學學報(工程技術版), 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]. 計算機集成制造系統, 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]. 機械設計與制造, 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]蔣超, 吳波, 李明宇, 等. 基于遺傳算法的產品裝配序列規劃研究[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]丁慧敏, 李蓓智, 周亞琴. 基于遺傳算法的裝配序列規劃[J]. 東華大學學報(自然科學版), 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]. 廈門理工學院學報, 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]史士財, 李榮, 付宜利, 等. 基于改進蟻群算法的裝配序列規劃[J]. 計算機集成制造系統, 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]. 武漢大學學報(工學版), 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]方建新. 基于蟻群算法的裝配序列規劃研究[D]. 武漢：華中科技大學, 2007.

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

[10]謝龍, 付宜利, 馬玉林. 基于蟻群算法的裝配序列生成策略[J]. 哈爾濱工業大學學報, 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]盧天宇. 遺傳蟻群混合算法研究及應用[D]. 西安：西安科技大學, 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]. 科學技術與工程, 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]李宗斌, 高新勤, 趙麗萍. 基于多色集合理論的信息建模與優化技術[M]. 北京:科學出版社, 2010.

[14]趙姍姍, 李宗斌. 基于多色集合的裝配序列形式化推理方法[J]. 計算機集成制造系統, 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]李宗斌. 先進制造中多色集合理論的研究及應用[M]. 北京:中國水利水電出版社, 2005.

[16]王松, 孫振忠, 郭建文, 等. 基于混合蛙跳算法的復雜產品裝配序列規劃[J]. 計算機集成制造系統, 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]于宏, 王成恩, 于嘉鵬, 等. 基于粒子群算法的復雜產品裝配序列規劃[J]. 東北大學學報(自然科學版), 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]張秀芬, 張樹有. 基于粒子群算法的產品拆卸序列規劃方法[J]. 計算機集成制造系統, 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]陳海彬, 郭建文, 孫振忠, 等. 基于自適應變異粒子群優化算法的產品裝配序列規劃[J]. 組合機床與自動化加工技術, 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]張博, 張洪濤, 趙姍姍, 等. 基于多色集合理論的產品裝配規劃建模與算法研究[J]. 西安交通大學學報, 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

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

基金項目：河北省應用基礎研究計劃重點基礎研究項目(14961811D)

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

中圖分類號：TP391

文獻標志碼：A

doi:10.7535/hbkd.2016yx01009

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