求解平衡約束圓集布局問題的啟發(fā)式并行蟻群優(yōu)化方法研究.pdf

1、布局問題(Packing問題),其研究背景包括印刷電路板(PCB)布局方案設(shè)計,航天器艙的布局方案設(shè)計,工廠機(jī)床擺放問題等。求解這些問題不僅要求待布物能放置在盡可能小的空間內(nèi),而且還必須滿足多個約束條件。因此,這些布局問題稱為帶性能約束的布局問題。平衡約束的圓集Packing問題(ECPP問題)是其中最典型的一類。由于它的NP屬性,被國內(nèi)外學(xué)者廣泛研究,并提出了許多有效的算法,例如,啟發(fā)式算法和演化算法(模擬退火、禁忌算法、蟻群算法、粒

2、子群算法和遺傳算法)等。由于啟發(fā)式算法的針對性強(qiáng),演化算法的效率提高遇到干涉量計算的瓶頸問題,故學(xué)者們一直在探索將啟發(fā)式算法與演化算法相結(jié)合的混合算法。本課題組在湖南省自然科學(xué)基金的支持下,以衛(wèi)星艙布局設(shè)計為背景,對ECPP問題的啟發(fā)式算法、階梯式優(yōu)化策略和并行蟻群優(yōu)化進(jìn)行研究,取得了多項研究成果,提高了算法的計算效率、求解精度和穩(wěn)定性。其主要工作如下:
　　(1)針對ECPP問題,提出一種快速啟發(fā)式構(gòu)造的隨機(jī)搜索算法(HRSA)

3、。其可行解的啟發(fā)式構(gòu)造是在輪盤賭選擇的定序概率公式中將半徑和質(zhì)量都作為啟發(fā)信息,以及外圍逆時針排列定位待布圓,其定序定位規(guī)則比徐義春(2007,控制與決策)提出的逐步定序定位算法降低了計算復(fù)雜度,且構(gòu)造的布局方案的外包絡(luò)半徑和靜不平衡量更小。實驗結(jié)果表明:FHRSA比已有隨機(jī)搜索算法提高了計算精度和效率。.
　　(2)針對 ECPP問題,提出一種快速啟發(fā)式蟻群算法(FHACOA)。文中算法充分利用蟻群算法的正反饋原理,將提出的發(fā)式

4、方法與蟻群優(yōu)化相結(jié)合,以避免迭代過程中的干涉量計算,提高ECPP的求解效率和計算精度。實驗結(jié)果驗證了所提出算法的有效性。
　　(3)針對 ECPP問題,提出一種并行階梯式蟻群算法(SPACOA)。文中階梯式蟻群優(yōu)化是將解空間分成若干多子空間,然后依次優(yōu)化每一個子空間的解分量。其子空間的優(yōu)化是在整個解空間上對種群進(jìn)行給定次數(shù)的蟻群迭代,并且已優(yōu)化的子空間分量保持不變。將并行機(jī)制和提出階梯式蟻群優(yōu)化結(jié)合,進(jìn)一步提高平衡約束的圓集Pac