衛(wèi)星艙布局問題的啟發(fā)式求解與涌現(xiàn)計算.pdf

1、衛(wèi)星艙布局設(shè)計是考慮將有效載荷(儀器、設(shè)備)合理的放置在衛(wèi)星艙內(nèi)，以滿足衛(wèi)星設(shè)計的各種約束要求并優(yōu)化各項性能指標，它屬于帶性能約束的復(fù)雜布局設(shè)計問題。衛(wèi)星艙布局優(yōu)化設(shè)計的質(zhì)量，對于衛(wèi)星設(shè)計周期、成本、性能等方面有著重要影響。在數(shù)學(xué)上，它屬于NP難(non-deterministic polynomial-time hard)的優(yōu)化問題；在工程上，屬于復(fù)雜工程系統(tǒng)設(shè)計問題。
　　目前衛(wèi)星艙布局設(shè)計問題的研究存在的下面兩方面的問題：(

2、1)在求解問題模型上，鑒于問題的復(fù)雜性，以衛(wèi)星艙布局為背景的優(yōu)化模型中考慮的布局圖形主要為簡化了的規(guī)則圖形，對不規(guī)則圖形的研究較少。然而，實際布局設(shè)備不總是規(guī)則圖形，而是不規(guī)則圖形，簡化處理可能會較大影響布局質(zhì)量。(2)在求解算法上，現(xiàn)階段主要為智能算法或啟發(fā)式方法結(jié)合智能算法形成混合算法求解。但智能算法往往為基于中央控制(一個全局評價函數(shù))的概率算法，當求解比較復(fù)雜的布局問題時，這類方法也會產(chǎn)生“早熟“問題。
　　針對上述問題，

3、在數(shù)學(xué)模型方面，本文將衛(wèi)星艙布局問題模型由簡化處理的規(guī)則圖形的布局問題擴展到更為一般的不規(guī)則圖形的布局問題。相對于規(guī)則圖形的布局問題，不規(guī)則圖形的布局問題的求解要復(fù)雜的多。在求解方法方面，本文從啟發(fā)式算法結(jié)合智能算法的混合求解和涌現(xiàn)計算兩方面研究高效求解方法。首先針對不規(guī)則圖形的布局問題特點，設(shè)計一些啟發(fā)式求解算法，結(jié)合智能算法形成混合求解算法，并利用數(shù)值實驗驗證算法的有效性。隨著研究問題的逐漸深入，基于中央控制的智能算法在求解較復(fù)雜的

4、布局問題時，也容易產(chǎn)生早熟問題，影響求解質(zhì)量。為了進一步提高求解質(zhì)量，本文將系統(tǒng)科學(xué)中的自組織涌現(xiàn)思想引入復(fù)雜布局問題求解當中，針對二維不規(guī)則圖形布局問題和三維帶多約束的復(fù)雜布局問題，分別設(shè)計涌現(xiàn)計算方法和多階段自組織協(xié)同涌現(xiàn)方法。論文主要研究工作如下：
　　(1)考慮二維帶靜平衡約束的矩形集在圓容器內(nèi)的衛(wèi)星艙布局問題，圍繞其靜平衡約束和矩形布局的特點，提出了一種啟發(fā)式算法——動態(tài)匹配算法，進而將其與壓縮策略和粒子群算法結(jié)合起來，

5、形成混合算法加以求解，為進一步求解不規(guī)則圖形布局問題提供參考。
　　(2)針對帶靜平衡約束的凸多邊形衛(wèi)星艙布局問題，設(shè)計了一種能兼顧靜平衡和緊湊性優(yōu)化的波紋探測啟發(fā)式定位算法，在此基礎(chǔ)上，利用廣義模擬退火算法優(yōu)化布局順序，形成混合算法。
　　(3)在對凸多邊形布局問題研究的基礎(chǔ)上，討論了更為一般的不規(guī)則多邊形布局問題，并同時考慮靜平衡約束、轉(zhuǎn)動慣量和包絡(luò)半徑的優(yōu)化。首先構(gòu)造了一種具有較低計算復(fù)雜度的離散重心臨界多邊形模型，進

6、而設(shè)計了的波紋探測啟發(fā)式算法；同時提出了一種自適應(yīng)選擇機制的改進蜂群算法，利用改進的蜂群算法優(yōu)化波紋探測啟發(fā)式放置算法中排序函數(shù)的參數(shù)，形成不規(guī)則多邊形布局問題的混合求解方法。
　　(4)為了進一步提高二維衛(wèi)星艙多邊形布局問題求解質(zhì)量，將自組織涌現(xiàn)思想引入布局求解中。通過將該布局問題映射到一個類似物理系統(tǒng)的多智能體系統(tǒng)，提出了一種基于多智能體系統(tǒng)的自組織涌現(xiàn)方法。根據(jù)衛(wèi)星艙布局特點，自組織涌現(xiàn)方法將整個布局系統(tǒng)分為三層結(jié)構(gòu)：分離層

7、、交換層和調(diào)整層。不同層中具有不同的鄰域結(jié)構(gòu)和交互規(guī)則。在每一層中，根據(jù)該層的智能體的局部信息和鄰域規(guī)則指導(dǎo)智能體之間以及智能體與環(huán)境之間的交互，系統(tǒng)涌現(xiàn)出具有一定特征的布局解。同時，通過層與層之間的交互，系統(tǒng)在微觀層面上自組織進化并最終產(chǎn)生一個滿足衛(wèi)星艙性能約束的布局解。計算實驗顯示自組織涌現(xiàn)方法優(yōu)化性能優(yōu)于其他的一些優(yōu)化技術(shù)，例如廣義模擬退火算法。
　　(5)最后研究了更為復(fù)雜的三維衛(wèi)星艙布局設(shè)計問題(three-dimens

8、ional satellite module layout design problem, TSMLDP)，TSMLDP是一個多約束耦合問題，其解空間是一個非連續(xù)、非線性、多模態(tài)的，這個性質(zhì)導(dǎo)致現(xiàn)在主要的求解方法——基于概率搜索的智能算法容易陷入早熟問題。為了解決這一問題，提出了基于多智能體系統(tǒng)的多階段協(xié)同進化涌現(xiàn)算法(multi-stage co-evolution emergent algorithm, SCEA)。SCEA將系統(tǒng)分

9、解策略和多階段優(yōu)化策略與自組織協(xié)同進化技術(shù)結(jié)合起來求解TSMLDP。與基于中央控制的進化算法不同，SCEA通過系統(tǒng)自組織進化來搜索滿意解，其不僅利用全局評價函數(shù)信息，還利用智能體的局部信息。TSMLDP的計算實驗結(jié)果顯示，SCEA在解的質(zhì)量和效率上均優(yōu)于其他的進化算法。
　　上述研究中，(1)-(3)屬于啟發(fā)式算法結(jié)合智能算法的求解方法，(4)-(5)屬于自組織涌現(xiàn)計算的求解方法。前者在局部范圍內(nèi)為后者提供實現(xiàn)基礎(chǔ)，后者則是在整體