幾種優(yōu)化網(wǎng)格算法在智能集裝箱中的應(yīng)用

張潔

摘 要：目前的集裝箱運(yùn)輸占據(jù)了大部分的運(yùn)輸比例，優(yōu)化智能集裝箱的裝箱問題顯然可以減少成本和提高運(yùn)輸效率，智能集裝箱已成為當(dāng)今運(yùn)輸?shù)陌l(fā)展趨勢(shì)，而網(wǎng)格算法應(yīng)用于智能集裝箱也是科技發(fā)展的結(jié)果，重點(diǎn)闡述了優(yōu)化的遺傳算法和多重網(wǎng)格算法在智能集裝箱中的應(yīng)用，從算法的優(yōu)化搜索出發(fā)，提出了混合遺傳算法和網(wǎng)格模型融合算法，使得集裝箱的裝箱變得更簡(jiǎn)單合理，提高了裝箱率。

關(guān)鍵詞：智能集裝箱；網(wǎng)格算法；遺傳算法；最優(yōu)化

中圖分類號(hào)：TP393.4 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：2095-1302（2015）03-00-03

0 引 言

目前集裝箱這種新型、高效率和高效益的運(yùn)輸方式已廣泛用于國(guó)際貿(mào)易，集裝箱制造是一門融合機(jī)械、冶金、化工、木業(yè)、電子、計(jì)算機(jī)等行業(yè)為一體的綜合性行業(yè)。它是資本密集、管理技術(shù)要求高的產(chǎn)業(yè)。隨著科學(xué)技術(shù)的不斷進(jìn)步，新技術(shù)、新材料在集裝箱行業(yè)的應(yīng)用越來(lái)越廣泛。隨著社會(huì)進(jìn)步，科技的發(fā)展，集裝箱應(yīng)用新技術(shù)、新材料、新工藝、新方法的創(chuàng)新不斷出現(xiàn)。而電子、信息、自動(dòng)識(shí)別等新技術(shù)的成熟和推廣應(yīng)用，又為提高集裝箱運(yùn)輸效率，提供了巨大的空間。業(yè)內(nèi)專家也認(rèn)為智能化、信息化是今后集裝箱業(yè)務(wù)的重點(diǎn)和發(fā)展方向。

智能集裝箱[1]是在一個(gè)集裝箱內(nèi)安裝多臺(tái)服務(wù)器機(jī)架，以提供對(duì)IT設(shè)備的最大支持，同時(shí)包含必要的消防、安防與監(jiān)控設(shè)施，所需動(dòng)力配套設(shè)施在集裝箱外部布署。另外RFID射頻技術(shù)也被應(yīng)用其中，再結(jié)合GPS，能把集裝箱狀態(tài)變化發(fā)生的時(shí)間、地點(diǎn)以及周圍的環(huán)境信息傳遞給管理人員的計(jì)算機(jī)，以實(shí)現(xiàn)集裝箱的實(shí)時(shí)跟蹤和監(jiān)控?，F(xiàn)在的集裝箱都安裝了智能電子標(biāo)簽（包括電子封條和傳感器封條），通過(guò)它可以將集裝箱的一些關(guān)鍵信息傳給TSS系統(tǒng)（Transportation Security System，交通安全信息系統(tǒng)），通過(guò)這些大大地提高了集裝箱的安全性能。那如何來(lái)提高智能集裝箱空間和載重能力呢？集裝箱中貨物多樣化、結(jié)構(gòu)特殊化、運(yùn)載時(shí)間和地點(diǎn)變化大等特征，使得智能集裝箱中必須要有一種超級(jí)處理能力的計(jì)算機(jī)來(lái)幫助其實(shí)現(xiàn)這諸多的性能。但它的造價(jià)極其昂貴，通常只有一些國(guó)家級(jí)的部門，如航天、軍事、氣象等部門才有能力配置這樣的設(shè)備。而隨著人們?cè)谌粘９ぷ饔龅降纳虡I(yè)計(jì)算越來(lái)越復(fù)雜，人們迫切需要數(shù)據(jù)處理能力更強(qiáng)大的計(jì)算機(jī)，而超級(jí)計(jì)算機(jī)的價(jià)格顯然阻止了它進(jìn)入普通人的工作領(lǐng)域。一種造價(jià)低廉而數(shù)據(jù)處理能力超強(qiáng)的計(jì)算模式——Grid Computing（網(wǎng)格計(jì)算）[2，3]滿足了人們的需求。網(wǎng)格也是一種先進(jìn)的計(jì)算基礎(chǔ)設(shè)施（Advanced Computational Infrastructure，ACI），用于研究與工程應(yīng)用相結(jié)合的項(xiàng)目，學(xué)科領(lǐng)域涉及超級(jí)計(jì)算技術(shù)、網(wǎng)絡(luò)技術(shù)、數(shù)據(jù)庫(kù)技術(shù)、中間件技術(shù)、并行算法和各種計(jì)算科學(xué)研究與應(yīng)用技術(shù)，是一個(gè)綜合性的跨學(xué)科高技術(shù)研究課題。

