姓名：張藝倫 ? ?學(xué)號(hào)：17011210282
轉(zhuǎn)載自：https://www.zhihu.com/question/23293449/answer/120220974，有刪節(jié)
【嵌牛導(dǎo)讀】：本文簡(jiǎn)單的介紹了遺傳算法的思想，之后進(jìn)一步介紹了它的具體步驟，最后給出了它的流程以及在matlab中的實(shí)現(xiàn)方法。
【嵌牛鼻子】：遺傳算法，流程，matlab。
【嵌牛提問】：怎樣理解遺傳算法？具體步驟是什么？
【嵌牛正文】：
一個(gè)簡(jiǎn)單的問題用到了遺傳算法，問題是這樣的：
求解函數(shù) f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在區(qū)間[0,9]的最大值。
這個(gè)函數(shù)大概長(zhǎng)這樣：
那么如何應(yīng)用遺傳算法如何來(lái)找到這個(gè)奇怪的函數(shù)的最大值呢？
事實(shí)上，不管一個(gè)函數(shù)的形狀多么奇怪，遺傳算法都能在很短的時(shí)間內(nèi)找到它在一個(gè)區(qū)間內(nèi)的(近似)最大值。
相當(dāng)神奇，不是嗎？
接下來(lái)圍繞這個(gè)問題，講講我對(duì)遺傳算法的一些理解。在Matlab中使用遺傳算法的小教程都附在最后。
1.介紹
遺傳算法(Genetic Algorithm)遵循『適者生存』、『優(yōu)勝劣汰』的原則，是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。
遺傳算法模擬一個(gè)人工種群的進(jìn)化過(guò)程，通過(guò)選擇(Selection)、交叉(Crossover)以及變異(Mutation)等機(jī)制，在每次迭代中都保留一組候選個(gè)體，重復(fù)此過(guò)程，種群經(jīng)過(guò)若干代進(jìn)化后，理想情況下其適應(yīng)度達(dá)到***近似最優(yōu)***的狀態(tài)。
自從遺傳算法被提出以來(lái)，其得到了廣泛的應(yīng)用，特別是在函數(shù)優(yōu)化、生產(chǎn)調(diào)度、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制等領(lǐng)域，遺傳算法發(fā)揮了很大的作用，提高了一些問題求解的效率。
2.遺傳算法組成
1.編碼 -> 創(chuàng)造染色體
2.個(gè)體 -> 種群
3.適應(yīng)度函數(shù)
4.遺傳算子
? ?選擇
? ?交叉
? ?變異
5.運(yùn)行參數(shù)
? ?是否選擇精英操作
? ?種群大小
? ?染色體長(zhǎng)度
? ?最大迭代次數(shù)
? ?交叉概率
? ?變異概率
2.1 編碼與解碼
實(shí)現(xiàn)遺傳算法的第一步就是明確對(duì)求解問題的編碼和解碼方式。
對(duì)于函數(shù)優(yōu)化問題，一般有兩種編碼方式，各具優(yōu)缺點(diǎn)
1.實(shí)數(shù)編碼：直接用實(shí)數(shù)表示基因，容易理解且不需要解碼過(guò)程，但容易過(guò)早收斂，從而陷入局部最優(yōu)
2.二進(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ù)來(lái)表示這些解。換句話說(shuō)，一個(gè)解的編碼就是一個(gè)17位的二進(jìn)制串。
一開始，這些二進(jìn)制串是隨機(jī)生成的。
一個(gè)這樣的二進(jìn)制串代表一條染色體串，這里染色體串的長(zhǎng)度為17。
對(duì)于任何一條這樣的染色體chromosome，如何將它復(fù)原(解碼)到[0,9]這個(gè)區(qū)間中的數(shù)值呢？
對(duì)于本問題，我們可以采用以下公式來(lái)解碼：
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)
lower_bound: 函數(shù)定義域的下限
upper_bound: 函數(shù)定義域的上限
chromosome_size: 染色體的長(zhǎng)度
通過(guò)上述公式，我們就可以成功地將二進(jìn)制染色體串解碼成[0,9]區(qū)間中的十進(jìn)制實(shí)數(shù)解。
2.2 個(gè)體與種群
『染色體』表達(dá)了某種特征，這種特征的載體，稱為『個(gè)體』。
對(duì)于本次實(shí)驗(yàn)所要解決的一元函數(shù)最大值求解問題，個(gè)體可以用上一節(jié)構(gòu)造的染色體表示，一個(gè)個(gè)體里有一條染色體。
許多這樣的個(gè)體組成了一個(gè)種群，其含義是一個(gè)一維點(diǎn)集(x軸上[0,9]的線段)。
2.3 適應(yīng)度函數(shù)
遺傳算法中，一個(gè)個(gè)體(解)的好壞用適應(yīng)度函數(shù)值來(lái)評(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é)合求解問題本身的要求而定。
2.4 遺傳算子
我們希望有這樣一個(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)。
如果種群無(wú)休止地進(jìn)化，那總能找到最好的解。但實(shí)際上，我們的時(shí)間有限，通常在得到一個(gè)看上去不錯(cuò)的解時(shí)，便終止了進(jìn)化。
對(duì)于給定的種群，如何賦予它進(jìn)化的能力呢？
1.首先是選擇(selection)
選擇操作是從前代種群中選擇***多對(duì)***較優(yōu)個(gè)體，一對(duì)較優(yōu)個(gè)體稱之為一對(duì)父母，讓父母?jìng)儗⑺鼈兊幕騻鬟f到下一代，直到下一代個(gè)體數(shù)量達(dá)到種群數(shù)量上限
在選擇操作前，將種群中個(gè)體按照適應(yīng)度從小到大進(jìn)行排列
采用輪盤賭選擇方法（當(dāng)然還有很多別的選擇方法），各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比
輪盤賭選擇方法具有隨機(jī)性，在選擇的過(guò)程中可能會(huì)丟掉較好的個(gè)體，所以可以使用精英機(jī)制，將前代最優(yōu)個(gè)體直接選擇
2.其次是交叉(crossover)
兩個(gè)待交叉的不同的染色體(父母)根據(jù)交叉概率(cross_rate)按某種方式交換其部分基因
采用單點(diǎn)交叉法，也可以使用其他交叉方法
3.最后是變異(mutation)
染色體按照變異概率(mutate_rate)進(jìn)行染色體的變異
采用單點(diǎn)變異法，也可以使用其他變異方法
一般來(lái)說(shuō)，交叉概率(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)秀后代的可能性極低，不過(guò)也有存在可能一下就變異出非常優(yōu)秀的后代。這也是符合自然界生物進(jìn)化的特征的。
3.遺傳算法流程
最后就再介紹一下如何在Matlab中使用遺傳算法。
在MATLAB中使用GA
1. 打開 Optimization 工具，在 Solver 中選擇 ga - genetic algorithm，在 Fitness function 中填入@target
2. 在你的工程文件夾中新建 target.m，注意MATLAB的當(dāng)前路徑是你的工程文件夾所在路徑
3. 在 target.m 中寫下適應(yīng)度函數(shù)，比如
function [ y ] = target(x)y = -x-10*sin(5*x)-7*cos(4*x);end
*MATLAB中的GA只求解函數(shù)的(近似)最小值，所以先要將目標(biāo)函數(shù)取反。
4. 打開 Optimization 工具，輸入 變量個(gè)數(shù)(Number of variables) 和 自變量定義域(Bounds) 的值，點(diǎn)擊 Start，遺傳算法就跑起來(lái)了。最終在輸出框中可以看到函數(shù)的(近似)最小值，和達(dá)到這一程度的迭代次數(shù)(Current iteration)和最終自變量的值(Final point)
5. 在 Optimization - ga 工具中，有許多選項(xiàng)。通過(guò)這些選項(xiàng)，可以設(shè)置下列屬性
種群(Population)
選擇(Selection)
交叉(Crossover)
變異(Mutation)
停止條件(Stopping criteria)
畫圖函數(shù)(Plot functions)
