国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

遺傳算法求解N皇后問題的優(yōu)化

2010-01-15 10:53:38王振義
關(guān)鍵詞:山西大同皇后適應(yīng)度

王振義

(1.太原理工大學(xué)計(jì)算機(jī)與軟件學(xué)院,山西太原030024;2.山西大同大學(xué)物理與電子科學(xué)學(xué)院,山西大同037009)

遺傳算法求解N皇后問題的優(yōu)化

王振義1,2

(1.太原理工大學(xué)計(jì)算機(jī)與軟件學(xué)院,山西太原030024;2.山西大同大學(xué)物理與電子科學(xué)學(xué)院,山西大同037009)

∶采用vector容器高效的染色體整數(shù)編碼和成熟的泛型算法,改良遺傳算法求解N皇后問題,說明此方法更通用、簡(jiǎn)潔和高效.

∶N皇后問題 適應(yīng)值 遺傳算法 STL

1 N皇后問題描述

八皇后問題是著名的數(shù)學(xué)家Gauss于1850年提出的.要求橫、豎、斜方向上都不能有兩個(gè)及兩個(gè)以上皇后在同一條直線上,問題也可以推廣到N個(gè)皇后.求解這一問題的算法很多,過去一般用窮舉法、回溯法求解.由于其時(shí)間復(fù)雜度為O(N!),是一個(gè)NP難問題.對(duì)于皇后變多耗時(shí)激增的計(jì)算機(jī)求解問題,就需利用非常規(guī)的技術(shù)求解.解決的辦法通常是編寫快速的算法,或是采用多個(gè)CPU并行計(jì)算或分布式計(jì)算.本文使用STL中的容器和泛型算法對(duì)基本遺傳算法進(jìn)行改進(jìn),達(dá)到滿意的效果.

2 遺傳算法

遺傳算法(Genetic Algorithms,簡(jiǎn)稱GA),是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型,基于生物學(xué)進(jìn)化原理的一種全局搜索算法.通過用計(jì)算機(jī)模擬生物進(jìn)化過程,使群體不斷優(yōu)化,并在進(jìn)化過程中逐漸接近最優(yōu)解.其特點(diǎn)是簡(jiǎn)單、通用、魯棒性強(qiáng)和適于并行處理.把遺傳算法用于求解NP完全問題,可為求解NP完全問題給出新的思路.

遺傳算法的框架是由Holland提出的,可描述為:

①隨機(jī)產(chǎn)生初始種群;

②利用適應(yīng)度函數(shù)對(duì)個(gè)體計(jì)算函數(shù)值;

③按一定的概率選擇對(duì)個(gè)體進(jìn)行選擇、交叉、變異等操作產(chǎn)生新種群;

④重復(fù)②、③兩步,直到找到最佳解或迭代次數(shù)達(dá)到指定的上限;

3 STL(Standard Template Library)

STL是C++標(biāo)準(zhǔn)庫的一部分,全稱叫做標(biāo)準(zhǔn)模板庫,它的作用就是提供一些泛型算法和容器.

使用STL主要有如下理由:

①效率高:算法通常比程序員產(chǎn)生的循環(huán)更高效.

②正確性:寫循環(huán)時(shí)比調(diào)用算法更容易產(chǎn)生錯(cuò)誤.

③可維護(hù)性:算法通常使代碼比相應(yīng)的顯式循環(huán)更干凈、更直觀.

在進(jìn)行遺傳算法求解N皇后問題的計(jì)算中,當(dāng)基因數(shù)量和總?cè)簲?shù)量較大時(shí),使用遺傳算法對(duì)數(shù)據(jù)的處理,需多次用到數(shù)組循環(huán),這是相當(dāng)耗時(shí)的.本文采用vector容器存放數(shù)據(jù),運(yùn)用STL泛型算法處理數(shù)據(jù),如accumulate求和,max_element求最大值,remove和copy配合著對(duì)vector數(shù)據(jù)重排等,為用遺傳算法求解N皇后問題的數(shù)據(jù)處理帶來極大的便捷、簡(jiǎn)潔和高效.

4 編程實(shí)現(xiàn)

