Ant colony optimization is a metaheuristic that has been applied to a variety of combinatorial optimization problems. In this paper, an ant colony optimization approach is proposed to deal with the multidimensional knapsack problem. It is an extension of Max Min Ant System which imposes lower and upper trail limits on pheromone values to avoid stagnation. In order to choose the lower trail limit, we provide a new method which takes into account the influence of heuristic information. Furthermore, a local search procedure is proposed to improve the solutions constructed by ants. Computational experiments on benchmark problems are carried out. The results show that the proposed algorithm can compete efficiently with other promising approaches to the problem.
展开▼
机译:蚁群优化是一种元启发式方法,已应用于多种组合优化问题。本文提出了一种蚁群优化方法来解决多维背包问题。它是Max Min Ant System的扩展,该系统对信息素值施加上下限,以避免停滞。为了选择下限,我们提供了一种新方法,该方法考虑了启发式信息的影响。此外,提出了一种局部搜索程序来改进蚂蚁构造的解决方案。进行了基准问题的计算实验。结果表明,该算法可以与其他有希望的解决方案有效竞争。
展开▼