摘要
提出了一种求解0-1背包问题的遗传算法,该算法首先设计出基于适应度的自适应变异策略,提高了变异的科学性和新算法的搜索能力;然后提出了基于单位价值信息和满足约束最大化的双优化策略,提高了求解的质量.3个0-1背包问题的仿真实验表明:与已有的HGA算法和GGA算法相比,新算法在求解质量上具有一定优势.
A genetic algorithm for solving 0-1 knapsack problems（ GA-KP） is proposed. Firstly,the new algorithm designed self-adapted mutation strategy based on the fitness to improve the scientificity of mutation and the search ability of it; and then,a dual optimization strategy is presented to improve the quality of solution,which is based on the unit value information and maximization of satisfying the constraints. The three simulation experiments of 0-1 knapsack problems show that compared with the existing HGA algorithm and GGA algorithm,the new algorithm has certain advantages in solving quality.
出处
《南阳师范学院学报》
CAS
2014年第6期21-25,共5页
Journal of Nanyang Normal University
基金
河南省基础与前沿技术研究计划项目(142300410183
132300410433)
校级项目(QN2010010
QN2013040)
关键词
0-1背包问题
遗传算法
适应变异策略
双优化策略
0-1 knapsack problem
genetic algorithm
self-adapted mutation strategy
dual optimization strategy
