當前位置:首頁 » 操作系統 » 遺傳演算法的步驟

遺傳演算法的步驟

發布時間: 2024-02-23 21:44:28

❶ 遺傳演算法的主要步驟

為了使用遺傳演算法來解決優化問題,准備工作分為以下四步[56,57,61]

7.4.1 確定問題的潛在解的遺傳表示方案

在基本的遺傳演算法中,表示方案是把問題的搜索空間中每個可能的點表示為確定長度的特徵串(通常是二進制串)。表示方案的確定需要選擇串長l和字母表規模k。在染色體串和問題的搜索空間中的點之間選擇映射有時容易實現,有時又非常困難。選擇一個便於遺傳演算法求解問題的表示方案經常需要對問題有深入的了解。

7.4.2 確定適應值的度量

適應值度量為群體中每個可能的確定長度的特徵串指定一個適應值,它經常是問題本身所具有的。適應值度量必須有能力計算搜索空間中每個確定長度的特徵串的適應值。

7.4.3 確定控制該演算法的參數和變數

控制遺傳演算法的主要參數有群體規模Pop-Size、演算法執行的最大代數N-Gen、交叉概率Pc、變異概率Pm和選擇策略R等參數。

(1)群體規模Pop-Size。群體規模影響到遺傳演算法的最終性能和效率。當規模太小時,由於群體對大部分超平面只給出了不充分的樣本量,所以得到的結果一般不佳。大的群體更有希望包含出自大量超平面的代表,從而可以阻止過早收斂到局部最優解;然而群體越大,每一代需要的計算量也就越多,這有可能導致一個無法接受的慢收斂率。

(2)交叉率Pc。交叉率控制交叉運算元應用的頻率,在每代新的群體中,有Pc·Pop-Size個串實行交叉。交叉率越高,群體中串的更新就越快。如果交叉率過高,相對選擇能夠產生的改進而言,高性能的串被破壞得更快。如果交叉率過低,搜索會由於太小的探查率而可能停滯不前。

(3)變異率Pm。變異是增加群體多樣性的搜索運算元,每次選擇之後,新的群體中的每個串的每一位以相等的變異率進行隨機改變。對於M進制串,就是相應的位從1變為0或0變為1。從而每代大約發生Pm·Pop-Size·L次變異,其中L為串長。一個低水平的變異率足以防止整個群體中任一給定位保持永遠收斂到單一的值。高水平的變異率產生的實質是隨機搜索。

比起選擇和交叉,變異在遺傳演算法中是次要的,它在恢復群體中失去的多樣性方面具有潛在的作用。例如,在遺傳演算法執行的開始階段,串中一個特定位上的值1可能與好的性能緊密聯系,也就是說從搜索空間中某些初始隨機點開始,在那個位上的值1可能一致地產生適應性度量好的值。因為越好的適應值與串中那個位上的值1相聯系,復製作用就越會使群體的遺傳多樣性損失。當達到一定程度時,值0會從整個群體中的那個位上消失,然而全局最優解可能在串中那個位上是0。一旦搜索范圍縮小到實際包含全局最優解的那部分搜索空間,在那個位上的值0就可能正好是達到全局最優解所需的。這僅僅是一種說明搜索空間是非線性的方式,這種情形不是假定的,因為實際上所有我們感興趣的問題都是非線性的。變異作用提供了一個恢復遺傳多樣性的損失的方法。

(4)選擇策略R。有兩種選擇策略。一是利用純選擇,即當前群體中每個點復制的次數比與點的性能值成比例。二是利用最優選擇,即首先執行純選擇,且具有最好性能的點總是保留到下一代。在缺少最優選擇的情況下,由於采樣誤差、交叉和變異,最好性能的點可能會丟失。

通過指定各個參數Pop-Size、Pc、Pm和R的值,可以表示一個特定的遺傳演算法。

7.4.4 確定指定結果的方法和停止運行的准則

當遺傳的代數達到最大允許代數時,就可以停止演算法的執行,並指定執行中得到的最好結果作為演算法的結果。

基本的遺傳演算法

1)隨機產生一個由固定長度字元串組成的初始群體。

2)對於字元串群體,迭代地執行下述步驟,直到選擇標准被滿足為止。

①計算群體中的每個個體字元串的適應值;

②實施下列三種操作(至少前兩種)來產生新的群體,操作對象的選取基於與適應度成比例的概率。

選擇:把現有的個體串按適應值復制到新的群體中。

