1、用遺傳算法解決N-皇后問(wèn)題劉振(南昌大學(xué)信息與工程學(xué)院計(jì)算機(jī)應(yīng)用江西南昌)摘要：本文首先介紹了N皇后問(wèn)題的和遺傳算法的基本知識(shí)和來(lái)源背景。結(jié)合一般的遺傳算法的實(shí)現(xiàn)過(guò)程和傳統(tǒng)的處理皇后問(wèn)題判斷攻擊的方法，給出了一種實(shí)數(shù)編碼方法。同時(shí)，實(shí)現(xiàn)了該算法，并通過(guò)和回溯法、構(gòu)造法的比較來(lái)說(shuō)明該算法的優(yōu)劣。關(guān)鍵詞：遺傳算法皇后問(wèn)題編碼SolvingtheproblemofN-QueenbygeneticalgorithmLIUZhen(CollegeofComputerandInformation,NanchangUniversity,JiangxiNanchang)Abstract:Theknowledg

2、eofthebasicandsourcesofbackgroundoftheN-Queenproblemandgeneticalgorithmsareintroducedfirstlyinthispaper.TakeuseofgeneralgeneticalgorithmandthetraditionalmethodofdealwithN-Queenproblem,givenareal-codedmethod.Atthesametime,thealgorithmisrealizaded,comparedwithmethodofbacktrackingandconstructionmethodt

3、oillustratethatthealgorithmisgoodorbad.Keywords:GeneticalgorithmN-QueenproblemCoding0引言N-皇后問(wèn)題是一個(gè)經(jīng)典的NP問(wèn)題。1850年著名的數(shù)學(xué)家高斯提出的八皇后是這一問(wèn)題的特例。N-皇后問(wèn)題的目標(biāo):是在N*N格的棋盤(pán)中擺放N個(gè)皇后，使它們互不攻擊，即任意的兩個(gè)皇后不能處在同一行、同一列或同一對(duì)角線上。由于這個(gè)問(wèn)題的求解需要大量的實(shí)臉和計(jì)算，用手工難以完成計(jì)算。因此，當(dāng)時(shí)高斯并沒(méi)有完全解決它。現(xiàn)在雖然可以采用遞歸程序來(lái)很方便地求出目標(biāo)解但由于N-皇后在N*N棋盤(pán)上分布的可能的布局?jǐn)?shù)目非常大有cn個(gè)。所以，用遞歸

4、求解的有算法的時(shí)間隨著問(wèn)題的n*n規(guī)模的增大而呈幾何指數(shù)增長(zhǎng)的缺點(diǎn)。但N-皇后問(wèn)題屬于全局并行搜索問(wèn)題，并且在搜索過(guò)程中，不斷向可能包含目標(biāo)解的方向調(diào)整搜索空間，而這正是遺傳算法的優(yōu)勢(shì)所在。遺傳算法是1975年美國(guó)J.Holland教授首先提出以來(lái)，它是基于達(dá)爾文的生物進(jìn)化理論中的“優(yōu)勝劣汰，適者生存”的進(jìn)化原則提出的。它是從一組隨機(jī)生成的種群開(kāi)始搜索，群體中的每一個(gè)個(gè)體被稱(chēng)為染色體，染色體的好壞用適應(yīng)度來(lái)衡量。根據(jù)適應(yīng)度的大小從上一代和子代中選擇一定量的個(gè)體作為新的一代，繼續(xù)進(jìn)化，經(jīng)過(guò)若干代進(jìn)化后算法收斂于最優(yōu)個(gè)體，它可能就是問(wèn)題的最優(yōu)解或次優(yōu)解。本文是一個(gè)遺傳算法的應(yīng)用實(shí)例，也有人做過(guò)類(lèi)似

