基因遺傳演算法

Post date: 2013/1/16 上午 04:28:50

基因遺傳演算法是一個保留大量狀態種群的隨機爬山法搜尋。新的狀態透過突變和雜交產生,雜交把來自種群的狀態對結合在一起。

再提到隨機爬山法之前先說一下爬山法,它是一個向值增加的方向持續移動的簡單迴圈過程——亦即,登高。它將會在到達一個「峰頂」時終止,相鄰狀態中沒有比它更高的值。這個演算法不維護搜尋樹,因此當前節點的資料結構只需要記錄當前狀態與其目標函數值。

爬山法不會前瞻與當前狀態不直接相鄰的狀態值。這就像健忘的人在大霧中試圖登頂聖母峰一樣。

爬山法搜尋演算法,其為最基本的局部搜尋技術。在每一步中當前的節點都會被最佳鄰節點所代替;按這種方式,鄰節點意味著有最高的值,但是如果使用啟發函數成本估計h,我們要找的就是h 最低的鄰節點

爬山法有時稱為貪婪局部搜尋,因為它只是選擇相鄰狀態中最好的一個,而不事先考慮之後的下一步往哪個方向走。

爬山法能很快朝著解的方向進展,因為它通常很容易改進一個壞的狀態。

爬山法經常會遇到下面的問題:

● 局部極大值:局部極大值是一個比它的每個相鄰狀態都高的峰頂,但是比全局最大值要低。爬山法演算法到達局部極大值附近就會被拉向峰頂,然後被卡在局部極大值處而無處可走。圖4.1示意性地表現了這種情況。

圖4.1 一維的狀態空間地形圖,

高度對應於目標函數。目標是找到

全局最大值。如箭頭所示,爬山搜

尋法會修正當前狀態並試圖改進

它。各種地形特徵在課文中有定義

更具體地,圖4.3(b)中的狀態事實上是一個局部極大值(即成本h 的局部極小值);不管移動哪個皇后得到的情況都會比原來差。

圖4.3 (a)八皇后問題的一個狀態,其中啟發函數成本估計h = 17,方格中顯示的數字表示將這一列中的皇后移到該方格而得到的後繼者的h 值。最佳移動在圖中已標記出來了。(b)八皇后問題狀態空間中的一個局部極小值;該狀態的h = 1,但是它的每個後繼者的h 值都比它高

● 山脊:圖4.4 顯示了山脊的情況。山脊造成一系列的局部極大值,貪婪演算法處理這種情況是很難的。

圖4.4 為什麼山脊會給爬山法帶來困難

的圖示。圖中的狀態網格(黑色圓點)疊加

在從左到右上升的山脊上,創造了一個

彼此不直接相連的局部極大值序列。從

每個局部極大值出發,所有的可能行動

都是指向下山方向

● 高原:高原是在狀態空間地形圖上的一塊平坦區域。它可能是一塊平坦的局部極大值,不存在上山的出路,或者是一個山肩,從山肩還有可能取得進展(參見圖4.1)。爬山法搜尋可能會在高原迷路。

隨機爬山法採用方式是隨機產生後繼者節點直到產生一優於當前節點的後繼者。這個演算法在有很多後繼者節點的情況下(例如上千個)是個好策略。

隨機重新開始爬山法採納了一條著名的諺語:「如果一開始沒有成功,那麼嘗試,繼續嘗試。它透過隨機產生的初始狀態[1]來進行一系列的爬山法搜尋,直到找到目標時停止搜尋。這個演算法是完備的機率接近於1,原因是它最終會產生一個目標狀態作為初始狀態。如果每次爬山法搜尋成功的概率為p,那麼需要重新開始搜尋的期望次數為1/p。對於不允許側向移動的八皇后問題實例,p ≈ 0.14,因此我們大概需要7 次疊代就能找到目標(6 次失敗1 次成功)。