在科學(xué)計(jì)算領(lǐng)域，網(wǎng)格計(jì)算可以在以下幾個(gè)方面得到廣泛應(yīng)用：

（1）分布式超級(jí)計(jì)算。網(wǎng)格計(jì)算可以把分布于不同位置的超級(jí)計(jì)算機(jī)集中起來(lái)，把眾多復(fù)雜的大規(guī)模的問題聯(lián)合解決，并且把許多閑置的計(jì)算機(jī)資源得到了有效的組織，提高了系統(tǒng)資源的利用率，節(jié)省了大量的重復(fù)投資，使用戶的需求能夠得到及時(shí)滿足。

（2）高吞吐率計(jì)算。網(wǎng)格技術(shù)能夠十分有效地提高計(jì)算的吞吐率，它利用CPU的周期竊取技術(shù)，將大量閑置的計(jì)算機(jī)資源集中起來(lái)，提供給對(duì)那些對(duì)時(shí)間分配不是很重要的問題，作為計(jì)算資源的重要來(lái)源。

（3）數(shù)據(jù)緊密型計(jì)算。對(duì)于數(shù)據(jù)緊密型的問題的求解，對(duì)通訊和計(jì)算會(huì)生成很大的需求，一般的算法難以解決，需要網(wǎng)格能力才可以解決。而網(wǎng)格計(jì)算恰好可以在電子學(xué)、生物學(xué)、藥物分子設(shè)計(jì)、計(jì)算力學(xué)、計(jì)算材料、核反應(yīng)、航空航天等眾多的領(lǐng)域得到廣泛的需求。

（4）信息共享的人與人交互。網(wǎng)格技術(shù)突破了人與人之間地理位置的限制，便于科研者之間溝通，從某種程度上可以說(shuō)實(shí)現(xiàn)人與人之間的智慧共享。

（5）更廣泛的資源貿(mào)易。隨著大型機(jī)性能的提高和微機(jī)普及應(yīng)用，計(jì)算機(jī)資源的閑置問題也越來(lái)越明顯，網(wǎng)格技術(shù)能夠有效地組織這些閑置的資源，使得那些有大量計(jì)算需求的用戶能及時(shí)地獲取資源。

1 網(wǎng)格算法

網(wǎng)格計(jì)算實(shí)際上是一種分布式計(jì)算。什么是分布式計(jì)算？所謂分布式計(jì)算是一門計(jì)算機(jī)科學(xué)，它研究如何把一個(gè)需要非常巨大的計(jì)算能力能解決的問題分成許多小的部分，然后把這些部分分配給許多計(jì)算機(jī)分別進(jìn)行處理，最后把這些計(jì)算結(jié)果綜合起來(lái)得到最終的結(jié)果?？偟膩?lái)說(shuō)網(wǎng)格算法比起其它算法具有以下幾個(gè)優(yōu)點(diǎn)：

（1）共享緊缺資源；

（2）平衡計(jì)算負(fù)載；

（3）可以把程序放在最適合運(yùn)行它的計(jì)算機(jī)上。

其中，共享緊缺資源和平衡負(fù)載是計(jì)算機(jī)分布式計(jì)算的核心思想之一。參與這種計(jì)算的不只是一臺(tái)計(jì)算機(jī)，而是一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)，所以這種“螞蟻搬山”的方式具有很強(qiáng)的數(shù)據(jù)處理能力。網(wǎng)格算法的實(shí)質(zhì)就是組合與共享資源并確保系統(tǒng)安全。

2 集裝箱常用的網(wǎng)格算法

（1）遺傳算法[4-6]：是模擬生物進(jìn)化過(guò)程的計(jì)算模型，是自然遺傳學(xué)與計(jì)算機(jī)科學(xué)相互結(jié)合、相互滲透而形成的新的計(jì)算方法。通常用來(lái)生成有用的解決方案來(lái)優(yōu)化和搜索問題。

