背包问题中的遗传算法变异算子研讨.doc

JIANGXI AGRICULTURAL UNIVERSITY 本 科 毕 业 论 文（设 计） 题目： 背包问题中遗传算法的变异算子研究 学 院： 理学院 姓 名： 学 号： 专 业： 信息与计算科学 年 级： 2009级 指导教师： 职 称： 二〇一三 年 五 月  摘要 背包问题是管理科学和计算机领域的NP难题,对于大规模问题,目前的主流算法是遗传算法等进化算法. 而变异算子是遗传算法能否找到全局最优解的关键之一. 但是目前专门针对背包问题的变异算子研究并不多. 鉴此, 本文旨在研究,具有不同变异算子的遗传算法在解0-1背包问题时的性能表现. 本文首先介绍了0-1背包问题的数学模型及其求解的意义. 然后,介绍了遗传算法的主要算子及其优缺点,并详细介绍了遗传算法的变异算子. 本文通过对变异算子的不同改进,得到不同的遗传算法,并且将这些不同算法进行实验测试,以期得到具有最佳变异算子的遗传算法. 最后通过数值实验,比较了不同变异算子的优缺点. 基于0-1背包问题的仿真实验表明：不同变异算子会影响遗传算法的收敛速度和计算精度,在性能上各有优劣. 关键词：遗传算法；变异算子；背包问题；MATLAB  Abstract Knapsack problem is a NP hard problem which is widely involved in management science and computer science. The most popular algorithms to solve the large scale problems are evolutionary algorithms, such as genetic algorithm and so. It is well known that the mutation operator is the key operator of the genetic algorithm. But there are few literatures dedicated to study the impact of mutation operator in genetic algorithm to solve the knapsack problem. In view of this, this paper aims to study the performance of the genetic algorithms with different mutation operator in solving the 0-1 knapsack problem. Firstly the mathematical model of 0-1 knapsack problem and its significance are introduced. Then, the operator of genetic algorithm and its advantages and disadvan- tages are discussed. With different mutation operators designed, four genetic algorithms are presented accordingly. Finally, the numerical experiments were conducted to test the performance of the different algorithm. Simulation results in solving the 0-1 knapsack problems indicate that different mutation operator will affect the performance of the genetic algorithm in it’s convergence speed and computational accuracy. Key words : genetic algorithm；mutation operator；knapsack problem；  目录 1 背包问题 1