情報信息動態規劃優化網絡算法軟件研發與應用

〔摘 要〕動態規劃是處理情報信息領域信息獲取方式與路徑選擇，網絡信息的傳遞與交換途徑等階段決策問題的重要方法。本研究介紹一種動態規劃方法，給出了Java網絡算法軟件，該軟件可在兼容Java的網絡瀏覽器上運行，可用于計算最優策略和目標泛函的階段最優和總最優值。同時，用該算法進行了用例分析，以期為有關情報信息研究與應用提供一種在線計算工具。

〔關鍵詞〕信息;動態規劃;網絡算法;軟件;應用

〔中圖分類號〕G350.7 〔文獻標識碼〕B 〔文章編號〕1008-0821(2009)03-0039-03

信息獲取的方式與路徑選擇，網絡信息的傳遞與交換途徑，以及節點與通道的搜索與選擇(齊艷紅，2007)，等等，都是多階段決策問題。有關多階段決策問題，多數可用線性規劃或非線性規劃來處理。然而，用動態規劃處理這類問題，會更加有效(Bellman，1957)。動態規劃是Bellman于20世紀50年代提出的。目前，已廣泛應用于各領域的多階段決策問題中。鑒于此，本研究建立一種Java動態規劃網絡算法，以期用于上述情報信息問題，可能有一定的應用價值。網絡在線軟件具有平臺無關等優點，已在有關領域得到了應用(齊艷紅，2003，2004，2006，2007)。鑒于此，本文研制了動態規劃的一種網絡算法軟件，以期為有關情報信息研究與應用提供一種在線計算工具。

1 動態規劃算法

動態規劃的核心是Bellman原理:多階段決策過程的最優決策序列有如此性質，即不論其初始階段，初始狀態，及初始決策如何，以第一個決策所形成的階段和狀態為初始條件時，隨后的決策對相應的問題必須構成最優決策系列(Norton，1972;李德等，1982)。動態規劃類型較多，有連續型動態規劃，離散型動態規劃，確定型動態規劃，不確定型動態規劃，等等。不同的方法，其算法也不相同。本研究所用的動態規劃，為離散型確定型動態規劃。算法步驟如下:

首先，將過程劃分為n個階段，k=1，2，…，n，要確定階段k的狀態x_k，x_k為階段k的某個初始狀態。

然后，要確定每階段的決策變量。設u_k(x_k)為階段k當狀態為x_k時的決策變量，u_k(x_k)∈D_k(x_k)，其中，D_k(x_k)為階段k的容許決策集。從階段k到終點的決策函數序列，即子策略為:

P_kn={u_k(x_k)，u_k+1(x_k+1)，…，u_n(x_n)}

接著，要確定狀態轉移規則。已知階段k的狀態x_k，應用決策變量u_k，則階段k+1的狀態x_k+1可被確定，即x_k+1=T_k(x_k，u_k)。

此后，定義目標泛函。目標泛函V_kn用于評價過程的優度:

V_kn=V_kn(x_k，u_k，x_k+1，…，x_n+1)，k=1，2，…，n

其中，V_kn的最優值為最優目標泛函f_k(x_k)。目標泛函的計算公式為:

V_kn=v_k(x_k，u_k)+V_k+1n(x_k+1，…，x_n+1)

其中，v_k(x_k，u_k)為階段k的的目標值。目標泛函是初始狀態和策略的函數，故目標泛函的計算公式可寫為:

V_kn(x_k，P_kn)=v_k(x_k，u_k)+V_k+1n(x_k+1，P_k+1n)

其中，P_kn={u_k(x_k)，P_k+1n (x_k+1)}。

最后，進行逆向序列最優化:

opt(P_kn)V_kn(x_k，P_kn)=opt(u_k){v_k(x_k，u_k)+opt(P_k+1n)V_k+1n k=n，n-1，…，1

f₁(x₁)=opt(P1n)V1n(x₁，P1n)

或

f_k(x_k)=opt(u_k∈D_k(x_k)){v_k(x_k，u_k)+f_k+1(x_k+1)} k=n，n-1，…，1

f_n+1(x_n+1)=0

此處，opt為最小或最大。于k=n開始，向前計算直到得出f₁(x₁)。從而，可得最優策略和目標泛函的最優值。

2 算法實現

動態規劃算法dynamicprograming以Java程序設計工具包JDK研制，包括1個Java類和一個HTML文件(圖1)。

算法的Java核心代碼為:

cut=0;

for(i=1;i<=m;i++)

for(k=1;k<=m;k++)

x[i][k]=10000000000;

for(i=1;i<=m;i++)

{

a[i]=10000000000;

c[i]=0;

p[i]=0;

}

for(k=1;k<=n;k++)

{

i=(int)Double.valueOf(sp.substring(0，sp.indexOf(′′))).doubleValue();

sp=sp.substring(sp.indexOf(′′)).trim();

j=(int)Double.valueOf(sp.substring(0，sp.indexOf(′′))).doubleValue();

sp=sp.substring(sp.indexOf(′′)).trim();

if(k!= n)

{

x[i][j]=Math.pow(-1D，type)*Double.valueOf(sp.substring(0，sp.indexOf(′′))).doubleValue();

}else

{

x[i][j]=Math.pow(-1D，type)*Double.valueOf(sp).doubleValue();

break;

}

sp=sp.substring(sp.indexOf(′′)).trim();

}

a[s]=0.0;

c[s]=1;

z=s;

time();

while((double)z<=1.0000000000000001E+050)

{

for(k=1;k<=m;k++)

if(!((c[k]==1)|(a[z]+x[z][k]>=a[k])))

{

a[k]=a[z]+x[z][k];

p[k]=z;

}

h=10000000000;

for(k=1;k<=m;k++)

if(!((a[k]>h)|(c[k]==1)))

{

h=a[k];

q=k;

}

if(h==10000000000)

return true;

z=q;

if(z==e)

break;

c[z]=1;

}

time();

w=a[e];

for(i=1;i>=1;i++)

{

d[i]=e;

if(e==s)

break;

e=p[e];

}

editt1.appendText(″Optimal strategy:\″);

for(;i>0;i-=2)

{

editt1.appendText(String.valueOf(d[i])+″

″+″(″+String.valueOf((int)(Math.pow(-1，type)*a[d[i]]))+″)″);

if(i==1)

break;

editt1.appendText(″---″+String.valueOf(d[i - 1])+″

″+″(″+String.valueOf((int)(Math.pow(-1，type)*a[d[i - 1]]))+″)″);

if(i==2)

break;

editt1.appendText(″---″);

}

editt1.appendText(″\″);

if(type==1)

editt1.appendText(″Maximum benefit=″+String.valueOf((double)(int)(-w*100000)/100000)+″\″);

else

editt1.appendText(″Minimum cost=″+String.valueOf((double)(int)(w*100000)/100000)+″\″);

Java算法dynamicprograming的Applet被載入瀏覽器后，顯示輸入窗口。輸入或選擇內容依次為:最優化類型(最大化為1，最小化為0)，狀態數(結點總數)，決策變量數(路徑總數)，初始狀態編號，終點狀態編號，打開數據文件。

在數據文件中(圖2)，列1為前一狀態的編號，列2為后一狀態的編號，列3為這兩個相鄰狀態之間的路徑的目標泛函值。數據文件為普通的MS-DOS文本文件(.txt)。在數據文件中，每個數據前后應保留至少1個空格?？稍贛S-DOS中的文本編輯器中編輯，或在記事本中編輯。

運行后輸出最優策略和目標泛函的階段最優和總最優值。

3 應用分析

一個信息獲取方式與路徑選擇問題，要求信息獲取的總耗費最小。多階段決策過程見圖3，原始數據見圖2所示。這里，狀態數為11，決策變量數為20。

應用前述動態規劃算法dynamicprograming，得到最優策略(圖3)，即最優路徑序列為:1→2→6→8→11;目標泛函的階段最優值為:0→9→13→18→28;目標泛函的總最優值為28。

參考文獻

[1]李德，等.運籌學[M].北京:清華大學出版社，1982.

[2]齊艷紅.網絡計量學的一種Internet分布式聚類分析軟件[J].情報科學，2003，21(10):1069-1071，1079.

[3]齊艷紅.情報信息因果分析的多變量回歸模型網絡軟件MultiVarRegr[J].情報科學，2004，22(1):104-106，114.

[4]齊艷紅.多變量情報信息的統計假設檢驗網絡軟件研究[J].情報雜志，2006，25(1):96-97.

[5]齊艷紅.情報信息的判別分析網絡計算軟件研究[J].情報雜志，2006，25(11):64-65.

[6]齊艷紅.選擇網絡節點與通道的Java決策樹計算[J].情報科學，2007.25(Suppl.):140-141.

[7]韓璽.競爭情報人際關系網絡及其構建[J].圖書情報工作，2006.4:43-46，76.

[8]Bellman RE.Dynamic Programming[M].Princeston University Press.Princeston，1957:88-135.

[9]Norton M.Modern Control Engineering[M].Pergamon Press，1972:121-168.