遺傳算法在計(jì)算機(jī)仿真技術(shù)中的應(yīng)用

時(shí)間：2024-10-13 21:10:44 計(jì)算機(jī)應(yīng)用畢業(yè)論文我要投稿

相關(guān)推薦

摘要：通過(guò)對(duì)隨機(jī)性問(wèn)題進(jìn)行計(jì)算機(jī)仿真，從而得出待解問(wèn)題的解。提出了基于遺傳算法進(jìn)行計(jì)算機(jī)仿真的基本模型。通過(guò)圓周率的計(jì)算，實(shí)踐了該模型的應(yīng)用過(guò)程。實(shí)踐證明，該模型在進(jìn)行計(jì)算機(jī)仿真時(shí)準(zhǔn)確度比較高。 關(guān)鍵詞：蒙特卡羅方法；；隨機(jī)數(shù)；遺傳算法

0 引言

計(jì)算機(jī)的出現(xiàn)和計(jì)算技術(shù)的發(fā)展為仿真技術(shù)的發(fā)展提供了強(qiáng)有力的手段和工具。最近幾年，隨著計(jì)算機(jī)的迅速發(fā)展和普及，尤其是微型計(jì)算機(jī)的發(fā)展和普及，很多大計(jì)算量的仿真系統(tǒng)得以實(shí)現(xiàn)，并在國(guó)民生產(chǎn)、科學(xué)研究等領(lǐng)域得到廣泛的應(yīng)用。

現(xiàn)代科技發(fā)展中提出愈來(lái)愈復(fù)雜的隨機(jī)性問(wèn)題, 除極少數(shù)外, 要想通過(guò)仿真給出其嚴(yán)格解是困難的, 用確定性方法給出其近似解也很困難, 甚至不可能。遺傳算法 GA (Genetic Algorithm)[1]是模擬生物進(jìn)化的優(yōu)化算法，把遺傳算法GA 應(yīng)用到仿真技術(shù)中，是一種很強(qiáng)的特殊的數(shù)值方法。

1 遺傳算法[ 1 ]

1.1 并行遺傳算法實(shí)現(xiàn)方案目前并行遺傳算法的實(shí)現(xiàn)方案大致可分為3 類： (1)全局型—主從式模型(master-slave model)：并行

系統(tǒng)分為一個(gè)主處理器和若干個(gè)從處理器。主處理器監(jiān)控整個(gè)染色體種群，并基于全局統(tǒng)計(jì)執(zhí)行選擇操作；各個(gè)從處理器接受來(lái)自主處理器的個(gè)體進(jìn)行重組交叉和變異，產(chǎn) 生新一代個(gè)體，并計(jì)算適應(yīng)度，再把計(jì)算結(jié)果傳給主處理

器。

從而加快滿足終止條件的要求。粗粒度模型也稱島嶼模型

(island model)，基于粗粒度模型的遺傳算法也稱為分布式遺傳算法(Distributed Genetic Algorithm)，也是目前應(yīng)用最廣泛的一種并行遺傳算法。

(3)分散型—細(xì)粒度模型(fine-grained model)：為種群中的每一個(gè)個(gè)體分配一個(gè)處理器，每個(gè)處理器進(jìn)行適應(yīng) 度的計(jì)算，而選擇、重組交叉和變異操作僅在與之相鄰的一個(gè)處理器之間相互傳遞個(gè)體中進(jìn)行，細(xì)粒度模型也稱鄰域模型(neighborhood model)，適合于連接機(jī)、陣列機(jī)和 SIMD 系統(tǒng)。

1.2 遷移策略

遷移(migration)是并行遺傳算法引入的一個(gè)新的算子，它是指在進(jìn)化過(guò)程中子群體間交換個(gè)體的過(guò)程，一般的遷移方法是將子群體中最好的個(gè)體發(fā)給其它的子群體，通過(guò)遷移可以加快較好個(gè)體在群體中的傳播，提高收斂速度和解的精度。最基本的遷移模型是環(huán)狀拓?fù)淠Ｐ?/SPAN>，如圖

1 所示。

(2)獨(dú)立型—粗粒度模型(coarse-grained model)：將種群分成若干個(gè)子群體并分配給各自對(duì)應(yīng)的處理器，每個(gè) 處理器不僅獨(dú)立計(jì)算適應(yīng)度，而且獨(dú)立進(jìn)行選擇、重組交叉和變異操作，還要定期地相互傳送適應(yīng)度最好的個(gè)體，

