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

南京理工大學(xué)人工智能大論文題目：遺傳算法實(shí)現(xiàn)八皇后問題姓名：xxxx學(xué)號(hào)：xxxxxxxxxxxxxx專業(yè)：xxxxxxxxxx院系：xxxxxxxxxxxxxxxx老師：xxxxxx日期：2015年12月20日目錄TOC\o"1-5"\h\z\o"CurrentDocument"摘要3一、實(shí)驗(yàn)背景4\o"CurrentDocument"1.1N皇后問題描述4\o"CurrentDocument"1.2遺傳算法4\o"CurrentDocument"二、實(shí)驗(yàn)?zāi)康?\o"CurrentDocument"三、實(shí)驗(yàn)內(nèi)容5\o"CurrentDocument"四、實(shí)驗(yàn)步驟5\o"CurrentDocument"4.1編碼方案5\o"CurrentDocument"4.2初始化種群6\o"CurrentDocument"4.3適應(yīng)度的計(jì)算7\o"CurrentDocument"4.4遺傳算子84.4.1選擇算子84.4.2交叉方法84.4.3變異方法8\o"CurrentDocument"4.5局部搜索10\o"CurrentDocument"4.6終止策略10\o"CurrentDocument"4.7實(shí)現(xiàn)描述10\o"CurrentDocument"五、實(shí)驗(yàn)結(jié)果和分析11\o"CurrentDocument"六、總結(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ǔ)知識(shí)和基本方法的綜合運(yùn)用及變通能力，增強(qiáng)對算法的理解能力，提高軟件設(shè)計(jì)能力，在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。通過本實(shí)驗(yàn)的設(shè)計(jì)與編程實(shí)現(xiàn)讓學(xué)生掌握基于狀態(tài)空間知識(shí)表示的局部搜索策略，對遺傳算法中的編碼方法以及選擇、復(fù)制、交叉、變異等基本算子有深入的理解，熟練運(yùn)用C++，編寫一個(gè)遺傳算法解決八皇后問題的應(yīng)用程序。關(guān)鍵詞：八皇后；遺傳算法；C++1.1N皇后問題描述N皇后問題描述如下：在nXn格棋盤上放置彼此不受攻擊的N個(gè)皇后。按國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。N皇后問題等價(jià)于在以下三個(gè)約束條件：任何2個(gè)皇后不放在同一行；任何2個(gè)皇后不放在同一列；任何2個(gè)皇后不放在同斜線。我們把nXn的棋盤看作二維方陣，其行號(hào)從上到下列號(hào)從左到右依次編號(hào)為0，1，…，7。設(shè)任意兩個(gè)皇后，皇后1和皇后2的坐標(biāo)分別是（i，j）和（k，1），則如果這兩個(gè)皇后在從棋盤左上角到右下角的主對角線及其平行線（斜率為-1的線）上，有i—j=k—l；如果這兩個(gè)皇后在斜率為+1的每一斜線上，有i+j=k+1；以上兩個(gè)方程分別等價(jià)于i—k=j—l和i—k=l—j因此任兩皇后的在同一斜線上的充要條件是'「—k|=V_，|。滿足兩個(gè)皇后不在同一斜線上的條件表示為：li—kUj?—I'兩皇后不在同一行用式表示為：Jk兩皇后不在同一列用式表示為：j』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)空間知識(shí)表示的局部搜索策略，對遺傳算法中的編碼方法以及選擇、復(fù)制、交叉、變異等基本算子有深入的理解。本次設(shè)計(jì)旨在學(xué)習(xí)各種算法，訓(xùn)練對基礎(chǔ)知識(shí)和基本方法的綜合運(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é)號(hào)末尾為0，按照老師要求，則應(yīng)該實(shí)現(xiàn)n=8，即八皇后問題。四、實(shí)驗(yàn)步驟現(xiàn)在我們把任意n個(gè)皇后的任意一種放置辦法當(dāng)作一個(gè)個(gè)體（染色體），把其中的任意一個(gè)皇后當(dāng)作一個(gè)基因，用遺傳算法來解決該問題。4.1編碼方案對于此問題有三種編碼方案：排列編碼、二進(jìn)制編碼、矩陣編碼，在這里，采用第一重編碼方案，即排列編碼，具體描述如下：用一維n元數(shù)組M0,1...,n-1]來表示一個(gè)個(gè)體，其中x[i]e{0,1...,n-1},x[i]表示皇后i放在棋盤的第i行第x[i]列，即第i行第x[i]列放置一個(gè)皇后。例如，x[0]=0表示棋盤的第0行第0列放一個(gè)皇后。數(shù)組第i個(gè)元素表示第i行的放置情況，可以看作一個(gè)基因。這種編碼可以自然的解決了某一行只能放一個(gè)皇后的約束，如果數(shù)組的每一個(gè)元素x[i]都不重復(fù)，可以看成0—n-1的一種排列，就自然保證每一列只能放一個(gè)皇后。因此在交叉變異和產(chǎn)生個(gè)體時(shí)必須注意x[i]的唯一性。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ì)算11‘和/攻擊設(shè)七表示皇后i和皇后j之間的相互攻擊，即：a廣.訐和不攻擊皇后i和j的攻擊度:11Ix[i]-X[j]l=i-皇后i和j的攻擊度:ij0other第i個(gè)皇后的攻擊度a表示皇后i在除自身外其余n-1個(gè)皇后中與皇后i相沖突的i數(shù)目，即有幾個(gè)皇后與皇后i相攻擊。如果皇后i和所有皇后都沖突則攻擊度為n-1，與所有的皇后都不沖突攻擊度為0。因此，得到氣=方:%+丈%。j=1j=i+1同理，皇后i的非攻擊度表示和皇后i沒有沖突的皇后數(shù)目，設(shè)々表示i的非攻擊度，則b=n_1一氣。我們根據(jù)非攻擊度計(jì)算：用/表示基因i的適應(yīng)度，即第i個(gè)皇后的非攻擊度，則ifi=bi。如果某一個(gè)皇后i和所有其余的n-1個(gè)皇后都互不攻擊，則L=n—L個(gè)體的適應(yīng)度是指所有皇后的非攻擊度之和，適應(yīng)度函數(shù)可表示如下：f=^fi。i=1對于一個(gè)合法的放置方案每一個(gè)基因的適應(yīng)度都是n-1，此時(shí)染色體的適應(yīng)度是乃X(n—1)。//更新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)生出超級(jí)個(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ī)生成交叉位置m(0<m<n-1)，把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.unitFitnessII(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)描述人、雙親遺傳算法。產(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)化解，如下圖:「墮：MonDec2115：11：042015吉聆MonDftc211?；：11：04231S遜小為80-000秒-由結(jié)果可得：程序的開始時(shí)間與結(jié)束時(shí)間，因而得出運(yùn)算所用時(shí)間，這里運(yùn)算時(shí)間非常小，因而為0秒。還可以看到八皇后的一個(gè)優(yōu)化解，與本次迭代的次數(shù)。222秒cc*1□□□□□□■□BEes;匚□口匚■匚□口onon80.士-口口■口口口口口HM為！^?_Jr~nnn=小"—□□□□□■□□:-八耳□□□□□□□■一M策拉中匚■□匚匚匚口口一廿是」.苴一口□□■□□□口繼續(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,