?????????????組成：

? 編碼 －＞ 創(chuàng)造染色體

? 個(gè)體 －＞ 種群

? 適應(yīng)度函數(shù)

? 遺傳算子

      ? 選擇

      ? 交叉

      ? 變異

? 運(yùn)行參數(shù)

      ? 是否選擇精英操作

      ? 種群大小

      ? 染色體長(zhǎng)度

      ? 最大迭代次數(shù)

      ? 交叉概率

      ? 變異概率

編碼與解碼：

實(shí)現(xiàn)遺傳算法的第一步就是明確對(duì)求解問題的編碼和解碼方式。
對(duì)于函數(shù)優(yōu)化問題，一般有兩種編碼方式，各具優(yōu)缺點(diǎn)。

實(shí)數(shù)編碼：直接用實(shí)數(shù)表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優(yōu)；

二進(jìn)制編碼：穩(wěn)定性高，種群多樣性大，但需要的存儲(chǔ)空間大，需要解碼且難以理解。

對(duì)于求解函數(shù)最大值問題，我一般選擇二進(jìn)制編碼：

以目標(biāo)函數(shù) f（x） ＝ x ＋ 10sin（5x） ＋ 7cos（4x）， x∈［0，9］ 為例。

假如設(shè)定求解的精度為小數(shù)點(diǎn)后4位，可以將x的解空間劃分為 （9－0）×（1e＋4）＝90000個(gè)等分。

2＾16＜90000＜2＾17，需要17位二進(jìn)制數(shù)來表示這些解。換句話說，一個(gè)解的編碼就是一個(gè)17位的二進(jìn)制串。

一開始，這些二進(jìn)制串是隨機(jī)生成的。

一個(gè)這樣的二進(jìn)制串代表一條染色體串，這里染色體串的長(zhǎng)度為17。

對(duì)于任何一條這樣的染色體chromosome，如何將它復(fù)原（解碼）到［0，9］這個(gè)區(qū)間中的數(shù)值呢？

對(duì)于本問題，我們可以采用以下公式來解碼：

x ＝ 0 ＋ decimal（chromosome）×（9－0）／（2＾17－1）decimal（ ）： 將二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)

一般化解碼公式：

f（x）， x∈［lower＿bound， upper＿bound］x ＝ lower＿bound ＋ decimal（chromosome）×（upper＿bound－lower＿bound）／（2＾chromosome＿size－1）f（x）， x∈［lower＿bound， upper＿bound］x ＝ lower＿bound ＋ decimal（chromosome）×（upper＿bound－lower＿bound）／（2＾chromosome＿size－1）lower＿bound： 函數(shù)定義域的下限
upper＿bound： 函數(shù)定義域的上限
chromosome＿size： 染色體的長(zhǎng)度

通過上述公式，我們就可以成功地將二進(jìn)制染色體串解碼成［0，9］區(qū)間中的十進(jìn)制實(shí)數(shù)解。

個(gè)體與種群：

『染色體』表達(dá)了某種特征，這種特征的載體，稱為『個(gè)體』。

對(duì)于本次實(shí)驗(yàn)所要解決的一元函數(shù)最大值求解問題，個(gè)體可以用上一節(jié)構(gòu)造的染色體表示，一個(gè)個(gè)體里有一條染色體。

許多這樣的個(gè)體組成了一個(gè)種群，其含義是一個(gè)一維點(diǎn)集（x軸上［0，9］的線段）。

適應(yīng)度函數(shù)：

遺傳算法中，一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來評(píng)價(jià)，在本問題中，f（x）就是適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)值越大，解的質(zhì)量越高。

適應(yīng)度函數(shù)是遺傳算法進(jìn)化的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。

遺傳算子：

我們希望有這樣一個(gè)種群，它所包含的個(gè)體所對(duì)應(yīng)的函數(shù)值都很接近于f（x）在［0，9］上的最大值，但是這個(gè)種群一開始可能不那么優(yōu)秀，因?yàn)閭�(gè)體的染色體串是隨機(jī)生成的。

如何讓種群變得優(yōu)秀呢？

不斷地進(jìn)化

每一次進(jìn)化都盡可能保留種群中的優(yōu)秀個(gè)體，淘汰掉不理想的個(gè)體，并且在優(yōu)秀個(gè)體之間進(jìn)行染色體交叉，有些個(gè)體還可能出現(xiàn)變異。

種群的每一次進(jìn)化，都會(huì)產(chǎn)生一個(gè)最優(yōu)個(gè)體。種群所有世代的最優(yōu)個(gè)體，可能就是函數(shù)f（x）最大值對(duì)應(yīng)的定義域中的點(diǎn)。

如果種群無休止地進(jìn)化，那總能找到最好的解。但實(shí)際上，我們的時(shí)間有限，通常在得到一個(gè)看上去不錯(cuò)的解時(shí)，便終止了進(jìn)化。

對(duì)于給定的種群，如何賦予它進(jìn)化的能力呢？

首先是選擇（selection）

? 選擇操作是從前代種群中選擇＊＊＊多對(duì)＊＊＊較優(yōu)個(gè)體，一對(duì)較優(yōu)個(gè)體稱之為一對(duì)父母，讓父母?jìng)儗⑺鼈兊幕�因傳遞到下一代，直到下一代個(gè)體數(shù)量達(dá)到種群數(shù)量上限

? 在選擇操作前，將種群中個(gè)體按照適應(yīng)度從小到大進(jìn)行排列

? 采用輪盤賭選擇方法（當(dāng)然還有很多別的選擇方法，比如競(jìng)標(biāo)賽法），各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比

? 輪盤賭選擇方法具有隨機(jī)性，在選擇的過程中可能會(huì)丟掉較好的個(gè)體，所以可以使用精英機(jī)制，將前代最優(yōu)個(gè)體直接選擇

其次是交叉（crossover）

? 兩個(gè)待交叉的不同的染色體（父母）根據(jù)交叉概率（cross＿rate）按某種方式交換其部分基因
? 采用單點(diǎn)交叉法，也可以使用其他交叉方法

最后是變異（mutation）

? 染色體按照變異概率（mutate＿rate）進(jìn)行染色體的變異

? 采用單點(diǎn)變異法，也可以使用其他變異方法

一般來說，交叉概率（cross＿rate）比較大，變異概率（mutate＿rate）極低。像求解函數(shù)最大值這類問題，我設(shè)置的交叉概率（cross＿rate）是0．6，變異概率（mutate＿rate）是0．01。

因?yàn)檫z傳算法相信2條優(yōu)秀的父母染色體交叉更有可能產(chǎn)生優(yōu)秀的后代，而變異的話產(chǎn)生優(yōu)秀后代的可能性極低，不過也有存在可能一下就變異出非常優(yōu)秀的后代。這也是符合自然界生物進(jìn)化的特征的。

03

算例代碼

上述算例是我學(xué)習(xí)遺傳算法時(shí)的算例，比較容易理解，如果還有不懂得可以后臺(tái)聯(lián)系我們，這里附上算例的代碼（matlab版本）：

鏈接：https：／／pan．baidu．com／s／1rvhtA4kaxQuJTmndiVS71Q提取碼：bfrr