作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (24): 156-157. doi: 10.3969/j.issn.1000-3428.2010.24.056

• 人工智能及识别技术 • 上一篇    下一篇

基于免疫-蚁群算法的TSP问题研究

叶 菁   

  1. (福州大学数学与计算机科学(软件)学院,福州 350108)
  • 出版日期:2010-12-20 发布日期:2010-12-14
  • 作者简介:叶 菁(1974-),男,讲师、硕士,主研方向:智能算法
  • 基金资助:
    教育部科学技术研究基金资助重点项目(206073);福建省自然科学基金资助重点项目(A0820002);福建省自然科学基金资助项目(2009J01284);福建省科技创新平台计划基金资助项目(2009J1007);福建省教育厅基金资助项目(2007JB07024)

Study on TSP Problem Based on Immune-Ant Colony Algorithm

YE Jing   

  1. (College of Mathematics and Computer Science (Software), Fuzhou University, Fuzhou 350108, China)
  • Online:2010-12-20 Published:2010-12-14

摘要: 针对蚁群算法加速收敛和早熟停滞现象的矛盾,借鉴免疫系统的自我调节机制来保持种群的多样性的能力,提出免疫-蚁群算法。该算法根据解的微观多样性、宏观多样性和弧的浓度指标动态调整路径选择概率和信息量更新策略。以数种对称和不对称TSP问题为例进行仿真实验。结果表明,该算法比一般蚁群算法具有更好的局部求精能力、收敛性和多样性,更适合于求解大规模的TSP问题。

关键词: 蚁群算法, 免疫算法, 多目标优化, 旅行商问题, 信息素

Abstract: To solve the contradictory between convergence speed and precocity and stagnation in ant colony algorithm, this paper references the ability of the self-regulation mechanism to maintain the population diversity on immune algorithm. The immune-ant colony algorithm is presented. According to micro-diversity, macro-diversity and the concentration of arc, this algroithm dynamically adjusts the selection probabilities of the paths and the trail information updating. Simulation experimental results on symmetric and asymmetric TSP show that the presented algorithm has much better intensification and diversification than that of classical ant colony algorithm and is more suitable for solving large scale TSP.

Key words: ant colony algorithm, immune algorithm, multi-objective optimization, traveling salesman problem, pheromone

中图分类号: