繆桂根,高羽佳

(安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院物流工程系,合肥 230036)

改進(jìn)遺傳算法求解TSP問(wèn)題的M atlab程序設(shè)計(jì)

繆桂根,高羽佳

(安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院物流工程系,合肥 230036)

用改進(jìn)遺傳算法求解TSP問(wèn)題,并編制了完整的Matlab程序予以仿真實(shí)現(xiàn).程序中選擇算子采用最佳個(gè)體保存與賭輪選擇相結(jié)合的策略,最后分析了最佳個(gè)體保存比例對(duì)尋優(yōu)效果的影響.

改進(jìn)遺傳算法;TSP問(wèn)題;Matlab程序

0 引 言

旅行商問(wèn)題(Traveling Saleman Problem,TSP),又叫貨郎擔(dān)問(wèn)題,是最基本的路線問(wèn)題,該問(wèn)題是在尋求單一旅行者由起點(diǎn)出發(fā),通過(guò)所有給定的城市之后,最后再回到原點(diǎn)的最小路徑成本.該問(wèn)題具有廣泛的應(yīng)用性,如物流中的配送車輛調(diào)度問(wèn)題就可看成一個(gè)約束性多路旅行商問(wèn)題.因此,對(duì)TSP問(wèn)題求解具有一定的現(xiàn)實(shí)意義.

TSP問(wèn)題屬于組合優(yōu)化問(wèn)題,隨著問(wèn)題規(guī)模增大,其可行解空間也急劇擴(kuò)大,有時(shí)在當(dāng)前的計(jì)算機(jī)上用枚舉法很難甚至不能求出最優(yōu)解,而用啟發(fā)式算法求解這類問(wèn)題的滿意解是一個(gè)很好的方式,遺傳算法就是尋求這種滿意解的最佳工具之一.遺傳算法模擬自然進(jìn)化過(guò)程來(lái)搜索最優(yōu)解[1],其本質(zhì)是一種高效、并行、全局搜索的方法.本文采用遺傳算法求解 TSP問(wèn)題并編制Matlab程序進(jìn)行仿真試驗(yàn).

1 TSP問(wèn)題的數(shù)學(xué)模型

TSP問(wèn)題即尋找一條最短的遍歷n個(gè)城市的最短路徑,使得:

取最小值,di,i+1表示兩城市i和i+1之間的距離.

2 遺傳算法的運(yùn)行過(guò)程

遺傳算法是一種"生成+檢測(cè)"的迭代搜索算法,其運(yùn)算流程可用圖1來(lái)表示.

圖1 遺傳算法的程序

3 TSP問(wèn)題的Matlab實(shí)現(xiàn)

參數(shù)說(shuō)明:POPSIZE表示群體規(guī)模,NCITIES表示城市數(shù)目,pop表示初始種群,MAXGEN表示進(jìn)化代數(shù),Pc表示個(gè)體交叉概率,Pm表示個(gè)體變異概率.

3.1 編碼并生成初始種群

編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題,也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵環(huán)節(jié).求解TSP問(wèn)題時(shí),采用所遍歷城市的順序排列來(lái)表示各個(gè)個(gè)體的編碼是最自然的編碼方法[2],而且這種表示方法無(wú)需解碼過(guò)程,占用的內(nèi)存空間較小.

3.2 適應(yīng)度評(píng)估

適應(yīng)度用來(lái)度量群體中各個(gè)體在優(yōu)化過(guò)程中達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度.適應(yīng)度較高的個(gè)體被選中遺傳到下一代的概率較大;而適應(yīng)度較低的個(gè)體被選中遺傳到下一代的概率相對(duì)較小一些.本文用個(gè)體所表示的循環(huán)路線的倒數(shù)來(lái)作為適應(yīng)度評(píng)估值,路線越短,個(gè)體適應(yīng)度值越大.

3.3 選擇、交叉、變異

