遺傳算法入門(mén)到掌握（一）
本文關(guān)鍵詞：遺傳算法，由筆耕文化傳播整理發(fā)布。
遺傳算法的有趣應(yīng)用很多，諸如尋路問(wèn)題，8數(shù)碼問(wèn)題，囚犯困境，動(dòng)作控制，找圓心問(wèn)題（這是一個(gè)國(guó)外網(wǎng)友的建議：在一個(gè)不規(guī)則的多邊形 中，尋找一個(gè)包含在該多邊形內(nèi)的最大圓圈的圓心。），TSP問(wèn)題（在以后的章節(jié)里面將做詳細(xì)介紹。），生產(chǎn)調(diào)度問(wèn)題，人工生命模擬等。直到最后看到一個(gè)非 常有趣的比喻，覺(jué)得由此引出的袋鼠跳問(wèn)題（暫且這么叫它吧），既有趣直觀又直達(dá)遺傳算法的本質(zhì)，確實(shí)非常適合作為初學(xué)者入門(mén)的例子。
問(wèn)題的提出與解決方案
讓我們先來(lái)考慮考慮下面這個(gè)問(wèn)題的解決辦法。
已知一元函數(shù)：
現(xiàn)在要求在既定的區(qū)間內(nèi)找出函數(shù)的最大值
極大值、最大值、局部最優(yōu)解、全局最優(yōu)解
在解決上面提出的問(wèn)題之前我們有必要先澄清幾個(gè)以后將常常會(huì)碰到的概念：極 大值、最大值、局部最優(yōu)解、全局最優(yōu)解。學(xué)過(guò)高中數(shù)學(xué)的人都知道極大值在一個(gè)小鄰域里面左邊的函數(shù)值遞增，右邊的函數(shù)值遞減，在圖2.1里面的表現(xiàn)就是一 個(gè)“山峰”。當(dāng)然，在圖上有很多個(gè)“山峰”，所以這個(gè)函數(shù)有很多個(gè)極大值。而對(duì)于一個(gè)函數(shù)來(lái)說(shuō)，最大值就是在所有極大值當(dāng)中，最大的那個(gè)。所以極大值具有局部性，而最大值則具有全局性。
因?yàn)檫z傳算法中每一條染色體，對(duì)應(yīng)著遺傳算法的一個(gè) 解決方案，一般我們用適應(yīng)性函數(shù)（fitness function）來(lái)衡量這個(gè)解決方案的優(yōu)劣。所以從一個(gè)基因組到其解的適應(yīng)度形成一個(gè)映射。所以也可以把遺傳算法的過(guò)程看作是一個(gè)在多元函數(shù)里面求最優(yōu)解的過(guò)程。在這個(gè)多維曲面里面也有數(shù)不清的“山峰”，而這些最優(yōu)解所對(duì)應(yīng)的就是局部最優(yōu)解。而其中也會(huì)有一個(gè)“山峰”的海拔最高的，那么這個(gè)就是全局最優(yōu) 解。而遺傳算法的任務(wù)就是盡量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遺傳算法不一定要找“最高的山峰”，如果問(wèn)題的適應(yīng)度評(píng)價(jià)越小越好的話，那么全局最優(yōu)解就是函數(shù)的最小值，對(duì)應(yīng)的，遺傳算法所要找的就是“最深的谷底”）如果至今你還不太理解的話，那么你先往下看。本章的示例程序?qū)?huì) 非常形象的表現(xiàn)出這個(gè)情景。
“袋鼠跳”問(wèn)題
既然我們把 函數(shù)曲線理解成一個(gè)一個(gè)山峰和山谷組成的山脈。那么我們可以設(shè)想所得到的每一個(gè)解就是一只袋鼠，我們希望它們不斷的向著更高處跳去，直到跳到最高的山峰（盡管袋鼠本身不見(jiàn)得愿意那么做）。所以求最大值的過(guò)程就轉(zhuǎn)化成一個(gè)“袋鼠跳”的過(guò)程。下面介紹介紹“袋鼠跳”的幾種方式。
爬山法、模擬退火和遺傳算法
解決尋找最大值問(wèn)題的幾種常見(jiàn)的算法：
1. 爬山法（最速上升爬山法）：
從搜索空間中隨機(jī)產(chǎn)生鄰近的點(diǎn)，從中選擇對(duì)應(yīng)解最優(yōu)的個(gè)體，替換原來(lái)的個(gè)體，不斷 重復(fù)上述過(guò)程。因?yàn)橹粚?duì)“鄰近”的點(diǎn)作比較，所以目光比較“短淺”，常常只能收斂到離開(kāi)初始位置比較近的局部最優(yōu)解上面。對(duì)于存在很多局部最優(yōu)點(diǎn)的問(wèn)題，通過(guò)一個(gè)簡(jiǎn)單的迭代找出全局最優(yōu)解的機(jī)會(huì)非常渺茫。（在爬山法中，袋鼠最有希望到達(dá)最靠近它出發(fā)點(diǎn)的山頂，但不能保證該山頂是珠穆朗瑪峰，或者是一個(gè)非常 高的山峰。因?yàn)橐宦飞纤活櫳掀�，沒(méi)有下坡。）
2. 模擬退火：
這個(gè)方法來(lái)自金屬熱加工過(guò)程的啟發(fā)。在金屬熱加工過(guò)程中，當(dāng)金屬的溫度超過(guò)它的熔點(diǎn)（Melting Point）時(shí)，原子就會(huì)激烈地隨機(jī)運(yùn)動(dòng)。與所有的其它的物理系統(tǒng)相類似，原子的這種運(yùn)動(dòng)趨向于尋找其能量的極小狀態(tài)。在這個(gè)能量的變遷過(guò)程中，開(kāi)始時(shí)。溫度非常高， 使得原子具有很高的能量。隨著溫度不斷降低，金屬逐漸冷卻，金屬中的原子的能量就越來(lái)越小，最后達(dá)到所有可能的最低點(diǎn)。利用模擬退火的時(shí)候，讓算法從較大的跳躍開(kāi)始，使到它有足夠的“能量”逃離可能“路過(guò)”的局部最優(yōu)解而不至于限制在其中，當(dāng)它停在全局最優(yōu)解附近的時(shí)候，逐漸的減小跳躍量，以便使其“落腳 ”到全局最優(yōu)解上。（在模擬退火中，袋鼠喝醉了，而且隨機(jī)地大跳躍了很長(zhǎng)時(shí)間。運(yùn)氣好的話，它從一個(gè)山峰跳過(guò)山谷，到了另外一個(gè)更高的山峰上。但最后，它漸漸清醒了并朝著它所在的峰頂跳去。）
3. 遺傳算法：
模擬物競(jìng)天擇的生物進(jìn)化過(guò)程，通過(guò)維護(hù)一個(gè)潛在解的群體執(zhí)行了多方向的搜索，并支持這些方向上的信息構(gòu)成和交換。以面為單位的搜索，比以點(diǎn)為單位的搜索，更能發(fā)現(xiàn)全局最優(yōu)解。（在遺傳算法中，有很多袋鼠，它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠并不知道它們的任務(wù)是尋找珠穆朗瑪峰。但每過(guò)幾年，就在一些海拔高度較低的地方射殺一些袋鼠，并希望存活下來(lái)的袋鼠是多產(chǎn)的，在它們所處的地方生兒育女。）（后來(lái)，一個(gè)叫天行健的網(wǎng)游給我想了一個(gè)更恰切的故事：從前，有一大群袋鼠，它們被莫名其妙的零散地遺棄于喜馬拉雅山脈。于是只好在那里艱苦的生活。海拔 低的地方彌漫著一種無(wú)色無(wú)味的毒氣，海拔越高毒氣越稀薄�？墒强蓱z的袋鼠們對(duì)此全然不覺(jué)，還是習(xí)慣于活蹦亂跳。于是，不斷有袋鼠死于海拔較低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有機(jī)會(huì)生兒育女。就這樣經(jīng)過(guò)許多年，這些袋鼠們竟然都不自覺(jué)地聚攏到了一個(gè)個(gè)的山峰上，可是在所有的袋鼠中，只有聚 攏到珠穆朗瑪峰的袋鼠被帶回了美麗的澳洲。）
下面主要介紹介紹遺傳算法實(shí)現(xiàn)的過(guò)程。
遺傳算法的實(shí)現(xiàn)過(guò)程
遺傳算法的實(shí)現(xiàn)過(guò)程實(shí)際上就像自然界的進(jìn)化過(guò)程那樣。首先尋找一種對(duì)問(wèn)題潛在解進(jìn)行“數(shù)字化”編碼的方案。（建立表現(xiàn)型和基因型的映射關(guān)系。）然后用隨機(jī) 數(shù)初始化一個(gè)種群（那么第一批袋鼠就被隨意地分散在山脈上。），種群里面的個(gè)體就是這些數(shù)字化的編碼。接下來(lái)，通過(guò)適當(dāng)?shù)慕獯a過(guò)程之后，（得到袋鼠的位置 坐標(biāo)。）用適應(yīng)性函數(shù)對(duì)每一個(gè)基因個(gè)體作一次適應(yīng)度評(píng)估。（袋鼠爬得越高，越是受我們的喜愛(ài)，所以適應(yīng)度相應(yīng)越高。）用選擇函數(shù)按照某種規(guī)定擇優(yōu)選 擇。（我們要每隔一段時(shí)間，在山上射殺一些所在海拔較低的袋鼠，以保證袋鼠總體數(shù)目持平。）讓個(gè)體基因交叉變異。（讓袋鼠隨機(jī)地跳一跳）然后產(chǎn)生子 代。（希望存活下來(lái)的袋鼠是多產(chǎn)的，并在那里生兒育女。）遺傳算法并不保證你能獲得問(wèn)題的最優(yōu)解，但是使用遺傳算法的最大優(yōu)點(diǎn)在于你不必去了解和操心如何 去“找”最優(yōu)解。（你不必去指導(dǎo)袋鼠向那邊跳，跳多遠(yuǎn)。）而只要簡(jiǎn)單的“否定”一些表現(xiàn)不好的個(gè)體就行了。（把那些總是愛(ài)走下坡路的袋鼠射殺。）以后你會(huì) 慢慢理解這句話，這是遺傳算法的精粹！
所以我們總結(jié)出遺傳算法的一般步驟：
開(kāi)始循環(huán)直至找到滿意的解。
1.評(píng)估每條染色體所對(duì)應(yīng)個(gè)體的適應(yīng)度。
2.遵照適應(yīng)度越高，選擇概率越大的原則，從種群中選擇兩個(gè)個(gè)體作為父方和母方。
3.抽取父母雙方的染色體，進(jìn)行交叉，產(chǎn)生子代。
4.對(duì)子代的染色體進(jìn)行變異。
5.重復(fù)2，3，4步驟，直到新種群的產(chǎn)生。
結(jié)束循環(huán)。
接下來(lái)，我們將詳細(xì)地剖析遺傳算法過(guò)程的每一個(gè)細(xì)節(jié)。
編制袋鼠的染色體----基因的編碼方式
通過(guò)前一章的學(xué)習(xí)，讀者已經(jīng)了解到人類染色體的編碼符號(hào)集，由4種堿基的兩種配合組成。共有4種情況，相當(dāng)于2 bit的信息量。這是人類基因的編碼方式，那么我們使用遺傳算法的時(shí)候編碼又該如何處理呢？
受到人類染色體結(jié)構(gòu)的啟發(fā)，我們可以設(shè)想一下，假設(shè)目前只有“0”，“1”兩種堿基，我們也用一條鏈條把他們有序的串連在一起，因?yàn)槊恳粋�(gè)單位都能表現(xiàn)出 1 bit的信息量，所以一條足夠長(zhǎng)的染色體就能為我們勾勒出一個(gè)個(gè)體的所有特征。這就是二進(jìn)制編碼法，染色體大致如下：
010010011011011110111110
上面的編碼方式雖然簡(jiǎn)單直觀，但明顯地，當(dāng)個(gè)體特征比較復(fù)雜的時(shí)候，需要大量的編碼才能精確地描述，相應(yīng)的解碼過(guò)程（類似于生物學(xué)中的DNA翻譯過(guò)程，就是把基因型映射到表現(xiàn)型的過(guò)程。）將過(guò)份繁復(fù)，為改善遺傳算法的計(jì)算復(fù)雜性、提高運(yùn)算效率，提出了浮點(diǎn)數(shù)編碼。染色體大致如下：
1.2 – 3.3 – 2.0 –5.4 – 2.7 – 4.3
那么我們?nèi)绾卫眠@兩種編碼方式來(lái)為袋鼠的染色體編碼呢？因?yàn)榫幋a的目的是建立表現(xiàn)型到基因型的映射關(guān)系，而表現(xiàn)型一般就被理解為個(gè)體的特征。比如人的基因型是46條染色體所描述的（總長(zhǎng)度 兩 米的紙條？），卻能解碼成一個(gè)個(gè)眼，耳，口，鼻等特征各不相同的活生生的人。所以我們要想為“袋鼠”的染色體編碼，我們必須先來(lái)考慮“袋鼠”的“個(gè)體特征”是什么。也許有的人會(huì)說(shuō)，袋鼠的特征很多，比如性別，身長(zhǎng)，體重，也許它喜歡吃什么也能算作其中一個(gè)特征。但具體在解決這個(gè)問(wèn)題的情況下，我們應(yīng)該進(jìn) 一步思考：無(wú)論這只袋鼠是長(zhǎng)短，肥瘦，只要它在低海拔就會(huì)被射殺，同時(shí)也沒(méi)有規(guī)定身長(zhǎng)的袋鼠能跳得遠(yuǎn)一些，身短的袋鼠跳得近一些。當(dāng)然它愛(ài)吃什么就更不相關(guān)了。我們由始至終都只關(guān)心一件事情：袋鼠在哪里。因?yàn)橹灰覀冎来笤谀抢铮覀兙湍茏鰞杉仨毴プ龅氖虑椋?/span>
（1）通過(guò)查閱喜瑪拉雅山脈的地圖來(lái)得知袋鼠所在的海拔高度（通過(guò)自變量求函數(shù)值。）以判斷我們有沒(méi)必要把它射殺。
（2）知道袋鼠跳一跳后去到哪個(gè)新位置。
如 果我們一時(shí)無(wú)法準(zhǔn)確的判斷哪些“個(gè)體特征”是必要的，哪些是非必要的，我們常常可以用到這樣一種思維方式：比如你認(rèn)為袋鼠的愛(ài)吃什么東西非常必要，那么你就想一想，有兩只袋鼠，它們其它的個(gè)體特征完全同等的情況下，一只愛(ài)吃草，另外一只愛(ài)吃果。你會(huì)馬上發(fā)現(xiàn)，這不會(huì)對(duì)它們的命運(yùn)有絲毫的影響，它們應(yīng)該有同 等的概率被射殺！只因它們處于同一個(gè)地方。（值得一提的是，如果你的基因編碼設(shè)計(jì)中包含了袋鼠愛(ài)吃什么的信息，這其實(shí)不會(huì)影響到袋鼠的進(jìn)化的過(guò)程，而那只攀到珠穆朗瑪峰的袋鼠吃什么也完全是隨機(jī)的，但是它所在的位置卻是非常確定的。）
以上是對(duì)遺傳算法編碼過(guò)程中經(jīng)常經(jīng)歷的思維過(guò)程，必須把具體問(wèn)題抽象成數(shù)學(xué)模型，突出主要矛盾，舍棄次要矛盾。只有這樣才能簡(jiǎn)潔而有效的解決問(wèn)題。希望初學(xué)者仔細(xì)琢磨。
既然確定了袋鼠的位置作為個(gè)體特征，具體來(lái)說(shuō)位置就 是橫坐標(biāo)。那么接下來(lái)，我們就要建立表現(xiàn)型到基因型的映射關(guān)系。就是說(shuō)如何用編碼來(lái)表現(xiàn)出袋鼠所在的橫坐標(biāo)。由于橫坐標(biāo)是一個(gè)實(shí)數(shù)，所以說(shuō)透了我們就是要對(duì)這個(gè)實(shí)數(shù)編碼�；仡櫸覀兩厦嫠榻B的兩種編碼方式，讀者最先想到的應(yīng)該就是，對(duì)于二進(jìn)制編碼方式來(lái)說(shuō)，編碼會(huì)比較復(fù)雜，而對(duì)于浮點(diǎn)數(shù)編碼方式來(lái)說(shuō)，則會(huì) 比較簡(jiǎn)潔。恩，正如你所想的，用浮點(diǎn)數(shù)編碼，僅僅需要一個(gè)浮點(diǎn)數(shù)而已。而下面則介紹如何建立二進(jìn)制編碼到一個(gè)實(shí)數(shù)的映射。
明顯地，一定長(zhǎng)度的二進(jìn)制編碼序列，只能表示一定精度的浮點(diǎn)數(shù)。譬如我們要求解精確到六位小數(shù)，由于區(qū)間長(zhǎng)度為2 – (-1) = 3 ,為了保證精度要求，至少把區(qū)間[-1,2]分為3 × 106等份。又因?yàn)?/span>
所以編碼的二進(jìn)制串至少需要22位。
把一個(gè)二進(jìn)制串（b0,b1,....bn)轉(zhuǎn)化位區(qū)間里面對(duì)應(yīng)的實(shí)數(shù)值通過(guò)下面兩個(gè)步驟。
（1）將一個(gè)二進(jìn)制串代表的二進(jìn)制數(shù)轉(zhuǎn)化為10進(jìn)制數(shù)：
（2）對(duì)應(yīng)區(qū)間內(nèi)的實(shí)數(shù)：
例如一個(gè)二進(jìn)制串<1000101110110101000111>表示實(shí)數(shù)值0.637197。
二進(jìn)制串<0000000000000000000000>和<1111111111111111111111>則分別表示區(qū)間的兩個(gè)端點(diǎn)值-1和2。
由于往下章節(jié)的示例程序幾乎都只用到浮點(diǎn)數(shù)編碼，所以這個(gè)“袋鼠跳”問(wèn)題的解決方案也是采用浮點(diǎn)數(shù)編碼的。往下的程序示例（包括裝載基因的類，突變函數(shù)）都是針對(duì)浮點(diǎn)數(shù)編碼的。（對(duì)于二進(jìn)制編碼這里只作簡(jiǎn)單的介紹，不過(guò)這個(gè)“袋鼠跳”完全可以用二進(jìn)制編碼來(lái)解決的，而且更有效一些。所以讀者可以自己嘗試用 二進(jìn)制編碼來(lái)解決。）
我們定義一個(gè)類作為袋鼠基因的載體。（細(xì)心的人會(huì)提 出這樣的疑問(wèn)：為什么我用浮點(diǎn)數(shù)的容器來(lái)儲(chǔ)藏袋鼠的基因呢？袋鼠的基因不是只用一個(gè)浮點(diǎn)數(shù)來(lái)表示就行嗎？恩，沒(méi)錯(cuò)，事實(shí)上對(duì)于這個(gè)實(shí)例，我們只需要用上一個(gè)浮點(diǎn)數(shù)就行了。我們這里用上容器是為了方便以后利用這些代碼處理那些編碼需要一串浮點(diǎn)數(shù)的問(wèn)題。）
class Genome { public: friend class GenAlg; friend class GenEngine; Genome():fitness(0){} Genome(vector <double> vec, double f): vecGenome(vec), fitness(f){} //類的帶參數(shù)初始化參數(shù)。 private: vector <double> vecGenome; // 裝載基因的容器 double fitness; //適應(yīng)度 };
好了，目前為止我們把袋鼠的染色體給研究透了，讓我們繼續(xù)跟進(jìn)袋鼠的進(jìn)化旅程。
物競(jìng)天擇－－適應(yīng)性評(píng)分與及選擇函數(shù)。
1.物競(jìng)――適應(yīng)度函數(shù)（fitness function）
自然界生物競(jìng)爭(zhēng)過(guò)程往往包含兩個(gè)方面：生物相互間的搏斗與及生物與客觀環(huán)境的搏斗過(guò)程。但在我們這個(gè)實(shí)例里面，你可以想象到，袋鼠相互之間是非常友好的，它們并不需要互相搏斗以爭(zhēng)取生存的權(quán)利。它們的生死存亡更多是取決于你的判斷。因?yàn)槟阋饬磕闹淮笤摎�，哪只袋鼠不該殺，所以你必須制定一個(gè)衡量的標(biāo)準(zhǔn)。而對(duì)于這個(gè)問(wèn)題，這個(gè)衡量的標(biāo)準(zhǔn)比較容易制定：袋鼠所在的海拔高度。（因?yàn)槟銌渭兊叵Ｍ笈赖迷礁咴胶谩＃┧晕覀冎苯佑么蟮暮０胃叨茸鳛樗鼈兊倪m應(yīng)性評(píng)分。即適應(yīng)度函數(shù)直接返回函數(shù)值就行了。
2.天擇――選擇函數(shù)（selection）
自然界中，越適應(yīng)的個(gè)體就越有可能繁殖后代。但是也不能說(shuō)適應(yīng)度越高的就肯定后代越多，只能是從概率上來(lái)說(shuō)更多。（畢竟有些所處海拔高度較低的袋鼠很幸運(yùn)，逃過(guò)了你的眼睛。）那么我們?cè)趺磥?lái)建立這種概率關(guān)系呢？下面我們介紹一種常用的選擇方法――輪盤(pán)賭（Roulette Wheel Selection）選擇法。假設(shè)種群數(shù)目,某個(gè)個(gè)體其適應(yīng)度為,則其被選中的概率為：
比如我們有5條染色體，他們所對(duì)應(yīng)的適應(yīng)度評(píng)分分別為：5，7，10，13，15。
所以累計(jì)總適應(yīng)度為：
所以各個(gè)個(gè)體被選中的概率分別為：
呵呵，有人會(huì)問(wèn)為什么我們把它叫成輪盤(pán)賭選擇法��？其實(shí)你只要看看圖2-2的輪盤(pán)就會(huì)明白了。這個(gè)輪盤(pán)是按照各個(gè)個(gè)體的適應(yīng)度比例進(jìn)行分塊的。你可以想象一下，我們轉(zhuǎn)動(dòng)輪盤(pán)，輪盤(pán)停下來(lái)的時(shí)候，指針會(huì)隨機(jī)地指向某一個(gè)個(gè)體所代表的區(qū)域，那么非常幸運(yùn)地，這個(gè)個(gè)體被選中了。（很明顯，適應(yīng)度評(píng)分越高的個(gè)體被選中的概率越大。）
那么接下來(lái)我們看看如何用代碼去實(shí)現(xiàn)輪盤(pán)賭。
Genome GenAlg:: GetChromoRoulette() { //產(chǎn)生一個(gè)0到人口總適應(yīng)性評(píng)分總和之間的隨機(jī)數(shù). //中m_dTotalFitness記錄了整個(gè)種群的適應(yīng)性分?jǐn)?shù)總和) double Slice = (random()) * totalFitness; //這個(gè)基因?qū)⒊休d轉(zhuǎn)盤(pán)所選出來(lái)的那個(gè)個(gè)體. Genome TheChosenOne; //累計(jì)適應(yīng)性分?jǐn)?shù)的和. double FitnessSoFar = 0; //遍歷總?cè)丝诶锩娴拿恳粭l染色體。 for (int i=0; i本文關(guān)鍵詞：遺傳算法，，由筆耕文化傳播整理發(fā)布。
本文編號(hào)：45543
本文鏈接：http://www.lk138.cn/jianzhugongchenglunwen/45543.html
