關(guān)于一種基于基因庫和多重搜索策略求解TSP的遺傳算法

1、關(guān)于一種基于基因庫和多重搜索策略求解TSP的遺傳算法    論文關(guān)鍵詞：旅行商問題  遺傳算法  基因庫  多重搜索策略 論文摘要：TSP是組合優(yōu)化問題的典型代表,該文在分析了遺傳算法的特點(diǎn)后,提出了一種新的遺傳算法(GB?MGA),該算法將基因庫和多重搜索策略結(jié)合起來,利用基因庫指導(dǎo)單親遺傳演化的進(jìn)化方向,在多重搜索策略的基礎(chǔ)上利用改進(jìn)的交叉算子又增強(qiáng)了遺傳算法的全局搜索能力。通過對國際TSP庫中多個(gè)實(shí)例的測試,結(jié)果表明:算法(GB?MGA)加快了遺傳算法的收斂速度,也加強(qiáng)了算法的尋優(yōu)能力。 TSP(traveling s

2、alesman problem)可以簡述為:有n個(gè)城市1,2,n,一旅行商從某一城市出發(fā),環(huán)游所有城市后回到原出發(fā)地,且各城市只能經(jīng)過一次,要求找出一條最短路線。TSP的搜索空間是有限的,如果時(shí)間不受限制的話,在理論上這種問題終會(huì)找到最優(yōu)解,但對于稍大規(guī)模的TSP,時(shí)間上的代價(jià)往往是無法接受的。這是一個(gè)典型的組合最優(yōu)化問題,已被證明是NP難問題,即很可能不存在確定的算法能在多項(xiàng)式時(shí)間內(nèi)求到問題的解1。由于TSP在工程領(lǐng)域有著廣泛的應(yīng)用,如貨物運(yùn)輸、加工調(diào)度、網(wǎng)絡(luò)通訊、電氣布線、管道鋪設(shè)等,因而吸引了眾多領(lǐng)域的學(xué)者對它進(jìn)行研究。TSP的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法2、螞蟻算法

3、3、模擬退火算法、遺傳算法等。 遺傳算法是一種借鑒生物界自然選擇和遺傳機(jī)制的隨機(jī)化搜索算法,其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換,搜索不依賴于梯度信息4。遺傳算法主要包括選擇、交叉和變異3個(gè)操作算子,它是一種全局化搜索算法,尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問題。遺傳算法雖然不能保證在有限的時(shí)間內(nèi)獲得最優(yōu)解,但隨機(jī)地選擇充分多個(gè)解驗(yàn)證后,錯(cuò)誤的概率會(huì)降到可以接受的程度。 用遺傳算法求解TSP能得到令人滿意的結(jié)果,但是其收斂速度較慢,而且種群在交叉算子作用下,會(huì)陷入局部解。采用局部啟發(fā)式搜索算法等,雖然能在很短的時(shí)間內(nèi)計(jì)算出小規(guī)模城市的高質(zhì)量解,一旦城市規(guī)模稍大就容易陷入

4、局部最優(yōu)解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優(yōu)解,該文采納了文5中楊輝提出的基因庫的想法,并結(jié)合文6中Cheng-Fa Tsai提出的多重搜索策略思想,使用單親演化與群體演化相結(jié)合的方式來求解TSP問題。該文根據(jù)文7中最小生成樹MST(minimum cost spanning tree)的應(yīng)用,由MST建立TSP的基因庫,保存有希望成為最優(yōu)解的邊,利用基因庫提高初始群體的質(zhì)量進(jìn)行單親演化,然后利用改進(jìn)后的交叉算子和的多重搜索策略進(jìn)行群體演化。 1單親演化過程    現(xiàn)有的大多數(shù)演化算法在整個(gè)演化過程當(dāng)中所涉及的基因,大多來源于

5、個(gè)體本身,個(gè)體質(zhì)量的高低決定了算法的全局性能,如果群體中初始個(gè)體的適應(yīng)度都較差,肯定要影響算法的收斂速度,對于規(guī)模稍大的TSP尤其明顯8。該文為了克服上述弱點(diǎn),首先利用普里姆算法求出TSP中最小生成樹,并將各個(gè)MST中的每一條邊都保存在一個(gè)n*(n-1)方陣?yán)锩?就構(gòu)成了一個(gè)基因庫,在生成初始群體的時(shí)候盡量使用基因庫中的基因片段,來提高整個(gè)初始群體的適應(yīng)度,從而提高算法的效率。 1.1TSP編碼表示 設(shè)n個(gè)城市編號為1,2,n,為一條可行路徑,Pk=Vk1Vk2Vkn為一條可行路徑,它是1,2,n的一個(gè)隨機(jī)排列,其含意是第k條路徑起點(diǎn)城市是Vk1,最后一個(gè)城市是Vkn,則第k條環(huán)路的總長度可以

6、表示為: 其中,d(Vki,Vkj)表示城市Vki與城市Vkj之間的距離。在算法中環(huán)路Pk的總長d(Pk)用來評價(jià)個(gè)體的好壞9。適應(yīng)度函數(shù)取路徑長度d(Pk)的倒數(shù),f(Pk)=1/ d(Pk)。 1.2構(gòu)建TSP基因庫 對n個(gè)編號為1,2,n的城市,根據(jù)它們的坐標(biāo)計(jì)算各城市之間的歐氏距離d(i,j),i,j=1,2,n,得到一個(gè)n*n的方陣D= d(i,j)。然后利用普里姆算法求得該TSP的一棵MST,并將這棵MST中的每一條邊e(i,j)對應(yīng)地存儲在一個(gè)n*(n-1)的方陣M= e(i,j),即該文的基因庫。由于一個(gè)TSP可能有多棵MST,操作可以重復(fù)多次,這樣生成的基因庫中的基因就更多,

7、增強(qiáng)了初始群體的全局性。具體算法如下: Void MiniSpanTree?PRIM(MGraph G,VertexTypeu) Struct VertexType adjvex; VRType lowcost; closedgeMAX?VERTEX?NUM; k=LocateVex(G,u); for(j=0;j<G.vexnum;+j) if(j!=k)closedgej=u,G.arcskj.adj; closedgek.lowcost=0; for(i=0;i<G.vexnum;+i) k=minimum(closedge); printf(closedgek.adjvex

8、,G.vexsk); closedgek.lowcost=0; for(j=0;j<G.vexnum;+j) if(G.arcs kj.adj<closedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; 1.3單親演化算法 單親演化算法是利用遺傳算法的優(yōu)勝劣汰的遺傳特性,在單個(gè)染色體內(nèi)以基因重組的方式,使子代在滿足TSP問題的限定條件下進(jìn)行繁衍,然后保留適應(yīng)度高的染色體種群,達(dá)到優(yōu)化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯(cuò)位和基因段倒轉(zhuǎn)三種操作來實(shí)現(xiàn)?；驌Q位操作是將親代的染色體基因進(jìn)行對換后,形成子代,其換位又分為單基因換

9、位和基因段換位兩種方式?；蚨五e(cuò)位操作是隨機(jī)確定基因段,也隨機(jī)選定錯(cuò)位位置,整段錯(cuò)移?；蚨蔚罐D(zhuǎn)操作則是隨機(jī)地確定倒轉(zhuǎn)基因段的起止位置,倒轉(zhuǎn)操作是對該段內(nèi)基因按中垂線作鏡面反射,若段內(nèi)基因數(shù)為奇數(shù)時(shí),則中位基因不變。單親演化時(shí)可以是單個(gè)操作用于單個(gè)父代,也可以是幾種操作同時(shí)采用。為了編程方便,文中采用基因段倒轉(zhuǎn)操作。     2群體演化過程 在單親演化算法求得的初始群體基礎(chǔ)上,再利用多重搜索策略并行地進(jìn)行群體演化,這樣在保證算法的快速收斂的同時(shí)也注重了搜索空間的全局性。 2.1交叉算子 該文算子采用一種與順序交叉OX(order crossover)法類

10、似的交叉方法11,即隨機(jī)在串中選擇一個(gè)交配區(qū)域,例如以下兩個(gè)父串及交配區(qū)域選定為: P1=(12|3456|789)P2=(98|7654|321) 將P2的交配區(qū)域加到P1的前面或后面,P1的交配區(qū)域加到P2的前面或后面,得 M1=(7654|123456789) M2=(3456|987654321) 在M1中自交配區(qū)域后依次刪除與交配區(qū)域相同的城市碼,得到最終的兩個(gè)子串: S1=(765412389)S2=(345698721) 同時(shí)為了能更好地增強(qiáng)算子的全局搜索能力,對該算子作了如下的改進(jìn)。子代個(gè)體的新邊來自:隨機(jī)生成和群體中其他個(gè)體,其選擇比例由隨機(jī)數(shù)p和閾值P來決定。如果隨機(jī)數(shù)p小

11、于閾值P,則子代個(gè)體的新邊來自隨機(jī)生成,否則就來自群體中的其他個(gè)體。 這種改進(jìn)后的交叉算子在父串相同的情況下仍能產(chǎn)生一定程度的變異效果,這對維持群體的多樣化特性有一定的作用。實(shí)驗(yàn)結(jié)果也證實(shí)了這種改進(jìn)算子對于種群的全局搜索能力有一定的提高,避免搜索陷入局部解。 2.2局部啟發(fā)式算子 為了增強(qiáng)遺傳算法的局部搜索性能,在算法中引入2-Opt局部搜索算子12。該算子通過比較兩條邊并交換路徑以提升算法的局部搜索性能,示例見圖2。 比較子路徑ab+cd和ac+bd,如果ab+cd>ac+bd則交換,否則就不交換。考慮到程序的運(yùn)行效率,不可能對每對邊都做檢查,所以選取染色體中的一定數(shù)量的邊進(jìn)行比較。2

12、-Opt搜索算子實(shí)際上進(jìn)行的相當(dāng)于變異操作,同時(shí)又不僅僅是簡單的變異,而是提高算法的局部搜索性能的變異操作。 2.3選擇機(jī)制和收斂準(zhǔn)則 為了限制種群的規(guī)模13,該文采用了聯(lián)賽選擇法的淘汰規(guī)則。聯(lián)賽選擇法就是以各染色體的適應(yīng)度作為評定標(biāo)準(zhǔn),從群體中任意選擇一定數(shù)目的個(gè)體,稱為聯(lián)賽規(guī)模,其中適應(yīng)度最高的個(gè)體保存到下一代。這個(gè)過程反復(fù)執(zhí)行,直到保存到下一代的個(gè)體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)目為止。這樣做可能導(dǎo)致種群過早收斂,因此在收斂準(zhǔn)則上要采取苛刻的要求來保證搜索的全局性。 遺傳算法求TSP問題如果不設(shè)定終止條件,其演化過程將會(huì)無限制地進(jìn)行下去。終止條件也稱收斂準(zhǔn)則,因?yàn)槎鄶?shù)最優(yōu)化問題事先并不了解最優(yōu)的目標(biāo)

