APG算法在TSP優(yōu)化中的應(yīng)用

張瑞星　李秀娟

摘要：為解決蟻群算法（ACO）求解TSP收斂速度緩慢、易陷入局部最優(yōu)的問題，提出一種基于蟻群的融合算法（APG）。首先在ACO的初始種群中引入精英策略，獲得精英路徑并構(gòu)建精英可行解空間；其次引入PSO模型，令精英可行解作為PSO的初始種群，加入GA中的進化策略，使粒子與Gbest進行交叉操作，再使交叉操作后的粒子發(fā)生變異，得到第二次優(yōu)化的可行解空間；最后更新ACO信息素，完成一次ACO優(yōu)化迭代過程。通過APG在TSPLIB中不同實例的驗證，結(jié)果表明，APG算法較其它路徑優(yōu)化算法能夠得到更優(yōu)路徑。

關(guān)鍵詞：TSP；ACO；精英策略；PSO；GA

DOIDOI：10.11907/rjdk.181237

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）009008104

英文標題Application of APG Algorithm in TSP Optimization

--副標題

英文作者ZHANG Ruixing， LI Xiujuan

英文作者單位（College of Electrical Engineering，Henan University of Technology，Zhengzhou 450001，China）

英文摘要Abstract：In order to solve the problem that ACO is of slow convergence and easy to fall into the local optimal when solving TSP problem，an ant colony based fusion algorithm （APG） is proposed.First of all，the elite strategy is introduced into the initial population of ACO to obtain the elite path and build the elite feasible solution space； secondly，the PSO model is introduced to make the elitist feasible solution as the initial population of PSO.The evolutionary strategy of GA is added to cross operation between particles and Gbest，and then the variation of particles after cross operation is achieved，and the second feasible solution space is obtained； finally，the ACO pheromone is updated to complete a ACO optimization iteration process.The verification results of different instances of APG in TSPLIB show that the proposed APG algorithm can get a better path than other path optimization algorithms.

英文關(guān)鍵詞Key Words：TSP；ACO；elite strategy；PSO；GA

0引言

商旅問題（Traveling Salesman Problem，TSP）作為多組合優(yōu)化的NP問題，有著很強的現(xiàn)實意義。很多領(lǐng)域的問題都可以轉(zhuǎn)化為TSP模型進行求解，如點焊機器人的路徑規(guī)劃、物流配送、車間管理調(diào)度、城市道路規(guī)劃等。

隨著人工智能的迅猛發(fā)展，目前學(xué)者們已經(jīng)提出許多智能算法并應(yīng)用于求解TSP問題中。寧桂英等[1]提出一種離散型差分進化算法解決 TSP問題。王學(xué)武等[2]將萊維飛行策略與粒子群算法結(jié)合以優(yōu)化TSP問題。吳虎勝等[3]采用離散狼群算法解決TSP問題。劉克勝等[4]提出一種免疫框架，利用免疫算法求解TSP問題。文藝等[5]提出一種改進交叉算子和基于種群相似度的更新策略，改進遺傳算法以解決TSP問題，克服了“早熟”現(xiàn)象。胡中華等[6]采用不同的動態(tài)轉(zhuǎn)移策略改進人工蜂群算法優(yōu)化TSP問題，提高了算法的收斂速度。楊進等[7]通過引入交換概念和改進貓的行為模式將貓群算法用于求解TSP問題。

蟻群算法（Ant Colony Optimization，ACO）是Marco Dorigo等[8]提出的一種具有正反饋調(diào)節(jié)能力的群體智能算法。學(xué)者們針對算法存在的問題，提出了很多改進方法。張于賢[9]針對蟻群算法信息素更新的時效性問題提出一種改進信息素更新策略，提高了算法的收斂速度。徐金榮等[10]提出一種基于啟發(fā)式遺傳信息的蟻群遺傳算法求解TSP問題，提高了算法的收斂速度。潘曉萌等[11]提出一種基于多目標Pareto支配的蟻群優(yōu)化算法，增強了算法的全局搜索能力。Ratanavilisagul C[12]提出一種基于變異策略的蟻群算法，當螞蟻陷入局部最優(yōu)時，使螞蟻的信息素發(fā)生變異，提高了算法的全局搜索能力。Niu Y等[13]提出一種隨機蟻群算法，通過優(yōu)化路徑、選擇概率更新規(guī)則和信息素更新規(guī)則，加快了算法的收斂速度。Castillo O等[14]利用分散控制原理改進蟻群算法，其核心是通過α的動態(tài)變換避免或減緩?fù)耆諗?，提高了算法的全局搜索能力?/p>

根據(jù)上文分析可知，提高蟻群算法的收斂速度與全局搜索能力是改進蟻群算法的主要切入點。本文針對蟻群算法和粒子群算法進行分析，提出一種基于蟻群的融合算法（Ant Colony Particle Swarm Genetic Algorithm，APG）求解TSP問題。實驗結(jié)果表明，APG算法對不同規(guī)模的目標優(yōu)化都能快速進行全局尋優(yōu)，得到最優(yōu)解。

