用遺傳算法解決n皇后問題

1、用遺傳算法解決n皇后問題（李懷遠(yuǎn)）一、問題提出N皇后問題描述如下：在nxn格棋盤上敖置彼此不受攻擊的n個(gè)皇后。按國際象棋的 規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。N皇后問題等價(jià)于在以 下三個(gè)約束條件下：約束任何 2個(gè)皇后不放在同一行；約束任何 2個(gè)皇后不放在同一 歹U；約束任 何2個(gè)皇后不放在同斜線；找出一種合法的放置方案。我們把nxn的棋盤看作二維方陣，其行號(hào)從上到下列號(hào)從左到右依次編號(hào)為0, 1, -； n-l. o設(shè)任意兩個(gè)皇后，皇后1和皇后2的坐標(biāo)分別是（i.j）和（k,l）,則如果這兩個(gè)皇 后在從棋盤左 上角到右下角的主對角線及其平行線（斜率為-1的線）上，有i

2、-j=k-l=0 ;如果這兩個(gè)皇后在斜率為+ 1的每一斜線上，有i+j=k+l ；以上兩個(gè)方程分別等價(jià)于i-k=j-l和i-k=l-j因此任兩皇后的 在同一斜線上的充要條件是l/-Al=l J-/I式因此滿足兩個(gè)皇后不在同一斜線上的條件表示為：式兩皇后不在同一行用式表示為：iHk式兩皇后不在同一列用式表示為：jAl式此屬NP問題不易求解，現(xiàn)在我們把任意n個(gè)皇后的任意一種放置辦法當(dāng)作一個(gè)個(gè)體（染色體），把其中的任意一個(gè)皇后當(dāng)作一個(gè)基因，用遺傳算法來解決該問題。二、編碼方案對于此問題我提出兩種編碼方案。A.編碼方案1:排列編碼用一維n元數(shù)組x0 : n-l來表示一個(gè)個(gè)體，其中xie0,l,n-1,

3、 xi表示皇后i放在棋盤的第i行第xi歹U,即第i行第xi列放置一個(gè)皇后。例如，x0=0表示棋盤 的第0行第0列敖一個(gè)皇后。數(shù)組第i個(gè)元素表示第i行的放置情況，可以看作一個(gè)基因。這種編碼可以自然的解決了某一行只能放一個(gè)皇后的約束，如果數(shù)組的每一個(gè)元素xi都不重復(fù)，可以看成0n-l的一種排列，就自然保證每一列只能放一個(gè)皇后。因此在交叉變異和產(chǎn)生個(gè)體時(shí)必須注意 xi的唯一性。B.編碼方案2:二進(jìn)制編碼用一維數(shù)組x0 : n2-l表示一個(gè)個(gè)體，其中 A/e0,l ） o設(shè)i = rxn+c,其中r e xI xeZ A0 x n-1,c e xI xeZ A0 x /?-1 ） , r 表示行號(hào)是

4、n 整除 i 的整數(shù)部分，C是余數(shù)表示列號(hào)，如果 xi = l表示棋盤的第r行第c列放有某一個(gè)皇后， 如 果xi= 0表示棋盤的第r行第c列沒有放置皇后。因?yàn)樗褂昧硕M(jìn)制編碼，所以 這種編 碼方法可以借用通用的二進(jìn)制編碼的交叉變異方法，這是它優(yōu)于編碼1的地方， 但是用它 隨機(jī)產(chǎn)生的編碼可能不滿足題目的約束和約束，因此可能在生成個(gè)體或 者交叉變異時(shí) 強(qiáng)制它滿足前兩個(gè)約束或者加大對不滿足約束的個(gè)體進(jìn)行懲罰或淘汰或 計(jì)算適應(yīng)值時(shí)加以 分辨。C.編碼方案3:矩陣編碼用矩陣或二維數(shù)組xO: n-lO : n-l表示一個(gè)染色體，且頁刀？0,1如果xij = l表示棋盤的第i行第j列放置一個(gè)皇后，xij=

5、0表示棋盤的第i行第j列為空。該編碼雖然直觀，但為了滿足題目的約束和約束，同樣需要在生成個(gè)體或者交叉變異時(shí)強(qiáng)制它滿足前兩個(gè)約束或者加大對不滿足約束的個(gè)體進(jìn)行懲罰或淘汰或計(jì)算適應(yīng)值時(shí)加 以分辨。腳攻擊,和? ?不攻 擊三、適應(yīng)度的計(jì)算設(shè)”表示皇后i和皇后j之間的相互攻擊，即對于編碼1:皇后i和j的攻擊度：=v0other對于編碼2:設(shè)i和j可以分別分解成,=八+ J =,廠l/CC分別是皇后:和j的行號(hào)和列號(hào)，i和j攻擊度：=l時(shí)放大差異。C.方法3:綜合合法的皇后數(shù)目和非攻擊度的自適應(yīng)方法可以想象隨機(jī)生成的個(gè)體合法皇后的數(shù)目幾乎都是0,特別是在初始迭代中，即使像方法2中那樣放大適應(yīng)值效果也不會(huì)