13、函數(shù)值,故無法判斷尋優(yōu)的精度。該文采用如下兩條收斂準(zhǔn)則:在連續(xù)K1代不再出現(xiàn)更優(yōu)的染色體;優(yōu)化解的染色體占種群的個(gè)數(shù)達(dá)K2的比例以上。當(dāng)兩準(zhǔn)則均滿足時(shí),則終止運(yùn)算,輸出優(yōu)化結(jié)果和對應(yīng)的目標(biāo)函數(shù)值。由數(shù)值實(shí)驗(yàn)表明,添加第2條準(zhǔn)則之后,全局最優(yōu)解的出現(xiàn)頻率將大為提高。    2.4基于多重搜索策略的群體演化算法 由于基因庫的引入,可能降低初始種群的多樣性,為避免算法陷入局部最優(yōu)解,因此在群體演化中采取多重搜索策略。由Cheng-Fa Tsai提出的多重搜索策略6,就是把染色體集中的染色體分成保守型和探索型兩種不同類型的集合,然后針對不同類型的染色體集合根據(jù)不

14、同的交叉、變異概率分別進(jìn)行交叉變異操作,對保守型染色體集合就采用比較低的交叉變異概率,而對探索型染色體集合就采用比較高的交叉變異概率。這種策略對保守型染色體集合的操作最大限度地保留了父代的優(yōu)秀基因片段,另一方面對探索型染色體集合的操作又盡可能地提高了算法的全局搜索能力。為了提高算法的收斂速度,初始染色體集合該文采用了前面單親演化的結(jié)果中的染色體集合,交叉算子則利用的是前面介紹的改進(jìn)后的算子,改進(jìn)后的多重搜索策略見下。 3實(shí)驗(yàn)結(jié)果與分析 該文的GB?MGA算法由C#編程實(shí)現(xiàn),所有的結(jié)果都是在P42.0G微機(jī)上完成,并進(jìn)行通用的TSP庫實(shí)驗(yàn),選用了具有一定代表性的TSP實(shí)例,并把該算法和其他算法做

15、了一個(gè)對比。為了減少計(jì)算量,程序中的數(shù)據(jù)經(jīng)過四舍五入整數(shù)化處理,與實(shí)數(shù)解有一定的偏差,下面給出圖Kroa100的示例。 為了證明該文提出的GB?MGA算法的有效性,將該文算法與典型的遺傳算法GA、單親遺傳算法PGA以及文5中楊輝提出的Ge?GA(gene pool genetic algorithm)算法和文12中提出的MMGA(modified multiple-searching genetic algorithm)算法都進(jìn)行了一個(gè)對比。 實(shí)驗(yàn)結(jié)果證明,該文算法的求解質(zhì)量要優(yōu)于GA、PGA、MMGA算法,而求解速度方面則優(yōu)于Ge?GA算法,特別是對于大規(guī)模城市的TSP問題求解效果尤其明顯,

16、具有快速收斂的特性。Ge?GA算法對于中等城市規(guī)模的TSP實(shí)例求解,其運(yùn)算時(shí)間就大幅度增加,如果把該算法用于求解大規(guī)模和超大規(guī)模TSP問題,那么時(shí)間上的代價(jià)就讓人無法忍受。而該文的GB?MGA算法在單親遺傳演化中就使用了基因庫中的優(yōu)質(zhì)基因,使得單個(gè)個(gè)體的進(jìn)化速度大大提高,從而為進(jìn)一步的演化提供了條件,群體演化過程的選擇機(jī)制和收斂準(zhǔn)則的恰當(dāng)選取使得算法在注重了求解質(zhì)量的同時(shí)兼顧了算法的效率。 結(jié)束語該文在對TSP問題進(jìn)行分析的基礎(chǔ)上,通過對全局最優(yōu)解和局部最優(yōu)解中的邊關(guān)系的分析發(fā)現(xiàn),通過最小生成樹的求解保存最有希望成為全局最優(yōu)解的邊,可以提高算法的效率,同時(shí)并不降低搜索的性能。在實(shí)驗(yàn)中發(fā)現(xiàn),通過

17、生成基因庫快速提高種群質(zhì)量,雖然可以快速收斂,但是TSP問題的求解質(zhì)量并沒有達(dá)到一個(gè)可以接受的程度,因此在群體演化階段中又加入了2-Opt局部搜索算子和多重搜索策略,對不同類型的染色體以不同幾率進(jìn)行選擇交叉操作。    用該算法測試TSP庫中的典型實(shí)例,結(jié)果顯示,對初始種群運(yùn)用單親遺傳算法,并引入基因庫方法是可行的,有效地提高了算法的效率和收斂速度,在群體演化過程中引入多重搜索策略的方法,提高了算法的并行性和全局尋優(yōu)性能,即使在較少的尋優(yōu)步數(shù)也能得到適應(yīng)度不錯(cuò)的局部優(yōu)化解。GB-MGA算法在提高算法求解質(zhì)量的同時(shí)兼顧了算法的效率, 但是其中還有許多有待解

18、決的問題,比如如何構(gòu)建高質(zhì)量的基因庫,如何對現(xiàn)有基因庫進(jìn)行優(yōu)化和擴(kuò)充,以及算法中一些參數(shù)的選取問題等,這些方面,還需要進(jìn)一步的研究。 參考文獻(xiàn) 1 Bck T B,Hammel U,Schwefel H P.Evolutionary computation:Comments on the history and current state J. lEEE Transactions On Evolutionary Computation,1997,2(6):317 2王磊,潘進(jìn),焦李成.免疫算法J.電子學(xué)報(bào),2000,28(7):7478 3 Dorigo M,Gambardella L M.A

19、nt Colony System:A CooperativeLearning Approach to the Traveling Salesman Problem J. IEEETransactions on Evolutionary Computation,1997,2(8):5366 4 Holland J H. Adaptation in Natural and Artificial Systems M.Ann Arbor:The University of Michigan,1975.1015 5楊輝,康立山,陳毓屏.一種基于構(gòu)建基因庫求解TSP問題的遺傳算法J.計(jì)算機(jī)學(xué)報(bào),2003,

20、26(12):17531758 6 Tsai Cheng-Fa, Tsai Chun-Wei, Yang Tzer. A Modified Multiple-Searching Method to Genetic Algorithms for Solving TravelingSalesman Problem J.IEEE Transactions on Systems,Man andCybernetics,2002,3(10):612 7 Baraglia R,Hidalgo J I, Perego R. A Hybrid Heuristic for theTraveling Salesman Problem J. IEEE Transactions on Evolutionary Computation,2001,5(12):613622 8 Tsai Cheng-Fa, Tsai Chun-Wei. A New Approach for SolvingLarge Traveling Salesman Problem Using Evolutionary Ant RulesC.In:Proc.of the 2002 Internation