曾森 劉繼紅 郝佳

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

?

衛(wèi)星裝配序列規(guī)劃的智能優(yōu)化算法研究

曾森1劉繼紅2郝佳1

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

結(jié)合單個算法的優(yōu)缺點，文章提出了一種用包含多種改進型智能優(yōu)化算法的算法庫(IIAL)來解決衛(wèi)星裝配序列規(guī)劃問題的方法。算法庫由算法向?qū)Ш投喾N算法組成，算法向?qū)Э梢罁?jù)若干參數(shù)描述給出適合當前規(guī)劃任務(wù)的最合適算法，規(guī)劃人員可依據(jù)向?qū)Ыㄗh在遺傳算法、粒子群算法、蟻群算法、模擬退火算法中選擇相應(yīng)算法進行求解。最后，用實例驗證了方法的合理性。該方法可為星上設(shè)備裝配序列規(guī)劃提供參考。

衛(wèi)星裝配；裝配序列規(guī)劃；智能優(yōu)化算法；算法庫

1 引言

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

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

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

2 衛(wèi)星裝配序列優(yōu)化模型建立

2.1 裝配序列優(yōu)化模型

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

基于上述分析，星上設(shè)備裝配序列優(yōu)化問題的數(shù)學(xué)模型為

(1)

(2)

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

2.2 優(yōu)化模型中相關(guān)參數(shù)的計算

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

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

(2)設(shè)備均安裝在方箱式星體結(jié)構(gòu)板上，星體坐標系為XYZ三軸坐標系，裝配路徑為直線裝配，即裝配方向為±X，±Y，±Z共6個，若設(shè)備安裝方向已裝有結(jié)構(gòu)板，則該方向?qū)υ撛O(shè)備存在干涉。

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

(3)

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

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

(4)

(5)

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

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

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

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

3 算法庫原理及組成

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

算法庫由算法向?qū)Ш退惴ǔ亟M成。算法向?qū)б砸?guī)劃人員對待求解問題的描述為輸入，以算法庫中已總結(jié)的各個算法效能指標歷史經(jīng)驗值為主要量化參考依據(jù)，通過一定加權(quán)計算后，由算法向?qū)Ыo出當前問題的各算法適合值排序，幫助規(guī)劃人員快速選擇算法。算法池中包含裝配規(guī)劃遺傳算法(GA-SAP)、裝配規(guī)劃粒子群算法(PSO-SAP)、裝配規(guī)劃蟻群算法(AC-SAP)和裝配規(guī)劃模擬退火算法(SA-SAP)等4種智能優(yōu)化算法，規(guī)劃人員可基于同一優(yōu)化模型，按照算法向?qū)У慕ㄗh排序采用一種或多種算法進行計算，并將最后結(jié)果反饋到算法庫中。

3.1 算法向?qū)?/p>

3.1.1 問題描述

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

根據(jù)上述輸入，可以大體判定當前問題的特點和規(guī)劃人員對算法的使用需求等信息，支持算法向?qū)Ыo出更合理的算法選擇建議。

3.1.2 算法評價指標

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

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

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

3.2 算法池

針對衛(wèi)星裝配仍主要以手工操作為主、星體多為箱式結(jié)構(gòu)等特點。本文建立了適應(yīng)衛(wèi)星裝配特點的4種智能優(yōu)化算法。規(guī)劃人員可根據(jù)算法向?qū)У慕ㄗh選擇相應(yīng)算法，設(shè)置裝配序列優(yōu)化模型參數(shù)和算法參數(shù)來完成問題的求解。這當中，由于蟻群算法尋優(yōu)機制的獨特性，需要建立不同設(shè)備之間的裝配關(guān)系矩陣。區(qū)別于一般的機電產(chǎn)品，衛(wèi)星各設(shè)備之間一般沒有聯(lián)接關(guān)系。為此，適用于星上設(shè)備的裝配關(guān)系矩陣可做如下定義。

(6)

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

4 實例與分析

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

(1)建立集成干涉矩陣I和裝配關(guān)系矩陣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語言實現(xiàn)了算法庫。利用算法庫來處理該裝配規(guī)劃問題，第一步是問題描述：零件數(shù)9，裝配關(guān)系數(shù)8，裝配類型為多軸裝配，尚未獲得可行序列；對算法質(zhì)量、效率、成功率要求均衡，接受參數(shù)較復(fù)雜算法；規(guī)劃人員經(jīng)驗均為空，圖3為問題描述界面。第二步是選擇算法：根據(jù)描述，算法向?qū)Ыo出的算法建議從高到底依次為遺傳、模擬退火、蟻群、粒子群算法。第三步是設(shè)置裝配序列優(yōu)化模型參數(shù)和算法參數(shù)，其中ct、cd、cc和cg權(quán)重系數(shù)分別設(shè)置為0.5，0.2，0.3和50。第四步是迭代計算，結(jié)果分析、應(yīng)用。

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

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

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

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

算法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 結(jié)束語

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

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]鄧明星，唐秋華，雷喆. 基于蟻群算法的改進裝配序列規(guī)劃方法[J].武漢大學(xué)學(xué)報：工學(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 (in Chinese)

[5]寧黎華，古天龍. 基于免疫算法的裝配序列規(guī)劃問題求解[J].計算機集成制造系統(tǒng)，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]陳剛，陸海濱，莊純，等. 基于配合節(jié)點序列的航天產(chǎn)品裝配序列規(guī)劃[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īng)網(wǎng)絡(luò)的裝配序列規(guī)劃方法研究[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版)，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]劉海江，李玲玉，張含葉. 基于改進粒子群算法的鋰電池模塊裝配序列規(guī)劃[J].中國工程機械學(xué)報，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]曾冰，李明富，張翼，等. 基于螢火蟲算法的裝配序列規(guī)劃研究[J].機械工程學(xué)報，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] 王松，孫振忠，郭建文，等. 基于混合蛙跳算法的復(fù)雜產(chǎn)品裝配序列規(guī)劃[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 (in Chinese)

[11]王俊峰，李世其，劉繼紅，等. 計算機輔助裝配規(guī)劃研究綜述[J].工程圖學(xué)學(xué)報，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

曾森，男，碩士，工程師，研究方向衛(wèi)星數(shù)字化總裝，智能優(yōu)化算法等。Email：dddyx026@163.com。

TP391.7

A

10.3969/j.issn.1673-8748.2017.01.007