求最短路問題的神經(jīng)動力系統(tǒng)模型優(yōu)化方法

高 健，許文杰，歐宜貴

（海南大學理學院，海南?？?570228）

最短路問題，一般來說就是從給定的網(wǎng)絡圖中找出給定的起點和終點之間距離最短的一條路徑.這里所說的“距離”只是權(quán)數(shù)的代稱，可以是通常說的距離，也可以是時間、費用等.

眾所周知，最短路問題不僅在生產(chǎn)管理、交通運輸和通訊領(lǐng)域具有廣泛的應用，而且經(jīng)常被作為一個基本工具，用于解決其他優(yōu)化問題［1-2］.因此，此類問題吸引了眾多研究人員對其求解算法進行探討.迄今為止，求最短路問題的主要經(jīng)典算法有Bellman-動態(tài)規(guī)劃算法、Dijkstra算法和Floyd算法［1］.需要指出的是，這些經(jīng)典的數(shù)值算法屬于離散化的迭代方法，一般只能處理小規(guī)模的問題，而對較大規(guī)模的問題以及需要實時解的問題（比如業(yè)務路由選擇問題和路線規(guī)劃問題［3-4］）就會失效，甚至無能為力.這是由于求解此類優(yōu)化問題的運行時間主要依賴于問題的維數(shù)和結(jié)構(gòu)以及所用優(yōu)化算法的復雜性.為了克服這些缺陷，一種結(jié)合神經(jīng)網(wǎng)絡和動力系統(tǒng)（一般由一階微分方程表示）的神經(jīng)動力系統(tǒng)模型優(yōu)化方法［5-6］應運而生.

基于神經(jīng)動力系統(tǒng)模型的優(yōu)化方法是近三十多年發(fā)展起來的一類優(yōu)化方法［6］.以光滑優(yōu)化問題為例，這類方法的本質(zhì)是：基于原始優(yōu)化問題構(gòu)造某一常微分方程系統(tǒng)，使得該系統(tǒng)的平衡點對應于原問題的最優(yōu)解，然后再選取適當?shù)臄?shù)值方法來求解該微分方程系統(tǒng)，從而獲得原優(yōu)化問題的最優(yōu)解或近似最優(yōu)解.引入微分方程的魅力在于能幫助研究者系統(tǒng)地研究微分系統(tǒng)解的瞬態(tài)性能和極限行為，從而追蹤從初始點到極限點之間的連續(xù)運動軌跡.由于此類優(yōu)化方法兼顧了經(jīng)典的動力系統(tǒng)和神經(jīng)網(wǎng)絡2種方法的優(yōu)點（即大規(guī)模并行計算和分批處理信息的能力以及解的實時在線特性），同時在分析動力系統(tǒng)的穩(wěn)定性時采用了不同以往的新策略，從而可能避免使用傳統(tǒng)的Lyapunov函數(shù)，使得在利用這類新方法來研究最優(yōu)化問題時獲得了較先前更好的理論結(jié)果以及更具競爭力的數(shù)值表現(xiàn)性能.目前，基于神經(jīng)動力系統(tǒng)的優(yōu)化方法已取得了若干重要進展［6-10］.

最近，已有學者研究并提出了求解最短路問題的神經(jīng)動力系統(tǒng)模型優(yōu)化方法［11-14］.但是這些方法的模型結(jié)構(gòu)復雜，且不容易實施.因此，如何構(gòu)造結(jié)構(gòu)簡單、穩(wěn)定性好且容易實施的神經(jīng)動力系統(tǒng)模型來處理這類特殊優(yōu)化問題就顯得非常必要.

基于上述討論，并受文獻［8，11，15］的啟發(fā)，筆者提出了一個基于神經(jīng)動力系統(tǒng)模型的求解最短路問題的優(yōu)化方法，其基本思想：先將最短路問題轉(zhuǎn)化為線性規(guī)劃（LP）模型，再利用該LP模型來構(gòu)造結(jié)構(gòu)簡單且容易實施的神經(jīng)動力系統(tǒng)模型（理論上可以證明該模型的平衡點等價于LP的最優(yōu)解），最后通過求解所提出的系統(tǒng)模型來得到最短路問題的最短路徑和最短路長.

1 最短路問題的LP模型

為討論問題的方便，只考慮含有n個頂點的有向賦權(quán)圖，且假設所考慮的圖沒有負回路［1］.

給定一個賦權(quán)有向圖G=(V，A，W)，其中V是含有n個頂點的集合（記為V={v1，v2，…，v n}），A是具有m條弧的集合（記為A={e1，e2，…，e m}），而W=(w ij)為圖G的所有弧的權(quán)集合（也稱為權(quán)矩陣，而wij表示弧(v i，v j)?(i，j)的權(quán)數(shù)）.又給定G中的一個起點v s和一個終點v t，并設P是G中從v s到v t的一條路，則定義路P的權(quán)是P中所有弧的權(quán)之和，記為w(P)，即

又若P*是圖P中從v s到v t的一條路，且滿足：對G中所有從v s到v t的路P，均有

則稱P*為從v s到v t的最短路，w(P*)為從v s到v t的最短距離.在一個圖G=(V，A，W)中，求從v s到v t的最短路和最短距離的問題就稱為最短路問題.

為了建模的方便，不妨設圖G=(V，A，W)中的起點v s和終點v t分別是1和n.引入0-1整數(shù)決策變量x ij，其定義

