統(tǒng)計學(xué)論文-關(guān)于一種基于基因庫和多重搜索策略求解TSP的遺傳算法.doc

統(tǒng)計學(xué)論文-關(guān)于一種基于基因庫和多重搜索策略求解TSP的遺傳算法論文關(guān)鍵詞：旅行商問題遺傳算法基因庫多重搜索策略論文摘要：TSP是組合優(yōu)化問題的典型代表,該文在分析了遺傳算法的特點后,提出了一種新的遺傳算法(GBMGA),該算法將基因庫和多重搜索策略結(jié)合起來,利用基因庫指導(dǎo)單親遺傳演化的進化方向,在多重搜索策略的基礎(chǔ)上利用改進的交叉算子又增強了遺傳算法的全局搜索能力。通過對國際TSP庫中多個實例的測試,結(jié)果表明:算法(GBMGA)加快了遺傳算法的收斂速度,也加強了算法的尋優(yōu)能力。TSP(travelingsalesmanproblem)可以簡述為:有n個城市1,2,n,一旅行商從某一城市出發(fā),環(huán)游所有城市后回到原出發(fā)地,且各城市只能經(jīng)過一次,要求找出一條最短路線。TSP的搜索空間是有限的,如果時間不受限制的話,在理論上這種問題終會找到最優(yōu)解,但對于稍大規(guī)模的TSP,時間上的代價往往是無法接受的。這是一個典型的組合最優(yōu)化問題,已被證明是NP難問題,即很可能不存在確定的算法能在多項式時間內(nèi)求到問題的解1。由于TSP在工程領(lǐng)域有著廣泛的應(yīng)用,如貨物運輸、加工調(diào)度、網(wǎng)絡(luò)通訊、電氣布線、管道鋪設(shè)等,因而吸引了眾多領(lǐng)域的學(xué)者對它進行研究。TSP的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法2、螞蟻算法3、模擬退火算法、遺傳算法等。遺傳算法是一種借鑒生物界自然選擇和遺傳機制的隨機化搜索算法,其主要特點是群體搜索策略和群體中個體之間的信息交換,搜索不依賴于梯度信息4。遺傳算法主要包括選擇、交叉和變異3個操作算子,它是一種全局化搜索算法,尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問題。遺傳算法雖然不能保證在有限的時間內(nèi)獲得最優(yōu)解,但隨機地選擇充分多個解驗證后,錯誤的概率會降到可以接受的程度。用遺傳算法求解TSP能得到令人滿意的結(jié)果,但是其收斂速度較慢,而且種群在交叉算子作用下,會陷入局部解。采用局部啟發(fā)式搜索算法等,雖然能在很短的時間內(nèi)計算出小規(guī)模城市的高質(zhì)量解,一旦城市規(guī)模稍大就容易陷入局部最優(yōu)解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優(yōu)解,該文采納了文5中楊輝提出的基因庫的想法,并結(jié)合文6中Cheng-FaTsai提出的多重搜索策略思想,使用單親演化與群體演化相結(jié)合的方式來求解TSP問題。該文根據(jù)文7中最小生成樹MST(minimumcostspanningtree)的應(yīng)用,由MST建立TSP的基因庫,保存有希望成為最優(yōu)解的邊,利用基因庫提高初始群體的質(zhì)量進行單親演化,然后利用改進后的交叉算子和的多重搜索策略進行群體演化。1單親演化過程現(xiàn)有的大多數(shù)演化算法在整個演化過程中所涉及的基因,大多來源于個體本身,個體質(zhì)量的高低決定了算法的全局性能,如果群體中初始個體的適應(yīng)度都較差,肯定要影響算法的收斂速度,對于規(guī)模稍大的TSP尤其明顯8。該文為了克服上述弱點,首先利用普里姆算法求出TSP中最小生成樹,并將各個MST中的每一條邊都保存在一個n*(n-1)方陣里面,就構(gòu)成了一個基因庫,在生成初始群體的時候盡量使用基因庫中的基因片段,來提高整個初始群體的適應(yīng)度,從而提高算法的效率。1.1TSP編碼表示設(shè)n個城市編號為1,2,n,為一條可行路徑,Pk=Vk1Vk2Vkn為一條可行路徑,它是1,2,n的一個隨機排列,其含意是第k條路徑起點城市是Vk1,最后一個城市是Vkn,則第k條環(huán)路的總長度可以表示為:其中,d(Vki,Vkj)表示城市Vki與城市Vkj之間的距離。在算法中環(huán)路Pk的總長d(Pk)用來評價個體的好壞9。適應(yīng)度函數(shù)取路徑長度d(Pk)的倒數(shù),f(Pk)=1/d(Pk)。1.2構(gòu)建TSP基因庫對n個編號為1,2,n的城市,根據(jù)它們的坐標計算各城市之間的歐氏距離d(i,j),i,j=1,2,n,得到一個n*n的方陣D=d(i,j)。然后利用普里姆算法求得該TSP的一棵MST,并將這棵MST中的每一條邊e(i,j)對應(yīng)地存儲在一個n*(n-1)的方陣M=e(i,j),即該文的基因庫。由于一個TSP可能有多棵MST,操作可以重復(fù)多次,這樣生成的基因庫中的基因就更多,增強了初始群體的全局性。具體算法如下:VoidMiniSpanTreePRIM(MGraphG,VertexTypeu)StructVertexTypeadjvex；VRTypelowcost；closedgeMAXVERTEXNUM；k=LocateVex(G,u)；for(j=0；jG.vexnum；+j)if(j!=k)closedgej=u,G.arcskj.adj；closedgek.lowcost=0；for(i=0；iG.vexnum；+i)k=minimum(closedge)；printf(closedgek.adjvex,G.vexsk)；closedgek.lowcost=0；for(j=0；jG.vexnum；+j)if(G.arcskj.adjac+bd則交換,否則就不交換?？紤]到程序的運行效率,不可能對每對邊都做檢查,所以選取染色體中的一定數(shù)量的邊進行比較。2-Opt搜索算子實際上進行的相當于變異操作,同時又不僅僅是簡單的變異,而是提高算法的局部搜索性能的變異操作。2.3選擇機制和收斂準則為了限制種群的規(guī)模13,該文采用了聯(lián)賽選擇法的淘汰規(guī)則。聯(lián)賽選擇法就是以各染色體的適應(yīng)度作為評定標準,從群體中任意選擇一定數(shù)目的個體,稱為聯(lián)賽規(guī)模,其中適應(yīng)度最高的個體保存到下一代。這個過程反復(fù)執(zhí)行,直到保存到下一代的個體數(shù)達到預(yù)先設(shè)定的數(shù)目為止。這樣做可能導(dǎo)致種群過早收斂,因此在收斂準則上要采取苛刻的要求來保證搜索的全局性。遺傳算法求TSP問題如果不設(shè)定終止條件,其演化過程將會無限制地進行下去。終止條件也稱收斂準則,因為多數(shù)最優(yōu)化問題事先并不了解最優(yōu)的目標函數(shù)值,故無法判斷尋優(yōu)的精度。該文采用如下兩條收斂準則:在連續(xù)K1代不再出現(xiàn)更優(yōu)的染色體；優(yōu)化解的染色體占種群的個數(shù)達K2的比例以上。當兩準則均滿足時,則終止運算,輸出優(yōu)化結(jié)果和對應(yīng)的目標函數(shù)值。由數(shù)值實驗表明,添加第2條準則之后,全局最優(yōu)解的出現(xiàn)頻率將大為提高。2.4基于多重搜索策略的群體演化算法由于基因庫的引入,可能降低初始種群的多樣性,為避免算法陷入局部最優(yōu)解,因此在群體演化中采取多重搜索策略。由Cheng-FaTsai提出的多重搜索策略6,就是把染色體集中的染色體分成保守型和探索型兩種不同類型的集合,然后針對不同類型的染色體集合根據(jù)不同的交叉、變異概率分別進行交叉變異操作,對保守型染色體集合就采用比較低的交叉變異概率,而對探索型染色體集合就采用比較高的交叉變異概率。這種策略對保守型染色體集合的操作最大限度地保留了父代的優(yōu)秀基因片段,另一方面對探索型染色體集合的操作又盡可能地提高了算法的全局搜索能力。為了提高算法的收斂速度,初始染色體集合該文采用了前面單親演化的結(jié)果中的染色體集合,交叉算子則利用的是前面介紹的改進后的算子,改進后的多重搜索策略見下。3實驗結(jié)果與分析該文的GBMGA算法由C#編程實現(xiàn),所有的結(jié)果都是在P42.0G微機上完成,并進行通用的TSP庫實驗,選用了具有一定代表性的TSP實例,并把該算法和其他算法做了一個對比。為了減少計算量,程序中的數(shù)據(jù)經(jīng)過四舍五入整數(shù)化處理,與實數(shù)解有一定的偏差,下面給出圖Kroa100的示例。為了證明該文提出的GBMGA算法的有效性,將該文算法與典型的遺傳算法GA、單親遺傳算法PGA以及文5中楊輝提出的GeGA(genepoolgeneticalgorithm)算法和文12中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都進行了一個對比。實驗結(jié)果證明,該文算法的求解質(zhì)量要優(yōu)于GA、PGA、MMGA算法,而求解速度方面則優(yōu)于GeGA算法,特別是對于大規(guī)模城市的TSP問題求解效果尤其明顯,具有快速收斂的特性。GeGA算法對于中等城市規(guī)模的TSP實例求解,其運算時間就大幅度增加,如果把該算法用于求解大規(guī)模和超大規(guī)模TSP問題,那么時間上的代價就讓人無法忍受。而該文的GBMGA算法在單親遺傳演化中就使用了基因庫中的優(yōu)質(zhì)基因,使得單個個體的進化速度大大提高,從而為進一步的演化提供了條件,群體演化過程的選擇機制和收斂準則的恰當選取使得算法在注重了求解質(zhì)量的同時兼顧了算法的效率。結(jié)束語該文在對TSP問題進行分析的基礎(chǔ)上,通過對全局最優(yōu)解和局部最優(yōu)解中的邊關(guān)系的分析發(fā)現(xiàn),通過最小生成樹的求解保存最有希望成為全局最優(yōu)解的邊,可以提高算法的效率,同時并不降低搜索的性能。在實驗中發(fā)現(xiàn),通過生成基因庫快速提高種群質(zhì)量,雖然可以快速收斂,但是TSP問題的求解質(zhì)量并沒有達到一個可以接受的程度,因此在群體演化階段中又加入了2-Opt局部搜索算子和多重搜索策略,對不同類型的染色體以不同幾率進行選擇交叉操作。用該算法測試TSP庫中的典型實例,結(jié)果顯示,對初始種群運用單親遺傳算法,并引入基因庫方法