張潔

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

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

中圖分類號：TP393.4 文獻標識碼：B 文章編號：2095-1302（2015）03-00-03

0 引 言

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

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

在科學計算領域，網(wǎng)格計算可以在以下幾個方面得到廣泛應用：

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

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

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

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

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

1 網(wǎng)格算法

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

（1）共享緊缺資源；

（2）平衡計算負載；

（3）可以把程序放在最適合運行它的計算機上。

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

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

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

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

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

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

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

2.1 遺傳算法在智能集裝箱中應用

2.1.1 優(yōu)化搜索

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

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

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

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

（4）對保留的候選解進行某些操作，生成新的候選解。

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

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

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

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

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

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

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

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

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

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

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

另一種情況下：

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

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

隨著數(shù)據(jù)規(guī)模的擴大，分類組合優(yōu)化的問題也急劇增大，目前其他搜索法很難求出最優(yōu)解。對這種復雜的問題，我們只要能求出最優(yōu)解就可以了，而遺傳算法是尋求這種最優(yōu)解的最佳算法之一。所謂組合優(yōu)化是從有限個可行解中找出使某個目標函數(shù)達到最優(yōu)的解的優(yōu)化問題?？煞譃檫B續(xù)優(yōu)化和離散優(yōu)化。而組合優(yōu)化是一種離散最優(yōu)化問題，典型的有旅行商問題、加工調(diào)度問題、背包問題、裝箱問題、類聚問題、車輛路徑問題等?，F(xiàn)以裝箱問題作為例子來描述組合優(yōu)化。設有許多長為L的一維箱子及長分別為：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

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

當i=j時，xij=1；

當i≠j時，xij=0；

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

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

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

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

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

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

3 結 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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

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

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