先解釋下什么是8皇后問題：在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。在不考慮翻轉(zhuǎn)和旋轉(zhuǎn)等價(jià)的情況下，8皇后問題共有96個(gè)不同的解。
而n皇后問題就是將8*8的棋盤換為n*n的棋盤，同時(shí)擺放n個(gè)皇后使之不能相互攻擊。
常用的解法是回溯法，通過不斷遞歸的嘗試來一個(gè)一個(gè)放置棋子，這種方法其實(shí)規(guī)避了很多不成立的情況，所以控制了一些解空間的范圍，但是這種方法試圖在一段程序當(dāng)中將所有解求出來，隨著n的變大，解空間在急速變大，遞歸的巨大空間開銷會(huì)讓求解變得很困難，效率會(huì)下降很多。
遺傳算法也可以用來解決n皇后問題，但是遺傳算法的本質(zhì)是根據(jù)適應(yīng)值來選擇和制造更多的靠近目標(biāo)情況的解，所以不一定能得到所有的解，同時(shí)也不能知道對(duì)于確定的n皇后問題的解的個(gè)數(shù)。在這種情況下的遺傳算法有一些暴力破解的因素在其中。
下面談一談幾個(gè)關(guān)鍵問題的解決（以8皇后問題為例）。
1、編碼問題
我采用的是整數(shù)編碼，染色體長(zhǎng)度（基因位的個(gè)數(shù)）等于8，每一位為一個(gè)整數(shù)（該整數(shù)≥0，＜8*8），且不能相同，每一個(gè)基因位表示的就是一個(gè)棋子擺放的位置。
2、適應(yīng)值的計(jì)算問題
適應(yīng)值的評(píng)價(jià)標(biāo)準(zhǔn)為發(fā)生沖突的個(gè)數(shù)n的倒數(shù)，即沖突越多，適應(yīng)值越低，不發(fā)生沖突時(shí)適應(yīng)值為1（1/1），但是這種評(píng)價(jià)也存在一定的問題，就是隨著沖突的增多，適應(yīng)值的減小會(huì)變的沒那么明顯（比如說不沖突適應(yīng)值為1，沖突一個(gè)為0.5，沖突2個(gè)為0.333，沖突三個(gè)為0.25，沖突四個(gè)為0.2），所以選擇的力度會(huì)相對(duì)較弱。可以考慮改為其他的方式進(jìn)行評(píng)價(jià)。
3、選擇問題
采用的是線性排名選擇方式，因?yàn)樯鲜鲈?，采用線性排名選擇策略會(huì)一定程度上抵消掉適應(yīng)值計(jì)算的問題。
4、突變問題
突變采用的是自適應(yīng)性變異，即越收斂搜索范圍越小的方法。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式