遺傳算法求解N皇后問題的優化

王振義

(1.太原理工大學計算機與軟件學院，山西太原030024;2.山西大同大學物理與電子科學學院，山西大同037009)

遺傳算法求解N皇后問題的優化

王振義1,2

(1.太原理工大學計算機與軟件學院，山西太原030024;2.山西大同大學物理與電子科學學院，山西大同037009)

∶采用vector容器高效的染色體整數編碼和成熟的泛型算法，改良遺傳算法求解N皇后問題，說明此方法更通用、簡潔和高效.

∶N皇后問題 適應值 遺傳算法 STL

1 N皇后問題描述

八皇后問題是著名的數學家Gauss于1850年提出的.要求橫、豎、斜方向上都不能有兩個及兩個以上皇后在同一條直線上，問題也可以推廣到N個皇后.求解這一問題的算法很多，過去一般用窮舉法、回溯法求解.由于其時間復雜度為O(N!)，是一個NP難問題.對于皇后變多耗時激增的計算機求解問題，就需利用非常規的技術求解.解決的辦法通常是編寫快速的算法，或是采用多個CPU并行計算或分布式計算.本文使用STL中的容器和泛型算法對基本遺傳算法進行改進，達到滿意的效果.

2 遺傳算法

遺傳算法(Genetic Algorithms，簡稱GA)，是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，基于生物學進化原理的一種全局搜索算法.通過用計算機模擬生物進化過程，使群體不斷優化，并在進化過程中逐漸接近最優解.其特點是簡單、通用、魯棒性強和適于并行處理.把遺傳算法用于求解NP完全問題，可為求解NP完全問題給出新的思路.

遺傳算法的框架是由Holland提出的，可描述為:

①隨機產生初始種群;

②利用適應度函數對個體計算函數值;

③按一定的概率選擇對個體進行選擇、交叉、變異等操作產生新種群;

④重復②、③兩步，直到找到最佳解或迭代次數達到指定的上限;

3 STL(Standard Template Library)

STL是C++標準庫的一部分，全稱叫做標準模板庫，它的作用就是提供一些泛型算法和容器.

使用STL主要有如下理由:

①效率高:算法通常比程序員產生的循環更高效.

②正確性:寫循環時比調用算法更容易產生錯誤.

③可維護性:算法通常使代碼比相應的顯式循環更干凈、更直觀.

在進行遺傳算法求解N皇后問題的計算中，當基因數量和總群數量較大時，使用遺傳算法對數據的處理，需多次用到數組循環，這是相當耗時的.本文采用vector容器存放數據，運用STL泛型算法處理數據，如accumulate求和，max_element求最大值，remove和copy配合著對vector數據重排等，為用遺傳算法求解N皇后問題的數據處理帶來極大的便捷、簡潔和高效.

4 編程實現

N皇后問題要求，每行，每列，主次對角線都只有一個棋子存在.這里采用整數編碼，每個染色體都是由N個基因的整數組成，取值范圍是1-N.編碼位置和數值代表皇后所處行和列的位置.這樣，保證了在每行，每列只有一個皇后，一個染色體代表著一種棋盤的布局.例設染色體用G=(G1，G2，…Gi… Gn)表示，Gi代表在第i行上的皇后放在第Gi列的位置.采用VC作為平臺，在建立main程序后，建立基因組類和群體類.

4.1 基因組類∶CGenome

成員 vector＜int＞ vecBits;//表示一個染色體

dFitness;//染色體對應的適應度.成員函數有:

CreateGenome函數創建個體.首先生成一個按從小到大順序排列的基因組，再用random_shuffle函數使這個染色體中的基因隨機重排，得到新的個體.

UpdateFitnessScore計算適應度.在主次對角線上的彼此有一個沖突數記為1，累加本染色體中所有的沖突后加1，再求倒數作為適應度，顯然沖突越多，對應的適應度值越小，沒有任何沖突時，值為1，表示找到了一個合適的解.

4.2 種群類∶CPopulation

成員

vector＜CGenome＞ vGenomes;//群體

vector＜CGenome＞::iterator vGit;//迭代器

vector＜CGenome＞ vBabyGenomes;//下級群體

intm_iBestIndex;//最好個體的索引

intm_iWorstIndex;//最好個體的索引

