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

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

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

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

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

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

6、太好，此時各個棋局的差異主要在非攻擊度方面。當(dāng) 在迭代 后期一個棋局中合法皇后數(shù)目可能會增多，而且此時合法皇后數(shù)目更有意義。鑒于此我們應(yīng)同時考慮合法的皇后數(shù)目和非攻擊度兩個因素，并且他們的重要性隨迭代次數(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是要交叉的兩個父染色體，cl, c2是子代,是交 叉的結(jié)果，n是編碼長度。交叉方法1:單點交叉。先

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

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

9、，而且對于編碼2和3者B有一個致命的缺陷：交叉后棋局中 1的個數(shù)（皇后的數(shù)目）可能發(fā)生變化。例 2:以編碼 2 的兩點交叉為例，設(shè) pl=0100 1000 0010 0001, p2=0001 0100 0010 1000,棋局為 4X4,交叉位置是 3, cl=0101 0100 0010 1000, c2=0000 1000 00100001,顯然 cl多了一個1 （皇后）c2少了 一個1。解決此問題可以有多種方法，總的來說有調(diào)整交叉位置和增加刪除1來實現(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ù)目相等，即必須選擇兩個含 1的數(shù) 目相等的兩 行（列）進行交叉。這種方法對隨機生成交叉位置的交叉方法而言，需要動態(tài)的尋找每一對基因串的交叉位置；如果是固定位置的交叉方法，很難保證在固定位置段上1的數(shù)目符合要求，故不可取。B.均勻的插入刪除1。我們從交叉后含1數(shù)目超過n的子個體中刪除某些1使的子個體中1的數(shù)目等于n,在 1的個數(shù)不足n的子個體中插入1使得1的數(shù)目到達no在插入刪除后盡可能得使 1的個數(shù) 均勻分布在串中，這樣可能使皇后之間的沖突減少。刪除 1的原則是優(yōu)先刪除其 前0的個 數(shù)最少的那些

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

12、能的保持較小的攻擊度盡可能得保持最優(yōu)。也可以在插入刪除時不僅以基因的攻擊度為原則，還可進一步以整個個體和基因的攻擊度都盡可能小為原則，但這樣計算量就更大了。對于交叉方法4,可以只對交換的兩行進行插入刪除操作。下面以例2變異的子代為例。 例4:首先統(tǒng)計cl中所有1的攻擊度和c2中所有0的攻擊度（在統(tǒng)計0的攻擊度 時把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、個1。這些插入刪除1 的方法也可以應(yīng)用于初始種群的生成中。D.隨機插入刪除1。對多余的1隨機的選擇一個將它刪除；在插入1時隨機的選擇一個空位置。該方法 實現(xiàn)簡單，但啟發(fā)程度不高。E.加大淘汰和懲罰的力度。在解碼時如果發(fā)現(xiàn)1的個數(shù)非法則淘汰之，或在計算適應(yīng)值時懲罰1的個數(shù)非法的染色體。但是由于這種現(xiàn)象比較嚴重，用此方法有可能會因為淘汰過多而多樣性不足收斂過早，因此在淘汰時最好還要隨機生成新的個體以補充多樣性不足的問題。五、變異方法A.基于位置的變異。隨機的產(chǎn)生兩個變異位置 ml、m2,把m2處的基因放在 ml前，即隨機選擇兩個基因?qū)?一個 基因放在另一個基因前面。B.基于次序的變異。隨機的產(chǎn)生兩

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

15、只改變段間的順序）。F.隨機變異。隨機生成變異數(shù)目 m,隨機選擇m個皇后把它去掉，然后再隨機選擇m個位置放上皇后。G.基于攻擊度的變異。選擇染色體中若干個攻擊度最高的皇后把它去掉；在攻擊度最低的幾個空位置放置同樣多個皇后。這樣可以具有較高的啟發(fā)性，但是計算復(fù)雜。六、實現(xiàn)描述。選擇方法多種多樣：按適應(yīng)度比例選擇；Boltzmann選擇；排序選擇；聯(lián)賽選擇；精英 選擇；隨機遍歷抽樣法；父子競爭選擇；穩(wěn)態(tài)選擇等都可以應(yīng)用于此問題。A.普通遺傳算法。.產(chǎn)生初始種群。. 從當(dāng)前種群中選擇兩個個體。. 把選中的兩個父個體雜交生成中間個體。. 重復(fù)2和3的（選擇和雜交）操作直至中間個體生成完畢。.對雜交后的中間個體根據(jù)變異概率進行變異，生成新種群。.檢驗停止準則，如果有解則停止，否則轉(zhuǎn)到2重復(fù)執(zhí)行。B.單親遺傳算法。.產(chǎn)生初始種群。.對當(dāng)前種群根據(jù)變異概率進行變異，生成新種群。. 檢驗停止準則，如果有解則停止，否則轉(zhuǎn)到2重復(fù)執(zhí)行。C.非迭代遺傳算法。產(chǎn)