簡述

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

2.選擇策略

2.1輪盤賭選擇法

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

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

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

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

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

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

2.2 隨機(jī)遍歷抽樣法

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

2.3 錦標(biāo)賽選擇法

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

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

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

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

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

參考資料

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

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

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/legend1130/p/5333087.html

總結(jié)

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

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