遺傳算法在平面魔方游戲中的應用

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

關鍵詞:平面魔方;簇;遺傳算法

1 引言

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

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

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

勝負的判定為，在規定的時間內，使得各種顏色的單元格的最大連通數之和最大，在最大連通數之和相同時盡量使旋轉次數最少。

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

2 問題分析

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

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

3 遺傳算法設計

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

3.1 適應函數的確定

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

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

F=單元格數-“簇”數

遺傳算法就是在規定的旋轉次數內找到函數F的最大值，F的理論最大值是單元格數減去顏色數。

3.2 “簇”數的計算

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

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

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

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

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

3.3 編碼方案和種群的初始

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

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

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

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

3.4 選擇策略

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

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

3.5 雜交和變異

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

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

3.6 算法的終止條件

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

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

(2)遺傳MAX_M代，MAX_M預先設定。

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

4 算法實現

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

初始種群并計算所有個體適應函數值;

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

while(!滿足終止條件)

{

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

{

使用選擇策略產生新種群的第i個個體;

}

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

{

產生隨機數p;

if(p

{

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

的隨機數j;

雜交個體i和個體j;

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

{

產生隨機數q1，q2;

if(q1

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

if(q2

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

}

}

}

計算所有個體適應函數值;

}

5 算法測試

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

6 結束語

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

參考文獻

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

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

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

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