CGenome m_CCurrentBestGenome;//目前最好的個體CGenomem_CBestGenome;//當代最好的個體CGenomem_CWorstGenome;//當代最糟的個體建立一些算法函數完成指定功能.

①初始化種群:(GenerateInitialPopulation)

完成每個種群的初始化，同時調用CGenome建立的UpdateFitnessScore對每個個體進行計算.

②選擇算子(SelectionOperator)

按賭輪選擇，保證適應度較高的個體將有更多的機會遺傳到下一代群體中.在計算總的適應度時用到了 accumulate(vG.begin()，vG.end()，0.0，Add);其中 Add(const double Val，const CGenome&element){return Val＋element.dFitness;}就是對類中成員適應度(dFitness)的累加.

③交叉算子(CrossoverOperator)

當隨機數小于交叉概率(這里取0.75)時，進行交叉運算，由于新種群的個體是隨機產生的，選用相鄰(也可以隨機配對)的個體作為父母本進行交叉.不同于位編碼的交叉，為確保同行同列不沖突，新個體中的數字不能有重復的.先隨機生成單個交叉點的位置，子代個體的前半段直接拷入交叉點前父(母)的前半段，母(父)本中刪除個體前半段已有的數字作為個體的后半段.

④變異算子(MutationOperator)

為了避免出現早熟收斂，當隨機數小于變異概率(這里取0.2)時隨機生成兩個基因位，交換兩個位置的基因，對個體進行變異，這里用到了swap函數.

⑤干預進化(PerformEvolution)

運用 max_element(vG.begin()，vG.end()，best);記錄當前群體中最好(或最糟)的個體，以及對應的索引編號，其中best為自定義的判斷式，容器中的相鄰項比較，后的數大時為真進行代換，最后得到適應度最大的個體，最糟的結果是利用后面的數小時為真，也就是得到整個群體中適應度最小的個體.用最優的個體替換掉最糟的個體，保證最優的個體直接進入下一代，剔除最糟的個體保證的整個群體有更大的適應度.

表1 和其它文獻用時對比(t/s)

測試條件:染色體長度等于皇后數，種群大小選200，交叉概率0.75，變異概率0.2，最大代數根據要求皇后的數量決定，一般取200即可，可以通過試解后在調整.

通過在VC＋＋集成編輯環境下的運行，本程序用時明顯小于回溯法用時[5]，對皇后數量大于100的問題求解，明顯優于基本遺傳算法.此方法稍加修改就可以解決其他問題，如旅行商和其它數值類求解問題.本文利用容器和調用算法的方法，對其他類似問題的算法的優化有一定借鑒意義.

[1]李建華.智能組卷系統與遺傳算法[J].山西大同大學學報：自然科學版，2009，25(3):14-16.

[2]胡能發.一種二元單親演化差基因變異算法[J].長江大學學報:自然科學版，2004，1(1):74-76.

[3]宋曉霞.遺傳算法中初始群體技術的改進與實現[J].計算機工程與設計，2007，28(22):5485-5487.

[4]馬永，賈俊芳.遺傳算法研究綜述[J].山西大同大學學報:自然科學版，2007，23(3):11-13.

[5]劉娟，歐陽建權，陳良軍.用混合遺傳算法求解N皇后問題[J].湘潭大學自然科學學報，2007，29(2):37-41.

[6]楊凱，羅文俊.基于BIT位運算的N皇后問題解法[J].貴州師范大學學報:自然科學版，2009，27(2):96-98.

Genetic A lgorithm Optim ization of N Queens Problem

WANG Zhen－yi1,2
(1.College of Computer and Software，Taiyuan University of Technology，Taiyuan S hanxi，030024;2.School of Physics and Electronics Science，ShanxiDatong University，Datong Shanxi，037009)

This literary grace is with high-efficient chromosome integer code of vector container and ripe suffused withing type algorithm，can improve the algorithm algorithm and solve N queen's question，which prove s thismethod is common，more succinct and high-efficient.

N Queen;f itness;Genetic Algorithm;STL

∶TP18

∶A

∶1674－0874（2010）02－0013－02

∶2010-01-08

∶王振義(1955-)，男，山西大同人，副教授，研究方向:算法.

〔編輯 高海〕