衛星裝配序列規劃的智能優化算法研究

曾森 劉繼紅 郝佳

(1 航天東方紅衛星有限公司，北京 100094) (2 北京航空航天大學機械工程及自動化學院，北京 100191)

?

衛星裝配序列規劃的智能優化算法研究

曾森1劉繼紅2郝佳1

(1 航天東方紅衛星有限公司，北京 100094) (2 北京航空航天大學機械工程及自動化學院，北京 100191)

結合單個算法的優缺點，文章提出了一種用包含多種改進型智能優化算法的算法庫(IIAL)來解決衛星裝配序列規劃問題的方法。算法庫由算法向導和多種算法組成，算法向導可依據若干參數描述給出適合當前規劃任務的最合適算法，規劃人員可依據向導建議在遺傳算法、粒子群算法、蟻群算法、模擬退火算法中選擇相應算法進行求解。最后，用實例驗證了方法的合理性。該方法可為星上設備裝配序列規劃提供參考。

衛星裝配；裝配序列規劃；智能優化算法；算法庫

1 引言

衛星總裝是衛星研制的重要階段，總裝工藝規劃是衛星總裝的關鍵環節，而衛星裝配序列規劃是總裝工藝規劃的重要內容。隨著基于三維模型的數字化制造技術的推廣應用，利用計算機輔助給出多種約束條件下的最優裝配序列就很有必要。早期的裝配規劃方法大都是通過“割集法”[1]等圖論方法求出所有可能的裝配序列，然后按照評價標準從中選取較好的序列。但是，基于圖搜索的裝配規劃方法會遇到“組合爆炸”和“盲目搜索”的問題，從而難以選擇出最優的裝配序列。

為了解決上述難題，隨著人工智能的發展，眾多學者將諸如遺傳算法、蟻群算法、人工神經網絡等 “智能優化算法”引入裝配規劃研究中[2]。如Marian等人通過改進操作算子的遺傳算法迭代計算求得理想的裝配序列[3]。鄧明星、寧黎華、陳剛、張晶、劉海江等人分別探究了蟻群算法、免疫算法、模擬退火算法、人工神經網絡算法、粒子群算法在裝配序列規劃問題中的應用[4-8]。此外，曾冰、王松等人分別將螢火蟲算法和混合蛙跳算法引入到復雜產品裝配序列規劃中來[9-10]。

智能優化算法都是利用啟發式信息來探索最優解。總體來說，待求解裝配規劃問題的特點不同，采用的智能優化算法不同，最終的求解效果也不同。針對衛星裝配特點，為有助于選擇更合理的智能優化算法，本文對遺傳算法、粒子群算法、蟻群算法、模擬退火算法等智能優化算法在衛星裝配序列規劃中的應用進行了研究，提出了智能優化算法庫(IIAL)，幫助規劃人員便捷獲得最優裝配序列。

2 衛星裝配序列優化模型建立

2.1 裝配序列優化模型

裝配序列優化是指在滿足給定裝配工藝約束的條件下，產生或找到裝配成本最低、裝配效率最高的幾何可行裝配序列[11]。求解最優裝配序列，必須首先建立數學模型。在星上設備裝配中，要考慮幾何干涉、設備安裝方向、安裝工具、安裝方式、是否涂膠、是否涂抹導熱硅脂、接地阻值測量等因素。實際操作中，涂膠、涂抹導熱硅脂可提前實施，接地阻值測量可安裝后統一實施，此3項不占用設備安裝主線時間。影響星上設備裝配序列成本的因素主要包括4個方面：①序列存在幾何干涉則無法安裝；②裝配方向的改變直接影響裝配輔助時間；③螺釘規格和操作空間不同所導致的工具更換會降低裝配效率；④單人安裝、雙人協作以及依靠吊裝輔助安裝等不同裝配方式導致占用的資源和時間不同，從而增加裝配成本。因此，評價星上設備裝配序列優劣的要素應包括幾何和成本約束兩類，前者剔除幾何干涉的裝配序列，縮小求解空間；后者主要包括裝配方向、工具、方式等成本信息。

基于上述分析，星上設備裝配序列優化問題的數學模型為

(1)

(2)

式中：nt、nd、nc是一次計算過程中裝配工具、裝配方向和裝配方式的改變次數；M是幾何干涉的零件數目；ct、cd、cc和cg為裝配約束的權重系數，一般ct、cd、cc之和為1，可根據實際情況分配各值，而cg一般取值為50(遠大于1)。對于n個待安裝的星上設備，s={p1，p2，…，pn}表示裝配序列，pi(1≤i≤n)，滿足幾何約束，用f1(s)計算裝配成本，否則，用f1(s)+f2(s)計算。

2.2 優化模型中相關參數的計算

優化模型中需要計算的參數有M、nd、nt和nc。需要指出的是，與一般機電產品的裝配不同，星上設備裝配是將不同設備按要求安裝到星體結構上，設備之間沒有連接關系；同時，因部分方向結構板阻擋，星上設備無法從6個方向裝配到位。為此，給出如下兩點限定：

(1)參與裝配的星上設備或組件均為剛體，且每次操作設備均一次裝配到位；

(2)設備均安裝在方箱式星體結構板上，星體坐標系為XYZ三軸坐標系，裝配路徑為直線裝配，即裝配方向為±X，±Y，±Z共6個，若設備安裝方向已裝有結構板，則該方向對該設備存在干涉。

為計算幾何干涉零件數，須建立適合星上設備裝配特點的集成干涉矩陣，定義如下：

(3)

式中：Iijx=0是指當設備pi從結構外沿+X方向裝配到位時不與設備pj發生干涉；Iijx=1是指當設備pi從結構外沿+X方向裝配到位時與設備pj或+X側結構板發生干涉。同理，I中的元素Iijy、Iijz分別表示設備pi在+Y軸方向和+Z軸方向上裝配與設備pj或結構板的干涉情況，其取值類似于式(3)。設備pi沿-X軸方向裝配與設備pj干涉的情況，與設備pj沿+X軸方向裝配與設備pi干涉的情況相同，由元素Ijix表示。同樣，可以確定Ijiy和Ijiz的值。

定義pi是待裝配設備，Sa是在當前裝配狀態下由m個已裝配好的設備組成的臨時組件，Sa={P1，P2，…，Pm}，設備pi的裝配方向向量βi，βi={+Iix，+Iiy，+Iiz，-Iix，-Iiy，-Iiz}，某元素的值為0就表示待裝設備在該方向上是可裝配的，若為1則表示待裝設備在該方向上裝配將發生干涉。其中

(4)

(5)

式中：“∨”表示二進制的“或”操作。其余4個方向數值的求解與式(4)、(5)類似。待裝設備pi的裝配方向向量βi中的0值元素所對應的裝配方向組成了待裝設備pi的可行裝配方向集Fi。如果Fi=Φ，則表示待裝設備在當前狀態下沒有可行的裝配方向。裝配序列中存在一個沒有可行裝配方向的設備，則該序列就不可行，存在多個此類設備，就發生多次干涉，就可得出M值。

裝配工具方面，星上設備的裝配一般可由多種工具來完成，用一個Bit代表一種工具的信息，某一位值為1代表該種工具可用，值為0代表該種工具不可用，按二進制求值后，用一維矩陣E(q)來儲存裝配工具的信息，若有4種工具T1,T2,T3和T4，某個零件q可以用T1和T4來裝配，則T1位、和T4位所對應的值均為1，則E(q)=23+20=9，依此類推可以完成裝配工具信息的存儲。建立矩陣后，可通過給定初始值再對矩陣各元素按Bit位求“與”操作來求得裝配工具更換次數nt。

裝配方式方面，一般規定一臺設備對應一種裝配方式，可用一維矩陣B(q)來儲存裝配方式的信息。若有3種裝配方式，分別為C1,C2和C3，零件pi和零件pj的裝配方式屬于C1和C2，則相應的B(q)值為1和2，依此類推，可以完成裝配方式信息的存儲。建立該矩陣后，可通過直接通過對矩陣中各元素的比較來求得裝配方式更換次數nc。

