呂學(xué)義,鄭紹鈺

1(裝備學(xué)院 研究生管理大隊(duì),北京 101416)

2(裝備學(xué)院 裝備采辦系,北京 101416)

模糊聚類遺傳算法在軍事裝備物流中心選址中的應(yīng)用①

呂學(xué)義1,鄭紹鈺2

1(裝備學(xué)院 研究生管理大隊(duì),北京 101416)

2(裝備學(xué)院 裝備采辦系,北京 101416)

在分析軍事裝備物流中心選址問題基礎(chǔ)上,構(gòu)建了模糊聚類和遺傳算法的混合算法模型,核心技術(shù)是把模糊聚類網(wǎng)絡(luò)模型融合到遺傳算法種群構(gòu)建中,可以有效地避免遺傳算法易出現(xiàn)早熟的現(xiàn)象,驗(yàn)證了算法具有很好的魯棒性和可信度,仿真結(jié)果能夠?yàn)闆Q策者科學(xué)正確的選址提供一定的參考.

模糊聚類; 遺傳算法; 選址

軍事裝備物流中心作為平戰(zhàn)一體的物資保障單位,直接目的是保障軍事行動(dòng)的最終勝利. 這一點(diǎn)和地方物流以成本或是服務(wù)水平為目標(biāo)明顯不同. 軍事裝備物流中心具有較高的保密性,主要功能是滿足平時(shí)與戰(zhàn)時(shí)諸軍兵種聯(lián)合保障需求,其選址往往決定著物資的配送效率和配送方式,而選址的具體位置一旦被確定,往往難以改變,因此需要找到一個(gè)全局最優(yōu)的地理位置. 一般說來,軍事裝備物流中心選址模型是一個(gè)非凸和非光滑的帶有復(fù)雜約束的非線性規(guī)劃模型難題[1].模糊聚類遺傳算法非常適合用于解決非線性規(guī)劃模型,它不僅是借鑒生物的適者生存規(guī)則和遺傳進(jìn)化機(jī)制相結(jié)合開發(fā)出的一種高效全局尋優(yōu)搜索方法,而且優(yōu)化計(jì)算時(shí)不依賴梯度信息或其他輔助知識(shí),只需要影響搜索方向的目標(biāo)函數(shù)和適應(yīng)度函數(shù),特別適合研究解決一些大型、復(fù)雜非線性系統(tǒng)的最優(yōu)化問題,對(duì)目標(biāo)函數(shù)的凸(凹)性、連續(xù)性、線性都沒有限制,因此它是解決選址問題的一種比較理想方法.

1 模糊聚類遺傳算法基本思想

在軍事物流中心選址問題上,因軍事需求多元化、政治、經(jīng)濟(jì)、地理和人文等方面決定了選址高度的復(fù)雜性,該中心選址作為帶有強(qiáng)約束性的非線性規(guī)劃模型,僅僅采用模糊聚類算法非常容易陷入局部?jī)?yōu)化值,得不到全局的最優(yōu)解. 模糊聚類算法模糊聚類遺傳算法基本思想是利用該算法使群體中的每個(gè)個(gè)體快速趨向于各自的極值點(diǎn),通過遺傳算子擺脫個(gè)體可能陷入的局部最優(yōu)解,重復(fù)進(jìn)行這樣的搜索,直到找到最優(yōu)解. 對(duì)于該模型的理解,具體可分為兩個(gè)方面: (1)模糊聚類(Fuzzy clustering,FC)是用來快速估計(jì)樣本數(shù)據(jù)中聚類個(gè)數(shù)和聚類中心位置的單次算法[1]. 在裝備物資集中采購(gòu)中心選址問題中,它將每個(gè)已知物資中心地址作為可能的聚類中心,并依據(jù)各個(gè)樣本數(shù)據(jù)周圍信息量的密度來估計(jì)該位置作為聚類中心的可能性.它能夠非?？斓墓烙?jì)出具體位置的聚類個(gè)數(shù)和聚類中心,并按照每一個(gè)坐標(biāo)聚類的模糊聯(lián)系程度自動(dòng)地劃分規(guī)則,使規(guī)則的數(shù)目降為最低而數(shù)據(jù)的行為達(dá)到最好. 在選址問題上,需要綜合衡量的因素很多,具有多個(gè)復(fù)雜的非線性影響因素,這樣數(shù)學(xué)模型中規(guī)則的數(shù)目將急劇增加,經(jīng)常出現(xiàn)指數(shù)式增長(zhǎng)問題,系統(tǒng)顯得龐大而不易理解. (2)遺傳算法 (Genetic algorithm,GA)是受到生物免疫系統(tǒng)的啟發(fā),在免疫學(xué)理論基礎(chǔ)上發(fā)展起來的一種新的智能計(jì)算方法[2]. 主要是采用群體搜索策略,注重群體之間的信息交換,經(jīng)過“初始種群產(chǎn)生—評(píng)價(jià)標(biāo)準(zhǔn)計(jì)算—種群之間個(gè)體信息交換—產(chǎn)生新的種群”循環(huán)過程,最終以大概率勝出獲得最優(yōu)解. 但在使用遺傳算法求解問題的時(shí)候,會(huì)出現(xiàn)得到的近似最優(yōu)解與最優(yōu)解相差很大的情況. 這是因?yàn)檫z傳算法陷入了局部最優(yōu)解,很難跳出局部最優(yōu)解. 很多學(xué)者做過改進(jìn)遺傳算法方面的工作[3].

