基于蚁群数量动态调整的改进蚁群优化算法

蚁群优化（ACO）算法是一种常用的元启发式算法，它通过模拟蚁群寻找食物的过程，为求解多维背包问题（MKP）等NP难（Non-deterministic Polynomial hard）问题提供可行途径。原始ACO算法及其改进算法，通常分为多个轮次，每个轮次均会生成一个蚂蚁种群寻找可行解。在不同轮次中，每轮蚁群中蚂蚁的数量是固定的，因此，如果将其指定一个较大的值，会导致算法出现不必要的时间消耗；反之，如果指定的值较小，则会降低算法全局最优解搜索能力。为此，提出了一种基于蚁群数量动态调整的改进蚁群优化算法ACO-ANDA(ACO algorithm based on Ant Number Dynamic Adjustment)，所提算法在可行解搜索过程中，引入了一种新的蚁群数量动态调整机制。在每轮可行解搜索结束后，均根据近几轮可行解和历史最优解之间的关系，调整下一轮蚁群数量，实现对算法时间耗费和最优解搜索能力的平衡。再基于MKP基准测试集SAC-94的多组实验结果表明，相较于原始ACO算法，所提算法能够在最优解利润平均降低0.02%的情况下，平均降低77.85%的时间耗费。