遺傳算法在平面魔方游戲中的應(yīng)用

摘要:平面魔方游戲類似于傳統(tǒng)魔方、九連環(huán)等智力游戲，它具有很高的啟智、益智的功能，并且包含了豐富的搜索優(yōu)化的算法，本文針對游戲規(guī)則，提出了一種簇減少的算法思想，并且采用遺傳算法來代替?zhèn)鹘y(tǒng)的搜索算法。最后，通過程序的實現(xiàn)和演示，對算法進行了測試和驗證。

關(guān)鍵詞:平面魔方;簇;遺傳算法

1 引言

像魔方、九連環(huán)等智力游戲都具有很高的啟智、益智的功能，并且包含了豐富的搜索優(yōu)化的算法，對這些算法的研究具有重要的理論價值和應(yīng)用價值。平面魔方是一種類似傳統(tǒng)魔方的旋轉(zhuǎn)拼圖游戲，游戲規(guī)則為:

如圖1中“初始狀態(tài)”所示，由帶有顏色的區(qū)域(這里用數(shù)字表示，一個數(shù)代表一種顏色)所構(gòu)成的N*N的矩陣區(qū)域。通過不斷旋轉(zhuǎn)場地中某些部分的正方形，擴大縱橫相連同色的區(qū)域，最終達到如圖1“完成狀態(tài)”所示。

每一次旋轉(zhuǎn)，將對n*n(n為正偶數(shù))的區(qū)域，以該區(qū)域的中心為旋轉(zhuǎn)中心，可以進行90度、180度和270度的旋轉(zhuǎn)。圖2便是示例的對4*4的區(qū)域進行270度右旋轉(zhuǎn)的樣子。

勝負的判定為，在規(guī)定的時間內(nèi)，使得各種顏色的單元格的最大連通數(shù)之和最大，在最大連通數(shù)之和相同時盡量使旋轉(zhuǎn)次數(shù)最少。

該游戲過程中包含一個基本的命題:如何用最少的旋轉(zhuǎn)次數(shù)將各種顏色連接到一起。

2 問題分析

根據(jù)問題描述，可以知道該問題最終的解有很多，解的步數(shù)也不確定。采用搜索算法時，搜索樹中的各個節(jié)點信息可以用一個數(shù)據(jù)結(jié)構(gòu)表示:(旋轉(zhuǎn)中心x坐標，旋轉(zhuǎn)中心y坐標，旋轉(zhuǎn)半徑，旋轉(zhuǎn)角度)。例如圖2中的旋轉(zhuǎn)可以表示為(1，3，2，3)，其中(1，3)表示旋轉(zhuǎn)中心的坐標，2表示為旋轉(zhuǎn)半徑，3表示270度(1表示90度，2表示180度)。

假設(shè)圖形由N*N的矩陣區(qū)域構(gòu)成，那么，可以作為旋轉(zhuǎn)中心的點有(N-1)*(N-1)個，旋轉(zhuǎn)半徑可以是1到MinDis (旋轉(zhuǎn)中心到四個邊界最短距離)中的任意一個，而對于確定中心和半徑的每一個旋轉(zhuǎn)來說又有3種旋轉(zhuǎn)角度。可以想象當N的值較大時，圖3中的搜索樹將非常龐大，本文提出采用遺傳算法來代替?zhèn)鹘y(tǒng)的搜索算法思想，在有限的計算時間和旋轉(zhuǎn)步驟內(nèi)，使得圖形中同種顏色的單元格盡量連通。

3 遺傳算法設(shè)計

使用遺傳算法解決問題時，需要確定適應(yīng)函數(shù)、編碼方案、選擇策略以及遺傳算子等信息的表示。

3.1 適應(yīng)函數(shù)的確定

先來介紹一個概念“簇”，它指的是由上下左右相鄰的超過1塊同色區(qū)域所構(gòu)成的區(qū)域。換言之，“簇”是由1個以上的同色單元格所構(gòu)成的。同理，在沒達到完成狀態(tài)之前，在圖形中將會有多塊相同顏色的“簇”。

