遺傳算法在計算機仿真技術中的應用
摘 要：通過對隨機性問題進行計算機仿真，從而得出待解問題的解。提出了基于遺傳算法進行計算機仿真 的基本模型。通過圓周率的計算，實踐了該模型的應用過程。實踐證明，該模型在進行計算機仿真時準確度比較高。 關鍵詞：蒙特卡羅方法；；隨機數；遺傳算法0 引 言
計算機的出現和計算技術的發展為仿真技術的發展 提供了強有力的手段和工具。最近幾年，隨著計算機的迅 速發展和普及，尤其是微型計算機的發展和普及，很多大 計算量的仿真系統得以實現，并在國民生產、科學研究等 領域得到廣泛的應用。
現代科技發展中提出愈來愈復雜的隨機性問題, 除極 少數外, 要想通過仿真給出其嚴格解是困難的, 用確定性 方法給出其近似解也很困難, 甚至不可能。遺傳算法 GA (Genetic Algorithm)[1]是模擬生物進化的優化算法，把遺 傳算法GA 應用到仿真技術中，是一種很強的特殊的數值 方法。
1 遺傳算法[ 1 ]
1.1 并行遺傳算法實現方案 目前并行遺傳算法的實現方案大致可分為3 類： (1)全局型—主從式模型(master-slave model)：并行
系統分為一個主處理器和若干個從處理器。主處理器監控 整個染色體種群，并基于全局統計執行選擇操作；各個從 處理器接受來自主處理器的個體進行重組交叉和變異，產 生新一代個體，并計算適應度，再把計算結果傳給主處理
器。
從而加快滿足終止條件的要求。粗粒度模型也稱島嶼模型
(island model)，基于粗粒度模型的遺傳算法也稱為分布 式遺傳算法(Distributed Genetic Algorithm)，也是目 前應用最廣泛的一種并行遺傳算法。
(3)分散型—細粒度模型(fine-grained model)：為種 群中的每一個個體分配一個處理器，每個處理器進行適應 度的計算，而選擇、重組交叉和變異操作僅在與之相鄰的 一個處理器之間相互傳遞個體中進行，細粒度模型也稱鄰 域模型(neighborhood model)，適合于連接機、陣列機和 SIMD 系統。
1.2 遷移策略
遷移(migration)是并行遺傳算法引入的一個新的算 子，它是指在進化過程中子群體間交換個體的過程，一般 的遷移方法是將子群體中最好的個體發給其它的子群體， 通過遷移可以加快較好個體在群體中的傳播，提高收斂速 度和解的精度。最基本的遷移模型是環狀拓撲模型，如圖
1 所示。
1.3 并行遺傳算法的性能參數 為了評價并行算法的性能，人們提出了許多不同的 評價指標，其中最重要的一個評價標準是加速比。設T 1 為
個方面，它們除了與遷移策略有關，還與一些參數選取的 合理性密切相關，如遺傳代數、群體數目、群體規模、遷 移率和遷移間隔。
2 計算機仿真
“系統仿真是通過對系統模型的實驗，研究一個存在 的或設計中的系統”[2] 。對于給定目標，仿真過程可大致分 為仿真建模、程序實現、仿真結果的統計分析三大部分[3] 。 其中仿真建模是最基礎的.、關系整個仿真成敗的環節。如 果有軟件能夠輔助用戶方便快捷地完成仿真建模工作，那 么不僅可大大減少工作量，而且還可使用戶集中精力于提 高建模質量[4] 。
通過以上的概念分析，可以看出：仿真成敗的關鍵是 仿真前的建模，模型建起來以后對輸入數據的優化也很重 要。因此，可以把并行遺傳算法應用在計算機仿真中，從 而來提高仿真的準確度。
3 并行遺傳算法在計算機仿真中的應用
并行遺傳算法敘述如下：
( 1) 基于對待解問題的詳細分析，建立詳細的符合其 特點的并行遺傳算法模型。
( 2) 基于并行遺傳算法模型確定仿真前各參數的實現 方案。
(3)運用蒙特卡羅方法生成的大量隨機數，結合(2)的 實現方案對隨機數進行優化。
( 4) 進行仿真試驗，得出仿真結果。
遺傳算法在計算機仿真技術中的應用 張少剛 面隨意地投擲長度為 l 的細針, 設細針與平行線的垂直方 向的夾角為a,則細針與平行線相交的概率為I=Ig∣cosa∣。
由于a 是在[0, π] 間均勻分布的，所以細針與平行線相交
的概率等于1/
4.2 計算方法和結果
4.2.1 模型
在二維平面上畫三條相距為O.5 ，長度為L 的平行線， 取細針長度為 O.5 ，如圖 3 所示，因為本文所用隨機數在 [0 ，1] 之間，所以平行線的有效長度為L ，也就是說所有投 擲試驗都等效于在上述邊長為 L 的正方形區域內進行的。
根據對這個問題的分析，可以確定該仿真例子適合 遺傳算法的第(1) 類全局型—主從式模型，基于并行遺傳 算法模型確定仿真前各參數為x1、x2、y1、y2，其實現方案見
以下算法。
4.2.2 算法
(1)為計算作準備，取總投針次數初始值N=0 ，相交次 數M=0，設定總投針試驗次數Nmax；
(2) 由蒙特卡羅方法產生兩個[O ，1] 間均勻分布的隨 機數，并作為隨機構造的細針的一個端點的坐標(x 1 ,y 2 )； (3) 再產生一個隨機數，作為細針另一端點的橫坐標
X2 ；
(4)如果∣x2-x1 ∣>0.5，說明本次欲構造的細針長度已 超過0.5 ，應舍棄之，并回到上步；
(5) 利用細針長度為0.5 這個約束條件，計算細針端 點的縱坐標y2=y1 ±
細針已不在選定的區域之內，應舍棄，回到(3 )；否則投針
有效，投針次數加1，N=N+1； (6)判斷細針是否與平行線相交如果x1>0．5 且x2>0．5,
或者x1<0．5 且x2<0．5，則細針與平行線不相交，回到(2)；
否則相交，并令M=M+1； (7)如果N=Nmax，試驗結束，輸出結果，否則，(回到2)，
繼續下一次投針試驗。
4 投針試驗
4.1 試驗
圖2 仿真過程圖
著名的Bufon 投針實驗是一種求π近似值的方法, 該 方法是在平坦桌面上劃一組相距為 l 的平行線, 然后向桌
圖3 模擬計算結果
模擬計算結果如圖 3 所示，可以看出，基于并行遺傳
度和求解質量。
參考文獻
算法模型確定的仿真前各參數的實現方案準確，所得圓周 率的計算精度比較高。因此，并行遺傳算法模型具有一定 的實用性。
5 結束語
本文將遺傳算法應用到計算機仿真技術中，提出了 基于并行遺傳算法的仿真模型，并通過圓周率的計算，實 踐了它的應用過程。成功地解決了一類多變量、多約束條 件的線性仿真問題。結果表明，PGA 有效地提高了運行速
1 Holland J. Adaptation in Natural and Artificial Systems
[M].Michigan:University of Michigan Press,2005
2 李書臣, 趙禮峰. 仿真技術的現狀及發展[J].自動化與儀表,
2004,14(6):1～4
3 徐庚保.系統仿真的過去、現在和未來[J].計算機仿真,2006,
15(3):2～4
4 惠天舒,李裕山,陳宗基.仿真模型的可重用性研究[J].北京航 空航天大學學報,2008,25(3):329～333
【遺傳算法在計算機仿真技術中的應用】相關文章：