蚁群算法参数优化及其应用

《蚁群算法参数优化及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1绪论硕士学位论文越来越多的学者，其应用范围也逐步拓展到更多的工程应用技术领域。1．3蚁群算法研究进展及其存在问题自意大利学者DorigoM提出“人工蚁群算法”后，又于1996年发表了‘'Antsystem：optimizationbyacolonyofcooperatingagents”一文【31，这是蚁群算法发展史上极为重要的奠基性论文。在这篇文章中，DorigoM等不仅系统地阐述了蚁群算法的基本原理和数学模型，还同遗传算法、禁忌搜索算法、模拟退火算法等进行了仿真实验比较，并把单纯地解决对称TSP拓展到解决非对称TSP、指派问题以及车间作业调度问

2、题。自此后的几年时间内，蚁群算法逐渐引起广大学者的关注，大量有价值的研究成果陆续发表并不断地拓宽了其应用领域。蚁群算法经过十多年的发展，其主要研究成果包括算法性能改进、算法理论和收敛性证明以及应用领域的扩展等三个方面。大量具有实际应用价值的改进算法，主要可以分为离散域算法的改进和连续域算法的改进两大类。DorigoM等【58】在基本蚁群基础之上提出了一种称之为Ant-QSystem的蚁群算法，该算法仅让循环中最短路径上的信息量作更新，并仅让信息量大的路径以较大的概率被选中，充分利用学习机制强化信息的反馈；德国学者SmtzleT和HoosH提出了另一种

3、改进的算法MMAS(最大最小蚂蚁系统)【59】，MMAS限定了信息量允许值的上下限，这样各条路径上的信息量都在最大值和最小值之间，从而避免了过早收敛的现象。除此以外，比较著名改进算法还有带精英策略的蚂蚁系统、基于优化排序蚂蚁系统及最优．最差蚂蚁系统等【4】。BilehevGA等【6川最早提出了一种连续域蚁群算法，求解问题时先使用遗传算法对解空间进行全局搜索，然后利用蚁群算法对所得结果进行局部优化；高尚等【6l】提出了一种基于网格划分的连续域蚁群算法；WangL等【62】将离散域蚁群算法中的“信息量留存”过程拓展为连续域中的“信息量分布函数”，并定义了

4、应用于连续函数寻优问题的改进算法。由于国内外的学者提出的改进算法较多，这里就不再一一列举了。对某些改进算法进行了收敛性证明，GutjahrWJ最先从有向图论的角度对一种改进蚁群算法的收敛性进行了证明K】；StuezleT和DorigoM针对具有组合优化性质的极小化问题提出了一类改进算法并对其收敛性进行了证明【5】；丁建立等【63】对一种遗传．蚁群算法的收敛性进行了Markov理论分析，并证明其优化解满意值序列单调不增且收敛；HouYH等基于不动点理论对一类广义蚁群算法的收敛性进行了初步分析【5】o自DorigoM等首次将蚁群算法应用于TSP以来，许多

5、学者对其应用进行了大量的研究工作，将其推广到诸多优化领域并且取得了丰硕的应用性成果。这些应用2硕士学位论文蚁群算法参数优化及其应用领域包括：车间作业调度问题、网络路由问题、车辆路径问题、电力系统、机器人领域、故障诊断、控制参数优化、聚类分析、数据挖掘、图象处理、武器分配、生命科学化学工业等15]。另外在蚁群算法的硬件实现上取得了突破性进展，．在算法模型改进及与其他仿生优化算法的融合方面也取得了相当丰富的研究成果等。蚁群算法发展至今取得了令人瞩目的成就，但也存在着许多尚未解决的问题，这就预示着它仍然具有广阔的发展前景。有待研究改进的主要方面有：模型的进

6、一步改进研究，主要包括提高模型的普适性和模型的智能化；蚁群算法的理论性分析，大致包括统一框架下的收敛性证明、参数的优化选择及收敛速度问题等；蚁群算法的并行实现；各种新型仿生算法的智能融合等【4’51。特别是参数的优化，对于蚁群算法的应用起到关键性的作用。因为，蚁群算法所涉及到的参数值的确定，对算法的性能和优化结果有较大的影响。据此，本文对蚁群算法参数的优化进行了一定的研究，并提出了一种参数组合优化的方案。该方案突破了传统靠经验和直觉选择参数的局限，并且较容易实现和推广。1．4论文主要工作和研究内容l、-本文在讨论蚁群算法基本模型的基础之上，分析了对蚁

7、群算法影响较大的三个参数启发式因子口、期望启发式因子∥及信息持久因子P对算法性能的影响，结合目前一些学者实验得出的参数合理范围。利用微粒群算法设计了一套参数优化方案，．对这三个参数进行组合优化。最后将这个设计方案应用到车间作业调度，并进行了仿真实验。主要工作如下：1、通过基本蚁群算法，结合TSP问题进行编程实验，研究了参数的选择对蚁群算法性能及结果的影响。根据实验数据的图形分析，确定了相关三个参数的合理取值范围，为后续参数的优化工作奠定了基础。2、根据微粒群算法，提出了一套蚁群算法参数的组合优化方案。该方案突破了传统确定参数的局限性，发挥了参数的组合

8、优化效应。3、对微粒群算法进行一定的改进，同时针对TSP问题进行编程实现并对程序运行结果进行了性能分析。．4