遗传算法在0/1背包问题中的应用及研究

Application and Study of Genetic Algorithm on Knapsack Problem

遗传算法作为一种优胜劣汰的自然规律,可应用于人工智能、机器学习等多个方面。本文将遗传算法应用于0/1背包问题,首先介绍简单遗传算法,通过实验数据分析遗传算法在搜索范围、收敛速度和精度等方面的不足,进而基于贪心算法、适应度函数及遗传算子,修正可行解和不可行解,逐步改进遗传算法,防止算法陷于局部最优,提高算法的全局搜索能力和收敛速度。最后通过实验数据,比较简单遗传算法和改进遗传算法的实验结果,证明改进遗传算法在0/1背包问题应用中的精确性和高效性。

As the principle of ＂selecting the superior and eliminating the inferior＂ in biology, genetic algorithm has been widely applied on artificial intelligence, machine learning ,etc. This paper proposes the idea of genetic algorithm to solve the 0/1 package problem, it first analyzes the weaknesses of the traditional genetic algorithm in resolving 0/1 knapsack problem. A new novel improved genetic algorithm is described, which is combined with greedy algorithm, fitness function and genetic operator. Through improving the feasible and infcasible solntion, the algorithm avoids local optimum and enlarges the search space. The experiment compares the results of the two genetic algorithms and represeats that the improved genetic algorithm is more efficient and accurate than the traditional method in ghobal research and convergence speed.