求解帶性能約束圓集布局問題的啟發(fā)式蟻群算法研究.pdf

1、帶性能約束復(fù)雜布局問題,如印刷電路板(PCB)和航天器艙的布局方案設(shè)計及工廠機(jī)床設(shè)備布置問題等,屬于NP-Complete問題,求解困難。在求解這些問題時,除了要求滿足待布物間不干涉,盡量提高空間利用率之外,還要考慮各種性能約束,如不平衡性、穩(wěn)定性、振動、連通性和相鄰性等。因此,這類問題被稱為帶性能約束的布局問題。許多學(xué)者進(jìn)行了大量的研究,提出的已有算法,如啟發(fā)式算法、演化算法、人機(jī)交互算法、圖論法等,都只能求出其工程滿意解。隨著近幾十

2、年來工業(yè)、交通、國防等方面高技術(shù)的發(fā)展,一些亟待解決的帶復(fù)雜性能約束的布局優(yōu)化(如大規(guī)模集成電路的布局設(shè)計)問題希望具有更高的求解精度和效率。為此,本文研究:(1)從布局問題的已知信息獲取布局知識;(2)將獲取的布局知識用于構(gòu)造布局方案的啟發(fā)式策略;(3)將啟發(fā)式策略和蟻群算法相結(jié)合的混合布局算法。本文將提出的演化布局算法用于求解2-D帶性能的加權(quán)圓集布局問題和帶平衡約束的圓形布局問題,以提高其求解精度和效率。本文主要工作如下:

3、　　1.本文提出求解圓集布局問題的啟發(fā)式蟻群算法(Heuristic Ant colony Approach,HACA)。從加權(quán)矩陣信息獲取布局知識,用于定義待布圓的選擇概率,是該算法構(gòu)造布局方案的定序機(jī)理。通過篩選已布的相切圓位置作為下一個待布圓的侯選位置,以減少確定其最優(yōu)位置的計算量,是該算法構(gòu)造布局方案的定位規(guī)則思想。本文算法的啟發(fā)式策略是由定序機(jī)理和定位規(guī)則構(gòu)成,用于構(gòu)造較優(yōu)的蟻群個體的布局方案。在求解加權(quán)圓集布局問題時,本文的

4、啟發(fā)式蟻群算法是通過將定序機(jī)理和定位規(guī)則組成的啟發(fā)式策略和蟻群算法相結(jié)合;在求解平衡約束布局問題時,則是將改進(jìn)的定位規(guī)則和蟻群算法相結(jié)合。數(shù)值實驗表明:與已有的算法相比,該算法能得到較好的求解效率和精度。
　　2.本文在啟發(fā)式蟻群算法基礎(chǔ)上,提出一種基于非同構(gòu)布局模式的改進(jìn)啟發(fā)式蟻群圓集布局算法(A Improved Heuristic Ant Colony Approach,IHACA)。該算法在每次迭代過程中先由啟發(fā)式策略構(gòu)造

5、下一代的部分蟻群個體的布局方案,再通過構(gòu)造已生成蟻群個體布局方案的非同構(gòu)布局模式,快速產(chǎn)生另一部分蟻群個體的布局方案,這兩部分個體合在一起構(gòu)成蟻群算法的種群。數(shù)值實驗驗證表明:文中算法求解加權(quán)圓集布局問題提高了求解效率和精度,求解帶平衡約束布局問題時提高了求解效率且求解精度不降低。
　　本文以衛(wèi)星艙和電子線路布局問題為背景,研究了帶約束的圓集布局問題。利用布局問題中的布局知識和非同構(gòu)布局模式,探索出啟發(fā)式策略與蟻群算法相結(jié)合的圓集