一种自适应蚁群算法的研究及仿真

来源 :中国科技博览 | 被引量 : 0次 | 上传用户:pomerku
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  [摘要]蚁群算法是一种新型的群智能优化算法,自提出以来,因其正反馈性、自组织性以及并行性等优点在很多领域取得了很好的应用。本文介绍了基本蚁群算法的寻优方式和数学模型,并针对其收敛速度慢、易陷入局部最优解的缺点,采用自适应调整信息素挥发因子的值的策略进行改进。并用MATLAB软件运行了改进前后的算法程序,对比求得的结果,证明了所做改进的正确性和有效性。
  [关键词]基本蚁群算法改进蚁群算法旅行商问题
  中图分类号:K919 文献标识码:K 文章编号:1009―914X(2013)28―0488―01
  
  
  1、基本蚁群算法
  1.1 蚁群算法思想
  蚁群寻找食物过程可以这样表示,每只蚂蚁独立地搜索食物,当它们碰到一个障碍物时,就随机挑选一条可行的路径前行,同时释放出与路径长度有关的被称为信息素的化学物质。当后续的蚂蚁再次碰到这个障碍物的时候,能够感知到这种信息素的存在,就会以较大的概率选择信息素浓度较高的路径,且在这条路径上继续释放信息素,影响后来的蚂蚁,整个蚁群就通过这种正反馈过程找到了食物。
  1.2 基本蚁群算法求解TSP问题的数学模型
  为了更好地理解蚁群算法,本文以求解平面上 n 个城市的 TSP 问题为例来说明该算法的数学模型和寻优过程。TSP问题可以简单地描述為:给定n个城市和它们两两之间的直线距离,寻找一条闭合的路径,使得每个城市刚好经过一次回到出发点且总的距离最短。为模拟蚁群觅食行为,引入以下记号:m——蚁群中蚂蚁总数;n——城市个数; ——¬¬¬¬¬城市i与城市j之间的直线距离; ——路径(i,j)的能见度; ——启发因子; ——期望启发因子; ——信息素挥发因子 , 即为信息素的残留系数; ——蚂蚁完成所有城市周游在所经过的路径上释放的信息素总量; ——时刻t路径(i,j)上残留的信息素量; ——一次循环中蚂蚁在所经路径(i,j)上的信息素增量; ——第k只蚂蚁在一次循环中留在路径(i,j)上的信息素量; ——t时刻蚂蚁k由城市i转移到城市j的概率。
  在初始时刻,各条路径上都有一定量且相等的信息素浓度,即设 常数。蚂蚁k在搜索过程中根据各条路径上信息素浓度决定其转移方向,在t时刻,蚂蚁k由城市i选择城市j的概率公式 可表示为:
  (1)
  其中, 表示蚂蚁k下一步能够选择的城市集合, 为用来记录蚂蚁k当前已经走过的城市集合的。蚂蚁在所经过的路径上留下信息素,同时随着算法的进行,以前留下的信息素也会逐渐流逝,因此,需要对路径上的信息素每隔一段时间进行更新处理。设(t+n)时刻,蚂蚁要对路径(i,j)上的信息素进行更新处理,其更新公式如下:
   (2)
   (3)
   (4)
  其中 表示第k只蚂蚁在完成一次循环后所走路径的总长度。
  2、自适应蚁群算法
  在蚁群算法中,信息素挥发因子 的取值对算法的全局搜索能力及收敛速度有着较大的影响[3]。由于信息素挥发因子 的存在,使那些从未被搜索到路径上的信息量会减小到接近于0,这样就降低了算法搜索全局最优解的能力。根据公式(1)和(2),解的信息素浓度会随着 的增大而增大,那么以前搜索过的解就会以很大的概率被再次搜索到,这就降低了算法搜索全局最优解的能力。然而,减小 虽然可以提高算法的全局搜索能力,但又会增加搜索时间降低收敛速度。因此本文对此进行了改进,让信息素挥发因子 的取值在搜索过程中自适应地改变大小来提高算法的全局搜索能力而又不降低其收敛速度;如果蚁群算法求得的最优值在一定次数循环内没有明显改进,则对信息素挥发因子 按照以下公式作自适应调整:
  (5)
  上式中,用 作为为 的最小值来防止因它的值过小而降低算法的收敛速度。
  3、仿真实验
  根据以上所述,本文选用TSP库中的30个城市的TSP问题,用MATLAB软件进行编程求解。30城市的位置坐标为:
  [41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;64,60;18,54;22,60;83,46;91,38;25,38;24,42;58,69;71,71;74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44,35;4,50],城市距离理论值为423.7406。根据相关文献[4],本文选用的参数组合为: 、 、 、 、 以及信息素初始值取为1。用MATLAB软件对基本蚁群算法和自适应调整信息素的蚁群算法各进行20次仿真,记录每次迭代时间和求得的解,取其中最优解、最差解和计算的平均解、平均时间以及误差率制作表1。其中:
  
  4、结束语
  本文对基本蚁群算法做了较详细的介绍,并且针对其容易陷入局部最优和收敛速度慢的问题,采用自适应调整信息素挥发因子的策略来改进算法。用MATLAB软件运行了改进前后的蚁群算法程序,对比改进前后蚁群算法的求解结果可知,改进后的蚁群算法求得的最优解、最差解、平均解、误差率以及所用的平均时间都要优于改进前的基本蚁群算法,即能用较短的时间求得较好的解,而且满足误差条件。
  参考文献:
  [1]Dorigo M.,Gambardella L M.Ant colonies for the travelling salesman problem[J].Biosystems.1997,43(2):73-81.
  [2]孙昌志,曲春雨,陈东阳.改进蚁群算法及其在永磁同步电机设计中的应用[J].沈阳工业大学学报2006,28(6):601.2008,22(1):9-11.
  
