1、關于一種基于基因庫和多重搜索策略求解TSP的遺傳算法    論文關鍵詞：旅行商問題  遺傳算法  基因庫  多重搜索策略論文摘要：TSP是組合優化問題的典型代表,該文在分析了遺傳算法的特點后,提出了一種新的遺傳算法(GBMGA),該算法將基因庫和多重搜索策略結合起來,利用基因庫指導單親遺傳演化的進化方向,在多重搜索策略的基礎上利用改進的交叉算子又增強了遺傳算法的全局搜索能力。通過對國際TSP庫中多個實例的測試,結果表明:算法(GBMGA)加快了遺傳算法的收斂速度,也加強了算法的尋優能力。TSP(traveling sales

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

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

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

5、體的適應度都較差,肯定要影響算法的收斂速度,對于規模稍大的TSP尤其明顯8。該文為了克服上述弱點,首先利用普里姆算法求出TSP中最小生成樹,并將各個MST中的每一條邊都保存在一個n*(n-1)方陣里面,就構成了一個基因庫,在生成初始群體的時候盡量使用基因庫中的基因片段,來提高整個初始群體的適應度,從而提高算法的效率。1.1TSP編碼表示設n個城市編號為1,2,n,為一條可行路徑,Pk=Vk1Vk2Vkn為一條可行路徑,它是1,2,n的一個隨機排列,其含意是第k條路徑起點城市是Vk1,最后一個城市是Vkn,則第k條環路的總長度可以表示為:其中,d(Vki,Vkj)表示城市Vki與城市Vkj之間的

6、距離。在算法中環路Pk的總長d(Pk)用來評價個體的好壞9。適應度函數取路徑長度d(Pk)的倒數,f(Pk)=1/ d(Pk)。1.2構建TSP基因庫對n個編號為1,2,n的城市,根據它們的坐標計算各城市之間的歐氏距離d(i,j),i,j=1,2,n,得到一個n*n的方陣D= d(i,j)。然后利用普里姆算法求得該TSP的一棵MST,并將這棵MST中的每一條邊e(i,j)對應地存儲在一個n*(n-1)的方陣M= e(i,j),即該文的基因庫。由于一個TSP可能有多棵MST,操作可以重復多次,這樣生成的基因庫中的基因就更多,增強了初始群體的全局性。具體算法如下:Void MiniSpanTree

7、PRIM(MGraph G,VertexTypeu)Struct VertexType adjvex;VRType lowcost;closedgeMAXVERTEXNUM;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,G.vexsk);closedgek.lowcost=0;for(j=0;j<G.vexnu

8、m;+j)if(G.arcs kj.adj<closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;1.3單親演化算法單親演化算法是利用遺傳算法的優勝劣汰的遺傳特性,在單個染色體內以基因重組的方式,使子代在滿足TSP問題的限定條件下進行繁衍,然后保留適應度高的染色體種群,達到優化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯位和基因段倒轉三種操作來實現。基因換位操作是將親代的染色體基因進行對換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式。基因段錯位操作是隨機確定基因段,也隨機選定錯位位置,整段錯移。基因段倒轉操作則是隨機地確

9、定倒轉基因段的起止位置,倒轉操作是對該段內基因按中垂線作鏡面反射,若段內基因數為奇數時,則中位基因不變。單親演化時可以是單個操作用于單個父代,也可以是幾種操作同時采用。為了編程方便,文中采用基因段倒轉操作。2群體演化過程在單親演化算法求得的初始群體基礎上,再利用多重搜索策略并行地進行群體演化,這樣在保證算法的快速收斂的同時也注重了搜索空間的全局性。2.1交叉算子該文算子采用一種與順序交叉OX(order crossover)法類似的交叉方法11,即隨機在串中選擇一個交配區域,例如以下兩個父串及交配區域選定為:P1=(12|3456|789)P2=(98|7654|321)將P2的交配區域加到P

10、1的前面或后面,P1的交配區域加到P2的前面或后面,得M1=(7654|123456789)M2=(3456|987654321)在M1中自交配區域后依次刪除與交配區域相同的城市碼,得到最終的兩個子串:S1=(765412389)S2=(345698721)同時為了能更好地增強算子的全局搜索能力,對該算子作了如下的改進。子代個體的新邊來自:隨機生成和群體中其他個體,其選擇比例由隨機數p和閾值P來決定。如果隨機數p小于閾值P,則子代個體的新邊來自隨機生成,否則就來自群體中的其他個體。這種改進后的交叉算子在父串相同的情況下仍能產生一定程度的變異效果,這對維持群體的多樣化特性有一定的作用。實驗結果也

11、證實了這種改進算子對于種群的全局搜索能力有一定的提高,避免搜索陷入局部解。2.2局部啟發式算子為了增強遺傳算法的局部搜索性能,在算法中引入2-Opt局部搜索算子12。該算子通過比較兩條邊并交換路徑以提升算法的局部搜索性能,示例見圖2。比較子路徑ab+cd和ac+bd,如果ab+cd>ac+bd則交換,否則就不交換。考慮到程序的運行效率,不可能對每對邊都做檢查,所以選取染色體中的一定數量的邊進行比較。2-Opt搜索算子實際上進行的相當于變異操作,同時又不僅僅是簡單的變異,而是提高算法的局部搜索性能的變異操作。2.3選擇機制和收斂準則為了限制種群的規模13,該文采用了聯賽選擇法的淘汰規則。聯

12、賽選擇法就是以各染色體的適應度作為評定標準,從群體中任意選擇一定數目的個體,稱為聯賽規模,其中適應度最高的個體保存到下一代。這個過程反復執行,直到保存到下一代的個體數達到預先設定的數目為止。這樣做可能導致種群過早收斂,因此在收斂準則上要采取苛刻的要求來保證搜索的全局性。遺傳算法求TSP問題如果不設定終止條件,其演化過程將會無限制地進行下去。終止條件也稱收斂準則,因為多數最優化問題事先并不了解最優的目標函數值,故無法判斷尋優的精度。該文采用如下兩條收斂準則:在連續K1代不再出現更優的染色體;優化解的染色體占種群的個數達K2的比例以上。當兩準則均滿足時,則終止運算,輸出優化結果和對應的目標函數值。

13、由數值實驗表明,添加第2條準則之后,全局最優解的出現頻率將大為提高。2.4基于多重搜索策略的群體演化算法 由于基因庫的引入,可能降低初始種群的多樣性,為避免算法陷入局部最優解,因此在群體演化中采取多重搜索策略。由Cheng-Fa Tsai提出的多重搜索策略6,就是把染色體集中的染色體分成保守型和探索型兩種不同類型的集合,然后針對不同類型的染色體集合根據不同的交叉、變異概率分別進行交叉變異操作,對保守型染色體集合就采用比較低的交叉變異概率,而對探索型染色體集合就采用比較高的交叉變異概率。這種策略對保守型染色體集合的操作最大限度地保留了父代的優秀基因片段,另一方面對探索型染色體集合的操作又盡可能地

14、提高了算法的全局搜索能力。為了提高算法的收斂速度,初始染色體集合該文采用了前面單親演化的結果中的染色體集合,交叉算子則利用的是前面介紹的改進后的算子,改進后的多重搜索策略見下。3實驗結果與分析該文的GBMGA算法由C#編程實現,所有的結果都是在P42.0G微機上完成,并進行通用的TSP庫實驗,選用了具有一定代表性的TSP實例,并把該算法和其他算法做了一個對比。為了減少計算量,程序中的數據經過四舍五入整數化處理,與實數解有一定的偏差,下面給出圖Kroa100的示例。為了證明該文提出的GBMGA算法的有效性,將該文算法與典型的遺傳算法GA、單親遺傳算法PGA以及文5中楊輝提出的GeGA(gene

15、pool genetic algorithm)算法和文12中提出的MMGA(modified multiple-searching genetic algorithm)算法都進行了一個對比。實驗結果證明,該文算法的求解質量要優于GA、PGA、MMGA算法,而求解速度方面則優于GeGA算法,特別是對于大規模城市的TSP問題求解效果尤其明顯,具有快速收斂的特性。GeGA算法對于中等城市規模的TSP實例求解,其運算時間就大幅度增加,如果把該算法用于求解大規模和超大規模TSP問題,那么時間上的代價就讓人無法忍受。而該文的GBMGA算法在單親遺傳演化中就使用了基因庫中的優質基因,使得單個個體的進化速度大