從而加快滿足終止條件的要求。粗粒度模型也稱島嶼模型 (island model)，基于粗粒度模型的遺傳算法也稱為分布式遺傳算法(Distributed Genetic Algorithm)，也是目前應(yīng)用最廣泛的一種并行遺傳算法。 (3)分散型—細(xì)粒度模型(fine-grained model)：為種群中的每一個(gè)個(gè)體分配一個(gè)處理器，每個(gè)處理器進(jìn)行適應(yīng) 度的計(jì)算，而選擇、重組交叉和變異操作僅在與之相鄰的一個(gè)處理器之間相互傳遞個(gè)體中進(jìn)行，細(xì)粒度模型也稱鄰域模型(neighborhood model)，適合于連接機(jī)、陣列機(jī)和 SIMD 系統(tǒng)。 1.2 遷移策略遷移(migration)是并行遺傳算法引入的一個(gè)新的算子，它是指在進(jìn)化過(guò)程中子群體間交換個(gè)體的過(guò)程，一般的遷移方法是將子群體中最好的個(gè)體發(fā)給其它的子群體，通過(guò)遷移可以加快較好個(gè)體在群體中的傳播，提高收斂速度和解的精度。最基本的遷移模型是環(huán)狀拓?fù)淠Ｐ�，如圖

1 所示。

1.3 并行遺傳算法的性能參數(shù) 為了評(píng)價(jià)并行算法的性能，人們提出了許多不同的評(píng)價(jià)指標(biāo)，其中最重要的一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)是加速比。設(shè)T 1 為

某算法在串行計(jì)算機(jī)上的運(yùn)行時(shí)間，T P 是該算法在由p 個(gè) 處理機(jī)所構(gòu)成的并行機(jī)上的運(yùn)行時(shí)間，則此算法在該并行機(jī)上的加速比S p 定義為：

, （1）并行遺傳算法的性能主要體現(xiàn)在收斂速度和精度兩

個(gè)方面，它們除了與遷移策略有關(guān)，還與一些參數(shù)選取的合理性密切相關(guān)，如遺傳代數(shù)、群體數(shù)目、群體規(guī)模、遷移率和遷移間隔。

2 計(jì)算機(jī)仿真

“系統(tǒng)仿真是通過(guò)對(duì)系統(tǒng)模型的實(shí)驗(yàn)，研究一個(gè)存在的或設(shè)計(jì)中的系統(tǒng)”[2] 。對(duì)于給定目標(biāo)，仿真過(guò)程可大致分為仿真建模、程序?qū)崿F(xiàn)、仿真結(jié)果的統(tǒng)計(jì)分析三大部分[3] 。其中仿真建模是最基礎(chǔ)的、關(guān)系整個(gè)仿真成敗的環(huán)節(jié)。如果有軟件能夠輔助用戶方便快捷地完成仿真建模工作，那么不僅可大大減少工作量，而且還可使用戶集中精力于提高建模質(zhì)量[4] 。

通過(guò)以上的概念分析，可以看出：仿真成敗的關(guān)鍵是仿真前的建模，模型建起來(lái)以后對(duì)輸入數(shù)據(jù)的優(yōu)化也很重要。因此，可以把并行遺傳算法應(yīng)用在計(jì)算機(jī)仿真中，從而來(lái)提高仿真的準(zhǔn)確度。

3 并行遺傳算法在計(jì)算機(jī)仿真中的應(yīng)用

并行遺傳算法敘述如下：

( 1) 基于對(duì)待解問(wèn)題的詳細(xì)分析，建立詳細(xì)的符合其特點(diǎn)的并行遺傳算法模型。

( 2) 基于并行遺傳算法模型確定仿真前各參數(shù)的實(shí)現(xiàn) 方案。

(3)運(yùn)用蒙特卡羅方法生成的大量隨機(jī)數(shù)，結(jié)合(2)的實(shí)現(xiàn)方案對(duì)隨機(jī)數(shù)進(jìn)行優(yōu)化。

( 4) 進(jìn)行仿真試驗(yàn)，得出仿真結(jié)果。

( 5) 若這個(gè)結(jié)果和預(yù)期理論結(jié)果不相符，則說(shuō)明仿真失敗，重新回到第一步。否則，此次仿真過(guò)程成功。仿真過(guò)程如圖2 所示。

