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

0 引 言

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

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

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

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

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

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

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

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

1 網(wǎng)格算法

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

(1) 共享緊缺資源 ；

(2) 平衡計算負(fù)載；

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

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

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

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

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

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

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

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

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

2.1.1 優(yōu)化搜索

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

(1) 首先組成一組候選解 ；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

另一種情況下：

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

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

隨著數(shù)據(jù)規(guī)模的擴大，分類組合優(yōu)化的問題也急劇增大， 目前其他搜索法很難求出最優(yōu)解。對這種復(fù)雜的問題，我們只要能求出最優(yōu)解就可以了，而遺傳算法是尋求這種最優(yōu)解的最佳算法之一。所謂組合優(yōu)化是從有限個可行解中找出使某個目標(biāo)函數(shù)達到最優(yōu)的解的優(yōu)化問題?？煞譃檫B續(xù)優(yōu)化和離散優(yōu)化。而組合優(yōu)化是一種離散最優(yōu)化問題，典型的有旅行商問題、加工調(diào)度問題、背包問題、裝箱問題、類聚問題、車輛路徑問題等。現(xiàn)以裝箱問題作為例子來描述組合優(yōu)化。設(shè)有許多長為 L 的一維箱子及長分別為 ：Wi，i=1，2，…，n 的 n 件物品，且 0<Wi<L，欲把這些物品全部裝入箱中，為了給出它的整數(shù)線性規(guī)劃描述，先引入一些變量：如果第 i 個箱子使用， 則 yi=1，否則 yi=0，第 j 個物品放入第 j 個箱子中 xij=1，否則xij=0。用數(shù)學(xué)方法來描述即：

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

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

集裝箱的裝箱問題實際上是NP 完全問題，求解是十分困難的，而多重網(wǎng)格方法是一種快速計算方法，該方法采用不同尺度的網(wǎng)格，不同疏密的網(wǎng)格消除不同波長的誤差分量， 首先在細(xì)網(wǎng)格上采用迭代法，當(dāng)收斂速度變緩慢時暗示誤差已經(jīng)光滑，則轉(zhuǎn)移到較粗的網(wǎng)格上消除與該層網(wǎng)格上相對應(yīng)的較易消除的那些誤差分量，這樣逐層進行下去直到消除各種誤差分量，再逐層返回到細(xì)網(wǎng)格上。多重網(wǎng)格法是迭代法與

粗網(wǎng)格修正的組合，經(jīng)過證明，迭代法可迅速地將那些高頻 分量去掉，粗網(wǎng)格修正則可以幫助消除那些光滑了的低頻分量， 而對那些高頻分量基本不起作用。如果把集裝箱當(dāng)成一個數(shù) 學(xué)模型，首先可將各參數(shù)變量值的區(qū)間，劃分成一片片的小網(wǎng) 格，由計算機算出各參數(shù)變量值的組合情況，再對所對應(yīng)的 目標(biāo)值進行逐一比較擇優(yōu)，從而得出該區(qū)間的最小目標(biāo)值及對 應(yīng)的最佳參數(shù)值，也就得出了裝箱的全局最優(yōu)解，而 Powell 算法 [10] 具有在局部求解最優(yōu)解的能力，它是一種方向集方法， 專門針對當(dāng)目標(biāo)函數(shù)特別復(fù)雜，沒有辦法掌握目標(biāo)函數(shù)特性的 一類優(yōu)化問題，在集裝箱裝箱過程中，可用多重網(wǎng)格并行優(yōu)化 搜索法來確定裝箱模型中的各個待定參數(shù)，把集裝箱采用均 勻分布點的方法，讓這些點在變量空間中均勻分布，再把這 分布點作為 Powell 算法的初始點，通過 Powell 算法從各初始 點開始對整個集裝箱模型進行優(yōu)化計算，即可得到局部最優(yōu) 點和最優(yōu)值，再取所有局部最優(yōu)值中的最優(yōu)值，就得到了全局 最優(yōu)值，這樣把這種具有全局和局部最優(yōu)解的算法結(jié)合起來， 形成了并行全局最優(yōu)化算法，避免了裝箱中空間浪費、物品歸 類不當(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ī)則的， 這樣計算出來結(jié)果非常接近實際問題，而且可以根據(jù)自己的 意愿建立生成一定的、確定的單元個數(shù)，從而加快后期計算 速度等 ；另外，映射網(wǎng)格技術(shù)可以避免產(chǎn)生一些特別畸形的 單元等，也是映射網(wǎng)格的好處。在集裝箱裝箱物品的過程中， 有不規(guī)則的也有規(guī)則的，或者是兩種混合的，這就需要把這 兩種網(wǎng)格技術(shù)都相互結(jié)合起來，那么就可采用一種網(wǎng)格模型 融合算法 [11-13]，該算法首先將需要的部分網(wǎng)格從源模型上交 互剪切下來，并將其配準(zhǔn)對齊 ；然后將兩網(wǎng)格模型轉(zhuǎn)化成點 模型表示，并將點模型轉(zhuǎn)化成 RBF 隱函數(shù)表示 ；再對兩隱函 數(shù)進行布爾運算 ；最后將布爾運算生的隱函數(shù)曲面在兩網(wǎng)格 接合區(qū)域進行三角形化 ；得到最終的網(wǎng)格模型。這種算法具 有很好的網(wǎng)格融合效果，可用于集裝箱的三維立體構(gòu)造，便 于裝箱人員更好地利用集裝箱空間。

結(jié) 語

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