幾種優化網格算法在智能集裝箱中的應用

張潔

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

關鍵詞：智能集裝箱；網格算法；遺傳算法；最優化

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

0 引 言

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

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

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

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

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

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

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

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

1 網格算法

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

（1）共享緊缺資源；

（2）平衡計算負載；

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

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

2 集裝箱常用的網格算法

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

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

（3）海量數據三角網格算法：以最近鄰域快速搜索邊界點的最近鄰域，以增量算法的邊界環為基礎向外生成三角形，實現點云數據點間合理的三角剖分網格。

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

（5）協克里金算法（Collocated Cokriging）：適合層位、斷層、網格、XYZ數據、層段屬性、鉆井分層。

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

2.1.1 優化搜索

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.2 函數優化

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

另一種情況下：

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

2.1.3 分類組合優化

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

那么，此問題的一個最優解：

當i=j時，xij=1；

當i≠j時，xij=0；

根據yi=wi/L最優解值為：

2.2 多重網格算法在智能集裝箱中應用

2.2.1 并行全局最優化

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

2.2.2 網格融合技術創建三維模型

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

3 結 語

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

參考文獻

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

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

[3] 劉群鋒.最優化問題的幾種網格型算法[D].長沙：湖南大學，2011.

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

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

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

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

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

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

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

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

[12] 王衛紅，秦緒佳.一種網格融合算法[J].小型微機計算機系統，2011（6）：1113-1116.

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

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