AI tools
Loading AI tools

基因演算法（英語：Genetic Algorithm，GA）是計算數學中用於解決最佳化的搜尋演算法，是進化演算法的一種。進化演算法最初是借鑑了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等等。

基因演算法通常實現方式為一種電腦模擬。對於一個最佳化問題，一定數量的候選解（稱為個體）可抽象表示為染色體，使種群向更好的解進化。傳統上，解用二進制表示（即0和1的串），但也可以用其他表示方法。進化從完全隨機個體的種群開始，之後一代一代發生。在每一代中評價整個種群的適應度，從當前種群中隨機地選擇多個個體（基於它們的適應度），通過自然選擇和突變產生新的生命種群，該種群在演算法的下一次迭代中成為當前種群。

基因演算法的機理

在基因演算法裏，最佳化問題的解被稱為個體，它表示為一個變數序列，叫做染色體或者基因串。染色體一般被表達為簡單的字串或數字串，不過也有其他的依賴於特殊問題的表示方法適用，這一過程稱為編碼。首先，演算法隨機生成一定數量的個體，有時候操作者也可以干預這個隨機產生過程，以提高初始種群的質素。在每一代中，都會評價每一個體，並通過計算適應度函數得到適應度數值。按照適應度排序種群個體，適應度高的在前面。這裏的「高」是相對於初始的種群的低適應度而言。

下一步是產生下一代個體並組成種群。這個過程是通過選擇和繁殖完成，其中繁殖包括交配（crossover，在演算法研究領域中我們稱之為交叉操作）和突變（mutation）。選擇則是根據新個體的適應度進行，但同時不意味着完全以適應度高低為導向，因為單純選擇適應度高的個體將可能導致演算法快速收斂到局部最佳解而非全域最佳解，我們稱之為早熟。作為折中，基因演算法依據原則：適應度越高，被選擇的機會越高，而適應度低的，被選擇的機會就低。初始的數據可以通過這樣的選擇過程組成一個相對最佳化的群體。之後，被選擇的個體進入交配過程。一般的基因演算法都有一個交配概率（又稱為交叉概率），範圍一般是0.6~1，這個交配概率反映兩個被選中的個體進行交配的概率。例如，交配概率為0.8，則80%的「夫妻」會生育後代。每兩個個體通過交配產生兩個新個體，代替原來的「老」個體，而不交配的個體則保持不變。交配父母的染色體相互交換，從而產生兩個新的染色體，第一個個體前半段是父親的染色體，後半段是母親的，第二個個體則正好相反。不過這裏的半段並不是真正的一半，這個位置叫做交配點，也是隨機產生的，可以是染色體的任意位置。再下一步是突變，通過突變產生新的「子」個體。一般基因演算法都有一個固定的突變常數（又稱為變異概率），通常是0.1或者更小，這代表變異發生的概率。根據這個概率，新個體的染色體隨機的突變，通常就是改變染色體的一個位元組（0變到1，或者1變到0）。

經過這一系列的過程（選擇、交配和突變），產生的新一代個體不同於初始的一代，並一代一代向增加整體適應度的方向發展，因為總是更常選擇最好的個體產生下一代，而適應度低的個體逐漸被淘汰掉。這樣的過程不斷的重複：評價每個個體，計算適應度，兩兩交配，然後突變，產生第三代。周而復始，直到終止條件滿足為止。一般終止條件有以下幾種：

  • 進化次數限制；
  • 計算耗費的資源限制（例如計算時間、計算佔用的主記憶體等）；
  • 一個個體已經滿足最佳值的條件，即最佳值已經找到；
  • 適應度已經達到飽和，繼續進化不會產生適應度更好的個體；
  • 人為干預；
  • 以及以上兩種或更多種的組合。

演算法

  • 選擇初始生命種群
  • 迴圈
    • 評價種群中的個體適應度
    • 以比例原則（分數高的挑中概率也較高）選擇產生下一個種群（輪盤法（roulette wheel selection）、競爭法（tournament selection）及等級輪盤法（Rank Based Wheel Selection））。不僅僅挑分數最高的的原因是這麼做可能收斂到局部的最佳點，而非整體的。
    • 改變該種群（交叉和變異）
  • 直到停止迴圈的條件滿足.

