改進的遺傳神經(jīng)網(wǎng)絡優(yōu)化選址方法

李景文,俞 娜,姜建武+,李 旭

(1.桂林理工大學 廣西空間信息與測繪重點實驗室，廣西 桂林 541006；2.桂林理工大學 測繪地理信息學院，廣西 桂林 541006)

0 引 言

選址問題是地理信息資源優(yōu)化配置的重要研究領域之一[1]，如何有效、科學合理選出最優(yōu)方案是選址工作的難點問題。近年來，國內(nèi)研究學者通過采用不同的算法來研究優(yōu)化選址問題，生力軍[2]通過將量子理論融入粒子群算法中，提高了最優(yōu)選址的尋優(yōu)能力和效率能力；王志剛等[3]采用人工蜂群算法對配送中心最優(yōu)化方案進行求解；袁群等[4]將遺傳算法、禁忌搜索算法和貪婪算法相結合得到混合遺傳算法，通過實驗對比分析驗證了該混合算法模型的有效性。目前在選址方法中利用遺傳算法和神經(jīng)網(wǎng)絡對選址都具有很好的優(yōu)化效果，但是這些算法存在易于過早局部收斂的缺點[5]，影響了選址的優(yōu)化精度。因此本文在GA-BP(genetic algorithm and back propagation)算法基礎上探索利用模糊C均值聚類算法改進遺傳神經(jīng)網(wǎng)絡模型，以達到選址最優(yōu)化狀態(tài)。首先通過影響因子權重值確定方法建立選址中心決策矩陣，確定影響因子及其取值范圍，利用變異系數(shù)法計算得到影響因子的權重，然后通過模糊C均值聚類算法對影響因子的輸入數(shù)據(jù)進行優(yōu)化定性篩選，然后對符合相應指標的要素進行歸一化處理，再利用遺傳算法對神經(jīng)網(wǎng)絡算法的權重和閾值進行優(yōu)化，解決了收斂速度緩慢的問題，為得到優(yōu)化的選址方案提供了一種方法。

1 GA-BP算法

GA-BP算法是對神經(jīng)網(wǎng)絡的參數(shù)進行編碼，按照誤差平方和最小的原則和“適者生存，優(yōu)勝劣汰”的進化理論，用優(yōu)化的參數(shù)訓練網(wǎng)絡[6]。該算法具有較高的預測精度[7]，利用GA來優(yōu)化BP神經(jīng)網(wǎng)絡初始權重和閾值，提高BP神經(jīng)網(wǎng)絡的收斂速度，減少BP算法陷入局部最優(yōu)的可能性[8]。GA-BP算法的具體步驟如下：

(1)首先確定神經(jīng)網(wǎng)絡的相應結構；依據(jù)該網(wǎng)絡結構，確定其閾值、權值并對確定的該閾值權值等待求參數(shù)進行編碼；

(2)對種群進行初始化處理的同時，對訓練的樣本進行歸一化處理，將處理過后的數(shù)據(jù)送入神經(jīng)網(wǎng)絡中；

(3)其次利用BP神經(jīng)網(wǎng)絡計算誤差，采用該誤差做適應度函數(shù)，進而得到所有個體的適應度值；

(4)然后通過選擇操作、交叉操作和變異操作得到下一代種群；

(5)尋找(3)式得到的適應度值，在滿足遺傳終止限定條件的情況下尋找得到最佳個體；

(6)對最佳個體進行解碼，分別賦值于神經(jīng)網(wǎng)絡的權值和閾值；

(7)最后對BP神經(jīng)網(wǎng)絡進行再次訓練，當滿足終止條件時，保留其結構并預測輸出。

GA遺傳算法能夠利用其全局最優(yōu)的特點，幫助BP算法解決局部優(yōu)化等缺陷，能夠將全局最優(yōu)和局部最優(yōu)有機結合，互為補償，達到良好的優(yōu)化效果，得出了最優(yōu)的權值和閾值[9]。但該算法存在缺少考慮影響因子權重的問題以及算法在求解時易與過早收斂的缺陷，因此本文在GA-BP算法基礎上提出了利用模糊C均值聚類算法改進遺傳神經(jīng)網(wǎng)絡模型的優(yōu)化選址方法。

2 C-GA-BP算法描述

