改進(jìn)混合蛙跳算法求解旅行商問題

1、改進(jìn)混合蛙跳算法求解旅行商問題羅雪暉,楊燁,李霞(深圳大學(xué)信息工程學(xué)院,廣東深圳 518060摘 要:以旅行商問題(TSP為例,引入調(diào)整序思想設(shè)計了局部搜索策略,同時在全局信息交換過程中加入變異操作,提出一種改進(jìn)混合蛙跳算法求解TSP問題。實(shí)驗(yàn)結(jié)果表明,與遺傳算法和粒子群優(yōu)化算法相比較,改進(jìn)混合蛙跳算法在求解TSP問題上具有更好的搜索性能和頑健性。關(guān)鍵詞:混合蛙跳算法;旅行商問題;局部搜索;全局信息交換中圖分類號:TP18 文獻(xiàn)標(biāo)識碼:A 文章編號:1000-436X(200907-0130-06Modified shuffled frog-leaping algorithm tosolve

2、traveling salesman problemLUO Xue-hui, YANG Ye, LI Xia(College of Information Engineering, Shenzhen University, Shenzhen 518060,ChinaAbstract: Modified shuffled frog-leaping algorithm to solve TSP was proposed, which presented the concept of adjustment sequence to design the strategy of local search

3、ing, and added the mutation operation in the global exchange of information. Experimental results indicate that, compared with genetic algorithm and particle swarm optimization algorithm, the proposed algorithm has more powerful search capability and more strong robustness in solving TSP.Key words:

4、shuffled frog-leaping algorithm; traveling salesman problem; local search; global information exchange1引言混合蛙跳算法是2000年由Muzaffar Eusuff和Kevin Lansey提出的一種基于群智能的亞啟發(fā)式計算優(yōu)化算法,用于解決離散組合優(yōu)化問題1。作為一種新型的仿生物學(xué)智能優(yōu)化算法,SFLA結(jié)合了基于模因(meme進(jìn)化的模因演算法(MA,memetic algorithm和基于群體行為的粒子群算法(PSO, particle swarm optimization2種群智能優(yōu)化算法

5、的優(yōu)點(diǎn)。該算法具有概念簡單,調(diào)整的參數(shù)少,計算速度快,全局搜索尋優(yōu)能力強(qiáng),易于實(shí)現(xiàn)的特點(diǎn)2?；旌贤芴惴ㄖ饕獞?yīng)用于解決多目標(biāo)優(yōu)化問題,例如水資源分配、橋墩維修、車間作業(yè)流程安排等工程實(shí)際應(yīng)用問題35。著名的旅行商問題6(TSP, traveling salesman problem是一類典型組合優(yōu)化問題,求得一條遍歷所有城市的最短回路,屬于NP難問題。對TSP問題一般分為兩大類的研究:一類著重于研究算法解決大規(guī)模實(shí)際問題7,如文獻(xiàn)7中解決的TSP問題城市規(guī)模最大達(dá)到316 228個,側(cè)重點(diǎn)在于算法能快速地有效求得可行解;另一類則是利用TSP問題來驗(yàn)證優(yōu)化算法解決離散組合優(yōu)化問題的有效性。幾十年

6、來,出現(xiàn)了很多近似優(yōu)化算法用于求解TSP 問題,基本分為2類:與問題本身特征相關(guān)的局部啟發(fā)式搜索算法,如2-Opt、3-Opt和Lin-Kernighan(LK8等。這類優(yōu)化算法多數(shù)充分收稿日期:2008-08-02;修回日期:2008-11-20基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(60772148Foundation Item: The National Natural Science Foundation of China (600772148第7期 羅雪暉等:改進(jìn)混合蛙跳算法求解旅行商問題 ·131·利用問題本身特征的相關(guān)信息有效尋找問題的局部最優(yōu)解,但是這些算法過分

7、依賴于問題本身特征,當(dāng)問題的規(guī)模擴(kuò)大后,問題本身特征的相關(guān)信息更復(fù)雜,大大增加算法計算量,使得算法搜索時間過長。獨(dú)立于問題的經(jīng)典智能優(yōu)化算法,如蟻群算法、遺傳算法、模擬退火法、粒子群算法、免疫算法等。此類算法大多數(shù)是模擬生物進(jìn)化算法,不依賴于問題本身特征,具有較強(qiáng)的全局搜索能力。近年來,許多學(xué)者將局部啟發(fā)式搜索算法和智能優(yōu)化算法相結(jié)合產(chǎn)生新型混合算法應(yīng)用于求解TSP 問題。文獻(xiàn)8提出了一種求解TSP 問題的混合遺傳算法,該算法結(jié)合了基于領(lǐng)域的LK 算法和采用了交叉逆轉(zhuǎn)算子;文獻(xiàn)9介紹了求解TSP 問題的蟻群算法,在算法中引入局部信息激素、信息激素更新策略與變參數(shù)策略等;文獻(xiàn)10提出了基于改進(jìn)粒

8、子群優(yōu)化算法求解旅行商問題,文中引入了速度變異機(jī)制和粒子自探索機(jī)制。這些研究成果表明把智能優(yōu)化算法與局部啟發(fā)式搜索相結(jié)合能有效提高算法搜索到最優(yōu)解的能力?；旌贤芴惴ㄌ岢鰰r間不長,無論在理論還是在實(shí)踐方面都處于起步階段。文獻(xiàn)11 嘗試提出了運(yùn)用混合蛙跳算法求解TSP 問題,本文在此基礎(chǔ)上引入調(diào)整序思想設(shè)計了局部搜索策略,同時在全局信息交換過程中加入變異操作,從而提出一種改進(jìn)的混合蛙跳算法求解TSP 問題。實(shí)驗(yàn)結(jié)果表明,與遺傳算法和粒子群優(yōu)化算法相比較,改進(jìn)的混合蛙跳算法在求解TSP 問題上具有更好的搜索性能和頑健性。2 混合蛙跳算法的數(shù)學(xué)模型1混合蛙跳算法(SFLA是一種受自然生物模仿啟示而產(chǎn)

9、生的基于群體的協(xié)同搜索方法。這種算法模擬青蛙群體尋找食物時,按族群分類進(jìn)行模因信息傳遞的過程?；旌贤芴惴ㄖ饕?個部分:局部搜索和全局信息交換。各族群局部搜索使模因信息在局部個體間傳遞優(yōu)化局部個體,混合全部青蛙,然后排序再分族群的過程使局部間的模因信息得到全局信息交換。局部搜索和全局信息交換一直持續(xù)交替進(jìn)行到滿足收斂條件結(jié)束為止。以下簡要介紹混合蛙跳算法的數(shù)學(xué)模型。 2.1 基本概念隨機(jī)生成F 只青蛙組成初始群體,每個青蛙個體表示問題的一個可行解為12(,d U U U U =",計算青蛙個體適應(yīng)度(i f ,其中d 表示解空間的維數(shù)。在隨機(jī)生成初始群體之后,將青蛙個體按適應(yīng)度(

10、i f 降序排列存儲于(,(,1,X U i f i i F =",然后按照特定的劃分原則將整個青蛙群體分成m 個族群Y 1,Y 2,Y m ,每個族群中包含n 只青蛙,滿足下列關(guān)系:k k k k k i f i m k U i U i f i U Y (,1(|(,(+=(1, 1, 1,; f k m i i n k m F mn =+="" (1 若設(shè)定m =3,F 只青蛙按適應(yīng)度由高到低排列,位置位于第1的青蛙分入第1族群,第2的青蛙分入第2族群,第3的青蛙分入第3族群,第4的青蛙分入第1族群,依次類推,將所有青蛙個體劃分到3個族群中。 2.2 局部搜索

11、青蛙種群中各族群執(zhí)行局部搜索策略的目的是在不同的搜索方向上搜索局部最優(yōu),搜索迭代一定次數(shù)后使得族群中局部最優(yōu)個體逐步趨向于全局最優(yōu)個體。首先將青蛙種群劃分成多個族群,對每個族群進(jìn)行局部搜索,但是為了避免青蛙個體過早陷入局部最優(yōu),同時加快收斂速度,在每個族群中按照特定的原則選擇一定數(shù)目的青蛙構(gòu)成該族群的子族群。對于青蛙群體,具有全局最好適應(yīng)度的解表示為g U ;對于每一個子族群,具有最好適應(yīng)度的解表示為B U ,最差適應(yīng)度的解表示為W U 。首先對每個子族群進(jìn)行局部搜索,即對子族群中最差適應(yīng)度的青蛙個體進(jìn)行更新操作,更新策略為B W max B W B W max B W min int(, ,

12、 0max int(, , 0 rand U U s U U S rand U U s U U =< (2q W U U S =+ (3其中,S 表示青蛙個體的調(diào)整矢量,max s 表示青蛙個體允許改變的最大步長。如設(shè)W U =1 3 5 4 2, U B =2 1 5 3 4,允許改變的最大步長max s =3,若rand=0.5,則q (1U =1+minint0.5×(21,3=1; q (2U =3+maxint0.5×(13, 3=2;依此相同的操作完成更新策略后可得到一個新解q U =1 2 5 4 3。 2.3 全局信息交換全局信息交換有助于收集各族群搜

13、索的局部·132· 通 信 學(xué) 報 第30卷信息,通過模因在全局中的傳遞,獲得新的搜索全局最優(yōu)解的方向。當(dāng)所有族群經(jīng)過一定次數(shù)的局部搜索后,將各族群中青蛙個體混合在一起,按適應(yīng)度(i f 降序排列后,重新劃分族群,這樣使得青蛙個體間的模因信息得到充分的傳遞,然后繼續(xù)進(jìn)行局部搜索,如此反復(fù)直到滿足收斂條件算法停止。3 混合蛙跳算法求解TSP 問題TSP 問題描述如下:給定d 個城市及各個城市的坐標(biāo),求一條經(jīng)過各城市一次且僅一次,起始城市和終止城市相同的最短閉合路徑。 3.1 青蛙個體位置向量表示每個青蛙個體的位置向量表示TSP 問題的一個可行解。設(shè)青蛙12(,d U U U

14、U =",其中d U U U ,21"代表d 個城市的編號,U 表示從城市1U 出發(fā)依次經(jīng)過城市d U U ,2"最后回到城市1U 的路徑。另外,青蛙個體適應(yīng)度函數(shù)(i f 定義為閉合路徑長度的倒數(shù)。3.2 子族群的構(gòu)造和青蛙個體的更新策略 子族群中青蛙個體的選擇策略是青蛙個體的選擇權(quán)重大小與適應(yīng)度的大小成正比,即適應(yīng)度越大的青蛙個體,選擇權(quán)重越大,越容易被選入子族群;反之亦然。族群中的青蛙依概率選取構(gòu)造成子族群,其概率公式為2(1/(1i P n i n n =+,1,2,i n =" (4其中,i P 表示在當(dāng)前族群中第i 青蛙被選入子族群的概率,n

15、 表示每個族群中青蛙個數(shù),族群中每個青蛙被選擇的概率之和滿足關(guān)系式11=ni i P 。2.1節(jié)中有關(guān)混合蛙跳算法的青蛙個體更新策略有可能會出現(xiàn)不可行解,所以針對TSP 問題,混合蛙跳算法中的青蛙個體更新策略為任意截取B U 中的一段路徑序列,替換W U 與之相對應(yīng)的位置,W U 其余位置的城市序號若出現(xiàn)在這段路徑序列中,則將其去除掉,反之保持不變,最后將沒有出現(xiàn)的城市序號隨機(jī)插入路徑序列中,從而生成一個新的可行解q U 。若q U 優(yōu)于W U ,用q U 更新W U ,否則,用全局最優(yōu)的g U 代替B U ,然后進(jìn)行上述相同操作,生成一個新的可行解q U 。若q U 優(yōu)于W U ,用q U

16、更新W U ,否則,隨機(jī)產(chǎn)生一個新的可行解更新U w 。 4 改進(jìn)的混合蛙跳算法求解TSP 問題雖然文獻(xiàn)11中混合蛙跳算法采用的局部搜索能保證更新解的可行性,但是隨機(jī)截取一段的操作存在盲目性,使得局部搜索容易早熟。為此,本文在文獻(xiàn)11的基礎(chǔ)上,引入調(diào)整因子和調(diào)整序思想設(shè)計了局部搜索策略,同時在全局信息交換過程中加入變異操作,從而提出了一種改進(jìn)的混合蛙跳算法求解TSP 問題。4.1 基于調(diào)整序的局部搜索策略調(diào)整序12是一個可行解向另一個可行解轉(zhuǎn)換的一個調(diào)整序列。局部搜索中子族群的最差解利用調(diào)整序思想優(yōu)化,比簡單的隨機(jī)截取一段替換更有指導(dǎo)性,所以在局部搜索中引入這種思想更新子族群的最差解。1 調(diào)整

17、因子設(shè)d 個城市的TSP 問題的解為(,i U U = 1,2,i d ="定義調(diào)整因子,(21i i TO 為將U 中的1i U 插入到2i U 位置之前,則,(21'i i TO U U +=為U 經(jīng)調(diào)整因子,(21i i TO 操作后的新解。例如,當(dāng)U =(1 3 5 2 4,調(diào)整因子為2,4(TO ,則2,4('TO U U +=(1 2 3 5 42 調(diào)整序一個或多個調(diào)整因子的有序排列就是調(diào)整序,記作ST ,(21N TO TO TO ST "=,其中N TO TO TO ,21"是調(diào)整因子,它們之間的順序是有意義的。A U 、B U 分

18、別為2個不同解,調(diào)整序B A (ST U U 表示將A U 調(diào)整為B U 的調(diào)整序,即B A B A A 12(,N U U ST U U U TO TO TO =+=+"A 12(N U TO TO TO =+" (5 構(gòu)造一個調(diào)整序。設(shè)定A U =(1 3 5 2 4,B U =(31 42 5,需要構(gòu)造一個調(diào)整序B A (ST U U ,使得A B A B (U ST U U U +=。可見12B A 3U U =,所以第一個調(diào)整因子1,2(1TO ,A1A 1U U TO =+,得到A1U =(3 1 52 4;35B A14U U =,所以第二個調(diào)整因子是3,5(

19、2TO ,A2A12(5,3U U TO =+,由此類推,可得B A 123(2,1,(5,3,(5,4ST U U TO TO TO =文獻(xiàn)12中求解2個TSP 解序列之間的調(diào)整序之前,需要將兩個TSP 解序列轉(zhuǎn)化為均以1為起點(diǎn),預(yù)處理的目的是求解出兩個TSP 解序列之間的最簡短的調(diào)整序列(即調(diào)整因子個數(shù)最少。因?yàn)樵诘?期 羅雪暉等:改進(jìn)混合蛙跳算法求解旅行商問題 ·133·求解過程中,大多數(shù)所得的調(diào)整序是將局部最差解調(diào)整為局部最優(yōu)解的情況,為了盡可能使得調(diào)整序中調(diào)整因子個數(shù)較多,增加青蛙個體更新的多樣性,從而增加了算法搜索能力,避免過早陷入局部最優(yōu),本文在求解調(diào)整序列時

20、,不需要進(jìn)行解序列預(yù)處理。青蛙個體之間的差異是青蛙個體之間的調(diào)整序,調(diào)整序的數(shù)目為非負(fù)數(shù),所以青蛙個體的更新策略為B W max minint(,l rand length ST U U l = (6B W (|(,1,2,i i S TO TO ST U U i l =" (7q W U U S =+ (8 其中,B W (length ST U U 表示調(diào)整序B W (ST U U 中全部調(diào)整因子個數(shù),l 表示更新W U 所選用的B W (ST U U 部分調(diào)整因子個數(shù),max l 表示允許選用的最大調(diào)整因子個數(shù),S 表示更新W U 的調(diào)整序。圖1所示為青蛙個體更新的一個例子B

21、W (5length ST U U =,3l =,12(,S TO TO = 3TO 。 圖1 改進(jìn)的混合蛙跳算法中局部搜索的青蛙個體更新策略4.2 全局信息交換策略 求解TSP 問題的混合蛙跳算法并未考慮到TSP問題所具有的特點(diǎn),即邊與邊之間的鄰接關(guān)系,不能很好地保留原有邊的鄰接關(guān)系,所以不能將可行解中的優(yōu)良性能很好地保留在青蛙群體中,不能提高算法的收斂速度。因此在改進(jìn)的算法中,各個族群的青蛙進(jìn)行過局部搜索之后,將全體青蛙重新混合在一起,按照一定的概率對每一個青蛙個體進(jìn)行貪婪倒位變異操作。改進(jìn)的混合蛙跳算法在全局信息交換過程中加入青蛙個體變異操作,保證了青蛙個體的多樣性,縮短算法搜索到全局最

22、優(yōu)解的時間。貪婪倒位變異算子13利用了貪婪法的基本思想,其主要思想是:對某一青蛙個體U ,隨機(jī)選擇一個城市i U ,與城市i U 左、右連接的城市分別表示為1i U ,1+i U ,然后選取除了i U 、1i U 、1+i U 以外的距離i U 最近的城市j U ,若在U 中j U 與1+i U 之間間隔的城市數(shù)少于j U 與1i U 之間間隔的城市數(shù),則對1+i U 到j(luò) U 之間的城市進(jìn)行倒位;反之,則對j U 與1i U 之間的城市進(jìn)行倒位。例如:對青蛙個體U (1 3 5 2 6 4 8 7 9,隨機(jī)選擇一個城市i U =5,則1+i U =2,1i U =3,離城市5最近的城市j U

23、 =8,則倒位后產(chǎn)生新的青蛙個體1U (1 3 5 8 4 62 7 9,如果新的青蛙個體1U 優(yōu)于青蛙個體U ,則用1U 取代U 放入青蛙群體中。 4.3 算法實(shí)現(xiàn)不失一般性,假設(shè)算法收斂的準(zhǔn)則為連續(xù)多次迭代所得TSP 路徑的總長度未有改善。以下給出改進(jìn)的混合蛙跳算法求解TSP 問題的基本步驟。 1 初始化參數(shù)(青蛙族群數(shù)m ,族群中青蛙數(shù)n (總青蛙數(shù)F =(mn ,子族群中青蛙數(shù)q ,還有族群中青蛙更新迭代次數(shù)IT 的設(shè)置; 2 隨機(jī)產(chǎn)生F 個初始可行解,并計算青蛙個體的適應(yīng)度;3 青蛙個體按適應(yīng)度降序排列劃分成m 個族群,構(gòu)造子族群;4 局部搜索。對每個族群中的子族群按4.1節(jié)的方式進(jìn)

24、行青蛙個體的更新;5 所有族群混合,每個青蛙個體進(jìn)行4.2節(jié)青蛙個體變異操作,如產(chǎn)生的新個體優(yōu)于原來個體則取代原來青蛙個體放入青蛙種群中,重新計算適應(yīng)度;6 判斷是否滿足算法收斂條件,若滿足,輸出最優(yōu)路徑序列;否則,更新全局最優(yōu)解,返回到步驟3。 5 實(shí)驗(yàn)仿真本文采用TSPLIB 14中的Burma14、Bays29、Eil51和Eil101對算法進(jìn)行測試。實(shí)驗(yàn)環(huán)境:PC 機(jī)PIV-2.8GHz CPU ,512M RAM ,Window XP ,Matlab 6.5。參數(shù)設(shè)置:青蛙群體總數(shù)10F N =,族群數(shù)10m =,子族群中青蛙個數(shù)2/3q N =,族群中青蛙更新迭代次數(shù)IT =q ,

25、青蛙個體允許選擇的最大調(diào)整因子個數(shù)max /2l N =(其中N 表示城市數(shù)。采用平均距離對算法的性能進(jìn)行客觀評價,收斂時所需的平均時間對算法運(yùn)算量進(jìn)行評價;算法穩(wěn)定性的評·134· 通 信 學(xué) 報 第30卷價是基于相對誤差。實(shí)驗(yàn)仿真是以同樣實(shí)驗(yàn)條件下對每個TSP 問題進(jìn)行50次計算機(jī)仿真的統(tǒng)計平均,結(jié)果如表1所示,其中針對不同規(guī)模TSP 問題,第一行表示混合蛙跳算法的實(shí)驗(yàn)結(jié)果,第二行是改進(jìn)混合蛙跳算法的實(shí)驗(yàn)結(jié)果。表1 混合蛙跳算法和改進(jìn)混合蛙跳算法在不同規(guī)模TSP 問題上的測試結(jié)果TSP 實(shí)例已知 最優(yōu)值 算法 最優(yōu)值平均 距離相對 誤差/%平均運(yùn)行時間/s30.88 3

26、0.88 0.00 1.84 Burma1430.8830.88 30.88 0.00 2.352 020 2 044 1.20 6.75 Bays292020 2 0202 0200.008.21428.87 436.76 1.84 17.42 Eil51428.8711428.87 430.66 0.42 22.36655 673 6.99 28.38Eil101 629629 649 3.18 42.74注:相對誤差%100×=OptOptAvg Err 由表1可知,與混合蛙跳算法相比較,改進(jìn)算法在求解Burma14、Bays29和 Eil51問題能夠搜索到最優(yōu)路徑,而且尋找到

27、最優(yōu)路徑的成功率有顯著改善。值得注意的是,混合蛙跳算法在求解Eil101問題搜索不到最優(yōu)解,而改進(jìn)算法可以搜索到最優(yōu)解。以51點(diǎn)Eil51為例,運(yùn)行10次每次迭代50代。將改進(jìn)混合蛙跳算法與混合蛙跳算法在搜索最優(yōu)值時,隨迭代次數(shù)變化的平均情況如圖2所示。由圖中可見,雖然改進(jìn)混合蛙跳算法每一次迭代需要操作的步驟增多了,但是它所需的收斂次數(shù)明顯比混合蛙跳算法少,而且搜索的平均結(jié)果也有改善,所以所耗費(fèi)的運(yùn)行時間雖然較長,但綜合考慮還是可接受范圍。 圖2 混合蛙跳算法和改進(jìn)混合蛙跳算法求解Eil51問題的搜索收斂速度對比表2給出了改進(jìn)混合蛙跳算法,改進(jìn)粒子群優(yōu)化算法15,遺傳局部搜索算法16在運(yùn)行環(huán)境大致相同的情況下求解Eil51問題所得到的算法最優(yōu)值、平均距離、相對誤差和平均運(yùn)行時間的數(shù)據(jù)結(jié)果。表2 混合蛙跳算法與其他改進(jìn)算法在求解Eil51問題上的測