于是，最短路問題的LP模型就可表示為

且滿足

對于上述LP模型，由于式（2）中定義的等式約束的系數(shù)矩陣具有全幺模性［2］，那么在最短路徑唯一的條件下，0-1整數(shù)性約束（3）可以等價地被替換為非負性約束.換言之，如果最短路問題存在唯一最優(yōu)解，則上述整數(shù)線性規(guī)劃問題（1）～（3）的最優(yōu)解總是由數(shù)0和1構(gòu)成的［2］.最短路問題可以通過下列等價的LP來求解

且滿足

其中，δij表示Kroneckerδ函數(shù)，其定義是

基于上述討論，可以得出：最短路問題可轉(zhuǎn)化為一類LP問題（4）～（6）.因此，考慮比上述LP問題更一般的LP問題

其中，A∈R m×n，b∈Rn，c∈Rn，x∈Rn，且rankA=m.問題（7）的對偶問題是

2 最短路問題的神經(jīng)動力系統(tǒng)模型

為了定義最短路問題的神經(jīng)動力系統(tǒng)模型，給出下列定義.

設Ω是Rn上的非空閉凸集.對于任意給定的v∈Rn，v在Ω的投影PΩ(v)定義為

特別地，如果Ω={x∈Rn|l≤x≤u}，有

其中，(x)i表示向量x∈R n的第i個分量.

類似于文獻［15］中的討論，可以得到求解LP問題（7）和（8）的神經(jīng)動力系統(tǒng)模型

其中，X={x∈Rn|x i≥0，i=1，2，…，n}，ε＞0是時間控制參數(shù)，而y∈Rn是對偶變量.顯然，當ε=1時，模型（10）就是文獻［15］中模型.

關(guān)于神經(jīng)動力系統(tǒng)模型（10）的穩(wěn)定性，有如下結(jié)論.

定理1神經(jīng)動力系統(tǒng)模型（10）的解軌跡z(t)=(x(t)，y(t))T全局收斂于問題（7）和（8）的精確解z*=(x*，y*)T.

證明類似于文獻［15］中定理3.3的證明方法可得證，在此略去.

注1 若將LP問題（7）～（8）中的非負約束x≥0看成不等式約束，則類似于文獻［16］中的討論，可以得到LP問題（7）～（8）的另一個神經(jīng)動力系統(tǒng)模型

顯然，模型（11）具有2n+m個狀態(tài)變量，而模型（10）具有n+m個狀態(tài)變量.因此，同模型（11）相比而言，模型（10）的計算量更少，且更易實施.

3 數(shù)值模擬實驗

為了驗證神經(jīng)動力系統(tǒng)模型（10）的表現(xiàn)性能，選取了2個實例［17］來進行數(shù)值模擬測試，在實驗過程中，采用Matlab的常微分方程求解器是ODE23.

問題1 求圖1中的頂點V1到V7的最短路徑.

圖1 頂點V1到V7的路徑圖

此問題可表示為下列0-1整數(shù)線性規(guī)劃模型

按上一節(jié)的討論，可簡化為

其中，x1=x12，x2=x13，x3=x23，x4=x24，x5=x25，x6=x34，x7=x36，x8=x45，x9=x46，x10=x57，x11=x65，x12=x67.

此問題有最短路徑：V1→V2→V5→V7.在［0，1］隨機產(chǎn)生初始點x10，其模擬結(jié)果如圖2所示.圖3給出了誤差‖x(t)-x*‖對初始點x10的收斂性.

圖2 例1中x（t）對初始點x01的瞬態(tài)行為

圖3 例1中誤差‖x(t)-x*‖對初始點x01的收斂性

問題2 求圖4中的頂點V1到V9的最短路徑.

圖4 頂點V1到V9的路徑圖

此問題可表示為下列0-1整數(shù)線性規(guī)劃模型

可簡化為

其中，x1=x12，x2=x13，x3=x15，x4=x24，x5=x27，x6=x25，x7=x35，x8=x38，x9=x36，x10=x47，x11=x57，x12=x59，x13=x58，x14=x68，x15=x79，x16=x89.

此問題有最短路徑：V1→V2→V5→V8→V9.在［0，1］隨機產(chǎn)生初始點x20，其模擬結(jié)果如圖5所示.圖6給出了誤差‖x(t)-x*‖對初始點x20的收斂性.

圖5 例2中x（t）對初始點x02的瞬態(tài)行為

圖6 例2中誤差‖x(t)-x*‖對初始點x02的收斂性

盡管從這有限的2個實例得不到一般性的結(jié)論，但從圖2和3以及圖5和6可以看出：神經(jīng)動力系統(tǒng)模型（10）能比較有效地求出網(wǎng)路圖的最短路徑.

4 結(jié)束語

給出了一個基于神經(jīng)動力系統(tǒng)模型的求解最短路問題的連續(xù)化優(yōu)化方法，并得到其全局穩(wěn)定性結(jié)論.2個具體的數(shù)值模擬結(jié)果驗證了該方法的可行性.本文所得到的結(jié)果對解決工程中的最短路徑問題具有比較重要的理論價值.利用本文所提出的連續(xù)化優(yōu)化方法來解決較大規(guī)模的最短路問題并檢驗本文所提出方法的實踐價值是下一步工作的重點.