N皇后問題要求,每行,每列,主次對(duì)角線都只有一個(gè)棋子存在.這里采用整數(shù)編碼,每個(gè)染色體都是由N個(gè)基因的整數(shù)組成,取值范圍是1-N.編碼位置和數(shù)值代表皇后所處行和列的位置.這樣,保證了在每行,每列只有一個(gè)皇后,一個(gè)染色體代表著一種棋盤的布局.例設(shè)染色體用G=(G1,G2,…Gi… Gn)表示,Gi代表在第i行上的皇后放在第Gi列的位置.采用VC作為平臺(tái),在建立main程序后,建立基因組類和群體類.

4.1 基因組類∶CGenome

成員 vector<int> vecBits;//表示一個(gè)染色體

dFitness;//染色體對(duì)應(yīng)的適應(yīng)度.成員函數(shù)有:

CreateGenome函數(shù)創(chuàng)建個(gè)體.首先生成一個(gè)按從小到大順序排列的基因組,再用random_shuffle函數(shù)使這個(gè)染色體中的基因隨機(jī)重排,得到新的個(gè)體.

UpdateFitnessScore計(jì)算適應(yīng)度.在主次對(duì)角線上的彼此有一個(gè)沖突數(shù)記為1,累加本染色體中所有的沖突后加1,再求倒數(shù)作為適應(yīng)度,顯然沖突越多,對(duì)應(yīng)的適應(yīng)度值越小,沒有任何沖突時(shí),值為1,表示找到了一個(gè)合適的解.

4.2 種群類∶CPopulation

成員

vector<CGenome> vGenomes;//群體

vector<CGenome>::iterator vGit;//迭代器

vector<CGenome> vBabyGenomes;//下級(jí)群體

intm_iBestIndex;//最好個(gè)體的索引

intm_iWorstIndex;//最好個(gè)體的索引

CGenome m_CCurrentBestGenome;//目前最好的個(gè)體CGenomem_CBestGenome;//當(dāng)代最好的個(gè)體CGenomem_CWorstGenome;//當(dāng)代最糟的個(gè)體建立一些算法函數(shù)完成指定功能.

①初始化種群:(GenerateInitialPopulation)

完成每個(gè)種群的初始化,同時(shí)調(diào)用CGenome建立的UpdateFitnessScore對(duì)每個(gè)個(gè)體進(jìn)行計(jì)算.

②選擇算子(SelectionOperator)

按賭輪選擇,保證適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中.在計(jì)算總的適應(yīng)度時(shí)用到了 accumulate(vG.begin(),vG.end(),0.0,Add);其中 Add(const double Val,const CGenome&element){return Val+element.dFitness;}就是對(duì)類中成員適應(yīng)度(dFitness)的累加.

③交叉算子(CrossoverOperator)

當(dāng)隨機(jī)數(shù)小于交叉概率(這里取0.75)時(shí),進(jìn)行交叉運(yùn)算,由于新種群的個(gè)體是隨機(jī)產(chǎn)生的,選用相鄰(也可以隨機(jī)配對(duì))的個(gè)體作為父母本進(jìn)行交叉.不同于位編碼的交叉,為確保同行同列不沖突,新個(gè)體中的數(shù)字不能有重復(fù)的.先隨機(jī)生成單個(gè)交叉點(diǎn)的位置,子代個(gè)體的前半段直接拷入交叉點(diǎn)前父(母)的前半段,母(父)本中刪除個(gè)體前半段已有的數(shù)字作為個(gè)體的后半段.

④變異算子(MutationOperator)

為了避免出現(xiàn)早熟收斂,當(dāng)隨機(jī)數(shù)小于變異概率(這里取0.2)時(shí)隨機(jī)生成兩個(gè)基因位,交換兩個(gè)位置的基因,對(duì)個(gè)體進(jìn)行變異,這里用到了swap函數(shù).

⑤干預(yù)進(jìn)化(PerformEvolution)