GA參數

  • 種群規模（P,population size）：即種群中染色體個體的數目。
  • 字串長度（l, string length）：個體中染色體的長度。
  • 交配概率（pc, probability of performing crossover）：控制着交配算子的使用頻率。交配操作可以加快收斂，使解達到最有希望的最佳解區域，因此一般取較大的交配概率，但交配概率太高也可能導致過早收斂，則稱為早熟。
  • 突變概率（pm, probability of mutation）：控制着突變算子的使用頻率。
  • 中止條件（termination criteria）

特點

基因演算法在解決最佳化問題過程中有如下特點：

  • 基因演算法在適應度函數選擇不當的情況下有可能收斂於局部最佳，而不能達到全域最佳。
  • 初始種群的數量很重要，如果初始種群數量過多，演算法會佔用大量系統資源；如果初始種群數量過少，演算法很可能忽略掉最佳解。
  • 對於每個解，一般根據實際情況進行編碼，這樣有利於編寫變異函數和適應度函數(Fitness Function)。
  • 在編碼過的基因演算法中，每次變異的編碼長度也影響到基因演算法的效率。如果變異代碼長度過短，變異的多樣性會受到限制；如果變異代碼過長，變異的效率會非常低下，選擇適當的變異長度是提高效率的關鍵。
  • 變異率也是一個重要的參數。
  • 對於動態數據，用基因演算法求最佳解比較困難，因為染色體種群很可能過早地收斂，而對以後變化了的數據不再產生變化。對於這個問題，研究者提出了一些方法增加基因的多樣性，從而防止過早的收斂。其中一種是所謂觸發式超級變異，就是當染色體群體的質素下降（彼此的區別減少）時增加變異概率；另一種叫隨機外來染色體，是偶爾加入一些全新的隨機生成的染色體個體，從而增加染色體多樣性。
  • 選擇過程很重要，但交叉和變異的重要性存在爭議。一種觀點認為交叉比變異更重要，因為變異僅僅是保證不遺失某些可能的解；而另一種觀點則認為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對於初期的種群來說，交叉幾乎等效於一個非常大的變異率，而這麼大的變異很可能影響進化過程。
  • 基因演算法很快就能找到良好的解，即使是在很複雜的解空間中。
  • 基因演算法並不一定總是最好的最佳化策略，最佳化問題要具體情況具體分析。所以在使用基因演算法的同時，也可以嘗試其他演算法，互相補充，甚至根本不用基因演算法。
  • 基因演算法不能解決那些「大海撈針」的問題，所謂「大海撈針」問題就是沒有一個確切的適應度函數表徵個體好壞的問題，使得演算法的進化失去導向。
  • 對於任何一個具體的最佳化問題，調節基因演算法的參數可能會有利於更好更快收斂，這些參數包括個體數目、交叉率和變異率。例如太大的變異率會導致遺失最佳解，而過小的變異率會導致演算法過早的收斂於局部最佳點。對於這些參數的選擇，現在還沒有實用的上下限。
  • 適應度函數對於演算法的速度和效果也很重要。

變數

最簡單的基因演算法將染色體表示為一個數碼串，數值變數也可以表示成整數，或者實數（浮點數）。演算法中的雜交和突變都是在位元組串上進行的，所以所謂的整數或者實數表示也一定要轉化為數碼形式。例如一個變數的形式是實數，其範圍是0～1，而要求的精度是0.001，那麼可以用10個數碼表示：0000000000表示0，1111111111表示1。那麼0110001110就代表0.398。

在基因演算法里，精英選擇是一種非常成功的產生新個體的策略，它是把最好的若干個個體作為精英直接帶入下一代個體中，而不經過任何改變。

通過平行計算實現基因演算法一般有兩種，一種是所謂粗糙並列基因演算法，即一個計算單元包含一個種群；而另一種是所謂精細並列基因演算法，每一個計算單元處理一個染色體個體。

基因演算法有時候還引入其他變數，例如在即時最佳化問題中，可以在適應度函數中引入時間相關性和干擾。

適用的問題

