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

1、改進(jìn)混合蛙跳算法求解旅行商問(wèn)題羅雪暉,楊燁,李霞(深圳大學(xué)信息工程學(xué)院,廣東深圳 518060摘 要:以旅行商問(wèn)題(TSP為例,引入調(diào)整序思想設(shè)計(jì)了局部搜索策略,同時(shí)在全局信息交換過(guò)程中加入變異操作,提出一種改進(jìn)混合蛙跳算法求解TSP問(wèn)題。實(shí)驗(yàn)結(jié)果表明,與遺傳算法和粒子群優(yōu)化算法相比較,改進(jìn)混合蛙跳算法在求解TSP問(wèn)題上具有更好的搜索性能和頑健性。關(guān)鍵詞:混合蛙跳算法;旅行商問(wèn)題;局部搜索;全局信息交換中圖分類號(hào):TP18 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):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ā)式計(jì)算優(yōu)化算法,用于解決離散組合優(yōu)化問(wèn)題1。作為一種新型的仿生物學(xué)智能優(yōu)化算法,SFLA結(jié)合了基于模因(meme進(jìn)化的模因演算法(MA,memetic algorithm和基于群體行為的粒子群算法(PSO, particle swarm optimization2種群智能優(yōu)化算法

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

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

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

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

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

10、i f 降序排列存儲(chǔ)于(,(,1,X U i f i i F =",然后按照特定的劃分原則將整個(gè)青蛙群體分成m 個(gè)族群Y 1,Y 2,Y m ,每個(gè)族群中包含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族群,依次類推,將所有青蛙個(gè)體劃分到3個(gè)族群中。 2.2 局部搜索

11、青蛙種群中各族群執(zhí)行局部搜索策略的目的是在不同的搜索方向上搜索局部最優(yōu),搜索迭代一定次數(shù)后使得族群中局部最優(yōu)個(gè)體逐步趨向于全局最優(yōu)個(gè)體。首先將青蛙種群劃分成多個(gè)族群,對(duì)每個(gè)族群進(jìn)行局部搜索,但是為了避免青蛙個(gè)體過(guò)早陷入局部最優(yōu),同時(shí)加快收斂速度,在每個(gè)族群中按照特定的原則選擇一定數(shù)目的青蛙構(gòu)成該族群的子族群。對(duì)于青蛙群體,具有全局最好適應(yīng)度的解表示為g U ;對(duì)于每一個(gè)子族群,具有最好適應(yīng)度的解表示為B U ,最差適應(yīng)度的解表示為W U 。首先對(duì)每個(gè)子族群進(jìn)行局部搜索,即對(duì)子族群中最差適應(yīng)度的青蛙個(gè)體進(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 表示青蛙個(gè)體的調(diào)整矢量,max s 表示青蛙個(gè)體允許改變的最大步長(zhǎng)。如設(shè)W U =1 3 5 4 2, U B =2 1 5 3 4,允許改變的最大步長(zhǎng)max s =3,若rand=0.5,則q (1U =1+minint0.5×(21,3=1; q (2U =3+maxint0.5×(13, 3=2;依此相同的操作完成更新策略后可得到一個(gè)新解q U =1 2 5 4 3。 2.3 全局信息交換全局信息交換有助于收集各族群搜

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

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

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

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

17、因子設(shè)d 個(gè)城市的TSP 問(wèn)題的解為(,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)整序一個(gè)或多個(gè)調(diào)整因子的有序排列就是調(diào)整序,記作ST ,(21N TO TO TO ST "=,其中N TO TO TO ,21"是調(diào)整因子,它們之間的順序是有意義的。A U 、B U 分

18、別為2個(gè)不同解,調(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)造一個(gè)調(diào)整序。設(shè)定A U =(1 3 5 2 4,B U =(31 42 5,需要構(gòu)造一個(gè)調(diào)整序B A (ST U U ,使得A B A B (U ST U U U +=?？梢?jiàn)12B A 3U U =,所以第一個(gè)調(diào)整因子1,2(1TO ,A1A 1U U TO =+,得到A1U =(3 1 52 4;35B A14U U =,所以第二個(gè)調(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個(gè)TSP 解序列之間的調(diào)整序之前,需要將兩個(gè)TSP 解序列轉(zhuǎn)化為均以1為起點(diǎn),預(yù)處理的目的是求解出兩個(gè)TSP 解序列之間的最簡(jiǎn)短的調(diào)整序列(即調(diào)整因子個(gè)數(shù)最少。因?yàn)樵诘?期 羅雪暉等:改進(jìn)混合蛙跳算法求解旅行商問(wèn)題 ·133·求解過(guò)程中,大多數(shù)所得的調(diào)整序是將局部最差解調(diào)整為局部最優(yōu)解的情況,為了盡可能使得調(diào)整序中調(diào)整因子個(gè)數(shù)較多,增加青蛙個(gè)體更新的多樣性,從而增加了算法搜索能力,避免過(guò)早陷入局部最優(yōu),本文在求解調(diào)整序列時(shí)

20、,不需要進(jìn)行解序列預(yù)處理。青蛙個(gè)體之間的差異是青蛙個(gè)體之間的調(diào)整序,調(diào)整序的數(shù)目為非負(fù)數(shù),所以青蛙個(gè)體的更新策略為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)整因子個(gè)數(shù),l 表示更新W U 所選用的B W (ST U U 部分調(diào)整因子個(gè)數(shù),max l 表示允許選用的最大調(diào)整因子個(gè)數(shù),S 表示更新W U 的調(diào)整序。圖1所示為青蛙個(gè)體更新的一個(gè)例子B

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

22、優(yōu)解的時(shí)間。貪婪倒位變異算子13利用了貪婪法的基本思想,其主要思想是:對(duì)某一青蛙個(gè)體U ,隨機(jī)選擇一個(gè)城市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ù),則對(duì)1+i U 到j(luò) U 之間的城市進(jìn)行倒位;反之,則對(duì)j U 與1i U 之間的城市進(jìn)行倒位。例如:對(duì)青蛙個(gè)體U (1 3 5 2 6 4 8 7 9,隨機(jī)選擇一個(gè)城市i U =5,則1+i U =2,1i U =3,離城市5最近的城市j U

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

24、行青蛙個(gè)體的更新;5 所有族群混合,每個(gè)青蛙個(gè)體進(jìn)行4.2節(jié)青蛙個(gè)體變異操作,如產(chǎn)生的新個(gè)體優(yōu)于原來(lái)個(gè)體則取代原來(lái)青蛙個(gè)體放入青蛙種群中,重新計(jì)算適應(yīng)度;6 判斷是否滿足算法收斂條件,若滿足,輸出最優(yōu)路徑序列;否則,更新全局最優(yōu)解,返回到步驟3。 5 實(shí)驗(yàn)仿真本文采用TSPLIB 14中的Burma14、Bays29、Eil51和Eil101對(duì)算法進(jìn)行測(cè)試。實(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 =,子族群中青蛙個(gè)數(shù)2/3q N =,族群中青蛙更新迭代次數(shù)IT =q ,

25、青蛙個(gè)體允許選擇的最大調(diào)整因子個(gè)數(shù)max /2l N =(其中N 表示城市數(shù)。采用平均距離對(duì)算法的性能進(jìn)行客觀評(píng)價(jià),收斂時(shí)所需的平均時(shí)間對(duì)算法運(yùn)算量進(jìn)行評(píng)價(jià);算法穩(wěn)定性的評(píng)·134· 通 信 學(xué) 報(bào) 第30卷價(jià)是基于相對(duì)誤差。實(shí)驗(yàn)仿真是以同樣實(shí)驗(yàn)條件下對(duì)每個(gè)TSP 問(wèn)題進(jìn)行50次計(jì)算機(jī)仿真的統(tǒng)計(jì)平均,結(jié)果如表1所示,其中針對(duì)不同規(guī)模TSP 問(wèn)題,第一行表示混合蛙跳算法的實(shí)驗(yàn)結(jié)果,第二行是改進(jìn)混合蛙跳算法的實(shí)驗(yàn)結(jié)果。表1 混合蛙跳算法和改進(jìn)混合蛙跳算法在不同規(guī)模TSP 問(wèn)題上的測(cè)試結(jié)果TSP 實(shí)例已知 最優(yōu)值 算法 最優(yōu)值平均 距離相對(duì) 誤差/%平均運(yùn)行時(shí)間/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注:相對(duì)誤差%100×=OptOptAvg Err 由表1可知,與混合蛙跳算法相比較,改進(jìn)算法在求解Burma14、Bays29和 Eil51問(wèn)題能夠搜索到最優(yōu)路徑,而且尋找到

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