5、的研究，他們的編碼方法采用二維二進(jìn)制編碼。這會(huì)導(dǎo)致搜索的空間很大，從而降低了搜索的效率。本文采用的是自然數(shù)串編碼機(jī)制，搜索的空間就要小很多。1. 遺傳算法概述遺傳算法是模擬生物進(jìn)化的計(jì)算模型，由于其簡(jiǎn)單通用、魯棒性強(qiáng)、適用于并行處理。因此，得到廣泛的應(yīng)用。因?yàn)樗亲匀贿z傳學(xué)和計(jì)算機(jī)科學(xué)相互結(jié)合滲透而形成的,所以這里就簡(jiǎn)單介紹一下有關(guān)遺傳算法的相關(guān)術(shù)語(yǔ)和一般遺傳算法的執(zhí)行步驟。1.1染色體：它代表問(wèn)題的一個(gè)可能解，通常使用位串或字符串表示，其中每一位代表一個(gè)基因，各個(gè)染色體中位于同一位置的基因稱(chēng)為等位基因。1.2 群體：一個(gè)群體是若干個(gè)體的集合，因?yàn)槊恳粋€(gè)個(gè)體代表一個(gè)解，所以群體稱(chēng)為問(wèn)題解的集合

6、。1.3 適應(yīng)度：它是用來(lái)表征個(gè)體對(duì)目標(biāo)要求的適應(yīng)程度。通常用一個(gè)函數(shù)值來(lái)表示適應(yīng)度。一般情況下，適應(yīng)度的值越高，個(gè)體對(duì)環(huán)境的適應(yīng)性越強(qiáng)。1.4 編碼：即采用恰當(dāng)?shù)姆绞絹?lái)構(gòu)造個(gè)體的基因型。一般采用二進(jìn)制編碼方案，有時(shí)也采用其他的編碼方法。1.5 選擇：根據(jù)個(gè)體的適應(yīng)度，在群體中選擇出作為雙親的個(gè)體。選擇的原則是適應(yīng)度大的個(gè)體優(yōu)先選擇。1.6 復(fù)制：按照一定的適應(yīng)度選擇到的作為雙親的個(gè)體，把他們的基因復(fù)制到后代中。1.7 交叉：交叉是在兩個(gè)父代染色體中隨機(jī)產(chǎn)生基因交叉點(diǎn)，通過(guò)互相交換基因來(lái)產(chǎn)生新的個(gè)體。1.8 變異：是對(duì)于一個(gè)個(gè)體，隨機(jī)選擇一個(gè)基因點(diǎn)來(lái)改變此處的基因，從而產(chǎn)生新的個(gè)體。新產(chǎn)生的個(gè)

7、體的適應(yīng)度可能比原來(lái)個(gè)體高也可能比原個(gè)體低。1.9 一般遺傳算法的步驟：1) 初始化種群；2) 根據(jù)所設(shè)置的求個(gè)體適應(yīng)度的函數(shù)求出種群中個(gè)體的適應(yīng)度；3) 設(shè)定個(gè)體選擇概率；4) 選擇個(gè)體遺傳操作，生成下一代種群；5) 選擇最佳個(gè)體，判斷是否滿足要求，如是則到6)，否則到2)；6) 打印出問(wèn)題的一個(gè)解，算法結(jié)束。2. 算法介紹及實(shí)現(xiàn)根據(jù)一般遺傳算法的思想和步驟，這里主要是讓兩個(gè)適應(yīng)度高的個(gè)體通過(guò)變異來(lái)產(chǎn)生適應(yīng)度更高的個(gè)體，同時(shí)又選擇其他的個(gè)體通過(guò)交叉來(lái)產(chǎn)生出新的個(gè)體。以下就是這個(gè)遺傳算法的主要框架，介紹了其實(shí)現(xiàn)過(guò)程。2.1 染色體編碼文獻(xiàn)23中采用的染色體編碼方式為兩維二進(jìn)制編碼，即對(duì)于N個(gè)皇

8、后問(wèn)題該編碼方式的染色體長(zhǎng)度為N*N，那么整個(gè)算法的搜索空間為2n*n，采用這種編碼方式不能很好保證行列之間的約束，導(dǎo)致算法的收斂效率降低。而本文染色體采用實(shí)數(shù)編碼機(jī)制，它的優(yōu)點(diǎn)是5：適合于表示大范圍的數(shù)，便于較大空間的搜索，可以提高遺傳算法的精確度，便于和傳統(tǒng)的算法相結(jié)合，無(wú)需解碼即通過(guò)基因就可以直接的知道問(wèn)題的解。這是采用了文獻(xiàn)1的編碼方法。對(duì)于N皇后問(wèn)題其染色體長(zhǎng)度為N(N為皇后數(shù))，染色體中每一個(gè)基因位代表一個(gè)皇后所在行的位置，而基因值則代表一個(gè)皇后在列的位置，可以看出，采用本文的染色體編碼方式的搜索空間為Nn，要遠(yuǎn)遠(yuǎn)小于采用兩維二進(jìn)制編碼的搜索空間，且在編碼時(shí)就避免了皇后間在行列之間

