遺傳算法論文：淺談遺傳算法的研究與改進

《遺傳算法論文：淺談遺傳算法的研究與改進》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、遺傳算法論文：淺談遺傳算法的研究與改進【摘要】遺傳算法是模擬自然界生物進化機制的概率性搜索算法，可以處理傳統(tǒng)搜索方法難以解決的非線性問題。但是經(jīng)典遺傳算法存在局部收斂、收斂速度慢等缺點，這使得經(jīng)典遺傳算法有時很難找到全局最優(yōu)解。本文針對經(jīng)典遺傳算法中所存在的缺點，采用階段式的適應度函數(shù)、基于競爭機制的交叉方式和仿粒子群變異操作，使遺傳算法的收斂速率、全局收斂概率都得到了較大的提高。【關(guān)鍵詞】遺傳算法適應度交叉操作仿粒子群變異一遺傳算法遺傳算法（geneticalgorithm，簡稱ga）是holland在研究自然遺傳現(xiàn)象與人工系統(tǒng)的自適

2、應行為時，模擬生物進化現(xiàn)象，并采用自然進化機制來表現(xiàn)復雜現(xiàn)象的一種全局群體搜索算法。遺傳算法的基本思想起源于darwin進化論和mendel的遺傳學說。作為一類智能計算工具和學習算法，由于其實現(xiàn)簡單、對目標函數(shù)要求不高等特性，遺傳算法已廣泛應用于如人工智能、組合優(yōu)化等研究領域。1．遺傳算法的優(yōu)越性遺傳算法（geneticalgorithm）利用某種編碼技術(shù)作用在稱為染色體的二進制串上，模擬由這些串組成的個體的進化過程。通過有組織的、隨機的信息交換來重新結(jié)合那些適應性好的串，在每一代中，利用上一代串結(jié)構(gòu)中適應性好的位和段來形成一個新的串的

3、群體，同時在串結(jié)構(gòu)中嘗試用新的位和段來代替原來的部分以形成新的個體，以增加種群的多樣性。遺傳算法的最大優(yōu)點是能夠通過群體間的相互作用，保存已經(jīng)搜索到的信息，這是基于單次搜索過程的優(yōu)化方法所無法比擬的。但是，遺傳算法也存在著計算速度較慢，并且容易陷入局部最優(yōu)解的問題中。遺傳算法的優(yōu)越性歸功于它與傳統(tǒng)搜索方法不同的特定結(jié)構(gòu)。第一，遺傳算法的操作對象是編碼，對問題的限制極少，對函數(shù)的一些約束條件如連續(xù)性、可導性等不做要求，減少了要解決問題的復雜性。第二，遺傳算法同時搜索解空間內(nèi)的許多點，因而可以有效地防止搜索過程中收斂到局部最優(yōu)解，并獲得全局

4、最優(yōu)解，與其他單點搜索的方法相比，在計算時間上也有較大的優(yōu)勢。第三，遺傳算法使用遺傳操作時是按概率在解空間進行搜索，因而既不同于隨機搜索，也不同于枚舉法那樣盲目地舉例，而是一種有目標、有方向的啟發(fā)式搜索。2．遺傳算法的基本步驟遺傳算法的實現(xiàn)中包括復制、交叉、變異三個算子，需要確定關(guān)鍵的幾個參數(shù)與標準包括：種群規(guī)模、基因編碼、適值函數(shù)、選擇概率、遺傳算子以及停機準則。下面分別對其進行說明：第一，表示法與適應度計算。標準遺傳算法（二進制編碼）作用于確定長度的二進制位串上，即i＝{0，1}l。假設需要解決如下函數(shù)優(yōu)化問題，一般是將位串分為n段

5、，每段長度為lx，即l＝nlx，每段表示分量xi∈［ui，vi］的二進制代碼。位段譯碼函數(shù)的常見形式為：…（1）其中…記為個體…的第i段。把位段譯碼函數(shù)組合成一個個體的譯碼函數(shù)…，則適應度函數(shù)可設置為，其中δ為比例變換函數(shù)，作用之一是確保適應值為正值，并且最好使個體的適應度值最大。常見的比例變換有線性比例、冪比例和指數(shù)比例等。第二，交叉。交叉操作是將已有個體組合出新個體，使兩個個體的有效信息得以遺傳到下一代，并可能得到新的個體信息。在遺傳算法中，交叉操作是主要的遺傳操作，它把兩個不同個體上的有用段組合在一起，ga的性能在很大的程度上依賴

6、所使用的交叉算子。交叉操作算子r'∶iμ→i也是作用在位串上，以概率pc對兩個個體進行交叉，pc的作用范圍一般為［0.6，1.0］。兩個父輩個體s＝（s1，…，sl），v＝（v1，…，vl）被隨機地從群體中選擇而進行交叉，產(chǎn)生了兩個子代個體：s'＝（s1，…，sh－1，sh，vh－1，…，vl，）（2）v'＝（v1，…，vh－1，vh，sh－1，…，sl，）（3）其中交叉點h為1到l之間的一個隨機整數(shù)。這種交叉即為一點交叉，通過選擇更多的交叉點并交替地變換交叉點之間的位段，就可以把一點交叉擴展到m點交叉算子。另外還有一些其他形式的交叉算

7、子，如一致交叉算子等。不過目前還沒有明確的理論或可靠的實驗證據(jù)來決定哪一種交叉算子是最適合的。第三，變異。變異操作的目的是通過隨機改變?nèi)旧w的某些基因來引入新個體，增加種群多樣性，并在一定程序上進行局部搜索。相對于交叉操作，變異操作的設計和實現(xiàn)更為簡單和靈活。在標準遺傳算法中，變異一般被看作為輔助算子，它作用在位串上，以較小的概率pm隨機地改變串上的每一位（即相應位上的0變?yōu)?，或者1變?yōu)?）。變異概率pm的值一般為0.001到0.01之間，它不依賴目標變量的維數(shù)和位串的總長。個體（s1，…，sl）經(jīng)變異算子作用后變?yōu)椋ā渲校骸?/p>

8、4）這里θi是0與1之間的一致隨機數(shù)，對串上的每一位都要重新采樣。常用的變異操作包括：（1）互換：隨機變換若干不同位置上的不同基因。（2）逆序：將某兩隨機位置間的基因串逆序。（3）插入：即將某一位置上的基因