帶靜不平衡約束的矩形裝填問題的啟發(fā)式算法

　　衛(wèi)星艙布局問題不僅是一個復(fù)雜的耦合系統(tǒng)設(shè)計問題，也是一個特殊的優(yōu)化問題，具有NP難度性。解決這類問題最大的挑戰(zhàn)在于需要優(yōu)化的目標函數(shù)具有大量的被高能勢壘分隔開的局部極小值點。Wang-Landau（WL）抽樣算法是一種改進的蒙特卡羅方法，已經(jīng)被成功地運用蛋白質(zhì)結(jié)構(gòu)預(yù)測等優(yōu)化問題。本文以衛(wèi)星艙布局優(yōu)化問題為背景，首次將WL抽樣算法引入矩形裝填問題的求解。針對矩形裝填物的特點，提出了啟發(fā)式格局更新策略，以引導(dǎo)抽樣算法在解空間中進行有效行走。為了加速搜索全局最優(yōu)解，每次蒙特卡羅掃描生成新的布局時，便執(zhí)行梯度法進行局部搜索。通過將局部搜索機制、啟發(fā)式格局更新策略與WL抽樣算法相結(jié)合，提出了一種用于解決帶靜不平衡約束的任意矩形裝填問題的啟發(fā)式布局算法。在布局優(yōu)化過程中，通過在擠壓彈性勢能的基礎(chǔ)上增加靜不平衡量懲罰項并采用質(zhì)心平移的方法，使布局系統(tǒng)的靜不平衡量達到約束要求。另外，為了改進算法的搜索效率，提出了改進的有限圓族法用于裝填物之間的干涉性判斷和干涉量計算。通過對文獻中兩組共10個有代表性的算例進行實算，計算結(jié)果表明，所提出的裝填算法是一種求解帶靜不平衡性能約束的任意矩形裝填問題的有效算法。