所需步數的期望值為一次成功疊代的搜尋步數加上失敗的搜尋步數與(1 − p)/p 的乘積,大約是22步。當我們允許側向移動時,平均需要疊代約1/0.94 ≈ 1.06 次,平均的數為(1×21) + (0.06/0.94)×64 ≈25 步。那麼對於八皇后問題,隨機重新開始的爬山法實際上是非常有效的。甚至對於三百萬個皇后,這個方法用不了一分鐘就可以找到解[2]。

爬山法演算法成功與否大部份取決於狀態空間地形圖的形狀:如果在圖中幾乎沒有局部極大值和高原,隨機重新開始的爬山法將會很快地找到好的解。

局部剪枝搜尋

在記憶體中只保存一個節點,看來是對記憶體限制問題的一個極端反應。局部剪枝搜尋(localbeam search)演算法[3]記錄k 個狀態而不是一個。它由k 個隨機產生的狀態開始。每一步都產生全部k 個狀態的所有後繼者狀態。如果其中有一個是目標狀態,演算法就停止。否則,它從整個後繼者列表中選擇k 個最佳的後繼者,然後重複這個過程。

隨機剪枝搜尋不是從候選後繼者集合中選擇最好的k 個後繼者狀態,而是按一定概率隨機地選擇k 個後繼者狀態,其中選擇給定後繼者狀態的概率是狀態值的遞增函數。隨機剪枝選擇和自然選擇的過程有些相似性,「狀態」(生物體)根據它的「值」(適應性)產生它的「後繼者」(後代)作為下一代。

基因遺傳演算法(genetic algorithm,或縮寫為GA)是隨機剪枝搜尋的一個變化形式,它不是透過修改單一狀態而是透過把兩個父代結合來產生後繼者的。它與自然選擇類似,這點和隨機剪枝搜尋是一樣的,除了我們現在處理的是有性繁殖而不是無性繁殖。

