一种具备簇状特征的TSP问题的ABC改进解法

An ABC Solution of TSP with Cluster Feature

摘要: 针对节点分布呈现簇状特征的旅行商问题，提出了一种改进的人工蜂群算法。根据该问题簇内节点分布的密度特点，对引领蜂、跟随蜂和侦查蜂角色转变机制和搜索策略进行了相应的调整。蜂群角色转变基于密度值的大小，引领蜂搜索基于领域优先的原则，侦查蜂搜索在陷入局部最优值时具有跳出领域约束的机制，跟随蜂搜索根据相应的跟随策略从而提高在领域内的运算速度。最后的仿真结果表明，算法对具有簇状特征的TSP问题能够在较短时间内找到满意解，在时间和精度上比经典的仿生算法具有明显的优势。

Abstract: In view of the Travel Salema Problem with cluster distribution, an improved Artificial Bee Colony algorithm is proposed. According to the density characteristics of node distribution in and outside the cluster, the role transformation mechanism and search strategy of leading bee, following bee and detection bee are adjusted accordingly. The change of the role of bee colony is based on the size of the density value. The searching strategy of the leading bee search is based on the principle of domain priority, the searching strategy of the detection bee search has the mechanism of jumping out of the domain constraints when it falls into the local optimal value, and strategy of the following bee search improves the operation speed in the domain according to the corresponding following principle. Finally, the simulation results show that the improved ABC algorithm can find a satisfactory solution to the TSP problem with cluster characteristics in a short time, and has obvious advantages over the classical bionic algorithm in time and accuracy.