2 選址問題求解

選址問題種類多而且求解比較困難,不同的問題需要采用不同的優(yōu)化求解方法,主要包括精確算法和啟發(fā)式算法[4-8]. 本文中研究類型屬于離散選址問題,可以選用遺傳算法實(shí)現(xiàn)優(yōu)化求解. 下面,分兩個(gè)部分分別研究.

2.1 減法聚類分析討論

為不失一般性,假設(shè)空間為M維,x1,x2,···,xn為n個(gè)樣本數(shù)據(jù),設(shè)樣本數(shù)據(jù)已歸一化到超立方體,因?yàn)槊總€(gè)樣本數(shù)據(jù)都可能是聚類中心,所以樣本數(shù)據(jù)的密度指標(biāo)可具體表示為:

圖1 模糊聚類網(wǎng)絡(luò)結(jié)構(gòu)

SCANFIS共分為5層,前3層為規(guī)則前件層,后2層為規(guī)則后件層. 具體結(jié)構(gòu)說明如下:

第二層: 規(guī)則推理層,計(jì)算規(guī)則強(qiáng)度,這里的規(guī)則強(qiáng)度等于輸入向量X對(duì)應(yīng)聚類Ci的隸屬度O2.

第三層: 這一層的每個(gè)單元以符號(hào)“N”標(biāo)注,其作用是把各條規(guī)則的激勵(lì)強(qiáng)度進(jìn)行歸一化處理,第i條規(guī)則歸一化的激勵(lì)強(qiáng)度是該條規(guī)則的激勵(lì)強(qiáng)度與所有規(guī)則的激勵(lì)強(qiáng)度之和的商.

第五層: 輸出層以符號(hào)“∑”標(biāo)注,總輸出為:

構(gòu)建模糊聚類網(wǎng)絡(luò)模型主要有四個(gè)步聚: (1)選取樣本數(shù)據(jù)和驗(yàn)證樣本數(shù)據(jù); (2)將樣本數(shù)據(jù)進(jìn)行聚類分析,建立 SCANFIS 初始模糊模型; (3)假定 SCANFIS訓(xùn)練參數(shù),確定算法,訓(xùn)練網(wǎng)絡(luò)模型; (4)檢驗(yàn)得到的模糊神經(jīng)網(wǎng)絡(luò)模型性能. 減法聚類的函數(shù)實(shí)現(xiàn),通過上面分析討論,主要通過Matlab7.1軟件平臺(tái)調(diào)用函數(shù)實(shí)現(xiàn).