裝配方向方面，可采用類似裝配工具的方法來求得待解序列的裝配方向改變次數nd。

3 算法庫原理及組成

由于智能優化算法各自不同的特點以及裝配規劃問題的復雜性，沒有哪種算法能解決所有規劃問題，而且對各算法在質量、效率等方面表現的評價仍停留在定性評價階段。為了便捷給出最優裝配序列，針對星上設備裝配特點，本文構建了一個算法庫，基于量化指標將多種智能優化算法集成到同一平臺下進行研究。算法庫原理示意圖如圖1所示。

算法庫由算法向導和算法池組成。算法向導以規劃人員對待求解問題的描述為輸入，以算法庫中已總結的各個算法效能指標歷史經驗值為主要量化參考依據，通過一定加權計算后，由算法向導給出當前問題的各算法適合值排序，幫助規劃人員快速選擇算法。算法池中包含裝配規劃遺傳算法(GA-SAP)、裝配規劃粒子群算法(PSO-SAP)、裝配規劃蟻群算法(AC-SAP)和裝配規劃模擬退火算法(SA-SAP)等4種智能優化算法，規劃人員可基于同一優化模型，按照算法向導的建議排序采用一種或多種算法進行計算，并將最后結果反饋到算法庫中。

3.1 算法向導

3.1.1 問題描述

問題描述是算法向導的主要輸入，包括3個方面：一是算法性能要求，明確使用者對算法質量、效率、成功率的優先權重以及參數復雜性方面的要求。初始階段，使用者可能更偏重于效率高且參數設置比較簡單的算法；而在實際處理階段，使用者就需要在算法效率與質量以及參數復雜性方面做一個平衡。二是裝配特征要求，明確裝配體零件數、裝配關系數、裝配類型、是否已得可行初始序列等信息。面對不同零件數、不同層級復雜度、不同裝配類型(單軸/多軸)的裝配規劃問題，不同算法求得的結果有明顯的質量差異。三是規劃人員經驗需求，明確其熟悉、傾向或指定的算法。算法應用效果與參數設置密切相關，必須考慮規劃人員已有的算法應用經驗。

根據上述輸入，可以大體判定當前問題的特點和規劃人員對算法的使用需求等信息，支持算法向導給出更合理的算法選擇建議。

3.1.2 算法評價指標

本文主要從求解質量、效率及成功率三方面量化評價算法的性能，評價指標見表1。

表1 算法評價指標體系Table 1 Algorithm evaluation index system

其中，相對誤差越小，求解質量越好；搜索效率值越小，算法收斂速度越快；成功率越高，算法可信度越高。依據上述評價指標，可量化評價算法庫中各算法的效能。

3.2 算法池

針對衛星裝配仍主要以手工操作為主、星體多為箱式結構等特點。本文建立了適應衛星裝配特點的4種智能優化算法。規劃人員可根據算法向導的建議選擇相應算法，設置裝配序列優化模型參數和算法參數來完成問題的求解。這當中，由于蟻群算法尋優機制的獨特性，需要建立不同設備之間的裝配關系矩陣。區別于一般的機電產品，衛星各設備之間一般沒有聯接關系。為此，適用于星上設備的裝配關系矩陣可做如下定義。

(6)

式中：Rij=0 是指當設備pi安裝后影響或無法判斷是否影響設備pj的安裝。Rij=1 當指當設備pi安裝后不影響設備pj的安裝。

4 實例與分析

本文以某微小衛星為例對前文所述方法進行了驗證，例子相關信息如圖2所示。

(1)建立集成干涉矩陣I和裝配關系矩陣R

(2) 建立存儲裝配工具的矩陣E(q)，E(q)={1,17,4,2,4,2,8,1,17}。裝配工具總共有5種，信息存儲格式為

T5T4T3T2T1

(3) 建立存儲裝配方式的矩陣B(q)，B(q)={2,3,2,1,1,2,2,1,2}。

