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

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

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

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

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