歸納起來,模糊聚類算法具有以下幾個(gè)缺點(diǎn): 一是處理有噪聲樣本數(shù)據(jù)集時(shí),噪聲數(shù)據(jù)對(duì)聚類結(jié)果影響較大; 二是聚類算法是一種無監(jiān)督式的,在確定聚類數(shù)C的方法上還不是很完善; 三是模糊聚類算法對(duì)樣本數(shù)據(jù)總是劃分為C個(gè)類中心,導(dǎo)致聚類的有效性分析是離散的粒子狀態(tài).

2.2 模糊聚類遺傳算法模型設(shè)計(jì)

模糊聚類遺傳算法主要是利用遺傳算法的全局收斂性及模糊聚類強(qiáng)大的局部尋優(yōu)能力,對(duì)初始種群進(jìn)行聚類,將得到新聚類中心作為選址模型,算法中還采用自適應(yīng)交叉和變異概率,進(jìn)一步增強(qiáng)算法的局部搜索性能.

模糊聚類遺傳算法具體實(shí)施步驟: 第一步,按照編碼規(guī)則產(chǎn)生初始種群,實(shí)質(zhì)是在問題的解空間與算法的搜索空間之間建立一個(gè)映射; 第二步,種群中的各個(gè)染色體進(jìn)行個(gè)體適應(yīng)度值計(jì)算; 第三步,利用遺傳算子進(jìn)行GA進(jìn)化; 第四步,以各個(gè)體為中心進(jìn)行一次模糊聚類,對(duì)種群進(jìn)行重新劃分,并根據(jù)重新劃分的種群集合進(jìn)行重新聚類,得到新的聚類中心,作為新個(gè)體替換原有的種群個(gè)體; 第五步,按照一定的交叉概率進(jìn)行交叉操作; 第六步,按照一定的變異概率進(jìn)行變異操作;第七步,將子代染色體于父代染色體進(jìn)行合并,得到一個(gè)臨時(shí)種群; 第八步,判斷算法是否結(jié)束,如果沒有,則返回步驟二繼續(xù)計(jì)算,否則,輸出適應(yīng)度值最優(yōu)的計(jì)算結(jié)果. 具體模糊聚類遺傳優(yōu)化算法的流程,如圖2所示.

圖2 模糊聚類遺傳算法流程

在遺傳算法中,通過編碼組成初始群體后,遺傳操作的任務(wù)就是對(duì)群體的個(gè)體按照其對(duì)環(huán)境的適應(yīng)度施加操作,實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化目的[9]. 遺傳操作主要包括選擇算子、交叉算子和變異算子.

(1)選擇算子. 目前常用的選擇算子有適應(yīng)度比例方法、隨機(jī)遍歷抽樣法和局部選擇法等,本文選擇一種最簡(jiǎn)單和常用的輪盤賭選擇法,在該方法中,各個(gè)個(gè)體的選擇概率和其適應(yīng)度值成比例. 設(shè)群體大小N,其中個(gè)體i的適應(yīng)度為f(i),則i被選中的概率為:

(2)交叉算子. 最常用的交叉算子為單點(diǎn)交叉. 具體操作是: 在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn),實(shí)行交叉時(shí),該點(diǎn)前后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換,并生成兩個(gè)新個(gè)體. 比如,個(gè)體A: 0011011; 個(gè)體B: 1010101,在第四位進(jìn)行交叉時(shí),生成的新個(gè)體為:A1: 0011101和B1: 1010011.

(3)變異算子. 基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng),分為實(shí)值變異和二進(jìn)制變異. 一般來說,變異操作分兩步完成: 一是對(duì)群中所有個(gè)體以事先設(shè)定的編譯概率判斷是否進(jìn)行變異; 二是對(duì)進(jìn)行變異的個(gè)體隨機(jī)選擇變異位置進(jìn)行變異. 通常取值在0.001到0.01之間.

遺傳算法中,交叉算子因其具有全局搜索能力而作為主要算子,變異算子因其局部搜索能力而作為輔助算子,通過交叉和變異相互配合又相互競(jìng)爭(zhēng)的操作,使其具備兼顧全局和局部的均衡搜索能力.

3 選址模型構(gòu)建