（2）多重網(wǎng)格算法（Multi Grid）：是一種用于求解方程組的方法，可用于插值、解微分方程等。從專業(yè)角度講多重網(wǎng)格法實(shí)際上是一種多分辨率的算法，由于直接在高分辨率（用于求解的間隔?。┥线M(jìn)行求解時(shí)對(duì)于低頻部分收斂較慢，與間隔的平方成反比。

（3）海量數(shù)據(jù)三角網(wǎng)格算法：以最近鄰域快速搜索邊界點(diǎn)的最近鄰域，以增量算法的邊界環(huán)為基礎(chǔ)向外生成三角形，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)點(diǎn)間合理的三角剖分網(wǎng)格。

（4）矩形網(wǎng)格生成等值線算法：該算法思想是建立矩形網(wǎng)格的關(guān)聯(lián)表，不用找線頭和線尾就可一次追蹤到某一高程的多條等值線。

（5）協(xié)克里金算法（Collocated Cokriging）：適合層位、斷層、網(wǎng)格、XYZ數(shù)據(jù)、層段屬性、鉆井分層。

2.1 遺傳算法在智能集裝箱中應(yīng)用

2.1.1 優(yōu)化搜索

遺傳算法是解決搜索問題的一種通用算法，對(duì)于各種通用問題都可以使用。搜索算法的共同特征為：

（1）首先組成一組候選解；

（2）依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度；

（3）根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解；

（4）對(duì)保留的候選解進(jìn)行某些操作，生成新的候選解。

但是遺傳算法的局部搜索能力較差，導(dǎo)致單純的遺傳算法比較費(fèi)時(shí)，在進(jìn)化后期搜索效率較低。在實(shí)際應(yīng)用中，遺傳算法容易產(chǎn)生早熟收斂的問題，不能很好地解決大規(guī)模計(jì)算量問題?？蓪⒕植克阉髂芰?qiáng)的爬山算法與傳統(tǒng)的遺傳算法相結(jié)合，形成混合遺傳算法來(lái)替代?；旌线z傳算法是一種更全局優(yōu)化的算法，還具有以下幾方面的優(yōu)點(diǎn)：

（1）混合遺傳算法從問題解的串集開始搜索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。

（2）混合遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。

（3）混合遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。此特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。

（4）混合遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)他的搜索方向。

（5）混合遺傳算法對(duì)于各種特殊問題可以提供極大的靈活性來(lái)混合構(gòu)造領(lǐng)域獨(dú)立的啟發(fā)式，從而保證算法的有效性。

（6）混合遺傳算法對(duì)所求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求，由于他的進(jìn)化特性，搜素過(guò)程中不需要問題的內(nèi)在性質(zhì)，對(duì)于任意形式的目標(biāo)函數(shù)和約束，無(wú)論是線性的還是非線性的，離散的還是連續(xù)的都可處理。

（7）進(jìn)化算子的各態(tài)歷經(jīng)性使得遺傳算法能夠非常有效地進(jìn)行概率意義的全局搜素。

混合遺傳算法具有擺脫局部最優(yōu)解的能力，能夠以隨機(jī)搜索技術(shù)從概率的意義上找出目標(biāo)函數(shù)的全局最小點(diǎn)。

2.1.2 函數(shù)優(yōu)化

函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。遺傳算法的適應(yīng)度函數(shù)[7-9]也叫評(píng)價(jià)函數(shù)，是用來(lái)判斷群體中的個(gè)體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來(lái)進(jìn)行評(píng)估的。目標(biāo)函數(shù)是求解的優(yōu)化變量的函數(shù)形式，為了得到好的搜索性能，經(jīng)過(guò)一些變化就可以得到適應(yīng)度函數(shù)，而適應(yīng)度函數(shù)是求解的優(yōu)化變量的一種度量，由于遺傳算法中，適應(yīng)度函數(shù)要比較排序并在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計(jì)要結(jié)合求解問題本身的要求而定。它的設(shè)計(jì)直接影響到遺傳算法的性能。下面來(lái)討論一下改進(jìn)的適應(yīng)度函數(shù)：

另一種情況下：

在理想情況下，設(shè)β=2，α值分別取0.5、1、1.5，就可在a，b值確定的情況下得到3種適應(yīng)度函數(shù)。當(dāng)α=1時(shí)，適應(yīng)度值在（0.5～1）之間是線性的；當(dāng)α=1.5時(shí)，適應(yīng)度值則是相反的情況。

2.1.3 分類組合優(yōu)化

