帶有模糊約束最短路問題的數(shù)學(xué)模型及算法

孫 小 軍

(寶雞文理學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院,陜西 寶雞 721013)

?

帶有模糊約束最短路問題的數(shù)學(xué)模型及算法

孫 小 軍

(寶雞文理學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院,陜西 寶雞 721013)

針對(duì)帶有模糊約束的最短路問題,在其模糊線性規(guī)劃模型的基礎(chǔ)上,利用容差法和罰函數(shù)法對(duì)該模型進(jìn)行轉(zhuǎn)化,得到了與原模型具有相同最優(yōu)解與最優(yōu)值的轉(zhuǎn)化模型,并提出一種修正的螢火蟲算法求解轉(zhuǎn)化模型.數(shù)值算例結(jié)果表明,該模型與算法對(duì)求解帶有模糊約束的最短路問題有效.

模糊約束；最短路問題；螢火蟲算法；修正算法

網(wǎng)絡(luò)優(yōu)化作為運(yùn)籌學(xué)的一個(gè)重要分支,主要研究生產(chǎn)管理、科學(xué)技術(shù)等諸多領(lǐng)域中與網(wǎng)絡(luò)有關(guān)的各類問題的優(yōu)化模型和算法,其中與網(wǎng)絡(luò)密切相關(guān)的是最短路問題(shortest path problem,SPP),對(duì)該問題的模型與算法目前已有廣泛研究[1-9].

隨著不確定性理論的發(fā)展,不確定環(huán)境下的最短路問題已引起人們的廣泛關(guān)注.Dubois等[10]利用模糊集理論中的最大、最小值算子和Zadeh擴(kuò)展原理求模糊最短路的長(zhǎng)度,但由于模糊運(yùn)算的特點(diǎn),雖然能求出模糊最短路的長(zhǎng)度,但卻找不到與之對(duì)應(yīng)的實(shí)際路徑；Klein[11]基于模糊效用函數(shù)的概念,提出了一種動(dòng)態(tài)規(guī)劃的方法,該方法可得到一條或多條滿足決策者要求的路徑；此后,基于多準(zhǔn)則決策理論,Okada等[12]提出了非被支配路徑的概念,并取得了模糊最短路問題的一些階段性成果;文獻(xiàn)[13]受變形蟲的有機(jī)體----多頭絨泡菌的啟發(fā),設(shè)計(jì)了一種模糊多頭絨泡菌算法解決模糊最短路問題;Hassanzadeha等[14]討論了帶有混合模糊弧長(zhǎng)的模糊最短路問題,采用α-截集方法作為弧長(zhǎng)不同模糊數(shù)的加法運(yùn)算,通過建立最小二乘模型,提出了一種遺傳算法求解該問題.

1 螢火蟲算法

螢火蟲算法[15]通過模擬自然界中螢火蟲在其搜索區(qū)域內(nèi)由發(fā)光尋找伙伴,并向鄰域結(jié)構(gòu)內(nèi)位置較優(yōu)的螢火蟲移動(dòng),從而實(shí)現(xiàn)位置進(jìn)化的生物學(xué)特性,將搜索空間中的點(diǎn)視為自然界中的螢火蟲個(gè)體,并將優(yōu)化問題的目標(biāo)函數(shù)度量成個(gè)體所處位置的優(yōu)劣,從而將搜索和優(yōu)化過程模擬成螢火蟲個(gè)體的吸引和移動(dòng)過程.該算法參數(shù)少、實(shí)現(xiàn)簡(jiǎn)單、并行性強(qiáng),且對(duì)連續(xù)空間和離散空間的優(yōu)化均具有可行性和有效性.

2 帶有模糊約束最短路問題的數(shù)學(xué)模型

故帶有模糊約束最短路問題的模糊線性規(guī)劃模型如下：

(1)

定義上述模糊不等式的隸屬函數(shù)為

其中,d為所選擇路徑的容忍度.根據(jù)容差法[16],模型(1)可轉(zhuǎn)化為如下形式：

(2)

其中α∈[0,1]為滿意度因子.顯然,模型(2)可化為如下模型：

(3)

針對(duì)模型(3)中的不等式約束,利用罰函數(shù)法[17]對(duì)模型(3)進(jìn)行轉(zhuǎn)化,選取罰函數(shù)為

其中M為懲罰因子.當(dāng)M充分大時(shí),模型(3)可相應(yīng)地轉(zhuǎn)化為如下模型：

(4)

是“煙富3號(hào)”的早熟株變。2015年通過貴州省品種審定委員會(huì)審定。其主要的優(yōu)良變異體現(xiàn)在成熟期上，在貴州長(zhǎng)順8月中下旬成熟。果實(shí)近圓形，果形指數(shù)0.87，平均單果重210～250克。果面平滑，稀有果粉，果皮底色淡黃，條紅，著色面積85%以上。果肉淡黃，質(zhì)地硬脆，肉質(zhì)細(xì)，汁液多，風(fēng)味酸甜，香氣濃，品質(zhì)上等?？扇苄怨绦挝?4.7%～15.9%。

