蚁群优化算法的理论研究及其应用

蚁群优化算法（ant colony optimization，ACO）是基于蚂蚁群体觅食过程中沿最短路径行进的生物学行为发展起来的一类群智能优化方法。该算法在解决传统优化方法难以奏效的具有NP-hard特性的组合优化问题中取得了令人鼓舞的效果，因而受到学术界和工业界的广泛关注。目前，蚁群优化算法已成为计算智能方法中的一个重要分支，并在很多国际会议上作为专题加以讨论，成为蓬勃发展的热点研究课题。 蚁群优化算法的理论研究相对滞后，特别是算法的参数选择和收敛性证明方面还有许多问题有待进一步研究。网络路由问题的很多特征，如信息的分布式特性、动态性和异步性等与蚁群算法的特征匹配得很好，因此利用蚁群优化算法解决网络路由问题一直倍受关注。此外，将蚁群优化算法与其它仿生优化方法进行巧妙的融合、互补长短是近年来蚁群优化算法的另一个热点研究方向。 本文致力于以上问题的研究，主要研究内容及创新点包括以下几方面： 1、在将组合优化极小化问题映射为全连通图的基础上，对蚁群优化算法的参数设置进行了研究。证明了信息素增量Δτ是介于最大伪可行解smax和最小伪可行解smin之间的量，即g(smax)≤Δτ≤g(smin)，为信息素初值的选取提供了理论依据：进一步紧缩了信息素挥发系数ρ的取值范围，由ρ（?）(0，1)变为ρ（?）(0，1-(emin／emax)1／t0)，其中emin和emax分别表示构造图中的最小和最大权值，t0表示算法的有效迭代次数；最话给出了最大迭代次数Itermax的估算公式。 2、在收敛性证明方面：证明了当蚂蚁数目和迭代次数的乘积趋于无穷时算法将以概率1找到全局最优解的结论；对使算法以概率P*（m，t）找到全局最优解所需m·t的上界进行了研究；对在假设算法找到最优解的情况下，通过信息素更新使最优解“凸现”出来的时刻进行了讨论；最后证明了在已经找到最优解的情况下，任意蚂蚁构造最优解的概率下界为完全随机算法构造任意解的概率（?）。 3、提出了归一化蚁群优化算法框架ACO-UF，并在ACO-UF下实现了MMAS算法，以TSP为例对其参数设置进行了研究。ACO-UF在标准ACO的基础上作了两点改进，即问题的归一化预处理和信息素初值的统一设定，克服了标准ACO受同形问题的困扰和信息素初值选取经验性强的不足。 4、提出了一种基于蚁群优化的分布式QoS多播路由算法DMRACO，并结合多播路由问题的特点对算法进行了改进。DMRACO可方便的避免循环回路的产生，引起的额外负载较小，具有合理的链路建立时间。通过仿真实验讨论了网络规模、多播规模和时延限制对DMRACO性能的影响，并与BSMA算法和KMB算法进行了比较，验证了该方法的有效性。 5、提出了一种将ACO与BP算法相融合共同完成反传神经网络训练的方法，ACO-BP算法。该算法首先采用ACO对网络权值进行整体寻优，克服BP算法容易陷入局部最优的不足；再以找到的较优的权值为初值，采用BP算法做进一步的寻优，克服单一ACO训练网络时间较长、精度不高的缺点。以函数逼近问题为例，将ACO-BPNN与ACONN、BPNN和遗传神经网络进行了比较，验证了该方法的优越性。将ACO-BPNN用于煤灰熔点的建模问题，将其预测结果与BPNN模型和经验公式的结果进行了比较，验证了该ACO-BPNN灰熔点模型的有效性，具有一定的工程应用价值。