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

(1.桂林理工大學(xué) 廣西空間信息與測(cè)繪重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541006；2.桂林理工大學(xué) 測(cè)繪地理信息學(xué)院，廣西 桂林 541006)

0 引 言

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

1 GA-BP算法

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

(1)首先確定神經(jīng)網(wǎng)絡(luò)的相應(yīng)結(jié)構(gòu)；依據(jù)該網(wǎng)絡(luò)結(jié)構(gòu)，確定其閾值、權(quán)值并對(duì)確定的該閾值權(quán)值等待求參數(shù)進(jìn)行編碼；

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

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

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

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

(6)對(duì)最佳個(gè)體進(jìn)行解碼，分別賦值于神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值；

(7)最后對(duì)BP神經(jīng)網(wǎng)絡(luò)進(jìn)行再次訓(xùn)練，當(dāng)滿足終止條件時(shí)，保留其結(jié)構(gòu)并預(yù)測(cè)輸出。

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

2 C-GA-BP算法描述

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

2.1 C-GA-BP算法流程

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

圖1 C-GA-BP算法流程

2.2 影響因子權(quán)重值確定方法

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

(1)

(2)

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

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

(1)計(jì)算第i項(xiàng)的影響因子的均方差

(3)

(4)

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

(5)

(3)通過(guò)變異系數(shù)來(lái)計(jì)算得到第i項(xiàng)影響因子的權(quán)重

(6)

則各因子的權(quán)重為

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

2.3 C-GA-BP計(jì)算過(guò)程

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

(7)

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

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

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

(8)

式中：dik表示為各個(gè)對(duì)象到聚類(lèi)中心的距離值，m表示對(duì)象維度，U表示聚類(lèi)矩陣，其距離計(jì)算公式如下

(9)

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

(10)

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

(4)初始化目標(biāo)的聚類(lèi)矩U

(11)

(5)計(jì)算求得目標(biāo)對(duì)象的聚類(lèi)中心V,集群中心采用下式可獲得

(12)

其中，n表示未分類(lèi)對(duì)象個(gè)數(shù)，uik表示第k個(gè)元素在第i類(lèi)的相關(guān)隸屬度，z表示加權(quán)參數(shù)。

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

3 仿真實(shí)驗(yàn)及結(jié)果

3.1 實(shí)驗(yàn)分析

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

表1 物流公司建設(shè)需求點(diǎn)坐標(biāo)及需求量

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

表2 影響因子權(quán)重

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

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

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

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

圖3 GA-BP訓(xùn)練

圖4 C-GA-BP訓(xùn)練

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

3.2 與部分文獻(xiàn)比較

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

表3 算法比較結(jié)果

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

圖5 算法運(yùn)行結(jié)果對(duì)比

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

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

4 結(jié)束語(yǔ)

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