情報(bào)信息動(dòng)態(tài)規(guī)劃優(yōu)化網(wǎng)絡(luò)算法軟件研發(fā)與應(yīng)用

〔摘 要〕動(dòng)態(tài)規(guī)劃是處理情報(bào)信息領(lǐng)域信息獲取方式與路徑選擇，網(wǎng)絡(luò)信息的傳遞與交換途徑等階段決策問題的重要方法。本研究介紹一種動(dòng)態(tài)規(guī)劃方法，給出了Java網(wǎng)絡(luò)算法軟件，該軟件可在兼容Java的網(wǎng)絡(luò)瀏覽器上運(yùn)行，可用于計(jì)算最優(yōu)策略和目標(biāo)泛函的階段最優(yōu)和總最優(yōu)值。同時(shí)，用該算法進(jìn)行了用例分析，以期為有關(guān)情報(bào)信息研究與應(yīng)用提供一種在線計(jì)算工具。

〔關(guān)鍵詞〕信息;動(dòng)態(tài)規(guī)劃;網(wǎng)絡(luò)算法;軟件;應(yīng)用

〔中圖分類號(hào)〕G350.7 〔文獻(xiàn)標(biāo)識(shí)碼〕B 〔文章編號(hào)〕1008-0821(2009)03-0039-03

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

1 動(dòng)態(tài)規(guī)劃算法

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

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

然后，要確定每階段的決策變量。設(shè)u_k(x_k)為階段k當(dāng)狀態(tài)為x_k時(shí)的決策變量，u_k(x_k)∈D_k(x_k)，其中，D_k(x_k)為階段k的容許決策集。從階段k到終點(diǎn)的決策函數(shù)序列，即子策略為:

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

接著，要確定狀態(tài)轉(zhuǎn)移規(guī)則。已知階段k的狀態(tài)x_k，應(yīng)用決策變量u_k，則階段k+1的狀態(tài)x_k+1可被確定，即x_k+1=T_k(x_k，u_k)。

此后，定義目標(biāo)泛函。目標(biāo)泛函V_kn用于評(píng)價(jià)過程的優(yōu)度:

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

其中，V_kn的最優(yōu)值為最優(yōu)目標(biāo)泛函f_k(x_k)。目標(biāo)泛函的計(jì)算公式為:

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

其中，v_k(x_k，u_k)為階段k的的目標(biāo)值。目標(biāo)泛函是初始狀態(tài)和策略的函數(shù)，故目標(biāo)泛函的計(jì)算公式可寫為:

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)}。

最后，進(jìn)行逆向序列最優(yōu)化:

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

f₁(x₁)=玱pt(P1n)V1n(x₁，P1n)

或

f_k(x_k)=玱pt(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

此處，玱pt為最小或最大。于k=n開始，向前計(jì)算直到得出f₁(x₁)。從而，可得最優(yōu)策略和目標(biāo)泛函的最優(yōu)值。

2 算法實(shí)現(xiàn)

動(dòng)態(tài)規(guī)劃算法dynamicprograming以Java程序設(shè)計(jì)工具包JDK研制，包括1個(gè)Java類和一個(gè)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被載入瀏覽器后，顯示輸入窗口。輸入或選擇內(nèi)容依次為:最優(yōu)化類型(最大化為1，最小化為0)，狀態(tài)數(shù)(結(jié)點(diǎn)總數(shù))，決策變量數(shù)(路徑總數(shù))，初始狀態(tài)編號(hào)，終點(diǎn)狀態(tài)編號(hào)，打開數(shù)據(jù)文件。

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

運(yùn)行后輸出最優(yōu)策略和目標(biāo)泛函的階段最優(yōu)和總最優(yōu)值。

3 應(yīng)用分析

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

應(yīng)用前述動(dòng)態(tài)規(guī)劃算法dynamicprograming，得到最優(yōu)策略(圖3)，即最優(yōu)路徑序列為:1→2→6→8→11;目標(biāo)泛函的階段最優(yōu)值為:0→9→13→18→28;目標(biāo)泛函的總最優(yōu)值為28。

參考文獻(xiàn)

[1]李德，等.運(yùn)籌學(xué)[M].北京:清華大學(xué)出版社，1982.

[2]齊艷紅.網(wǎng)絡(luò)計(jì)量學(xué)的一種Internet分布式聚類分析軟件[J].情報(bào)科學(xué)，2003，21(10):1069-1071，1079.

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

[4]齊艷紅.多變量情報(bào)信息的統(tǒng)計(jì)假設(shè)檢驗(yàn)網(wǎng)絡(luò)軟件研究[J].情報(bào)雜志，2006，25(1):96-97.

[5]齊艷紅.情報(bào)信息的判別分析網(wǎng)絡(luò)計(jì)算軟件研究[J].情報(bào)雜志，2006，25(11):64-65.

[6]齊艷紅.選擇網(wǎng)絡(luò)節(jié)點(diǎn)與通道的Java決策樹計(jì)算[J].情報(bào)科學(xué)，2007.25(Suppl.):140-141.

[7]韓璽.競(jìng)爭(zhēng)情報(bào)人際關(guān)系網(wǎng)絡(luò)及其構(gòu)建[J].圖書情報(bào)工作，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.