隨著數(shù)據(jù)規(guī)模的擴(kuò)大，分類組合優(yōu)化的問題也急劇增大，目前其他搜索法很難求出最優(yōu)解。對(duì)這種復(fù)雜的問題，我們只要能求出最優(yōu)解就可以了，而遺傳算法是尋求這種最優(yōu)解的最佳算法之一。所謂組合優(yōu)化是從有限個(gè)可行解中找出使某個(gè)目標(biāo)函數(shù)達(dá)到最優(yōu)的解的優(yōu)化問題。可分為連續(xù)優(yōu)化和離散優(yōu)化。而組合優(yōu)化是一種離散最優(yōu)化問題，典型的有旅行商問題、加工調(diào)度問題、背包問題、裝箱問題、類聚問題、車輛路徑問題等?，F(xiàn)以裝箱問題作為例子來(lái)描述組合優(yōu)化。設(shè)有許多長(zhǎng)為L(zhǎng)的一維箱子及長(zhǎng)分別為：Wi，i=1，2，…，n的n件物品，且0

min

s.t ，i=1，2，…，n

j=1，2，…，n

yi=0或者1，i=1，2，…，n

xij=0或者1，i，j=1，2，…，n

那么，此問題的一個(gè)最優(yōu)解：

當(dāng)i=j時(shí)，xij=1；

當(dāng)i≠j時(shí)，xij=0；

根據(jù)yi=wi/L最優(yōu)解值為：

2.2 多重網(wǎng)格算法在智能集裝箱中應(yīng)用

2.2.1 并行全局最優(yōu)化

集裝箱的裝箱問題實(shí)際上是NP完全問題，求解是十分困難的，而多重網(wǎng)格方法是一種快速計(jì)算方法，該方法采用不同尺度的網(wǎng)格，不同疏密的網(wǎng)格消除不同波長(zhǎng)的誤差分量，首先在細(xì)網(wǎng)格上采用迭代法，當(dāng)收斂速度變緩慢時(shí)暗示誤差已經(jīng)光滑，則轉(zhuǎn)移到較粗的網(wǎng)格上消除與該層網(wǎng)格上相對(duì)應(yīng)的較易消除的那些誤差分量，這樣逐層進(jìn)行下去直到消除各種誤差分量，再逐層返回到細(xì)網(wǎng)格上。多重網(wǎng)格法是迭代法與粗網(wǎng)格修正的組合，經(jīng)過(guò)證明，迭代法可迅速地將那些高頻分量去掉，粗網(wǎng)格修正則可以幫助消除那些光滑了的低頻分量，而對(duì)那些高頻分量基本不起作用。如果把集裝箱當(dāng)成一個(gè)數(shù)學(xué)模型，首先可將各參數(shù)變量值的區(qū)間，劃分成一片片的小網(wǎng)格，由計(jì)算機(jī)算出各參數(shù)變量值的組合情況，再對(duì)所對(duì)應(yīng)的目標(biāo)值進(jìn)行逐一比較擇優(yōu)，從而得出該區(qū)間的最小目標(biāo)值及對(duì)應(yīng)的最佳參數(shù)值，也就得出了裝箱的全局最優(yōu)解，而Powell算法[10]具有在局部求解最優(yōu)解的能力，它是一種方向集方法，專門針對(duì)當(dāng)目標(biāo)函數(shù)特別復(fù)雜，沒有辦法掌握目標(biāo)函數(shù)特性的一類優(yōu)化問題，在集裝箱裝箱過(guò)程中，可用多重網(wǎng)格并行優(yōu)化搜索法來(lái)確定裝箱模型中的各個(gè)待定參數(shù)，把集裝箱采用均勻分布點(diǎn)的方法，讓這些點(diǎn)在變量空間中均勻分布，再把這分布點(diǎn)作為Powell算法的初始點(diǎn)，通過(guò)Powell算法從各初始點(diǎn)開始對(duì)整個(gè)集裝箱模型進(jìn)行優(yōu)化計(jì)算，即可得到局部最優(yōu)點(diǎn)和最優(yōu)值，再取所有局部最優(yōu)值中的最優(yōu)值，就得到了全局最優(yōu)值，這樣把這種具有全局和局部最優(yōu)解的算法結(jié)合起來(lái)，形成了并行全局最優(yōu)化算法，避免了裝箱中空間浪費(fèi)、物品歸類不當(dāng)?shù)葐栴}，從而提高集裝箱裝箱率。

2.2.2 網(wǎng)格融合技術(shù)創(chuàng)建三維模型

