Currently available dynamic optimization strategies for Ant Colony Optimization (ACO) algorithm offer a trade-off of slower algorithm convergence or significant penalty to solution quality after each dynamic change occurs. This paper proposes a discrete dynamic optimization strategy called Ant Colony Optimization (ACO) with Aphids, modelled after a real-world symbiotic relationship between ants and aphids. ACO with Aphids strategy is designed to improve solution quality of discrete domain Dynamic Optimization Problems (DOPs) with event-triggered discrete dynamism. The proposed strategy aims to improve the inter-state convergence rate throughout the entire dynamic optimization. It does so by minimizing the fitness penalty and maximizing the convergence speed that occurs after the dynamic change. This strategy is tested against Full-Restart and Pheromone-Sharing strategies implemented on the same ACO core algorithm solving Dynamic Multidimensional Knapsack Problem (DMKP) benchmarks. ACO with Aphids has demonstrated superior performance over the Pheromone-Sharing strategy in every test on average gap reduced by 29.2%. Also, ACO with Aphids has outperformed the Full-Restart strategy for large datasets groups, and the overall average gap is reduced by 52.5%.
翻译:当前,蚂蚁群算法的动态优化策略在较慢的算法收敛或每次动态变化后的显著解质量惩罚之间进行权衡。本文提出了一个称为“奶牛蚂蚁”的离散动态优化策略,该策略模拟了蚂蚁和蚜虫之间的实际共生关系。通过最小化解质量罚分并最大化动态变化后的收敛速度,奶牛蚂蚁策略旨在提高事件触发的离散动态领域动态优化问题的解决方案质量。该策略在解决动态多维背包问题(DMKP)基准测试时,与完全重启和信息素分享策略相比较。结果显示,平均差距减少了29.2%。此外,在大型数据集组中,奶牛蚂蚁策略的表现优于全重启策略,总体平均差距减少了52.5%。