求解衛(wèi)星艙布局問題的分治混合算法.pdf

1、布局設(shè)計問題(Packing問題)來源于許多工程應(yīng)用領(lǐng)域，例如工程機械設(shè)計，板材切割排版，建筑空間設(shè)計、電子元器件擺放設(shè)計和衛(wèi)星艙布局設(shè)計等。這些問題的求解目標通常是要求裝填給定物體的容器尺寸盡可能小，或者是在一個給定尺寸的容器內(nèi)放置更多的裝填物，以達到充分利用容器空間的目的。布局問題，尤其是三維布局問題，難以在一個多項式時間內(nèi)求得最優(yōu)解。目前求解布局問題的算法主要包括啟發(fā)式算法、演化算法、協(xié)同算法以及人機交互。啟發(fā)式算法的針對性太強不

2、具有普適性，很難找到具有共性的啟發(fā)式思路。演化算法收斂速度慢，且容易陷入局部最優(yōu)解。協(xié)同算法以及人機交互為求解復雜問題提供了新思路，但要求與其它方法相結(jié)合，才能獲得更好的效果。
　　本文基于三階段分治策略對衛(wèi)星艙布局問題求解。三個階段分別是：(a)問題的解空間分解；(b)子空間(承載面)裝填方案優(yōu)化求解；(c)將最優(yōu)子空間方案合并成整體方案，并對其質(zhì)心偏移量及慣性夾角進行優(yōu)化。本文研究的重點是在(b)和(c)兩階段。對于(b)，將

3、子空間裝填優(yōu)化問題歸結(jié)為圓和矩形混合布局問題，并充分利用本課題組已有的矩形裝填布局成果。對于(c)，通過旋轉(zhuǎn)承載面，采用遺傳算法實現(xiàn)慣量夾角的優(yōu)化。主要內(nèi)容包括：⑴提出圓和矩形混合布局問題的啟發(fā)式蟻群算法。對于圓和矩形混合布局問題，提出區(qū)域定位及向質(zhì)心移動策略的構(gòu)造布局方案，將移動策略進行優(yōu)化調(diào)整，并提出了一種新的啟發(fā)式蟻群算法。待布局物選擇空白區(qū)域放置時，分多步慢慢向質(zhì)心移動，減小移動步長，可能獲得更好的解，通過實驗證明了可能的存在性