梁佳成 （1978-）
男，遼寧工業(yè)大學(xué)研究生，研究方向為智能控制。

摘要：介紹了采用自適應(yīng)遺傳算法和改進(jìn)BP 算法相結(jié)合的混合算法來訓(xùn)練BP網(wǎng)絡(luò)的方法，
即先用自適應(yīng)遺傳算法進(jìn)行全局訓(xùn)練，再用改進(jìn)BP 算法進(jìn)行精確訓(xùn)練，以達(dá)到加快網(wǎng)絡(luò)
收斂速度和避免陷入局部極小值的目的。結(jié)果表明該算法收斂速度快、分類精度較高。

關(guān)鍵詞：改進(jìn)BP 算法；自適應(yīng)遺傳算法；混合算法；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 引言

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

    2 VRP問題的數(shù)學(xué)描述

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

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

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

    由這些參數(shù)和變量可以求出VRP問題的數(shù)學(xué)模型表示為：


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

    （1）貨車的容量約束為  


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

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

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



    3 BP算法的改進(jìn)

    BP算法是目前應(yīng)用最為普遍的一種神經(jīng)網(wǎng)絡(luò)訓(xùn)練方法。標(biāo)準(zhǔn)BP 算法是一種簡單的快速下降靜態(tài)尋優(yōu)算法。在修正權(quán)值時，如果只按照k時刻的負(fù)梯度方式進(jìn)行，而沒有考慮到以前積累的經(jīng)驗，常常會使學(xué)習(xí)過程發(fā)生振蕩，收斂緩慢。本研究提出了動量法和各層變尺度學(xué)習(xí)步長相結(jié)合的策略，以提高網(wǎng)絡(luò)的收斂速度并增強算法的可靠性。該改進(jìn)算法分以下兩種情況討論權(quán)向量的修正。

    1) 若權(quán)向量為輸出層的權(quán)向量，其調(diào)整公式為：

    2) 若權(quán)向量為隱含層的權(quán)向量，其調(diào)整公式為：


    式中，w(k)和w (k+1) 分別為k及k+1時刻的權(quán)向量；是學(xué)習(xí)步長；D(k) 是k時刻的負(fù)梯度；mc是動量因子，由于各層權(quán)值的調(diào)整都與激勵函數(shù)的函數(shù)的導(dǎo)數(shù)有關(guān)，且輸出層權(quán)值正比于,隱含層的權(quán)值正比于。

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

    4 自適應(yīng)遺傳算法的應(yīng)用

    4.1 編碼設(shè)計

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

    4.2 適應(yīng)度函數(shù)設(shè)計

    以訓(xùn)練集樣本對為網(wǎng)絡(luò)的輸入和期望輸出，根據(jù)激勵函數(shù)，即型函數(shù)的對數(shù)式計算網(wǎng)絡(luò)輸出，運行后計算網(wǎng)絡(luò)輸出和期望輸出的誤差，取其均方誤差作為目標(biāo)函數(shù)：

    

    式中,x為種群中的個體；N為網(wǎng)絡(luò)輸入樣本個數(shù)；M為輸出層節(jié)點個數(shù)；、分別為第k個樣本輸入時，第j個輸出節(jié)點的期望輸出與實際輸出。因目標(biāo)函數(shù)為極小值問題，故將極小值問題轉(zhuǎn)化為極大值問題,其適應(yīng)度函數(shù)為：
    
    4.3 遺傳算子設(shè)計

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

    (2) 交叉。具體做法是先使用選擇算子在群體中選擇兩個父體和，根據(jù)父體的適應(yīng)度確定交叉概率。交叉概率的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性。越大，新個體產(chǎn)生的速度越快，但過大時遺傳模式被破壞的可能性也越大。交叉概率的計算公式如下：
    
    式中，為交叉前父代雙親中適應(yīng)度大者；和分別為群體最大適應(yīng)度及平均適應(yīng)度；實驗過程中根據(jù)具體情況調(diào)節(jié)這兩個參數(shù)的值。對于選定的個體，采用均勻變異的方式進(jìn)行變異，即在個體用來代替，其后代為，其中，為(0 ,1)之間的一個隨機數(shù)。

    5 混合算法

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

    使用均方誤差函數(shù)作為判斷網(wǎng)絡(luò)是否達(dá)到預(yù)定精度的標(biāo)準(zhǔn)。

    6 算法仿真研究

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

    隨機產(chǎn)生一個總倉庫（代號為0）和24個分倉庫（代號為1-23的位置坐標(biāo)和各倉庫中需運輸?shù)呢浳锪咳绫? 所示，試求運輸車輛的載重量為q=10t時合理的需用車輛臺數(shù)和車輛運輸路徑安排。

                                      表1   倉庫位置坐標(biāo)和貨運量/t

    這里選擇文獻(xiàn)[4]中提出的公式來確定需要參與運輸?shù)能囕v臺數(shù)。

    

    實驗中遺傳算法參數(shù)popsize=50,gen=50 隨機運行標(biāo)準(zhǔn)遺傳算法和帶改進(jìn)BP-自適應(yīng)遺傳算子的改進(jìn)遺傳算法各14次，計算的總運輸距離結(jié)果如表2所示。

    由表2可看到改進(jìn)算法得到3次最優(yōu)結(jié)果972.47km,(06101821222301220802161195019710031341714150),而標(biāo)準(zhǔn)遺傳算法得到最優(yōu)運輸距離(路徑)最短為988.96，而且14次運算得到的平均運輸距離和標(biāo)準(zhǔn)差均比改進(jìn)算法的結(jié)果差,由此可知改進(jìn)后的算法在求解VRP, 問題時收斂性好于標(biāo)準(zhǔn)算法.

    7 結(jié)論

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

    其他作者：王艷秋（1955-），女，教授，博士，碩士研究生導(dǎo)師，研究方向：近代交流調(diào)速系統(tǒng)；智能控制。楊克儉（1980- ），男，遼寧工業(yè)大學(xué)研究生，研究方向：智能控制。

    參考文獻(xiàn)：

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

    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

    袁健,劉晉.隨機需求情況VRP的Hopfield神經(jīng)網(wǎng)絡(luò)界解法[J].南京航空航天大學(xué)學(xué)報，2000．32（5）：579-584．

    李軍、謝秉磊、郭耀煌，非滿載車輛調(diào)度問題的遺傳算法[J].系統(tǒng)工程理論與實踐，2000.20（3）：235-239．

    金丕彥,芮勇. BP 算法各種改進(jìn)算法的研究及應(yīng)用[J].南京航空航天大學(xué)學(xué)報, 1994 (26) :201-205.

   
    王小平,曹立明. 遺傳算法--理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.

    熊忠陽,劉道群,張玉芳. 用改進(jìn)的遺傳算法訓(xùn)練神經(jīng)網(wǎng)絡(luò)構(gòu)造分類器[J]. 計算機應(yīng)用,2005,25(1):31-34.

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

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