摘要
多维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.
出处
《辽宁石油化工大学学报》
CAS
2015年第4期53-57,共5页
Journal of Liaoning Petrochemical University
关键词
蛙跳算法
贪心策略
蚁群算法
多维0-1背包问题
轮盘赌算法
Leap frog algorithm
Greedy strategy
Ant colony algorithm
Multi-dimension 0-1knapsack problem
Roulette algorithm
