遺傳算法

概     述

遺傳算法（Genetic Algorithm，GA）最早是由美國(guó)的 John holland于20世紀(jì)70年代提出，該算法是根據(jù)大自然中生物體進(jìn)化規(guī)律而設(shè)計(jì)提出的。是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。該算法通過(guò)數(shù)學(xué)的方式，利用計(jì)算機(jī)仿真運(yùn)算，將問(wèn)題的求解過(guò)程轉(zhuǎn)換成類似生物進(jìn)化中的染色體基因的交叉、變異等過(guò)程。在求解較為復(fù)雜的組合優(yōu)化問(wèn)題時(shí)，相對(duì)一些常規(guī)的優(yōu)化算法，通常能夠較快地獲得較好的優(yōu)化結(jié)果。遺傳算法已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。

01

大致了解

遺傳算法屬于啟發(fā)式算法的一種，大家理解啟發(fā)式算法的時(shí)候可以將其與枚舉法類比。舉個(gè)簡(jiǎn)單的例子，我們?cè)谇蠼饽骋缓瘮?shù)f（x）的最大值時(shí)，通常的方法是通過(guò)求導(dǎo)，找到極值點(diǎn)。但是大家一定還知道另外一種最笨的辦法，就是枚舉法。假設(shè)x的可行域在［0，1］之間，x最大值的精確度是0．01，那就可以把［0，1］之間所有的可行解（0．01， 0．02， 0．03，．．． 0．98， 0．99， 1．00）都拿出來(lái)代入f（x），計(jì)算比較它們的大小，找到最大值對(duì)應(yīng)的x＇即為最優(yōu)解，f（x＇）為最大值。但是這種方法的求解效率太低了，為了解決這一問(wèn)題，各路大神就根據(jù)各種學(xué)科的不同原理，比如生物界的遺傳、魚群、蟻群、冶金學(xué)的退火等，將這些理論應(yīng)用在求解中，以提高求解效率。同樣是不斷地嘗試找到最優(yōu)解，利用這些原理可以讓嘗試的過(guò)程沒(méi)那么盲目，而是按照一定的規(guī)律去尋找最優(yōu)解，可以有效地提高求解效率，讓我們更快地尋找到f（x）的最優(yōu)解。

總之，為了更容易理解遺傳算法，大家首先可以有一個(gè)大致的思維：遺傳算法是枚舉法的升級(jí)版本。

02

簡(jiǎn)單算例

問(wèn)題：求解函數(shù) f（x） ＝ x ＋ 10＊sin（5＊x） ＋ 7＊cos（4＊x） 在區(qū)間［0，9］的最大值。

p．s．  f（x） 函數(shù)大致圖像如上圖

流程：??????????????遺傳算法（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)。

p．s．  遺傳算法流程圖如上圖