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

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

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

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

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

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