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

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

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

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

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