C-GA-BP(fuzzy C-means and genetic algorithm and back propagation)算法是通過影響因子權重值確定，建立了選址中心決策矩陣，確定了影響因子及其取值范圍，利用變異系數(shù)法得到了影響因子的權重值，并且對輸入數(shù)據(jù)的篩選過濾與歸一化處理，限定了輸入數(shù)據(jù)的范圍，簡化了數(shù)據(jù)的處理，依據(jù)輸入數(shù)據(jù)的范圍限定輸入數(shù)據(jù)，提高了輸入數(shù)據(jù)的精度，降低了迭代次數(shù)，提高了效率。

2.1 C-GA-BP算法流程

C-GA-BP算法思想是在建立選址中心決策矩陣的基礎上確定相應影響因子及其取值范圍，利用變異系數(shù)法計算求得影響因子的權重值，然后通過模糊C均值聚類分析算法對輸入數(shù)據(jù)進行定性篩選和歸一化處理，減少數(shù)據(jù)量，提高計算速度。具體算法流程如圖1所示。

圖1 C-GA-BP算法流程

2.2 影響因子權重值確定方法

為了更好分析影響因子對優(yōu)化選址方法的影響，根據(jù)可拓原理，選取影響選址的主要影響因子組成影響因子集合，建立選址中心決策矩陣，然后利用變異系數(shù)法對這些影響因子進行分析，確定影響因子權重值

(1)

(2)

式(1)中，R0表示同意方案的決策矩陣，Q0表示滿意方案，xi表示選址方案中的決策影響因子，xoj表示決策矩陣的影響因子xi的取值區(qū)間。式(2)中，Rj表示待選方案的決策矩陣，Qj表示第j個候選方案，xji為第j個候選方案對應于影響因子xi的量值。

通過上述選址中心決策矩陣的建立和對影響因子的分析，再利用變異系數(shù)法來計算求得各個影響因子的權重。具體操作步驟如下：

(1)計算第i項的影響因子的均方差

(3)

(4)

(2)計算求得第i項影響因子的變異系數(shù)

(5)

(3)通過變異系數(shù)來計算得到第i項影響因子的權重

(6)

則各因子的權重為

通過計算影響因子權重值，克服主觀人為決策因素和客觀地理因素的對選址方案的影響，可以更加精確得到最理想的選址方案。

2.3 C-GA-BP計算過程

(1)首先確定選址方案，利用影響因子權重值確定方法建立選址中心決策矩陣，確定影響選址的因子及其相應的取值范圍，然后利用變異系數(shù)法求得出各個影響因子之間的權重值，根據(jù)權重對輸入數(shù)據(jù)進行歸一化處理，歸一化處理公式如下

(7)

式中：xmax為該指標樣本數(shù)據(jù)中的最大值，xmin為該指標樣本數(shù)據(jù)中的最小值，x為該樣本指標數(shù)據(jù)，x*為歸一化處理后的數(shù)值，μ為影響因子的權重值。

(2)依據(jù)選址對象確定模糊C均值聚類模型，分類數(shù)c，加權參數(shù)z和初始隸屬度矩陣U。

(3)根據(jù)模糊C均值模型，目標化下式目標函數(shù)

(8)

式中：dik表示為各個對象到聚類中心的距離值，m表示對象維度，U表示聚類矩陣，其距離計算公式如下

(9)

根據(jù)數(shù)值解的集合，計算每個解與最優(yōu)解之間的相應距離，并將距離值最高的k個值用作下一步的輸入值[10]。距離值計算公式如下

(10)

式中：Ri表示每個解i與最優(yōu)解之間的距離值，Xij是每個值之間i的各個因子取值，XIL為合格值。

(4)初始化目標的聚類矩U

(11)

(5)計算求得目標對象的聚類中心V,集群中心采用下式可獲得

(12)

其中，n表示未分類對象個數(shù)，uik表示第k個元素在第i類的相關隸屬度，z表示加權參數(shù)。

(7)隨機產(chǎn)生初始權重種群p，種群中的每一條染色體由權重向量和閾值向量所組成，表示為W=(w1i,w2i,…,wui,b1i,b2i,…,bvi), 其中 (i=1，2，…，N, 其中N為種群大小),u為神經(jīng)網(wǎng)絡結構中權重總數(shù)，v為神經(jīng)網(wǎng)絡中隱含層和輸出層總閾值。

3 仿真實驗及結果

3.1 實驗分析

為了驗證本文提出的C-GA-BP算法在優(yōu)化選址方面的有效性，選取黑龍江省物流公司的選址需求進行仿真實驗。擬在該省22個市轄區(qū)中，建設3個物流公司以滿足各個市轄區(qū)對物流的需求。物流公司的建設既要滿足建設成本最低，也要滿足實際的物流需求。市轄區(qū)坐標以及市轄區(qū)所對應的物流需求量見表1。表中i表示市轄區(qū)，(x,y)表示市轄區(qū)坐標；wi為需求量。

