浅析自适应蚁群算法

论文导读：(2)所有通过路段的搜索路径对应的候选解均会对该路段带来信息素的增量。(3)采用了信息素均匀分配策略，即对已搜索路径中的所有路段采用同样的信息素增量，与路段的重要性无关,没有考虑当连续空间优化问题转换到有向图搜索问题时，信息素分配给可行解带来的尺度变化对于连续解空间搜索效率的影响。不同的信息素更新方式对蚁群算法的性能影响很大，比如算法的收敛效率等。为了解决这一问题，提高蚁群算法的全局收敛能力和搜索速度，提出了一种新的自适应的信息量更新策略。
关键词：蚁群算法，自适应，信息素，优化

　　1 引 言
　　受自然界中真实蚂蚁行为的启发，1991年意大利学者MDofigo等首先提出了蚁群算法 ，并将之应用于复杂组合优化问题的求解，取得了较好的效果。但该算法也存在一些缺点，如进化速度慢，易陷入局部最优等。论文大全。我国于1998年末才开始有少量公开报道和研究成果，
　　2 蚁群算法原理
　　蚂蚁在外出觅食的过程中,不断地在经过的路径上释放信息激素以便和其他的蚂蚁进行联系，这种信息激素的浓度随着经过该路径的蚂蚁数量而增大，而蚂蚁在回巢或觅食时也会选择信息激素浓度较大的路径，这就会有更多的蚂蚁选择此路径，这就是一种正反馈现象。也就是说某一路径上经过的蚂蚁越多，则后来者选择该路径的概率就越大。
　　3.基本蚁群算法的优缺点
　　3.1 基本蚁群算法的优点：
　　（1）较强的鲁棒性：对基本蚂蚁算法模型稍加修改，便可应用于其它问题。
　　（2）分布式计算。该算法是一种基于种群的拟生态系统算法，具有本质并行性，易于并行实现。
　　(3)易于与其它方法结合。该算法很容易与多种启发式算法结合，以改善算法的性能。
　　3.2 基本蚁群算法的缺点
　　(1)需要较长的计算时间，容易出现停滞现象。蚂蚁中各个体的运动是随机的，虽然通过信息激素交换能够向着最优路径进化，但是当群体规模较大时，很难在较短时间内从大量杂乱无章的路径中找到一条较好的路径。
　　(2)所有通过路段的搜索路径对应的候选解均会对该路段带来信息素的增量。而实际上，候选解并非都是最好解，这样计算信息素的增量会导致错误的引导信息，从而造成大量的无效搜索，使系统出现停滞现象。
　　(3)采用了信息素均匀分配策略，即对已搜索路径中的所有路段采用同样的信息素增量，与路段的重要性无关,没有考虑当连续空间优化问题转换到有向图搜索问题时，信息素分配给可行解带来的尺度变化对于连续解空间搜索效率的影响。
　　4.自适应蚁群算法的概述
　　蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合，这种算法在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度较慢，正反馈原理旨在强化性能较好的解,却容易出现停滞现象。这是造成蚁群算法的不足之处的根本原因．因而我们从选择策略方面进行修改，我们采用确定性选择和随机选择相结合的选择策略，并且在搜索过程中动态地调整作确定性选择的概率当进化到一定代数后，进化方向已经基本确定，这时对路径上信息量作动态凋整。论文大全。缩小最好和最差路径上的信息量的差距，并且适当加大随机选择的概率，以小于l对解空间的更完全搜索，从而可 有效地克服基本蚁群算法的不足，此算
　　法属于自适应算法。该算法按照下式确定蚂蚁由所在转移到下一个城市S
　　
　　其中，P0∈(0，1)，r是(0，1)中均匀分布的随机数。当进化方向基本确定后，简单的放大(或缩小)方法调整每一路径上的信息量，该方法不仅能够加快收敛速度，节省搜索时间，而且能够克服停滞行为的过早出现，有利于发现更好的解这对于求解大规模优化问题是有益的。论文大全。通过标准蚁群算法的对比，学者就提出了一种自适应蚁群算法。
　　5.自适应的信息更新策略
　　不同的信息素更新方式对蚁群算法的性能影响很大，比如算法的收敛效率等。如果对全部路径上的信息素进行更新，则算法不易收敛；若只是更新目前搜索到最优边上的信息素，则加强了算法的正反馈作用，导致陷入局部最优解。为了解决这一问题，提高蚁群算法的全局收敛能力和搜索速度，提出了一种新的自适应的信息量更新策略。
　　当问题规模较大时，由于信息量挥发系数的存在，使那些从未被搜索过的路径上的信息量减小到接近于0，从而降低了算法在这些路径上的搜索能力，反之，当某条路径中信息量较大时，这些路径中的信息量增大，搜索过的路径再次被选择的机会就会变得较大，这也影响了算法的全局搜索能力，此时通过固定地变化挥发系数虽然可以提高全局搜索能力，但却使算法的收敛速度降低，因而提出一种自适应的改变值的方法，将信息素更新公式：
　　其中是一个与收敛次数m成正比的函数，收敛次数m越多的取值越大，如：
　　=连续收敛次数，
　　这里c为常数，根据解的分布情况自适应地进行信息量的更新，从而动态地调整各路径上的信息量强度，使蚂蚁既不过分集中也不过分分散，从而避免了早熟和局部收敛，提高全局搜索能力。
　　6. 结 论
　　蚁群算法是一种新型的进化算法，它与其它进化算法同样存在易陷入局部最优值的缺点，通过自适应调整后的改进蚁群算法可以提高算法的全局搜索能力和收敛性能。改进后的蚁群算法具有更好的稳定性和收敛性。对传统蚁群算法容易出现早熟和停滞现象的缺陷，提出了一种动态更新信息素的蚁群算法。实验表明，改进的蚁群算法具有比传统蚁群算法更强的搜索全局最优解的能力，并具有更好的稳定性和收敛性。
　　
参考文献 :
[1] 杨德芹，一种自适应蚁群算法及其应用[J]，软件导刊，2007·11
[2] 张纪会，自适应蚁群算法[J]，控制理论与应用 ，2000.2
[3] 周燕霞，一种自适应信息素改进蚁群算法[J]，计算机系统应用，2009.10
[4] 李士勇，蚁群优化算法及其应用研究进展，计算机测量与控制，2003