遺傳算法

概     述

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

01

大致了解

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

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

02

簡單算例

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

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

流程：??????????????遺傳算法（Genetic Algorithm）遵循『適者生存』、『優(yōu)勝劣汰』的原則，是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。遺傳算法模擬一個人工種群的進化過程，通過選擇（Selection）、交叉（Crossover）以及變異（Mutation）等機制，在每次迭代中都保留一組候選個體，重復此過程，種群經(jīng)過若干代進化后，理想情況下其適應度達到＊＊＊近似最優(yōu)＊＊＊的狀態(tài)。

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