基于種子優化算法的救災物資調度優化問題的研究

摘要:研究在救災物資調度中，建立物資調度問題的數學模型，運用種子優化算法的思想求解該問題，并進行了實驗計算。計算結果表明，用種子優化算法解決救災物資調度問題，可以方便、快速地求得最優解或近似最優解。

關鍵詞:物資調度;種子優化算法;適應度;父種

中圖分類號:F244.0 文獻標志碼:A文章編號:1673-291X(2010)08-0252-02

1998年，我國南方發生的特大洪澇災害，2003年的“非典”肆虐大半個中國，2006年珍珠、泰利，桑美等臺風輪番席卷我國東南沿海而且重慶地區出現嚴重的干旱和高溫，2008年的四川汶川特大地震災害等，都給我們造成了重大的經濟損失和人員傷亡，也顯示出我國自然災害應急響應能力有待提高。在此背景下，自然災害預警、應急和災后緊急救助已經成為我們關注、研究的重要課題。自然災害發生以后，需要大量的救災物資進行緊急調配，這種應急問題顯著的特點就是時間的緊迫性，其時間效益高于經濟效益。并且在進行物資調度的過程中要盡量做到在限定時間內救災物資供應的同時兼顧費用問題[1]。對于應急物資的調度，許多學者進行了深入的研究，大多采用傳統數學方法或傳統的進化算法去求解。本文則采用種子優化算法的思想解決這種物資調度問題。種子優化算法在尋優結果和收斂速度方面明顯優于基本遺傳算法和粒子群優化算法，更適合進行對于實時性要求高的實際應用[2]。

一、 種子優化算法

1.算法思想

將待優化問題的問題域看作是土地，目標點所在的區域是最肥沃之地，根據目標函數值來確定該區域的肥沃程度，即越是背離最優目標值，其所代表的土地就越貧瘠，否則就越肥沃。一包種子被隨機撒到土地上面，如果種子落到肥沃區域，其成長的概率和繁衍后代的機會就會很大;否則，就很可能被淘汰。經過多代繁衍，最終會有一顆植株生長在最富饒的土地上。經過算法抽象，將演化過程大大壓縮，表現為在某幾個強大植株附近大量涌現后代植株，如此循環往復，因此稱該算法為種子優化算法(Seed Optimization Algorithm，SOA)[3]。

2.算法實現

算法中，種子個體用實值向量X={x1，x2，x3，……，xn}來表示，n的大小由問題本身決定。大量種子組成種子群體，它用sum表示，大小由初始化設定。種子被隨機播撒到問題空間，其中適應度最大的幾個種子稱為父種，根據父種適應度的大小決定其后代的大小和分布情況。后代種子的分布以父種周邊為主，父種的適應度值越大，其后代種子的數量就越多;否則，其后代種子的數量就越少，而且種子的分布更具有隨機性[4]。

后代種子生成后，對所有種子的適應度再進行評價，選擇適應度最優的種子作為父種候選。然后計算候選父種與同代其他父種的歐式距離是否滿足設定的閥值，主要用來保證父種在空間上有較為合理的分布，避免算法過早收斂，提高算法的搜索效率和全局尋優性能.最后決定該種子是否作為本代的父種[5]。根據種子的進化方程，在生成的每個父種的傳播范圍內生成相應的后代種子群體。整個種子群體以此方式循環進化，直到得到理想的優化結果或一號父種(每代中的最優種子)不再變化為止[5]。

二、救災物資調度問題的模型

