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

1、入黨積極分子思想?yún)R報模板尊敬的黨組織：今天，我懷著無比激動鍵詞：旅行商問題 遺傳算 法基因庫多重搜索策略論文摘要：t sp是組合優(yōu)化問題的典型代表，該文在分 析了遺傳算法的特點(diǎn)后，提出了一種新的遺傳算法(gb mga )，該算法將基因庫和多重搜索策略結(jié)合起來，利用基因 庫指導(dǎo)單親遺傳演化的進(jìn)化方向，在多重搜索策略的基礎(chǔ)上 利用改進(jìn)的交叉算子又增強(qiáng)了遺傳算法的全局搜索能力。通 過對國際tsp庫中多個實(shí)例的測試，結(jié)果表明：算法(gbmga ) 加快了遺傳算法的收斂速度，也加強(qiáng)了算法的尋優(yōu)能力。tsp(trave lingsalesman problem)可以簡述為：有 n 個 城市1,2,n, 旅

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

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

4、遺傳算法的收斂速度，又能得到更 好的近似最優(yōu)解，該文采納了文5 中楊輝提出的基因庫的 想法，并結(jié)合文6中ch eng-fatsai提出的多重搜索策略思 想，使用單親演化與群體演化相結(jié)合的方式來求解tsp問題。 該文根據(jù)文7中最小 生成樹mst(minimu mcostspannin gtree)的應(yīng)用，由mst建立tsp的基因庫，保存有希望成為最 優(yōu)解的邊，利用基因庫提高初始群體的質(zhì)量進(jìn)行單親演化， 然后利用改進(jìn)后的交叉算子和的多重搜索策略進(jìn)行群體演 化。1單親演化過程現(xiàn)有的大多數(shù)演化算法在整個演化過程中所涉及的基因，大多來源于個體本身，個體質(zhì)量的髙低決定了算法的全 局性能，如果群體中初始個體

5、的適應(yīng)度都較差，肯定要影響 算法的收斂速度，對于規(guī)模稍大的tsp尤其明顯8。該文為 了克服上述弱點(diǎn)，首先利用普里姆算法求出tsp中最小生成 樹，并將各個mst中的每一條邊都保存在一個n*(n-l )方陣 里面，就構(gòu)成了一個基因庫，在生成初始群體的時候盡量使 用基因庫中的基因片段，來提高整個初始群體的適應(yīng)度，從 而提高算法的效率。tsp編碼表示設(shè)n個城市編號為1,2 ，n,為一條可行路 徑,pk=vklvk2-v kn為一條可行路徑，它是1,2,，n的一個 隨機(jī)排列，其含意是第k條路徑起點(diǎn)城市是vkl,最后一個城 市是vkn,則第k條環(huán)路的總長度可以表示為：其中,d(vki ,vkj)表示城市v

6、ki與城市vkj之間的距離。 在算法中環(huán)路pk的總長d(pk)用來評價個體的好壞9。適 應(yīng)度函數(shù)取路徑長度d (pk)的倒數(shù),f(pk)=l/d(pk)o構(gòu)建tsp基因庫對n個編號為1,2,n的城市，根據(jù)它們的坐標(biāo)計算各 城市之間的歐氏距離d(i, j), i, j=l,2,n,得到一個n*n的 方陣d=d(i, j)o然后利用普里姆算法求得該tsp的一棵mst, 并將這棵mst中的每一條邊e (i, j)對應(yīng)地存儲在一個 n*(n-1)的方陣m = e(i, j),即該文的基因庫。由于一個ts p可能有多棵mst,操作可以重復(fù)多次，這樣生成的基因庫中 的基因就更多，增強(qiáng)了初始群體的全局性。具

