一种改进的蚁群算法求解多维背包问题  

An Improved Ant Colony Algorithm Solving Multi-Dimension Knapsack Problem

作　　者：王小彤[1] 侯立刚[1] 苏成利[1] 

机构地区：[1]辽宁石油化工大学信息与控制工程学院,辽宁抚顺113001

出　　处：《辽宁石油化工大学学报》2015年第4期53-57,共5页Journal of Liaoning Petrochemical University

摘　　要：多维0-1背包问题是经典的非确定多项式问题(Non-Deterministic Polynomial,NP),针对蚁群算法求解该问题时易出现陷入局部最优、收敛速度慢等问题,提出了一种改进的蚁群算法。本文算法引入蛙跳算法的分群思想,将蚂蚁分为拥有不同文化的两个群体,提高了全局搜索能力;采用贪心策略修改公式,针对具体问题具体分析,提高了算法的精确度;融合轮盘赌算法简化了公式。仿真结果表明,本文算法加强了全局搜索能力,得到的结果更为精确。Multi-dimension 0-1knapsack 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.

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

分 类 号：TP202.7[自动化与计算机技术—检测技术与自动化装置]