本文基于JAVA語言實現了算法庫。利用算法庫來處理該裝配規劃問題，第一步是問題描述：零件數9，裝配關系數8，裝配類型為多軸裝配，尚未獲得可行序列；對算法質量、效率、成功率要求均衡，接受參數較復雜算法；規劃人員經驗均為空，圖3為問題描述界面。第二步是選擇算法：根據描述，算法向導給出的算法建議從高到底依次為遺傳、模擬退火、蟻群、粒子群算法。第三步是設置裝配序列優化模型參數和算法參數，其中ct、cd、cc和cg權重系數分別設置為0.5，0.2，0.3和50。第四步是迭代計算，結果分析、應用。

在算法參數設置上，遺傳算法設置初始種群為200，循環次數200，交叉概率0.8，變異概率0.6，交叉方式為OX算子，變異方式為雙點，個體選擇為指數排序法；蟻群算法設置螞蟻數目為9，循環次數為20，信息素為0.8，信息素的重要性為1，啟發信息的重要性為1，信息素局部和全局揮發率為0.6和0.1，調節常數為2；模擬退火算法設置初始溫度為500，狀態接受函數為概率方式Ⅱ，領域解產生為兩位置點間序列逆序，溫度更新系數為0.95，內循環迭代步數為500，外循環終止溫度為0.001；粒子群算法設置粒子數為500，循環次數為500，速度算子的保留概率c0，c1，c2分別為0.8，0.5，0.5。圖4為粒子群算法參數設置。圖5為利用算法庫中各算法計算出的最優裝配序列。

為了驗證算法向導所給出算法建議的有效性，同時進一步研究各算法的性能，本文對同數據源采用算法庫中4種算法進行了多次運算。圖6為各算法多次運算的裝配成本折線圖(局部)。并根據多次運算結果，計算了表1中算法評級體系中各項指標值，如表2所示。其中，基于智能優化算法求解目標函數的隨機收斂原理，同種算法在多次運算中結果并不完全相同，這也是開展智能優化算法性能評價研究的出發點。

從表2中可以看出，針對該實例，遺傳算法的求解質量最優、搜索效率居上(收斂速度快)、成功率最優，綜合比較，遺傳算法最適合當前實例。其余算法，模擬退火算法求解質量居上，成功率高，但搜索效率一般；蟻群算法求搜索效率居中，成功率高，但求解質量居中；粒子群算法搜索效率居上，但成功率一般。綜合比較，基于對求解質量、效率、成功率要求均衡等描述，算法向導給出的有關適合實例的算法排序是合理的。即算法向導可向規劃人員推薦最優算法，從而便捷獲得多種約束下的最優裝配序列。

此外，依據算法庫計算得出的最優裝配序列，完成了一次實例中星上設備安裝，與之前依靠工藝人員的經驗規劃確定的裝配序列相比，依據最優序列節省了約20%的工時，同時，進一步規范了設備安裝過程中方向、工具、方式等因素的選用，避免了盲目操作和純經驗操作。

算法fafbEm/%Ga/次Ta/sEs/%Rsuc/%Rb_suc/%遺傳算法3.33.301996.13.1100100模擬退火算法3.43.3016623.113.910020蟻群算法3.83.815.2191.89.51000粒子群算法3.53.3049914.62.99040

5 結束語

基于三維模型的數字化制造背景，本文提出的面向星上設備裝配特點的改進型智能優化算法庫，可增強規劃人員便捷獲取最優裝配序列的能力，同時為量化評價各算法的效能提供了同一平臺。隨著研究的深入，可加入更多的算法并將相應效能值存入到算法庫中，不斷拓展算法庫的維度和應用深度，為規劃人員提供更加便捷、可靠的工具。

References)

[1] Homem de Mello L S,Sanderson A C. A correct and complete algorithm for the generation of mechanical assembly sequences [J]. IEEE Transactions on Robotics and Automation,1991,7(2): 228-240

[2]Liu Jihong，Zeng Sen. A survey of assembly planning based on intelligent optimization algorithms[C]//Proceedings of the ASME 2008 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference. New York,USA: ASME,2008