7、體算法如下：voidm inispantree一prim(mgraphg , vertextypeu ) struct v ertextypeadj vex；vrtypel owcost； clo sedge maxve rtexnum；k =locatevex(g,u)；for (j=0 ； jif (j!=k)cl osedgej = u , k j. adj； closedgek . lowcost二0；for (i=0； ik=m inimum(close dge)；printf (closedgekadjvex,k)；closedgek . lowcost二0；for (j=0； j

8、if (k j. adjc losedgej = k, k j. a dj;單親演化算法單親演化算法是利用遺傳算法的優(yōu)勝劣汰的遺傳特性,在單個染色體內(nèi)以基因重組的方式，使子代在滿足tsp問題 的限定條件下進(jìn)行繁衍，然后保留適應(yīng)度高的染色體種群， 達(dá)到優(yōu)化的目的。單親演化算法的基因重組操作包括基因換 位、基因段錯位和基因段倒轉(zhuǎn)三種操作來實(shí)現(xiàn)。基因換位操 作是將親代的染色體基因進(jìn)行對換后，形成子代，其換位又 分為單基因換位和基因段換位兩種方式?；蚨五e位操作是 隨機(jī)確定基因段，也隨機(jī)選定錯位位置，整段錯移?；蚨蔚?轉(zhuǎn)操作則是隨機(jī)地確定倒轉(zhuǎn)基因段的起止位置，倒轉(zhuǎn)操作是 對該段內(nèi)基因按中垂線作鏡面反

9、射，若段內(nèi)基因數(shù)為奇數(shù)時, 則中位基因不變。單親演化時可以是單個操作用于單個父代, 也可以是幾種操作同時采用。為了編程方便，文中采用基因 段倒轉(zhuǎn)操作。2群體演化過程在單親演化算法求得的初始群體基礎(chǔ)上，再利用多重搜 索策略并行地進(jìn)行群體演化，這樣在保證算法的快速收斂的 同時也注重了搜索空間的全局性。交叉算子該文算子采用一種與順序交叉ox(ordercrossov er)法 類似的交叉方法11,即隨機(jī)在串中選擇一個交配區(qū)域，例 如以下兩個父串及交配區(qū)域選定為：pl=(12|3456 |789)p2=(98|7654|321)將p2的交配區(qū)域加到p1的前面或后面,p1的交配區(qū)域加到p2的前面或后面，

10、得ml=(7654| 12 3456789)m2= (34561987654 321)在ml中自交配區(qū)域后依次刪除與交配區(qū)域相同的城市 碼，得到最終的兩個子串：sl=(76 5412389)s2= (345698721)同時為了能更好地增強(qiáng)算子的全局搜索能力，對該算子 作了如下的改進(jìn)。子代個體的新邊來自：隨機(jī)生成和群體中 其他個體,其選擇比例由隨機(jī)數(shù)p和閾值p來決定。如果隨 機(jī)數(shù)p小于閾值p,則子代個體的新邊來自隨機(jī)生成，否則就 來自群體中的其他個體。這種改進(jìn)后的交叉算子在父串相同的情況下仍能產(chǎn)生 一定程度的變異效果，這對維持群體的多樣化特性有一定的 作用。實(shí)驗(yàn)結(jié)果也證實(shí)了這種改進(jìn)算子對于種群

11、的全局搜索 能力有一定的提高，避免搜索陷入局部解。局部啟發(fā)式算子為了增強(qiáng)遺傳算法的局部搜索性能，在算法中引入2- opt局部搜索算子12。該算子通過比較兩條邊并交換路徑 以提升算法的局部搜索性能，示例見圖2。比較子路徑ab+cd和a c+bd,如果ab+cd >ac+bd則交換, 否則就不交換?？紤]到程序的運(yùn)行效率，不可能對每對邊都 做檢查，所以選取染色體中的一定數(shù)量的邊進(jìn)行比較。2-opt 搜索算子實(shí)際上進(jìn)行的相當(dāng)于變異操作，同時又不僅僅是簡 單的變異，而是提高算法的局部搜索性能的變異操作。選擇機(jī)制和收斂準(zhǔn)則為了限制種群的規(guī)模13,該文采用了聯(lián)賽選擇法的淘 汰規(guī)則。聯(lián)賽選擇法就是以各染

12、色體的適應(yīng)度作為評定標(biāo)準(zhǔn), 從群體中任意選擇一定數(shù)目的個體，稱為聯(lián)賽規(guī)模，其中適 應(yīng)度最高的個體保存到下一代。這個過程反復(fù)執(zhí)行，直到保 存到下一代的個體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)目為止。這樣做可能 導(dǎo)致種群過早收斂，因此在收斂準(zhǔn)則上要采取苛刻的要求來 保證搜索的全局性。遺傳算法求ts p問題如果不設(shè)定終止條件，其演化過程 將會無限制地進(jìn)行下去。終止條件也稱收斂準(zhǔn)則，因?yàn)槎鄶?shù) 最優(yōu)化問題事先并不了解最優(yōu)的目標(biāo)函數(shù)值，故無法判斷尋 優(yōu)的精度。該文采用如下兩條收斂準(zhǔn)則：在連續(xù)k1代不再出 現(xiàn)更優(yōu)的染色體;優(yōu)化解的染色體占種群的個數(shù)達(dá)k2的比例 以上。當(dāng)兩準(zhǔn)則均滿足時，則終止運(yùn)算，輸出優(yōu)化結(jié)果和對應(yīng) 的目標(biāo)函

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

