Research-on-Dynamic-0-1-Knapsack-Problem-Based-on-Genetic-Algorithms.

The topic of my undergraduate graduation project is Research on Dynamic 0-1 Knapsack Problem Based on Genetic Algorithms. Three variants of the standard genetic algorithm were studied for solving the dynamic combinatorial optimization problem.

Abstract:
There are many Combinatorial Optimization Problems in real-world production and life, such as allocation problems, packing problems, etc. Instead of being unchanged, most of them will change with time, so do the optimal solutions. Thus, how to solve combinatorial optimization problems in dynamic environment has a very important theoretical and practical significance.
Genetic algorithms (GAs) derived from Darwin's theory of natural selection, compliance with the "survival of the fittest, natural selection." Since Professor Holland firstly proposed it in 1975, genetic algorithm has been successfully applied to many fields.
In this thesis, starting with the existing research results, the author proposes a new method for dynamic knapsack problem which can be used to simulate loading problems and packing problems in dynamic environment. The author uses a variety of improved GAs to solve the dynamic knapsack problem. The detailed work is summarized below:
(1)Analyzed the basic concepts and implementation methods of standard GA in details and compared it with other existing optimization algorithms. Specifically discussed the classification and description of knapsack problems and described how to generate dynamic items knapsack problem.
(2)The author presented three variants of the standard genetic algorithm. The first one is random restart genetic algorithm (RRGA) which re-initializes the population whenever the environment changed. The second one is random immigrant genetic algorithm (RIGA) which substitutes a portion of worst individuals in the current population with random immigrants every generation. The third one is elitism-based immigrant genetic algorithm (EIGA) which replaces a portion of worst individuals in the current generation with the elite from the previous generation. Their performance is analyzed and compared via different dynamic environments by changing environmental parameters. The experimental results show that EIGA can be adapted for a variety of dynamic environments. Compared with other GAs, global optimal solution can be found by EIGA more rapidly and more effectively. The overall convergence of EIGA is also faster and better.
This thesis proposes a number of GAs, where different immigration mechanisms are incorporated into the framework of the standard GA. These GAs are then applied to 0-1 knapsack problems in dynamic environments. The work reported is of great significance on, not only theoretical studies of genetic algorithm for dynamic combinatorial optimization problem, but also applications to dynamic optimization problems in real life.

Keywords: Genetic Algorithm; Dynamic Knapsack Problem; Random Immigrants; Elitism-based Immigrant; Random Restart