表1 物流公司建設需求點坐標及需求量

通過實地考察和建設物流公司的經(jīng)驗與調(diào)研情況，歸納得到幾個建設物流公司的影響因子：建設成本、交通要素、員工成本、周邊環(huán)境、客戶和商家的分布以及配送距離7個影響因子。表2為通過變異系數(shù)法得到的影響因子權重表。

表2 影響因子權重

該選址方案所選用的實驗平臺為MATLAB R2016a，在進一步驗證該方法的可行性過程中，由上述表2可知，建設成本影響因子所占的權重最大，故據(jù)物流公司建設需求點坐標及其需求量，分別采用BP算法模型、GA-BP算法模型、C-GA-BP算法模型對選址的建設成本進行優(yōu)化計算，在迭代次數(shù)均為80次的情況下，3種算法模型的建設費用分別如圖2所示。

圖2 尋優(yōu)曲線對比

通過圖2對比可知，在迭代次數(shù)相同的情況下，C-GA-BP 算法模型的訓練得到的建設成本費用明顯低于BP神經(jīng)網(wǎng)絡和GA-BP算法，因此可得出C-GA-BP算法在訓練建設成本方面的確有優(yōu)化能力。

在精度優(yōu)化方面，利用GA-BP和C-GA-BP算法模型對精度進行訓練，來驗證C-GA-BP算該實驗方法的精確度。將初始個體數(shù)和迭代次數(shù)的取值都以選取3個物流公司為主，通過對模型的訓練，算法和參數(shù)的調(diào)整，同時與GA-BP算法的收斂曲線進行比較，驗證C-GA-BP算法的收斂性。兩種模型分別訓練100次，分別選出其中目標進化函數(shù)收斂效果最好的結果圖進行比較。其中GA-BP算法模型的收斂圖如圖3所示，C-GA-BP算法模型的收斂圖如圖4 所示。

圖3 GA-BP訓練

圖4 C-GA-BP訓練

通過對比，GA-BP算法模型訓練精度與C-GA-BP算法模型訓練精度相比較，在收斂速度方面具有明顯的差距。兩者相同的訓練次數(shù)相同的情況下，C-GA-BP算法模型的精度達到了5.224×10-9，而GA-BP算法模型的精度為2.3026×10-8，C-GA-BP算法模型的精度明顯高于GA-BP算法模型的精度，大大提高了收斂速度，由此可見，C-GA-BP 算法的確對于在選址方面具有明顯的優(yōu)化效果，并且具有一定的優(yōu)越性。

3.2 與部分文獻比較

為了進一步驗證該算法的精準優(yōu)化效果，選用AFSA算法[5]、BFO-AFSA算法[5]、ICS算法[11]、GA-BP算法各個算法比較結果見表3。

表3 算法比較結果

對上述表中算法參數(shù)設置均相同的情況下，迭代次數(shù)均為50次時，所有算法平均適應度與迭代次數(shù)之間的關系及運行結果如圖5所示。

圖5 算法運行結果對比

通過結合上述所有實驗圖表與參考文獻中算法的運行結果對比數(shù)據(jù)，可以看出C-GA-BP算法不僅在迭代次數(shù)相同的情況下，平均適應度值最優(yōu)，收斂速度快，而且在選址方面的確具有訓練精度高和優(yōu)化選址的優(yōu)點，結合圖2中C-GA-BP算法在建設成本方面優(yōu)化得到的結果，通過實驗得出了圖6為C-GA-BP選址優(yōu)化方案。

圖6 C-GA-BP優(yōu)化選址方案

4 結束語

本文提出的C-GA-BP算法優(yōu)化選址方法，通過影響因子權重值確定方法，建立了選址中心決策矩陣，確定了影響因子及其取值范圍，利用變異系數(shù)法得到了影響因子的權重值，并且對輸入數(shù)據(jù)的篩選過濾與歸一化處理，更好得到最優(yōu)化的選址方案。該優(yōu)化方法經(jīng)過實驗驗證可得，在提高訓練精度的同時降低了建設所耗成本,從而得到建設成本最低的選址方案，解決了GA-BP算法模型運行數(shù)據(jù)量大、收斂速度緩慢、過早收斂和易陷入局部最優(yōu)解[12]的雙重問題，為建設選址提供了新的方法。