一類改進的概率采樣模型

鐘新成

（長治學院 計算機系，山西 長治 046011）

近年來，在進化計算[1,2]領域出現了一種新型的概率算法——分布估計算法[3,4]。其源于遺傳算法，卻在采樣個體的方法上和遺傳算法有著本質的區別。前者采用交叉、變異等手段來采樣個體以及引導種群進化，但可能出現建筑塊破壞問題，后者通過估計個體分布來建立概率模型從而采樣個體以及引導種群進化，能有效的解決遺傳算法可能遇到的建筑塊破壞問題。分布估計算法的核心問題是通過估計種群的分布情況來建立概率模型，在離散域（比如典型的TSP問題以及混合流水車間調度問題）通常采用一種概率矩陣模型來采樣個體，但是該方法在采樣個體時可能會出現全零行或全零列，導致程序無法向下運行。為解決該問題，文章引進勞斯穩定判據用無窮小ε來替代0的思想，從根本上解決了采樣個體不能順利進行的問題。

1 概率矩陣模型描述

以典型的旅行商問題（TSP問題）為例，如果不考慮回到原點，以五個城市為例，那么（2，4，3，1，5）便是一個個體（也可以說是一條路徑）。由于文章只討論采樣個體，故不討論其目標函數的具體約束形式，只討論其具體的概率約束形式，即對于每一個位置，各個城市出現的概率和為1。

概率矩陣采樣個體的思想是：用隨機數和列累計和相比較，按照位置順序逐個確定個體因子。首先將概率矩陣置為均勻矩陣，即每個城市在某個位置上出現的概率相等，對應本例就是每個位置上都是0.2。接著給矩陣A一個隨機數k（0＜k＜1）并比較k與概率矩陣第一列的累計和，比如k小于前兩項的累加和便選定第二個城市，并將位置A21置為1，第一列和第二行其他位置置零，然后將其他列歸一化處理。也就是說第一個位置選中了第二個城市，其他城市就不可能出現在第一個位置，同理，第二個城市選中了第一個位置，那么它就不可能出現在其他的位置上。接著再給矩陣一個隨機數k并比較其與第二列的累計和，依此類推直至一個個體采樣完畢。

隨著第一代個體的采樣結束，計算出適應值后來估計種群的分布情況，很可能得到諸如下面滿足要求的概率矩陣模型，任意給出隨機數0.25和0.74，于是試著一步一步的往下推便會得到全零列，采樣第三個位置便不能繼續。

圖1 未經改進的概率采樣模型

2 概率采樣模型改進分析

勞斯穩定判據是根據特征方程系數來分析系統穩定性的一種判據，它避免了求特征方程根的繁瑣過程。勞斯判據指出線性系統穩定的充要條件是勞斯表第一列系數都為正，如果出現負系數，則系統不穩定。應用勞斯判據分析系統穩定性的步驟是，首先將特征方程按奇偶次數的系數排成兩行，然后建立勞斯表，最后根據勞斯判據判定系統的穩定性。假若給定三階系統，其特征方程是：

那么其對應的勞斯表如下：

圖2 勞斯表

如果a2=0或勞斯陣列某一行第一項系數為零，而其他系數不全為零，按照勞斯表的算法則該系數會成為分母而使運算不能進行。那如何解決這一問題呢，勞斯判據給出用無窮小數ε來代替0而使運算繼續下去。于是運用這一思想，可以將概率采樣模型做如下改進，即將每代得到的概率矩陣模型中的0全部用無窮小數ε代替，此處不妨令ε=0.0001，這樣便能從根本上解決采樣中斷的問題。改進后的采樣步驟分析如下。

圖3 改進后的概率采樣模型

3 改進概率采樣模型算法描述及采樣結果對比

圖4 改進概率采樣模型算法描述

原始的概率采樣模型采樣個體時并不是每次都會出現采樣個體不能進行下去的情況。以TSP采樣生成路徑為例，假設每次采樣個體20個，經過10次運行程序，原始概率采樣模型出現了3次采樣中斷的情形，分別是采樣到第10個個體時出現中斷、采樣第6個個體時出現中斷以及采樣第13個個體時出現中斷。而改進后的概率模型采樣個體未出現中斷。改進前后采樣個體結果對比如表1和表2所示。

表1 原始概率采樣模型采樣結果

表2 改進概率采樣模型采樣結果

4 結束語

概率采樣模型是概率型算法的核心，如果采樣方法存在缺陷，便可能會使采樣個體中斷，從而達不到預期目的。文章引進勞斯穩定判據用無窮小來替代0的思想，能有效的解決采樣個體中斷的問題，從根本上解決了采樣個體不能順利進行的問題，使該概率采樣模型更加成熟。