其他文献
[摘要]在高中英语课堂中运用图片,能调动学生的积极性,激发学生的思维空间;大幅度提高课堂教学的效率;并对学生的听、说、读写技能有极大帮助。正如心理学研究表明,通过视觉感知情景,加深影像和文字的结合、理解、记忆来掌握语言的效果比单纯的听或读要好。图片教学具有独特的教学效果,在教学中大大增加了学生的英语语言机会,提高了学生的英语学习兴趣和掌握运用英语的能力。  [关键词]图片学习兴趣课堂氛围语言知识视
期刊
[摘要]当前,我国民航发展已经进入了一个新的快速增长的时期,民用飞机和基础设施不断增多,资金收入和大众需求逐渐增加,这就需要更多的专业技术稀有人才和高层管理人才。因此,我国民航事业的发展离不开人才的支持。本文结合民航空中交通管制的概念和特点,具体分析了当前我国民航空中交通管制的现状,并对未来我国民航空中交通管制做出了科学的前景展望。  [关键词]民航空中交通管制特点现状分析前景展望  中图分类号:
期刊
[摘要]本文主要阐明天行动导向教学法的涵义,阐述对行动导向教学的理解,提出了行动导向教学法在实践应用中应遵循能力本位、自主活动和领域学习的三个重要原则,介绍了行动导向教学法之应用方法,可作职业教育同行们参考借鉴。  [关键词]行动导向教学原则应用方法  中图分类号:U642.6+4 文献标识码:U 文章编号:1009―914X(2013)28―0493―01       行动导向(Handlung
期刊
中图分类号:D422.62 文献标识码:D 文章编号:1009―914X(2013)28―0490―01       高职高专思想政治教育的本质是一种培养人、塑造人、转化人、发展人、完善人的社会性教育活动,是一门人文色彩很浓的学科,具有广泛而深厚的人文关怀内涵。加强和改进思想政治教育,致力于推进思想政治教育的创新发展,体现时代性、把握规律性、富于创造性,积极探寻新形势下思想政治教育的新特点和新规律
期刊
[摘要]铁路作为国民经济的大动脉、国家重要基础设施和大众化交通工具,在中国经济社会发展中具有重要作用。近年来随着高速铁路的飞速发展,对轨道要求很高的平顺性和精确的几何线性参数,本文对高速铁路的精密测量方法、原理、步骤以及未来发展方向。  [关键词]高速铁路测量工程技术  中图分类号:U892. 3 文献标识码:U 文章编号:1009―914X(2013)28―0496―01       1 概述 
期刊
[摘要]面对新的教育形势,为了搞好自己的中学数学教学,我不断提升个人教育教学水平,努力做到与新课改接轨,创新教学手法,与时俱进,取得了很好的教学效果。特别近几年来,又领略了不少教授的新基础教育实验,更加树立了我对教学改革的决心。在专家教育理论的引领下,我精心研究,细致推敲,将理论與教学实践相结合,总结出了一套行之有效的教学模式。  [关键词]中学数学教学模式  中图分类号:H09 文献标识码:H
期刊
[摘要]电工电子技术是一门相对比较抽象难学的课程,本文通过从怎么学习基础概念,如何更好的做实验,怎么调动学生的学习积极性,以便为更好的做好工学结合,理实一体入手,分析了在电工电子教学中常见到的典型问题,为高职高专电工电子的教学提供一些参考。  [关键词]电工电子教学  中图分类号:TD6 文献标识码:TD 文章编号:1009―914X(2013)28―0489―01       电工电子技术在机电
期刊
[摘要]教无定法,贵在得法。好的教学方法,不仅让教师感受到教的乐趣和创造的价值,也会让学生感受到学的乐趣和求知的真谛。在多年的语文教学中,有些尝试颇有收益,效果良好,为巩固成果,再接再厉,特整理如下:一、上好“印象课”。每接一班学生,第一次上課很重要,要给学生留下个性鲜明的印象,激发学生兴趣,争取学生信任。二、坚持课前积累,培养良好的学习习惯。语文学习的真谛在于积累,有量的积累,逐步才能发生质的变
期刊
[摘要]工程力学作为中职学校机械专业的一门专业基础课,对专业课的学习起着重要的桥梁作用,如何提高工程力学的教学质量显得很重要。在教学过程中遇到的最大问题是老师难讲,学生难学,教学效果往往不太理想。针对这一问题,本文就如何提高工程力学的教学质量谈一些看法。  [关键词]工程力学教学质量有效教学工程实践  中图分类号:TB12 文献标识码:TB 文章编号:1009―914X(2013)28―0486―
期刊
[摘要]在教学中,教师要经常研读《义务教育数学课程标准》,力争准确整体地把握教材,还要精心设计每一个教学环节,特别注意教学中细节的处理,以达到实现高效课堂。  [关键词]小学数学课堂效率高效课堂  中图分类号:Z822.7 文献标识码:Z 文章编号:1009―914X(2013)28―0492―01       2001年,我国启动了新世纪基础教育改革。经过十几年的探索,课程改革取得了显著成效。随
期刊