16、大提高,從而為進一步的演化提供了條件,群體演化過程的選擇機制和收斂準則的恰當選取使得算法在注重了求解質量的同時兼顧了算法的效率。結束語該文在對TSP問題進行分析的基礎上,通過對全局最優解和局部最優解中的邊關系的分析發現,通過最小生成樹的求解保存最有希望成為全局最優解的邊,可以提高算法的效率,同時并不降低搜索的性能。在實驗中發現,通過生成基因庫快速提高種群質量,雖然可以快速收斂,但是TSP問題的求解質量并沒有達到一個可以接受的程度,因此在群體演化階段中又加入了2-Opt局部搜索算子和多重搜索策略,對不同類型的染色體以不同幾率進行選擇交叉操作。用該算法測試TSP庫中的典型實例,結果顯示,對初始種群

17、運用單親遺傳算法,并引入基因庫方法是可行的,有效地提高了算法的效率和收斂速度,在群體演化過程中引入多重搜索策略的方法,提高了算法的并行性和全局尋優性能,即使在較少的尋優步數也能得到適應度不錯的局部優化解。GB-MGA算法在提高算法求解質量的同時兼顧了算法的效率, 但是其中還有許多有待解決的問題,比如如何構建高質量的基因庫,如何對現有基因庫進行優化和擴充,以及算法中一些參數的選取問題等,這些方面,還需要進一步的研究。參考文獻1 Bck T B,Hammel U,Schwefel H P.Evolutionary computation:Comments on the history and cu

18、rrent state J. lEEE Transactions On Evolutionary Computation,1997,2(6):3172王磊,潘進,焦李成.免疫算法J.電子學報,2000,28(7):74783 Dorigo M,Gambardella L M.Ant Colony System:A CooperativeLearning Approach to the Traveling Salesman Problem J. IEEETransactions on Evolutionary Computation,1997,2(8):53664 Holland J H. Ad

19、aptation in Natural and Artificial Systems M.Ann Arbor:The University of Michigan,1975.10155楊輝,康立山,陳毓屏.一種基于構建基因庫求解TSP問題的遺傳算法J.計算機學報,2003,26(12):175317586 Tsai Cheng-Fa, Tsai Chun-Wei, Yang Tzer. A Modified Multiple-Searching Method to Genetic Algorithms for Solving TravelingSalesman Problem J.IEEE T

20、ransactions on Systems,Man andCybernetics,2002,3(10):6127 Baraglia R,Hidalgo J I, Perego R. A Hybrid Heuristic for theTraveling Salesman Problem J. IEEE Transactions on Evolutionary Computation,2001,5(12):6136228 Tsai Cheng-Fa, Tsai Chun-Wei. A New Approach for SolvingLarge Traveling Salesman Problem Using Evolutionary Ant RulesC.In:Proc.of the 2002 International Joint Conf.on Neural Networks,Hawaiian:honolulu,20029 Jung S,Moon B R.Toward Minimal Restriction of Genetic