基于连续空间优化问题的蚁群算法与其应用分析

《基于连续空间优化问题的蚁群算法与其应用分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华北电力大学硕士学位论文1．1选题背景及意义第一章引言弟一旱jl苗仿生优化算法是人工智能领域中一个重要的分支，其中包括模拟生物界中自然选择和遗传机制的遗传算法、模拟蚂蚁群体觅食行为的蚁群算法以及模拟鸟类群体捕食行为的微粒群算法等。上世纪90年代初期，意大利学者DofigoMacro[啦川等人从生物进化论中受到启发，通过模拟自然界中蚂蚁集体寻优的行为而提出了蚁群优化算法(AntColonyOptimization，ACO)，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法之后的一种新型的基于种群的启发式仿生

2、类进化算法。由于该算法不依赖于具体问题的数学描述，具有全局优化能力和本质上的并行性，同时比遗传算法模拟退火法等早期的进化算法具备更高的可靠性，求解时间短，易于计算机实现等优点，因而受到系统优化领域研究人员的广泛重视。如今这一新兴的仿生优化算法已经成为人工智能领域的一个研究热点。目前对其研究已经渗透到多个应用领域，并由解决一维静态优化问题发展到解决多维动态组合优化问题。如今在国内外许多学术期刊和重要国际会议上，蚁群算法已经成为交叉学科中一个非常活跃的前沿性研究问题。最初人们充分利用蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性，

3、解决了TSP问题，取得了很好的结果。随后，蚁群算法被用来求解二次分配问题(QAP)、车辆路径规划问题(VRP)、车间作业调度问题(JSP)等NP完全问题，显示出蚁群算法在求解复杂优化问题方面的优越性。近10年来的研究结果已经表明：蚁群算法用于组合优化具有很强的发现较好解的能力，是一个增强型学习系统，具有分布式的计算特性，具有很强的鲁棒性，易于与其它优化算法融合。然而，蚁群算法存在搜索时间过长、易于停滞的问题。为了克服这些缺点，不少学者提出了改进算法。例如，Dorigo和Gambardella提出蚁群系统(AntColonySyste

4、m，ACS)算法【4l，使用伪随机比例状态转移规则选择下一个城市，仅让每一代中最好的个体所走过的路径上的信息素进行更新，以加快收敛速度。Stutzle和Hoos提出最大一最小蚂蚁系统(Max-MinAntSystem。MMAS)【5’6J，对路径上的信息素进行限制，’以期克服停滞的问题。胡晓兵等人根据节点分支数动态地调整转移概率以避免算法出现停滞现象【71。朱庆保，杨志军以最近节点选择和动态信息更新策略来加速全局收敛，以一种独特的变异策略来加快局部华北电力大学硕士学位论文寻优，使收敛速度大幅度地提高【8】。陈岐，秦玲等人提出了一种具

5、有感觉和知觉特征的蚁群算法【9】，根据路径上信息量的情况动态地、自适应地决定路径选择策略，有效地缓解基本蚁群算法容易早熟、停滞和收敛速度之间的矛盾。从以上分析，蚁群算法的性能好坏就在于节点选择方法和信息素变化趋势。所以，从这两个方面对蚁群算法进行改进，采用基于分散度的自适应节点选择方式和基于自适应信息素挥发因子的信息素更新方式，提高蚁群算法的性能。蚁群算法的另一个缺点就是难以处理连续空间的优化问题。由于每个蚂蚁在每个阶段所作的选择总是有限的，它要求离散的解空间，因而它对组合优化等离散优化问题很适用，而对连续空间的优化问题的求解不能直

6、接应用。在实际控制工程的优化问题中大量遇到的是连续性问题，因此，在将优化性能良好的蚁群算法用于连续性空间优化问题时，只能利用蚁群算法的原理和人对优化函数取得的有关先验知识来构造相应的算法模型，并对算法中许多实施细节加以修正，从而确定在优化过程中蚁群协同决策所选择的移动方向，由此来求得最优解。本文提出了一种运用人工蚊群搜索的规律来求解一般函数(连续性变量空间)优化的蚁群算法模型i该模型在全局上表现为人工蚂蚁在某种先验知识和启发信息引导下的优化搜索，在局部上则采用了随机性的搜索策略。该策略能提高搜索过程的效率以及搜索状态的多样性和随机性

7、，而且不受目标函数是否连续、可微等因素的限制，为蚁群算法应用于实际优化问题提供了一条可行途径。1．2蚁群算法的研究进展自1991年意大利学者DofigoMacro等提出蚁群算法后的5年时间里，并没有在国际学术界引起广泛关注，自然这段时期在蚁群算法理论及应用上也没有取得突破性进展。到了1996年DorigoMacro等在(IEEETransactionsonSystems，Man，andCybernetics-PartB》上发表了“Antsystem：optimizationbyacolonyofcooperatingagents"一

8、文，在这篇文章中，DorigoMacro等不仅更加系统地阐述了蚁群算法的基本原理和数学模型，还将其与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较，并把单纯地解决对称TSP问题拓展到解决非对称TSP、指派问题(Qua