軍事裝備物流中心選址模型是非凸和非光滑的帶有復(fù)雜約束的非線性規(guī)劃模型,在構(gòu)建中心模型時(shí),先明確如下假設(shè): (1)中心容量總是可以滿足所屬單位的需求量,并由該中心保障供應(yīng)的所有單位的需求量確定; (2)一個(gè)需求單位僅由一個(gè)集中物流中心保障供應(yīng);(3)不考慮裝備物資生產(chǎn)廠家到物流中心的運(yùn)輸費(fèi)用.基于以上三條假設(shè)建立模型. 目標(biāo)函數(shù)是各個(gè)采購(gòu)中心到需求點(diǎn)的以需求量為權(quán)重的距離之和最小,目標(biāo)函數(shù)模型如下所示:

約束條件為:

4 實(shí)例驗(yàn)證

假設(shè),某部擬選址建立一個(gè)軍事裝備物流中心,實(shí)現(xiàn)平時(shí)和戰(zhàn)時(shí)裝備物資保障一體化,可以同時(shí)為武漢、無錫、桂林、西寧、沈陽(yáng)和鄭州六個(gè)聯(lián)勤保障基地和中心供應(yīng)戰(zhàn)備物資,考慮到武漢作為聯(lián)勤保障基地,要求新建的軍事裝備物流中心應(yīng)充分考慮該基地所在的地理位置. 經(jīng)了解,每個(gè)聯(lián)勤保障單位每日運(yùn)輸需求量見表1,六個(gè)聯(lián)勤保障單位的地理位置由實(shí)地測(cè)量得出. 政策支持,通過15-25位領(lǐng)域?qū)＜易稍兊贸?量化后的數(shù)據(jù)值1-10之間,數(shù)值越大表明支持越大.為簡(jiǎn)便起見,設(shè)每單位運(yùn)費(fèi)為1元.

表1 裝備物資日運(yùn)輸需求量和政策支持量化表

因聯(lián)勤保障單位A的每天的運(yùn)輸需求是16噸,所以每天向A運(yùn)輸貨物的費(fèi)用是:

同理,可以得到物流中心向其他五個(gè)聯(lián)勤保障單位運(yùn)輸貨物每日所需的運(yùn)輸費(fèi)用,由此得到費(fèi)用最小化的目標(biāo)函數(shù)如下:

很顯然,這個(gè)目標(biāo)函數(shù)是非線性的,考慮到駐地運(yùn)輸能力和軍工企業(yè)分布態(tài)勢(shì),經(jīng)過相關(guān)領(lǐng)域?qū)＜液蛯?shí)地考察綜合衡量評(píng)判,得出約束條件是:

根據(jù)軍事裝備物流中心選址數(shù)學(xué)模型,按照模糊聚類遺傳算法步驟進(jìn)行優(yōu)化求解,該算法的參數(shù)設(shè)置為: 種群規(guī)模為20,記憶庫(kù)容量為10,迭代次數(shù)為100,交叉概率為0.5,變異概率為0.4. 運(yùn)行結(jié)果如圖3所示.可知,x1=1.38363;x2=0.54044;x3=0.22713,因此新選軍事裝備物流中心位置為P(1.38363,0.54044,0.22713),每日的最小運(yùn)輸費(fèi)用為133.3317元. 加上政策支持、法律法規(guī)等評(píng)估值的權(quán)重系數(shù),可計(jì)算得出具體選址位置.

圖3 模型優(yōu)化結(jié)果

在實(shí)地調(diào)研的基礎(chǔ)上,綜合考慮當(dāng)?shù)卣?、法律法?guī)以及交通狀況等,統(tǒng)籌兼顧、突出重點(diǎn),是軍事準(zhǔn)備物流中心選址的基本準(zhǔn)則. 在設(shè)計(jì)的算法模型中,經(jīng)過多次運(yùn)行實(shí)驗(yàn),得到的軍事裝備物流中心選址結(jié)果趨于一致,可知該模型具有較好的魯棒性; 對(duì)選址優(yōu)化結(jié)果,采取實(shí)地分析測(cè)算和綜合評(píng)估的方法,可知具體較高的可信度. 在本文中軍事裝備物流中心選址的問題主要考慮三維地理坐標(biāo)和駐地兵工廠分布態(tài)勢(shì),但由于其他因素的不確定性,軍事裝備物流中心的選址還需要加強(qiáng)頂層設(shè)計(jì)和統(tǒng)一衡量.

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

