一种基于Metropolis抽样准则的蚁群算法的信息素更新策略

针对蚁群优化算法的关键步骤——信息素轨迹更新过程进行了分析。在理论证明和实验验证的基础上,针对此过程提出一种基于Metropolis接受准则的信息素更新策略,并通过引入一种非齐次的模拟退火方法有效地减少算法在早期落入较差解的可能性。在系统温度较高时,算法将以较大的概率接受不同的解,进行广泛的试探,能够有效地避免算法初期陷入较差解的状况;当系统温度较低时,将以小概率接受不同的解,在算法的后期将搜索集中到迄今最优解的邻域中,保证了算法收敛的同时减少了算法的收敛时间。同时将基于Metropolis接受准则的信息素更新策略和已有的信息素更新策略在4个不同规模的TSP问题上进行对比实验,试验结果也证明了本文策略的有效性。

基于改进蚁群算法的VRPTW优化问题研究

VRPTW被证明是一个NP难题,VRPTW的意义旨在车辆数最少和路径长度最短。本文在对VRPTW的数学模型进行分析的前提下,对基本蚁群算法状态转移概率加入了时间窗限制因素,对信息素轨迹更新采用了上下限因素,且应用改进后的蚁群算法解决了算法在处理带时间窗的车辆路径问题时出现的搜索效率低、易陷入局部最优等问题。仿真结果表明,本文的改进算法与其他智能启发式算法在解决VRPTW时,具有最优路径较短、总耗时少的优势。