基于交叉熵方法的布局問題求解算法研究.pdf

1、布局問題是一種經(jīng)典的組合優(yōu)化問題，在求解復(fù)雜性上具有NP完全性。布局問題不僅在實際工程中具有廣泛的應(yīng)用，而且在理論研究上一直是數(shù)學(xué)家和計算機算法研究學(xué)者的研究熱門問題。長期以來，關(guān)于求解布局問題的算法不斷翻新，分類也相當(dāng)詳細(xì)。交叉熵方法是近幾年來創(chuàng)立并發(fā)展起來的一種新的優(yōu)化方法，在許多組合優(yōu)化領(lǐng)域已經(jīng)取得了很好的效果。本文在理解交叉熵方法的基本思想的基礎(chǔ)上，實現(xiàn)交叉熵方法若干布局問題求解中的應(yīng)用，并用數(shù)值實驗驗證交叉熵方法求解布局問題的

2、有效性。 首先對國內(nèi)外關(guān)于布局問題建模及求解算法的研究現(xiàn)狀進(jìn)行了細(xì)致的了解，分析了P、NP、NPH和NPC問題之間的關(guān)系，并探討優(yōu)化問題最優(yōu)解及優(yōu)化方法所具有的統(tǒng)計性，從而引出本課題的研究內(nèi)容。 接著從信息熵的概念談起，通過對小概率事件仿真方法的分析，引出交叉熵優(yōu)化方法的思想。作者概括性地闡述了交叉熵方法的基本理論，探討了交叉熵方法的全局優(yōu)化意義。并且從優(yōu)化思想和過程等方面將交叉熵方法和遺傳算法、蟻群算法和模擬退火算法進(jìn)

3、行了比較，分析它們之間主要的不同點與相同點。 隨后是本文的主要工作和貢獻(xiàn)，具體給出了交叉熵方法求解部分布局問題的求解算法：(1)采用佰努利分布和樣本修正策略給出了0-1背包問題的裝填方案和相應(yīng)的求解算法；(2)用BL裝箱策略和基于序列及概率矩陣的樣本生成方法來確定裝箱方案，給出了參數(shù)更新機制；(3)用基于退化的二元組方法和相應(yīng)的解碼策略來生成聚塊解方案，并設(shè)計概率矩陣更新策略，進(jìn)而給出完整的求解算法。并對涉及的主要數(shù)據(jù)結(jié)構(gòu)和偽代

4、碼做了說明。 然后通過不同的應(yīng)用實例驗證本文設(shè)計的算法。主要是采用目前研究文獻(xiàn)中的具體算例，并將求解結(jié)果與文獻(xiàn)所給最優(yōu)解相比較，說明本文所提出算法的有效性。 最后，作者對全文的工作進(jìn)行了總結(jié)，并展望了下一步可能進(jìn)行的研究工作的內(nèi)容。 本文首次采用交叉熵方法來求解布局問題，數(shù)值實驗結(jié)果表明，求解質(zhì)量不低于目前一些流行的元啟發(fā)式方法，而且基于交叉熵的算法具有很好的穩(wěn)定性。算例及結(jié)果真實可靠，而且具有可重復(fù)性，可以供以