基因演算法擅長解決的問題是全域最佳化問題，例如，解決時間表安排問題就是它的一個特長，很多安排時間表的軟件都使用基因演算法，基因演算法還經常被用於解決實際工程問題。

跟傳統的爬山演算法相比，基因演算法能夠跳出局部最佳而找到全域最佳點。而且基因演算法允許使用非常複雜的適應度函數（或者叫做目標函數），並對變數的變化範圍可以加以限制。而如果是傳統的爬山演算法，對變數範圍進行限制意味着複雜的多的解決過程，這方面的介紹可以參看受限最佳化問題和非受限最佳化問題。

發展歷史

基因演算法由密歇根大學的約翰·霍蘭德和他的同事於二十世紀六十年代在對細胞自動機（英文：cellular automata）進行研究時率先提出。在二十世紀八十年代中期之前，對於基因演算法的研究還僅僅限於理論方面，直到在匹茲堡召開了第一屆世界基因演算法大會。隨着電腦計算能力的發展和實際應用需求的增多，基因演算法逐漸進入實際應用階段。1989年，紐約時報作者約翰·馬科夫寫了一篇文章描述第一個商業用途的基因演算法--進化者（英文：Evolver）。之後，越來越多種類的基因演算法出現並被用於許多領域中，財富雜誌500強企業中大多數都用它進行時間表安排、數據分析、未來趨勢預測、預算、以及解決很多其他組合最佳化問題。

應用領域

Thumb
日本新幹線N700系列車「氣動雙翼」的獨特空氣動力造型車鼻；是基因演算法運算結果

相關技術

遺傳程式是John Koza與基因演算法相關的一個技術，在遺傳程式中，並不是參數最佳化，而是電腦程式最佳化。遺傳程式一般採用樹型結構表示電腦程式用於進化，而不是基因演算法中的列表或者陣列。一般來說，遺傳程式比基因演算法慢，但同時也可以解決一些基因演算法解決不了的問題。

互動式基因演算法是利用人工評價進行操作的基因演算法，一般用於適應度函數無法得到的情況，例如，對於圖像、音樂、藝術的設計和「最佳化」，或者對運動員的訓練等。

模擬退火是解決全域最佳化問題的另一個可能選擇。它是通過一個解在搜尋空間的隨機變動尋找最佳點的方法：如果某一階段的隨機變動增加適應度，則總是被接受，而降低適應度的隨機變動根據一定的概率被有選擇的接受。這個概率由當時的退火溫度和適應度惡化的程度決定，而退火溫度按一定速度降低。從模擬退火演算法看，最佳化問題的解是通過尋找最小能量點找到的，而不是尋找最佳適應點找到的。模擬退火也可以用於標準基因演算法里，只要把突變率隨時間逐漸降低就可以了。

參見

參考文獻

  • Goldberg, David E (1989), 基因演算法：搜尋、最佳化和機器學習，Kluwer Academic Publishers, Boston, MA.
  • Goldberg, David E (2002), 創新的設計：競爭基因演算法課程，Addison-Wesley, Reading, MA.
  • Harvey, Inman (1992), 物種適應和基因演算法持續進行的基礎 in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F.J. Varela and P. Bourgine (eds.), MIT Press/Bradford Books, Cambridge, MA, pp. 346-354.
  • Koza, John (1992), 基因演算法：通過自然選擇編寫電腦程式
  • Michalewicz, Zbigniew (1999), 基因演算法+數據結構=進化程式，Springer-Verlag.
  • Mitchell, Melanie, (1996), 基因演算法概論，MIT Press, Cambridge, MA.
  • Poli, R., Langdon, W. B., McPhee, N. F. A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. 2008. ISBN 978-1-4092-0073-4.
  • Schmitt, Lothar M (2001), 基因演算法理論，Theoretical Computer Science (259), pp. 1-61
  • Schmitt, Lothar M (2004), 基因演算法理論（二），Theoretical Computer Science (310), pp. 181-231
  • Vose, Michael D (1999), 簡單基因演算法：基礎和理論，MIT Press, Cambridge, MA.

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Chrome
Wikiwand for Chrome
Edge
Wikiwand for Edge
Firefox
Wikiwand for Firefox