人工智能論文-遺傳算法實(shí)現(xiàn)八皇后問題

南京理工大學(xué)人工智能大論文

題目：遺傳算法實(shí)現(xiàn)八皇后問題 姓名：xxxx學(xué)號：xxxxxxxxxxxxxx專業(yè)：xxxxxxxxxx院系：xxxxxxxxxxxxxxxx老師：xxxxxx日期：2015年12月20日

目錄摘要 3一、實(shí)驗(yàn)背景 41.1N皇后問題描述 41.2遺傳算法 4二、實(shí)驗(yàn)?zāi)康?5三、實(shí)驗(yàn)內(nèi)容 5四、實(shí)驗(yàn)步驟 54.1編碼方案 54.2初始化種群 64.3適應(yīng)度的計(jì)算 74.4遺傳算子 84.4.1選擇算子 84.4.2交叉方法 84.4.3變異方法 84.5局部搜索 104.6終止策略 104.7實(shí)現(xiàn)描述 10五、實(shí)驗(yàn)結(jié)果和分析 11六、總結(jié)與思考 12摘要眾所周知的八皇后問題是一個(gè)非常古老的問題，具體描述如下：在8*8的國際象棋棋盤上放置了八個(gè)皇后，要求沒有一個(gè)皇后能吃掉另一個(gè)皇后，即任意兩個(gè)皇后都不處于棋盤的同一行、同一列或同一對角線上。本實(shí)驗(yàn)要求設(shè)計(jì)并實(shí)現(xiàn)解決八皇后問題的遺傳算法。能夠給定任意一個(gè)初始狀態(tài)，使用遺傳算法搜索最優(yōu)解，程序能顯示優(yōu)化的計(jì)算過程。獨(dú)立運(yùn)行20次以上，統(tǒng)計(jì)遺傳算法的尋優(yōu)指標(biāo)（包括是否找到最優(yōu)解、平均迭代次數(shù)等）。本次設(shè)計(jì)旨在學(xué)習(xí)各種算法，訓(xùn)練對基礎(chǔ)知識和基本方法的綜合運(yùn)用及變通能力，增強(qiáng)對算法的理解能力，提高軟件設(shè)計(jì)能力，在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。通過本實(shí)驗(yàn)的設(shè)計(jì)與編程實(shí)現(xiàn)讓學(xué)生掌握基于狀態(tài)空間知識表示的局部搜索策略，對遺傳算法中的編碼方法以及選擇、復(fù)制、交叉、變異等基本算子有深入的理解，熟練運(yùn)用C++，編寫一個(gè)遺傳算法解決八皇后問題的應(yīng)用程序。關(guān)鍵詞：八皇后；遺傳算法；C++

