帶有模糊約束最短路問題的數學模型及算法

孫 小 軍

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

?

帶有模糊約束最短路問題的數學模型及算法

孫 小 軍

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

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

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

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

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

1 螢火蟲算法

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

2 帶有模糊約束最短路問題的數學模型

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

(1)

定義上述模糊不等式的隸屬函數為

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

(2)

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

(3)

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

其中M為懲罰因子.當M充分大時,模型(3)可相應地轉化為如下模型：

(4)

是“煙富3號”的早熟株變。2015年通過貴州省品種審定委員會審定。其主要的優良變異體現在成熟期上，在貴州長順8月中下旬成熟。果實近圓形，果形指數0.87，平均單果重210～250克。果面平滑，稀有果粉，果皮底色淡黃，條紅，著色面積85%以上。果肉淡黃，質地硬脆，肉質細，汁液多，風味酸甜，香氣濃，品質上等。可溶性固形物14.7%～15.9%。

3 修正的螢火蟲算法

3.1算法思想

3.2算法步驟

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

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

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

3.3計算復雜度分析

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

4 數值算例

圖1 有向網絡GFig.1 Directed network G

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

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

表1 MFA的計算結果Table 1 Numerical results of MFA

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

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

[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] 方述誠,汪定偉.模糊數學與模糊優化 [M].北京:科學出版社,1997.(FANG Shucheng,WANG Dingwei.Fuzzy Mathematics and Fuzzy Optimization [M].Beijing:Science Press,1997.)

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

(責任編輯：韓 嘯)

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—),男,漢族,碩士,副教授,從事網絡優化與數學建模的研究,E-mail:bwlsxj@163.com.

陜西省自然科學基礎研究計劃項目(批準號:2013JM1001).

TP301.6

：A

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