遺傳算法程序設(shè)計(jì)探討

1、遺傳算法程序設(shè)計(jì)探討     摘  要本文通過對(duì)基本遺傳算法添加初始化啟發(fā)信息、改進(jìn)交叉算子和利用本身所固有的并行性構(gòu)架粗粒度并行遺傳算法等方法提高了遺傳算法的收斂性及其尋優(yōu)能力。    關(guān)鍵詞  遺傳算法；TSP；交叉算子 1  引言    遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法?？偟恼f來，遺傳算法是按不依賴于問題本身的方式去求解問題。它的目標(biāo)是搜索

2、這個(gè)*、高度非線性空間以找到具有最優(yōu)適應(yīng)值(即最小費(fèi)用的)的點(diǎn)1。    基本遺傳算法是一個(gè)迭代過程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，反復(fù)將選擇算子、交叉算子和變異算子作用于種群，最終可得到問題的最優(yōu)解和近似最優(yōu)解。2 遺傳算法程序設(shè)計(jì)改進(jìn)比較2.1 基本遺傳算法對(duì)TSP問題解的影響    本文研究的遺傳算法及改進(jìn)算法的實(shí)現(xiàn)是以C+語言為基礎(chǔ)，在Windows2000的版本上運(yùn)行，其實(shí)現(xiàn)程序是在Microsoft Visual Stadio 6.0上編寫及運(yùn)

3、行調(diào)試的。    1) 遺傳算法的執(zhí)行代碼m_Tsp.Initpop()；            /種群的初始化for(int i=0；i<m_Tsp.ReturnPop()；i+)         m_Tsp.calculatefitness(i)；  /計(jì)算各個(gè)個(gè)體的適應(yīng)值m_Tsp.statist

4、ics()；         /統(tǒng)計(jì)最優(yōu)個(gè)體while(entropy>decen|variance>decvar)/m_Tsp.m_gen<100)/將新種群更迭為舊種群，并進(jìn)行遺傳操作m_Tsp.alternate()；         /將新種群付給舊種群m_Tsp.generation()；        /對(duì)舊

5、種群進(jìn)行遺傳操作，產(chǎn)生新種群m_Tsp.m_gen+；m_Tsp.statistics()；        /對(duì)新產(chǎn)生的種群進(jìn)行統(tǒng)計(jì)    2) 簡(jiǎn)單的遺傳算法與分支定界法對(duì)TSP問題求解結(jié)果的對(duì)比    遺傳算法在解決NPC問題的領(lǐng)域內(nèi)具有尋找最優(yōu)解的能力。但隨著城市個(gè)數(shù)的增加，已沒有精確解，無法確定遺傳算法求解的精度有多高。一般情況下，當(dāng)?shù)鷶?shù)增大時(shí)，解的精度可能高，但是時(shí)間開銷也會(huì)增大。因此可以通過改進(jìn)遺傳算法來提高搜

6、索能力，提高解的精度。表1  10個(gè)城市的TSP問題求解結(jié)果數(shù)據(jù)算法試驗(yàn)結(jié)果簡(jiǎn)單遺傳算法分支定界法最佳解時(shí)間精確解時(shí)間試驗(yàn)12448.6100375s  2448.610037  00：07：30試驗(yàn)22448.61003713s試驗(yàn)32448.6100379s試驗(yàn)42459.54305410s試驗(yàn)52459.5430547s2.2  初始化時(shí)的啟發(fā)信息對(duì)TSP問題解的影響    1) 初始化啟發(fā)信息    在上述實(shí)驗(yàn)算法的基

7、礎(chǔ)上，對(duì)每一個(gè)初始化的個(gè)體的每五個(gè)相鄰城市用分支界定法尋找最優(yōu)子路徑，然后執(zhí)行遺傳算法。    2) 遺傳算法與含有啟發(fā)信息的遺傳算法求解結(jié)果的對(duì)比    當(dāng)城市數(shù)增至20個(gè)時(shí)，用分支定界法已經(jīng)不可能在可以接受的時(shí)間內(nèi)得到精確的解了，只能通過近似算法獲得其可接受的解。試驗(yàn)設(shè)計(jì)中算法的截止條件：固定迭代1000代。表2中的平均最優(yōu)解為經(jīng)過多次試驗(yàn)(10次以上)得到的最優(yōu)解的平均值，最優(yōu)解的出現(xiàn)時(shí)間為最優(yōu)解出現(xiàn)的平均時(shí)間，交叉操作次數(shù)為最優(yōu)解出現(xiàn)時(shí)交叉次數(shù)的平均值。表2  20個(gè)城市的TS

8、P問題求解結(jié)果數(shù)據(jù)算法交叉操作次數(shù)最優(yōu)解出現(xiàn)時(shí)間平均最優(yōu)解簡(jiǎn)單遺傳算法80244.479.4s1641.8含初始化啟發(fā)信息的GA79000.237.4s1398.9    從表2中可以看出，當(dāng)初始種群時(shí)引入啟發(fā)信息將提高遺傳算法的尋優(yōu)能力。同時(shí)縮短了遺傳算法的尋優(yōu)時(shí)間和問題的求解精度。2.3  交叉算子對(duì)TSP問題解的影響    1)循環(huán)貪心交叉算子的核心代碼for(i=1；i<m_Chrom；i+)  flag=0；  city=m_newpopf