1TSP問題描述

已知n個城市之間的相互距離，某個商人從其中一個城市出發(fā)，依次訪問剩余（n-1）個城市，每個城市只能訪問一次，最后返回最初城市。TSP問題即如何安排走訪城市的路線，使得路徑總長度Td最小。

Td=∑n-1i=1di，i+1+dn，1（1）

其中，di，i+1表示兩座城市之間的距離。則：

di，i+1=（xi+1-xi）2+（yi+1-yi）2（2）

式（1）為本文構(gòu)建的TSP數(shù)學(xué)模型。

2APG算法

2.1蟻群算法

蟻群算法（ACO）是人工模擬自然界中蟻群覓食行為的一種群體仿生算法[15]。螞蟻在尋找食物的過程中會在路徑上留下信息素，通過信息素彼此交流，從而選擇一條離食物源最近的路徑。

設(shè)蟻群的種群規(guī)模為m，需要遍歷的城市集為n，任意兩座城市之間的路徑長度為d，τ為兩座城市之間的權(quán)值即信息素濃度，η為啟發(fā)函數(shù)，s為任意一座城市，allowk為待訪問城市的集合，α、β分別為信息素濃度重要因子與啟發(fā)函數(shù)重要程度因子，p為螞蟻選擇下一個訪問城市的概率。概率p計算方法如下：

pkij=[τij（t）]α·[ηij（t）]β∑s∈allowk[τij（t）]α·[ηij（t）]β s∈allowk0 sallowk（3）

蟻群在釋放信息素的同時，信息素也會揮發(fā)，設(shè)揮發(fā)率為θ。如果路徑短節(jié)點的信息素濃度越來越高，而其它路徑節(jié)點的信息素濃度就會越來越少，則可形成ACO的正反饋調(diào)節(jié)機制。最后只有一條最優(yōu)路徑上擁有信息素，指導(dǎo)蟻群尋優(yōu)。信息素更新方法如下：

τij（t+1）=（1-θ）τij+ΔτijΔτij=∑nk=1Δτkij，0<θ<1（4）

2.2粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是模擬自然界鳥群協(xié)作捕食行為的一種仿生算法[16]。每個粒子代表一個目標函數(shù)的可行解，通過粒子與粒子變化率、粒子的個體極值（Pbest）和群體極值（Gbest）相互作用，不斷更新粒子，向最優(yōu)解逼近。其更新方法如下：

Vk+1i=r0Vki+r1（pki-Xki）+r2（pkg-Xki）（5）Xk+1i=Xki+VK+1i（6）

其中，Vi為粒子更新的速度，Xi為目標函數(shù)對應(yīng)粒子的適應(yīng)度值，r0、r1、r2均為分布在[0，1]上的任意數(shù)，Pi - Xi、Pg - Xi分別為粒子對個體極值與群體極值的影響程度，Xi+Vi表示粒子速度對于粒子的影響程度。

2.3APG算法思想

APG算法的核心思想是令優(yōu)秀的路徑解集合參與信息素更新，在正反饋調(diào)節(jié)作用下，指導(dǎo)蟻群在下一次優(yōu)化迭代中建立優(yōu)秀的可行解空間。分為3步：

（1）利用精英策略思想完成對可行解的第一次優(yōu)化。用m只螞蟻構(gòu)建可行解空間，將其按照路徑長短進行排序，選擇最短的前n條精英路徑作為初始參數(shù)。

（2）將n條精英路徑作為PSO的初始種群，利用粒子群算法快速收斂性質(zhì)，為避免“早熟”發(fā)生，在PSO優(yōu)化計算過程中引入遺傳算法（Genetic Algorithm，GA）中的進化策略。隨機在粒子上選擇一個區(qū)間fi～fj，用群體極值相應(yīng)區(qū)間位置上的元素代替粒子的元素，完成與群體極值的交叉操作；隨機在粒子上選擇一個元素fi，將fi與fi+1交換，完成變異操作。通過融合PSO、GA完成對可行解的第二次優(yōu)化。

（3）令經(jīng)過二次優(yōu)化后的路徑參與信息素更新，幫助蟻群在迭代中選擇優(yōu)秀路徑。

3算法設(shè)計與仿真

3.1算法設(shè)計

根據(jù)上述算法的工作原理，本文算法流程如圖1所示。

3.2MATLAB仿真與分析

為驗證本文設(shè)計APG算法的有效性，選取TSPLIB標準庫中的3個實例進行實驗，選擇ACO、PSO_GA兩種算法的優(yōu)化結(jié)果作為對比。

3.2.1Eil51問題

針對Eil51問題，設(shè)置參數(shù)如下：ACO算法，設(shè)m=200，α=0.5，β=10，θ=0.2；PSO_GA算法，設(shè)m=200；APG，設(shè)m=200，α=0.5，β=10，θ=0.2。設(shè)置迭代次數(shù)為300，分別進行10次運算，得到最優(yōu)路徑如圖2所示。