根據(jù)游戲規(guī)則，最終的狀態(tài)就是要達到一個圖形中“簇”的數(shù)量等于顏色的數(shù)目。初始狀態(tài)到終止狀態(tài)的過程就是“簇”減少的過程。因此，我們將遺傳算法的適應(yīng)函數(shù)設(shè)定如下:

F=單元格數(shù)-“簇”數(shù)

遺傳算法就是在規(guī)定的旋轉(zhuǎn)次數(shù)內(nèi)找到函數(shù)F的最大值，F(xiàn)的理論最大值是單元格數(shù)減去顏色數(shù)。

3.2 “簇”數(shù)的計算

將保存圖形的二維數(shù)組看作“圖”結(jié)構(gòu)，每個單元格看作“圖”的一個節(jié)點，相同顏色且坐標相鄰的節(jié)點視為連通。此時，可以通過深度優(yōu)先的算法遍歷“圖”中的各個節(jié)點，從而確定“簇”數(shù)。具體算法如下:

(1)定義計數(shù)器count，初始為0，定義存放節(jié)點的棧，初始為空;

(2)如果“圖”中存在未標記結(jié)點，取一個未標記結(jié)點放入棧中，計數(shù)器增1，否則返回計數(shù)器，算法結(jié)束;

(3)如果棧為空，返回至第(2)步，否則，從棧頂取出一個節(jié)點，并標記當前取到的節(jié)點已被訪問;

(4)如果當前節(jié)點存在未標記的連通節(jié)點(相鄰且同色)，則將所有連通節(jié)點放入棧中，返回第(3)步，否則直接返回第(3)步。

3.3 編碼方案和種群的初始

對于平面魔方問題，我們采用有序串的編碼方案為遺傳算法中的個體進行編碼。假定個體是長度為L的有序串，對應(yīng)該問題的一個解，串中的每一個元素對應(yīng)一次合法的旋轉(zhuǎn)。

上面的兩個公式中表示個體，表示第i次旋轉(zhuǎn)是個體的基因，分別表示旋轉(zhuǎn)中心的橫縱坐標，分別表示旋轉(zhuǎn)的半徑和角度。

通過上述的編碼方案，我們將平面魔方問題轉(zhuǎn)換為:在規(guī)定的旋轉(zhuǎn)次數(shù)內(nèi)(L次旋轉(zhuǎn)，取決于個體的長度)，求“簇”數(shù)最少的問題。

我們假定種群大小為M，即種群中有M個個體。因此，初始種群時需要隨機產(chǎn)生M*L個旋轉(zhuǎn)，旋轉(zhuǎn)中心都是0到N-2的隨機整數(shù)(N為圖形的邊長)，旋轉(zhuǎn)半徑是1到MinDis (旋轉(zhuǎn)中心到四個邊界最短距離)的隨機整數(shù)，旋轉(zhuǎn)角度是0-2的隨機整數(shù)(0表示90度，1表示180度，3表示270度，角度以順時針為方向)。

3.4 選擇策略

在選擇策略上，本問題采用基于概率的輪轉(zhuǎn)盤選擇策略。首先，在產(chǎn)生下一代種群之前，計算出當前每個個體適應(yīng)函數(shù)的值，記為p0，p1…pL-1，并對所有值求和，記為SUM。然后，在產(chǎn)生下一代種群的第i個個體時，在0到SUM-1中產(chǎn)生一個隨機整數(shù)p，如果p小于p0，則將上一代中的第0個個體作為本輪種群的第i個個體，否則，將p減去p0，繼續(xù)與p1進行比較……。

通過上述選擇策略，我們可以使種群中適應(yīng)函數(shù)值較高的個體遺傳到下一代種群當中。

3.5 雜交和變異

雜交組合了兩個親體父體的特征，并通過交換父代相應(yīng)片斷形成兩個后代。本文問題中，假定雜交概率為pc(0到1之間的隨機小數(shù))，為新種群中的每個個體產(chǎn)生一個隨機數(shù)pci(0到1之間的隨機小數(shù))，當pci小于pc時，再隨機選擇另一個體與當前個體雜交。假設(shè)個體長度為L，在0到L-1之間產(chǎn)生隨機整數(shù)q，雜交之前的兩個個體為:

變異是一種局部隨機搜索，可提高算法的局部搜索能力。本文問題中，假定變異概率為pm(0到1之間的隨機小數(shù))，為雜交后產(chǎn)生的新個體的每一個基因(旋轉(zhuǎn))產(chǎn)生一個隨機數(shù)pmi(0到1之間的隨機小數(shù))，當pmi小于pm時，則重新隨機產(chǎn)生該基因。

3.6 算法的終止條件

本問題中，遺傳算法將在滿足以下3種條件之一時終止:

(1)存在個體的適應(yīng)函數(shù)F取得理論最大值，此時的“簇”數(shù)等于顏色數(shù)。

(2)遺傳MAX_M代，MAX_M預(yù)先設(shè)定。

(3)連續(xù)遺傳MAX_N代，群體中個體的適應(yīng)函數(shù)F的最大值無變化，MAX_N預(yù)先設(shè)定。

4 算法實現(xiàn)

根據(jù)上述分析設(shè)計，我們使用Microsoft Visual 6.0作為開發(fā)平臺，開發(fā)了該游戲軟件。下面給出遺傳算法的偽代碼:

初始種群并計算所有個體適應(yīng)函數(shù)值;

初始雜交概率pc，變異概率pm，最大遺傳代數(shù)等參數(shù);

while(!滿足終止條件)

{

for(i:0->個體數(shù)-1)

{

使用選擇策略產(chǎn)生新種群的第i個個體;

}

for(i:0->個體數(shù)-1)

{

產(chǎn)生隨機數(shù)p;

if(p

{

生成在0到個體數(shù)-1之間且不等于i

的隨機數(shù)j;

雜交個體i和個體j;

for(k:0->個體長度-1)

{

產(chǎn)生隨機數(shù)q1，q2;

if(q1

變異個體i的第k位上的基因;

if(q2

變異個體j的第k位上的基因;

}

}

}

計算所有個體適應(yīng)函數(shù)值;

}

5 算法測試

運行軟件，使用圖4中的5*5的圖作為測試用例，最大遺傳代數(shù)為10000，最大不增長代數(shù)為1000，種群大小為50，個體長度為6雜交概率0.6，變異概率0.15，在10秒內(nèi)得到最優(yōu)解。具體的旋轉(zhuǎn)方法為:(3，1，2，3)，(1，2，2，2)，(4，4，2，1)，(4，1，2，1)，(2，1，2，2)，(2，3，4，2)。最終狀態(tài)如圖4所示，測試結(jié)果經(jīng)手動測試完全正確。

6 結(jié)束語

該問題是日本第20屆國際編程大賽的題目，圖形的初始情況(圖形的大小，顏色數(shù)以及各個單元格的初始顏色等)將在比賽前由主辦方給出。在此次比賽的準備階段，我們使用傳統(tǒng)的剪枝搜索算法以及本文提出的遺傳算法，分別開發(fā)了兩套比賽程序。經(jīng)實驗驗證，在圖形較小時(7*7以下)，遺傳算法在參數(shù)設(shè)定合理的情況下與剪枝搜索算法的效率相仿，但是遺傳算法的各個參數(shù)需要提前訓(xùn)練、摸索，特別是個體的長度(旋轉(zhuǎn)的步數(shù))，因此，我們認為，在圖形較小時應(yīng)采用剪枝搜索算法。在圖形較大時(8*8以上)，由于搜索空間過龐大，在有限時間內(nèi)(5分鐘)，剪枝搜索算法和遺傳算法都不能得到最優(yōu)解，但是，圖形越大遺傳算法得到的解越要優(yōu)于剪枝搜索算法得到的解，因此，我們認為，在圖形較大時應(yīng)采用遺傳算法。

參考文獻

[1].武蘇里，王湘桃等.易陣游戲中兩子交換算法的研究[J].計算機應(yīng)用與軟件，2009(2).

[2].劉汝佳，黃亮.算法藝術(shù)與信息學競賽[M].北京:清華大學出版社，2004.

[3].鄭宗漢，鄭曉明.算法設(shè)計與分析[M].北京:清華大學出版社，2005.

[4].金聰，戴上平，等.人工智能教程[M].北京:清華大學出版社，2007.