一、實(shí)驗(yàn)背景1.1N皇后問題描述 N皇后問題描述如下：在格棋盤上放置彼此不受攻擊的N個(gè)皇后。按國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。N皇后問題等價(jià)于在以下三個(gè)約束條件：任何2個(gè)皇后不放在同一行；任何2個(gè)皇后不放在同一列；任何2個(gè)皇后不放在同斜線。 我們把的棋盤看作二維方陣，其行號從上到下列號從左到右依次編號為0，1，…，7。設(shè)任意兩個(gè)皇后，皇后1和皇后2的坐標(biāo)分別是（i，j）和（k，l），則如果這兩個(gè)皇后在從棋盤左上角到右下角的主對角線及其平行線（斜率為-1的線）上，有；如果這兩個(gè)皇后在斜率為＋1的每一斜線上，有；以上兩個(gè)方程分別等價(jià)于和因此任兩皇后的在同一斜線上的充要條件是。滿足兩個(gè)皇后不在同一斜線上的條件表示為： 兩皇后不在同一行用式表示為： 兩皇后不在同一列用式表示為： 1.2遺傳算法遺傳算法（GeneticAlgorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。遺傳算法是從代表問題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度（fitness）大小選擇（selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（geneticoperators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。二、實(shí)驗(yàn)?zāi)康腘皇后問題是經(jīng)典的益智游戲，通過本實(shí)驗(yàn)的設(shè)計(jì)與編程實(shí)現(xiàn)讓學(xué)生掌握基于狀態(tài)空間知識表示的局部搜索策略，對遺傳算法中的編碼方法以及選擇、復(fù)制、交叉、變異等基本算子有深入的理解。本次設(shè)計(jì)旨在學(xué)習(xí)各種算法，訓(xùn)練對基礎(chǔ)知識和基本方法的綜合運(yùn)用及變通能力，增強(qiáng)對算法的理解能力，提高軟件設(shè)計(jì)能力，在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。熟練運(yùn)用C++語言，獨(dú)立編程，實(shí)現(xiàn)一個(gè)遺傳算法解決八皇后問題的應(yīng)用程序。三、實(shí)驗(yàn)內(nèi)容本實(shí)驗(yàn)要求設(shè)計(jì)并實(shí)現(xiàn)解決八皇后問題的遺傳算法。能夠給定任意一個(gè)初始狀態(tài)，使用遺傳算法搜索最優(yōu)解，程序能顯示優(yōu)化的計(jì)算過程。獨(dú)立運(yùn)行20次以上，統(tǒng)計(jì)遺傳算法的尋優(yōu)指標(biāo)（包括是否找到最優(yōu)解、平均迭代次數(shù)等）。因?yàn)槲业膶W(xué)號末尾為0，按照老師要求，則應(yīng)該實(shí)現(xiàn)，即八皇后問題。四、實(shí)驗(yàn)步驟現(xiàn)在我們把任意n個(gè)皇后的任意一種放置辦法當(dāng)作一個(gè)個(gè)體（染色體），把其中的任意一個(gè)皇后當(dāng)作一個(gè)基因，用遺傳算法來解決該問題。4.1編碼方案對于此問題有三種編碼方案：排列編碼、二進(jìn)制編碼、矩陣編碼，在這里，采用第一重編碼方案，即排列編碼，具體描述如下：用一維n元數(shù)組來表示一個(gè)個(gè)體，其中，表示皇后放在棋盤的第行第列，即第行第列放置一個(gè)皇后。例如，表示棋盤的第0行第0列放一個(gè)皇后。數(shù)組第i個(gè)元素表示第i行的放置情況，可以看作一個(gè)基因。這種編碼可以自然的解決了某一行只能放一個(gè)皇后的約束，如果數(shù)組的每一個(gè)元素都不重復(fù)，可以看成0—n-1的一種排列，就自然保證每一列只能放一個(gè)皇后。因此在交叉變異和產(chǎn)生個(gè)體時(shí)必須注意的唯一性。4.2初始化種群初始化種群的主要工作為：確定種群的大小及產(chǎn)生初始種群.種群的大小能夠?qū)z傳算法的收斂性產(chǎn)生很大的影響，種群較小算法收斂速度較快，但它的搜索面不夠廣，容易導(dǎo)致局部收斂；而種群較大算法收斂全局最優(yōu)的概率也大，但是算法的收斂速度較慢。因此根據(jù)N皇后問題的特點(diǎn)，本文將種群大小設(shè)為N(皇后數(shù))。初始化種群的方法為：首先為每個(gè)體的染色體的基因位從1到N，然后隨機(jī)交換兩個(gè)基因位的值，對每個(gè)個(gè)體共交換N/2次，對種群中所有個(gè)體做上述操作。雙親遺傳時(shí)候的初始化種群實(shí)現(xiàn)如下：voidCreateMultiStartPopulation(){ intloop,i,j; inttmp[MAX_QUEENS]; for(loop=0;loop<m_size;loop++) { for(i=0;i<n;i++) tmp[i]=i; for(i=0;i<n;i++) { j=rand()%(n-i); m_population[loop].queen[i]=tmp[j]; tmp[j]=tmp[n-i-1]; } UpdateFitnessScore(&m_population[loop]); }}4.3適應(yīng)度的計(jì)算設(shè)表示皇后i和皇后j之間的相互攻擊，即：皇后i和j的攻擊度： 第i個(gè)皇后的攻擊度表示皇后i在除自身外其余n-1個(gè)皇后中與皇后i相沖突的數(shù)目，即有幾個(gè)皇后與皇后i相攻擊。如果皇后i和所有皇后都沖突則攻擊度為n-1，與所有的皇后都不沖突攻擊度為0。因此，得到。同理，皇后i的非攻擊度表示和皇后i沒有沖突的皇后數(shù)目，設(shè)表示i的非攻擊度，則。我們根據(jù)非攻擊度計(jì)算：用表示基因i的適應(yīng)度，即第i個(gè)皇后的非攻擊度，則。如果某一個(gè)皇后i和所有其余的n-1個(gè)皇后都互不攻擊，則。個(gè)體的適應(yīng)度是指所有皇后的非攻擊度之和，適應(yīng)度函數(shù)可表示如下：。對于一個(gè)合法的放置方案每一個(gè)基因的適應(yīng)度都是n-1，此時(shí)染色體的適應(yīng)度是。//更新p的適應(yīng)度voidUpdateFitnessScore(Population*p){ inti,j; p->unitFitness=0; for(i=0;i<n;i++) { p->eachFitness[i]=0; for(j=0;j<n;j++) p->eachFitness[i]+=Aggressive(p,i,j); p->unitFitness+=p->eachFitness[i];//個(gè)體的適應(yīng)度為所有的基因的適應(yīng)度的總和 }}4.4遺傳算子4.4.1選擇算子 目前常用的選擇算子有二種：輪盤賭選擇算子和二進(jìn)制錦標(biāo)賽選擇算子。輪盤賭選擇算子的缺點(diǎn)在于容易產(chǎn)生出超級個(gè)體，易導(dǎo)致算法局部收斂。但為了實(shí)現(xiàn)簡單，我選擇輪盤賭選擇算子，即被選到的概率與適應(yīng)度呈正比（越是優(yōu)越的個(gè)體基因越容易被保留下來），具體試下如下：intRouletteWheelSelection(){ intselection=0; inti; doubleslice=(double)rand()/RAND_MAX; doubleaddFitness=0; for(i=0;i<m_size;i++) { addFitness+=(double)m_population[i].unitFitness/m_totFitness; if(addFitness>slice) { selection=i; break; } } returnselection;}4.4.2交叉方法 交叉方法可用的交叉方法有以下幾種。設(shè)p1，p2是要交叉的兩個(gè)父染色體，c1，c2是子代，是交叉的結(jié)果，n是編碼長度。單點(diǎn)交叉：先隨機(jī)生成交叉位置，把p1[0:m]與p2[0:m]部分互換分別得到c1，c2。4.4.3變異方法采用隨機(jī)變異方法。隨機(jī)生成變異數(shù)目m，隨機(jī)選擇m個(gè)皇后把它去掉，然后再隨機(jī)選擇m個(gè)位置放上皇后。單親遺傳：通過隨機(jī)交換適應(yīng)度最低的基因與其他基因的位置，產(chǎn)生新的子代。具體性實(shí)現(xiàn)如下：//單親遺傳父代變異函數(shù)voidSimpleMutate(){ inti,j,swap; intworst; Populationbaby; worst=0; for(i=0;i<n;i++) if(s_population.eachFitness[i]<s_population.eachFitness[worst]) worst=i; do{ j=rand()%n; }while(worst==j); baby=s_population; swap=baby.queen[worst]; baby.queen[worst]=baby.queen[j]; baby.queen[j]=swap; UpdateFitnessScore(&baby); //如果子代的適應(yīng)度更高的話，則子代保存下來 //當(dāng)概率小于某臨界值的時(shí)候子代不管是否更優(yōu)都保留 if(baby.unitFitness>s_population.unitFitness ||(double)rand()/RAND_MAX<Critical) s_population=baby;}雙親遺傳中的變異算子，對種群中的最優(yōu)兩個(gè)個(gè)體保留，并局部變異看是否可以達(dá)到結(jié)果，具體代碼如下：//單親遺傳父代變異函數(shù)voidMultiMutate(Population*p){ inti,j,swap; intworst; Populationbaby; worst=0; for(i=0;i<n;i++) if(p->eachFitness[i]<p->eachFitness[worst]) worst=i; baby=*p; for(i=0;i<n/4;i++) { j=rand()%n; swap=baby.queen[worst]; baby.queen[worst]=baby.queen[j]; baby.queen[j]=swap; UpdateFitnessScore(&baby); if(baby.unitFitness>p->unitFitness||(double)rand()/RAND_MAX<M_Critical) { *p=baby; break; } }}4.5局部搜索在實(shí)驗(yàn)中，發(fā)現(xiàn)遺傳算法在求解N皇后問題時(shí)，前期算法收斂非?？?，而到了算法運(yùn)行的后期算法收斂就比較慢，特別是當(dāng)適應(yīng)度為1時(shí).就是因?yàn)檫z傳算法的全局搜索能力較強(qiáng)，而局部搜索卻較弱。局部搜索算法的基本思想為：依次交換染色體的基因位，當(dāng)發(fā)現(xiàn)得到的新個(gè)體的適應(yīng)值小于交換前的個(gè)體的適應(yīng)值時(shí)，停止局部搜索.該局部搜索算法實(shí)際上改良了當(dāng)前代的最優(yōu)個(gè)體的染色體。由于局部搜索的時(shí)間耗費(fèi)較多，為了提高算法的效率，我們只對當(dāng)前種群中的最好的個(gè)體的進(jìn)行局部搜索操作.4.6終止策略本文采用的終止策略為：當(dāng)群體中的最優(yōu)個(gè)體的適應(yīng)值為0時(shí)，即表示算法搜索到了一個(gè)有效解。4.7實(shí)現(xiàn)描述A、雙親遺傳算法。產(chǎn)生初始種群。從當(dāng)前種群中選擇兩個(gè)個(gè)體。把選中的兩個(gè)父個(gè)體雜交生成中間個(gè)體。重復(fù)2和3的（選擇和雜交）操作直至中間個(gè)體生成完畢。對雜交后的中間個(gè)體根據(jù)變異概率進(jìn)行變異，生成新種群。檢驗(yàn)停止準(zhǔn)則，如果有解則停止，否則轉(zhuǎn)到2重復(fù)執(zhí)行。B、單親遺傳算法。產(chǎn)生初始種群。對當(dāng)前種群根據(jù)變異概率進(jìn)行變異，生成新種群。檢驗(yàn)停止準(zhǔn)則，如果有解則停止，否則轉(zhuǎn)到2重復(fù)執(zhí)行。五、實(shí)驗(yàn)結(jié)果和分析選擇8個(gè)皇后作為測試用例。實(shí)驗(yàn)使用內(nèi)存為512M的PC機(jī)進(jìn)行測試，操作系統(tǒng)為WINDOWS7，開發(fā)軟件為VC++6.0，開發(fā)語言為C++。程序經(jīng)過執(zhí)行后，輸入8，則得到一個(gè)優(yōu)化解，如下圖： 由結(jié)果可得：程序的開始時(shí)間與結(jié)束時(shí)間，因而得出運(yùn)算所用時(shí)間，這里運(yùn)算時(shí)間非常小，因而為0秒。還可以看到八皇后的一個(gè)優(yōu)化解，與本次迭代的次數(shù)。 繼續(xù)輸入8，又可以得到八皇后的一個(gè)解與相應(yīng)的迭代的次數(shù)，連續(xù)輸入20次，則得到的迭代次數(shù)為：91,1317，165,233,359,30,11,40,216,127,195,639,13,200,90,177,219,274,1072,2691。算得平均迭代次數(shù)為：408次。六、總結(jié)與思考就編寫的程序而言，雖然能達(dá)到預(yù)期