摘要
针对蚁群算法在求解TSP问题时,存在容易陷入局部最优,收敛速度慢,且求解时间较长的问题,提出了一种基于K-means与信息挥发速率动态调整策略的改进蚁群算法,利用K-means聚类算法将大规模TSP问题分解为数个子问题。在城市选择上,加入轮盘赌规则,对信息素更新规则进行了改进,每轮迭代时动态调整信息挥发速率。实验表明,相比蚁群算法,改进算法避免了求解陷入局部最优解,加快了算法的收敛。
When solving TSP problem,the ant colony algorithm has the problem that it is easy to fall into the local optimum,the convergence speed is full,and the solving time is long.In this paper,an improved ant colony algorithm based on K-means and dynamic volatility rate adjustment strategy is proposed.The K-means clustering algorithm is used to decompose large-scale TSP problem into several sub problems.In the city selection,the roulette rules were added,the pheromone update rules were improved,and the information volatilization rate was dynamically adjusted during each iteration.Experiments show that compared with the ant colony algorithm,the improved algorithm avoids the solution to the local optimal solution and accelerates the convergence of the algorithm.
作者
王铁
胡泓
WANG Tie;HU Hong(Harbin Institute of Technology,Shenzhen 518055,China)
出处
《机械与电子》
2020年第2期25-29,共5页
Machinery & Electronics
