现有的蚁群算法在传统算法的基础上做以下改进:路径的选择策略、信息素的更新方式、多重蚁群算法以及其他方法。
第一,路径的选择策略。
传统意义上的蚁群算法容易快速收敛到局部最优解且进化速度较慢,为了有效弥补不足,现代蚁群算法主要根据伪随机比例规则(pseudo-random proportional rule)来进行路径的构建。有了这种规则的有效指导,蚂蚁首先依照状态转移规则进行寻优操作,以便快速找到可行解;同时,为了加快算法的收敛过程,按照一定概率允许当前系统所出现的累积状态(即选择当前具有最大转移概率的城市)。通过伪随机比例规则降低算法收敛到局部最优解的概率,可以有效提高蚁群算法的优化绩效。
第二,信息素的更新方式。
基于信息素更新方式是影响蚁群算法优化性能的关键因素,国内外许多学者在原方式的基础上做了大量调整与修改,并取得了令人满意的优化结果,如运用锦标赛竞争策略、引入精英策略以提高优化绩效、在排序思想的指导下释放一定比例的信息素到所经路径上,以提升解的精确度等。(www.daowen.com)
第三,多重蚁群算法。
在多重蚁群算法中,不同于传统算法中仅有的一个蚁群,它可以同时使用多个蚁群来进行问题的求解。在解决问题的过程中,多重蚁群算法可以充分挖掘一些传统算法未探索到的优良特征,如分布式计算、本质并行性等,还可以借助蚁群群体层间的交互作用以及正信息素与负信息素效应,进行规划信息的有效交流,并在维持搜索过程中蚁群多样化的同时,使问题得到有效解决。因此,当智能体策略基本一致时,多重蚁群算法能更好地解决问题。
第四,其他方法。
蚁群算法的优点:在信息素较匮乏的初期,进化的速度比较慢;在受到较强正反馈力影响的后期,收敛速度极快。与之相反,遗传算法无法利用系统反馈的信息,但却具有较强的全局寻优能力,能够快速搜索到全局最优解。基于蚁群算法与遗传算法优势互补的特性,通过前者的耦合能力结合这两种算法,采用蚁群算法和遗传算法可以在获得精确解的同时得到信息素的初始分布,从而实现了两者优势的最大化利用。吴庆洪等针对蚁群算法收敛速度较慢的缺陷,提出了带有变异特性的改进蚁群算法,通过逆转变异方式所进行的随机变异来增加信息素数量;随机变异方式可能会降低最优解的精确程度,为了避免该问题的产生,也为了有效提高算法的性能,以遗传算法的交叉算子为基础,陈烨提出了解决该问题的改进算法。Dorigo等基于对多个蚂蚁协同效应的深入研究,提出了Ant-Q算法,这种算法结合了Q学习机制和蚁群算法,具有一般性,可以更好地搜索全局,有效地克服算法求解过程中所出现的易陷入局部最优及进化速度较慢等问题,但可能会有出现停滞现象。Gambardella等将3-Opt局部搜索法融入了蚁群算法中,提出了ACS-3-Opt算法,这种算法在提高蚁群算法计算效率和求解精度等方面效果显著。最后,为了进一步改进蚁群算法,洪炳熔等将蚁群算法具有的快速全局寻优能力与神经网络具有的广泛映射能力进行了有效结合,并呈现出复合算法独有的特性。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。