Abstract: A new type of ant colony algorithm based on the dissimilarity of the solutions is presented to solve the 0-1 knapsack problem. In the algorithm, the paper introduces the mechanism of local pheromone updating and the operation of mutation in which the operation probability is decided by the dissimilarity of the solutions. Experimental results show that the method has high convergence speed, diversity of the solutions and high generality.

Key words: Knapsack problem; Ant colony algorithm; Local pheromone updating

摘要： 针对经典的0-1 背包问题，提出一种基于解的相异度的新的蚁群优化算法，该方法引入信息量的局部更新机制，并根据解的相异程度确定解的交叉概率。数值实验计算表明，该算法加快计算速度的同时保证了解的多样性，具有较好的通用性。

关键词: 背包问题；蚁群算法；局部更新