Loading AI tools
竞争算法搜索空间问题 来自维基百科,自由的百科全书
基因演算法(英語:Genetic Algorithm,GA)是計算數學中用於解決最佳化的搜尋演算法,是進化演算法的一種。進化演算法最初是借鑑了進化生物學中的一些現象而發展起來的,這些現象包括遺傳、突變、自然選擇以及雜交等等。
基因演算法通常實現方式為一種電腦模擬。對於一個最佳化問題,一定數量的候選解(稱為個體)可抽象表示為染色體,使種群向更好的解進化。傳統上,解用二進制表示(即0和1的串),但也可以用其他表示方法。進化從完全隨機個體的種群開始,之後一代一代發生。在每一代中評價整個種群的適應度,從當前種群中隨機地選擇多個個體(基於它們的適應度),通過自然選擇和突變產生新的生命種群,該種群在演算法的下一次迭代中成為當前種群。
在基因演算法裡,最佳化問題的解被稱為個體,它表示為一個變數序列,叫做染色體或者基因串。染色體一般被表達為簡單的字串或數字串,不過也有其他的依賴於特殊問題的表示方法適用,這一過程稱為編碼。首先,演算法隨機生成一定數量的個體,有時候操作者也可以干預這個隨機產生過程,以提高初始種群的品質。在每一代中,都會評價每一個體,並通過計算適應度函式得到適應度數值。按照適應度排序種群個體,適應度高的在前面。這裡的「高」是相對於初始的種群的低適應度而言。
下一步是產生下一代個體並組成種群。這個過程是通過選擇和繁殖完成,其中繁殖包括交配(crossover,在演算法研究領域中我們稱之為交叉操作)和突變(mutation)。選擇則是根據新個體的適應度進行,但同時不意味著完全以適應度高低為導向,因為單純選擇適應度高的個體將可能導致演算法快速收斂到局部最佳解而非全域最佳解,我們稱之為早熟。作為折中,基因演算法依據原則:適應度越高,被選擇的機會越高,而適應度低的,被選擇的機會就低。初始的資料可以通過這樣的選擇過程組成一個相對最佳化的群體。之後,被選擇的個體進入交配過程。一般的基因演算法都有一個交配概率(又稱為交叉概率),範圍一般是0.6~1,這個交配概率反映兩個被選中的個體進行交配的概率。例如,交配概率為0.8,則80%的「夫妻」會生育後代。每兩個個體通過交配產生兩個新個體,代替原來的「老」個體,而不交配的個體則保持不變。交配父母的染色體相互交換,從而產生兩個新的染色體,第一個個體前半段是父親的染色體,後半段是母親的,第二個個體則正好相反。不過這裡的半段並不是真正的一半,這個位置叫做交配點,也是隨機產生的,可以是染色體的任意位置。再下一步是突變,通過突變產生新的「子」個體。一般基因演算法都有一個固定的突變常數(又稱為變異概率),通常是0.1或者更小,這代表變異發生的概率。根據這個概率,新個體的染色體隨機的突變,通常就是改變染色體的一個位元組(0變到1,或者1變到0)。
經過這一系列的過程(選擇、交配和突變),產生的新一代個體不同於初始的一代,並一代一代向增加整體適應度的方向發展,因為總是更常選擇最好的個體產生下一代,而適應度低的個體逐漸被淘汰掉。這樣的過程不斷的重複:評價每個個體,計算適應度,兩兩交配,然後突變,產生第三代。周而復始,直到終止條件滿足為止。一般終止條件有以下幾種:
基因演算法在解決最佳化問題過程中有如下特點:
最簡單的基因演算法將染色體表示為一個數位串,數值變數也可以表示成整數,或者實數(浮點數)。演算法中的雜交和突變都是在位元組串上進行的,所以所謂的整數或者實數表示也一定要轉化為數位形式。例如一個變數的形式是實數,其範圍是0~1,而要求的精度是0.001,那麼可以用10個數位表示:0000000000表示0,1111111111表示1。那麼0110001110就代表0.398。
在基因演算法里,精英選擇是一種非常成功的產生新個體的策略,它是把最好的若干個個體作為精英直接帶入下一代個體中,而不經過任何改變。
通過平行計算實現基因演算法一般有兩種,一種是所謂粗糙並列基因演算法,即一個計算單元包含一個種群;而另一種是所謂精細並列基因演算法,每一個計算單元處理一個染色體個體。
基因演算法有時候還引入其他變數,例如在即時最佳化問題中,可以在適應度函式中引入時間相關性和干擾。
基因演算法擅長解決的問題是全域最佳化問題,例如,解決時間表安排問題就是它的一個特長,很多安排時間表的軟體都使用基因演算法,基因演算法還經常被用於解決實際工程問題。
跟傳統的爬山演算法相比,基因演算法能夠跳出局部最佳而找到全域最佳點。而且基因演算法允許使用非常複雜的適應度函式(或者叫做目標函式),並對變數的變化範圍可以加以限制。而如果是傳統的爬山演算法,對變數範圍進行限制意味著複雜的多的解決過程,這方面的介紹可以參看受限最佳化問題和非受限最佳化問題。
基因演算法由密西根大學的約翰·霍蘭德和他的同事於二十世紀六十年代在對細胞自動機(英文:cellular automata)進行研究時率先提出。在二十世紀八十年代中期之前,對於基因演算法的研究還僅僅限於理論方面,直到在匹茲堡召開了第一屆世界基因演算法大會。隨著電腦計算能力的發展和實際應用需求的增多,基因演算法逐漸進入實際應用階段。1989年,紐約時報作者約翰·馬科夫寫了一篇文章描述第一個商業用途的基因演算法--進化者(英文:Evolver)。之後,越來越多種類的基因演算法出現並被用於許多領域中,財富雜誌500強企業中大多數都用它進行時間表安排、資料分析、未來趨勢預測、預算、以及解決很多其他組合最佳化問題。
遺傳程式是John Koza與基因演算法相關的一個技術,在遺傳程式中,並不是參數最佳化,而是電腦程式最佳化。遺傳程式一般採用樹型結構表示電腦程式用於進化,而不是基因演算法中的列表或者陣列。一般來說,遺傳程式比基因演算法慢,但同時也可以解決一些基因演算法解決不了的問題。
互動式基因演算法是利用人工評價進行操作的基因演算法,一般用於適應度函式無法得到的情況,例如,對於圖像、音樂、藝術的設計和「最佳化」,或者對運動員的訓練等。
類比退火是解決全域最佳化問題的另一個可能選擇。它是通過一個解在搜尋空間的隨機變動尋找最佳點的方法:如果某一階段的隨機變動增加適應度,則總是被接受,而降低適應度的隨機變動根據一定的概率被有選擇的接受。這個概率由當時的退火溫度和適應度惡化的程度決定,而退火溫度按一定速度降低。從類比退火演算法看,最佳化問題的解是通過尋找最小能量點找到的,而不是尋找最佳適應點找到的。類比退火也可以用於標準基因演算法里,只要把突變率隨時間逐漸降低就可以了。
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.