9、irst.chromi-1；         /確定當(dāng)前城市  j=0；  while(flag=0&&j<4)        sign=adjcitycityj； /adjcity數(shù)組的數(shù)據(jù)為當(dāng)前城市按順序排列的鄰接城市      flag=judge(first，i，sign)； &

10、#160;/判斷此鄰接城市是否已經(jīng)存在待形成的個(gè)體中      j+；    if(flag= =0)       /如果所有鄰接城市皆在待擴(kuò)展的個(gè)體中        while(flag= =0)           

11、      sign=(int)rand()/(RAND_MAX/(m_ Chrom-1)；     /隨機(jī)選擇一城市           flag=judge(first，i，sign)；          if(flag=1)   &#

12、160;  m_newpopfirst.chromi=sign；      2)問題描述與結(jié)果比較    下面筆者用經(jīng)典的測(cè)試遺傳算法效率的Oliver TSP問題來測(cè)試循環(huán)貪心交叉算子的解的精度和解效率。Oliver TSP問題的30個(gè)城市位置坐標(biāo)如表3所示2。表3  Oliver TSP問題的30個(gè)城市位置坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)1(87，7)11(58，69)21(4，50)2(91，83)12(54，6

13、2)22(13，40)3(83，46)13(51，67)23(18，40)4(71，44)14(37，84)24(24，42)5(64，60)15(41，94)25(25，38)6(68，58)16(2，99)26(41，26)7(83，69)17(7，64)27(45，21)8(87，76)18(22，60)28(44，35)9(74，78)19(25，62)29(58，35)10(71，71)20(18，54)30(62，32) 表4  貪心交叉與部分匹配交叉的比較(Oliver TSP問題的30個(gè)城市)交叉算子交叉操作次數(shù)平均時(shí)間平均最優(yōu)解部分匹配

14、交叉5976031.2s517.0貪心交叉1577428.6s433.4    從表4、圖1中可以看到，貪心交叉算子大大提高了遺傳算法的尋優(yōu)能力，同時(shí)也降低了交叉操作次數(shù)。在多次試驗(yàn)中，貪心交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率為2.7%。而部分匹配交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率高達(dá)7%。從而可以得到交叉算子對(duì)于遺傳算法的計(jì)算效率和計(jì)算結(jié)果起主導(dǎo)性作用3。 圖1  遺傳算法的收斂過程2.4  并行遺傳算法消息傳遞實(shí)現(xiàn)的核心代碼    &#

15、160;1)主程序代碼/接收各個(gè)從程序的最優(yōu)個(gè)體for(i=0；i<slave；i+)MPI_Recv(Rchromi，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；/計(jì)算接收各個(gè)從程序的最優(yōu)個(gè)體的回路距離for(i=0；i<slave；i+)        fitnessi=0.0；        for(int j=0；j&l

16、t;chrom-1；j+)        fitnessi=fitnessi+distanceRchromijRchrom ij+1；        fitnessi=fitnessi+distanceRchromi0Rchrom ichrom-1；            /找到最優(yōu)的個(gè)體并把它記錄

17、到文件里        for(i=0；i<slave；i+)                    if(1/fitnessi>min)              &

18、#160;              sign=i；                 min=1/fitnessi；              

19、60;             fwrite(&gen，sizeof(int)，1，out)；        for(i=0；i<chrom；i+)        fwrite(&Rchromsigni，sizeof(unsigned)，1，out)；   

20、     fwrite(&fitnesssign，sizeof(double)，1，out)；        /每九代向從程序發(fā)送一個(gè)最優(yōu)個(gè)體        if(gen%9=0)        MPI_Bcast(Rchromsign，chrom，MPI_ UNSIGNED，0，MPI_C

21、OMM_WORLD)；    2)從程序代碼/將上一代的最優(yōu)個(gè)體傳回主程序MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；/每九代接收一個(gè)最優(yōu)個(gè)體并將其加入種群中替換掉最差個(gè)體if(gen%9=0)    PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；    Tsp.IndiAlternate(Rchrom2)；/進(jìn)行下一代的計(jì)算Tsp.Atern

22、ate()；Tsp.Generation()；     Tsp.Statistics()；             3)并行遺傳算法的性能    筆者在MPI并行環(huán)境下，用C語言實(shí)現(xiàn)了一個(gè)解決TSP問題的粗粒度模型的并行遺傳算法。該程序采用的是主從式的MPI程序設(shè)計(jì)，通過從硬盤的文件中讀取數(shù)據(jù)來設(shè)置染色體長(zhǎng)度、種群的規(guī)模、交叉概率和變異概率等參數(shù)。試驗(yàn)環(huán)境為曙光TC1700機(jī)，測(cè)試的對(duì)象是Oliver TSP問題的30個(gè)城市的TSP問題。    正如在測(cè)試串行遺傳算法所提到的數(shù)據(jù)結(jié)果，并行遺傳算法也沒有達(dá)到目前所記錄的最好解，但是它提高了算法的收斂性，并行遺傳算法的收斂趨勢(shì)如圖2所示4。 圖2  遺傳