遺傳算法在計算機仿真技術中的應用

時間：2024-10-13 21:10:44 計算機應用畢業論文我要投稿

相關推薦

遺傳算法在計算機仿真技術中的應用

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

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 所示。

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

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

1 所示。

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

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

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

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

2 計算機仿真

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