遺傳算法求解N皇后問題的優(yōu)化

王振義

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

遺傳算法求解N皇后問題的優(yōu)化

王振義1,2

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

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

∶N皇后問題 適應(yīng)值 遺傳算法 STL

1 N皇后問題描述

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

2 遺傳算法

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

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

①隨機(jī)產(chǎn)生初始種群;

②利用適應(yīng)度函數(shù)對個體計算函數(shù)值;

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

④重復(fù)②、③兩步，直到找到最佳解或迭代次數(shù)達(dá)到指定的上限;

3 STL(Standard Template Library)

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

使用STL主要有如下理由:

①效率高:算法通常比程序員產(chǎn)生的循環(huán)更高效.

②正確性:寫循環(huán)時比調(diào)用算法更容易產(chǎn)生錯誤.

③可維護(hù)性:算法通常使代碼比相應(yīng)的顯式循環(huán)更干凈、更直觀.

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

4 編程實(shí)現(xiàn)

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

4.1 基因組類∶CGenome

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

dFitness;//染色體對應(yīng)的適應(yīng)度.成員函數(shù)有:

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

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

4.2 種群類∶CPopulation

成員

vector＜CGenome＞ vGenomes;//群體

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

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

intm_iBestIndex;//最好個體的索引

intm_iWorstIndex;//最好個體的索引

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

①初始化種群:(GenerateInitialPopulation)

完成每個種群的初始化，同時調(diào)用CGenome建立的UpdateFitnessScore對每個個體進(jìn)行計算.

②選擇算子(SelectionOperator)

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

③交叉算子(CrossoverOperator)

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

④變異算子(MutationOperator)

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

⑤干預(yù)進(jìn)化(PerformEvolution)

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

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

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

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

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

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

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

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

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

[6]楊凱，羅文俊.基于BIT位運(yùn)算的N皇后問題解法[J].貴州師范大學(xué)學(xué)報:自然科學(xué)版，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-)，男，山西大同人，副教授，研究方向:算法.

〔編輯 高海〕