遺傳演算法

維基百科,自由的百科全書
(已重新導向自 基因演算法)
前往: 導覽搜尋

生物的進化(Evolution)過程主要是通過染色體之間的交叉和變異來完成的。基於對自然界中生物遺傳與進化機理的模仿,針對不同的問題,很多學者設計了許多不同的編碼方法來表示問題的可行解,開發出了許多種不同的遺傳算子來模仿不同環境下的生物遺傳特性。這樣,由不同的編碼(Coding)方法和不同的遺傳算子就構成了各種不同的遺傳演算法。

遺傳演算法是模仿自然界生物進化機制發展起來的隨機全局搜索和優化方法,它借鑒了 達爾文的進化論和孟德爾的遺傳學說。其本質是一種高效、並行、全局搜索的方法,它能在搜索過程中自動獲取和積累有關搜索空間的知識,並自適應的控制搜索過程以求得最優解。遺傳演算法操作使用適者生存的原則,在潛在的解決方案種群中逐次產生一個近似最優解的方案,在遺傳演算法的每一代中,根據個體在問題域中的適應度值和從自然遺傳學中借鑒來的再造方法進行個體選擇,產生一個新的近似解。這個過程導致種群中個體的進化,得到的新個體比原來個體更能適應環境,就像自然界中的改造一樣。

遺傳演算法計算機科學人工智慧領域中用於解決最優化的一種搜索啟發式演算法,是進化演算法的一種。這種啟發式通常用來生成有用的解決方案來優化和搜索問題。進化演算法最初是借鑒了進化生物學中的一些現象而發展起來的,這些現象包括遺傳突變自然選擇以及雜交等。

遺傳演算法廣泛應用在生物信息學、系統發生學、計算科學、工程學、經濟學、化學、製造、數學、物理、藥物測量學和其他領域之中。

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

遺傳演算法的機理[編輯]

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

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

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

  • 進化次數限制;
  • 計算耗費的資源限制(例如計算時間、計算佔用的內存等);
  • 一個個體已經滿足最優值的條件,即最優值已經找到;
  • 適應度已經達到飽和,繼續進化不會產生適應度更好的個體;
  • 人為干預;
  • 兩種或更多種的組合。

一個典型的遺傳演算法要求: 一個基因表示的求解域, 一個適應度函數來評價解決方案。


演算法[編輯]

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

GA參數[編輯]

  • 種群規模(P,population size):即種群中染色體個體的數目。
  • 字串長度(l, string length)
  • 交叉機率(pc, probability of performing crossover):控制著交叉算子的使用頻率。交叉操作可以加快收斂,使解達到最有希望的最優解區域,因此一般取較大的交叉機率,但交叉機率太高也可能導致過早收斂。
  • 變異機率(pm, probability of mutation):控制著變異算子的使用頻率,決定了遺傳演算法的局部搜索能力。
  • 中止條件(termination criteria)

模式定理[編輯]

  • 定義1 基於三值字符集(0,1,*}所產生的能描述具有某些結構相似性的0、1字元串集的字元串稱作模式。
引入模式後,我們可以看到一個串實際上隱含著多個模式,一個模式可以隱含在多個串中,不同的串之間通過模式而相互聯繫。遺傳演算法中串的運算實質上是模式的運算。因此,通過分析模式在遺傳操作下的變化,就可以了解什麼性質被延續,什麼性質被丟棄,從而把握遺傳演算法的實質,這正是模式定理所揭示的內容。
  • 定義2 模式H中確定位置的個數稱為該模式的階數,記作o(H)。
顯然,一個模式的階數越高,其樣本數就越少,因而確定性越高。
  • 定義3 模式H中第一個確定位置和最後一個確定位置之間的距離稱作該模式的定義距,記作б(H)。
模式的階數和定義距描述了模式的基本性質。
  • 模式定理 在遺傳算子選擇、交叉和變異的作用下,具有階數低、長度短、平均適應度高於群體平均適應度得模式在子代中將以指數級增長。

積木塊假設[編輯]

  • 階數低、長度短和適應度高的模式稱為積木塊
積木塊假設:階數低、長度短、適應度高的模式(積木塊)在遺傳算子作用下,相互結合,能生成階數高,長度長、適應度高的模式,可最終生成全局最優解。
與積木塊一樣,一些好的模式在遺傳演算法操作下相互拼搭、結合,產生適應度更高的串,從而找到更優的可行解,這正是積木塊假設所揭示的內容。

在線互動式演示與學習[編輯]