運(yùn)用 max_element(vG.begin(),vG.end(),best);記錄當(dāng)前群體中最好(或最糟)的個(gè)體,以及對(duì)應(yīng)的索引編號(hào),其中best為自定義的判斷式,容器中的相鄰項(xiàng)比較,后的數(shù)大時(shí)為真進(jìn)行代換,最后得到適應(yīng)度最大的個(gè)體,最糟的結(jié)果是利用后面的數(shù)小時(shí)為真,也就是得到整個(gè)群體中適應(yīng)度最小的個(gè)體.用最優(yōu)的個(gè)體替換掉最糟的個(gè)體,保證最優(yōu)的個(gè)體直接進(jìn)入下一代,剔除最糟的個(gè)體保證的整個(gè)群體有更大的適應(yīng)度.

表1 和其它文獻(xiàn)用時(shí)對(duì)比(t/s)

測(cè)試條件:染色體長(zhǎng)度等于皇后數(shù),種群大小選200,交叉概率0.75,變異概率0.2,最大代數(shù)根據(jù)要求皇后的數(shù)量決定,一般取200即可,可以通過試解后在調(diào)整.

通過在VC++集成編輯環(huán)境下的運(yùn)行,本程序用時(shí)明顯小于回溯法用時(shí)[5],對(duì)皇后數(shù)量大于100的問題求解,明顯優(yōu)于基本遺傳算法.此方法稍加修改就可以解決其他問題,如旅行商和其它數(shù)值類求解問題.本文利用容器和調(diào)用算法的方法,對(duì)其他類似問題的算法的優(yōu)化有一定借鑒意義.

[1]李建華.智能組卷系統(tǒng)與遺傳算法[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版,2009,25(3):14-16.

[2]胡能發(fā).一種二元單親演化差基因變異算法[J].長(zhǎng)江大學(xué)學(xué)報(bào):自然科學(xué)版,2004,1(1):74-76.

[3]宋曉霞.遺傳算法中初始群體技術(shù)的改進(jìn)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(22):5485-5487.

[4]馬永,賈俊芳.遺傳算法研究綜述[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版,2007,23(3):11-13.

[5]劉娟,歐陽建權(quán),陳良軍.用混合遺傳算法求解N皇后問題[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2007,29(2):37-41.

[6]楊凱,羅文俊.基于BIT位運(yùn)算的N皇后問題解法[J].貴州師范大學(xué)學(xué)報(bào):自然科學(xué)版,2009,27(2):96-98.

Genetic A lgorithm Optim ization of N Queens Problem

WANG Zhen-yi1,2
(1.College of Computer and Software,Taiyuan University of Technology,Taiyuan S hanxi,030024;2.School of Physics and Electronics Science,ShanxiDatong University,Datong Shanxi,037009)

This literary grace is with high-efficient chromosome integer code of vector container and ripe suffused withing type algorithm,can improve the algorithm algorithm and solve N queen's question,which prove s thismethod is common,more succinct and high-efficient.

N Queen;f itness;Genetic Algorithm;STL

∶TP18

∶A

∶1674-0874(2010)02-0013-02

∶2010-01-08

∶王振義(1955-),男,山西大同人,副教授,研究方向:算法.

〔編輯 高?!?/p>

猜你喜歡
山西大同皇后適應(yīng)度
改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
山西大同 黃花菜豐收在望
《山西大同大學(xué)學(xué)報(bào)(自然科學(xué)版)》征稿簡(jiǎn)則
山西大同大學(xué)采礦研究所簡(jiǎn)介
山西大同邀客共賞“小黃花大產(chǎn)業(yè)”
遇皇后
奇妙博物館(2018年7期)2018-08-07 08:08:34
為什么皇后鎮(zhèn)被稱為“冒險(xiǎn)之都”?
被放逐的皇后
基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
少數(shù)民族大學(xué)生文化適應(yīng)度調(diào)查
徐汇区| 商丘市| 博湖县| 玉田县| 博乐市| 长子县| 白城市| 广宗县| 大竹县| 尉犁县| 博白县| 克什克腾旗| 双江| 通化市| 习水县| 梨树县| 绍兴市| 沅陵县| 彰武县| 社旗县| 开原市| 嘉义县| 扎赉特旗| 郯城县| 竹溪县| 长岭县| 涪陵区| 巴南区| 清水河县| 军事| 霞浦县| 闻喜县| 定南县| 额济纳旗| 五指山市| 衡水市| 盐边县| 长治市| 伊宁县| 兴海县| 博罗县|