簡述

　　遺傳算法(GA)是一種模擬生物進化自然選擇過程的非確定性搜索方法，源于達爾文的進化論和孟德爾的遺傳定律，由美國 Michigan 大學的 Holland教授在 20 世紀 70 年代首先提出。生物理論指出， 生物個體的各種生命表征是由許多基因共同決定的。同一種群的不同生物個體通常擁有不同的基因，因此對外在環(huán)境的適應(yīng)能力也是不同的。 在自然選擇的作用下，一部分環(huán)境適應(yīng)能力較差的個體會死亡被淘汰，而環(huán)境適應(yīng)能力較強的個體則更多地存活下來并繁衍后代， 因此比較適應(yīng)環(huán)境的基因會有較大的概率流傳到下一代。 一般情況下子代的平均適應(yīng)力普遍強于父代。 在基因從父代傳遞到子代的過程中，一部分基因會因為變異而在子代中產(chǎn)生新的基因，這種變異是隨機的，有可能增強子代個體的環(huán)境適應(yīng)力，也有可能會降低子代個體的適應(yīng)力。
　　遺傳算法正是仿照上述理論，將一個問題的解空間編碼，每一個編碼代表一個個體，建立一個包含潛在的解的群體作為種群，在環(huán)境作用下通過選擇(selection)、交叉(crossover)和變異(mutation)一代代繁衍，由于子代的環(huán)境適應(yīng)力一般優(yōu)于父代，因此算法最終能夠得到問題的較優(yōu)解。其中，編碼中的每一位代表一個基因，環(huán)境作用由適應(yīng)度函數(shù)模擬，適應(yīng)度函數(shù)是判斷某個解的優(yōu)劣程度的函數(shù)，通常是目標函數(shù)本身或其修改形式。選擇又稱為選擇算子，是指參照適應(yīng)值函數(shù)，按照預先選定的策略隨機從父代中挑選一些個體生存下來，剩下的個體則被淘汰。交叉是指仿照自然界基因傳遞的過程交配，對存活下來的父代個體的某些基因進行優(yōu)化組合，辦法是將兩個父代個體某些對應(yīng)位置的基因互換，以產(chǎn)生新的個體。變異是指對編碼的某些位置上的基因按一定概率進行的改變。

2.選擇策略

2.1輪盤賭選擇法

輪盤賭選擇法是依據(jù)個體的適應(yīng)度值計算每個個體在子代中出現(xiàn)的概率，并按照此概率隨機選擇個體構(gòu)成子代種群。輪盤賭選擇策略的出發(fā)點是適應(yīng)度值越好的個體被選擇的概率越大。因此，在求解最大化問題的時候，我們可以直接采用適應(yīng)度值來進行選擇。但是在求解最小化問題的時候，我們必須首先將問題的適應(yīng)度函數(shù)進行轉(zhuǎn)換，以將問題轉(zhuǎn)化為最大化問題。下面給出最大化問題求解中遺傳算法輪盤賭選擇策略的一般步驟：

(1)??將種群中個體的適應(yīng)度值疊加，得到總適應(yīng)度值==1 ，其中 為種群中個體個數(shù)。

(2)??每個個體的適應(yīng)度值除以總適應(yīng)度值得到個體被選擇的概率

(3)??計算個體的累積概率以構(gòu)造一個輪盤。

(4)??輪盤選擇：產(chǎn)生一個[0,1]區(qū)間內(nèi)的隨機數(shù)，若該隨機數(shù)小于或等于個體的累積概率且大于個體1的累積概率，選擇個體進入子代種群。

重復步驟(4)次，得到的個體構(gòu)成新一代種群。

2.2 隨機遍歷抽樣法

像輪盤賭一樣計算選擇概率，只是在隨機遍歷選擇法中等距離的選擇體，設(shè)npoint為需要選擇的個體數(shù)目，等距離的選擇個體，選擇指針的距離是1/npoint，第一個指針的位置由[0，1/npoint]的均勻隨機數(shù)決定。

2.3 錦標賽選擇法

錦標賽方法選擇策略每次從種群中取出一定數(shù)量個體，然后選擇其中最好的一個進入子代種群。重復該操作，直到新的種群規(guī)模達到原來的種群規(guī)模。具體的操作步驟如下：

(1)?確定每次選擇的個體數(shù)量(本文以占種群中個體個數(shù)的百分比表示)。

(2)?從種群中隨機選擇個個體(每個個體入選概率相同) 構(gòu)成組，根據(jù)每個個體的適應(yīng)度值，選擇其中適應(yīng)度值最好的個體進入子代種群。

(3) 重復步驟(2)次，得到的個體構(gòu)成新一代種群。

需要注意的是，錦標賽選擇策略每次是從個個體中選擇最好的個體進入子代種群，因此可以通用于最大化問題和最小化問題，不像輪盤賭選擇策略那樣，在求解最小化問題的時候還需要將適應(yīng)度值進行轉(zhuǎn)換。

參考資料

　　[1]遺傳算法:理論、應(yīng)用及軟件實現(xiàn)/王小平, 曹立明著 西安交通大學出版社,2002

　　[2]張琛,詹志輝. 遺傳算法選擇策略比較[J]. 計算機工程與設(shè)計,2009,23:5471-5474+5478

文章轉(zhuǎn)自：https://www.cnblogs.com/legend1130/archive/2016/03/29/5333087.html

總結(jié)

以上是生活随笔為你收集整理的遗传算法中常用的选择策略的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。