3 修正的螢火蟲算法

3.1算法思想

3.2算法步驟

1)參數(shù)初始化.設(shè)螢火蟲的數(shù)目為m,螢火蟲間的最大吸引度為β0,光強(qiáng)吸收系數(shù)為γ,終止準(zhǔn)則中的最大迭代次數(shù)為maxG.

5)重新計(jì)算螢火蟲個(gè)體的亮度.根據(jù)更新后螢火蟲個(gè)體的空間位置,重新計(jì)算螢火蟲個(gè)體的亮度.比較種群中所有螢火蟲的亮度,并記錄當(dāng)前最大亮度及螢火蟲的最優(yōu)位置.

6)終止準(zhǔn)則.判斷是否已達(dá)到算法規(guī)定的最大迭代次數(shù)maxG,若是,停止迭代,輸出最大亮度(即最優(yōu)值,最小目標(biāo)函數(shù)值)及螢火蟲的最優(yōu)位置(即最短路徑)；否則,將迭代次數(shù)加1,轉(zhuǎn)3),進(jìn)行下一次優(yōu)化搜索.

3.3計(jì)算復(fù)雜度分析

設(shè)m為螢火蟲的種群數(shù)目,由文獻(xiàn)[17]可知FA的計(jì)算復(fù)雜度為O(m2).與FA相比,MFA針對(duì)螢火蟲之間的距離及步長(zhǎng)因子做了修正,整個(gè)過程并未增加運(yùn)算量,所以MFA的計(jì)算復(fù)雜度與FA相同.

4 數(shù)值算例

圖1 有向網(wǎng)絡(luò)GFig.1 Directed network G

給定有向網(wǎng)絡(luò)G如圖1所示,網(wǎng)絡(luò)中各條弧上有兩個(gè)權(quán)值,第一個(gè)權(quán)值表示費(fèi)用,第二個(gè)權(quán)值表示時(shí)間.這里取T=15,d=10,求起點(diǎn)1到終點(diǎn)16滿足時(shí)間模糊約束的最小費(fèi)用路徑.

采用MFA對(duì)帶模糊約束最短路問題的數(shù)學(xué)模型進(jìn)行求解.算法采用MATLAB R2012b軟件,在Windows 8.1(CPU:Intel(R)Core(TM)2,2.00 GHz,內(nèi)存2 GB)平臺(tái)上編碼實(shí)現(xiàn),這里取種群數(shù)m=50,最大迭代次數(shù)maxG=500,β0=1,γ=1.根據(jù)滿意度因子α的不同取值,分別運(yùn)行程序20次,得到該問題的計(jì)算結(jié)果列于表1.

表1 MFA的計(jì)算結(jié)果Table 1 Numerical results of MFA

由表1可見,當(dāng)滿意度因子α=0.1時(shí),模糊處理后的時(shí)間上限為24,在該時(shí)間上限內(nèi),求得的最小費(fèi)用路徑為：1→3→6→9→12→15→16,此時(shí)最小費(fèi)用為15；當(dāng)滿意度因子α=0.5時(shí),模糊處理后的時(shí)間上限為20,在該時(shí)間上限內(nèi),求得的最小費(fèi)用路徑為：1→2→5→8→12→15→16,最小費(fèi)用為18.由于此時(shí)時(shí)間上限變小,可行域也隨之變小,故此時(shí)所得路徑的最小費(fèi)用顯然大于滿意度因子α=0.1時(shí)所得路徑的最小費(fèi)用；同理,在滿意度為0.9時(shí)所得路徑的最小費(fèi)用也較之前兩種情形下所得路徑的最小費(fèi)用多.表明滿意度越高,時(shí)間限制越嚴(yán)格,可以滿足時(shí)間限制的路徑越少,從而使得所需的費(fèi)用呈遞增趨勢(shì).同時(shí),算例也表明了本文提出的模型及MFA對(duì)帶有模糊約束的最短路問題有效.

綜上所述,考慮到實(shí)際最短路問題中存在的模糊性,本文建立了帶有模糊約束最短路問題的數(shù)學(xué)模型,并對(duì)模型進(jìn)行了轉(zhuǎn)化.FA作為一種新的仿生群智能優(yōu)化算法,雖然無法對(duì)最短路問題進(jìn)行0,1編碼求解,但它對(duì)連續(xù)空間及離散空間的優(yōu)化具有良好的可行性和有效性,因此本文設(shè)計(jì)了一種MFA對(duì)轉(zhuǎn)化后的模型進(jìn)行0,1編碼求解,算法的復(fù)雜度分析和數(shù)值算例都表明了該算法具有良好的求解性能.

