Tackling Knapsack Problem With Improved Genetic Algorithm With Small Populationon

Genetic Algorithm is a self-adaptive and self-organizational artificial intelligence which simulates nature evolution to obtain best solution as possible. It regenerates population through executing genetic operations such as selection, crossover and mutation with probability to make population evolved. Because algorithm is easy to be realized and application effect is outstanding, Genetic Algorithm is applied in a lot of domains which contain self-adaptive control, combinatorial combination, pattern recognition, machine learning, and artificial life.Knapsack Problem (KP) is a typical NP's optimization problem and is widely used in many fields. So the research of GA solving KP has the important value of application.The research of GA solving KP with small population is presented in this paper. The main content is as follows:Firstly, introduce the background and the application of Genetic Algorithm. Introduce the basic theory of genetic algorithm in detail, including its working flow and the common technology that has been used in the optimization process. The schemata theorem and building block hypothesis are also expatiated in this paper.Secondly, introduce the Knapsack Problem and the premature in Genetic Algorithm. Find out the shortage with experiment.Then, improve the algorithm as follows: introduce into a parameter to weigh the sameness of chromosome which can increase the variety of the population. Secondly, in the process of crossover and mutation simulated annealing is used to accept the new individual. Thirdly, a new method in mutation is given to improve the efficiency in searching.Finally, tried with experiments of knapsack problem it concludes that the new genetic algorithm has better convergence, stability and efficiency in small population.