本文的模型建立在以下假設條件之上:此系統為一次性消耗系統，即指當所有的貨物到達應急地點后才能開始應急活動;運輸過程中沒有意外事件發生，即運輸時間比較準確;應急物資總儲備量充足，不需要額外生產和補給[6]。假設有m個物資儲備點A1，A2，A3，……，Am，n個應急點B1，B2，B3，……，Bn，每個物資儲備點可以提供的物資量依次為G1，G2，G3，……Gm，(Gi>0， i=l，2，……，m)，各應急點所需的物資量依次為D1，D2，D3，……Dn，(Di>0，i=l，2，……，m)。記Gij(i=l，2，……，m;j=1，2，……，n)為應急點Bj，從儲備點Ai實際調度的物資量。物資儲備點Ai達到應急地點Bj的時間為Tij(Tij>0;i=l，2，……，m;j=1，2，……，n)， 物資儲備點Ai達到應急地點Bj的成本為Cij(Cij>0;i=l，2，……，m;j=1，2，……，n)。

fmin=■■xij·Tij·Cij (1)

s.t.■xijGij≤Gij(2)■xijGij=Dj(3)■Dj≤■Gi (4)T≤T0(5)xij={0，1} (6)

從m個物資儲備點向n個應急點調度一種物資，使得時間小于預期T0，并且費用最低。根據題意，可建立上面的數學模型。其中，式(1)為目標函數;式(2)表示從一個儲備點調度的物資數量總和不超過它的庫存量;式(3)表示某個應急點調度的物資總量等于它的需求量;式(4)表示所有應急點所需物資的總量不超過所有儲備庫的庫存量;式(5)表示調度時間不超過要求的時間;式(6)表示當該儲備庫被某個應急點調度的物資大于0時，xij等于1，否則等于0.

三、實例分析

2008年汶川大地震發生后，災區房屋嚴重損壞，導致災區急需大量救災帳篷。假設計劃在30小時內從儲備庫A1，A2，A3，向災區應急點B1，B2分別調撥帳篷5萬頂和8萬頂帳篷[7]。儲備庫A1，A2，A3，庫存帳篷數量及到災區應急點B1，B2的時間和成本見表1，表2.

我們通過計算機模擬，得到這個問題的解x={1，1，1，1，1，0};Gij=(2，2，1，2，6，0);Tij={20，15，25，18，10，0};Cij={20，16，13，24，36，0};i={1，2，3}j={1，2}。所以，得到minT=max {xijTij}=25;minC=■■xijCij=109，fmin=■■xij·Tij·Cij=1757;適應度f=■=■。

本文針對我國長期來自然災害經常發生、應急響應能力有待提高的現狀，研究了自然災害發生后，運用種子優化算法的思想解決救災物資調度的優化問題。在此過程中，我們對這種要求時間最小、成本也最小的多對多物資調度問題建立了數學模型，并運用種子優化算法得到了可行解或滿意解。但是，本文中我們是把這種多對對的問題進行了簡化，我們的下一個研究目標是把諸如調度過程中的車輛路線的選擇等方面考慮進去，以期達到這種復雜對多對多物資調度問題的時間最短、成本最低的目標[8]。

參考文獻:

[1] 林浩，許維勝. 基于離散粒子群算法的應急物資調度系統研究[J].電腦知識與技術，2008，(3):1503-1511.

[2] 張曉明，王儒敬，宋良圖. 一種新的進化算法:種子優化算法:模式識別與人工智能[J].2008，(5):677-681.

[3] 劉靜，鐘偉才，劉芳，焦李成. 組織進化數值優化算法[J].計算機學報， 2004，(2):157-167 .

[4] 徐宗本.模擬進化計算[M].//計算智能:第一冊.北京:高等教育出版社，2004.

[5] Dote Y， Ovaska S J. Industrial applications of soft computing: A review. Proceedings of IEEE，2001，89(9):1243-1265

[6] Meijuan Gao，Jin Xu， Jingwen Tian，Hao Wu. Path Planning for Mobile Robot Based on Chaos Genetic Algorithm. Fourth International Conference on Natural Computation，Volume 4，2008:409-413.

[7] Gondro C.，Kinghorn BP. A simple geneticalgorithm for multiplesequence alignment. Genetics and Molecular Research，2007(6): 964-982.

[8] 張曉明，王儒敬.一種帶逆反的粒子群算法[J].計算機科學，2006，33(10):156-159.