求解旅行商问题的离散人工萤火虫算法  

Discrete Artificial Firefly Algorithm for Solving Traveling Salesman Problems

作　　者：于宏涛[1] 高立群[1] 韩希昌[2] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819 [2]沈阳工程学院自动化学院,辽宁沈阳110136

出　　处：《华南理工大学学报（自然科学版）》2015年第1期126-131,139,共7页Journal of South China University of Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61273155);辽宁省教育厅一般项目(L2014530)~~

摘　　要：针对旅行商问题,提出了一种结合变邻域搜索算法思想的离散人工萤火虫算法.文中通过引入交换子和交换序的概念对人工萤火虫算法中的距离进行了重新定义;为了增加萤火虫群的多样性,避免算法过早陷入局部最优,采用了基于变邻域搜索算法的扰动机制.在多个旅行商问题上的测试结果表明,与文献中的算法相比,文中提出的离散人工萤火虫算法具有较好的求解性能.Proposed in this paper is a discrete artificial firefly algorithm combined with variable neighborhood search algorithm, which is used to solve traveling salesman problems. First, the distance of artificial firefly algorithm is redefined by introducing the concepts of swap operator and swap sequence. Secondly, in order to increase the diversity of firefly swarms and to avoid quick convergence to local optimal solution, a perturbation mechanism is designed on the basis of variable neighborhood search algorithm. Then, several different traveling salesman problems are solved by using the proposed algorithm, and the results fina!ly show that the proposed algorithm is superior to the typical ones in literatures because it helps obtain good sdlving results.

关 键 词：人工萤火虫算法 变邻域搜索 旅行商问题 组合优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]