6、太好，此時(shí)各個(gè)棋局的差異主要在非攻擊度方面。當(dāng) 在迭代 后期一個(gè)棋局中合法皇后數(shù)目可能會(huì)增多，而且此時(shí)合法皇后數(shù)目更有意義。鑒于此我們應(yīng)同時(shí)考慮合法的皇后數(shù)目和非攻擊度兩個(gè)因素，并且他們的重要性隨迭代次數(shù)的變化而變化，因此可令適應(yīng)函數(shù)f為：/ = g|(/?)e + g、(/?)方，其中h是迭代次 數(shù)；e是合法皇后 數(shù)目；b是非攻擊度；g.(h)關(guān)于h的增函數(shù)；g2(h)關(guān)于h的增幅不能 大約gl(h)的增幅，例 如可取g = Ag =h 0 四、交叉方法可用的交叉方法有以下幾種。設(shè) pl, p2是要交叉的兩個(gè)父染色體，cl, c2是子代,是交 叉的結(jié)果，n是編碼長度。交叉方法1:單點(diǎn)交叉。先

7、隨機(jī)生成交叉位置 m(Om(%) = 2 = A(? )0,均值E(x)和方 %!差D(x)是位串長度n的函數(shù))生成交叉點(diǎn)數(shù)x;然后隨機(jī)生成交叉位置，把pl和p2分成x+1 段；令cl取pl的偶數(shù)段和p2的奇數(shù)段，c2取pl的奇數(shù)段和p2的偶數(shù)段。 注意對編碼方 案1仍需做映射匹配。交叉方法3:均勻交叉。設(shè)x是0,1上的均勻分布的隨機(jī)變量，新個(gè)體可按下面方法生成：cr p x 0.5_ I p2t 尢 0.5P 2 匚 x0.5x0.5使用偏置概率參數(shù)的均勻交叉 （0. 5x0. 8 ）不存在多點(diǎn)交叉算子操作引起的位置偏差。在實(shí)際中我們用隨機(jī)生成二進(jìn)制 01串來表示X。對于編碼方案3可以把pl

8、的第m行（列） 或 p2的第m行（列）進(jìn)行均勻交叉。對于編碼方案 1還要考慮重復(fù)時(shí)候的匹配映射。例 1: pl=1234567, p2=4523167, x=1100101，則 cl = 1253467, c2=4531267，其中 cl 中的 5 和4以及c2中的1和2是匹配映射的結(jié)果。D.交叉方法4:按行（列）交叉。對于編碼方案1,此方法不適合。對于編碼 2和3,先隨機(jī)生成要交叉的行（列） 數(shù)ml和 m2 （ml, m2 屬于a I xeZ aOx7?-1 ）;然后把 pl 的 ml 行（列）和 p2 的 m2行（列）互換便得cl和c2o以上的交叉方法不僅對于編碼1都要有一個(gè)映射匹配的過程

9、，而且對于編碼2和3者B有一個(gè)致命的缺陷：交叉后棋局中 1的個(gè)數(shù)（皇后的數(shù)目）可能發(fā)生變化。例 2:以編碼 2 的兩點(diǎn)交叉為例，設(shè) pl=0100 1000 0010 0001, p2=0001 0100 0010 1000,棋局為 4X4,交叉位置是 3, cl=0101 0100 0010 1000, c2=0000 1000 00100001,顯然 cl多了一個(gè)1 （皇后）c2少了 一個(gè)1。解決此問題可以有多種方法，總的來說有調(diào)整交叉位置和增加刪除1來實(shí)現(xiàn)。A.選擇合適的交叉位置。對于前三種交叉方法，根據(jù)交叉位置分段后，必須使pl的偶數(shù)段和p2的奇數(shù)段含1的 總數(shù)目等于n,相應(yīng)地pl的奇

10、數(shù)段和p2的偶數(shù)段1的總數(shù)目自然等于no對于交 叉方法4 必須使要交叉的行（列） ml和m2中1的數(shù)目相等，即必須選擇兩個(gè)含 1的數(shù) 目相等的兩 行（列）進(jìn)行交叉。這種方法對隨機(jī)生成交叉位置的交叉方法而言，需要?jiǎng)討B(tài)的尋找每一對基因串的交叉位置；如果是固定位置的交叉方法，很難保證在固定位置段上1的數(shù)目符合要求，故不可取。B.均勻的插入刪除1。我們從交叉后含1數(shù)目超過n的子個(gè)體中刪除某些1使的子個(gè)體中1的數(shù)目等于n,在 1的個(gè)數(shù)不足n的子個(gè)體中插入1使得1的數(shù)目到達(dá)no在插入刪除后盡可能得使 1的個(gè)數(shù) 均勻分布在串中，這樣可能使皇后之間的沖突減少。刪除 1的原則是優(yōu)先刪除其 前0的個(gè) 數(shù)最少的那些

