G4算法實現(xiàn)與布局問題的相對熵算法研究.pdf

1、布局問題是一個經(jīng)典的組合優(yōu)化問題，其現(xiàn)實的實用性和其本身的NP-完全性帶來的巨大挑戰(zhàn)吸引了來自工程、數(shù)學(xué)、計算機科學(xué)等領(lǐng)域的無數(shù)學(xué)者對其進行廣泛而深入的研究。針對不同的具體問題，其求解方法也層出不窮，G4算法就是求解裝盤問題的一個非常高效的算法，所以本文先對該算法進行編程實現(xiàn)，以對其思想進行消化吸收。繼而本文提出并采用交叉熵這種較新的元啟發(fā)式算法來求解2、3維布局問題。本文通過大量的實驗，證明了交叉熵求解布局問題的有效性。 首先

2、，本文總結(jié)歸納了布局問題的分類和國內(nèi)外研究現(xiàn)狀，提出了本課題的研究內(nèi)容。 結(jié)合企業(yè)的需求和G4求解裝盤問題的高效性，本文對其進行了重新編程實現(xiàn)，消化吸收了其思想。因為G4算法的理論基礎(chǔ)是動態(tài)規(guī)劃法，所以本文在介紹G4算法前對動態(tài)規(guī)劃的基本概念、思想、原理進行了簡單介紹。 然后，介紹了熵的起源、發(fā)展和信息熵與交叉熵的數(shù)學(xué)表達。在交叉熵定義的數(shù)學(xué)表達的基礎(chǔ)上，介紹了交叉熵求解小概率事件估計的基本原理。基于優(yōu)化問題出現(xiàn)最優(yōu)解一

3、般情況下概率很小，本文給出將優(yōu)化問題轉(zhuǎn)換為相應(yīng)的小概率估計問題，然后再采用交叉熵算法來求解的基本原理。為了更好地理解算法的本質(zhì)，本文對交叉熵算法與經(jīng)典元啟發(fā)式算法的共同點與相異性進行了總結(jié)與歸納。 然后，在交叉熵求解優(yōu)化問題的理論可行的基礎(chǔ)上提出了采用交叉熵來求解二維布局問題：采用基于概率矩陣的樣本生成方法與DROP和DROPF兩種解碼策略來確定裝箱方案，給出了參數(shù)更新機制和整個算法。并對DROP和DROPF解碼的數(shù)據(jù)結(jié)構(gòu)做了說

4、明，同時給出了DROPF解碼流程圖。在充分的理論基礎(chǔ)之上進行了大量數(shù)值模擬試驗，并將實驗結(jié)果與一些經(jīng)典的元啟發(fā)式算法進行了對比，其實驗效果非常好，驗證了算法的可行性。 繼后試探性地將交叉熵算法應(yīng)用于集裝箱布局優(yōu)化問題中來：采用基于Bernoulli分布的編碼原則和基于空間分解的解碼策略。在對基于Bernoulli分布的編碼原則和空間分解的解碼策略進行詳細說明之后，采用試驗驗證了算法的可行性。 最后對全文進行了總結(jié)，同時展