英國格拉斯哥大學在1997年出版了一個遺傳/進化演算法的網上在線互動式演示Java小程序: the EA_demo,以幫助進化計算的新手了解遺傳演算法的編碼和工作原理,至今仍廣泛使用,採用大學包括英國利物浦(Liverpool)大學、蘇塞克斯(Sussex)大學、北安普頓(Northampton)大學,德國烏爾姆(Ulm)大學,瑞士日內瓦(Geneva)大學,西班牙格瑞那達(Granada)大學,葡萄牙新里斯本(Nova de Lisboa)大學,美國加州大學戴維斯分校(UC Davies),加拿大卡爾加里(Calgary)大學,澳大利亞墨爾本皇家理工大學(RMIT),新加坡國立大學,台灣國立清華大學,上海交通大學,巴西PUCRS大學等。

EA_demo允許用戶直接在網頁上一代一代地手動運行,以看遺傳/進化演算法是怎樣一步一步操作的,亦可在背景中批次運行,以觀察演算法的收斂和染色體是否跳出局部最優。用戶可以改變終止代數,群體規模,交配率,變異率和選擇機制。也有其它自學課件收錄於AI中心網站歐洲軟計算中心網站

特點[編輯]

遺傳演算法在解決優化問題過程中有如下特點:

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

變數[編輯]

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

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

通過並行計算實現遺傳演算法一般有兩種,一種是所謂粗糙並行遺傳演算法,即一個計算單元包含一個種群;而另一種是所謂精細並行遺傳演算法,每一個計算單元處理一個染色體個體。

遺傳演算法有時候還引入其他變數,例如在實時優化問題中,可以在適應度函數中引入時間相關性和干擾。

適用的問題[編輯]

遺傳演算法擅長解決的問題是全局最優化問題,例如,解決時間表安排問題就是它的一個特長,很多安排時間表的軟體都使用遺傳演算法,遺傳演算法還經常被用於解決實際工程問題

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

遺傳演算法的不足之處[編輯]

遺傳演算法作為一種優化方法,它存在自身的局限性:

(1)編碼不規範及編碼存在表示的不準確性。

(2)單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值,這樣,計算的時間必然增加。

(3)遺傳演算法通常的效率比其他傳統的優化方法低。

(4)遺傳演算法容易出現過早收斂。

(5)遺傳演算法對演算法的精度、可行度、計算複雜性等方面,還沒有有效的定量分析方法。

改進的遺傳演算法[編輯]

儘管遺傳演算法有許多優點,也有許多專家學者對遺傳演算法進行不斷研究,但目前存在的問題依然很多,如:

(1)適應度值標定方式多種多樣,沒有一個簡潔、通用的方法,不利於對遺傳演算法的使用。

(2)遺傳演算法的早熟現象(即很快收斂到局部最優解而不是全局最優解)是迄今為止最難處理的關鍵問題。

(3)快要接近最優解時在最優解附近左右擺動,收斂較慢。

遺傳演算法通常需要解決一下問題,如確定編碼方案,適應度函數標定,選擇遺傳操作方式及相關控制參數,停止準則確定等。相應地,為改進簡單遺傳演算法的實際計算性能,很多學者的改進工作也是分別從參數編碼、初始群體設定、適應度函數標定、遺傳操作算子、控制參數的選擇以及遺傳演算法的結構等方面提出的。其基本途徑概括起來主要有下面幾個方面:

(1)改進遺傳演算法的組成成分或使用技術,如選用優化控制參數、適合問題特性的編碼技術等。

(2)採用混合遺傳演算法(Hybrid Genetic Alogrithm).

(3)採用動態自適應技術,在進化過程中調整演算法控制參數和編碼精度。

(4)採用非標準的遺傳操作算子。

(5)採用並行演算法。

幾種常見的改進遺傳演算法:

(1)分層遺傳演算法(Hierachic Genetic Alogrithm);

(2)CHC演算法;

(3)Messy遺傳演算法;

(4)自適應遺傳演算法(Adaptive Genetic Alogrithm);

(5)基於小生境技術的遺傳演算法(Niched Genetic Alorithm);

(6)並行遺傳演算法(Parallel Genetic Algorithm);

(7)混合遺傳演算法:

①遺傳演算法與最速下降法相結合的混合遺傳演算法;

②遺傳演算法與模擬退火法相結合的混合遺傳演算法。

發展歷史[編輯]

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

應用領域[編輯]

N700列車「氣動雙翼」的獨特空氣動力造型車鼻;是遺傳演算法運算結果

相關技術[編輯]

遺傳程序約翰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.

外部連結[編輯]