求解TSP的离散人工蜂群算法

针对旅行商问题,提出了一种新型的离散人工蜂群算法.根据该优化问题及离散量的特点,对引领蜂、跟随蜂和侦查蜂角色转变机制和搜索策略进行了重新定义.蜂群角色转变基于定义的收益比因子.引领蜂邻域搜索采用2-Opt算子和学习操作来加速算法收敛速度;跟随蜂搜索引入禁忌表来提高算法的局部求精能力;侦查蜂搜索定义了排斥操作来保持种群的多样性,从而较好地平衡了算法的探索及开采能力.实验结果表明,算法能够在较短时间内找到相对满意解,提高了TSP的求解效率.

Discrete Artificial Bee Colony Algorithm for TSP

Aimed at traveling salesman problems， a novel discrete artificial bee colony algorithm is proposed. Based on the characteristics of such problems and discrete variables， the transforming mechanism and searching strategy of leader bees， follower bees and scout bees are redefined. The roles of bees are changed dynamically according to the values of profitability ratios. The 2-Opt operator and learning operator are used for leader bees to search the neighborhood of food sources so as to accelerate the convergence. A taboo list is introduced for follower bees to improve the algorithm’s intensification ability， and a repulsion operator is designed for scout bees to maintain the diversity of bee colonies. The proposed algorithm can strike a good balance between exploration and exploitation by using these operators. The simulation results show that it can improve the efficiency of solving traveling salesman problems by finding relatively satisfactory solutions in a short time.