遺傳算法解n-queens問題
一， 課程介紹：
1.1 實驗内容
通過上一節的學習，對遺傳算法的理論知識和簡單實作有了初步了解。這一節，通過學習Pyevolve子產品，來更好地解決問題。
這一節我們通過兩個執行個體了解Pyevolve的使用方法，并且分析算法結果。通過執行個體n-queens問題了解Pyevolve遺傳算法架構。
1.2 實驗知識點
通過本節學習，我們将學習到以下知識點：
- Pyevolve的算法架構，及使用操作
- 進化算法的算子操作
- 可視化結果分析
1.3 實驗環境
- 作業系統：Ubuntu 14.04.5
- Xfce 終端
- Python版本：2.7.6
1.4 适合人群
本課程難度為一般，屬于初級級别課程。 比較适合以下使用者：
- 熟悉Python基礎的使用者
- 對智能算法比較感興趣的使用者
- 對多元問題優化有興趣的使用者
1.5 代碼擷取
（如果第一節有操作過，此步略過。）
cd Code
wget http://labfile.oss.aliyuncs.com/courses/776/Code_genetic.zip
unzip Code_genetic.zip
1.6 實驗效果
二，開發準備
2.1 virtualenv環境配置
（如果在先前已經進行過，此步略過）
#安裝virtualenv
sudo pip install virtualenv
#建立虛拟環境
virtualenv genetic_python
#cd genetic_python/bin/
source ./activate
配置成功之後的效果圖：
2.2 在新配置的Python環境中安裝相關子產品
#由上節環境直接下一節實驗進入無需安裝
$ sudo apt-get install python-numpy python-matplotlib
#本節實驗需要安裝子產品
$ sudo pip install pyevolve
2.3 運作示例代碼
- rastrigin函數驗證
cd Code/Code_genetic
Python rastrigin_problem.py
- 皇後問題
cd Code/Code_genetic
Python 8queens.py
- 提取資料庫個體資訊并畫圖
cd Code/Code_genetic
Python pyevole_graph.py -i queens -1
三，實驗步驟
3.1 Pyevolve
Pyevolve是一個完全由Python編寫的遺傳算法子產品，特點是： 純Python語言編寫；API接口簡單好用；進化過程可視化；可擴充；優化速度快；操作算子全面；有預設參數；開源。
3.1.1 基本概念：
- Raw score表示适應度函數傳回的還未進行比例換算的适應度。
- Fitness score對Rawscore進行比例換算後的适應度值，如果你使用線性的比例換算（Scaling LinerScaling(),fitness score将會使用線性方法進行換算，fitness score代表了個體與種群的相關程度）
- Sample genome是所有genome進行複制的基礎。
3.1.2 Pyevolve驗證
在遺傳算法中，經常使用一個函數來測試遺傳算法，這個函數就是Rastrigin函數，對于有兩個獨立變量的 Rastrigin函數，其定義的形式如下：
如函數圖所展現的，該函數有非常多的局部極小點，而僅僅隻有一個全局最小點，這個點就是[0 0]，在這個點處的函數的值為0，是以具有欺騙性，容易陷入局部解。該函數被用來測試遺傳算法的主要原因是，對于傳統的基于梯度的算法對付這個具有非常多局部極小點的函數來說，那是十分的困難。
是以我們可以通過示例代碼驗證pyevolve的搜尋能力：
cd Code/Code_genetic
Python rastrigin_problem.py
如果不想操作此步，請繼續往想看，有更好玩的例子學習呢！
3.2 n-queens 問題
八皇後問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。計算機發明後，有多種計算機語言可以解決此問題。窮舉法在問題規模不大的情況下還可以适用，回溯法是求解次問題的經典算法。但N皇後問題是個NP問題，随着皇後數目的增多，求解複雜程度激增，就需要利用人工智能的算法求解。遺傳算法在求解一些NP完全問題上得到了廣泛的應用。是以可以解決N皇後問題。
3.3 整體流程
3.4 定義目标函數
遺傳算法的難處在于如何将一個現實問題轉化為函數問題。比如現在我們要解決的N皇後問題。 這裡一個比較好的思路是：
（1）用個體表示每一行中皇後的位置genome[i],genome[j]
（2）在函數中用一定的條件标準來表示現實中的規則
（3）函數傳回一個正向相關的的數值，數值越大，滿足規則的個體越多。
根據皇後問題的描述可知，皇後位置不能出現以下兩種情況：
圖一所示的，同行或同列。即i = j(同行)， genome[i] = genome[j] (同列)。
(圖一)
圖二所示的，處于同一斜線。即 i !=j and abs(j - i) = abs(genome[j]-genome[i])。
因為我們的個體數目和格子數目相等，是以不會出現有多餘的個體占據同一行，而且因為個體各不相同，是以不會出現同一列的情況。
是以最終，問題簡化到隻考慮棋子處于同一斜線的情況。
(圖二)
分析過後，可以定義出皇後問題的描述函數：
首先導入依賴庫
from pyevolve import *
from random import shuffle
#可以更改皇後數目，這裡以64皇後為例
BOARD_SIZE =
def queens_eval(genome):
#用一個變量表示，碰撞即不滿足規則的個體數目
collisions =
for i in xrange(, BOARD_SIZE):
#如果第i行不在genome中，則傳回0
#可以測試一下随機生成的個體是包含了全部位置資訊
if i not in genome: return
for i in xrange(, BOARD_SIZE):
col = False
#因為随機生成的個體兩兩不同，是以不會這裡可以忽略
#皇後處于同一行或同一列的情況，隻需考慮對角線的情況。
for j in xrange(, BOARD_SIZE):
if (i != j) and (abs(i-j) == abs(genome[j]-genome[i])):
col = True
if col == True: collisions +=
#傳回沒有産生碰撞的個體數目。
return BOARD_SIZE-collisions
初始化個體，這裡種群的多樣性展現在一組位置清單的排序。 是以，初始化時對個體清單使用shuffle函數進行随機排序。
#對生成的個體進行随機排序
def queens_init(genome, **args):
genome.genomeList = range(, BOARD_SIZE)
shuffle(genome.genomeList)
3.5 Pyevolve主體部分
def run_main():
genome = G1DList.G1DList(BOARD_SIZE)
#genome執行個體，這裡使用的是1D清單項。
#參數設定，适應度最大值不超過格子大小，保留兩位小數。
genome.setParams(bestrawscore=BOARD_SIZE, rounddecimal=)
#初始化genome，這裡是傳回随機排序的個體清單。
genome.initializator.set(queens_init)
#變異算子：使用“交換”變異
genome.mutator.set(Mutators.G1DListMutatorSwap)
#交叉算子
genome.crossover.set(Crossovers.G1DListCrossoverCutCrossfill)
#求解器是計算目标函數傳回的滿足規則的個體數
genome.evaluator.set(queens_eval)
#簡單遺傳算法引擎
ga = GSimpleGA.GSimpleGA(genome)
#設定結束進行的标準：根據原函數值的收斂情況
ga.terminationCriteria.set(GSimpleGA.RawScoreCriteria)
#适應度最大值
ga.setMinimax(Consts.minimaxType["maximize"])
############################################設定遺傳參數
ga.setPopulationSize()
ga.setGenerations()
ga.setMutationRate()
ga.setCrossoverRate()
3.6 資料可視化分析
将每代個體資訊存入資料庫，以便後期資料分析：
#queens是資料庫中的ID
sqlite_adapter = DBAdapters.DBSQLite(identify="queens")
ga.setDBAdapter(sqlite_adapter)
當算法運作結束，所有個體資訊都會儲存到資料庫當中，這時我們可以使用Pyevolve自帶的畫圖子產品進行資料分析：
這裡需要說明的是，在程式運作完畢之後會在代碼目錄下生成一個Pyevolve資料庫檔案。使用pyevolve_graph函數可以對資料庫進行操作， pyevolve_graph和資料庫檔案必須在同一個目錄下。
這裡還需要對傳入參數進行說明：-i queens -1
-i是固定值，不需要改變。
queens是上面代碼中設定的ID号，因為同一目錄下的Pyevolve檔案生成的資料都會儲存在Pyevolve資料庫檔案中，是以用ID區分不同檔案産生的資料。
最後一個數字表示不同的圖形。 數字從-1 至 -9,每一個數字代表一種圖形。就主要的幾種圖進行說明。
- -1：畫出每一代個體未經線性變換的最大值，最小值和平均值。
- -2：畫出經過線性變換之後個體的最大值，最小值和平均值。
- -8：熱量圖，即反映了适應度的集中區域。
以傳入參數為 -i queens -1為例：
cd Code/Code_genetic
Python pyevole_graph.py -i queens -1
據圖可以看出，随着遺傳代數的增加，每一代中個體的最大适應度，最小适應度以及最高适應度都總體趨勢是不斷增加。即每一代個體（皇後的位置），滿足條件的比例越來越大，并最終全部滿足而收斂。
3.7 列印資訊
最後的一些列印操作：
#設定計劃過程中，種群資訊顯示頻率
#即每隔10代，列印出個體适應度，原值資訊
ga.evolve(freq_stats=10)
#擷取最終的最優個體資訊
best = ga.bestIndividual()
#列印相關資訊
print "\nBest individual score: %.2f\n" % (best.score,)
print best
為了更加直覺地顯示最終結果，可以直接将得到的best值列印到棋子格中。
for i in xrange(BOARD_SIZE):
print '+----+'+('----+')*(BOARD_SIZE-1)
for j in xrange(BOARD_SIZE):
if best[i] == 0:
line ='| Q |'+' |'*(BOARD_SIZE-1)
else:
line ='| |' +' |'*(best[i]-1)+' Q |' +(BOARD_SIZE-1-best[i])*' |'
print line
print '+----+'+('----+')*(BOARD_SIZE-1)
最終效果如實驗效果圖所示。
四，實驗總結
在了解遺傳算法流程的基礎上，使用pyevolve架構更加容易了解。通過将n皇後問題轉化為遺傳算法可以操作的個體參數，在n比較大時，遺傳算法可以更好地找到較優解。
五， 參考文獻：
- Pyevolve官方文檔