Abstract: Multidimension 01 knapsack problem is a typical NonDeterministic Polynomial problem. In view that ant colony algorithm solving often have local optimum and slow convergence speed problems, this article propose an improved ant colony algorithm. Based on the introduction of leap frog algorithm clustering thought, the ants have been developed into two groups with different culture, which improves the global search ability. The greedy strategy modified formula is applied in order to improve the accuracy of calculation. The formula is further simplified by roulette algorithm. Simulation results indicated that the modified algorithm improves the accuracy and global search ability.

Key words: Leap frog algorithm, Greedy strategy, Ant colony algorithm, Multidimension 01 knapsack problem, Roulette algorithm

摘要：  多维0 - 1背包问题是经典的非确定多项式问题( N o n - D e t e r m i n i s t i cP o l y n o m i a l ,N P) , 针对蚁群算法求解该问题时易出现陷入局部最优、 收敛速度慢等问题, 提出了一种改进的蚁群算法。本文算法引入蛙跳算法的分群思想, 将蚂蚁分为拥有不同文化的两个群体, 提高了全局搜索能力; 采用贪心策略修改公式, 针对具体问题具体分析, 提高了算法的精确度; 融合轮盘赌算法简化了公式。仿真结果表明, 本文算法加强了全局搜索能力, 得到的结果更为精确。

关键词: 蛙跳算法, 贪心策略, 蚁群算法, 多维0 - 1背包问题, 轮盘赌算法