[1] Bellman R.On a Routing Problem [J].Quarterly of Applied Mathematics,1958,16(1):87-90.

[2] Dijkstra E W.A Note on Two Problems in Connexion with Graphs [J].Numerical Mathematics,1959,1(1):269-271.

[3] Pallottino S.Shortest-Path Methods:Complexity,Interrelations and New Propositions [J].Networks,1984,14(2):257-267.

[4] Goldberg A V,Radzik T.A Heuristic Improvement of the Bellman-Ford Algorithm [J].Applied Mathematics Letters,1993,6(3):3-6.

[5] Thorup M.Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time [J].Journal of the ACM,1999,46(3):362-394.

[6] Ibrahim M S,Maculan N,Minnoux M.A Strong Flow-Based Formulation for the Shortest Path Problem in Digraphs with Negative Cycles [J].International in Operational Research,2009,16(3):361-369.

[7] Jolai F,Ghanbari A.Integrating Data Transformation Techniques with Hopfield Neural Networks for Solving Travelling Salesman Problem [J].Expert Systems with Applications,2010,37(7):5331-5335.

[8] Chen B Y,Lam W H K,Sumalee A,et al.Finding Reliable Shortest Paths in Road Networks under Uncertainty [J].Netwoks and Spatial Economics,2013,13(2):123-148.

[9] Han D H,Kim Y D,Lee J Y.Multiple-Criterion Shortest Path Algorithms for Global Path Planning of Unmanned Combat Vehicles [J] .Computers &Industrial Engineering,2014,71:57-69.

[10] Dubois D,Prade H.Systems of Linear Fuzzy Constraints [J].Fuzzy Sets and Systems,1980,3(1):37-48.

[11] Klein C M.Fuzzy Shortest Paths [J].Fuzzy Sets and Systems,1991,39(1):27-41.

[12] Okada S,Soper T.A Shortest Path Problem on a Network with Fuzzy Arc Lengths [J].Fuzzy Sets and Systems,2000,109(1):129-140.

[13] DENG Yong,CHEN Yuxin,ZHANG Yajuan,et al.Fuzzy Dijkstra Algorithm for Shortest Path Problem under Uncertain Environment [J].Applied Soft Computing,2012,12(3):1231-1237.

[14] Hassanzadeha R,Mahdavi I,Amiri N M,et al.A Genetic Algorithm for Solving Fuzzy Shortest Path Problems with Mixed Fuzzy Arc Lengths [J].Mathematical and Computer Modelling,2013,57(1/2):84-99.

[15] YANG Xinshe.Firefly Algorithms for Multimodal Optimization [C]//Proc of the 5th International Symposium on Stochastic Algorithms:Foundations and Applications.Berlin:Springer,2009:169-178.

[16] 方述誠(chéng),汪定偉.模糊數(shù)學(xué)與模糊優(yōu)化 [M].北京:科學(xué)出版社,1997.(FANG Shucheng,WANG Dingwei.Fuzzy Mathematics and Fuzzy Optimization [M].Beijing:Science Press,1997.)

[17] 刁在筠,鄭漢鼎,劉家壯,等.運(yùn)籌學(xué) [M].北京:高等教育出版社,2003.(DIAO Zaijun,ZHENG Handing,LIU Jiazhuang,et al.Operational Research [M].Beijing:Higher Education Press,2003.)

(責(zé)任編輯：韓 嘯)

MathematicalModelandAlgorithmfortheShortestPathProblemwithFuzzyConstraints

SUN Xiaojun

(CollegeofMathematicsandInformation,BaojiUniversityofArtsandSciences,Baoji721013,ShaanxiProvince,China)

In order to solve the shortest path problem with fuzzy constraint,based on the fuzzy linear programming model,tolerance method and penalty function method were adopted to convert the original model to obtain a transformed model with the same optimal solution and optimal value as those of the original model.Then,a modified firefly algorithm was proposed to solve the transformed model.In addition,the computational complexities of the modified algorithm as well as the firefly algorithm were analyzed and compared.Finally,numerical example was given to illustrate the efficiency of the new model and algorithm to solve the shortest path problem with fuzzy constraint.

fuzzy constraints;shortest path problem;firefly algorithm;modified algorithm

10.13413/j.cnki.jdxblxb.2015.03.25

2014-06-30.

孫小軍(1978—),男,漢族,碩士,副教授,從事網(wǎng)絡(luò)優(yōu)化與數(shù)學(xué)建模的研究,E-mail:bwlsxj@163.com.

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(批準(zhǔn)號(hào):2013JM1001).

TP301.6

：A

：1671-5489(2015)03-0478-05