9、的沖突，因此能極大提高算法的搜索效率，加快算法的收斂速度。2.2 初始化種群初始化種群的任務(wù)主要有兩個(gè)，一個(gè)是設(shè)定種群的大小，另一個(gè)就是種群的初始化。種群的大小的選擇對(duì)對(duì)算法的收斂性產(chǎn)生很大的影響。種群較小收斂速度就較快，可是搜索面就窄了，容易產(chǎn)生局部收斂。而種群較大時(shí)，雖然搜索面變寬了，但同時(shí)收斂的速度也變慢了。有人在處珈皇后問(wèn)題時(shí)直接讓種群個(gè)數(shù)等于皇后個(gè)數(shù)，這樣在皇后個(gè)數(shù)不多的時(shí)候，種群規(guī)模較小；但在皇后個(gè)數(shù)較多的時(shí)候，種群的規(guī)模又較大。本文是采用讓種群個(gè)數(shù)等于：a+n/b(其中a、b都為正整數(shù))。這樣可以避免上面的問(wèn)題：第一、當(dāng)皇后個(gè)數(shù)較少時(shí)可以通過(guò)調(diào)整a的值保證種群規(guī)模不太小；第二、當(dāng)

10、皇后個(gè)數(shù)較多時(shí)通過(guò)除b又保證了種群規(guī)模不太大。2.3 適應(yīng)度函數(shù)的設(shè)計(jì)適應(yīng)度函數(shù)在遺傳算法中有著至關(guān)重要的作用，它關(guān)系到整個(gè)算法能否求解的問(wèn)題。本文中個(gè)體的適應(yīng)度是用每一個(gè)基因的適應(yīng)度之和來(lái)表示的。每一個(gè)基因的適應(yīng)度是通過(guò)它和其它位置的基因的相容程度之和來(lái)計(jì)算的，基因之間的相容程度和傳統(tǒng)的利用回溯法時(shí)表示皇后不相互攻擊的方法是一樣的，具體分析如下：我們用i,j表示行，用queeni,queenj表示第i,j上皇后所處的位置。這樣，我們就有了下面兩個(gè)方面的考慮。第一、當(dāng)queeni=queenj(ij)時(shí)，兩個(gè)皇后必然互相攻擊，因此他們的相容度為0反之為1。第二、我們考慮在對(duì)角線的情況，可以知道

11、在|i-j|=|queeni-queenj|的情況下皇后是在對(duì)角線上的，它們的相容度為0，反之為1。這樣算出來(lái)，如果個(gè)體的適應(yīng)度函數(shù)的值越高它就越接近或滿足可行解。如果個(gè)體的適應(yīng)度達(dá)到了N時(shí)就不存在互相攻擊的皇后了，也就是說(shuō)滿足我們要求的解已經(jīng)找到。2.4 遺傳算子本文中簡(jiǎn)化了遺傳算法中的變異算子，只對(duì)種群中的最優(yōu)和次優(yōu)的個(gè)體進(jìn)行變異。對(duì)于其余的個(gè)體則是進(jìn)行交叉運(yùn)算的，首先通過(guò)輪盤(pán)賭局算法選擇出待交叉的兩個(gè)個(gè)體作為父代，通過(guò)一定的交叉算子來(lái)生成新的子代個(gè)體。2.5 終止策略本文采取的終止策略是：當(dāng)種群中的最優(yōu)個(gè)體的適應(yīng)度達(dá)到所設(shè)定的值時(shí)，即最優(yōu)個(gè)體的適應(yīng)度等于N時(shí)程序結(jié)束，求得一個(gè)滿足條件的解