11、1,插入1的原則是在0的連續(xù)最大長度中間位置插入 1。以上 面例2的交叉 結(jié)果cl, c2為例來說明此方法。例3:首先統(tǒng)計(jì)串中每一個(gè)位置前連續(xù)的0的數(shù)目。cl的統(tǒng)計(jì)串zl=0101 0101 23401012; z2=0123 4012 3450 1234。cl 中第 2、4、6、13 個(gè) 1 前 0 數(shù)目均為最小值 1,故 可任意選擇其中一個(gè)刪除；c2中第11個(gè)位置的1前有5個(gè)零，故選擇第5和第11的中間 位置8插入一個(gè)1。對于交叉方法4可以僅對交叉的兩行進(jìn)行上述操作。C.根據(jù)攻擊度插入刪除1。插入1的原則是把1插入在攻擊度最小的位置，刪除的原則是刪除攻擊度最大的1,這樣可以使變異的個(gè)體盡可

12、能的保持較小的攻擊度盡可能得保持最優(yōu)。也可以在插入刪除時(shí)不僅以基因的攻擊度為原則，還可進(jìn)一步以整個(gè)個(gè)體和基因的攻擊度都盡可能小為原則，但這樣計(jì)算量就更大了。對于交叉方法4,可以只對交換的兩行進(jìn)行插入刪除操作。下面以例2變異的子代為例。 例4:首先統(tǒng)計(jì)cl中所有1的攻擊度和c2中所有0的攻擊度（在統(tǒng)計(jì)0的攻擊度 時(shí)把0假定為1）得，cl中所有1的攻擊度依次是：2, 2, 2, 1, 1; c2中所有0的攻 擊度依次是：3. U 1.1、3、2、3、2、2、2、2、2、3。因此cl中攻擊度最大的皇后是第2, 4、6可以選擇其中之一刪除；c2中攻擊度最小的位置是 2、3、4因此可以在 其中之一插入一

13、個(gè)1。這些插入刪除1 的方法也可以應(yīng)用于初始種群的生成中。D.隨機(jī)插入刪除1。對多余的1隨機(jī)的選擇一個(gè)將它刪除；在插入1時(shí)隨機(jī)的選擇一個(gè)空位置。該方法 實(shí)現(xiàn)簡單，但啟發(fā)程度不高。E.加大淘汰和懲罰的力度。在解碼時(shí)如果發(fā)現(xiàn)1的個(gè)數(shù)非法則淘汰之，或在計(jì)算適應(yīng)值時(shí)懲罰1的個(gè)數(shù)非法的染色體。但是由于這種現(xiàn)象比較嚴(yán)重，用此方法有可能會(huì)因?yàn)樘蕴^多而多樣性不足收斂過早，因此在淘汰時(shí)最好還要隨機(jī)生成新的個(gè)體以補(bǔ)充多樣性不足的問題。五、變異方法A.基于位置的變異。隨機(jī)的產(chǎn)生兩個(gè)變異位置 ml、m2,把m2處的基因放在 ml前，即隨機(jī)選擇兩個(gè)基因?qū)?一個(gè) 基因放在另一個(gè)基因前面。B.基于次序的變異。隨機(jī)的產(chǎn)生兩

14、個(gè)變異位置 ml、m2,把ml和m2處的兩個(gè)基因互換，即隨機(jī)選擇兩個(gè)基因相互交換。C.打亂次序的變異。產(chǎn)生兩個(gè)隨機(jī)的位置 m 1、m2,把訊和m2之間的基因打亂次序隨機(jī)重排，即隨機(jī)選擇染色體中的一段打亂次序重排。其中把其中一段逆序是常用的方法。以上三種變異方法都可以分成單點(diǎn)變異和多點(diǎn)變異，單點(diǎn)變異一次只變異一對點(diǎn)，多點(diǎn)變異一次可以變異多對點(diǎn)。D.循環(huán)移位變異。隨機(jī)產(chǎn)生移動(dòng)位數(shù) m,然后把染色體向左/右移動(dòng)m位，把溢出的位數(shù)補(bǔ)到尾部，即染 色體 向左/右移動(dòng)若干位。E.分段重組變異。隨機(jī)生成變異點(diǎn)數(shù) X,然后隨機(jī)生成變異位置，把染色體分成x+1段，再把著x +1段 隨機(jī)混排（每一段內(nèi)部順序不變，

15、只改變段間的順序）。F.隨機(jī)變異。隨機(jī)生成變異數(shù)目 m,隨機(jī)選擇m個(gè)皇后把它去掉，然后再隨機(jī)選擇m個(gè)位置放上皇后。G.基于攻擊度的變異。選擇染色體中若干個(gè)攻擊度最高的皇后把它去掉；在攻擊度最低的幾個(gè)空位置放置同樣多個(gè)皇后。這樣可以具有較高的啟發(fā)性，但是計(jì)算復(fù)雜。六、實(shí)現(xiàn)描述。選擇方法多種多樣：按適應(yīng)度比例選擇；Boltzmann選擇；排序選擇；聯(lián)賽選擇；精英 選擇；隨機(jī)遍歷抽樣法；父子競爭選擇；穩(wěn)態(tài)選擇等都可以應(yīng)用于此問題。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í)行。C.非迭代遺傳算法。產(chǎn)