帶權(quán)重圓形布局問題的智能優(yōu)化算法研究.pdf

1、本文以超大規(guī)模集成電路板(VLSI)的布局設(shè)計和工廠機(jī)械設(shè)備擺放為工程應(yīng)用背景，深入研究一類具備NP難度的帶權(quán)重圓形布局(WCP)問題。WCP問題要求最終的合法解滿足:1）待布物之間的權(quán)重距離之和盡可能小;2）能容納所有待布物的外包絡(luò)容器的面積盡可能小，并同時滿足待布物之間不嵌入約束。本文采用線性加權(quán)法和多目標(biāo)方法分別求解WCP問題。主要研究內(nèi)容及成果如下:
　　(1)研究了WCP問題的單目標(biāo)求解算法，提出了一種基于二分策略的粗精

2、調(diào)啟發(fā)式擬物算法(HQPA-CFDM)。首先基于線性加權(quán)法，將帶約束的WCP問題轉(zhuǎn)化為無約束優(yōu)化問題，并建立相應(yīng)的數(shù)學(xué)模型。然后從任意一個初始構(gòu)形出發(fā)，采用二分法逐步構(gòu)造外包絡(luò)容器，并采用擬物算法逐步優(yōu)化當(dāng)前構(gòu)形下總的擠壓彈性勢能。為了快速找到問題的合法解，受工業(yè)制造中粗精控制過程的啟發(fā)，將擬物算法分解為兩個過程:粗調(diào)過程和精調(diào)過程。在擬物算法中，提出了一種彈性系數(shù)可變的策略。另外，為了避免算法陷入局部極小點(diǎn)，提出了一種啟發(fā)式跳坑策略。

3、通過對當(dāng)前國際上3個典型算例進(jìn)行計算，數(shù)值實(shí)驗(yàn)結(jié)果表明，算法HQPA-CFDM刷新了所有算例的最好結(jié)果。對計算結(jié)果進(jìn)行統(tǒng)計分析，進(jìn)一步驗(yàn)證了算法HQPA-CFDM的有效性和穩(wěn)定性。
　　(2)研究了WCP問題的多目標(biāo)方法，提出了一種多目標(biāo)構(gòu)形空間進(jìn)化算法(MOCSEA)。首先依據(jù)擬物思想和罰函數(shù)法，將帶約束的WCP問題轉(zhuǎn)化為無約束的多目標(biāo)優(yōu)化問題，并建立相應(yīng)的數(shù)學(xué)模型。然后隨機(jī)產(chǎn)生初始構(gòu)形庫（種群），并采用帶提前結(jié)束策略的自適應(yīng)步

4、長梯度法(GD)對初始構(gòu)形庫中的構(gòu)形（個體）進(jìn)行合法化操作;然后對初始構(gòu)形庫執(zhí)行進(jìn)化操作（包括選擇、交叉和變異，其中選擇操作采用精英策略，交叉操作采用單點(diǎn)交叉和多點(diǎn)交叉相結(jié)合的方式，變異操作采用啟發(fā)式變異策略），產(chǎn)生進(jìn)化構(gòu)形庫，并運(yùn)用GD進(jìn)行合法化操作。另外，提出了一種最優(yōu)個體選取方法和一種構(gòu)形更新機(jī)制，結(jié)合快速非支配排序法，從進(jìn)化構(gòu)形庫中挑選若干優(yōu)良個體，并對構(gòu)形庫進(jìn)行更新。經(jīng)多次更新構(gòu)形庫，最后得到一組Pareto最優(yōu)解。通過對當(dāng)前