導(dǎo)語(yǔ)：遺傳算法程序設(shè)計(jì)研究論文一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要本文通過(guò)對(duì)基本遺傳算法添加初始化啟發(fā)信息、改進(jìn)交叉算子和利用本身所固有的并行性構(gòu)架粗粒度并行遺傳算法等方法提高了遺傳算法的收斂性及其尋優(yōu)能力。

關(guān)鍵詞遺傳算法；TSP；交叉算子

1引言

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法?？偟恼f(shuō)來(lái)，遺傳算法是按不依賴于問(wèn)題本身的方式去求解問(wèn)題。它的目標(biāo)是搜索這個(gè)多維、高度非線性空間以找到具有最優(yōu)適應(yīng)值(即最小費(fèi)用的)的點(diǎn)[1]。

基本遺傳算法是一個(gè)迭代過(guò)程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，反復(fù)將選擇算子、交叉算子和變異算子作用于種群，最終可得到問(wèn)題的最優(yōu)解和近似最優(yōu)解。

2遺傳算法程序設(shè)計(jì)改進(jìn)比較

2.1基本遺傳算法對(duì)TSP問(wèn)題解的影響

本文研究的遺傳算法及改進(jìn)算法的實(shí)現(xiàn)是以C++語(yǔ)言為基礎(chǔ)，在Windows2000的版本上運(yùn)行，其實(shí)現(xiàn)程序是在MicrosoftVisualStadio6.0上編寫及運(yùn)行調(diào)試的。

1)遺傳算法的執(zhí)行代碼

m_Tsp.Initpop()；//種群的初始化

for(inti=0；i<m_Tsp.ReturnPop()；i++)

m_Tsp.calculatefitness(i)；//計(jì)算各個(gè)個(gè)體的適應(yīng)值

m_Tsp.statistics()；//統(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ì)舊種群進(jìn)行遺傳操作，產(chǎn)生新種群

m_Tsp.m_gen++；

m_Tsp.statistics()；//對(duì)新產(chǎn)生的種群進(jìn)行統(tǒng)計(jì)

}

2)簡(jiǎn)單的遺傳算法與分支定界法對(duì)TSP問(wèn)題求解結(jié)果的對(duì)比

遺傳算法在解決NPC問(wèn)題的領(lǐng)域內(nèi)具有尋找最優(yōu)解的能力。但隨著城市個(gè)數(shù)的增加，已沒(méi)有精確解，無(wú)法確定遺傳算法求解的精度有多高。一般情況下，當(dāng)?shù)鷶?shù)增大時(shí)，解的精度可能高，但是時(shí)間開(kāi)銷也會(huì)增大。因此可以通過(guò)改進(jìn)遺傳算法來(lái)提高搜索能力，提高解的精度。

2.2初始化時(shí)的啟發(fā)信息對(duì)TSP問(wèn)題解的影響

1)初始化啟發(fā)信息

在上述實(shí)驗(yàn)算法的基礎(chǔ)上，對(duì)每一個(gè)初始化的個(gè)體的每五個(gè)相鄰城市用分支界定法尋找最優(yōu)子路徑，然后執(zhí)行遺傳算法。

2)遺傳算法與含有啟發(fā)信息的遺傳算法求解結(jié)果的對(duì)比

當(dāng)城市數(shù)增至20個(gè)時(shí)，用分支定界法已經(jīng)不可能在可以接受的時(shí)間內(nèi)得到精確的解了，只能通過(guò)近似算法獲得其可接受的解。試驗(yàn)設(shè)計(jì)中算法的截止條件：固定迭代1000代。表2中的平均最優(yōu)解為經(jīng)過(guò)多次試驗(yàn)(10次以上)得到的最優(yōu)解的平均值，最優(yōu)解的出現(xiàn)時(shí)間為最優(yōu)解出現(xiàn)的平均時(shí)間，交叉操作次數(shù)為最優(yōu)解出現(xiàn)時(shí)交叉次數(shù)的平均值。

表220個(gè)城市的TSP問(wèn)題求解結(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í)間和問(wèn)題的求解精度。

2.3交叉算子對(duì)TSP問(wèn)題解的影響

1)循環(huán)貪心交叉算子的核心代碼

for(i=1；i<m_Chrom；i++)

{

flag=0；

city=m_newpop[first].chrom[i-1]；//確定當(dāng)前城市

j=0；

while(flag==0&&j<4)

{

sign=adjcity[city][j]；//adjcity數(shù)組的數(shù)據(jù)為當(dāng)前城市按順序排列的鄰接城市

flag=judge(first，i，sign)；//判斷此鄰接城市是否已經(jīng)存在待形成的個(gè)體中

j++；

}

if(flag==0)//如果所有鄰接城市皆在待擴(kuò)展的個(gè)體中

{

while(flag==0)

{

sign=(int)rand()/(RAND_MAX/(m_Chrom-1))；//隨機(jī)選擇一城市

flag=judge(first，i，sign)；

}

}

if(flag==1)

m_newpop[first].chrom[i]=sign；

}

