遺傳算法在計算機仿真技術(shù)中的應用

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

0      引 言

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

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

 

 

1      遺傳算法[ 1 ]

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

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

器。

從而加快滿(mǎn)足終止條件的要求。粗粒度模型也稱(chēng)島嶼模型

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

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

1.2 遷移策略

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

1 所示。

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

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

1 所示。

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

 

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

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

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

 

 

2     計算機仿真

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

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

 

 

3     并行遺傳算法在計算機仿真中的應用

并行遺傳算法敘述如下：

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

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

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

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

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

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

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

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

4.2 計算方法和結果

4.2.1 模型

在二維平面上畫(huà)三條相距為O.5 ，長(cháng)度為L 的平行線(xiàn)， 取細針長(cháng)度為 O.5 ，如圖 3 所示，因為本文所用隨機數在 [0 ，1] 之間，所以平行線(xiàn)的有效長(cháng)度為L ，也就是說(shuō)所有投 擲試驗都等效于在上述邊長(cháng)為 L 的正方形區域內進(jìn)行的。

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

以下算法。

4.2.2 算法

(1)為計算作準備，取總投針次數初始值N=0 ，相交次 數M=0，設定總投針試驗次數Nmax；

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

X2 ；

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

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

細針已不在選定的區域之內，應舍棄，回到(3 )；否則投針

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

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

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

繼續下一次投針試驗。

4.2.3 計算結果

 

 

 

 

 

 

4     投針試驗

4.1 試驗

圖2 仿真過(guò)程圖

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

圖3 模擬計算結果

 

模擬計算結果如圖 3 所示，可以看出，基于并行遺傳

度和求解質(zhì)量。

 

參考文獻

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

5      結束語(yǔ)

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

1   Holland J. Adaptation in Natural and Artificial Systems

[M].Michigan:University of Michigan Press,2005

2  李書(shū)臣, 趙禮峰. 仿真技術(shù)的現狀及發(fā)展[J].自動(dòng)化與儀表,

2004,14(6):1～4

3  徐庚保.系統仿真的過(guò)去、現在和未來(lái)[J].計算機仿真,2006,

15(3):2～4

4  惠天舒,李裕山,陳宗基.仿真模型的可重用性研究[J].北京航 空航天大學(xué)學(xué)報,2008,25(3):329～333

            

【遺傳算法在計算機仿真技術(shù)中的應用】相關(guān)文章：

計算機仿真技術(shù)的發(fā)展應用09-20

計算機仿真技術(shù)的發(fā)展應用論文09-23

遺傳算法及其在求解TSP中的應用09-22

淺談?dòng)嬎銠C仿真技術(shù)在21世紀航海教育中的發(fā)展與應用09-03

計算機三維仿真技術(shù)在復雜足踝部骨折手術(shù)中的應用09-12

基于遺傳算法的模型在交通線(xiàn)路選擇中的應用08-09

翻轉課堂在中職“計算機應用基礎”教學(xué)中的應用06-08

計算機應用技術(shù)在信息整合中的應用07-15

iFIX軟件在計算機中的應用10-21

高職計算機應用基礎教學(xué)中微課的應用分析06-19