遺傳算法在計(jì)算機(jī)仿真技術(shù)中的應(yīng)用張少剛面隨意地投擲長(zhǎng)度為 l 的細(xì)針, 設(shè)細(xì)針與平行線的垂直方向的夾角為a,則細(xì)針與平行線相交的概率為I=Ig∣cosa∣。

由于a 是在[0, π] 間均勻分布的，所以細(xì)針與平行線相交

的概率等于1/ ∣cosa ∣da=2/ π。設(shè)進(jìn)行了N 次投針試驗(yàn)，有M 次與平行線相交，當(dāng)N 足夠大時(shí)，細(xì)針與平行線相交的頻率就等于以上的概率，于是得到計(jì)算的π公式為： π=2N/M。

4.2 計(jì)算方法和結(jié)果

4.2.1 模型

在二維平面上畫(huà)三條相距為O.5 ，長(zhǎng)度為L 的平行線，取細(xì)針長(zhǎng)度為 O.5 ，如圖 3 所示，因?yàn)楸疚乃秒S機(jī)數(shù)在 [0 ，1] 之間，所以平行線的有效長(zhǎng)度為L ，也就是說(shuō)所有投擲試驗(yàn)都等效于在上述邊長(zhǎng)為 L 的正方形區(qū)域內(nèi)進(jìn)行的。

根據(jù)對(duì)這個(gè)問(wèn)題的分析，可以確定該仿真例子適合遺傳算法的第(1) 類全局型—主從式模型，基于并行遺傳算法模型確定仿真前各參數(shù)為x1、x2、y1、y2，其實(shí)現(xiàn)方案見(jiàn)

以下算法。

4.2.2 算法

(1)為計(jì)算作準(zhǔn)備，取總投針次數(shù)初始值N=0 ，相交次數(shù)M=0，設(shè)定總投針試驗(yàn)次數(shù)Nmax；

(2) 由蒙特卡羅方法產(chǎn)生兩個(gè)[O ，1] 間均勻分布的隨機(jī)數(shù)，并作為隨機(jī)構(gòu)造的細(xì)針的一個(gè)端點(diǎn)的坐標(biāo)(x 1 ,y 2 )； (3) 再產(chǎn)生一個(gè)隨機(jī)數(shù)，作為細(xì)針另一端點(diǎn)的橫坐標(biāo)

X2 ；

(4)如果∣x2-x1 ∣>0.5，說(shuō)明本次欲構(gòu)造的細(xì)針長(zhǎng)度已超過(guò)0.5 ，應(yīng)舍棄之，并回到上步；

(5) 利用細(xì)針長(zhǎng)度為0.5 這個(gè)約束條件，計(jì)算細(xì)針端點(diǎn)的縱坐標(biāo)y2=y1 ± ，如果y1>1 或y2<0，說(shuō)明

細(xì)針已不在選定的區(qū)域之內(nèi)，應(yīng)舍棄，回到(3 )；否則投針

有效，投針次數(shù)加1，N=N+1； (6)判斷細(xì)針是否與平行線相交如果x1>0．5 且x2>0．5,

或者x1<0．5 且x2<0．5，則細(xì)針與平行線不相交，回到(2)；

否則相交，并令M=M+1； (7)如果N=Nmax，試驗(yàn)結(jié)束，輸出結(jié)果，否則，(回到2)，

繼續(xù)下一次投針試驗(yàn)。

4.2.3 計(jì)算結(jié)果

4 投針試驗(yàn)

4.1 試驗(yàn)

圖2 仿真過(guò)程圖

著名的Bufon 投針實(shí)驗(yàn)是一種求π近似值的方法, 該方法是在平坦桌面上劃一組相距為 l 的平行線, 然后向桌

圖3 模擬計(jì)算結(jié)果

模擬計(jì)算結(jié)果如圖 3 所示，可以看出，基于并行遺傳

度和求解質(zhì)量。

參考文獻(xiàn)

算法模型確定的仿真前各參數(shù)的實(shí)現(xiàn)方案準(zhǔn)確，所得圓周率的計(jì)算精度比較高。因此，并行遺傳算法模型具有一定的實(shí)用性。

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

本文將遺傳算法應(yīng)用到計(jì)算機(jī)仿真技術(shù)中，提出了基于并行遺傳算法的仿真模型，并通過(guò)圓周率的計(jì)算，實(shí) 踐了它的應(yīng)用過(guò)程。成功地解決了一類多變量、多約束條件的線性仿真問(wèn)題。結(jié)果表明，PGA 有效地提高了運(yùn)行速