交叉:通過遺傳重組隨機選擇兩個現有的子串進行遺傳重組,產生兩個新的串。

變異:將現有串中某一位的字元隨機變異產生一個新串。

3)把在後代中出現的最好適應值的個體串指定為遺傳演算法運行的結果。這一結果可以是問題的解(或近似解)。

基本的遺傳演算法流程圖如圖7-1所示。

❷ 遺傳演算法理解

遺傳演算法是一種進化演算法,進化是什麼哪?就是種群逐漸適應生存環境,種群中個體不斷得到改良的過程。

遺傳演算法是一種對生物遺傳的模擬、在演算法中,初始化一個種群,種群中的每個染色體個體都是一種解決方案,我們通過適應性fitness來衡量這個解決方案的好壞。並對它們進行選擇、變異、交叉的操作,找到最優的解決方案。

總結一下遺傳演算法的基本的步驟:

1.初始化一個種群,並評估每條染色體所對應個體的適應度。

2.選擇、交叉、變異,產生新的種群

3.再評估每個個體的適應值,如果適應值達到要求或者達到最大循環次數,否則重復2,不斷產生新種群。

知道了GA的大致流程之後、來具體分析一下細節,怎麼實現吧

我們知道遺傳演算法起源於生物遺傳,因此在種群中每個個體就是一個染色體,那如何對染色體進行編碼,讓它表示我們的解決方案那(就是把現實要優化的參數用編碼表示成一個染色體)。這里就遇到了一個編碼、解碼的問題,我們將需要優化的目標編碼成染色體,然後再解碼為我們可以用來計算fitness的解;

一般在進行參數優化時,一般有兩種方式:實數編碼、二進制編碼

實數編碼:基因直接用實數進行表示,這樣的表示方法比較簡單,不用特意解碼了,但是在交叉和變異時,容易過早收斂,陷入局部最優。

二進制編碼:將基因用二進制的形式表示,將參數的值轉化為二進制形式,這樣交叉、變異時更好操作,多樣性好,但是佔用的存儲空間大,需要解碼。

染色體就稱為個體。對於一次實驗,個體就是需要優化參數的一種解、許多這樣的個體就構成了種群。

在面對群體中那麼多個體時,如何判斷個體的好壞呢,就是通過適應值函數了,將解帶入適應值函數,適應值越大、解越好。

在遺傳演算法中,我們怎麼使得裡面的個體變得越來越優秀呢?

核心思想就是:選擇優秀的、淘汰不好的,並且為了生成更好的解,我們要嘗試交叉、變異,帶來新的解。

選擇就是從當前的種群中選擇出比較好的個體、淘汰不好的個體

常見的選擇方法有:輪盤賭選擇、錦標賽選擇、最佳保留選擇等等

輪盤賭選擇就是根據每個個體fitness和種群所有fitness之和比較,確定每個個體被選中的概率,然後進行n次選擇,選擇n個個體構成新種群,是一種放回抽樣的方式。

錦標賽就是每次從種群中選擇m個個體,選擇最優的,放入新種群,重復選擇,直到新種群中個體數目達到n。

最佳保留選擇就是在輪盤賭的基礎上,將fitness個體先加進新種群,因為輪盤賭是一種概率模型,可能存在最優個體沒有進入新種群的情況。

在選擇之後,就要考慮產生新的、更優秀的解,為種群帶來新的血液。遺傳演算法的思路是交叉兩個優秀的解,往往get好的解。

交叉通過在經過選擇的種群中,隨機選擇一對父母,將它們的染色體進行交叉,生成新的個體,替代原來的解。

常用的交叉方法有:單點交叉、多點交叉等等。

交叉就像生物裡面,染色體交換基因一樣的~但是並不是種群中所有個體都進行交叉的,實現時可以,設置一個交叉率和交叉概率,隨機選擇種群中兩個體、隨機一個數,小於交叉率就進行交叉操作,並根據交叉概率判斷交叉的程度,從而生成新個體,反之就保留這兩個體。

變異也是一種產生新個體的方式,通過改變個體上基因,期望產生更好的解。比如在以二進制編碼的個體上,將裡面的0、1進行等位變化啥的,就是0變1、1變0這樣。同樣也要考慮變異率、變異產生的新解是不可控的,可能很好,也可能很壞,不能像交叉一樣,確保一定的效果,所以往往變異率設置的比較小。

❸ 用matlab遺傳演算法分析運動方式