2)問(wèn)題描述與結(jié)果比較

下面筆者用經(jīng)典的測(cè)試遺傳算法效率的OliverTSP問(wèn)題來(lái)測(cè)試循環(huán)貪心交叉算子的解的精度和解效率。OliverTSP問(wèn)題的30個(gè)城市位置坐標(biāo)如表3所示[2]。

從表4、圖1中可以看到，貪心交叉算子大大提高了遺傳算法的尋優(yōu)能力，同時(shí)也降低了交叉操作次數(shù)。在多次試驗(yàn)中，貪心交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率為2.7%。而部分匹配交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率高達(dá)7%。從而可以得到交叉算子對(duì)于遺傳算法

2.4并行遺傳算法消息傳遞實(shí)現(xiàn)的核心代碼

1)主程序代碼

//接收各個(gè)從程序的最優(yōu)個(gè)體

for(i=0；i<slave；i++)

{

MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；

}

//計(jì)算接收各個(gè)從程序的最優(yōu)個(gè)體的回路距離

for(i=0；i<slave；i++)

{

fitness[i]=0.0；

for(intj=0；j<chrom-1；j++)

fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom[i][j+1]]；

fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom[i][chrom-1]]；

}

//找到最優(yōu)的個(gè)體并把它記錄到文件里

for(i=0；i<slave；i++)

{

if(1/fitness[i]>min)

{

sign=i；

min=1/fitness[i]；

}

}

fwrite(&gen，sizeof(int)，1，out)；

for(i=0；i<chrom；i++)

fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；

fwrite(&fitness[sign]，sizeof(double)，1，out)；

//每九代向從程序發(fā)送一個(gè)最優(yōu)個(gè)體

if(gen%9==0)

MPI_Bcast(Rchrom[sign]，chrom，MPI_UNSIGNED，0，MPI_COMM_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.Aternate()；

Tsp.Generation()；

Tsp.Statistics()；

3)并行遺傳算法的性能

筆者在MPI并行環(huán)境下，用C＋＋語(yǔ)言實(shí)現(xiàn)了一個(gè)解決TSP問(wèn)題的粗粒度模型的并行遺傳算法。該程序采用的是主從式的MPI程序設(shè)計(jì)，通過(guò)從硬盤的文件中讀取數(shù)據(jù)來(lái)設(shè)置染色體長(zhǎng)度、種群的規(guī)模、交叉概率和變異概率等參數(shù)。試驗(yàn)環(huán)境為曙光TC1700機(jī)，測(cè)試的對(duì)象是OliverTSP問(wèn)題的30個(gè)城市的TSP問(wèn)題。

正如在測(cè)試串行遺傳算法所提到的數(shù)據(jù)結(jié)果，并行遺傳算法也沒(méi)有達(dá)到目前所記錄的最好解，但是它提高了算法的收斂性，并行遺傳算法的收斂趨勢(shì)如圖2所示[4]。

圖2遺傳算法的收斂過(guò)程

3結(jié)束語(yǔ)

本文通過(guò)對(duì)基本遺傳算法的不斷改進(jìn)，證明了添加啟發(fā)信息、改進(jìn)遺傳算子和利用遺傳算法固有的并行性都可以提高遺傳算法的收斂性，其中對(duì)遺傳算法交叉算子的改進(jìn)可以大大提高遺傳算法的尋優(yōu)能力。

參考文獻(xiàn)

[1]劉勇、康立山，陳毓屏著．非數(shù)值并行算法－遺傳算法．北京：科學(xué)出版社1995.1

[2]IMOliverDJSmithandJRCHolland，Astudyofpermutationcrossoveroperatorsonthetravelingsalesman[C]//ProblemofthesecondInternationalConferenceonGeneticAlgorithmsandTheirApplication，Erlbaum1897：224-230

[3]于海斌，王浩波，徐心和．兩代競(jìng)爭(zhēng)遺傳算法及其應(yīng)用研究．信息與控制，2000Vol.29，No.4：309-314

[4]穆艷玲，李學(xué)武，高潤(rùn)泉．遺傳算法解TSP問(wèn)題的并行實(shí)現(xiàn)．北京聯(lián)合大學(xué)學(xué)報(bào)(自然科學(xué)版)，2006Vol.20No.2：40-43