孫 小 軍

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

?

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

孫 小 軍

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

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

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

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

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

1 螢火蟲算法

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

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

3 修正的螢火蟲算法

3.1算法思想

3.2算法步驟

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

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

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

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

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

4 數(shù)值算例

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

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

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

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

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

綜上所述,考慮到實際最短路問題中存在的模糊性,本文建立了帶有模糊約束最短路問題的數(shù)學(xué)模型,并對模型進行了轉(zhuǎn)化.FA作為一種新的仿生群智能優(yōu)化算法,雖然無法對最短路問題進行0,1編碼求解,但它對連續(xù)空間及離散空間的優(yōu)化具有良好的可行性和有效性,因此本文設(shè)計了一種MFA對轉(zhuǎ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] 方述誠,汪定偉.模糊數(shù)學(xué)與模糊優(yōu)化 [M].北京:科學(xué)出版社,1997.(FANG Shucheng,WANG Dingwei.Fuzzy Mathematics and Fuzzy Optimization [M].Beijing:Science Press,1997.)

[17] 刁在筠,鄭漢鼎,劉家壯,等.運籌學(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ǔ)研究計劃項目(批準號:2013JM1001).

TP301.6

：A

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