網(wǎng)格可分為自由網(wǎng)格和映射網(wǎng)格，自由網(wǎng)格適合那些不太規(guī)則的模型；而映射網(wǎng)格就是建立的網(wǎng)格都是比較規(guī)則的，這樣計(jì)算出來(lái)結(jié)果非常接近實(shí)際問題，而且可以根據(jù)自己的意愿建立生成一定的、確定的單元個(gè)數(shù)，從而加快后期計(jì)算速度等；另外，映射網(wǎng)格技術(shù)可以避免產(chǎn)生一些特別畸形的單元等，也是映射網(wǎng)格的好處。在集裝箱裝箱物品的過(guò)程中，有不規(guī)則的也有規(guī)則的，或者是兩種混合的，這就需要把這兩種網(wǎng)格技術(shù)都相互結(jié)合起來(lái)，那么就可采用一種網(wǎng)格模型融合算法[11-13]，該算法首先將需要的部分網(wǎng)格從源模型上交互剪切下來(lái)，并將其配準(zhǔn)對(duì)齊；然后將兩網(wǎng)格模型轉(zhuǎn)化成點(diǎn)模型表示，并將點(diǎn)模型轉(zhuǎn)化成RBF隱函數(shù)表示；再對(duì)兩隱函數(shù)進(jìn)行布爾運(yùn)算；最后將布爾運(yùn)算生的隱函數(shù)曲面在兩網(wǎng)格接合區(qū)域進(jìn)行三角形化；得到最終的網(wǎng)格模型。這種算法具有很好的網(wǎng)格融合效果，可用于集裝箱的三維立體構(gòu)造，便于裝箱人員更好地利用集裝箱空間。

3 結(jié) 語(yǔ)

本文主要從網(wǎng)格算法的優(yōu)化搜索和改進(jìn)函數(shù)出發(fā)，提出的混合遺傳算法，是一種更全局優(yōu)化的算法，在求解適應(yīng)度函數(shù)時(shí)能夠得到更合適的最優(yōu)解，而優(yōu)化的多重網(wǎng)格算法能夠提高全局和局部的最優(yōu)化搜索，使集裝箱變成可視化的三維結(jié)構(gòu)，解決了裝箱的空間浪費(fèi)問題，提高了智能集裝箱的利用率。

參考文獻(xiàn)

[1] 鄧延潔，張成.安全智能集裝箱運(yùn)輸系統(tǒng)的概念及發(fā)展展望[J].武漢理工大學(xué)學(xué)報(bào)，2009（2）：31-32

[2] 黃席樾，向長(zhǎng)城，殷禮勝.現(xiàn)代智能算法理論及應(yīng)用[M].北京：科學(xué)出版社，2009.

[3] 劉群鋒.最優(yōu)化問題的幾種網(wǎng)格型算法[D].長(zhǎng)沙：湖南大學(xué)，2011.

[4] 汪松泉.遺傳算法在組合優(yōu)化中的應(yīng)用研究[D].合肥： 安徽大學(xué)，2010.

[5] 孫小勇.一種改進(jìn)的遺傳優(yōu)化算法[J].信息通信技術(shù)，2008（5）：57-58.

[6] 李建勛，文海玉.一類模擬退火算法與遺傳算法混合優(yōu)化策略[J].黑龍江工程學(xué)院學(xué)報(bào)，2010（2）：69-71.

[7] 周昕，凌興宏.遺傳算法理論及技術(shù)研究綜述[J].計(jì)算機(jī)與信息技術(shù)，2010 （4）：37-39.

[8] 金芬，孫春華，鐘鳴.遺傳算法中適應(yīng)度函數(shù)的改進(jìn)[J].機(jī)械設(shè)計(jì)與制造，2010 （3）： 218-219.

[9] 史峰，王輝，郁磊，等.MATLAB智能算法30個(gè)案例分析[M].北京：北京航空航天大學(xué)出版社，2011.

[10] 汪文英，沈斌， 陸忠華， 等.基于均勻設(shè)計(jì)與Powell算法的全局最優(yōu)化算法及并行實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2007（5）：52.

[11] 李秋云，朱慶保.用于連續(xù)域優(yōu)化的遺傳網(wǎng)格螞蟻融合算法[J].計(jì)算機(jī)工程與應(yīng)用，2011（8）：47.

[12] 王衛(wèi)紅，秦緒佳.一種網(wǎng)格融合算法[J].小型微機(jī)計(jì)算機(jī)系統(tǒng)，2011（6）：1113-1116.

[13] 曹巧玲.基于網(wǎng)格的聚類融合算法的研究[D].鄭州：鄭州大學(xué)，2011.

[14] 馬良，寧愛兵.高級(jí)運(yùn)籌學(xué)[M].北京：機(jī)械工業(yè)出版社，2007.