帶平衡約束圓與矩形Packing問題的啟發(fā)式蟻群算法研究與應(yīng)用.pdf

1、衛(wèi)星艙布局問題指的是衛(wèi)星有效載荷在衛(wèi)星艙體內(nèi)有限空間進(jìn)行合理擺放的組合優(yōu)化問題，是組合數(shù)學(xué)和運(yùn)籌學(xué)等多個學(xué)科的研究熱點。衛(wèi)星艙布局優(yōu)化問題涉及到多學(xué)科、多領(lǐng)域的知識如邏輯推理、計算機(jī)圖形學(xué)、計算幾何學(xué)、運(yùn)籌學(xué)等。衛(wèi)星艙布局問題在有限的時間內(nèi)無法得到其最優(yōu)解，屬于NP難問題的一種。通過簡化其儀器和設(shè)備為圓柱體和長方體并豎直放置在承載板上，衛(wèi)星艙布局設(shè)計問題主要?dú)w結(jié)為如下三類性能約束布局問題。(1)性能約束圓形Packing問題；(2)性能

2、約束矩形Packing問題；(3)性能約束圓與矩形Packing問題。其中，后者的求解較前兩種困難，其求解主要是采用EA、協(xié)同和人機(jī)交互演化算法。它們都需要進(jìn)行干涉量計算，這已成為其求解精度和計算效率提高的瓶頸。因此，本課題組在國家自然科學(xué)基金(61272294)、湖南省自然科學(xué)基金(11JJ6050)以及湖南省教育廳基金(11A120)等的支持下對上述問題展開研究。本文是以衛(wèi)星艙模型布局設(shè)計為背景研究二維慣性約束圓與矩形Packing

3、問題，提出求解性能驅(qū)動的圓與矩形Packing問題的啟發(fā)式蟻群算法，并用簡化國際商業(yè)通信衛(wèi)星艙的布局問題對算法進(jìn)行驗證。具體的工作和創(chuàng)新點如下：
　　1.針對圓與矩形Packing問題，提出了一種定序定位的啟發(fā)式算法。從問題本身的已知信息獲取布局知識，以此建立啟發(fā)式定位和定序規(guī)則。它能快速構(gòu)造出較優(yōu)的可行布局方案。
　　2.針對帶慣性約束的圓與矩形Packing問題，提出一種啟發(fā)式蟻群算法。將啟發(fā)式算法與蟻群優(yōu)化相結(jié)合求得衛(wèi)

4、星艙布局問題中四個承載面上的子布局方案的包絡(luò)半徑以及轉(zhuǎn)動慣量最優(yōu)的的布局方案。實驗表明，啟發(fā)式蟻群算法在求解帶慣性約束的圓與矩形Packing問題時優(yōu)于已有算法。
　　3.針對衛(wèi)星艙模型布局問題，提出一種分治協(xié)同演化算法。先用基于勢能函數(shù)的擬物算法對衛(wèi)星艙模型中四個承載面的包絡(luò)半徑和轉(zhuǎn)動慣量作進(jìn)一步優(yōu)化，再在其不變的基礎(chǔ)上通過粒子群算法優(yōu)化使慣量夾角和質(zhì)心偏移量達(dá)到最小，以獲得最優(yōu)整體布局方案。
　　本文以簡化國際商業(yè)通信衛(wèi)