文档介绍：蚂蚁算法在丁问题中的应用与研究
蚂蚁算法在问题中的应用与研究
电路与系统专业
研究生廖兴新指导教师王勇
摘要
组合优化是运筹学的重要分支,主要通过对数学方法的研究寻找离散事件
的最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法
求解,属于完全问题川。随着问题规模的扩大,问题空间呈现组合爆炸特征,
无法用常规的方法求解。旅行商问题‘就是一个经典的组合优化问题,属
于完全问题。此类问题目前只能用启发式算法进行求解。
自从上世纪年代中期创立仿生学以来,人们不断地从生物进化的机理中
得到启发,提出了许多用于解决复杂优化圈问题的新方法,比如神经网络〔〕、遗
传算法、模拟退火算法、进化规划等,并成功应用于解决实际问题。由意大利
学者,,于年首先提出的蚂蚁系统
,〔,,是一种新颖的仿生进化算法,适用求解复杂组合优化
’题。蚂蚁优化算法,〔,」是一种随机搜索算法,
它基于对自然界真实蚂蚁的集体觅食行为的研究,模拟真实的蚂蚁协作过程。
算法由若干个蚂蚁共同构造解路径,通过在解路径上遗留并交换信息素提高解
的质量,进而达到优化的日的。目前,蚂蚁系统己成功应用于求解旅行商问题
仃、二次分配问题和一调度问题,取得了很好的实验效果。受其影
响,蚂蚁系统的研究已经逐渐引起了更多学者和专家的关注。虽然,该研究方
法处于研究的初级阶段,但是一些研究成果己经显示出蚂蚁系统在求解复杂优
化问题方面的优越性。
的主要特征是正反馈和隐并行性。正反馈机制可以快速发现优化解。隐
四川大学硕士学位论文
封行性通过多个个体之间的并行交换信息素可防止算法陷入局部最优解,并可
使算法收敛于解空间的个子集,有利于对解空间进行进一步搜索,发现较好
解。蚂蚁算法在处理大规模优化问题时效率很低。为此我们本文中对蚂蚁算法
提出了一些改进和对影响解的参数进行了分析,得出了一些有益的结论。
引入选路优化策略,减少了算法中蚂蚁的选路次数,显著提高了算法
的执行效率。尤其对于以往较难处理的大规模尸问题,改进算法在执行效率
上有明显的优势。
引入了蚂蚁个体差异,使得蚂蚁选路策略具有多样性。模拟实验结果
表明改进算法的收敛速度和解的质量都有明显提高。
分析在求解问题中参数对解的影响,试图找到一些规律,对同类
问题进行简化处理。
关键词蚂蚁算法,组合优化,旅行商问题,信息激素
蚂蚁算法在’陈问题中的应用与研究

代鱿
面

汕
。
,,

一一叩,
’。
,
,。
,
,
一。
,,
。

。,,
,叩。
四戈学硕士学位论文
、丫工, ,
、〕
用,,七
〔川一,。,

。,
,
。

一伽工
盯,
,
腼,
,,
一
’
洲
七
叩
叩,
用
百,,尸,
蚂蚁耳法在’问题中的应用与研究
第一章绪论
蚂蚁算法基本原理
蚂蚁优化算法,川是一种随机搜索算法,
它基于对自然界真实蚂蚁的集体觅食行为的研究,模拟真实的蚂蚁协作过程。
算法由若干个蚂蚁共同构造解路径,通过在解路径上遗留并交换信息素提高解
的质量,进而达到优化的目的。该算法最早由意大利的等人在
年提出。的主要特征是正反馈和隐并行性。正反馈机制可以快速发现优化
解。隐并行性通过多个个体之间的并行交换信息素可防止算法陷入局部最优解,
并可使算法收敛于解空间的一个子集,有利于对解空间进行进一步搜索,发现
较好解。
由上述可知,蚂蚁算法优化过程的本质在于选择机制。信息量越大
的路径,被选择的概率越大更新机制。路径上面的信息量会随蚂蚁的经
过而增长,同时也随着时间的推移遂渐减小协调机制蚂蚁之间实际上
是通过信息量来互相通信、协同工作的。这样的机制使得蚂蚁算法具有很强的
发现较好解的能力。在过去的多年,蚂蚁算法的研究和应用取得了
很大的进展,大量结果证明了算法的有效性和在某些领域的优势。但是,蚂蚁
算法也有一些缺陷。例如,由于蚂蚁中多个个体的运动是随机的,当群体规模
较大时,要找出一条较好的路径需要较长的搜索时间。为此,吴庆洪等人提出
了具有变异特征的蚂蚁算法,有机地结合了一方法,提高了算法的性能。
等人在基本的蚂蚁算法的基础上提出称为一的更一般的
蚂蚁算法,每次让信息量最大的路径以较大的概率被选中,以充分利用学习机
制,强化最优信息的反馈。为了克服在一中可能出现的停滞现象,工
等人提出了一蚂蚁系统,允许各个路径上的信息量在一个限定的范
围内变化。吴斌、史忠植提出了基于蚂蚁算法的分段求解算