日本在线www-日本在线播放一区-日本在线不卡免费视频一区-日本在线不卡视频-成人影院久久久久久影院-成人影院一区二区三区

梁佳成 （1978-）
男，遼寧工業(yè)大學(xué)研究生，研究方向?yàn)橹悄芸刂啤?BR>
摘要：介紹了采用自適應(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é)省運(yùn)輸費(fèi)用和提高經(jīng)濟(jì)效益的重要手段。其中，車輛路徑安排問題(VRP)又成為車輛優(yōu)化調(diào)度的核心問題，由于其應(yīng)用的廣泛性和在經(jīng)濟(jì)上的重大價(jià)值，使得針對路徑優(yōu)化問題構(gòu)造性能優(yōu)良的啟發(fā)式算法，成為了一個(gè)值得深入研究的課題。同時(shí)，遺傳算法(GA)的出現(xiàn)為求解這一類問題提供了新的工具，Berthold、Malmborg等人都曾利用GA 進(jìn)行過研究，并取得了一些成果，但總體上他們所得出解的質(zhì)量都不高，這是由GA 本身局部搜索能力不強(qiáng)所致。針對GA 這一缺陷，本文在標(biāo)準(zhǔn)遺傳算法基礎(chǔ)上，將并行進(jìn)化思想與階段性進(jìn)化思想相結(jié)合，設(shè)計(jì)了求解VRP 模型的混合遺傳算法，并通過實(shí)驗(yàn)計(jì)算證明了該算法具有良好的尋優(yōu)性能。

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

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

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

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

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


    另外，還有幾個(gè)約束條件如下：

    （1）貨車的容量約束為  


    （2）保證每個(gè)份倉庫的運(yùn)輸任務(wù)僅由1輛貨車來完成，所有的運(yùn)輸任務(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)值時(shí)，如果只按照k時(shí)刻的負(fù)梯度方式進(jìn)行，而沒有考慮到以前積累的經(jīng)驗(yàn)，常常會(huì)使學(xué)習(xí)過程發(fā)生振蕩，收斂緩慢。本研究提出了動(dòng)量法和各層變尺度學(xué)習(xí)步長相結(jié)合的策略，以提高網(wǎng)絡(luò)的收斂速度并增強(qiáng)算法的可靠性。該改進(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時(shí)刻的權(quán)向量；是學(xué)習(xí)步長；D(k) 是k時(shí)刻的負(fù)梯度；mc是動(dòng)量因子，由于各層權(quán)值的調(diào)整都與激勵(lì)函數(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)練速度。同時(shí)引入動(dòng)量因子mc，用來傳遞最后一次權(quán)值變化的影響，有助于使網(wǎng)絡(luò)從誤差曲面的局部極小值中跳出。

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

    4.1 編碼設(shè)計(jì)

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

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

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

    

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

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

    (2) 交叉。具體做法是先使用選擇算子在群體中選擇兩個(gè)父體和，根據(jù)父體的適應(yīng)度確定交叉概率。交叉概率的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性。越大，新個(gè)體產(chǎn)生的速度越快，但過大時(shí)遺傳模式被破壞的可能性也越大。交叉概率的計(jì)算公式如下：
    
    式中，為交叉前父代雙親中適應(yīng)度大者；和分別為群體最大適應(yīng)度及平均適應(yīng)度；實(shí)驗(yàn)過程中根據(jù)具體情況調(diào)節(jié)這兩個(gè)參數(shù)的值。對于選定的個(gè)體，采用均勻變異的方式進(jìn)行變異，即在個(gè)體用來代替，其后代為，其中，為(0 ,1)之間的一個(gè)隨機(jī)數(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ù)單元是一個(gè)維數(shù)不加限制的矩陣，并且系統(tǒng)提供了大量處理矩陣的函數(shù)！因此，應(yīng)用MATLAB語言編制遺傳算法程序用于求解VRP問題時(shí)，可以將種群看作一個(gè)矩陣來處理，這有助于整體性地考慮和描述計(jì)算問題。為研究算法的有效性，安排了如下試驗(yàn)：

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

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

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

    

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

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

    7 結(jié)論

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

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

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

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

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

    熊忠陽,劉道群,張玉芳. 用改進(jìn)的遺傳算法訓(xùn)練神經(jīng)網(wǎng)絡(luò)構(gòu)造分類器[J]. 計(jì)算機(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é)報(bào),2004,44(4):582-588