梁佳成 （1978-）

    男，遼寧工業大學研究生，研究方向為智能控制。
 
    摘要：介紹了采用自適應遺傳算法和改進BP 算法相結合的混合算法來訓練BP網絡的方法，即先用自適應遺傳算法進行全局訓練，再用改進BP 算法進行精確訓練，以達到加快網絡收斂速度和避免陷入局部極小值的目的。結果表明該算法收斂速度快、分類精度較高。

    關鍵詞：改進BP 算法；自適應遺傳算法；混合算法；VRP

    Abstract: In this paper, we introduce a method to train BP network by combing adaptive GA and improved BP algorithm. In order to speed up convergence of BP network and avoid trapping into local minimum, a global training is first done by the use of  adaptiveGA and then a refine training using improved BP algorithm to improve the solution . The result shows t hat this method issuperior to improved BP algorithm in the convergence speed and classification accuracy.

    Key words: improved BP algorithm; adaptive GA; hybrid algorithm; VRP

    1 引言

    全球經濟的一體化使物流配送在供應鏈中的作用顯得尤為重要。在物流配送系統中，配送車輛優化調度是關鍵的一環，也是節省運輸費用和提高經濟效益的重要手段。其中，車輛路徑安排問題(VRP)又成為車輛優化調度的核心問題，由于其應用的廣泛性和在經濟上的重大價值，使得針對路徑優化問題構造性能優良的啟發式算法，成為了一個值得深入研究的課題。同時，遺傳算法(GA)的出現為求解這一類問題提供了新的工具，Berthold、Malmborg等人都曾利用GA 進行過研究，并取得了一些成果，但總體上他們所得出解的質量都不高，這是由GA 本身局部搜索能力不強所致。針對GA 這一缺陷，本文在標準遺傳算法基礎上，將并行進化思想與階段性進化思想相結合，設計了求解VRP 模型的混合遺傳算法，并通過實驗計算證明了該算法具有良好的尋優性能。
 
    2 VRP問題的數學描述

    車輛路徑問題可以表述為：有一個總倉庫(1, 2,...,n)和n個分倉庫第k個倉庫需運輸的貨物量為gk(k=1, 2,...,n)，總倉庫派出多輛貨車，將n個分倉庫的所有貨物運往總倉庫，求滿足貨運需求的最低成本車輛運輸行程路線。

    設總倉庫派出m輛貨車，每輛貨車的載重量為q，且q>gi，Cij表示點i到點j的運輸成本，總倉庫的編號為0，各分倉庫的編號為i(i=1,2,...,k)，另外還有幾個變量定義如下：

    貨車s由i駛向j；點i的貨運任務由s貨車完成

    由這些參數和變量可以求出VRP問題的數學模型表示為：

   （1） 
                       
    另外，還有幾個約束條件如下：

    （1）貨車的容量約束為 

    （2）

    （2）保證每個份倉庫的運輸任務僅由1輛貨車來完成，所有的運輸任務則由m輛貨車協同完成。

    （3）

    （3）到達某一倉庫的貨車有且僅有一輛

    （4）

    （4）離開某一份倉庫的貨車有且僅有一輛

     （5）

    3 BP算法的改進

    BP算法是目前應用最為普遍的一種神經網絡訓練方法。標準BP 算法是一種簡單的快速下降靜態尋優算法。在修正權值時，如果只按照k時刻的負梯度方式進行，而沒有考慮到以前積累的經驗，常常會使學習過程發生振蕩，收斂緩慢。本研究提出了動量法和各層變尺度學習步長相結合的策略，以提高網絡的收斂速度并增強算法的可靠性。該改進算法分以下兩種情況討論權向量的修正。

    1) 若權向量為輸出層的權向量，其調整公式為：

 （6）

    2) 若權向量為隱含層的權向量，其調整公式為：

 （7）

    = 6     （8）

    式中，w(k)和w (k+1) 分別為k及k+1時刻的權向量；是學習步長；D(k) 是k時刻的負梯度；mc是動量因子，由于各層權值的調整都與激勵函數的函數的導數有關，且輸出層權值正比于，隱含層的權值正比于。

    可見，多層權值的修正速率是不同的，離輸出層越遠的權值越難以修正，這是導致BP 網絡訓練速度緩慢的重要原因。因此,增大隱含層的學習步長能有效地提高網絡的訓練速度。同時引入動量因子mc，用來傳遞最后一次權值變化的影響，有助于使網絡從誤差曲面的局部極小值中跳出。

    4 自適應遺傳算法的應用

    4.1 編碼設計

    本文采用實數編碼方案，碼串由BP網絡的學習參數(包括學習步長和動量因子)、各隱含層的節點數和各層的權值三部分組成。對于三層結構的BP 網絡，其輸入層和輸出層的節點個數 m和n由實際問題決定。設其隱含層的節點個數為h，學習步長和動量因子分別為和mc，隱含層和輸出層的權向量分別為w1和w2，那么個體編碼為本實驗采用雙精度數組來表示個體。

    4.2 適應度函數設計

    以訓練集樣本對為網絡的輸入和期望輸出，根據激勵函數  ，即型函數的對數式計算網絡輸出，運行后計算網絡輸出和期望輸出的誤差，取其均方誤差作為目標函數：

  （9）    
                   
    式中,x為種群中的個體；N為網絡輸入樣本個數；M為輸出層節點個數；、分別為第k個樣本輸入時，第j個輸出節點的期望輸出與實際輸出。因目標函數為極小值問題，故將極小值問題轉化為極大值問題,其適應度函數為：
         （10）      
                                     
    4.3 遺傳算子設計

    (1) 選擇。采用最優個體保存法和輪盤賭法相結合的策略。先保留父代個體中適應度最大的個體，直接進入下一代，再利用輪盤賭法對其他個體進行選擇。這樣可以使最優個體不丟失，適應度低的個體也有被選中的可能，保證了個體的多樣性。

    (2) 交叉。具體做法是先使用選擇算子在群體中選擇兩個父體和，根據父體的適應度確定交叉概率。交叉概率的選擇是影響遺傳算法行為和性能的關鍵所在，直接影響算法的收斂性。越大，新個體產生的速度越快，但過大時遺傳模式被破壞的可能性也越大。交叉概率的計算公式如下：

       （11）                 
         （12） 
                                    
    式中，為交叉前父代雙親中適應度大者；和分別為群體最大適應度及平均適應度；=0.9；= 0.3。實驗過程中可根據具體情況調節參數的值。對于兩個父體，采用算術交叉，即

              （13）  
                                     
                （14）
                                   
    式中，和為子代個體；和為父代個體； 為(0,1)之間的實數。

    (3) 變異。變異算子首先用選擇算子選出父個體，根據父個體的適應度確定變異概率：

               （15）

        （16）
                               
    式中,為需變異的個體的適應度；和分別為群體最大適應度及平均適應度；= 0.1，= 0.009，實驗過程中根據具體情況調節這兩個參數的值。對于選定的個體，采用均勻變異的方式進行變異，即在個體中隨機地選擇一個分量用來代替，其后代為，其中， 為(0 ,1)之間的一個隨機數。

    5 混合算法

    在對改進BP算法和自適應遺傳算法分析的基礎上，提出先利用自適應遺傳算法來全局訓練神經元網絡，再用改進BP算法來進行精確求解的混合算法，其算法流程如圖1 所示。其中數據預處理是指把數據規格化在[0. 1 ,0.9]之間，這在一定程度上可以降低求解難度，加快BP 神經網絡的收斂速度。

 圖1   混合算法流程圖

    使用均方誤差函數作為判斷網絡是否達到預定精度的標準。

    6 算法仿真研究

    由于MATLAB 語言的基本數據單元是一個維數不加限制的矩陣，并且系統提供了大量處理矩陣的函數！因此，應用MATLAB語言編制遺傳算法程序用于求解VRP問題時，可以將種群看作一個矩陣來處理，這有助于整體性地考慮和描述計算問題。為研究算法的有效性，安排了如下試驗：

    隨機產生一個總倉庫（代號為0）和24個分倉庫（代號為1-23的位置坐標和各倉庫中需運輸的貨物量如表1 所示，試求運輸車輛的載重量為q=10t時合理的需用車輛臺數和車輛運輸路徑安排。

表1   倉庫位置坐標和貨運量/t

    這里選擇文獻[4]中提出的公式來確定需要參與運輸的車輛臺數。
      
    實驗中遺傳算法參數popsize=50,gen=50 隨機運行標準遺傳算法和帶改進BP-自適應遺傳算子的改進遺傳算法各14次，計算的總運輸距離結果如表2所示。

                                        表2   計算的總運輸距離結果/km
      
    由表2可看到改進算法得到3次最優結果972.47km,(0610182122230122080216119501971003 1341714150)，而標準遺傳算法得到最優運輸距離(路徑)最短為988.96，而且14次運算得到的平均運輸距離和標準差均比改進算法的結果差，由此可知改進后的算法在求解VRP，問題時收斂性好于標準算法。

    7 結論

    從試驗的結果可以看出，基于改進BP-自適應遺傳算法求解VRP問題時，標準遺傳算法不易收斂，得到的解與最優解相比，有比較大的差距，這說明選擇，交叉，變異算子在求解VRP問題時搜索能力較差，將進化算子引入改進標準遺傳算法后，算法的搜尋能力得到了加強，斂性明顯提高，仿真試驗結果表明了改進后算法的可行性和有效性。

    其他作者：王艷秋（1955-），女，教授，博士，碩士研究生導師，研究方向為近代交流調速系統，智能控制；楊克儉（1980- ），男，遼寧工業大學研究生，研究方向為智能控制。
 
    參考文獻

    [1]M ilosavljevic N Teodorovic D. A fuzzy approach to the vehicle assignment problem[J]. Transprotation Planning and Technology ,1997.20(1):33-47.

    [2]Teodorovic D,Pavkovic G.A simulated annealing technique approach to vehicle routing problem in the case of stochastic demand [J].Transportation Planning and Technology, 1995,19(1):19-29.

    [3]袁健,劉晉.隨機需求情況VRP的Hopfield神經網絡界解法[J].南京航空航天大學學報，2000．32（5）：579-584．

    [4]李軍、謝秉磊、郭耀煌.非滿載車輛調度問題的遺傳算法[J].系統工程理論與實踐，2000.20（3）：235-239．
 
    [5]金丕彥,芮勇. BP 算法各種改進算法的研究及應用[J].南京航空航天大學學報, 1994 (26) :201-205.

    [6]王小平,曹立明. 遺傳算法--理論、應用與軟件實現[M].西安:西安交通大學出版社,2002.

    [7]熊忠陽,劉道群,張玉芳. 用改進的遺傳算法訓練神經網絡構造分類器[J]. 計算機應用,2005,25(1):31-34.

    [8]李儀,陳云浩,李京.基于微種群遺傳算法和自適應BP算法的遙感遙感影像分類[J].光學技術,2005 ,31(1):17-20.

    [9]韓敏,程磊,邢軍.基于神經網絡的扎龍濕地覆蓋分類研究[J].大連理工大學學報,2004,44(4):582-588.