(1)首先計算出所有個體的適應度總和Σfi。
(2)其次計算出每個個體的相對適應度大小fi/Σfi,類似於softmax。
(3)再產生一個0到1之間的隨機數,依據隨機數出現在上述哪個概率區域內來確定各個個體被選中的次數。
(4)交叉(交配)運算。該步驟是遺傳演算法中產生新的個體的主要操作過程,它用一定的交配概率閾值(pc,一般是0.4到0.99)來控制是否採取單點交叉,多點交叉等方式生成新的交叉個體。
具體步驟如下: (1)先對群體隨機配對。(2)再隨機設定交叉點的位置。 (3)再互換配對染色體間的部分基因。
(5)變異運算。該步驟是產生新的個體的另一種操作。一般先隨機產生變異點,再根據變異概率閾值(pm,一般是0.0001到0.1)將變異點的原有基因取反。

❹ 如何用遺傳演算法實現多變數的最優化問題

將多個變數的數值編碼編排進去,進行組合,只需要增長基因個體的燃搭長度,但是要明確每個變數具體的位置,然後讓每個變數轉化成二進制的等長編碼,組合在一起,就可以來運算了。

❺ 變異操作是維持全體多樣性的關鍵正確嗎

正確。首先用最簡單的例子來介紹遺傳演算法
例:用遺傳演算法求y = x在[-1, 1]上的最小值。

步驟一:選擇二進制編碼,及將[-1, 1]上的數向[0000000000 1111111111]映射,例將-1映射為0000000000, 1映射為1111111111。
步驟二:初始化種群。隨意生成50個10位二進制數作為初始種群。
步驟三:適應度計算。由於我們要求最小值,所以我們將適應度函數設租跡擾為弊旦F = 1 / y。,然後計算初始種群的個體適應度。
步驟四:選擇操作。常見的選擇運算元有輪盤賭法,即基於適應度比例的選擇策略,個體i被選中的概率為

步驟五:交叉操作。交叉操作是指從種群中隨機選擇兩個個體,通過兩個個體的交換組合得到新的個體,例兩個個體為1010101010和0101010101,交換其後兩位得到1010101001和0101010110。
步驟六:變異操作。變異操作主要目的是維持種群多樣性。例:將 1010101010變異成1010101011。
重復步驟三到六,迭代500次,最後種群中的適應度最高的個體即為得到的最優解。

遺傳演算法的不足

全局搜索能力極強而局部尋優能力較差。研究發現,遺傳演算法可以用幾極快的速度達到最優解的90%左右,但要達到真正的最優解則需要花費很長的時間。
易出現早熟收斂現象。當種群規模較小,如果在進化初期出現適應度較高的個體,由於個別優勢個體繁殖過快,往往會破壞群體的多樣性,從而出現早熟收斂現象。

遺傳演算法的改進

為改善遺傳演算法的局部搜索能力,在變異操作後加上進化逆轉操作。例隨機變換一個個體中的兩個部分交換,如果這種操州告作使得適應度增強,則保留,否則不變。
使用精英策略,子代種群中的最優個體永遠不會比父代的個體差。父代中的精英會原封不動地直接傳給子代,而不經過交叉或變異操作。
多種群遺傳演算法,多個種群同時進化,然後加入移民運算元,將個體在種群之間交換。

量子遺傳演算法,每一個二進制位有兩個糾纏的量子表示,只有當測量的時候才知道其真實值。然後用量子旋轉操作代替選擇、交叉和變異操作。

作者:小鵬不會飛
鏈接:https://juejin.cn/post/6861568236341723149
來源:稀土掘金
著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請註明出處。

熱點內容
英雄聯盟和飢荒哪個配置要求更高 發布:2024-04-24 07:55:09 瀏覽:602
linuxcpu佔用進程 發布:2024-04-24 07:37:05 瀏覽:119
河南移動鶴壁dns伺服器地址 發布:2024-04-24 07:36:58 瀏覽:592
百度賬號密碼怎麼設置密碼 發布:2024-04-24 07:27:37 瀏覽:759
cf窗口化源碼 發布:2024-04-24 07:04:33 瀏覽:738
linuxi2c設備 發布:2024-04-24 06:53:50 瀏覽:346
寶馬x5買什麼配置性價比高 發布:2024-04-24 06:45:22 瀏覽:850
最小的編程語言 發布:2024-04-24 06:44:16 瀏覽:817
自動發朋友圈腳本 發布:2024-04-24 06:40:32 瀏覽:154
最早存儲盤 發布:2024-04-24 06:39:54 瀏覽:944