選擇操作,是從群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新種群的過(guò)程.選擇操作以個(gè)體的適應(yīng)度評(píng)估為基礎(chǔ),其主要目的是避免有用遺傳信息的丟失,從而提高算法的全局收斂性和計(jì)算效率.常用的選擇算子有賭輪選擇、聯(lián)賽選擇、最佳保留等.其中,最佳個(gè)體保存策略可保證迄今為止所得到的最優(yōu)個(gè)體不會(huì)被交叉、變異等遺傳操作所破壞,它是遺傳算法收斂性的一個(gè)重要保證條件,但它也容易使得某個(gè)局部最優(yōu)個(gè)體不易被淘汰反而快速擴(kuò)散,從而使得算法的全局搜索能力不強(qiáng),因此,最佳個(gè)體保存一般要與其他選擇方法配合使用方可取得良好的效果[4].本文采用最佳個(gè)體保存與賭輪選擇相結(jié)合的選擇策略.其運(yùn)行過(guò)程如下:對(duì)種群進(jìn)行賭輪選擇操作,找出當(dāng)前種群中適應(yīng)度最高的個(gè)體和適應(yīng)度最低的個(gè)體;如果當(dāng)前種群中最佳個(gè)體的適應(yīng)度比總的迄今為止的最好個(gè)體的適應(yīng)度還要高,則以當(dāng)前種群中的最佳個(gè)體作為新的迄今為止的最好個(gè)體.用迄今為止的最好個(gè)體替換掉當(dāng)前種群中的最差個(gè)體.此外,在每一代進(jìn)化過(guò)程中也可保留多個(gè)較優(yōu)的個(gè)體,直接將它們復(fù)制到下一代群體中.本文中用a表示最優(yōu)個(gè)體保存的比例.

[pxLengthnow1,N1]=sort(Lengthnow);%由低到高排

[pxLengthnow2,N2]=sort(-Lengthnow);%由高到低排

交叉運(yùn)算產(chǎn)生子代,子代繼承父代的基本特征.交叉算子一般包括兩個(gè)內(nèi)容:一是對(duì)種群中的個(gè)體隨機(jī)配對(duì)并按預(yù)先設(shè)定的交叉概率來(lái)確定需要進(jìn)行交叉操作的個(gè)體對(duì);二是設(shè)定個(gè)體的交叉點(diǎn),并對(duì)的部分結(jié)構(gòu)進(jìn)行相互交換.交叉算子的設(shè)計(jì)與編碼方式有關(guān).在TSP問(wèn)題中幾種有代表性的交叉算子如順序交叉、類OX交叉等,這些交叉算子在產(chǎn)生新個(gè)體的過(guò)程中沒(méi)有目的性,對(duì)于自然數(shù)編碼的TSP問(wèn)題,這些交叉可能破壞親代的較優(yōu)基因,從而使交叉算子的搜索能力大大降低.肖磊[5]等提出的受貪婪算法啟發(fā)的使適應(yīng)值上升的交叉算子,可以在很大程度上繼承父代的優(yōu)良基因,迅速優(yōu)化適應(yīng)值.本文采用該種交叉算子運(yùn)算,該程序模塊在其文中有詳細(xì)描述,此處略.

變異操作是對(duì)個(gè)體的某些基因值做變動(dòng).變異操作的目的有兩個(gè),一是使遺傳算法具有局部的隨機(jī)搜索能力,當(dāng)經(jīng)過(guò)交叉操作群體已接近最優(yōu)解領(lǐng)域時(shí),利用變異算子可以加速向最優(yōu)解收斂;二是使遺傳算法可維持群體的多樣性,以防止早熟現(xiàn)象.變異算子的設(shè)計(jì)也與編碼方法有關(guān),對(duì)于自然數(shù)編碼的TSP問(wèn)題,可采用逆轉(zhuǎn)變異、對(duì)換變異和插入變異等.逆轉(zhuǎn)變異,也稱倒位變異,是指在個(gè)體編碼中,隨機(jī)選擇兩點(diǎn)(兩點(diǎn)間稱為逆轉(zhuǎn)區(qū)域),再將這兩點(diǎn)內(nèi)的字串按反序插入到原位置中.倒位變異考慮了原有邊的鄰接關(guān)系,能將巡回路線上的優(yōu)良基因性能較好地遺傳到下一代,提高尋優(yōu)速度.針對(duì)肖磊[5]等提出的貪婪倒位變異編制程序如下.