12、。2.6 算法的執(zhí)行步驟終上所述，用遺傳算法求解N-皇后問(wèn)題的算法基本流程如下：1) 基于隨機(jī)產(chǎn)生基因位的種群的初始化，同時(shí)通過(guò)所設(shè)定的計(jì)算適應(yīng)度的函數(shù)求得個(gè)體的適應(yīng)度；2) 對(duì)當(dāng)前種群中的個(gè)體按照適應(yīng)度從大到小進(jìn)行排序；3) 從排序后的種群中挑選最優(yōu)和次優(yōu)個(gè)體進(jìn)行變異；4) 變異后的最優(yōu)的個(gè)體是否滿足終止條件，是則到6)，否則繼續(xù)；5) 通過(guò)交叉產(chǎn)生新一代種群并計(jì)算每一個(gè)個(gè)體的適應(yīng)度，轉(zhuǎn)至2)；6) 輸出最優(yōu)個(gè)體，算法結(jié)束。3. 實(shí)驗(yàn)結(jié)果我們選擇皇后個(gè)數(shù)分別為8，10，30，50，100，200，500時(shí)作為測(cè)試用例。表1是該遺傳算法和回溯法、構(gòu)造法求解N皇后所需時(shí)間的對(duì)比表。由于遺傳算法求

13、解問(wèn)題的隨機(jī)性，因此在計(jì)算時(shí)間時(shí)取十次運(yùn)行時(shí)間的平均值，由于在皇后個(gè)數(shù)多于50時(shí)所需時(shí)間較長(zhǎng)，這里50個(gè)皇后運(yùn)行5次，100個(gè)皇后的時(shí)候運(yùn)行一次，當(dāng)皇后個(gè)數(shù)是200和500的時(shí)候并沒(méi)有給出結(jié)果;表2是本文算法求解不同皇后數(shù)所需的進(jìn)化代數(shù)的平均代數(shù)、最多代數(shù)及最少代數(shù)表。表1和回溯法及構(gòu)造法所用時(shí)間比較表(t/s)皇后數(shù)810203050100200500本文方法0.00780.02180.48110.70465.125821.531回溯法0.0000.0160.0310.062構(gòu)造法1.7652.0002.4063.0623.2503.6713.9374.000表2遺傳算法所需進(jìn)化代數(shù)表皇后數(shù)

14、810203050100200500最少代數(shù)112420335437最多代數(shù)1334885693616平均代數(shù)513216188515從表1可以看出，用遺傳算法求解N皇后問(wèn)題的時(shí)間在皇后個(gè)數(shù)不多的情況下，并不比回溯法使用的時(shí)間少，但當(dāng)用回溯法求解大約40個(gè)以上的皇后問(wèn)題時(shí)因?qū)Y源需求很大，導(dǎo)致不能運(yùn)行，而未能給出求解時(shí)間。由于遺傳算法是一個(gè)種基于種群的搜索算法，因此它求解問(wèn)題的快慢與其初始種群有著很大的關(guān)系.從表2可以看出，對(duì)于同一個(gè)問(wèn)題，由于初始種群不同，相應(yīng)求解問(wèn)題所需的代數(shù)相差幾倍甚至幾十倍。因此可以考慮用啟發(fā)式算法使其得到一個(gè)較好的初始化種群，以加快收斂速度。4. 總結(jié)N皇后問(wèn)題是一個(gè)經(jīng)典的NP問(wèn)題，研究如何求解N皇后問(wèn)題有著非常重大的意義。本文采用遺傳算法求解N皇后問(wèn)題，提出用N皇后的約束條件作為遺傳算法的適應(yīng)度函數(shù)，設(shè)計(jì)了用實(shí)數(shù)編碼的方法來(lái)表示染色體、初始化種群方法、遺傳算子使它們符合問(wèn)題求解的需要。實(shí)驗(yàn)結(jié)果表明了該算法的有效性。但相對(duì)于回溯法用遺傳算法求解N皇后問(wèn)題只能求得一個(gè)有效解，而不能求出所有的有效解。而和構(gòu)造方法相比在皇后個(gè)數(shù)較少的時(shí)候，通常比構(gòu)造算法運(yùn)行時(shí)間還少，可是當(dāng)皇后的數(shù)目較大的時(shí)候沒(méi)有構(gòu)造法來(lái)的快。構(gòu)造法可以說(shuō)是最好的求解皇后問(wèn)題的算法，特別是皇后個(gè)數(shù)較多的時(shí)候，它唯一的缺點(diǎn)就是:求出的皇后的擺放比較