兵馬未動(dòng)糧草先行. 軍事物流中心是保障部隊(duì)平時(shí)和戰(zhàn)時(shí)履行使命任務(wù)的核心關(guān)鍵. 本文主要是對(duì)軍事裝備物流中心的選址問題進(jìn)行了研究,提出模糊聚類網(wǎng)絡(luò)模型和遺傳算法相結(jié)合的思想,分析了現(xiàn)在聯(lián)勤保障單位的三維坐標(biāo)系,通過實(shí)例驗(yàn)證了算法的收斂性和魯棒性,該模糊聚類遺傳算法的求解結(jié)果隨著進(jìn)化代數(shù)的增加而逐漸優(yōu)化,并沒有出現(xiàn)早熟收斂現(xiàn)象,這說明本文提出的該算法求解結(jié)果具有較強(qiáng)的精確性和可信度,為解決較復(fù)雜的或規(guī)模較大的選址問題提供了新思路,也為決策者科學(xué)正確的選址問題提供重要參考.

1周志華,陳世福. 神經(jīng)網(wǎng)絡(luò)集成. 計(jì)算機(jī)學(xué)報(bào),2002,25(1):1–8.

2施彥. 物流中心選址的神經(jīng)網(wǎng)絡(luò)集成模型研究. 計(jì)算機(jī)工程與應(yīng)用,2009,45(16): 211–214. [doi: 10.3778/j.issn.1002-8331.2009.16.062]

3蔡良偉,李霞. 遺傳算法交叉操作的改進(jìn). 系統(tǒng)工程與電子技術(shù),2006,28(6): 925–928.

4潘偉,刁華宗,井元偉. 一種改進(jìn)的實(shí)數(shù)自適應(yīng)遺傳算法. 控制與決策,2006,21(7): 792–795,800.

5衛(wèi)紹元,王冬梅. 基于混合遺傳算法的車輛路徑問題. 交通運(yùn)輸系統(tǒng)工程與信息,2006,6(6): 49–52.

6廉晚祥,朱參世,胡江華,等. 改進(jìn)遺傳算法在應(yīng)急救援物資運(yùn)輸中的應(yīng)用. 中國(guó)安全科學(xué)學(xué)報(bào),2013,23(5): 172–176.

7吳勇剛,徐香新,劉梅,等. 基于遺傳算法的最優(yōu)城市垃圾收運(yùn)路線探究. 計(jì)算機(jī)仿真,2012,29(4): 259–262,312.

8孫全穎,王藝霖,杜須韋. 遺傳算法在機(jī)械優(yōu)化設(shè)計(jì)中的應(yīng)用研究. 哈爾濱理工大學(xué)學(xué)報(bào),2015,20(4): 46–50.

9包子陽(yáng),余繼周. 智能優(yōu)化算法及其MATLAB實(shí)例. 北京:電子工業(yè)出版社,2016: 13–16.

Application of Fuzzy Clustering Genetic Algorithm to Military Equipment Logistics Center Location

LV Xue-Yi1,ZHENG Shao-Yu2

1(Company of Postgraduate Management,Equipment of Academy,Beijing 101416,China)
2(Department of Equipment Acquisition,Equipment of Academy,Beijing 101416,China)

This paper analyzes the military equipment logistics center location problem and based on the analysis,builds the hybrid algorithm model which combines fuzzy clustering and genetic algorithm. The core technology is to integrate the fuzzy clustering network model into genetic algorithm in the process of building groups,which can effectively avoid the possibility for genetic algorithm to be prone to premature. The algorithm has been validated to be robust and reliable.The simulation results offer certain references for policy-makers to select the location more scientifically.

fuzzy clustering; genetic algorithm; location

呂學(xué)義,鄭紹鈺.模糊聚類遺傳算法在軍事裝備物流中心選址中的應(yīng)用.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(12):170–174. http://www.c-sa.org.cn/1003-3254/6119.html

2017-03-16; 修改時(shí)間: 2017-04-05; 采用時(shí)間: 2017-04-17