基于改进萤火虫算法的TSP问题

胡 楠,徐晓光

(安徽工程大学电气工程学院,安徽芜湖 241000)



基于改进萤火虫算法的TSP问题

胡 楠,徐晓光∗

(安徽工程大学电气工程学院,安徽芜湖 241000)

摘要:针对旅行商问题,提出了一种改进的萤火虫算法．首先,重新定义萤火虫个体距离、位置更新公式．其次,为了增加萤火虫群的多样性、避免过早陷入局部最优、减少算法运行时间,引入了遗传算法．最后,通过仿真实验表明,改进后的算法能在迭代次数较少的情况下更快收敛到最优解,证明了所提方法的可行性和有效性．

关 键 词:旅行商问题;改进的萤火虫算法;遗传算法

旅行商问题(Travel Salesman Problem,TSP)是最基本的路线问题,其探索单一旅行者由起点出发,并通过所有给定点后,再回到起点的最小路径成本问题[1]．求解TSP一直是组合优化领域研究的热点和难点问题之一[2]．目前,为解决TSP问题引入了各种智能算法,如遗传算法、PSO算法、蚁群算法等[3-5],然而这些方法存在计算存储量大、运行时间长、求解城市规模太小等不足．萤火虫算法(Firefly Algorithm, FA)是近年来提出的一种新型群智能算法,已经在很多领域得到了应用[6-8],通过模拟自然界中萤火虫的发光特性发展而来,同蚁群算法、鱼群算法一样,也是一种高级启发式算法[9]．针对TSP问题,在标准萤火虫算法的基础上,提出了一种改进的萤火虫算法,对萤火虫个体距离、位置更新公式进行了重新定义．为了提高萤火虫算法求解TSP问题时的收敛速度,使其找到全局最优解,在标准萤火虫算法中引入……