14、的操作又盡可能地提 高了算法的全局搜索能力。為了提髙算法的收斂速度，初始 染色體集合該文采用了前面單親演化的結(jié)果中的染色體集 合，交叉算子則利用的是前面介紹的改進(jìn)后的算子，改進(jìn)后 的多重搜索策略見下。3實(shí)驗(yàn)結(jié)果與分析該文的gbmga算法由c#編程實(shí)現(xiàn)，所有的結(jié)果都是在 微機(jī)上完成，并進(jìn)行通用的tsp庫實(shí)驗(yàn)，選用了具有一定代表 性的tsp實(shí)例，并把該算法和其他算法做了一個對比。為了減 少計算量，程序中的數(shù)據(jù)經(jīng)過四舍五入整數(shù)化處理，與實(shí)數(shù) 解有一定的偏差，下面給出圖kroaloo的示例。為了證明該文提出的gbmga算法的有效性，將該文算 法與典型的遺傳算法ga、單親遺傳算法pga以及文5中楊 輝提

15、出的 gega (gen epoolgenetic algorithm)算法和文12 中提出的 mm ga (modi fi edm ultiplesear chinggenetic algorithm)算法都進(jìn)行了 一個對比。實(shí)驗(yàn)結(jié)果證明，該文算法的求解質(zhì)量要優(yōu)于ga、pga、 mmga算法，而求解速度方面則優(yōu)于ge-ga算法，特別是對于 大規(guī)模城市的tsp問題求解效果尤其明顯，具有快速收斂的 特性。gega算法對于中等城市規(guī)模的tsp實(shí)例求解，其運(yùn) 算時間就大幅度增加，如果把該算法用于求解大規(guī)模和超大 規(guī)模tsp問題，那么時間上的代價就讓人無法忍受。而該文 的gb-m ga算法在單親遺傳演

16、化中就使用了基因庫中的優(yōu)質(zhì) 基因，使得單個個體的進(jìn)化速度大大提高，從而為進(jìn)一步的 演化提供了條件,群體演化過程的選擇機(jī)制和收斂準(zhǔn)則的恰 當(dāng)選取使得算法在注重了求解質(zhì)量的同時兼顧了算法的效 率。結(jié)束語該文在對tsp問題進(jìn)行分析的基礎(chǔ)上，通過對全 局最優(yōu)解和局部最優(yōu)解中的邊關(guān)系的分析發(fā)現(xiàn)，通過最小生 成樹的求解保存最有希望成為全局最優(yōu)解的邊，可以提高算 法的效率，同時并不降低搜索的性能。在實(shí)驗(yàn)中發(fā)現(xiàn)，通過生 成基因庫快速提高種群質(zhì)量，雖然可以快速收斂，但是tsp問 題的求解質(zhì)量并沒有達(dá)到一個可以接受的程度，因此在群體 演化階段中又加入了 2-opt局部搜索算子和多重搜索策略, 對不同類型的染色體以

17、不同幾率進(jìn)行選擇交叉操作。用該算法測試tsp庫中的典型實(shí)例，結(jié)果顯示，對初始種群運(yùn)用單親遺傳算法，并引入基因庫方法是可行的，有效地 提高了算法的效率和收斂速度，在群體演化過程中引入多重 搜索策略的方法，提高了算法的并行性和全局尋優(yōu)性能，即 使在較少的尋優(yōu)步數(shù)也能得到適應(yīng)度不錯的局部優(yōu)化解。 gb-mga算法在提高算法求解質(zhì)量的同時兼顧了算法的效率, 但是其中還有許多有待解決的問題，比如如何構(gòu)建高質(zhì)量的 基因庫，如何對現(xiàn)有基因庫進(jìn)行優(yōu)化和擴(kuò)充，以及算法中一 些參數(shù)的選取問題等，這些方面，還需要進(jìn)一步的研究。參考文獻(xiàn)ibektb,hammelu,schwefelhcomputation :comm

18、entsont hehistoryand currentstate j.leeetran sactionsonev olutionaryco mputation,19 97,2(6):3172王磊，潘進(jìn)，焦李成.免疫算法j1.電子學(xué) 報，2000,28 (7)：74783dorig om,gambardel lalcolonysys tem：acoopera tivelearning approachtoth etravelingsa lesmanproble mjieeetra nsactionsone volutionaryc omputation,1 997,2(8):53664holl

19、andj h. adaptation innaturaland artificialsy stems m. ann arbor： theuni versityofmic higan, 155楊輝，康立山，陳毓屏一種基于構(gòu)建基因庫求解tsp問 題的遺傳算法j.計算機(jī)學(xué)報,xx,26(1 2): 175317586tsaicheng-fa, tsaichun-wei, yangtzer . amodif iedmu ltiple-searc hingmethodto geneticalgor ithmsforsolv ingtraveling salesmanprob lemj ieeet ransactionso nsystems,man andcybernetics, 2002, 3 (10 ): 6127bara gliar,hidalg oji,peregor. ahybridheuri sticforthetr avelingsales manproblemj .ieeetransa ctionsonevol utionarycomp utation, 2001 , 5 (12): 6136 228tsaichen gfa, tsaichu nwei. anewap proachforsol vinglargetra velingsalesm anproblemusi