鐘新成

（長(zhǎng)治學(xué)院 計(jì)算機(jī)系，山西 長(zhǎng)治 046011）

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

1 概率矩陣模型描述

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

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

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

圖1 未經(jīng)改進(jìn)的概率采樣模型

2 概率采樣模型改進(jìn)分析

勞斯穩(wěn)定判據(jù)是根據(jù)特征方程系數(shù)來(lái)分析系統(tǒng)穩(wěn)定性的一種判據(jù)，它避免了求特征方程根的繁瑣過(guò)程。勞斯判據(jù)指出線性系統(tǒng)穩(wěn)定的充要條件是勞斯表第一列系數(shù)都為正，如果出現(xiàn)負(fù)系數(shù)，則系統(tǒng)不穩(wěn)定。應(yīng)用勞斯判據(jù)分析系統(tǒng)穩(wěn)定性的步驟是，首先將特征方程按奇偶次數(shù)的系數(shù)排成兩行，然后建立勞斯表，最后根據(jù)勞斯判據(jù)判定系統(tǒng)的穩(wěn)定性。假若給定三階系統(tǒng)，其特征方程是：

那么其對(duì)應(yīng)的勞斯表如下：

圖2 勞斯表

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

圖3 改進(jìn)后的概率采樣模型

3 改進(jìn)概率采樣模型算法描述及采樣結(jié)果對(duì)比

圖4 改進(jìn)概率采樣模型算法描述

原始的概率采樣模型采樣個(gè)體時(shí)并不是每次都會(huì)出現(xiàn)采樣個(gè)體不能進(jìn)行下去的情況。以TSP采樣生成路徑為例，假設(shè)每次采樣個(gè)體20個(gè)，經(jīng)過(guò)10次運(yùn)行程序，原始概率采樣模型出現(xiàn)了3次采樣中斷的情形，分別是采樣到第10個(gè)個(gè)體時(shí)出現(xiàn)中斷、采樣第6個(gè)個(gè)體時(shí)出現(xiàn)中斷以及采樣第13個(gè)個(gè)體時(shí)出現(xiàn)中斷。而改進(jìn)后的概率模型采樣個(gè)體未出現(xiàn)中斷。改進(jìn)前后采樣個(gè)體結(jié)果對(duì)比如表1和表2所示。

表1 原始概率采樣模型采樣結(jié)果

表2 改進(jìn)概率采樣模型采樣結(jié)果

4 結(jié)束語(yǔ)

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