3.2.2Eil101問題

針對Eil101問題，設(shè)置參數(shù)如下：ACO算法，m=300，α=0.5，β=10，θ=0.2；PSO_GA算法，m=300；APG算法，m=300，α=0.5，β=10，θ=0.2。設(shè)置迭代次數(shù)為400，分別進行10次運算，得到最優(yōu)路徑如圖3所示。

3.2.3TSP225問題

針對TSP225問題，設(shè)置參數(shù)如下：ACO算法，m=500，α=0.5，β=10，θ=0.2；PSO_GA算法，m=500；APG算法，m=500，α=0.5，β=10，θ=0.2。設(shè)置迭代次數(shù)為500，分別進行10次運算，得到最優(yōu)路徑如圖4所示。

3.3實驗結(jié)果

表1列出了ACO算法、PSO_GA算法、APG算法在TSPLIB標準庫不同數(shù)據(jù)樣本下10次運算結(jié)果的平均值、最優(yōu)值和收斂迭代次數(shù)。在Eil51小樣本實驗中，無論是最優(yōu)值、平均值，還是收斂速度，APG算法較其它兩種算法都有明顯優(yōu)勢。在Eil101、TSP225的大型樣本實驗中，APG算法的優(yōu)化結(jié)果更加突出。上述實驗結(jié)果表明，本文設(shè)計的APG算法能夠較好地進行全局尋優(yōu)，對TSP問題能夠快速收斂得到更佳路徑。

4結(jié)語

本文提出了一種基于蟻群的融合算法，通過加入精英策略，同時融合PSO、GA算法，利用優(yōu)秀路徑得到優(yōu)化ACO信息素，有效地解決了ACO求解TSP問題時收斂速度緩慢、易陷入局部最優(yōu)的問題。通過實驗結(jié)果可知，本文設(shè)計的APG算法與其它優(yōu)化算法相比，對于求解不同規(guī)模的TSP問題，均能得到最優(yōu)解，提升了求解TSP類型問題的效率。

參考文獻參考文獻：

[1]寧桂英，曹敦虔，周永權(quán).求解TSP問題的離散型差分進化算法[J].計算機與數(shù)字工程，2017，45（11）：21362142.

[2]王學(xué)武，嚴益鑫，顧幸生.基于萊維飛行粒子群算法的焊接機器人路徑規(guī)劃[J].控制與決策，2017， 32（2）：373377.

[3]吳虎勝，張鳳鳴，李浩，等.求解TSP問題的離散狼群算法[J].控制與決策，2015（10）：18611867.

[4]劉克勝，曹先彬，鄭浩然，等.基于免疫算法的TSP問題求解[J].計算機工程，2000，26（1）：12.

[5]文藝，潘大志.用于求解TSP問題的改進遺傳算法[J].計算機科學(xué)，2016，43（s1）：9092.

[6]胡中華，趙敏.基于人工蜂群算法的TSP仿真[J].北京理工大學(xué)學(xué)報，2009，29（11）：978982.

[7]楊進，鄭允，馬良.改進的貓群算法求解TSP[J].計算機應(yīng)用研究，2017，34（12）：36073610.

[8]DORIGO M，GAMBARDELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：5366.

[9]張于賢，丁修坤，薛殿春，等.求解旅行商問題的改進蟻群算法研究[J].計算機工程與科學(xué)，2017， 39（8）：15761580.

[10]徐金榮，李允，劉海濤，等.一種求解TSP的混合遺傳蟻群算法[J].計算機應(yīng)用，2008，28（8）：20842087.

[11]潘曉萌，李冰.蟻群算法優(yōu)化和路徑規(guī)劃問題的應(yīng)用研究[J].科技通報，2016，32（6）：99103.

[12]RATANAVILISAGUL C.Modified ant colony optimization with pheromone mutation for travelling salesman problem[C].International Conference on Electrical Engineering/electronics，Computer，Telecommunications and Information Technology，2017：411414.

[13]NIU Y，ZHANG D.A randomness ant colony algorithm for solving TSP[C].Advanced Science and Industry Research Center：Proceedings of 2017 2nd International Conference on Computer，2017：5.

[14]CASTILLO O，NEYOY H，SORIA J，et al.Dynamic fuzzy logic parameter tuning for ACO and its application in the fuzzy logic control of an autonomous mobile robot[J].International Journal of Advanced Robotic Systems，2013，10（51）：110.

[15]杜鵬楨，唐振民，孫研.一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問題求解[J].控制與決策，2014（10）：17291736.

[16]李文，伍鐵斌，趙全友，等.改進的混沌粒子群算法在TSP中的應(yīng)用[J].計算機應(yīng)用研究，2015，32（7）：20652067.

責任編輯（責任編輯：何麗）