[3]Marian M R,Luong H S L,Abhary K,et al. A genetic algorithm for the optimization of assembly sequences [J]. Computer & Industrial Engineering,2006,50(4): 503-527

[4]鄧明星，唐秋華，雷喆. 基于蟻群算法的改進裝配序列規劃方法[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 (in Chinese)

[5]寧黎華，古天龍. 基于免疫算法的裝配序列規劃問題求解[J].計算機集成制造系統，2007,13(1): 81-87

Ning Lihua,Gu Tianlong. Immune algorithm for assembly sequence planning problem [J]. Computer Integrated Manufacturing Systems,2007,13(1): 81-87 (in Chinese)

[6]陳剛，陸海濱，莊純，等. 基于配合節點序列的航天產品裝配序列規劃[J].機械制造與自動化，2015,(5): 68-70

Chen Gang,Lu Haibin,Zhuang Chun,et al. Assembly sequence planning for aerospace products based on fit nodes sequence [J].Machine Building & Automation,2015 (5): 68-70 (in Chinese)

[7]張晶，崔漢國，朱石堅. 基于人工神經網絡的裝配序列規劃方法研究[J].武漢理工大學學報(交通科學與工程版)，2010,34(5): 1053-1056

Zhang Jing,Cui Hanguo,Zhu Shijian. Study on assembly sequence planning using neural networks [J]. Journal of Wuhan University of Technology (Transportation Science & Engineering),2010,34(5): 1053-1056 (in Chinese)

[8]劉海江，李玲玉，張含葉. 基于改進粒子群算法的鋰電池模塊裝配序列規劃[J].中國工程機械學報，2014,12(4):306-312

Liu Haijiang,Li Lingyu,Zhang Hanye. Assembly sequence planning for lithium-ion battery modules based on improved particle swarm optimization algorithm [J].Chinese Journal of Construction Machinery,2014,12(4):306-312 (in Chinese)

[9]曾冰，李明富，張翼，等. 基于螢火蟲算法的裝配序列規劃研究[J].機械工程學報，2013,49(11): 177-184

Zeng Bing,Li Mingfu,Zhang Yi,et al. Research on assembly sequence planning based on firefly algorithm [J]. Journal of Mechanical Engineering,2013,49(11):177-184 (in Chinese)

[10] 王松，孫振忠，郭建文，等. 基于混合蛙跳算法的復雜產品裝配序列規劃[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 (in Chinese)

[11]王俊峰，李世其，劉繼紅，等. 計算機輔助裝配規劃研究綜述[J].工程圖學學報，2005(2):1-7

Wang Junfeng,Li Shiqi,Liu Jihong,et al. A survey of computer aided assembly planning [J]. Journal of Engineering Graphics,2005(2):1-7 (in Chinese)

(編輯：李多)

Improved Intelligent Optimization Algorithm Library for Assembly Sequence Planning of Satellites

ZENG Sen1LIU Jihong2HAO Jia1

(1 DFH Satellite Co.,Ltd.，Beijing 100094，China) (2 School of Mechanical Engineering and Automation，Beihang University，Beijing 100191，China)

Considering the disadvantages of single algorithm，an approach to resolve assembly sequence planning problem of satellites with improved intelligent optimization algorithm library(IIAL)is proposed．The IIAL is composed of an algorithm advisor and several improved algorithms．The most suitable algorithm will be obtained to assembly planners by the algorithm advisor according to the description of the assembly planning problems. Assembly planners can chose one of then to solve the problem. Finally，an illustrative example is given to verify the rationality of the algorithms suggested by the IIAL．The approach could be useful for equipment assembly sequence planning on the satellite.

satellite integration；assembly sequence planning；intelligent optimization algorithm；algorithms library

2016-08-01；

2016-12-27

曾森，男，碩士，工程師，研究方向衛星數字化總裝，智能優化算法等。Email：dddyx026@163.com。

TP391.7

A

10.3969/j.issn.1673-8748.2017.01.007