像剪枝搜尋一樣,基因遺傳演算法也是從k 個隨機產生的狀態開始,我們稱作種群。每個狀態,或稱個體,用一個有限長度的字串表示——通常是0、1 字串。例如,八皇后問題的狀態必須指定八個皇后的位置,每列有八個位置,那麼一個狀態則需要8 × log28 = 24 位元來表示。或者每個狀態可以由八個數字表示,每個數字的範圍都是從1 到8。(我們將在後面看到這兩種不同的編碼形式其表現差異很大。圖4.6(a)顯示了一個由4 個表示八皇后狀態的8 數字字串組成的種群。

http://blog.udn.com/puzzlez/4342425

西洋棋的目的

西洋棋是一種兩人棋戲,目的是先將對方國王殺死者勝。

一、開局的擺設方式

※西洋棋由白棋先行。棋盤右下角(h1)必須為白格。

白棋皇后置於白格(d1);黑棋皇后置於黑格(d8)。

皇后(Queen)的走法與吃法:

1.只要沒有棋子擋住,可以直走無限步,也可以斜走無限步。

2.皇后是子力最強的棋子。

◆棋子的走法與吃法

西洋棋一共有32枚棋子──16枚黑(深)色,16枚白(淺)色。分別由兩位玩家持有。這16枚所含的軍種及數量表列如下。西洋棋一共只有六種軍種:

棋子圖示

名稱

國王(King)

皇后(Queen)

主教(Bishop)

騎士(Knight)

城堡(Rook)

士兵(Pawn)

每位棋手擁有個數

1

1

2

2

2

8

走法及吃法簡述

四面八方,只走一步。

四面八方,走無限步。

斜走無限步。

直走兩格,再往旁邊走一格。可跨越其他棋子。

直走無限步。

未曾動過的士兵可選擇向前走一步或兩步。已移動過的士兵只能向前走一步。不可後退。

兵只能吃「斜前」方的棋子。

八皇后問題

八皇后問題是一個以西洋棋為背景的問題:如何能夠在 8×8 的西洋棋棋盤上放置八個皇后,使得任何一個皇后都無法直接吃掉其他的皇后?為了達到此目的,任兩個皇后都不能處於同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題:這時棋盤的大小變為n×n,而皇后個數也變成n若且唯若 n = 1 或 n ≥ 4 時問題有解。

八皇后問題的解

八皇后問題一共有 92 個互不相同的解。如果將旋轉和對稱的解歸為一種的話,則一共有12個獨立解,具體如下:

圖4.6 基因遺傳演算法,圖解說明以數字字串表示八皇后的狀態。(a)是初始種群,(b)是適應度函數,(c)是配對結果。(d)是它們雜交產生的後代,(e)是突變的結果

圖4.6(b)-(e)顯示了產生下一代狀態的過程。在(b)中,每個狀態都由它的目標函數或適應度函數(在基因遺傳演算法的術語裡)給出評價值(適應值)。對於好的狀態,適應度函數將返回較高的值,因此,對於八皇后問題,我們用不相互攻擊的皇后對的數目來表示,最佳解的適應值是28。這四個狀態的適應值分別是24,23,20 和11。在這個特定的基因遺傳演算法形式中,被選擇進行繁殖的概率直接與個體的適應值成正比,其百分比在原始得分旁邊標出。

在(c)中,按照(b)中的機率隨機地選擇兩對進行繁殖。注意其中的一個個體被選擇了兩次而另一個一次也沒選中[4]。對於要配對的每一對個體,雜交點是在字串中隨機選擇的一個位置。在圖4.6 中,雜交點在第一對的第三數字之後和在第二對的第五數字之後[5]。

在(d)中,後代本身是透過父代字串在雜交點上進行雜交而創造出來的。例如,第一對的第一個後代從第一個父代得到了前三數字、從第二個父代那裡得到剩下的數字,而第二個後代從第二個父代得到了前三數字、從第一個父代得到剩下數字。圖4.7 顯示了這次繁殖過程中涉及的八皇后狀態。

這個例子顯示一個事實,如果兩個父代字串差異很大,那麼雜交產生的狀態和每個父代狀態都相差很遠。通常的情況是過程中早期的群體是多樣化的,因此雜交(類似於模擬退火)在搜尋過程的早期階段在狀態空間中常採用較大的步調,而在後來當大多數個體都很相似的時候採用較小的步調。

模擬退火(simulated annealing)就是這樣一個演算法。在冶金中,退火是為了增強金屬和玻璃的韌性或硬度而先把它們加熱到高溫再讓它們逐漸冷卻的過程,能使材料結合成一個低能量的結晶態。

為了更好地理解模擬退火演算法,讓我們把視線從爬山法轉移到梯度下降(也就是成本最小化),想像使不平表面上的一個乒乓球掉到最深的裂縫中的任務。如果我們只是讓乒乓球在表面上滾動,那麼它會停留在局部極小點。如果我們晃動平面,我們可以使乒乓球彈出局部極小點。技巧是晃動要足夠大讓乒乓球能從局部極小點彈出來,但又不能太大把它從全局最小點趕出來。模擬退火的解決辦法就是開始時使勁搖晃(也就是先高溫加熱)然後慢慢降低搖晃的強度(也就是逐漸降溫)。

圖4.7 與圖4.6(c)中的前兩個父代還有圖4.6(d)中的第一個後代相對應的八皇后問題的狀態。陰影部分的列在雜交過程中丟失了,非陰影部分的列保留了下來

最後,在(e)中每個位置都會按照一個獨立的小概率隨機地變異。在第一、第三和第四個後代中都有一個數字發生了突變。在八皇后問題中,這相當於隨機地選取一個皇后把它隨機地放到該列的某一個方格裡。圖4.8 描述了一個實作了所有這些步驟的演算法。

像隨機剪枝搜尋一樣,基因遺傳演算法結合了上山的趨勢和隨機的探索,並在並列搜尋引線之間交換資訊。基因遺傳演算法最主要的優點,如果有的話,還是來自於雜交的操作。不過可以在數學上證明,如果基因編碼的位置在初始的時候就隨機地轉換的話,雜交就沒有優勢了。直觀地講,雜交的優勢在於它能夠將獨立發展出來而能執行有用功能的「磚塊」(多個相對固定的字元構成)結合起來,因此提高了搜尋操作的解析度水準。例如,將前三個皇后分別放在位置2、4 和6(互相不攻擊)就組成了一個有用的磚塊,它可以和其他有用的磚塊結合起來構造問題的解。

基因遺傳演算法的理論用模式(schema)的想法解譯了這是怎樣運轉的,模式就是其中某些數字未確定的一個子字串。例如,模式246*****描述了所有前三個皇后的位置分別是2、4、6 的狀態。能匹配這個模式的字串(例如24613578)被稱作該模式的實例。可以顯示,如果一個模式的實例的平均適應值是超過均值的,那麼種群內這個模式的實例數量就會隨時間增加。顯然,如果鄰近位元相互之間是無關的,那麼這個效果就沒有那麼顯著了,因為只有很少的鄰接磚塊能提供一致的好處。基因遺傳演算法在模式與解的有意義的成份相對應時才工作得最好。例如,如果字串表示的是一個天線,那麼這些模式就表示天線的組成部分,諸如反射器和偏轉儀。一個好的組成部分在各種不同設計下很可能都是好的。這說明基因遺傳演算法的成功運用需要仔細的知識表示工程。

實際上,基因遺傳演算法在最佳化問題上有很廣泛的影響,諸如電路佈局和零工型工廠間排程問題。現在,還不清楚基因遺傳演算法的吸引力是源自其性能,還是源自其美學角度滿足了進化論的形式。為了確認在什麼情況下使用基因遺傳演算法能夠達到好的效果,還有很多研究工作要做。

Genetic Algorithm

Genetic Algorithm(基因演算法,又稱遺傳演算法)主要概念是使用自然界上,兩性生殖的演化機制,使用遺傳(inheritance)、選擇(selection)、雜交(crossover)、突變(mutation)、以及『物競天擇、適者生存』的概念,讓優秀的個體會被留下來,繼續繁殖;而相對差的個體將會慢慢被淘汰,直到絕種。此演算法基於優生學的理論基礎,認為相對優秀的基因互相交配才可以產生更為優秀的後代,但是,為了確保後代的多樣性,又加入了突變的機制,不會讓後代最終都趨於一致。一般來說,基因演算法都能夠找到不錯的解。

此方法最常被使用於搜尋近似最佳解,因此,在很多領域的研究上,只要是需要蒐尋最佳解,都可以使用基因演算法。

方法介紹

在基因演算法裡,問題的解稱之為個體(individual),會使用一個變數序列表示,稱之為染色體(chromosome)。通常會將個體編碼成簡單的數字字串,當然也是有其他特殊的表示方式。

而每一個個體,我們都會評估其適應值(fitness),用以表示此個體對此環境的適應能力,越能夠適應環境的個體將會有越高的機率被選中來產生下一代。

傳統上,會使用隨機的方式產生N個第一代個體群,使用者亦可介入產生第一代個體群的方式。產生的每一個個體,我們都會先評估其適應值(fitness),而下一代的產生是根據其適應值從當前的個體群中選出數個個體,並對其改變(雜交或是有機會隨機突變),新產生出來的個體即為下一代。

而此演算法的終止條件,通常有兩種方式:其一是經過特定次數的遺傳之後就停止;或是出現適應值超過特定門檻值的個體就終止。

一個典型的基因演算法需要:

    1. 一個基因序列(genetic representation)用以表示其問題的解
    2. 一個用來評估問題解的適應力函式(fitness function)

方法流程

以下介紹基因演算法的主要流程,範例為使用基因演算法來解八皇后(Eight queens)。

    1. 進行初始化。
    2. 重複進行選擇>雜交>突變,直到產生一代所需的個體數量時,即完成一次繁殖。
    3. 當終止條件達成時,停止此演算法。

初始

    1. 定義基因序列,使用染色體表示此問題的解。
        • 使用8個數字(0~7)來代表這8列上的皇后,每一個數字代表該列的皇后是位於第幾行。
  1. 例如:24751314、41700256。
    1. 定義適應力函式,用來評估此解的好壞。
        • 從第一列皇后開始計算,若不會吃右列的其他皇后,每一個加一分,故最高分為7+6+5+4+3+2+1=28分。
        • 例如:f(41700256)=24、f(12277051)=23、f(24713603)=27、
  1. f(71420635)=28(此為最佳解)
    1. 使用亂數產生N個第一代個體群。
        • 設N=5,則隨機產生5組第一代個體
        • 例如:51341714、16705214、57130241、67501230、14074251。

選擇

    1. 評估所有群體中的個體適應力。
    2. 根據適應力來選出兩個個體,適應力越高的個體會有較高的機率被選中。
        • 不僅僅只挑出適應力最高的是因為這樣做可能會產生出局部最佳解(Local solution),並不是全域性的最佳解(Global solution)。

雜交

將兩個選出來的個體進行雜交(Crossover)

    • 雜交的方式有很多種,我們使用單點雜交(One-point crossover)的方式。
        1. 隨機選擇一個位置將此兩個基因切成兩段。
            • 51341714和16705214 => 5134 \ 1714 和 1670 \ 5214
        2. 進行雜交
            • 51345214 和 16701714

突變

為了確保群體的多樣性,讓個體會有微小的機率進行突變。

    • 突變方式亦有很多種,我們使用單點突變(Single point mutation)的方式。
        • 當微小機率發生時,將此染色體的其中一個基因進行突變。
        • 51345214 -> 51345?14 -> 51345714

終止

常用的終止條件有:

    1. 進行了特定次數的繁衍。
    2. 出現滿足特定適應力的個體。
        • 例如:解八皇后問題中,若出現適應力為28的個體,即為找到最佳解。
    3. 達到計算耗費的資源限制(例如:計算時間、計算空間等)。
    4. 人為干涉。
    5. 以上兩種或是更多種的組合。

程式範例

以下為使用基因演算法來解決八皇后(Eight queens)的範例,以C++實作,僅供參考。

一開始,我們需要定義一些參數來控制基因演算法。

// 染色體長度

#define GEN_LENGTH 8

// 每一代的數量

#define POPULATION_COUNT 50

// 繁衍代數

#define GENERATION_COUNT 10000

// 突變機率

#define MUTATION_RATE 0.1

初始

首先,先使用數字字串來表示其問題的解。

class eightQ

{

public:

eightQ();

void randQ();

int getScore();

void show();

vector<int> sit;

};

並且定義此染色體的適應力函式,從第一列的皇后開始計算,若該皇后不會吃到右列其他皇后,每一個加一分,故最高分為7+6+5+4+3+2+1=28分。

int eightQ::getScore()

{

int nScore = 0;

for (int i = 0; i < GEN_LENGTH; ++i)

{

int iPosX = i;

int iPoxY = sit[i];

//與其他皇后比較

for (int j = i + 1; j < GEN_LENGTH; ++j)

{

//若不與此皇后同ROW

if (!(iPoxY == sit[j]))

//若不在此皇后右斜上

if (!(iPoxY - iPosX == sit[j] - j))

//若不在此皇后右斜下

if (!(iPosX + iPoxY == sit[j] + j))

nScore++;

}

}

return nScore;

}

接著,我們先隨機產生第一代族群。

void GA::init()

{

eightQ newQ;

// 隨機產生第一代

for(int i = 0 ; i < POPULATION_COUNT ; ++i)

{

newQ.randQ();

thisGen.push_back(newQ);

}

theBest = newQ;

}

選擇

我們根據適應力來進行選擇,分數越高的染色體會有較高的機會被選到來進行下一代的繁殖,本實作是先複製選到的染色體到母親或父親族群裡面,之後會用來雜交。

void GA::reproduction()

{

DadPool.clear();

MomPool.clear();

int nScoreSum = 0;

vector<int> vAccumulate;

// 將此代所有個體的適應力累加

for(int i = 0 ; i < POPULATION_COUNT ; ++i)

{

nScoreSum += thisGen[i].getScore();

vAccumulate.push_back(nScoreSum);

}

// 依照適應力的比例選擇母親與父親

for(int i = 0 ; i < POPULATION_COUNT ; ++i)

{

int nRand = rand() % nScoreSum;

for(int j = 0 ; j < POPULATION_COUNT ; ++j)

if(nRand < vAccumulate[j])

{

DadPool.push_back(thisGen[j]);

break;

}

nRand = rand() % nScoreSum;

for(int j = 0 ; j < POPULATION_COUNT ; ++j)

if(nRand < vAccumulate[j])

{

MomPool.push_back(thisGen[j]);

break;

}

}

}

雜交

根據選擇出來父母族群,每一對進行雜交。我們雜交的方式是使用單點雜交,先隨機選擇要切染色體的位置,之後,新的染色體前半部使用父親的染色體,後半部使用母親的染色體,產出N個下一代。

void GA::crossover()

{

int nPos;

thisGen.clear();

// 使用單點雜交

for(int i = 0 ; i < POPULATION_COUNT ; ++i)

{

// 決定雜交位置 3~6

nPos = rand()%4 + 3;

eightQ newQ;

// 前面使用爸爸的染色體

for(int j = 0 ; j < nPos ; ++j)

{

newQ.sit[j] = DadPool[i].sit[j];

}

// 後面使用媽媽的染色體

for(int j = nPos ; j < GEN_LENGTH ; ++j)

{

newQ.sit[j] = MomPool[i].sit[j];

}

thisGen.push_back(newQ);

}

}

突變

為了確保族群的多樣性,我們給定了一個小的機率會發生突變。突變的方式使用單點突變,先進行判斷是否要進行突變,若要突變的話,隨機選擇一個基因,並隨機突變。在這裡,我們也順便放入儲存族群中最好的染色體的判斷式,若出現完美的染色體時,即可結束本演算法。

void GA::mutation()

{

// 每一個染色體判斷要不要突變

for(int i = 0 ; i < POPULATION_COUNT ; ++i)

{

double dRate = (double)(rand() % 10000) / 10000.0f;

if(dRate < MUTATION_RATE)

{

// 決定突變位置

int nPos = MyRand();

thisGen[i].sit[nPos] = MyRand();

}

// 計算是否比最佳解更好

if(thisGen[i].getScore() > theBest.getScore())

theBest = thisGen[i];

}

}

主程式

依照上述的流程,進行了GENERATION_COUNT次或是出現適應力為28的染色體即停止,並印出該代所有染色體以及最佳的染色體。

int main()

{

srand((unsigned)time(0));

GA ga;

int nCounter = 0;

// 初始化

ga.init();

cout << "基因演算法開始" << endl;

while(nCounter < GENERATION_COUNT)

{

ga.reproduction();

ga.crossover();

ga.mutation();

//ga.show();

++nCounter;

//cout << "第" << nCounter << "代繁殖完成!" << endl;

// 若最好的個體已經找到,即可結束。

if(ga.theBest.getScore() >= 28)

break;

}

cout << "第" << nCounter << "代所有個體如下所示:" << endl;

ga.show();

cout << "最佳解為";

ga.theBest.show();

cout << "其分數為" << ga.theBest.getScore() << endl;

system("PAUSE");

return 0;

}