高级检索

    基于变异和信息素扩散的多维背包问题的蚁群算法

    An Ant Colony Optimization Algorithm Based on Mutation and Pheromone Diffusion for the Multidimensional Knapsack Problems

    • 摘要: 针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足,提出一种新的高性能的蚁群求解算法.算法将信息素更新和随机搜索机制的改进相融合.首先,基于对较优解的偏爱,采用Top-k策略从每次迭代的k个解中挖掘出对象间的关联距离;其次,以对象为信源借助关联距离建立信息素的扩散模型,通过信息素扩散的耦合补偿,强化了蚂蚁间的协作和交流;最后,利用一种简单的变异策略对迭代的结果进行优化.在通用数据集上的大量实验表明:与最新的蚁群算法相比,新算法不仅能获得更好的最优解,而且收敛速度有显著的提高.

       

      Abstract: Ant colony optimization (ACO) algorithm is a metaheuristic and stochastic search technology, which has been one of the effective tools for solving discrete optimization problems. The multidimensional knapsack problem (MKP) is a classical combinatorial optimization problem, whose goal is to find a subset of objects that maximizes the total profit while satisfying some resource constraints. There are many algorithms to effectively solve MKPs, where ACO algorithm is a new and robust method. However, there are two bottlenecks in which the ACO algorithm takes too much time and solves imprecisely for large-scaled MKP. In this paper, a novel ACO algorithm with high performance is proposed, which syncretizes the improvements of the pheromone updating and the stochastic search scheme. Firstly, in light of the preference to better solutions, the association distances among objects are mined in each cycle with a Top-k strategy. Then a pheromone diffusion model based on information fountain of an object is established, which strengthens the collaborations among ants. Finally, a simple mutation scheme is employed to optimize the evolution results of each step. The experimental results on the benchmark testing set of MKPs show that the proposed algorithm can not only get much more optimal solutions but also greatly enhance convergence speed compared with the latest improved algorithms.

       

    /

    返回文章
    返回