G4算法實(shí)現(xiàn)與布局問(wèn)題的相對(duì)熵算法研究.pdf

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

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

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

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