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

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

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

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

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