王振義
(1.太原理工大學(xué)計(jì)算機(jī)與軟件學(xué)院,山西太原030024;2.山西大同大學(xué)物理與電子科學(xué)學(xué)院,山西大同037009)
遺傳算法求解N皇后問題的優(yōu)化
王振義1,2
(1.太原理工大學(xué)計(jì)算機(jī)與軟件學(xué)院,山西太原030024;2.山西大同大學(xué)物理與電子科學(xué)學(xué)院,山西大同037009)
∶采用vector容器高效的染色體整數(shù)編碼和成熟的泛型算法,改良遺傳算法求解N皇后問題,說明此方法更通用、簡(jiǎn)潔和高效.
∶N皇后問題 適應(yīng)值 遺傳算法 STL
八皇后問題是著名的數(shù)學(xué)家Gauss于1850年提出的.要求橫、豎、斜方向上都不能有兩個(gè)及兩個(gè)以上皇后在同一條直線上,問題也可以推廣到N個(gè)皇后.求解這一問題的算法很多,過去一般用窮舉法、回溯法求解.由于其時(shí)間復(fù)雜度為O(N!),是一個(gè)NP難問題.對(duì)于皇后變多耗時(shí)激增的計(jì)算機(jī)求解問題,就需利用非常規(guī)的技術(shù)求解.解決的辦法通常是編寫快速的算法,或是采用多個(gè)CPU并行計(jì)算或分布式計(jì)算.本文使用STL中的容器和泛型算法對(duì)基本遺傳算法進(jìn)行改進(jìn),達(dá)到滿意的效果.
遺傳算法(Genetic Algorithms,簡(jiǎn)稱GA),是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型,基于生物學(xué)進(jìn)化原理的一種全局搜索算法.通過用計(jì)算機(jī)模擬生物進(jìn)化過程,使群體不斷優(yōu)化,并在進(jìn)化過程中逐漸接近最優(yōu)解.其特點(diǎn)是簡(jiǎn)單、通用、魯棒性強(qiáng)和適于并行處理.把遺傳算法用于求解NP完全問題,可為求解NP完全問題給出新的思路.
遺傳算法的框架是由Holland提出的,可描述為:
①隨機(jī)產(chǎn)生初始種群;
②利用適應(yīng)度函數(shù)對(duì)個(gè)體計(jì)算函數(shù)值;
③按一定的概率選擇對(duì)個(gè)體進(jìn)行選擇、交叉、變異等操作產(chǎn)生新種群;
④重復(fù)②、③兩步,直到找到最佳解或迭代次數(shù)達(dá)到指定的上限;
STL是C++標(biāo)準(zhǔn)庫的一部分,全稱叫做標(biāo)準(zhǔn)模板庫,它的作用就是提供一些泛型算法和容器.
使用STL主要有如下理由:
①效率高:算法通常比程序員產(chǎn)生的循環(huán)更高效.
②正確性:寫循環(huán)時(shí)比調(diào)用算法更容易產(chǎn)生錯(cuò)誤.
③可維護(hù)性:算法通常使代碼比相應(yīng)的顯式循環(huán)更干凈、更直觀.
在進(jìn)行遺傳算法求解N皇后問題的計(jì)算中,當(dāng)基因數(shù)量和總?cè)簲?shù)量較大時(shí),使用遺傳算法對(duì)數(shù)據(jù)的處理,需多次用到數(shù)組循環(huán),這是相當(dāng)耗時(shí)的.本文采用vector容器存放數(shù)據(jù),運(yùn)用STL泛型算法處理數(shù)據(jù),如accumulate求和,max_element求最大值,remove和copy配合著對(duì)vector數(shù)據(jù)重排等,為用遺傳算法求解N皇后問題的數(shù)據(jù)處理帶來極大的便捷、簡(jiǎn)潔和高效.
N皇后問題要求,每行,每列,主次對(duì)角線都只有一個(gè)棋子存在.這里采用整數(shù)編碼,每個(gè)染色體都是由N個(gè)基因的整數(shù)組成,取值范圍是1-N.編碼位置和數(shù)值代表皇后所處行和列的位置.這樣,保證了在每行,每列只有一個(gè)皇后,一個(gè)染色體代表著一種棋盤的布局.例設(shè)染色體用G=(G1,G2,…Gi… Gn)表示,Gi代表在第i行上的皇后放在第Gi列的位置.采用VC作為平臺(tái),在建立main程序后,建立基因組類和群體類.
成員 vector<int> vecBits;//表示一個(gè)染色體
dFitness;//染色體對(duì)應(yīng)的適應(yīng)度.成員函數(shù)有:
CreateGenome函數(shù)創(chuàng)建個(gè)體.首先生成一個(gè)按從小到大順序排列的基因組,再用random_shuffle函數(shù)使這個(gè)染色體中的基因隨機(jī)重排,得到新的個(gè)體.
UpdateFitnessScore計(jì)算適應(yīng)度.在主次對(duì)角線上的彼此有一個(gè)沖突數(shù)記為1,累加本染色體中所有的沖突后加1,再求倒數(shù)作為適應(yīng)度,顯然沖突越多,對(duì)應(yīng)的適應(yīng)度值越小,沒有任何沖突時(shí),值為1,表示找到了一個(gè)合適的解.
成員
vector<CGenome> vGenomes;//群體
vector<CGenome>::iterator vGit;//迭代器
vector<CGenome> vBabyGenomes;//下級(jí)群體
intm_iBestIndex;//最好個(gè)體的索引
intm_iWorstIndex;//最好個(gè)體的索引
CGenome m_CCurrentBestGenome;//目前最好的個(gè)體CGenomem_CBestGenome;//當(dāng)代最好的個(gè)體CGenomem_CWorstGenome;//當(dāng)代最糟的個(gè)體建立一些算法函數(shù)完成指定功能.
①初始化種群:(GenerateInitialPopulation)
完成每個(gè)種群的初始化,同時(shí)調(diào)用CGenome建立的UpdateFitnessScore對(duì)每個(gè)個(gè)體進(jìn)行計(jì)算.
②選擇算子(SelectionOperator)
按賭輪選擇,保證適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中.在計(jì)算總的適應(yīng)度時(shí)用到了 accumulate(vG.begin(),vG.end(),0.0,Add);其中 Add(const double Val,const CGenome&element){return Val+element.dFitness;}就是對(duì)類中成員適應(yīng)度(dFitness)的累加.
③交叉算子(CrossoverOperator)
當(dāng)隨機(jī)數(shù)小于交叉概率(這里取0.75)時(shí),進(jìn)行交叉運(yùn)算,由于新種群的個(gè)體是隨機(jī)產(chǎn)生的,選用相鄰(也可以隨機(jī)配對(duì))的個(gè)體作為父母本進(jìn)行交叉.不同于位編碼的交叉,為確保同行同列不沖突,新個(gè)體中的數(shù)字不能有重復(fù)的.先隨機(jī)生成單個(gè)交叉點(diǎn)的位置,子代個(gè)體的前半段直接拷入交叉點(diǎn)前父(母)的前半段,母(父)本中刪除個(gè)體前半段已有的數(shù)字作為個(gè)體的后半段.
④變異算子(MutationOperator)
為了避免出現(xiàn)早熟收斂,當(dāng)隨機(jī)數(shù)小于變異概率(這里取0.2)時(shí)隨機(jī)生成兩個(gè)基因位,交換兩個(gè)位置的基因,對(duì)個(gè)體進(jìn)行變異,這里用到了swap函數(shù).
⑤干預(yù)進(jìn)化(PerformEvolution)
運(yùn)用 max_element(vG.begin(),vG.end(),best);記錄當(dāng)前群體中最好(或最糟)的個(gè)體,以及對(duì)應(yīng)的索引編號(hào),其中best為自定義的判斷式,容器中的相鄰項(xiàng)比較,后的數(shù)大時(shí)為真進(jìn)行代換,最后得到適應(yīng)度最大的個(gè)體,最糟的結(jié)果是利用后面的數(shù)小時(shí)為真,也就是得到整個(gè)群體中適應(yīng)度最小的個(gè)體.用最優(yōu)的個(gè)體替換掉最糟的個(gè)體,保證最優(yōu)的個(gè)體直接進(jìn)入下一代,剔除最糟的個(gè)體保證的整個(gè)群體有更大的適應(yīng)度.
表1 和其它文獻(xiàn)用時(shí)對(duì)比(t/s)
測(cè)試條件:染色體長(zhǎng)度等于皇后數(shù),種群大小選200,交叉概率0.75,變異概率0.2,最大代數(shù)根據(jù)要求皇后的數(shù)量決定,一般取200即可,可以通過試解后在調(diào)整.
通過在VC++集成編輯環(huán)境下的運(yùn)行,本程序用時(shí)明顯小于回溯法用時(shí)[5],對(duì)皇后數(shù)量大于100的問題求解,明顯優(yōu)于基本遺傳算法.此方法稍加修改就可以解決其他問題,如旅行商和其它數(shù)值類求解問題.本文利用容器和調(diào)用算法的方法,對(duì)其他類似問題的算法的優(yōu)化有一定借鑒意義.
[1]李建華.智能組卷系統(tǒng)與遺傳算法[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版,2009,25(3):14-16.
[2]胡能發(fā).一種二元單親演化差基因變異算法[J].長(zhǎng)江大學(xué)學(xué)報(bào):自然科學(xué)版,2004,1(1):74-76.
[3]宋曉霞.遺傳算法中初始群體技術(shù)的改進(jìn)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(22):5485-5487.
[4]馬永,賈俊芳.遺傳算法研究綜述[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版,2007,23(3):11-13.
[5]劉娟,歐陽建權(quán),陳良軍.用混合遺傳算法求解N皇后問題[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2007,29(2):37-41.
[6]楊凱,羅文俊.基于BIT位運(yùn)算的N皇后問題解法[J].貴州師范大學(xué)學(xué)報(bào):自然科學(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-),男,山西大同人,副教授,研究方向:算法.
〔編輯 高?!?/p>