其中,距離矩陣D可由已知條件給出,也可根據(jù)給出的城市位置坐標(biāo)編制程序計(jì)算.城市的位置坐標(biāo)可編制程序隨機(jī)產(chǎn)生.

4 仿真及結(jié)果

以文獻(xiàn)[5]中提到的中國(guó)30個(gè)城市為例,城市坐標(biāo)為W=[877;9138;8346;7144;6460;6858;8369;8776;7478;7171;5869;5462;5167;3784;4194;299;764;2260;2562;1854;450;1340;1840;2442;2538;4126;4521;4435;5835;6232].控制參數(shù)為:POPSIZE、NCITIES、Pc、Pm 可根據(jù)實(shí)際需要調(diào)整.主程序如下:

程序運(yùn)行100次結(jié)果表明,有70次直接收斂到與最優(yōu)解非常接近的解424.8693,平均在第23代左右就能收斂到最優(yōu)解,程序運(yùn)算時(shí)間平均在10 s左右.變異概率Pm可適當(dāng)取大些,因?yàn)槭茇澙匪惴▎l(fā)的倒位變異是超適應(yīng)值增加的方向發(fā)展.最佳個(gè)體保存比例a的選取對(duì)算法尋優(yōu)會(huì)產(chǎn)生很大影響,比例過(guò)大,容易早熟,比例過(guò)小,解的質(zhì)量不穩(wěn)定.筆者對(duì)a的取值以0.05∶0.05∶0.3做實(shí)驗(yàn),發(fā)現(xiàn)在a=0.10時(shí),程序運(yùn)算能取得最好的綜合效果.

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

文章用改進(jìn)遺傳算法求解TSP問(wèn)題,并編制了完整的Matlab程序予以仿真實(shí)現(xiàn).程序中選擇算子采用最佳個(gè)體保存與賭輪選擇相結(jié)合的策略,最后分析了最佳個(gè)體保存比例對(duì)尋優(yōu)效果的影響.遺傳算法中遺傳控制參數(shù)的選取對(duì)算法的影響很大,這些參數(shù)包括群體規(guī)模、編碼長(zhǎng)度、交叉概率和變異概率等.不同的問(wèn)題各算子的影響程度不一樣,因此,在實(shí)際運(yùn)算時(shí),要根據(jù)不同的問(wèn)題進(jìn)行參數(shù)的選擇.

[1]雷英杰,等.M ATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2009:8-9.

[2]儲(chǔ)理才.基于MATLAB的遺傳算法程序設(shè)計(jì)及TSP問(wèn)題求解[J].集美大學(xué)學(xué)報(bào)(自然科學(xué)版),2001,6(1):14-19.

[3]溫清芳.遺傳算法求解TSP問(wèn)題的M ATLAB實(shí)現(xiàn)[J].韶關(guān)學(xué)院學(xué)報(bào)(自然科學(xué)版),2007,28(6):18-22.

[4]郎茂祥.配送車輛優(yōu)化調(diào)度模型與算法[M].北京:電子工業(yè)出版社,2009:75.

[5]肖 磊,張阿卜,徐文進(jìn).用MATLAB求解 TSP問(wèn)題的一種改進(jìn)遺傳算法[J].廈門理工學(xué)院學(xué)報(bào),2005,13(4):38-42.

Matlab Programming for Solving TSP Based on Genetic Algorithm

MIAO Gui-gen,GAO Yu-jia

(Department of Logistics Engineering,School of Information and Computer,Anhui Agricultural University,Hefei 230036,China)

This article solves TSP with the improved genetic algorithm and compiles a complete set of Matlab procedures to be simulated.When it comes to reproduction operator,it adopts a joint strategy based on the best individual preservation and the roulette wheel selection.Finally,the article analyzes the effect on the optimization of genetic algorithm for TSP when the proportion of the best individual preservation takes different values.

improved genetic algorithm;TSP;matlab programming

TP391

A

1671-119X(2011)02-0042-04

2011-01-17

安徽農(nóng)業(yè)大學(xué)青年科學(xué)基金資助項(xiàng)目(2009zr37)

繆桂根(1984-),女,碩士,助教,研究方向:物流系統(tǒng)優(yōu)化、物流與供應(yīng)鏈管理.