东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2015, Vol. 36 ›› Issue (8): 1074-1079.DOI: 10.12068/j.issn.1005-3026.2015.08.003

• 信息与控制 • 上一篇    下一篇

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

于宏涛1， 高立群1， 田卫华2   

  1. (1. 东北大学 信息科学与工程学院， 辽宁 沈阳110819； 2. 沈阳工程学院 自动化学院， 辽宁 沈阳110136)
  • 收稿日期:2014-06-24 修回日期:2014-06-24 出版日期:2015-08-15 发布日期:2015-08-28
  • 通讯作者: 于宏涛
  • 作者简介:于宏涛(1978-)，男，辽宁鞍山人，东北大学博士研究生，沈阳工程学院讲师； 高立群(1949-)，男，辽宁沈阳人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(61273155)；辽宁省教育厅一般项目(L2014530).

Discrete Artificial Bee Colony Algorithm for TSP

YU Hong-tao1， GAO Li-qun1， TIAN Wei-hua2   

  1. 1. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China; 2. College of Automation， Shenyang Institute of Engineering， Shenyang 110136， China.
  • Received:2014-06-24 Revised:2014-06-24 Online:2015-08-15 Published:2015-08-28
  • Contact: YU Hong-tao
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

1023

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

关键词: 离散人工蜂群算法, 旅行商问题, 2-Opt, 学习算子, 排斥算子

Abstract: 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.

Key words: discrete artificial bee colony algorithm, TSP(traveling salesman problem), 2-Opt, learning operator, repulsion operator

中图分类号: